Creating Templates to Achieve Low Delay in Multi-Carrier Frame-Based Wireless Data Systems

We consider the problem of creating template-based schedules for multi-carrier frame-based wireless data systems such as 802.16 (Wimax). A template consists of an assignment of carriers to users over a fixed set of time slots. This schedule can then be repeated multiple times. The aim is to assign the (time slot, carrier) pairs to the users in such a way that the service to each user is as smooth as possible. This in turn ensures that the users experience low delay. A number of elegant template scheduling algorithms exist for the single-carrier case. However, the case of multi-carrier systems where the channel rates can be different on different carriers has received much less attention. We present a general framework for studying the delay performance of a multi-carrier template. We then describe a number of deterministic and randomized scheduling algorithms for template creation and study their delay performance via analysis and simulation. We also show that the delay bounds can sometimes be improved by randomly shifting the schedule on each carrier and by scheduling in a hierarchical manner.