Topology formation for wireless mesh network planning

Chun Cheng Chen*, Chandra Chekuri, Diego Klabjan

*Corresponding author for this work

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

10 Scopus citations

Abstract

In this paper, we propose Greedy Selection Rounding (GSR), an efficient and near-optimal algorithm to design a wireless mesh network topology that maximizes the coverage of the users while ensuring that the network is resilient to node failures and and the deployment cost is under a given budget. In the case that GSR fails to find a solution satisfying the budget constraint, the incurred cost does not exceed the budget by a constant factor. Through extensive evaluation, we show that in all our test cases GSR always generates a topology above 95% of the optimal in terms of the number of covered users while never exceeding the budget by more than 15%.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2009 - The 28th Conference on Computer Communications
Pages2671-2675
Number of pages5
DOIs
StatePublished - Oct 12 2009
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

Other

Other28th Conference on Computer Communications, IEEE INFOCOM 2009
CountryBrazil
CityRio de Janeiro
Period4/19/094/25/09

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Topology formation for wireless mesh network planning'. Together they form a unique fingerprint.

  • Cite this

    Chen, C. C., Chekuri, C., & Klabjan, D. (2009). Topology formation for wireless mesh network planning. In IEEE INFOCOM 2009 - The 28th Conference on Computer Communications (pp. 2671-2675). [5062209] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2009.5062209