Abstract

We consider a basestation transmitting data to a set of mobile users. At each time step the basestation receives information about the channel conditions to each user. These channel conditions are time-varying and user-dependent. The job of the scheduler is to decide which user is served. In recent years this problem has received a great deal of attention. In the first part of the talk we give an overview of some specific models that arise from 3rd generation wireless standards. We summarize some of the main theoretical results and discuss the performance of scheduling algorithms that are implemented in practice.

We also describe some recent work on scheduling wireless data in multi-carrier 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. We present a set of results regarding the complexity of the multi-carrier scheduling problem.