无线传感器网络最小覆盖集的贪婪近似算法  

Greedy Approximation Algorithm of Minimum Cover Set in Wireless Sensor Networks

作　　者：陆克中[1,2] 孙宏元[3] 

机构地区：[1]深圳大学计算机与软件学院,广东深圳518060 [2]深圳大学国家高性能计算中心深圳分中心,广东深圳518060 [3]深圳大学ATR国防科技重点实验室,广东深圳518060

出　　处：《软件学报》2010年第10期2656-2665,共10页Journal of Software

基　　金：国家自然科学基金No.60602066;广东省自然科学基金No.2008254;广东省科技计划项目No.2006B36430001~~

摘　　要：网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.Network lifetime is a bottleneck that restricts the development of wireless sensor networks. One approach to save energy effectively and prolong network lifetime is to schedule some nodes to work and put other nodes into a low-powered sleep mode, while monitoring performance of network. The object of scheduling nodes is to obtain a minimum node set that can cover a monitored region. This is a NP-hard problem. Performances of present approximation algorithms have not been good. An approximation algorithm of a minimum cover set problem based on methodology is proposed. During the process of constructing a cover set, effective node that extends to maximal areas are selected to join the cover set. Theoretical analyses show that the algorithm can construct a cover set that perform well and has a time complexity that is O（n）, where n is initial node number. Experimental results show that performance of this new algorithm outperform that of present algorithms. The size of a cover set is decreased by 14.2%. Also, execution time is less than that of present algorithms. When initial nodes are deployed densely, the average degree of coverage obtained by the algorithm is below 1.75 and has an approximation ratio below 1.45.

关 键 词：无线传感器网络 网络生命期 节点调度 最小覆盖集 贪婪算法 近似算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]