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 -