无线传感器网络中最优覆盖节点集的求解算法  

Optimal Coverage Algorithm of Sensor Nodes Set Selection in Wireless Sensor Network

作　　者：贾杰[1] 陈剑[1] 常桂然[2] 赵林亮[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004 [2]东北大学计算中心,辽宁沈阳110004

出　　处：《东北大学学报（自然科学版）》2007年第11期1560-1563,共4页Journal of Northeastern University(Natural Science)

基　　金：教育部高等学校博士学科点专项科研基金资助项目(20030145017);国家高技术研究发展计划项目(2003AA712032)

摘　　要：在传感器节点高密度部署的环境中,如何保证在满足"覆盖要求"的同时,使用的节点数目最小是一个NP完全问题.结合遗传算法在处理集合搜索中的广泛应用,设计了一种基于遗传算法的节点集搜索机制.在保证充分覆盖的前提下,令一部分冗余节点进入低功耗休眠状态,形成最优覆盖节点集.最后进行了算法的性能评价和网络覆盖的仿真实验.结果表明,该算法能以较小的代价完成最优节点集的搜索,有效提高整个网络的生存时间.With respect to the high-density deployment of wireless sensor networks, a NP- complete problem is to be solved, i.e., how to find out the minimal number of nodes with the target region fully covered simultaneously. A new optimal algorithm for selecting the set of nodes is thus designed on the basis of genetic algorithm. With the full network coverage provided and part of redundant nodes entering into dormancy, an optimal coverage set of nodes is formed. A simulation test was done to evaluate the performance of the algorithm for network coverage, and the result showed that it can achieve an optimal selection of the set of nodes in hundreds at low cost, thus prolonging efficiently the network lifetime.

关 键 词：无线传感器网络 覆盖问题 节点集 遗传算法 网络生存时间 

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