Performance of random access scheduling schemes in multi-hop wireless networks

Changhee Joo, Ness B. Shroff

Research output: Contribution to journalArticlepeer-review

51 Citations (Scopus)


The scheduling problem in multi-hop wireless networks has been extensively investigated. Although throughput optimal scheduling solutions have been developed in the literature, they are unsuitable for multi-hop wireless systems because they are usually centralized and have very high complexity. In this paper, we develop a random-access based scheduling scheme that utilizes local information. The important features of this scheme include constant-time complexity, distributed operations, and a provable performance guarantee. Analytical results show that it guarantees a larger fraction of the optimal throughput performance than the state-of-the-art. Through simulations with both single-hop and multi-hop traffics, we observe that the scheme provides high throughput, close to that of a well-known highly efficient centralized greedy solution called the Greedy Maximal Scheduler.

Original languageEnglish
Pages (from-to)1481-1493
Number of pages13
JournalIEEE/ACM Transactions on Networking
Issue number5
Publication statusPublished - 2009
Externally publishedYes


  • Capacity region
  • Communication systems
  • Multi-hop wireless networks
  • Random access scheduling
  • Stability

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Performance of random access scheduling schemes in multi-hop wireless networks'. Together they form a unique fingerprint.

Cite this