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. 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. Repeated template schedules require no continuous feedback of information (such as channel conditions), thereby relieving the signaling overhead. This setup is suitable for applications such as Wimax where users are typically static. Our aim is to assign carriers to users in such a way that the service per 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.