A fast and efficient algorithm to exploit multi-user diversity in IEEE 802.16 BandAMC

Mobile broadband wireless access systems like IEEE 802.16/WiMAX use Orthogonal Frequency Division Multiple Access (OFDMA) in order to exploit frequency and multi-user diversity for improving the spectral efficiency. We assume in this work a two-stage approach for resource allocation, whereby scheduling of packets in a given time frame, and their allocation across different subcarriers and time slots, are carried out separately one after the other. We specifically focus on the allocation problem in the second stage. Our first contribution is a problem formulation which is based on a detailed system model close to a practical IEEE 802.16/WiMAX system using BandAMC. The problem is proved to be NPNP-complete. Secondly, we propose a heuristic allocation algorithm, called Maximum Regret Band Allocation, and show through an extensive numerical analysis that it is very effective in realistic scenarios, as well as so computationally efficient to be executed in times in the order of one millisecond.