无线传感器网络(k,m)-容错连通支配集的分布式构建

Distributed Construction for (k,m)-Fault Tolerant Connected Dominating Set in Wireless Sensor Network

采用连通支配集作为虚拟骨干可以延长无线传感器网络的生命时间,但是考虑到节点容易失效,虚拟骨干还需要具有一定的容错性。对此,针对任意k和m取值,提出了一种完全分布式的k-连通m-支配集构建算法,其中k-连通保证了网络中支配节点之间的容错性,m-支配则保证了普通节点与支配节点之间的容错性。该算法可以在异构网络中进行扩展,首先构建连通支配集,然后采用最大独立集和贪心的思想将普通节点进行m支配,最后在局部拓扑中通过公共邻居节点将连通支配集扩展为k-连通。仿真实验证实,该算法可以通过较低的通信开销获得规模较优的k-连通m-支配集。

Virtual backbone based on connected dominating set can prolong the lifetime of wireless sensor network.However,considering nodes are prone to failure,virtual backbone also needs to have a certain degree of fault tolerance.In this regard,a fully distributed algorithm was proposed for fault tolerance constructing k-connected m-dominated set for arbitrary kand mvalues.The algorithm can be extended in the heterogeneous network.It constructs connected dominating set firstly,then makes all common nodes m-dominating with the idea of maximum independent set and greedy,and finally extends the connected dominated set k-connectivity by the common neighbor nodes in the local topology.Simulation experiments confirm that the algorithm can obtain better size k-connected m-dominating set with low message overhead.