无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法  

Constructing d-Hop 2-Connected Dominating Sets for Fault-Tolerant Backbone in Wireless Sensor Networks

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

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

出　　处：《传感技术学报》2012年第5期696-701,共6页Chinese Journal of Sensors and Actuators

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

摘　　要：无线传感器网络随节点移动组成自我维持的自组织系统,采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大,d-hop连通支配集可以大大减小支配集节点数目。另外,由于存在节点失效、链路断裂等无线特性,虚拟骨干网需要具备一定的容错性。在单位圆盘图网络模型中为构建精简且具有容错能力的虚拟骨干网,提出d-hop 2-连通支配集的分布式构造算法,先构造d-hop独立支配集后再连通形成d-hop 2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证。Wireless sensor networks are self-maintaining and self-organizing structures with sensors nodes moving around. The virtual backbone base on connected dominating sets （CDS）helps to optimize multi-level hierarchical networks from fiat models. However the size of CDS nodes is still large in large-scale wireless sensor networks. Thus d-hop CDS which is generalized from the concept of CDS can further reduce the virtual backbones. Otherwise virtual backbones are often very vulnerable due to frequent node failure and link broken,which are inherent in wireless networks. It is desirable that the virtual backbone is fault tolerant since the nodes in the virtual backbone need to carry other node＇s traffic. A distributed algorithm of d-hop 2-connected dominating set construction was proposed in unit disk graph network model in this paper. The major strategy we used was clustering partition. A d-hop dominating set was selected from each cluster firstly, and then some connector nodes were added to make final sub-solutions 2-connected. The complexity,approximation ratio and performance of the algorithm were given through theoretical analysis and simulations.

关 键 词：无线传感器网络 虚拟骨干 d-hop连通支配集 2-连通支配集 容错 单位圆盘图 

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