Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks

Changhee Joo; Xiaojun Lin; Ness B. Shroff

doi:10.1109/TNET.2009.2026276

Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks

Changhee Joo, Xiaojun Lin, Ness B. Shroff

Research output: Contribution to journal › Article › peer-review

129 Citations (Scopus)

Abstract

In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multihop wireless networks. While a lower bound on the throughput performance of GMS has been well known, empirical observations suggest that it is quite loose and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. We show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K-hop interference model. Then, we show that the worst-case efficiency ratio of GMS in geometric unit-disk graphs is between 1/6 and 1/3.

Original language	English
Pages (from-to)	1132-1145
Number of pages	14
Journal	IEEE/ACM Transactions on Networking
Volume	17
Issue number	4
DOIs	https://doi.org/10.1109/TNET.2009.2026276
Publication status	Published - 2009
Externally published	Yes

Bibliographical note

Funding Information:
Manuscript received July 01, 2008; revised January 21, 2009. First published July 21, 2009; current version published August 19, 2009. This work was supported in part by NSF awards CNS-0626703, CNS-0721236, ANI-0207728, CCF-0635202, and CNS-0721484, by ARO MURI Award W911-NF-08-1-0238, by AFOSR Grant FA 9550-07-1-0456, and by the IT Scholarship Program supervised by IITA and MIC, Korea. A preliminary version of this work was presented at IEEE INFOCOM, Phoenix, AZ, April 13–18, 2008.

Keywords

Capacity region
Communication systems
Greedy maximal scheduling (GMS)
Longest queue first
Multihop wireless networks

ASJC Scopus subject areas

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

Access to Document

10.1109/TNET.2009.2026276

Cite this

@article{c8615c21b7184266b1c191a49a944cdf,

title = "Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks",

abstract = "In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multihop wireless networks. While a lower bound on the throughput performance of GMS has been well known, empirical observations suggest that it is quite loose and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. We show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K-hop interference model. Then, we show that the worst-case efficiency ratio of GMS in geometric unit-disk graphs is between 1/6 and 1/3.",

keywords = "Capacity region, Communication systems, Greedy maximal scheduling (GMS), Longest queue first, Multihop wireless networks",

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

note = "Funding Information: Manuscript received July 01, 2008; revised January 21, 2009. First published July 21, 2009; current version published August 19, 2009. This work was supported in part by NSF awards CNS-0626703, CNS-0721236, ANI-0207728, CCF-0635202, and CNS-0721484, by ARO MURI Award W911-NF-08-1-0238, by AFOSR Grant FA 9550-07-1-0456, and by the IT Scholarship Program supervised by IITA and MIC, Korea. A preliminary version of this work was presented at IEEE INFOCOM, Phoenix, AZ, April 13–18, 2008.",

year = "2009",

doi = "10.1109/TNET.2009.2026276",

language = "English",

volume = "17",

pages = "1132--1145",

journal = "IEEE/ACM Transactions on Networking",

issn = "1063-6692",

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

number = "4",

}

TY - JOUR

T1 - Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks

AU - Joo, Changhee

AU - Lin, Xiaojun

AU - Shroff, Ness B.

N1 - Funding Information: Manuscript received July 01, 2008; revised January 21, 2009. First published July 21, 2009; current version published August 19, 2009. This work was supported in part by NSF awards CNS-0626703, CNS-0721236, ANI-0207728, CCF-0635202, and CNS-0721484, by ARO MURI Award W911-NF-08-1-0238, by AFOSR Grant FA 9550-07-1-0456, and by the IT Scholarship Program supervised by IITA and MIC, Korea. A preliminary version of this work was presented at IEEE INFOCOM, Phoenix, AZ, April 13–18, 2008.

PY - 2009

Y1 - 2009

N2 - In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multihop wireless networks. While a lower bound on the throughput performance of GMS has been well known, empirical observations suggest that it is quite loose and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. We show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K-hop interference model. Then, we show that the worst-case efficiency ratio of GMS in geometric unit-disk graphs is between 1/6 and 1/3.

AB - In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multihop wireless networks. While a lower bound on the throughput performance of GMS has been well known, empirical observations suggest that it is quite loose and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. We show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K-hop interference model. Then, we show that the worst-case efficiency ratio of GMS in geometric unit-disk graphs is between 1/6 and 1/3.

KW - Capacity region

KW - Communication systems

KW - Greedy maximal scheduling (GMS)

KW - Longest queue first

KW - Multihop wireless networks

UR - http://www.scopus.com/inward/record.url?scp=69249215199&partnerID=8YFLogxK

U2 - 10.1109/TNET.2009.2026276

DO - 10.1109/TNET.2009.2026276

M3 - Article

AN - SCOPUS:69249215199

SN - 1063-6692

VL - 17

SP - 1132

EP - 1145

JO - IEEE/ACM Transactions on Networking

JF - IEEE/ACM Transactions on Networking

IS - 4

ER -

Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this