为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

【word】 基于路由最短路径树的动态多节点删除算法

2017-12-01 13页 doc 34KB 14阅读

用户头像

is_729658

暂无简介

举报
【word】 基于路由最短路径树的动态多节点删除算法【word】 基于路由最短路径树的动态多节点删除算法 基于路由最短路径树的动态多节点删除算 法 第37卷 VlO】-37 第5期 NO.5 计算机工程 ComputerEngineering 2011年3月 March20l1 ?网络与通信?文章编号:10o0_-_3428(2011)05—0121—一13文献标识码:A中图分类号:TP393 基于路由最短路径树的动态多节点删除算法 粱德恒,姚国祥,官全龙 (暨南大学信息科学技术学院,广州510632) 摘要:提出一种基于路由最短路径树的多节点删除动...
【word】 基于路由最短路径树的动态多节点删除算法
【word】 基于路由最短路径树的动态多节点删除算法 基于路由最短路径树的动态多节点删除算 法 第37卷 VlO】-37 第5期 NO.5 计算机工程 ComputerEngineering 2011年3月 March20l1 ?网络与通信?文章编号:10o0_-_3428(2011)05—0121—一13文献标识码:A中图分类号:TP393 基于路由最短路径树的动态多节点删除算法 粱德恒,姚国祥,官全龙 (暨南大学信息科学技术学院,广州510632) 摘要:提出一种基于路由最短路径树的多节点删除动态算法.算法建立一个最短路径树更新队列,将所有将被删除节点的子孙节点保存 到该队列;从原最短路径树中删除需要被删除的节点和其所有子孙节点;从队列中选取与根节点距离最短的节点进行更新,己更新节点不 再被插入队列,从而减少节点更新次数.实验结果表明,该算法能有效 减少节点的更新冗余. 关健诃:最短路径;动态更新;路由算法;多节点 DynamicMulti—nodeRemoveAlgorithm Based0nRoutingShortestPathTree LIANGDe-heng,YAOGuo-xiang,GUANQuan-long (CollegeofInformationScienceandTechnology,JinnanUniversity,Guangzhou510632,China) [Abstract]Thispaperproposesamulti—noderemoveddynamicalgorithmba sedonroutingShortestPathTree(SPT).Thealgorithmestablishesan SPTupdatequeuetopreserveallthedescendentnodesofremovednodes;deletesnodesthatneededtoberemovedandtheirdescendentnodesfrom originalSPT;selectsanodewiththeshortestdistancetothesourcenodefromthequeuetocarryontheupdating.Inordertoreducetheupdated frequency,thenodecannotbeinsertedintothequeueagainafterupdating.Experimentalresultshowsthatthisalgorithmcanlargelyreducethe updatedredundancy. [KeywordsIshortestpath;dynamicupdate;routingalgorithm;multi—node D0I:10.39690.issn.1000—3428.2011.05.041 1概述 在信息化程度越来越高的社会中,人们迫切希望得到高 速网络进行信息交换,这意味着计算机网络必须提供更高的 路由速度.在一些广泛使用的协议中,如OSPF和Is—Is,每 一 个路由器都以自己为根生成一棵最短路径树,并通过一张 路由表到达每一目的地的开销.然而,当网络拓扑结构 改变时,当前最短路径树和路由表需要及时得到更新.显然, 高效的最短路径树(ShortestPathTree,SPT)更新算法将大大 减少路由器的计算时间,进而提供更高的路由速度.SPT更 新算法分为静态和动态2类:静态算法并没有借助旧SPT的 有效信息而重新计算SPT,如Dijkstra;动态算法在旧SPT 的基础上,只更新需要更新的节点,从而生成新的SPT.很 明显,后者的效率更高.因此,本文只讨论动态的SPT更新 算法. 2更新冗余问题 文献[1】的算法对链路权值的增加和减少分进行分类处 理,其计算复杂度与静态方法相比得到减少,但存在一定的 冗余计算.此后,文献【2—3]提出的更新算法减少了冗余计算. 文献[4—6】的对最短路径树进行了进一步研究.虽然以上所有 文献对由于边的权值改变而更新最短路径树的方法已进行了 深入的研究,但对多个网络节点的增加或删除并没有给出详 细的解决方法.文献[7】给出了网络节点增加或删除的解决方 法,但在处理多个网络节点删除时,存在大量的冗余计算. 鉴于以上算法存在的一些不足,本文提出一种基于路由最短 路径树的多节点删除动态算法(Multi—nodeRemovedDynamic AlgorithmofShortestPathTree,MRDA—SPT). 在CD—SPT(CompletelyDynamicofShortestPathTree)t】 算法中,当多个网络节点被删除时,先将这些节点分成2组, 将其中一个节点放在第2组,其余所有节点放在第1组.更 新算法先处理第2组,在I13的SPT中删除本组的节点并更新 其子孙节点,生成临时SPT,然后再从第1组分出一个节点 放在第2组,继续进行处理,直至第1组没有节点.该算法 处理2个节点被删除的过程如图1所示. (a)更新前 FF (b)临时(c)更新后 图1CD—SPT算法的节点?除过程 可以看出,节点C和E是被删除的节点,分别将节点C 和E放到第2组和第1组,首先对第2组进行处理,删除节 点C,并更新节点D,E和F,生成临时SPT,最后删除节点 基金项目:国家自然科学基金资助项目(60773083);广东省高校科技 成果转化基金资助重大项目(cgzhzd0807);广东省教育部合作专项基 金资助项目(2008B090500201);广东省科技基金资助项目(2009 B010800023) 作者倚介:梁德恒(1985一),男,硕士研究生,主研方向:网络安全, 网络编码;姚国祥,教授,博士生导师;官全龙,博士 收稿日期:2010—07.24E-mail:hanson_lang@yahoo.cn 122计算机工程2011年3月5日 E,节点F再次被更新,生成最新的SPT.使用该算法,节3.3 点F被更新2次,而且被删除节点E也被更新一次,由此可 见,该算法存在更新冗余. 3MRDA—SPT算法设计 3.1算法符号说明 G(V,E,W):网络拓扑冈,其中,y表示节点集;E表示 边集;W表示E中的边的权值. Q:一个更新队列. v:一个节点,d表示节点v到源节点的距离,p表示 节点V的父节点. D(v):节点v到源节点的最短距离. P(v):节点的父节点. De}(n):节点n的所有子孙节点组成的集合. SP_,(:由节点集构成的SPT. Del(G):拓扑图G中所有被删除节点组成的集合. date(G):拓扑图G巾所有被删除节点的所有子孙节点 组成的集合. Source_part(N):所有节点,为起点的边. EndM)art(~J:所有以节点?为终点的边. 3.2算法设计思想 关于最短路径树的动态更新,在文献f1,7】中已给出了成 熟的算法,笔者在前人的基础上提出MRDA—SPT算法.该 算法主要围绕在多个网络节点被删除的情况下,如何减少更 新最短路径树的更新冗余.MRDASPT算法的实现基于如下 2个原理: (1)所有被删除节点的所有子孙节点的更新,不会影响其 他节点. (2)从所有被删除节点的所有子孙节点中选取一个到达 最短路径树SPV—Del(G)一Update(G))的根节点最近的节点进 行更新,此后,它不受其他节点更新的影响,即其不必再对 其更新. 该算法需要的基本操作定义:Enqueue(Q,表示节点v?): 判断执行此操作的节点v?是否已加入到队列Q,若没加入则 直接将该节点加入到Q,若已经加入则判断v?.d是否小于Q. „d,即v?.d是否小于节点v?原来保存在Q中的最短路径, 若小于则用v?.d代替Q.?.,否则不执行其他操作.Find(Q): 从队列中选取最短距离最小的节点v?,即v?.是最小的. 该算法的基本步骤如下: (1)等待多个网络节点被删除,记为n个. (2)对所有被删除节点的每个子孙节点都执行(3). (3)假定将执行此操作的节点v?加到SP兀V-DeI(G)一 Update(G))中,计算出v?到达根节点的最短距离(v?.d)并记录 其父节点(„.P),然后以v?为参数执行Enqueue(Q,v?)操作. (4)Temp=V-Del(G)一date(G),其中,Temp是一个临时 的节点集合. (5)判断队列Q中是否为空,若是则算法结束,跳转N(I), 否则执行Find(Q)操作. (6)对Find操作返回的节点v进行更新,D()=v.d,P()= v.P,然后将v加入到PTemp),生成尸r厂(Temp+v). (7)Temp=Temp+v. (8)找出所有以节点v为起点以节点v”为终点(v”存在Q 中)的边e,设置v”.=D(v)+w(e),v”.p=,然后以v”为参 数执行Enqueue操作. (9)跳转到(5). 算法实现 算法伪代码如下 1.1nitialtion: GetSPT(V)FromG=(V,E,W) 2Multinoderemoved: Waitunti1knodesni,i=l,2,…,k,areremoved Fori:1tOkdo Ifn,?Qthen removenIfromQ continue EndIf ForV?Des(ni1do Mindstance=.. Fore?Endart(v)do IfS(c)==P(v)then Continue TfD(S(e))十w(e)<Min—distance Min_distance=D(S(e))+w(e) P=S(e, EndFor IfMindistance??then Enqueue(Q,fv,(Min—distance,p)}) EndIt EndFor EndFor 3Update: WhileQ?do {V,(d,P))+_Find(Q),removeVfromQ Dfv1=V.d P(v1=V.d Fore?Source_ pa~(v1do IfE(e)?Qthen Enqueue(Q,{E((e),(D(S(e))+w(e),V))) EndIf EndFor EndWhile Goto1 使用MRDA—SPT算法更新如图1中的2个节点被删除 的最短路径树时,先将节点c和节点E的子孙节点放入队列 Q,然后删除原SPT中的节点c,节点E和它们的所有子孙 节点,生成如图2所示的尸V-DeI(G)一date(G)). 图2删除节点后的SPT 分别将节点D和节点F添加到P兀V-Del(G)一Update(G)) 中时,其最短距离分别为9和11,因为,节点D的最短距离 较小,因此,首先将D添加到SP丁(V-Del(G)一Update(G)),最 后选取F添加到P7丫V-Del(G)一Update(G)+D).在这里节点D 和节点F都只被更新一次,与文献【7]的CD—SPT算法相比, 冗余度得到减少. 4算法复杂度和性能评价 4.1算法的冗余度和时间复杂度分析 为更好地分析算法冗余度,这里以k表示删除的节点数, 以U表示被更新过的节点数,以U表示所有被更新节点中总 共被更新过的次数.在一个给定的SPT中,当需要删除的节 点被确定后,U的值也就被确定了.在MRDA—SPT中,当一 个节点被删除后,该节点在旧SPT中的子孙节点都需要被更 第37卷第5期梁德恒,姚国祥,官全龙:基于路由最短路径树的动态多节点删除算法123 新,这意味着,??lDes(n.)1,k最多为”,而lDes(n)f小于 等于U.因此R,的上界为U. 在本文算法中,把需要更新的节点插入队列Q和从队列 Q选取节点是时间复杂度的关键,由于插入一个节点的时间 是0(1),每一个被删除节点的子孙节点都要被插入队列, 而且还要计算这些子孙节点加入SPT(V-DeI(G)一Update(G))后 的最短距离,所以插入所有需更新的节点的复杂度为 O(kuNm),是节点的最大入度.由于需要从队列选取节 点次,而每次搜索队列的时间复杂度为O(u),所以从队列 选取所有节点时问复杂度为O(u).而总的时间复杂度为 O(kur?m+u2). 4.2性能评价 为了验证MRDA—SPT算法的有效性,实验使用VC++6.0 实现MRDA—SPT,CD,SPT和Dijkstra算法,而所使用的硬 件环境是:1台双核PC,内核频率2,2GHz,内存2GB,硬 盘300GB.实验中随机生成网络拓扑,并生成其最短路径树, 然后任意删除30个节点,最后更新最短路径树.这里随机生 成边的权值为1,100之间的任意整数.3种算法在4个不同 规模的网络下执行10次.表I列出这3种算法删除30个节 点需要更新节点的次数和平均运行时间. 表1算法比较结果 网络删除 节点数节点数 更新节点次数平均运行时间/ms 图3,图4分别表示在删除节点过程中,3种算法更新最 短路径树时对节点更新的次数和所需的运行时间.显然,动 态更新算法在节点更新次数和运行时间上均优于静态更新算 法,而MRDA—SPT的节点更新次数和运行时问都小于 CD—SPT算法,而且随着网络节点数量的增加,MRDA—SPT 在性能上的优势越来越明显. 鼎 壤 告点数 图3删除节点时需要更新节点的次数 点数 图4删除节点时更新所需的平均时间 5结束语 本文提出了MRDA—SPT算法,以处理网络中多节点出 故障或被删除的情况.虽然该算法的时间复杂度与CD—SPT 算法的时间复杂度相当,但该算法能有效减少需要被更新的 网络节点更新次数.实验证明,MRDA—SPT算法较CD—SPT 算法进一步减少了节点的更新冗余.在实际应用中,由于多 个网络节点删除只是其中一种情况,因此改善同时处理多节 点增删和多边权值变化的算法性能是进一步提高网络速度的 研究方向. 参考文献 [1]NarvaezSiuKar—Yeung,TzengHong—Yi.NewDynamicAlgo— rithmsforShortestPathComputati—onlJ】IEEE/ACMTransactions onNetworking,2000,8(6):734—746. [2】NarvaezSiuKar—Yeung,TzengHong—Yi.NewDynamicSPT AlgorithmBasedonaBall?and—stringModel[J].IEEE/ACM TransactionsonNetworking,2001,9(6):706—718 [3】XiaoBin,CaoJiannong.DynamicShortestPathTreeUpdatefor MultipleLinkStateDecrements[Cl//ProcofGlobecom?04.Dallas, Texas,USA:[S.n_],2004 【4]付天成,莫松海,王晖,等.基于Agent的动态路网行车最短 路径求解IJ1l计算机工程,2008,34(20):203.204. 【5]CamposR,RicardoM.AFastAlgorithmforComputingMinimum RoutingCostSpanningTreeslJ].ComputerNetworks,2008, 52rl71:3229—3247. [6】ShiodaS,OhtsukaK,SatoAnEfficientNetworkwideBroad— castingBasedonHop—limitedSho~est—pathTreeslJ].Computer Networks,2008,52r17):3284—3295. [7]孙知信,高艳娟,王文鼐.更新最短路径树的完全动态算法【Jll 吉林大学,2007,37(4):860—864 编辑顾姣健 (上接第120页) 参考文献 [1]ZhangZhensheng.DTRA:DirectionalTransmissionandRecep— tionAlgorithmsinWLANswithDirectionalAntennasforQoS Suppo~[J].IEEENetworks,2005,19(3):27—32. [2]NasipuriA.AMACProtocolforMobileAdhocNetworksUsing DirectionalAntennas[C]//Proc.ofWCNC?00.Chicago,USA: ACMPress.2000 [3]UedaT.AnEfficientMACProtocolwithDirectionFinding SchemeinWirelessAdhocNetworkUsingDirectional Antenna[Cl//Proc.ofRAWCON?03Boston,USA:IEEEPress, 2003 l4]PanYuxin,HamoudaW,ElhakeemAAnEfficientMedium AccessControlProtocolforMobileAdhocNetworksUsing AntennaArrays[J].CanadianJournalofElectricalandComputer Engineering,2007,32(1):19—25. [5]张筠,李颖.移动AdHoc网络中定向发送与接收算法的改 进『JI.计算机工程,2009,35(5):122一l24. [6]GandhamS,DawandeM.LinkSchedulinginSensorNetworks: DistributedEdgeColoringReVisited【C],/ProceedingsofIEEE INFOCOM?05.Miami,USA:【S.n.】,2005 【7]殷剑宏,吴开亚.图论及其算法IM1.合肥:中国科技大学出版 社,2003. 编辑顾姣健 蚪 卯姐 船 0O00m加?? “… 卯 ?如如? 00OOm如如如
/
本文档为【【word】 基于路由最短路径树的动态多节点删除算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索