Low-complexity distributed scheduling algorithms for wireless networks

Abhinav Gupta, Xiaojun Lin, R. Srikant

Research output: Contribution to journalArticle

Abstract

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
Volume17
Issue number6
DOIs
StatePublished - Dec 1 2009

    Fingerprint

Keywords

  • 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

Cite this