A general scheduling strategy based on an estimate of the rate region

We study a general scheduling strategy for the downlink wireless channel of a cellular data network. A fixed number of users, with saturated queues, share a slotted wireless channel using time division multiplexing. The objective of the scheduler is to achieve a long-time average throughput vector that maximizes a given network utility and/or satisfies given QoS constraints. The simple and asymptotically optimal schedulers described in [18] and in [10] are restricted to concave (and linear) network utilities and are unsuitable for general utility functions that are non-concave, non-differentiable or discontinuous. Also, most of the schedulers in literature are utility/QoS specific, and there is a lack of a sufficiently general framework for scheduler design. In this paper, we propose a general scheduling framework that uses channel and schedule histories, and can implement any continuous network utility, including non-concave and non-differentiable utilities. We, first, propose a rate region based scheduler, RRS, that uses the available channel history to identify a schedule in every slot. We prove that RRS is asymptotically optimal for all continuous network utilities, for some ergodic channels. We, then, propose a variant of RRS called RRS-RA (RRS using allocated rates), which uses schedule history and channel history in decision making. RRS-RA has several advantages over RRS as it makes consistent schedule decisions and handles sample path variations better than RRS. Using simulations, we demonstrate that rate region based schedulers can implement QoS defined using arbitrary continuous and some non-continuous functions, provide a parameter-less implementation and has better convergence behaviour than network utility-based gradient schedulers. Finally, we propose a simple strategy that uses channel history to increase the convergence rate of some popular schedulers in the literature.