Document Type
Article
Date
2011
Keywords
Wireless relay networks, WiMAX, scheduling, OFDMA
Language
English
Disciplines
Electrical and Computer Engineering | Engineering
Description/Abstract
Relay stations can be deployed in a wireless network to extend its coverage and improve its capacity. In this paper, we study a scheduling problem in OFDMA-based wireless relay networks with consideration for multi-user diversity, channel diversity and spatial reuse. First, we present a Mixed Integer Linear Programming (MILP) formulation to provide optimum solutions. It has been shown by previous research that performance of a wireless scheduling algorithm is usually related to the interference degree δ, which is the maximum number of links that interfere with a common link but do not interfere with each other. Therefore, we then show that the interference degree δ is at most 4 for any 2-hop relay network and 14 for any general h-hop (h >=2) relay network. Furthermore, we present a simple greedy algorithm for the scheduling problem and show it has an approximation ratio of 1/(1+δ), which leads to an approximation ratio of 1/5 for the 2-hop case and 1/15 for the general case. In addition, we present three heuristic algorithms, namely, the weighted degree greedy algorithm, the Maximum Weighted Independent Set (MWIS) algorithm and the Linear Programming (LP) rounding algorithm, to solve the scheduling problem. Extensive simulation results have showed that the LP rounding algorithm performs best and always provides close-to-optimum solutions. The performance of the simple greedy algorithm is comparable to that of the other algorithms.
Recommended Citation
S. Wan, J. Tang, B. Mumey, R. S. Wolff, and W. Zhang, "Leveraging multi-user diversity, channel diversity and spatial reuse for efficient scheduling in wireless relay networks," in 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011, October 17, 2011 - October 22, 2011, Valencia, Spain, 2011, pp. 401-410.
