In this correspondence, we consider a cellular network consisting of a base station and N receivers. The channel states of the receivers are assumed to be identical and independent of each other. The goal is to compare the throughput of two different scheduling policies (a queue-length-based (QLB) policy and a greedy policy) given an upper bound on the queue overflow probability or the delay violation probability. We consider a multistate channel model, where each channel is assumed to be in one of L states. Given an upper bound on the queue overflow probability or an upper bound on the delay violation probability, we show that the total network throughput of the (QLB) policy is no less than the throughput of the greedy policy for all N. We also obtain a lower bound on the throughput of the (QLB) policy. For sufficiently large N, the lower bound is shown to be tight, strictly increasing with N, and strictly larger than the throughput of the greedy policy. Further, for a simple multistate channel model - ON-OFF channel, we prove that the lower bound is tight for all N.

Original languageEnglish (US)
Pages (from-to)5088-5098
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number11
StatePublished - Nov 2006


  • Greedy policy
  • Large deviations
  • Multiuser wireless scheduling
  • Queue-length-based (QLB) policy
  • Wireless networks

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'A large deviations analysis of scheduling in wireless networks'. Together they form a unique fingerprint.

Cite this