A refined performance characterization of longest-queue-first policy in wireless networks

ABSTRACT

One of the major challenges in wireless networking is how to optimize the link scheduling decisions under interference constraints. Recently, a few algorithms have been introduced to address the problem. However, solving the problem to optimality for general wireless interference models is known to be NP-hard. The research community is currently focusing on finding simpler, sub-optimal scheduling algorithms and on characterizing the algorithm performance. In this paper, we address the performance of a specific scheduling policy called Longest Queue First (LQF), which has gained significant recognition lately due to its simplicity and high efficiency in empirical studies. There has been a sequence of studies characterizing the guaranteed performance of the LQF schedule, culminating at the construction of the σ-local pooling concept by Joo et al. [10]. In this paper, we refine the notion of σ-local pooling and use the refinement to capture a larger region of guaranteed performance.

REFERENCES

• 1: H. Balakrishnan, C. Barrett, V. Kumar, M. Marathe, and S. Thite. The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc networks. IEEE Journal On Selected Areas In Communications, 22(6):1069--1079, 2004.
• 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: A. Brzezinski, G. Zussman, and E. Modiano. Local pooling conditions for joint routing and scheduling. In Information Theory and Applications Workshop, pages 499--506, 2008.
• 4: P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees through maximal scheduling in wireless networks. In Proceedings of 43d Annual Allerton Conference on Communication, Control and Computing, pages 28--30, 2005.
• 5: J.G. Dai. On positive harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Annals of Applied Probability, 5:49--77, 1995.
• 6: 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:505--521, 2006.
• 7: A. Gupta, X. Lin, and R. Srikant. Low-complexity distributed scheduling algorithms for wireless networks. In Proceedings of IEEE INFOCOM, May 2007.
• 8: P. Gupta and P.R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, 2000.
• 9: 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]
• 10: 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, 2008.
• 11: C. Joo and N. Shroff. Performance of random access scheduling schemes in multi-hop wireless networks. In Proceedings of IEEE INFOCOM, 2007.
• 12: X. Lin and S.B. Rasool. Constant-time distributed scheduling policies for ad hoc wireless networks. In Proceedings of the IEEE CDC, 2006.
• 13: 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]
• 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: Gaurav Sharma , Ness B. Shroff , Ravi R. Mazumdar, Maximum Weighted Matching with Interference Constraints, Proceedings of the 4th annual IEEE international conference on Pervasive Computing and Communications Workshops, p.70, March 13-17, 2006 [doi>10.1109/PERCOMW.2006.79]
• 16: G. Sharma, N.B. Shroff, and R.R. Mazumdar. Joint congestion control and distributed scheduling for throughput guarantees in wireless networks. In Proceedings of IEEE INFOCOM, pages 2072--2080, 2007.
• 17: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936--1948, Dec 1992.
• 18: X. Wu, R. Srikant, and J.R. Perkings. Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks. In Proceedings of IEEE INFOCOM, 2006.

INDEX TERMS

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

General Terms:
Performance, Theory

Keywords:
interference, local pooling, longest queue first, scheduling, stability, wireless networks