Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks

Xinzhou Wu, Rayadurgam Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of distributed scheduling in wireless networks subject to simple collision constraints. In a network depletion problem with an initial traffic load and no further arrivals, we define the scheduling efficiency to be the ratio between the number of time slots required to deplete the network under an optimal centralized scheduling scheme and a distributed greedy scheduling scheme. In a network with stochastic arrivals, we define the scheduling efficiency to be the largest number (fraction) such that its throughput is at least equal to the efficiency multiplied by the throughput of a centralized policy. For 802.11-like scheduling constraints which ensure that there is no collision during the reception of a data packet or its ack, we prove a lower bound on the efficiency of a distributed scheduling algorithm. While the tightness of the lower bound is still open for networks with stochastic arrivals, we also prove an upper bound for the network depletion problem which shows that the efficiency can only be larger than the lower bound by a factor of two. The upper bound is established by deriving a new result on the ratio of the chromatic number to the number of colors required to color the nodes of a contention graph using a greedy coloring algorithm. Our results are not asymptotic in the number of nodes in the network, i.e, they hold for networks of any size. For a collision constraint which only avoids collision of the data packet, we also provide a lower bound on the achievable capacity region.

Original languageEnglish (US)
Title of host publicationProceedings - INFOCOM 2006
Subtitle of host publication25th IEEE International Conference on Computer Communications
DOIs
StatePublished - Dec 1 2006
EventINFOCOM 2006: 25th IEEE International Conference on Computer Communications - Barcelona, Spain
Duration: Apr 23 2006Apr 29 2006

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherINFOCOM 2006: 25th IEEE International Conference on Computer Communications
CountrySpain
CityBarcelona
Period4/23/064/29/06

ASJC Scopus subject areas

  • Computer Science(all)
  • 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