基于最短路径树的节点删除动态路由算法(1)

书书书 学术研究 !"#!!"#$%&%'(#)**+#!""!,$-./#."!.#"&#"!! 基于最短路径树的节点删除动态路由算法 收稿日期!."!.,"0,.. 江宝安!! . "!#电子科技大学 电子工程学院#成都 &!""0/$ .#重庆邮电大学 移通学院#重庆 /"!0."% 摘1要!提出一种基于最短路径树的节点删除动态路由算法" 算法建立一个最短路径树更新集合!该集合包括被 删除节点的断裂子树所有节点和其它节点连接的边!利用子树的结构信息!对子树节点的直系子孙节点和祖先节 点进行更新!采用2)(3*456算法对其它子树节点进行更新" 实验结果明!该算法能有效减少节点更新计算次数" 关键词!2)(3*456算法# 最短路径#动态路由算法 中图分类号!78$%$#"$111111111文献标识码!9 文章编号!!""0,$-./$."!.%"&,""/!,". $%引%言 已知源节点到所有节点的最短路径树":87%# 若某一节点被删除#需重新生成最短路径树& 文献 '!(的算法对链路权值的增加和减少分别进行分类 处理#其计算复杂度与静态相比得到减少#但 存在一定的冗余计算& 文献'.,$(提出的更新算法 减少了冗余计算#文献'/,0(中对最短路径树进行 了进一步研究& 虽然以上所有文献对由于边的权 值改变而更新最短路径树的方法已进行了深入的 研究#但对网络节点的删除并没有给出详细的解决 方法& 鉴于此#本文提出一种利用子树结构信息的 动态路由算法#该算法利用子树结构信息对子树节 点的直系子孙节点和直系祖先节点进行更新#采用 2)(3*456算法对其他子树节点进行更新#能有效减少 节点的更新次数& &%算%法 算法要点如下! !%更新集合"!#"%& !为子树所有节点和其他 节点连接的边#"为子树所有节点& .%子树结构信息利用& 若子树某一节点更新# 利用子树结构信息更新这一节点所有直系子孙节 点和所有直系祖先节点& $%其他子树节点更新应用2)(3*456算法& 8*;<=>,6?@>5)4AB! C)D;+ 6 E;)@A4;= C56@A#""#!% # EA;5;")*4A;*;4>F G;54)H;*#6+=!)*4A;*;4>FI=@;*# :+!" & '"(" $% $!'"" $% #" & % $ )"*% ')+F# * ! " $% $ EA)?;!)*+>4;BM4N) * + ! " & #* , ! " $% #-"* + #* , % ! !) ) ".% "* , % ')"* + % /0"* + #* , % KF) ".% "* , % 1)"* , % )"* , % " ) ".% "* , % OM=64;! OM=64)+@6???)+;6?=;*H;+=6+4+>=;*6+= 6+H;*4>5 +>=;*>F* , # =;*>F*5)4AB# I+= )F * ! " !(-* I+= EA)?; ><4M<4!Q5;64)+@6+;E5><4)+@:87& '%仿%真 为了验证本算法的有效性#实验中随机生成具 有 ."" 个节点的网络拓扑#边权值为两点间的距离# 并生成其最短路径树"如图 ! 所示%#然后删除一节 点 !!0#最后得到更新最短路径树"如图 . 所示%& 所 使用的硬件环境是!!台双核8Q#内核频率 $R. CSL# 内存 . CT#硬盘 0"" CT# 软件使用B64?6J语言编程 +!/+ 学术研究 !"#"$%&'())*+"'%$"(+,-./-0/- 实现& 图 ! 原最短路径树耗时 /UR0$ *#图 . 新的最 短路径耗时 "R"!! *#由此比较#验证了本算法的有 效性& 图 &%原最短路径树 图 '%新最短路径树 (%结%论 本文提出利用子树结构信息的动态路由算法# 以处理网络中节点出故障或被删除的情况& 该算 法能有效减少网络节点更新次数#算法简洁明了# 易于编程实现#对网络路由有实际的应用价值& 参考文献! &!'1V9WG9IX8! :KOYZ!7XIVCSZ#V;E=N+6B)H6?@>, 5)4AB*F>5*A>54;*4M64A H>BM<464),>+ &['#KIII'9Q\ 756+*6H4)>+*>+ V;4E>53)+@!."""!-$&%(U$/,U/&# &.'1V9WG9IX8! :KOYZ!7XIVCSZ#V;E=N+6B)H:87 6?@>5)4ABJ6*;= >+ 6J6??6+=,*45)+@B>=;?&['#KIII' 9Q\756+*6H4)>+*>+ V;4E>53)+@!.""!!%$&%(U"&,U!-# &$'1]K9PT)+!Q9P[)6++>+@#2N+6B)H*A>54;*4M64A 45;;5BH>FC?>, J;H>B^"/#26??6*!7;_6*!O:9(&*#+#'!.""/# &/'1付天成!莫松海!王晖!等#基于9@;+4的动态路网行车 最短路径求解&['#计算机工程!.""-!$/$."%(."$,."/# &0'1:SKP29:!PS7:OY9Y#9+ ;FF)H);+4+;4E>53 E)=;J5>6=, H6*4)+@J6*;= >+ A>M,?)B)4;= *A>54;*4,M64A 45;;*&['#Q>B, M<4;5V;4E>53*!.""-!0.$!U%($.-/,$.%0# 作者简介! 江宝安 $!%U/,%!男! 安徽全椒人!硕士!讲师!博士生! 研究方向为信号处理与通信网!I,B6)?J6>6+(."".`N6A>># H>B#H+" !)*+,-.*/0121,/31+45/2-67,8+910/*2/:6-*5 97/26196;+676211 [K9VCT6>6+ !#. "!#:HA>>?>FI?;H45>+)HI+@)+;;5)+@# O+)D#>FI?;H45>+#:H);+H;a7;HA#>FQA)+6# QA;+@=< &!""0/#8#W#QA)+6$ .#QA>+@b)+@O+)D;5*)4N>F8>*46+= 7;?;H>BB<+)H64)>+*# QA>+@b)+@/"""&0#8#W#QA)+6% <8962+.6!9+;E+>=;5;B>D)+@=N+6B)H6?@>5)4ABJ6*;= >+ 5><4)+@:A>54;*4864A 75;;":87% )*M5>M>*;=#c)5*4#)4;*46J?), *A;*6+ F*A>54;*4M64A 45;;#7A;*;4)+H?<=;*6??;=@;*H>++;H4)+@+>=;*>FJ5;63)+@*4A;5+>=;* >F@56MA#7A;+#)4463;*6=D6+46@;>F*455B64)>+ >F4A;*5)4AB4>=;*>F4A;*E*4A644A)*6?@>5)4ABH6+ ?65@;?N5;=/209!2)(3*456$*A>54;*4M64A 45;;$=N+6B)H5><4)+@6?@>5)4AB $责任编辑1张1诚% +./+