On exploiting diversity and spatial reuse in relay-enabled wireless networks

ABSTRACT

Relay-enabled wireless networks (eg. WIMAX 802.16j) represent an emerging trend for the incorporation of multi-hop networking solutions for last-mile broadband access in next generation wireless networks. The adoption of more sophisticated access technologies such as OFDM (orthogonal frequency division multiplexing) coupled with the relay-induced two-hop nature, provides two key benefits to these networks in the form of diversity and spatial reuse gains. However, leveraging these benefits calls for more sophisticated solutions, among which, user scheduling forms a key component.

We consider the specific problem of scheduling users with finite buffers on the multiple OFDM carriers (channels over the two hops of the relay-enabled network. We propose scheduling algorithms that help leverage diversity and spatial reuse gains from these networks. We show that even the scheduling problem to exploit diversity gains alone is NP-hard and provide both theoretically and practically efficient polynomial-time algorithms with approximation guarantees. Building on the diversity solutions, we also propose an efficient polynomial-time scheduling algorithm for exploiting both spatial reuse as well as diversity. The proposed solutions are evaluated to highlight the relative significance of diversity and spatial reuse gains with respect to varying network conditions.

REFERENCES

• 1: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh 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.1161092]
• 2: Tae-Suk Kim , Hyuk Lim , Jennifer C. Hou, Improving spatial reuse through tuning transmit power, carrier sense threshold, and data rate in multihop 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.1161131]
• 3: Z. Zhang, Y. He, and K. P. Chong, "Oppotunistic downlink scheduling for multiuser ofdm systems," in IEEE WCNC, Mar 2005.
• 4: G. Song and Y. Li, "Cross-layer optimization for OFDM wireless networks - Part I: Theoretical Framework," IEEE Transactions on Wireless Communications, vol. 4, no. 2, Mar 2005.
• 5: 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]
• 6: A. So and B. Liang, "Effect of relaying on capacity improvement in wireless local area networks," in IEEE WCNC, Mar 2005.
• 7: S. Mengesha and H. Karl, "Relay routing and scheduling for capacity improvement in cellular wlans," in WiOpt.
• 8: C. Hoymann, P. Dallas, A. Valkanas, A. Gosteau, D. Noguet, and R. Hoshyar, "Flexible relay wireless ofdm-based networks," in Funded by European Commission, 2006.
• 9: N. Challa and H. Cam, "Cost-aware downlink scheduling of shared channels for cellular networks with relays," in IEEE International Conference on Performance, Computing, and Communications, 2004.
• 10: H. Viswanathan and S. Mukherjee, "Performance of cellular networks with relays and centralized scheduling," IEEE Transactions on Wireless Communications, vol. 4, no. 5, Sep 2005.
• 11: M. Herdin, "A chunk based ofdm amplify-and-forward relaying scheme for 4g mobile radio systems," in IEEE ICC, Jun 2006.
• 12: A. Hottinen and T. Heikkinen, "Subchannel assignment in ofdm relay nodes," in Proc. of CISS, Mar 2006.
• 13: J. Jang and K. B. Lee, "Transmit power adaptation for multi-user OFDM systems," IEEE JSAC, vol. 21, no. 2, pp. 171--179, 2003.
• 14: B. Radunovic and J. Le Boudec, "Rate performance objectives of multi-hop wireless networks," in IEEE INFOCOM, Mar 2004.
• 15: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 16: 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]
• 17: R. G. Mukthar, "Qns: Queuing network simulator," in QNS v0.1, http://www.cubinlab.ee.mu.oz.au/rgmukht/qns, Nov 2003.

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:
Algorithms, Performance, Theory

Keywords:
OFDMA, diversity, scheduling, spatial reuse, wireless relay