A local greedy scheduling scheme with provable performance guarantee

ABSTRACT

In recent years, there have been many efforts to develop low-complexity scheduling schemes that can approximate optimal performance in multi-hop wireless networks. A centralized sub-optimal scheduling policy, called Greedy Maximal Scheduling (GMS) is a good candidate because it achieves high throughput. However, its distributed realization requires O(|V|) complexity, which becomes a major obstacle for practical implementation, where |V| is the number of nodes in the network. In this paper, we develop a simple distributed scheduling policy for multi-hop wireless networks. It achieves O(log |V|) complexity by relaxing the global ordering requirement of GMS. Instead, it deterministically schedules only links that have the largest queue length among their local neighbors. We show that, it still guarantees a fraction of the optimal performance, which is no smaller than GMS. We also further improve its performance and address some important implementation issues. The simulation results confirm that the new scheduling scheme achieves the performance equivalent of GMS and significantly outperforms state-of-the-art distributed random access scheduling policies.

REFERENCES

• 1: D. Avis. A Survey of Heuristics for the Weighted Matching Problem. Networks, 13(4):475--493, 1983.
• 2: 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]
• 3: L. Bui, A. Eryilmaz, R. Srikant, and X. Wu. Joint Asynchronous Congestion Control and Distributed Scheduling for Multi-Hop Wireless Networks. In IEEE INFOCOM, April 2006.
• 4: P. Chaporkar, K. Kar, and S. Sarkar. Throughput Guarantees in Maximal Scheduling in Wireless Networks. In the 43rd Annual Allerton Conference on Communication, Control and Computing, September 2005.
• 5: L. Chen, S. H. Low, M. Chiang, and J. C. Doyle. Cross-layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless Networks. In IEEE INFOCOM, April 2006.
• 6: J. G. Dai. On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach via Fluid Limit Models. Annals of Applied Probability, 5(1):49--77, 1995.
• 7: R. Diestel. Graph Theory. Springer, 3 edition, 2005.
• 8: A. Dimakis and J. Walrand. Sufficient Conditions for Stability of Longest-Queue-First Scheduling: Second-order Properties using Fluid Limits. Advances in Applied Probability, 38(2):505--521, 2006.
• 9: A. Eryilmaz, A. Ozdaglar, and E. Modiano. Polynomial Complexity Algorithms for Full Utilization of Multi-hop Wireless Networks. In IEEE INFOCOM, May 2007.
• 10: A. Eryilmaz and R. Srikant. Fair Resource Allocation in Wireless Networks Using Queue-length Based Scheduling and Congestion Control. In IEEE INFOCOM, March 2005.
• 11: A. Gupta, X. Lin, and R. Srikant. Low-Complexity Distributed Scheduling Algorithms for Wireless Networks. In IEEE INFOCOM, May 2007.
• 12: B. Hajek and G. Sasaki. Link Scheduling in Polynominal Time. IEEE Transactions on Information Theory, 34(5), September 1988.
• 13: J.-H. Heopman. Simple Distributed Weighted Matchings. eprint, October 2004.
• 14: C. Joo, X. Lin, and N. B. Shroff. Performance Limits of Greedy Maximal Matching in Multi-hop Wireless Networks. In IEEE CDC, December 2007.
• 15: C. Joo, X. Lin, and N. B. Shroff. Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multi-hop Wireless Networks. In IEEE INFOCOM, April 2008. To appear.
• 16: C. Joo and N. B. Shroff. Performance of Random Access Scheduling Schemes in Multi--hop Wireless Networks. In IEEE INFOCOM, May 2007.
• 17: 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]
• 18: X. Lin and S. Rasool. Constant-Time Distributed Scheduling Policies for Ad Hoc Wireless Networks. In IEEE CDC, December 2006.
• 19: X. Lin and N. B. Shroff. Joint Rate Control and Scheduling in Multihop Wireless Networks. In IEEE CDC, December 2004.
• 20: 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]
• 21: Eytan Modiano , Devavrat Shah , Gil Zussman, Maximizing throughput in wireless networks via gossiping, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
• 22: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 23: A. Penttinen, I. Koutsopoulos, and L. Tassiulas. Low-complexity Distributed Fair Scheduling for Wireless Multi-hop Networks. In Workshop on Resource Allocation in Wireless Networks, 2005.
• 24: R. Preis. Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs. In Symposium on Theoretical Aspects of Computer Science, 1999.
• 25: Sujay Sanghavi , Loc Bui , R. Srikant, Distributed link scheduling with constant overhead, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
• 26: S. Sarkar and L. Tassiulas. End-to-end Bandwidth Guarantees Through Fair Local Spectrum Share in Wireless Ad-hoc Networks. In IEEE CDC, December 2003.
• 27: G. Sharma, C. Joo, and N. B. Shroff. Distributed Scheduling Schemes for Throughput Guarantees in Wireless Networks. In the 44th Annual Allerton Conference on Communications, Control, and Computing, September 2006.
• 28: 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]
• 29: L. Tassiulas and A. Ephremides. Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximal Throughput in Multihop Radio Networks. IEEE Transactions on Automatic Control, 37(12):1936--1948, December 1992.
• 30: X. Wu and R. Srikant. Bounds on the Capacity Region of Multi-hop Wireless Networks Under Distributed Greedy Scheduling. In IEEE INFOCOM, April 2006.
• 31: Y. Yi and S. Shakkottai. Learning Contention Patterns and Adapting to Load/Topology Changes in a MAC Scheduling Algorithm. In IEEE WiMesh, September 2006.
• 32: G. Zussman, A. Brzezinski, and E. Modiano. Multihop Local Pooling for Distributed Throughput Maximization in Wireless Networks. In IEEE INFOCOM, April 2008. To appear.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Performance, Theory

Keywords:
distributed, greedy algorithm, multi-hop wireless networks, scheduling