资源描述:
《基于拓扑特性分布式虚拟骨干网算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.21,No.6,June2010,pp.1416−1425http://www.jos.org.cndoi:10.3724/SP.J.1001.2010.03572Tel/Fax:+86-10-62562563©byInstituteofSoftware,theChineseAcademyofSciences.Allrightsreserved.∗基于拓扑特性的分布式虚拟骨干网算法1+211解文斌,李佳,鲜明,陈永光
2、1(国防科学技术大学电子科学与工程学院,湖南长沙410073)2(湖南大学校办公室,湖南长沙410082)DistributedVirtueBackboneNetworkAlgorithmBasedonTopologyCharacteristic1+211XIEWen-Bin,LIJia,XIANMing,CHENYong-Guang1(SchoolofElectronicScienceandEngineering,NationalUniversityofDefenseTechnology,Changsha410073,China)2(SchoolOf
3、fice,Hu’nanUniversity,Changsha410082,China)+Correspondingauthor:E-mail:xiewenbin78@163.comXieWB,LiJ,XianM,ChenYG.Distributedvirtuebackbonenetworkalgorithmbasedontopologycharacteristic.JournalofSoftware,2010,21(6):1416−1425.http://www.jos.org.cn/1000-9825/3572.htmAbstract:Because
4、findingaminimumconnecteddominationset(MCDS)forageneralconnectednetworkisNP-complete,atopology-awareheuristicalgorithmisproposedinthispaperwhosecorrectnessisproved.Bytakingadvantageofthetopologycharacteristicofnodes,thealgorithmcanreducetheblindnessintheprocessofselectingdominati
5、ngnodes,andformasmallerCDS(connecteddominationset)basedon2-hoplocalinformation,consequentlyobtainavirtuebackbonenetworkwiththeCDS.ThesimulationresultsshowthatthealgorithmissuperiortootherdistributedCDSalgorithms,andclosertominimumCDS.Keywords:wirelessnetwork;virtuebackbonenetwor
6、k;connecteddominatingset;distributedalgorithm;topologycharacteristic摘要:由于在任意连通网络中搜索最小连通支配集(minimumconnecteddominationset,简称MCDS)是NP完全问题,提出了一种拓扑感知的MCDS启发式算法——TACDS(topology-awareconnecteddominationset),并证明了其正确性.通过利用节点的拓扑特性,减小了支配节点选择的盲目性.该算法能够根据2跳内的局部拓扑信息构造出较小的CDS(connecteddominat
7、ionset),从而得到基于该支配集的虚拟骨干网.仿真结果表明,该算法优于其他分布式CDS算法,可以更好地近似MCDS.关键词:无线网络;虚拟骨干网;连通支配集;分布式算法;拓扑特性中图法分类号:TP393文献标识码:A[1]无线传感器网络是由自治节点形成的自组织网络,模糊了网络基础设施和网络用户的差别,本质上是一种平坦型结构.传感器节点由电池供电,能量有限,节点数量多且很多情况下不易更换.因此,节能就成为无线传感器网络中最关键的问题.传感器节点的绝大部分能量消耗在无线通信上.无线通信模块主要包括发送、接收、空闲和休眠4种状态,∗Received200
8、8-03-19;Revised2008-10-06;Accepted2009-01-15解文斌