Scheduling over nonstationary wireless channels with finite rate sets

We consider a wireless basestation transmitting highspeed data to multiple mobile users in a cell. The channel conditions between the basestation and the users are time-varying and user-dependent. Our objective is to design a scheduler that determines which user to schedule at each time step. Previous work on this problem has typically assumed that the channel conditions are governed by a stationary stochastic process. In this setting, a popular algorithm known as Max-Weight has been shown to have good performance. However, the stationarity assumption is not always reasonable. In this paper, we study a more general worst-case model in which the channel conditions are governed by an adversary and are not necessarily stationary. In this model, we show that the nonstationarities can cause Max-Weight to have extremely poor performance. In particular, even if the set of possible transmission rates is finite, as in the CDMA 1xEV-DO system, Max-Weight can produce queue sizes that are exponential in the number of users. On the positive side, we describe a set of tracking algorithms that aim to track the performance of a schedule maintained by the adversary. For one of these tracking algorithms, the queue sizes are only quadratic. We discuss a number of practical issues associated with the tracking algorithms. We also illustrate the performance of Max-Weight and the tracking algorithms using simulation.