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

Changhee Joo, Ness B. Shroff

Research output: Contribution to journalArticlepeer-review

52 Citations (Scopus)

Abstract

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
Volume17
Issue number5
DOIs
Publication statusPublished - 2009
Externally publishedYes

Bibliographical note

Funding Information:
Manuscript received September 27, 2007; revised June 23, 2008; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor I. Stavrakakis. First published March 16, 2009; current version published October 14, 2009. This work was supported in part by the ARO MURI Awards W911NF-07-10376 (SA08-03) and W911NF-08-1-0238, and by NSF Awards 0626703-CNS, 0635202-CCF, and 0721236-CNS, and by AFOSR FA 9550-07-1-0456, USA, and in part by the IT Scholarship Program supervised by the Institute for Information Technology Advancement and Ministry of Information and Communications, Republic of Korea. A preliminary version of this work was presented at IEEE INFOCOM’07.

Keywords

  • 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

Fingerprint

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