Exploring the throughput boundaries of randomized schedulers in wireless networks

Bin Li, Atilla Eryilmaz

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


Randomization is a powerful and pervasive strategy for developing efficient and practical transmission scheduling algorithms in interference-limited wireless networks. Yet, despite the presence of a variety of earlier works on the design and analysis of particular randomized schedulers, there does not exist an extensive study of the limitations of randomization on the efficient scheduling in wireless networks. In this paper, we aim to fill this gap by proposing a common modeling framework and three functional forms of randomized schedulers that utilize queue-length information to probabilistically schedule nonconflicting transmissions. This framework not only models many existing schedulers operating under a timescale separation assumption as special cases, but it also contains a much wider class of potential schedulers that have not been analyzed. We identify some sufficient and some necessary conditions on the network topology and on the functional forms used in the randomization for throughput optimality. Our analysis reveals an exponential and a subexponential class of functions that exhibit differences in the throughput optimality. Also, we observe the significance of the network's scheduling diversity for throughput optimality as measured by the number of maximal schedules each link belongs to. We further validate our theoretical results through numerical studies.

Original languageEnglish (US)
Article number6068266
Pages (from-to)1112-1124
Number of pages13
JournalIEEE/ACM Transactions on Networking
Issue number4
StatePublished - 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Exploring the throughput boundaries of randomized schedulers in wireless networks'. Together they form a unique fingerprint.

Cite this