Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multihop Wireless Networks
Authors:
- Changhee JooCJChanghee Joo
- Xiaojun LinXLXiaojun Lin
- 21 July 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 17 (4) , 1132-1145
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
This publication has 22 references indexed in Scilit:
- Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multi-Hop Wireless Networks2008
- Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless NetworksIEEE Transactions on Information Theory, 2008
- Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limitsAdvances in Applied Probability, 2006
- Constant-Time Distributed Scheduling Policies for Ad Hoc Wireless Networks2006
- Scheduling Efficiency of Distributed Greedy Scheduling Algorithms in Wireless Networks2006
- Algorithmic aspects of capacity in wireless networksACM SIGMETRICS Performance Evaluation Review, 2005
- End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks2004
- On the stability of input-queued switches with speed-upIEEE/ACM Transactions on Networking, 2001
- Link scheduling in polynomial timeIEEE Transactions on Information Theory, 1988
- A fast and simple randomized parallel algorithm for maximal matchingInformation Processing Letters, 1986