Joint Scheduling of Rate-Guaranteed and Best-Effort Users over a Wireless Fading Channel

We address multi-user scheduling over the downlink channel in wireless data systems. Specifically, we consider a time-slotted system with a single transmitter serving multiple users, where the channel condition of each user is time varying. Based on the throughput requirements, the user set is divided into two classes (i) throughput guaranteed (QoS) users, and, (ii) best effort (BE) users. For this system we obtain the optimal policy that serves the QoS users with the minimum time-slot utilization and maximizes the total fraction of time-slots allocated to the BE users. We show that the optimal policy has a simple geometric structure that can be easily visualized graphically. In the special case of Rayleigh fading, we obtain closed-form formulas that relate the achievable throughput-rate guarantee of the QoS users as a function of other system parameters, thus, providing closed-from relationships to understand the various system tradeoffs. Analytical comparison between the optimal and the random-scheduling policy shows that gains on the order of ln(N) can be achieved, where N is the number of QoS users. Finally, we present simulation results comparing the optimal policy under Rayleigh and Nakagami fading with other heuristic policies including a well known opportunistic-scheduling policy.