Scheduling over nonstationary wireless channels with finite rate sets

We consider a wireless basestation transmitting high-speed data to multiple mobile users in a cell. The channel conditions between the basestation and the users are time-varying and user-dependent. We wish to define 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 1timesEV-DO system, Max-Weight can produce queues size 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