中文摘要：

构造无线传感网络中具有连通覆盖特性的节点子集是实现网络休眠调度、延长网络生命周期的关键技术之一,具有重要的研究意义.已有的研究大多侧重于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.