Optimal Linear-Time Uplink Scheduling Algorithms for WiMAX

A. Mohammadi, S.G. Akl, and F. Behnamfar (Canada)


WiMAX, OFDMA, uplink, optimal solution, linear solu tion, scheduling, modeling.


In this paper, we focus on a recent application of realtime scheduling in wireless communications industry; namely, uplink scheduling for WiMAX systems. More specifically, we address the problem of maximizing the number of data packets to be sent in uplink such that the expectations from the system are guaranteed. We argue that this problem is NP-Complete. Thus far, only a number of heuristic algo rithms have been developed for special cases of the prob lem and the problem has not been modeled formally. In this work, we present two formal models for the system. We take advantage of the properties of the appli cation and derive an algorithm for uplink scheduling which has two highly favourable features: it finds the optimal so lution in linear time.

Important Links:

Go Back