TY - GEN
T1 - Distributed gateway placement for cost minimization in wireless mesh networks
AU - Xu, Xiao Hua
AU - Tang, Shao Jie
AU - Mao, Xufei
AU - Li, Xiang Yang
PY - 2010
Y1 - 2010
N2 - We study the problem of gateway placement for cost minimization (GPCM) in two-dimensional wireless mesh networks. We are given a set of mesh routers, assume they have identical transmission range r, represented by unit transmission disks around them. A router may be selected as a gateway at certain placing cost. A router is served by a gateway if and only if the gateway is within its transmission range. The goal of this work is to select a set of mesh routers as gateways to serve the rest routers with minimum overall cost. This problem is NP-hard. To the best of our knowledge, no distributed algorithm with a constant approximation ratio has been given before. When all weights are uniform, the best approximation ratio is 38. We present both centralized and distributed algorithms which can achieve approximation ratios 6 + ε and 20 respectively. Our algorithms greatly improve the best approximation ratios.
AB - We study the problem of gateway placement for cost minimization (GPCM) in two-dimensional wireless mesh networks. We are given a set of mesh routers, assume they have identical transmission range r, represented by unit transmission disks around them. A router may be selected as a gateway at certain placing cost. A router is served by a gateway if and only if the gateway is within its transmission range. The goal of this work is to select a set of mesh routers as gateways to serve the rest routers with minimum overall cost. This problem is NP-hard. To the best of our knowledge, no distributed algorithm with a constant approximation ratio has been given before. When all weights are uniform, the best approximation ratio is 38. We present both centralized and distributed algorithms which can achieve approximation ratios 6 + ε and 20 respectively. Our algorithms greatly improve the best approximation ratios.
UR - https://www.scopus.com/pages/publications/77955914908
U2 - 10.1109/ICDCS.2010.51
DO - 10.1109/ICDCS.2010.51
M3 - Conference contribution
AN - SCOPUS:77955914908
SN - 9780769540597
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 507
EP - 515
BT - ICDCS 2010 - 2010 International Conference on Distributed Computing Systems
T2 - 30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010
Y2 - 21 June 2010 through 25 June 2010
ER -