OPTIMAL LINEAR-TIME UPLINK SCHEDULING ALGORITHMS FOR WIMAX

摘要

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 algorithms have been developed for special cases of the problem 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 application and derive an algorithm for uplink scheduling which has two highly favourable features: it finds the optimal solution in linear time.