TY - JOUR
T1 - Minimum Connected Dominating Set Under Routing Cost Constraint in Wireless Sensor Networks With Different Transmission Ranges
AU - Song, Liang
AU - Liu, Chunyan
AU - Huang, Hejiao
AU - Du, Hongwei
AU - Jia, Xiaohua
PY - 2019/4
Y1 - 2019/4
N2 - Wireless sensor networks (WSNs) are used to cover destination areas for a lot of practical applications. To enhance the performance of the WSN, the virtual backbone based on the connected dominating set is an efficient way with respect to the routing cost between sensors, lifetime of entire network, and so on. In this paper, especially for the WSN with different transmission radii among different sensors, we study the problem of constructing the minimum ρ-range connected dominating set under the constraint α-times of the minimum routing cost (αMOC-ρCDS), where α ≥ 5 and ρ is the ratio of the maximum-to-minimum transmission radius. Our contributions are three folds. First, we propose a polynomial time approximation scheme which generates the αMOC-ρCDS with the size of at most (1+ε) times of the optimum solution, where ε is the error parameter. Second, we propose a polynomial time algorithm and prove that it has two approximation ratios (6ρ +1)²(2ρ+1)² and 10⌈(2π/θ)⌉⌊(ln 3ρ/(ln(1/cos θ)))⌋⌊(ln ρ/(ln(2 cos(π/5))))⌋, where θ < arcsin(1/3ρ). Finally, we propose the distributed version of the constant approximation ratio algorithm which has both the time complexity and message complexity O(n³), where n is the number of sensor nodes. Besides, the simulation results demonstrate the efficiency of our algorithms.
AB - Wireless sensor networks (WSNs) are used to cover destination areas for a lot of practical applications. To enhance the performance of the WSN, the virtual backbone based on the connected dominating set is an efficient way with respect to the routing cost between sensors, lifetime of entire network, and so on. In this paper, especially for the WSN with different transmission radii among different sensors, we study the problem of constructing the minimum ρ-range connected dominating set under the constraint α-times of the minimum routing cost (αMOC-ρCDS), where α ≥ 5 and ρ is the ratio of the maximum-to-minimum transmission radius. Our contributions are three folds. First, we propose a polynomial time approximation scheme which generates the αMOC-ρCDS with the size of at most (1+ε) times of the optimum solution, where ε is the error parameter. Second, we propose a polynomial time algorithm and prove that it has two approximation ratios (6ρ +1)²(2ρ+1)² and 10⌈(2π/θ)⌉⌊(ln 3ρ/(ln(1/cos θ)))⌋⌊(ln ρ/(ln(2 cos(π/5))))⌋, where θ < arcsin(1/3ρ). Finally, we propose the distributed version of the constant approximation ratio algorithm which has both the time complexity and message complexity O(n³), where n is the number of sensor nodes. Besides, the simulation results demonstrate the efficiency of our algorithms.
KW - WSN
KW - MOC-CDS
KW - PTAS
KW - Approximation algorithm
KW - distributed algorithm
UR - http://www.scopus.com/inward/record.url?scp=85061525322&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85061525322&origin=recordpage
U2 - 10.1109/TNET.2019.2894749
DO - 10.1109/TNET.2019.2894749
M3 - 21_Publication in refereed journal
VL - 27
SP - 546
EP - 559
JO - IEEE - ACM Transactions on Networking
JF - IEEE - ACM Transactions on Networking
SN - 1063-6692
IS - 2
ER -