Leveraging multi-user diversity, channel diversity and spatial reuse for efficient scheduling in wireless relay networks

Shen Wan, Jian Tang, Brendan Mumey, Richard S. Wolff, Weiyi Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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 delta, 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 delta 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+delta), 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.

Original languageEnglish (US)
Title of host publicationProceedings - 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011
Pages401-410
Number of pages10
DOIs
StatePublished - 2011
Event8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011 - Valencia, Spain
Duration: Oct 17 2011Oct 22 2011

Publication series

NameProceedings - 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011

Other

Other8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011
CountrySpain
CityValencia
Period10/17/1110/22/11

Keywords

  • OFDMA
  • WiMAX
  • Wireless relay networks
  • scheduling

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Leveraging multi-user diversity, channel diversity and spatial reuse for efficient scheduling in wireless relay networks'. Together they form a unique fingerprint.

Cite this