The University of British Columbia

This paper considers the problem of scheduling multiple users in the downlink of a time-slotted cellular data network. For such a network, opportunistic scheduling algorithms improve system performance by exploiting time variations of the radio channel. We present novel optimal and approximate opportunistic scheduling algorithms that combine channel fluctuation and user mobility information in their decision rules. The algorithms modify the opportunistic scheduling framework of Liu et al., (1993) with dynamic constraints for fairness. These fairness constraints adapt according to the user mobility. The adaptation of constraints in the proposed algorithms implicitly results in giving priority to the users that are in the most favorable locations. The optimal algorithm is an offline algorithm that precomputes constraint values according to a known mobility model. The approximate algorithm is an online algorithm that relies on the future prediction of the user mobility locations in time. We show that the use of mobility information in opportunistic scheduling increases channel capacity. We also provide analytical bounds on the performance of the approximate algorithm using the fundamental inequality of Dyer et al., (1986) for linear programs. Simulation results on high data rate (HDR) illustrate the usefulness of the proposed schemes for elastic traffic and macrocell structures