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

无线传感器网络随节点移动组成自我维持的自组织系统,采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大,d-hop连通支配集可以大大减小支配集节点数目。另外,由于存在节点失效、链路断裂等无线特性,虚拟骨干网需要具备一定的容错性。在单位圆盘图网络模型中为构建精简且具有容错能力的虚拟骨干网,提出d-hop 2-连通支配集的分布式构造算法,先构造d-hop独立支配集后再连通形成d-hop 2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证。

Constructing d-hop 2-Connected Dominating Sets for Fault-tolerant Backbone in Wireless Sensor Networks

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 flat 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.