无线传感网络中覆盖保持的K-连通子集构造算法  

Coverage-preserving K-connected Subset Construction Algorithm in Wireless Sensor Networks

作　　者：徐涛[1,2] 黄刘生[1,2] 徐宏力[1,2] 王刚[1,2] 

机构地区：[1]中国科学技术大学计算机科学与技术系,安徽合肥230027 [2]中国科学技术大学苏州研究院,江苏苏州215123

出　　处：《小型微型计算机系统》2010年第5期871-874,共4页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展计划项目(2006CB303006)资助;中科院知识创新工程重要方向项目资助;国家自然科学基金项目(60803009;60803116)资助

摘　　要：构造无线传感网络中具有连通覆盖特性的节点子集是实现网络休眠调度、延长网络生命周期的关键技术之一,具有重要的研究意义.已有的研究大多侧重于k覆盖节点子集构造问题,由于k覆盖子集在一定条件下便满足k连通,故人们对k连通子集的构造问题研究较少,但通过构造k覆盖节点子集来实现k连通会耗费过多的节点,代价较大.因此,本文提出一个直接构造k连通1覆盖节点子集的算法-CPC,能够用较少的节点构造出一个既能满足网络的覆盖特性又能够满足k-连通特性的节点子集,使得在任意k-1个节点发生故障时,网络能够仍然保持连通.本文还对算法的正确性进行了严格证明,并通过仿真实验与相关算法进行了性能比较.结果表明,与已有的k覆盖算法相比,CPC算法能够节省约55%的节点数.Constructing a connected covering node subset is one of key technologies for enlarging lifetime and sleeping scheduling in wireless sensor networks,which is a significantly important research area. The previous researches focus on the k covering node subset construction problem. Because k covering subset is k-connected under certain conditions,people study the k-connected subset construction problem less. However,constructing k covering node subset as k-connected subset will use too many nodes,the cost is great. Therefore,this paper proposes a k-connected and 1-covered node subset construction algorithm-CPC,which can construct a node subset that is covering and k-connected with few nodes,making the network can still maintain connectivity when any k-1 nodes break down. This paper also proves the algorithm＇s correctness strictly,and compares the performance with related algorithm by simulation. Experimental results show that compared with previous k covering algorithms,CPC algorithm can save about 55% of nodes.

关 键 词：无线传感网络 K-连通 覆盖 节点子集 

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