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

在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网以进行分层路由。本文提出一个2-连通2-支配集的分布式构造算法,由2-连通2-支配集构成的虚拟骨干网在任意1个支配点发生故障时仍能生存。算法的主要思路是从任一节点开始,在局部形成一个由支配点组成的回路,以此回路为基础,不断地形成由支配点组成的回路直到不在回路中的节点是2-支配为止。模拟实验表明,该算法构造的连通支配集的尺寸明显优于现有算法。

Distributed Construction of 2-Connected 2-Dominating Set in Wireless Sensor Networks

In wireless sensor networks, a virtual backbone network constructed by a connected dominating set is a promising approach for layered routing. In this paper we propose a distributed algorithm to construct a 2-connected 2-dominating set. The virtual backbone network constructed by the 2-connected 2-dominating set still exists when any node in the network is failure. It starts from any node, and forms a localized loop made by the dominating nodes. Based on this loop, we continue to construct other loops formed by the dominating nodes until the nodes outside loops are 2-dominated.Simulation results show that the size of the connected dominating set is better than those of the previous works.