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.

REFERENCES

• 1: L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximal throughput in multihop radio networks," IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
• 2: Xiaojun Lin , Ness B. Shroff, The impact of imperfect scheduling on cross-layer congestion control in wireless networks, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.302-315, April 2006 [doi>10.1109/TENT.2006.872546]
• 3: G. Sharma, C. Joo, and N. B. Shroff, "Distributed scheduling schemes for throughput guarantees in wireless networks," in Proc. 44th Annu. Allerton Conf. Commun., Control, and Comput., Sep. 2006, pp. 1396-1405.
• 4: X. Lin and S. Rasool, "Constant-time distributed scheduling policies for ad hoc wireless networks," in IEEE CDC, Dec. 2006, pp. 1258-1263.
• 5: Eytan Modiano , Devavrat Shah , Gil Zussman, Maximizing throughput in wireless networks via gossiping, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
• 6: C. Joo and N. B. Shroff, "Performance of random access scheduling schemes in multi-hop wireless networks," in Proc. IEEE INFOCOM, May 2007, pp. 19-27.
• 7: A. Gupta, X. Lin, and R. Srikant, "Low-complexity distributed scheduling algorithms for wireless networks," in Proc. IEEE INFOCOM, May 2007, pp. 1631-1639.
• 8: Sujay Sanghavi , Loc Bui , R. Srikant, Distributed link scheduling with constant overhead, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 9: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 10: B. Hajek and G. Sasaki, "Link scheduling in polynominal time," IEEE Trans. Inf. Theory, vol. 34, no. 5, pp. 910-917, Sep. 1988.
• 11: S. Sarkar and L. Tassiulas, "End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks," in Proc. IEEE CDC, Dec. 2003, pp. 564-569.
• 12: P. Chaporkar, K. Kar, X. Luo, and S. Sarkar, "Throughput and fairness guarantees through maximal scheduling in wireless networks," IEEE Trans. Inf. Theory, vol. 54, no. 2, pp. 572-594, Feb. 2008.
• 13: X. Wu and R. Srikant, "Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks," in Proc. IEEE INFOCOM , Apr. 2006, pp. 1-12.
• 14: Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161116]
• 15: Emilio Leonardi , Marco Mellia , Fabio Neri , Marco Ajmone Marsan, On the stability of input-queued switches with speed-up, IEEE/ACM Transactions on Networking (TON), v.9 n.1, p.104-118, Feb., 2001 [doi>10.1109/90.909028]
• 16: Nicholas William McKeown, Scheduling algorithms for input-queued cell switches, University of California at Berkeley, Berkeley, CA, 1996
• 17: A. Dimakis and J. Walrand, "Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits," Adv. Appl. Probab., vol. 38, no. 2, pp. 505-521, 2006.
• 18: J.-H. Hoepman, "Simple distributed weighted matchings," Oct. 2004 [Online]. Available: http://arxiv.org/abs/cs/0410047v1
• 19: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, Algorithmic aspects of capacity in wireless networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 20: Andrew Brzezinski , Gil Zussman , Eytan Modiano, Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161094]
• 21: G. Zussman, A. Brzezinski, and E. Modiano, "Multihop local pooling for distributed throughput maximization in wireless networks," in Proc. IEEE INFOCOM, Apr. 2008, pp. 1139-1147.
• 22: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 23: J. G. Dai, "On positive harris recurrence of multiclass queueing networks: A unified approach via fluid limit models," Ann. Appl. Probab., vol. 5, no. 1, pp. 49-77, 1995.
• 24: Michael J. Neely , Eytan Modiano , Charles E. Rohrs, Power allocation and routing in multibeam satellites with time-varying channels, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.138-152, February 2003 [doi>10.1109/TNET.2002.808401]
• 25: R. L. Cruz and A. V. Santhanam, "Optimal routing, link scheduling and power control in multi-hop wireless networks," in Proc. IEEE INFOCOM , San Francisco, Apr. 2003, pp. 702-711.
• 26: C. Joo, X. Lin, and N. B. Shroff, "Performance limits of greedy maximal matching in multi-hop wireless networks," in Proc. IEEE CDC, Dec. 2007, pp. 1128-1133.
• 27: C. Joo, X. Lin, and N. B. Shroff, "Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks," Ohio State Univ., Columbus, 2008, Tech. Rep. [Online]. Available: http://www.ece.osu.edu/~cjoo
• 28: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, End-to-end packet-scheduling in wireless ad-hoc networks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 29: H. Balakrishnan, C. L. Barrett, V. S. A. Kumar, M. V. Marathe, and S. Thite, "The distance-2 matching problem and its relationship to the MAC-layer capacity of Ad Hoc wireless networks," IEEE J. Sel. Areas Commun., vol. 22, no. 6, pp. 1069-1079, Aug. 2004.
• 30: Amos Israel , A. Itai, A fast and simple randomized parallel algorithm for maximal matching, Information Processing Letters, v.22 n.2, p.77-80, 1986 [doi>10.1016/0020-0190(86)90144-4]
• 31: C. Buragohain, S. Suri, C. Toth, and Y. Zhou, "Improved throughput bounds for interference-aware routing in wireless networks," in Proc. COCOON, 2007, pp. 210-221.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication; Network topology
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Management, Performance

Keywords:
capacity region, communication systems, greedy maximal scheduling (GMS), longest queue first, multihop wireless networks