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

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

作　　者：马晨明[1] 王万良[2] 洪榛[3] 

机构地区：[1]浙江工业大学信息工程学院,杭州310023 [2]浙江工业大学计算机科学与技术学院,杭州310023 [3]浙江理工大学机械与自动控制学院,杭州310018

出　　处：《计算机科学》2016年第1期128-132,158,共6页Computer Science

基　　金：国家自然科学基金(61402414;61304256;61379123);"十二五"国家科技支撑计划(2012BAD10B01);浙江省自然科学基金(LQ14F020005;LQ13F030013);浙江省教育厅项目(Y201431815;Y201327006)资助

摘　　要：采用连通支配集作为虚拟骨干可以延长无线传感器网络的生命时间,但是考虑到节点容易失效,虚拟骨干还需要具有一定的容错性。对此,针对任意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.

关 键 词：无线传感器网络 容错 k-连通m-支配集 异构 分布式算法 

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