Low-complexity distributed scheduling algorithms for wireless networks

Abhinav Gupta, Xiaojun Lin, R. Srikant

Research output: Contribution to journalArticlepeer-review


We consider the problem of designing distributed scheduling algorithms for wireless networks. We present two algorithms, both of which achieve throughput arbitrarily close to that of maximal schedules, but whose complexity is low due to the fact that they do not necessarily attempt to find maximal schedules. The first algorithm requires each link to collect local queue-length information in its neighborhood, and its complexity is otherwise independent of the size and topology of the network. The second algorithm, presented for the node-exclusive interference model, does not require nodes to collect queue-length information even in their local neighborhoods, and its complexity depends only on the maximum node degree in the network.

Original languageEnglish (US)
Article number5169943
Pages (from-to)1846-1859
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 2009


  • Low-complexity and distributed algorithms
  • Maximal scheduling
  • Provable efficiency ratios
  • Wireless scheduling algorithms

ASJC Scopus subject areas

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


Dive into the research topics of 'Low-complexity distributed scheduling algorithms for wireless networks'. Together they form a unique fingerprint.

Cite this