Scheduling algorithms for multi-carrier wireless data systems

ABSTRACT

We consider the problem of scheduling wireless data in systems such as 802.16 (WIMAX). Each scheduling decision involves constructing a frame of one or more time slots. Within each time slot multiple carriers must be assigned to users. The important aspect of our problem is that a scheduler knows the channel rates across all users and all carriers whenever a scheduling decision is made. Hence there is no need to treat each carrier in complete isolation. This gives a potential for enhancing performance by allocating multiple carriers simultaneously.

We analyze this problem in a situation where finite queues are fed by a data arrival process. We generalize the well-known MaxWeight algorithm for the single-carrier setting to accommodate a number of natural optimization problems in the multi-carrier setting. We state the hardness of these problems and present simple algorithmic solutions with provable performance bounds. We also validate our algorithms via numerical examples.

REFERENCES

• 1: R. Agrawal and V. Subramanian. Optimality of certain channel aware scheduling policies. In Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, October 2002.
• 2: M. Andrews. Instability of the proportional fair scheduling algorithm for HDR. IEEE Transactions on Wireless Communications, 3(5), 2004.
• 3: M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting. CDMA data QoS scheduling on the forward link with variable channel conditions. Bell Labs Technical Memorandum, April 2000.
• 4: M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting. Providing quality of service over a shared wireless link. IEEE Communications Magazine, February 2001.
• 5: M. Andrews, L. Qian, and A. Stolyar. Optimal utility based multi-user throughput allocation subject to throughput constraints. In Proceedings of IEEE INFOCOM '05, 2005.
• 6: M. Andrews and A. Slivkins. Oscillations with TCP-like flow control in networks of queues. In Proceedings of IEEE INFOCOM '06, 2006.
• 7: Matthew Andrews , Lisa Zhang, Scheduling over nonstationary wireless channels with finite rate sets, IEEE/ACM Transactions on Networking (TON), v.14 n.5, p.1067-1077, October 2006 [doi>10.1109/TNET.2006.882835]
• 8: P. Bender, P. Black, M. Grob, R. Padovani, and N. Sindhushayana A. Viterbi. CDMA/HDR: A bandwidth efficient high speed data service for nomadic users. IEEE Communications Magazine, July 2000.
• 9: Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
• 10: A. Eryilmaz and R. Srikant. Fair resource allocation in wireless networks using queue-length based scheduling and congestion control. In Proceedings of IEEE INFOCOM '05, Miami, FL, March 2005.
• 11: M. Fisher, G. Nemhauser, and L. Wolsey. An analysis of approximations for maximizing submodular set functions-II. Mathematical Programming Study, 1978.
• 12: Lisa Fleischer , Michel X. Goemans , Vahab S. Mirrokni , Maxim Sviridenko, Tight approximation algorithms for maximum general assignment problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.611-620, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109624]
• 13: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 14: Dorit S. Hochbaum, Various notions of approximations: good, better, best, and more, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 15: A. Jalali, R. Padovani, and R. Pankaj. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system. In Proceedings of the IEEE Semiannual Vehicular Technology Conference, VTC2000-Spring, Tokyo, Japan, May 2000.
• 16: Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, v.37 n.1, p.27-35, Jan. 10, 1991 [doi>10.1016/0020-0190(91)90246-E]
• 17: H. Kushner and P. Whiting. Asymptotic properties of proportional-fair sharing algorithms. In 40th Annual Allerton Conference on Communication, Control, and Computing, 2002.
• 18: X. Liu, E. Chong, and N. B. Shroff. Opportunistic transmission scheduling with resource-sharing constraints in wireless networks. IEEE Journal on Selected Areas in Communications, 19(10), 2001.
• 19: Xin Liu , Edwin K. P. Chong , Ness B. Shroff, A framework for opportunistic scheduling in wireless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.4, p.451-474, 15 March 2003 [doi>10.1016/S1389-1286(02)00401-2]
• 20: M. Neely, E. Modiano, and C. Li. Fairness and optimal stochastic control for heterogeneous networks. In Proceedings of IEEE INFOCOM '05, Miami, FL, March 2005.
• 21: M. Neely, E. Modiano, and C. Rohrs. Power and server allocation in a multi-beam satellite with time varying channels. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002.
• 22: S. Shakkottai and A. Stolyar. Scheduling algorithms for a mixture of real-time and non-real-time data in HDR. In Proceedings of 17th International Teletraffic Congress (ITC-17), pages 793--804, Salvador da Bahia, Brazil, 2001.
• 23: S. Shakkottai and A. Stolyar. Scheduling for multiple flows sharing a time-varying channel: The exponential rule. Analytic Methods in Applied Probability, 207:185--202, 2002.
• 24: Alexander L. Stolyar, Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm, Queueing Systems: Theory and Applications, v.50 n.4, p.401-457, August 2005 [doi>10.1007/s11134-005-1450-0]
• 25: Alexander L. Stolyar, On the Asymptotic Optimality of the Gradient Scheduling Algorithm for Multiuser Throughput Allocation, Operations Research, v.53 n.1, p.12-25, January 2005 [doi>10.1287/opre.1040.0156]
• 26: 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, December 1992.
• 27: L. Tassiulas and A. Ephremides. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Transactions on Information Theory, 30:466--478, 1993.
• 28: D. Tse. Multiuser diversity in wireless networks. http://www.eecs.berkeley.edu/~dtse/stanford416.ps, 2002.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms

Keywords:
WIMAX, max weight, multiple carriers, queue performance, scheduling, stability, wireless communication