TY - JOUR
T1 - Performance evaluation for energy efficient topologic control in ad hoc wireless networks
AU - Li, Minming
AU - Huang, Shawn L.
AU - Sun, Xiaoming
AU - Huang, Xiao
PY - 2004/10/20
Y1 - 2004/10/20
N2 - Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρk for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρk for all k.
AB - Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρk for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρk for all k.
KW - Ad hoc wireless network
KW - Approximation algorithms
KW - Min power symmetric connectivity
UR - https://www.scopus.com/pages/publications/5144223046
U2 - 10.1016/j.tcs.2004.06.017
DO - 10.1016/j.tcs.2004.06.017
M3 - 文章
AN - SCOPUS:5144223046
SN - 0304-3975
VL - 326
SP - 399
EP - 408
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -