Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks

Changhee Joo, Xiaojun Lin, Ness B. Shroff

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

128 Citations (Scopus)

Abstract

In this paper, we characterize the performance of an important class of scheduling schemes, called Greedy Maximal Scheduling (GMS), for multi-hop wireless networks. While a lower bound on the throughput performance of GMS is relatively well-known in the simple node-exclusive interference model, it has not been thoroughly explored in the more general K-hop interference model. Moreover, empirical observations suggest that the known bounds are quite loose, and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. First, we show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the K-hop interference model. Second, we show that the worst-case efficiency ratio of GMS in geometric network graphs is between 1/6 and 1/3.

Original languageEnglish
Title of host publicationINFOCOM 2008
Subtitle of host publication27th IEEE Communications Society Conference on Computer Communications
Pages1777-1785
Number of pages9
DOIs
Publication statusPublished - 2008
Externally publishedYes
EventINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications - Phoenix, AZ, United States
Duration: 2008 Apr 132008 Apr 18

Publication series

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

Other

OtherINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications
Country/TerritoryUnited States
CityPhoenix, AZ
Period08/4/1308/4/18

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks'. Together they form a unique fingerprint.

Cite this