ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software, Vol.17, No.2, February 2006, pp.175 184 doc.guandang.net DOI: 10.1360/jos170175 Tel/Fax: +86-10-62562563 © 2006 by Journal of Software. All rights reserved.
无线传感器网络最小连通覆盖集问题求解算法
蒋 杰1+, 方 力2, 张鹤颖1, 窦文华1
12
(国防科学技术大学 计算机学院,湖南 长沙 410073) (国防科学技术大学 网络信息中心,湖南 长沙 410073)
An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks
JIANG Jie1+, FANG Li2, ZHANG He-Ying1, DOU Wen-Hua1
12
(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, doc.guandang.net
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):175 184. doc.guandang.net 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)
摘 要: 降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足“覆盖要求”(工作节点必须能够完全覆盖目标区域)和“连通性要求”(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralized Voronoi tessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小 Supported by the National Natural Science Foundation of China under Grant No.90104001 (国家自然科学基金); the National Grand
Fundamental Research 973 Program of China under Grant No.2003CB314802 (国家重点基础研究发展规划(973))
Received 2005-03-10; Accepted 2005-08-03
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入会员!获取文档下载券 无线传感器网络最小连通覆盖集问题求解算法...
更多>>在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对...
区域内的传感器节点采集网络覆盖区 域内感知对象的信息 节点间采用无线自组织...连通图中求解最小连通支 配集是一个 难问题 在实际应用中通常只能采用近似算法...
无线传感器网络最小连通覆盖的节能算法_信息与通信_工程科技_专业资料 暂无评价
它通过大量部署在检测区域内的传感器节点采集网络覆盖区 受无线传输距离的限制...由于求解最小连通支配集是一个 NP 难要 问题 ,许多近似算法被提出用于构建可用...
湖南大学 硕士学位论文 无线传感器网络中覆盖与连通算法的研究 姓名:杜辉 ...基于 Voronoi 划分的无线传感器网络最小连通覆盖集问题求解算法 . 软件学报 , ...
无线传感器网络最小覆盖集的贪婪近似算法_专业资料。网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点...
无线传感器网络中能量有效的最小连通支配集算法_专业资料。提出了一种分布式最小连通支配集求解算法,对RuleK算法中的标记算法进行了优化,从而形成了连通支配集,并...
flag=1&file_no=20030713&journal_id=jos [13] 蒋杰,方力,张鹤颖,窦文华.无线传感器网络最小连通覆盖集问题求解算法.软件学报,2006,17(2):175?184. http...
无线传感器网络最小联通... 14页 1下载券 无...无线传感器网络中的覆盖优化算法与连通问题研究 姓名...这两类基础问题都得到圆满解8 第1章绪论 决,传感...
热门文档