Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks

Mathieu Leconte, Jian Ni, R. Srikant

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

Abstract

Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been stud- ied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wire- less networks. In this paper, we prove that GMS achieves 100% throughput in all networks with eight nodes or less, under the two-hop interference model. Further, we obtain performance bounds that improve upon previous results for larger networks up to a certain size. We also provide a sim- ple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.

Original languageEnglish (US)
Title of host publicationMobiHoc'09 - Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing
Pages165-174
Number of pages10
DOIs
StatePublished - Nov 27 2009
Event10th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc'09 - New Orleans, LA, United States
Duration: May 18 2009May 21 2009

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

Other

Other10th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc'09
Country/TerritoryUnited States
CityNew Orleans, LA
Period5/18/095/21/09

Keywords

  • Greedy maximal scheduling
  • Longest queue first
  • Throughput optimality
  • Wireless networks

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks'. Together they form a unique fingerprint.

Cite this