A Large Deviations Analysis of Scheduling in Wireless Networks

We consider a cellular network consisting of a base station and N receivers. The channel to each receiver is assumed to be in one of two states (ON or OFF) and the channel states of the receivers are assumed to be independent of each other. The goal is to compare the throughput of two different scheduling policies given an upper bound on the queue overflow probability or the delay violation probability. The two scheduling policies that we consider are: (i) a greedy scheduling policy which chooses to serve any of the channels in the ON state, and (ii) a queue-length-based policy which serves the longest queue connected to an ON channel. We show that the total network throughput of the queue-length-based policy is no less than that of the greedy policy for all N and is strictly larger than the throughput of the greedy policy for large N. Further, given an upper bound on the delay violation probability, we show that the throughput of the queue-length-based policy is an increasing function of N while the throughput of the greedy policy eventually decreases with increasing N and goes to zero. Given an upper bound on the queue overflow probability, we show that the throughput of the queue-length-based policy is a strictly increasing function of N while the throughput of the greedy policy eventually goes to a constant.