Literature Database Entry

cheng2009complexity

Wei Cheng, Xiuzhen Cheng, T. Znati, Xicheng Lu and Zexin Lu, "The Complexity of Channel Scheduling in Multi-Radio Multi-Channel Wireless Networks," Proceedings of 28th IEEE Conference on Computer Communications (INFOCOM 2009), Rio de Janeiro, Brazil, April 2009, pp. 1512 –1520.

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 scheduling., identify conditions under which these two models are equivalent for channel

Quick access

Original Version DOI (at publishers web site)
BibTeX BibTeX

Contact

Wei Cheng
Xiuzhen Cheng
T. Znati
Xicheng Lu
Zexin Lu

BibTeX reference

@inproceedings{cheng2009complexity,
    author = {Cheng, Wei and Cheng, Xiuzhen and Znati, T. and Lu, Xicheng and Lu, Zexin},
    doi = {10.1109/INFCOM.2009.5062068},
    title = {{The Complexity of Channel Scheduling in Multi-Radio Multi-Channel Wireless Networks}},
    pages = {1512 --1520},
    address = {Rio de Janeiro, Brazil},
    booktitle = {28th IEEE Conference on Computer Communications (INFOCOM 2009)},
    month = {4},
    year = {2009},
   }
   
   

Copyright notice

Links to final or draft versions of papers are presented here to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted or distributed for commercial purposes without the explicit permission of the copyright holder.

The following applies to all papers listed above that have IEEE copyrights: Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

The following applies to all papers listed above that are in submission to IEEE conference/workshop proceedings or journals: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

The following applies to all papers listed above that have ACM copyrights: ACM COPYRIGHT NOTICE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or permissions@acm.org.

The following applies to all SpringerLink papers listed above that have Springer Science+Business Media copyrights: The original publication is available at www.springerlink.com.

This page was automatically generated using BibDB and bib2web.