Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks

ABSTRACT

Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been studied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wireless networks. In this paper, we prove that GMS achieves 100% throughput in all networks with eight nodes or less, under the two-hop interference model. Further, we obtain performance bounds that improve upon previous results for larger networks up to a certain size. We also provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.

REFERENCES

• 1: 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]
• 2: P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees in maximal scheduling in wireless networks. In Proceedings 43rd Annual Allerton Conference on Communication, Control and Computing, September 2005.
• 3: A. Dimakis and J. Walrand. Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits. Advances in Applied Probabilities, 38(2):505--521, 2006.
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: B. Hajek and G. Sasaki. Link scheduling in polynomial time. IEEE Transactions on Information Theory, pages 910--917, 1988.
• 6: J.-H. Hoepman. Simple distributed weighted matchings. http://arxiv.org/abs/cs.DC/0410047, October 2004.
• 7: Changhee Joo, A local greedy scheduling scheme with provable performance guarantee, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374634]
• 8: C. Joo, X. Lin, and N.B. Shroff. Performance limits of greedy maximal matching in multi-hop wireless networks. In Proceedings of IEEE CDC'07, December 2007.
• 9: C. Joo, X. Lin, and N.B. Shroff. Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. In Proceedings of IEEE INFOCOM'08, April 2008.
• 10: X. Lin and N.B. Shroff. The impact of imperfect scheduling on cross-layer control in multihop wireless networks. In Proceedings of IEEE INFOCOM'05, 2005.
• 11: Nicholas William McKeown, Scheduling algorithms for input-queued cell switches, University of California at Berkeley, Berkeley, CA, 1996
• 12: R. Preis. Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In Proceedings of STACS'99, 1999.
• 13: 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.
• 14: X. Wu and R. Srikant. Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. In Proceedings of IEEE INFOCOM'06, April 2006.
• 15: G. Zussman, A. Brzezinski, and E. Modiano. Multihop local pooling for distributed throughput maximization in wireless networks. In Proceedings of IEEE INFOCOM'08, April 2008.

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

Keywords:
greedy maximal scheduling, longest queue first, throughput optimality, wireless networks