Strong minimum energy topology in wireless sensor networks: NP-completeness and heuristics

被引:116
作者
Cheng, XZ [1 ]
Narahari, B
Simha, R
Cheng, MXY
Liu, D
机构
[1] George Washington Univ, Dept Comp Sci, Washington, DC 20052 USA
[2] Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA
关键词
minimum energy topology; power control; wireless sensor networks; NP-completeness; incremental power heuristic;
D O I
10.1109/TMC.2003.1233530
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Wireless sensor networks have recently attracted lots of research effort due to its wide range of applications. These networks must operate for months or years. However, the sensors are powered by battery, which may not be possible to be recharged after they are deployed. Thus, energy-aware network management is extremely important. In this paper, we study the following problem: Given a set of sensors in the plane, assign transmit power to each sensor such that the induced topology containing only bidirectional links is strongly connected. This problem is significant in both theory and application. We prove its NP-Completeness and propose two heuristics: power assignment based on minimum spanning tree (denoted by MST) and incremental power. We also show that MST heuristic has a performance ratio of 2. Simulation study indicates that the performance of these two heuristics does not differ very much, but, in average, the incremental power heuristic is always better than MST.
引用
收藏
页码:248 / 256
页数:9
相关论文
共 29 条
[1]  
[Anonymous], P 3 ACM INT S MOB AD
[2]  
ASADA G, 1998, P EUR SOL STAT CIRC
[3]   Distributed topology control algorithm for multihop wireless networks [J].
Borbash, SA ;
Jennings, EH .
PROCEEDING OF THE 2002 INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORKS, VOLS 1-3, 2002, :355-360
[4]  
Cagalj M., 2002, P 8 ANN INT C MOB CO, P172
[5]   THE STRONGLY CONNECTING PROBLEM ON MULTIHOP PACKET RADIO NETWORKS [J].
CHEN, WT ;
HUANG, NF .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1989, 37 (03) :293-295
[6]  
CHENG X, 2003, UNPUB VIRTUAL BACKBO
[7]  
CHENG X, 2003, UNPUB RELAY SENSOR P
[8]  
CLEMENTI AEF, 1999, LECT NOTES COMPUTER, V1671, P195
[9]  
Cormen T. H., 2001, Introduction to Algorithms, V2nd
[10]  
EYNDE FO, 2001, P IEEE INT SOL STAT, V446, P196