Topology Formation for Wireless Mesh Network Planning

Chun-cheng Chen, Chandra Chekuri, Diego Klabjan

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%.
BibTeX
@inproceedings{chen2009topology,
  author = {Chun-cheng Chen and Chandra Chekuri and Diego Klabjan},
  title = {{Topology Formation for Wireless Mesh Network Planning}},
  booktitle = {INFOCOM},
  year = {2009},
  doi = {10.1109/infcom.2009.5062209},
}

Loading related content...

Figure