TY - GEN
T1 - Topology formation for wireless mesh network planning
AU - Chen, Chun Cheng
AU - Chekuri, Chandra
AU - Klabjan, Diego
PY - 2009
Y1 - 2009
N2 - 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%.
AB - 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%.
UR - http://www.scopus.com/inward/record.url?scp=70349677460&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349677460&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2009.5062209
DO - 10.1109/INFCOM.2009.5062209
M3 - Conference contribution
AN - SCOPUS:70349677460
SN - 9781424435135
T3 - Proceedings - IEEE INFOCOM
SP - 2671
EP - 2675
BT - IEEE INFOCOM 2009 - The 28th Conference on Computer Communications
T2 - 28th Conference on Computer Communications, IEEE INFOCOM 2009
Y2 - 19 April 2009 through 25 April 2009
ER -