Joint Scheduling of Rate-guaranteed and Best-effort Services over a Wireless Channel

We address multi-user scheduling over the down-link channel in wireless data systems. Specifically, we consider a time-slotted system with a single transmitter serving multiple users. With fixed power transmission, the channel condition of a user determines the reliable rate of communication to that user in a particular time-slot. The user set consists of, (i) throughput guaranteed (QoS) users, and, (ii) best effort (BE) users. For such a system we obtain the optimal policy that serves the QoS users with minimum time-slot utilization, thereby, maximizing the remaining fraction of time-slots allocated to the BE users. We present a simple geometric visualization of the optimal policy. In the special scenario of symmetric Rayleigh fading, we obtain explicit formulas that relate the achievable throughput rate guarantee to the number of QoS users supportable and the fraction of time-slots allocated to the BE users. Finally, we compare the throughput results for the optimal policy with the random-scheduling policy and show that gains on the order of ln(N) can be achieved by exploiting multi-user diversity, where N is the number of QoS users.