TY - GEN

T1 - A large deviations analysis of scheduling in wireless networks

AU - Ying, Lei

AU - Srikant, R.

AU - Dullerud, G. E.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33847188472&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847188472&partnerID=8YFLogxK

U2 - 10.1109/CDC.2005.1583124

DO - 10.1109/CDC.2005.1583124

M3 - Conference contribution

AN - SCOPUS:33847188472

SN - 0780395689

SN - 9780780395688

T3 - Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05

SP - 6016

EP - 6021

BT - Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05

T2 - 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05

Y2 - 12 December 2005 through 15 December 2005

ER -