On Wireless Scheduling Algorithms for Minimizing the Queue-Overflow Probability

• Published in: IEEE/ACM transactions on networking 2010-06, Vol.18 (3), p.788-801
• Main Authors: Venkataramanan, V J, Xiaojun Lin
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Asymptotic properties; Asymptotically optimal algorithms; cellular system; Decay rate; Downlink; Flowcharts; H infinity control; Infinity; Interference; Land mobile radio cellular systems; large deviations; Optimization; Probability; queue-overflow probability; Queues; Queuing theory; Scheduling; Scheduling algorithm; Stability; Studies; System performance; Throughput; Upper bound; Upper bounds; wireless scheduling
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2009.2037896

In this paper, we are interested in wireless scheduling algorithms for the downlink of a single cell that can minimize the queue-overflow probability. Specifically, in a large-deviation setting, we are interested in algorithms that maximize the asymptotic decay rate of the queue-overflow probability, as the queue-overflow threshold approaches infinity. We first derive an upper bound on the decay rate of the queue-overflow probability over all scheduling policies. We then focus on a class of scheduling algorithms collectively referred to as the "α-algorithms." For a given α ≥ 1, the α-algorithm picks the user for service at each time that has the largest product of the transmission rate multiplied by the backlog raised to the power α. We show that when the overflow metric is appropriately modified, the minimum-cost-to-overflow under the α-algorithm can be achieved by a simple linear path, and it can be written as the solution of a vector-optimization problem. Using this structural property, we then show that when α approaches infinity, the α-algorithms asymptotically achieve the largest decay rate of the queue-overflow probability. Finally, this result enables us to design scheduling algorithms that are both close to optimal in terms of the asymptotic decay rate of the overflow probability and empirically shown to maintain small queue-overflow probabilities over queue-length ranges of practical interest.