TY - JOUR
T1 - Power Assignment for k-Connectivity in Wireless Ad Hoc Networks
AU - JIA, Xiaohua
AU - KIM, Dongsoo
AU - MAKKI, Sam
AU - WAN, Peng-Jun
AU - YI, Chih-Wei
PY - 2005/3
Y1 - 2005/3
N2 - The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k ≥ 3, a (k + 12H (k)) -approximation algorithm for k(2k-1) ≤ n where n is the network size, a (k + 2⌈(k + 1)/2⌉)-approximation algorithm for 2 ≤ k ≤ 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.
AB - The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k ≥ 3, a (k + 12H (k)) -approximation algorithm for k(2k-1) ≤ n where n is the network size, a (k + 2⌈(k + 1)/2⌉)-approximation algorithm for 2 ≤ k ≤ 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.
KW - k-connectivity
KW - Power assignment
KW - Wireless ad hoc sensor networks
UR - http://www.scopus.com/inward/record.url?scp=24144472248&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-24144472248&origin=recordpage
U2 - 10.1007/s10878-005-6858-2
DO - 10.1007/s10878-005-6858-2
M3 - 21_Publication in refereed journal
VL - 9
SP - 213
EP - 222
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 2
ER -