A Study of Scheduling Algorithms to Maintain Small Overflow Probability in Cellular Networks with a Single Cell

Nagarajan B., Venkatesan G., Santhosh Kumar C.


Wireless scheduling algorithms for the download of a single cell that can maximize the asymptotic decay rate of the queue-overflow probability as the overflow threshold approaches infinity. We first derive an upper bound on the decay rate of the queue-overflow probability over all scheduling policies. Specifically, we focus on the class of “α - algorithms,” the base station 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 α. The α-algorithms arbitrarily achieve the highest decay rate of the queue-overflow probability. We design a scheduling algorithm that is both close to optimal in terms of the asymptotic decay rate of the overflow probability and to maintain small queue-overflow probabilities over queue-length ranges of practical interest.


Asymptotically Optimal Algorithms; Cellular System; Large Deviations; Queue-Overflow Probability; Wireless Scheduling

Full Text: PDF


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.