Scheduling Over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data

In a wireless network, a basestation transmits data to mobiles at time-varying, mobile-dependent rates due to the ever changing nature of the communication channels. In this paper we consider a wireless system in which the channel conditions and data arrival processes are governed by an adversary. We first consider a single server and a set of users. At each time step t the server can only transmit data to one user. If user i is chosen the transmission rate is r sub i (t). We say that the system is (w,e)-admissible if in any window of w time steps the adversary can schedule the users so that the total data arriving to each user is at most 1-e times the total service it receives.