ISSN 1000-9825, CODEN RUXUEW Journal of Software, Vol.17, No.2, February 2006, pp.175184 DOI: 10.1360/jos170175 2006 by Journal of Software. All rights reserved.
E-mail: jos@iscas.ac.cn http://www.jos.org.cn Tel/Fax: +86-10-62562563
无线传感器网络最小连通覆盖集问题求解算法
蒋 杰 1+, 方 力 2, 张鹤颖 1, 窦文华 1
1 2
(国防科学技术大学 计算机学院,湖南 长沙 (国防科学技术大学 网络信息中心,湖南 长沙
410073) 410073)
An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks
JIANG Jie1+,
1 2
FANG Li2,
ZHANG He-Ying1,
DOU Wen-Hua1
(School of Computer, National University of Defense Technology, Changsha 410073, China) (Network Information Center, National University of Defense Technology, Changsha 410073, China)
+ Corresponding author: Phn: +86-731-4575830, Fax: +86-731-4575830, E-mail: jiangjie@nudt.edu.cn, http://www.nudt.edu.cn
Jiang J, Fang L, Zhang HY, Dou WH. An algorithm for minimal connected cover set problem in wireless sensor networks. Journal of Software, 2006,17(2):175184. http://www.jos.org.cn/ 1000-9825/17/175.htm Abstract: Reducing power consumption to extend network lifetime is one of the most important challenges in designing wireless sensor networks. One promising approach to conserving system energy is to keep only a minimal number of sensors active and put others into low-powered sleep mode, while the active sensors can maintain the communication connectivity and cover the target region completely. The problem of computing such minimal active sensor set is NP-hard. In this paper, a centralized Voronoi tessellation (CVT) based approximate algorithm is proposed to construct a near optimal cover set of active sensors required to cover the target region completely. The communication graph induced by the cover set computed by CVT algorithm is connected if sensor's communication radius is at least twice of its sensing radius. In case of sensor's communication radius is smaller than twice of its sensing radius, a minimum spanning tree (MST) based connection algorithm is proposed to ensure the communication connectivity of the cover set. Finally, the performance of the proposed algorithm is evaluated through theoretical analysis and extensive numerical experiments. Experimental results show that the proposed algorithm outperforms the greedy algorithm in terms of the runtime and the size of the constructed connected cover set. Key words: WSN (wireless sensor network); network lifetime; MCCS (minimal connected cover set); Voronoi tessellation; MIS (maximal independent set); MST (minimum spanning tree) 摘 要: 降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环

下一页