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

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

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

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 k and m values.The algorithm can be extended in the heterogeneous network.It constructs connected do-minating 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.