Topology formation for wireless mesh network planning

Chun Cheng Chen, Chandra Chekuri, Diego Klabjan

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

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 - 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
Country/TerritoryBrazil
CityRio de Janeiro
Period4/19/094/25/09

ASJC Scopus subject areas

  • General Computer Science
  • 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