WiMAX relay networks: opportunistic scheduling to exploit multiuser diversity and frequency selectivity

ABSTRACT

We study the problem of scheduling in OFDMA-based relay networks with emphasis on IEEE 802.16j based WiMAX relay networks. In such networks, in addition to a base station, multiple relay stations are used for enhancing the throughput, and/or improving the range of the base station. We solve the problem of MAC scheduling in such networks so as to serve the mobiles in a fair manner while exploiting the multiuser diversity, as well as the frequency selectivity of the wireless channel. The scheduling resources consist of tiles in a two-dimensional scheduling frame with time slots along one axis, and frequency bands or sub-channels along the other axis. The resource allocation problem has to be solved once every scheduling frame which is about 5 - 10 ms long. While the original scheduling problem is computationally complex, we provide an easy-to-compute upper bound on the optimum. We also propose three fast heuristic algorithms that perform close to the optimum (within 99.5%), and outperform other algorithms such as OFDM²A proposed in the past. Through extensive simulation results, we demonstrate the benefits of relaying in throughput enhancement (an improvement in the median throughput of about 25%), and feasibility of range extension (for e.g., 7 relays can be used to extend the cell-radius by 60% but mean throughput reduces by 36%). Our algorithms are easy to implement, and have an average running time of less than 0.05 ms making them appropriate for WiMAX relay networks.

REFERENCES

• 1: GLPK (GNU Linear Programming Kit), version 4.22.
• 2: M. Andrews. A survey of scheduling theory in wireless data networks. In Proceedings of the 2005 IMA summer workshop on wireless communications, 2005.
• 3: Matthew Andrews , Lisa Zhang, Scheduling algorithms for multi-carrier wireless data systems, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287856]
• 4: M. Charafeddine, O. Oymant, and S. Sandhu. System-level performance of cellular multihop relaying with multiuser scheduling. In CISS, March 2007.
• 5: Y. W. Cheong, R. S. Cheng, K. B. Latief, and R. D. Murch. Multiuser ofdm with adaptive subcarrier, bit and power allocation. IEEE Journal on Selected Areas in Communications, October 1999.
• 6: S. Deb, V. Mhatre, and V. Ramaiyan. WiMAX relay networks: Opportunistic scheduling to exploit multiuser diversity and frequency selectivity. Bell Labs Technical Report, Feb 2008.
• 7: M. Ergen, S. Coleri, and P. Varaiya. QoS aware adaptive resource allocation techniques for fair scheduling in ofdma based broadband wireless access systems. IEEE Tran. on Broadcasting, Dec 2003.
• 8: IEEE 802.16 task group. Channel Models for Fixed Wireless Applications, ieee 802.16.3c-01/29r4 edition, July 2001.
• 9: IEEE 802.16e task group. Air Interface for Fixed and Mobile Broadband Wireless Access Systems. Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands, 802.16e-2005 edition, February 2006.
• 10: IEEE 802.16j task group. Air Interface for Fixed and Mobile Broadband Wireless Access Systems: Multihop Relay Specification, 802.16j-06/026r4 edition, June 2007.
• 11: O. Jo and D. Cho. Traffic adaptive uplink scheduling scheme for relay station in ieee 802.16 based multihop system. In IEEE VTC, 2004.
• 12: R. Cohen L. Katzir. Computational analysis and efficient algorithms for micro and macro ofdma scheduling. In IEEE Infocom 2008.
• 13: F. P. Kelly, A.K. Maulloo, and D.K.H. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, (49):237--252.
• 14: D. Kivanc, G. Li, and H. Liu. Computationally efficient bandwidth allocation and power control for ofdma. IEEE Transactions on Wireless Communications, 2(6):1150--1158, November 2003.
• 15: H. J. Kushner and P. A. Whiting. Convergence of proportional-fair sharing algorithms under general conditions. IEEE Transactions on Wireless Communication, 3(4):1250--1259, July 2004.
• 16: G. Narlikar, G. Wilfong, and L. Zhang. Designing multihop wireless backhaul networks with delay guarantees. In IEEE Infocom 2006.
• 17: K. Navaie and Halim Yanikomeroglu. Multi-route and multi-user diversity in infrastructure-based multi-hop networks. Cooperation in Wireless Networks: Principles and Applications, Editors: Frank H.P. Fitzek and Marcos D. Katz, 2006.
• 18: O. Oyman. OFDMA2A: A centralized resource allocation policy for cellular multi-hop networks. In IEEE Asilomar Conference on Signals, Systems and Computers, Nov 2006.
• 19: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 20: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 21: W. Rhee and J. M. Cioffi. Increase in capacity of multiuser ofdm system using dynamic subchannel allocation. In IEEE VTC, 2000.
• 22: Wimax forum. Mobile WiMAX Part I: A Technical Overview and Performance Evaluation, August 2006.
• 23: Q. Wu and E. Esteves. The CDMA2000 high rate packet data system. Chapter 4 of Advances in 3G Enhanced Technologies for Wireless Communications. Editors: Jiangzhou Wang and Tung-Sang Ng.
• 24: Y. Yu, S. Murphy, and L. Murphy. A clustering approach to planning base station and relay station locations in ieee 802.16j multi-hop relay networks. In IEEE ICC, 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

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:
WiMAX, multiuser diversity, opportunistic scheduling, relays