无线传感器网络极小连通支配集算法的改进.pdf

《无线传感器网络极小连通支配集算法的改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第25卷第6期传感技术学报V0l_25NO．6CHINESEJOURNALOFSENSORSANDACTUATORS2012年6月Jun．2012AnImprovedWirelessSensorNetworkMCDSAlgorithmZHANGring，脚Chunfu，YANGTing(1．EngineeringTeachPracticeTrainingCenter，TianjinPolytechnicUniversity，nnjin300387，China；2．CollegeofInformationTechnicalScienceofNanKaiUniversity，Tianfin3

2、00071，China3．SchoolofElectricalEngtneeringandAutomation，TianjinUniversity，Tianjin300072，China)Abstract：Eficientroutingusingvirtualbackbonenetworkamongasetofmobilehostsisoneofthemostimportantapplicationinwirelesssensornetwork(WSN)．Routingbasedonaminimumconnecteddominatingset(MCDS)isapromisedapproa

3、ch，wherethesearchingspaceforarouteisreducedtonodesintheset．BasedonWLalgorithm，animprovedminimumconnecteddominatingsetisproposedinthispaper．Thesimulationresultsshowthatthesizeoftheresultantconnecteddominatingsetissmallandtheproposedalgorithmoutperformstwopreviousdistributedal—gorithms．Itcanbepoten

4、tiallyusedindesigningeficientroutinginWSN．Keywords：wirelessnetwork；distributedalgorithm；connecteddominatingset；virtualbackbonenetworkEEACC：6150Pdoi：10．3969／j．issn．1004—1699．2012．06．024无线传感器网络极小连通支配集算法的改进术张静．贾春福，杨挺(1．天津工业大学工程教学实习训练中心，天津300387；2．南开大学信息技术科学学院，天津300071；3．天津大学电气与自动化工程学院，天津300072)摘要：无线

5、传感器网络中，基于极小连通支配集的虚拟骨干网的构建使得路由搜索空间集中在支配节点之间．能够有效节省网络资源，减少冗余转发节点。首先提出连通支配集的数学模型。基于wL算法，提出改进的极小连通支配集分布式算法。仿真结果表明，改进算法求得的连通支配集较小，可为无线传感器网络中的路由协议提供通讯基础。关键词：无线传感器网络；分布式算法；连通支配集；虚拟骨干网中图分类号：TP393文献标识码：A文章编号：1004—1699(2012)06—0842—05集成了传感器、微机电系统和网络三大技术而形应的子网的大小。不幸的是，对大部分图来说。求一成的传感器网络是一种全新的信息获取和处理技个MCDS的问题

6、属NP—C问题l8J，在实际应用中需要术[1-3]。在无线传感器网络中，除了少数节点需要移设计近似求解算法。目前已有的算法主要分两类，集动以外．大部分节点都是静止的。它要求设计的算法中式算法0j和分布式算法l_1卜”]。集中式算法要求必须具有快速收敛的特性，减少路由查找的开销．提每个节点具有整个网络的拓扑结构信息，因而不适合高路由发现的性能和效率。基于最小连通支配集的移动网络多变的特点，可伸缩性差。分布式算法的主路由方法是一个很好的分层路由l4方法。它将路由要思想是通过节点之间的局部交互操作在网络中迅过程简化到生成的较小的子网中。这意味着在先应速构造一个虚拟骨干网。式路由中只有网关节点需

7、要维持路由信息，而在反应有关连通支配集的算法，国内外已经有许多人式路由中研究空间被简化到这个MCDS中。MCDS从事这一方向的研究。其中wLll川提出了求解连中的网关节点构成了高一级的虚拟骨干网，而每个网通支配集的简单且有效的方法，随后又提出多种改关节点在自己的簇中都起着控制中心的作用，用于路进算法。WL算法求解连通支配集分为标记阶由分组和广播路由信息。明显地，这种方法的有效性段和优化阶段．由于分步实施算法具有不完整性，即很大程度上