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

《无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第25卷第5期传感技术学报V01．25No．52012年5月CHINESEJOURNALOFSENSORSANDACTUATORSMav2012Constructingd-Hop2-ConnectedDominatingSetsforFault-TolerantBackboneinWirelessSensorNetworksZHENGChan，YINLing，SUNShixin(1．CollegeofComputerScienceandEngineering，UniversityofElectroni

2、cScienceandTechnology，Chengdu610054，China；2．Collegeof，rmation，SouthChinaAgriculturalUniversity，Guangzhou510642，China)Abstract：Wirelesssensornetworksareself-maintainingandself-organizingstructureswithsensorsnodesmovingaround．Thevirtualbackbonebaseonconne

3、cteddominatingsets(CDS)helpstooptimizemulti—levelhierarchicalnetworksfromflatmodels．HoweverthesizeofCDSnodesisstilllargeinlarge—scalewirelesssensornetworks．Thusd-hopCDSwhichisgeneralizedfromtheconceptofCDScanfurtherreducethevirtualbackbones．Otherwisevir

4、tualbackbonesareoftenveryvulnerableduetofrequentnodefailureandlinkbroken，whichareinherentinwirelessnetworks．Itisdesirablethatthevirtualbackboneisfaulttolerantsincethenodesinthevirtualbackboneneedtocarryothernode'straffic．Adistributedalgorithmofd-hop2一co

5、nnecteddominatingsetconstructionwasproposedinunitdiskgraphnetworkmodelinthispaper．Themajorstrategyweusedwasclusteringpartition．Ad-hopdominatingsetwasselectedfromeachclusterfirstly．andthensomeconnectornodeswereaddedtomakefinalsub-solutions2-connected．The

6、complexity，approximationratioandperformanceofthealgorithmweregiventhroughtheoreticalanalysisandsimulations．Keywords：wirelesssensornetworks；virtualbackbone；d-hopconnecteddominatingset；2-connecteddominatingset；unitdiskgraphEEACC：6150P；7230doi：10．3969／j．is

7、sn．1004—1699．2012．05．026无线传感器网络中d-H0p2．连通容错支配集的分布式构造算法米郑婵，尹令，孙世新(1．电子科技大学计算机学院，成都610054；2．华南农业大学信息学院，广州510642)摘要：无线传感器网络随节点移动组成自我维持的自组织系统，采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大，d-hop连通支配集可以大大减小支配集节点数目。另外，由于存在节点失效、链路断裂等无线特性，虚拟骨干

8、网需要具备一定的容错性。在单位网盘图网络模型巾为构建精简且具有容错能力的虚拟骨干网，提出d—hop2-连通支配集的分布式构造算法，先构造d—hop独立支配集后再连通形成d-hop2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证关键词：无线传感器网络；虚拟骨干；d—hop连通支配集；2一连通支配集；容错；单位圆盘图中图分类号：TP393文献标识码：A文章编号：1004—1699(2012)05—0696—06无线传感器网