【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如如如