无线传感器网络中2-连通k-支配的容错连通支配集构造  

Constructing 2-connected k-dominating sets for fault-tolerant backbone in wireless sensor networks

作　　者：郑婵[1,2] 尹令[2] 孙世新[1] 

机构地区：[1]电子科技大学计算机学院,成都610054 [2]华南农业大学信息学院,广州510642

出　　处：《控制与决策》2013年第5期650-656,共7页Control and Decision

基　　金：国家自然科学基金项目(41176026;40904011)

摘　　要：无线传感器网络可采用连通支配集的虚拟骨干技术使平面网络层次化,但传感器节点的失效和链路的断裂会导致网络失败,虚拟骨干网最好具有容错性好、可靠性高的特性.对此,提出具有容错性的2-连通k-支配集的构造算法,以节点自身和邻域信息分布式地构造k-支配节点,利用最小生成树和块-割点图将k-支配节点2-连通.理论分析和实验仿真表明此算法具有较好的算法性能比,在中等规模网络中会产生更少的具有容错性的k-支配节点,可节省传感器节点的能量消耗和网络的通信开销.Virtual backbones based on connected dominating sets（CDS） help to optimize multi-level hierarchical networks from fiat models in wireless sensor networks. However, the backbones are vulnerable due to frequent node/link failures. Therefore effective approaches are needed to make the virtual backbones fault-tolerant and highly reliable. In this paper, a distributed algorithm of 2-connected k-dominating set construction is proposed in unit disk＇graph network model. The informations of every node and its neighborhood are used to construct k-dominating sets distributedly, and then k-dominating sets are 2-connected. The complexity, approximation ratio and performance of the algorithm are given through theoretical analysis. Experimental simulations show that the algorithm can produce less k-dominating nodes than traditional approaches.

关 键 词：无线传感器网络 虚拟骨干 k-支配集 2-连通k-支配集 容错 

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