Delay-Optimal Opportunistic Scheduling and Approximations: The Log Rule
Authors:
- 30 August 2010
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 19 (2) , 405-418
Abstract
This paper considers the design of multiuser opportunistic packet schedulers for users sharing a time-varying wireless channel from performance and robustness points of view. For a simplified model falling in the classical Markov decision process framework, we numerically compute and characterize mean-delay-optimal scheduling policies. The computed policies exhibit radial sum-rate monotonicity: As users' queues grow linearly, the scheduler allocates service in a manner that deemphasizes the balancing of unequal queues in favor of maximizing current system throughput (being opportunistic). This is in sharp contrast to previously proposed throughput-optimal policies, e.g., Exp rule and MaxWeight (with any positive exponent of queue length). In order to meet performance and robustness objectives, we propose a new class of policies, called the Log rule, that are radial sum-rate monotone (RSM) and provably throughput-optimal. In fact, it can also be shown that an RSM policy minimizes the asymptotic probability of sum-queue overflow. We use extensive simulations to explore various possible design objectives for opportunistic schedulers. When users see heterogenous channels, we find that emphasizing queue balancing, e.g., Exp rule and MaxWeight, may excessively compromise the overall delay. Finally, we discuss approaches to implement the proposed policies for scheduling and resource allocation in OFDMA-based multichannel systems.Keywords
This publication has 28 references indexed in Scilit:
- Downlink Scheduling for Multiclass Traffic in LTEEURASIP Journal on Wireless Communications and Networking, 2009
- Instability of the Proportional Fair Scheduling Algorithm for HDRIEEE Transactions on Wireless Communications, 2004
- SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATESProbability in the Engineering and Informational Sciences, 2004
- Opportunistic beamforming using dumb antennasIEEE Transactions on Information Theory, 2002
- Discrete-review policies for scheduling stochastic networks: trajectory tracking and fluid-scale asymptotic optimalityThe Annals of Applied Probability, 2000
- CDMA/HDR: a bandwidth efficient high speed wireless data service for nomadic usersIEEE Communications Magazine, 2000
- Asymptotic buffer overflow probabilities in multiclass multiplexers: an optimal control approachIEEE Transactions on Automatic Control, 1998
- A survey of Markov decision models for control of networks of queuesQueueing Systems, 1993
- Dynamic server allocation to parallel queues with randomly varying connectivityIEEE Transactions on Information Theory, 1993
- Optimal control of two interacting service stationsIEEE Transactions on Automatic Control, 1984