Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks

Xinzhou Wu, R. Srikant, James R. Perkins

Research output: Contribution to journalArticle

Abstract

We consider the problem of distributed scheduling in wireless networks subject to simple collision constraints. We define the efficiency of a distributed scheduling algorithm to be the largest number (fraction) such that the throughput under the distributed scheduling policy is at least equal to the efficiency multiplied by the maximum throughput achievable under a centralized policy. For a general interference model, we prove a lower bound on the efficiency of a distributed scheduling algorithm by first assuming that all of the traffic only uses one hop of the network. We also prove that the lower bound is tight in the sense that, for any fraction larger than the tower bound, we can find a topology and an arrival rate vector within the fraction of the capacity region such that the network is unstable under a greedy scheduling policy. We then extend our results to a more general multihop traffic scenario and show that similar scheduling efficiency results can be established by introducing prioritization or regulators to the basic greedy scheduling algorithm.

Original languageEnglish (US)
Pages (from-to)595-605
Number of pages11
JournalIEEE Transactions on Mobile Computing
Volume6
Issue number6
DOIs
StatePublished - Jun 1 2007

Keywords

  • Greedy algorithms
  • Multihop wireless networks
  • Resource allocation
  • Scheduling

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks'. Together they form a unique fingerprint.

  • Cite this