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 language | English |
---|---|
Pages (from-to) | 1481-1493 |
Number of pages | 13 |
Journal | IEEE/ACM Transactions on Networking |
Volume | 17 |
Issue number | 5 |
DOIs | |
Publication status | Published - 2009 |
Externally published | Yes |
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