无线传感器网络最小连通覆盖的节能算法  

Energy Saving Algorithm for MCCS in WSN

作　　者：陈业纲[1] 徐则同[2] 

机构地区：[1]长江师范学院数学与计算机学院,重庆408100 [2]中国科学院数学研究所,北京100190

出　　处：《计算机仿真》2014年第3期324-327,350,共5页Computer Simulation

基　　金：重庆市教委科学技术研究项目(KJ131322)

摘　　要：网络的生存期是WSN发展的一个障碍,降低能耗是WSN设计的一个方向,在性能得以保障的前提下,用最少的节点投入工作是节能的有效方法。在目标区域中寻找最小连通覆盖集(MCCS)是一个NP问题,设计了通过CVT+MST构造MCCS的节能算法,当节点的通讯半径大于等于感知圆盘2倍时,CVT求得的就是MCCS,否则需要用MST算法计算WSN的最大独立子集添加辅助节点使之成为MCCS,通过仿真和性能分析,上述节能算法具有时间复杂度低,满足节点均匀环境的要求,为延长网络生存期的研究提供了依据。The drawback in the development of WSN is its network life cycle. One of the aims of WSN design is to reduce energy consumption, i.e. , to apply the minimum nodes without sacrificing efficiency is a valid method to save energy. Searching for MCCS in the target area is an NP problem, which provides an energy-saving algorithm based on CVT＋MST structure. When the communication radius of the node is twice as long as that of the perception disc, the result of CVT is MCCS, otherwise, the MST algorithm should be applied to calculate the maximum independent sub- sets of WSN appending auxiliary nodes, thus to get MCCS. Through the simulation and the performance analysis, the energy-saving algorithm provides the rationales for the study of prolonging the network life cycle with the advantage of low time complexity and meeting the needs of well-distributed condition of the nodes.

关 键 词：最小连通覆盖集 最大独立子集 无线传感器网络 

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