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

Changhee Joo; Ness B. Shroff

doi:10.1109/TNET.2008.2010857

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

Changhee Joo, Ness B. Shroff

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	1481-1493
Number of pages	13
Journal	IEEE/ACM Transactions on Networking
Volume	17
Issue number	5
DOIs	https://doi.org/10.1109/TNET.2008.2010857
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

Access to Document

10.1109/TNET.2008.2010857

Cite this

@article{c773f21dc96843c4b2e40f002b2fbc24,

title = "Performance of random access scheduling schemes in multi-hop wireless networks",

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.",

keywords = "Capacity region, Communication systems, Multi-hop wireless networks, Random access scheduling, Stability",

author = "Changhee Joo and Shroff, {Ness B.}",

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{\textquoteright}07.",

year = "2009",

doi = "10.1109/TNET.2008.2010857",

language = "English",

volume = "17",

pages = "1481--1493",

journal = "IEEE/ACM Transactions on Networking",

issn = "1063-6692",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

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 -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this