The complexity of channel scheduling in multi-radio multi-channel wireless networks

Wei Cheng, Xiuzhen Cheng, Taieb Znati, Xicheng Lu, Zexin Lu

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

33 Citations (Scopus)

Abstract

The complexity of channel scheduling in Multi-Radio Multi-Channel (MR-MC) wireless networks is an open research topic. This problem asks for the set of edges that can support maximum amount of simultaneous traffic over orthogonal channels under a certain interference model. There exist two major interference models for channel scheduling, with one under the physical distance constraint, and one under the hop distance constraint. The complexity of channel scheduling under these two interference models serves as the foundation for many problems related to network throughput maximization. However, channel scheduling was proved to be NP-Hard only under the hop distance constraint for SR-SC wireless networks. In this paper, we fill the void by proving that channel scheduling is NP-Hard under both models in MR-MC wireless networks. In addition, we propose a polynomial-time approximation scheme (PTAS) framework that is applicable to channel scheduling under both interference models in MR-MC wireless networks. Furthermore, we conduct a comparison study on the two interference models and identify conditions under which these two models are equivalent for channel scheduling.

Original languageEnglish
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Pages1512-1520
Number of pages9
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event28th Conference on Computer Communications, IEEE INFOCOM 2009 - Rio de Janeiro, Brazil
Duration: Apr 19 2009Apr 25 2009

Publication series

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

Conference

Conference28th Conference on Computer Communications, IEEE INFOCOM 2009
Country/TerritoryBrazil
CityRio de Janeiro
Period4/19/094/25/09

Keywords

  • Channel scheduling
  • Complexity
  • Maximum weight channel scheduling
  • Multi-radio multi-channel wireless networks
  • NP-hard
  • PTAS
  • Polynomial time approximation scheme

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'The complexity of channel scheduling in multi-radio multi-channel wireless networks'. Together they form a unique fingerprint.

Cite this