TY - JOUR
T1 - Performance of random access scheduling schemes in multi-hop wireless networks
AU - Joo, Changhee
AU - Shroff, Ness B.
N1 - 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.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - Capacity region
KW - Communication systems
KW - Multi-hop wireless networks
KW - Random access scheduling
KW - Stability
UR - http://www.scopus.com/inward/record.url?scp=70350558445&partnerID=8YFLogxK
U2 - 10.1109/TNET.2008.2010857
DO - 10.1109/TNET.2008.2010857
M3 - Article
AN - SCOPUS:70350558445
SN - 1063-6692
VL - 17
SP - 1481
EP - 1493
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 5
ER -