Scheduling Algorithms for Multi-Carrier Frame-Based Wireless Data Systems

We consider the problem of scheduling wireless data in systems such as 802.16 (Wimax). Each scheduling decision involves constructing a frame of one or more time slots. Within each time slot multiple carriers must be assigned to users. The important feature of our problem is that a scheduler knows the channel rates across all users and all carriers whenever a scheduling decision is made. This gives a potential for enhancing performance by allocating multiple carriers simultaneously. There is no need to treat each carrier in isolation. We first examine the multi-carrier scenario with finite queues and a data arrival process. We generalize the well-known MaxWeight algorithm for the single-carrier setting to accommodate a number of natural optimization problems in the multi-carrier setting. We state the hardness of these problems and present simple algorithmic solutions with provable performance bounds. We also study template-based schedules for scheduling multiple carriers over a multi-slot template that may consist of one or more time frames. An optimal template schedules each user in evenly spaced time slots. While elegant templates exist for the single-carrier case, we present a number of deterministic and randomized algorithms for the multi-carrier case and demonstrate the power of randomization. We validate our algorithms via analytical bounds as well as numerical examples.