Wireless scheduling algorithms with O(1) overhead for M-hop interference model

Yung Yi, Mung Chiang

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

12 Scopus citations


We develop a family of distributed wireless scheduling algorithms that requires only O(1) complexity for M-hop interference model, for any finite M. The recent technology advances and heterogeneity in wireless networks lead to various interference patterns. Thus, a scheduling algorithm geared into a specific interference model (typically one-hop or two-hop in literature) may be limited in its applicability. In this paper, we tackle this problem, and develop a family of scheduling algorithms (which guarantees throughput and delay performance) for M-hop interference models. To achieve such a goal, we use the concept of vertex augmentation, and for a given M, the family of parameterized algorithms are proposed and the tradeoffs among throughput, complexity, and delay are studied.

Original languageEnglish (US)
Title of host publicationICC 2008 - IEEE International Conference on Communications, Proceedings
Number of pages5
StatePublished - 2008
EventIEEE International Conference on Communications, ICC 2008 - Beijing, China
Duration: May 19 2008May 23 2008

Publication series

NameIEEE International Conference on Communications
ISSN (Print)0536-1486


OtherIEEE International Conference on Communications, ICC 2008

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Wireless scheduling algorithms with O(1) overhead for M-hop interference model'. Together they form a unique fingerprint.

Cite this