一种高效的最短路径完全动态更新算法

J4 ›› 2016, Vol. 38 ›› Issue (03): 449-453.

一种高效的最短路径完全动态更新算法

汪晓洁，郭文强，王思秀，蔡咏梅

(新疆财经大学计算机科学与工程学院,新疆乌鲁木齐 830012)

收稿日期:2015-01-10 修回日期:2015-05-15 出版日期:2016-03-25 发布日期:2016-03-25
基金资助:
国家自然科学基金（61163066）;新疆高校科研计划青年教师科研启动基金（XJEDU2014S046）;新疆财经大学科研基金（2015XYB007）

An efficient completely dynamic SPT algorithm

WANG Xiaojie,GUO Wenqiang,WANG Sixiu,CAI Yongmei

(School of Computer Science and Engineering,Xinjiang University of Finance & Economics,Urumqi 830012，China)

Received:2015-01-10 Revised:2015-05-15 Online:2016-03-25 Published:2016-03-25

摘要/Abstract

摘要：

在通信网络中，节点间最短路径的计算是链路状态路由协议计算路由的基础。通过对现有动态最短路径算法的深入研究，提出了一种处理网络拓扑变化的完全动态最短路径算法DSPTID。该算法利用已有SPT的信息，建立一个最短路径树的更新队列，当网络拓扑发生变化时，算法针对边的权值增大和减小，分别进行更新，并将更新节点局限在受拓扑变化影响的节点中，从而达到SPT的增量更新。算法复杂度分析和仿真结果显示，DSPTID算法具有更少的节点更新次数和更高的时间效率。

关键词: 最短路径, SPF算法, 动态更新, 路由协议

Abstract:

Computation of the shortest path between two nodes in communication networks is the basis of the link state routing protocol. Based on the study on the present dynamic SPT algorithms, we propose a new completely dynamic SPT algorithm (DSPTID) for handling network topology changing. This algorithm establishes an SPT update queue and pays attention only to the changes of nodes and edges by making use of information provided by the existing SPT, which can achieve incremental update. When the topology of the network changes, the increase or decrease of edge weights can be processed by the DSPTID algorithm. The analysis of algorithm complexity and simulation results show that the DSPTID requires less update of nodes and has higher efficiency.

Key words: shortest path;SPF algorithm;dynamic update;routing protocol

汪晓洁，郭文强，王思秀，蔡咏梅. 一种高效的最短路径完全动态更新算法[J]. J4, 2016, 38(03): 449-453.

WANG Xiaojie,GUO Wenqiang,WANG Sixiu,CAI Yongmei. An efficient completely dynamic SPT algorithm [J]. J4, 2016, 38(03): 449-453.

参考文献［9］

［1］	Moy J.OSPF Version 2:RFC2328［S］.199804．
［2］	Oran D.OSI ISIS Intradomain routing protocol:RFC1142［S］.199002．
［3］	Dijkstra E W.A note on two problems in connection with graphs［J］.Numerical Math,1959,1（1）:269271．
［4］	Bauer R, Wagner D. Batch dynamic singlesource shortestpath algorithms:An experimental study［C］∥Proc of Vahrenhold J,2009:5162．
［5］	Xiao Bin,Qing Zhuge.Minimum dynamic update for shortest path tree construction［C］∥Proc of the GLOBECOM’01,2001:126130．
［6］	Xiao Bin,Cao Jiangnong,Qing Zhuge,et al.Shortest path tree update for multiple link state decrements［C］∥Proc of the IEEE Global Telecommunications Conference，2004:11631167．
［7］	Liu Daibo，Hou Mengshu，Wu Zexu，et al.Efficient dynamic algorithm for computation of shortest path tree［J］.Computer Science，2011，38（7）:9699．(in Chinese)
［8］	Xiao Qiancai，Li Mingqi，Guo Wenqiang.Dynamic shortest path algorithm for multilink increment［J］.Computer Science，2012，39（4）:114117．(in Chinese)
［9］	Zhou Ling，Wang Jianxin.Path nodesdriven leastcost shortest path tree algorithm［J］.Journal of Computer Research and Development，2011，48（5）:721728．(in Chinese)
［10］	Sharma Y，Saini S C,et al.Comparison of Dijkstra shortest path algorithm with genetic algorithm for static and dynamic routing network［J］.International Journal of Electronics and Computer Science Engineering,2012,1（2）:416425．
［11］	Hong Qu,Simon X Yang,Zhang Yi,et al.A novel neural network method for shortest path tree computation［J］.Applied Soft Computing,2012,12（10）:32463259．
［12］	Xiao Bin,Cao Jiangnong,Shao Z,et al.An efficient algorithm for dynamic shortest path tree update in networking routing［J］.Journal of Communication and Networks，2007，9（4）:409510．
	附中文参考文献：
［7］	刘代波，候孟书，武泽旭，等.一种高效的最短路径树动态更新算法［J］.计算机科学,2011，38（7）:9699．
［8］	肖乾才，李明奇，郭文强.多链路权值增大的动态最短路径算法［J］.计算机科学，2012，39（4）:114117．
［9］	周灵，王建新.路径节点驱动的低代价最短路径树算法［J］.计算机研究与发展,2011，48（5）:721728．

[1]	段晨, 彭伟, 王宝生. 数据中心网络路由研究进展[J]. 计算机工程与科学, 2022, 44(04): 631-644.
[2]	周静, 关玉蓉. 基于SDN的DWSN技术分析及性能优化研究[J]. 计算机工程与科学, 2021, 43(08): 1413-1421.
[3]	王彩芬1,2，苏舜昌1，杨小东1. 可动态更新的口令授权多秘密共享方案[J]. 计算机工程与科学, 2019, 41(09): 1597-1602.
[4]	尚振浩，程华，房一泉. 基于最简子图的链接表示及预测[J]. 计算机工程与科学, 2019, 41(02): 253-259.
[5]	程佳乐，李伟东. 具有树和路约束的平行机排序问题[J]. 计算机工程与科学, 2018, 40(12): 2273-2279.
[6]	贾俊杰，闫国蕾，邢里程，陈菲. (p,k)匿名数据集的增量更新算法[J]. 计算机工程与科学, 2018, 40(07): 1206-1212.
[7]	张峰，王小明. 机会网络中基于能量消耗的缓存管理策略[J]. J4, 2016, 38(05): 891-897.
[8]	杨晓花1,2，武继刚1,2，史雯隽1,2，赵国栋1,2. 稳定的最短路径树及其构造算法[J]. J4, 2016, 38(03): 418-424.
[9]	罗旭，吴晓军. 蚁群优化算法在WSN路由中的应用研究[J]. J4, 2015, 37(04): 740-746.
[10]	陈雪寒，陈志刚，曾锋，吴嘉. WSN中一种基于时空相关性的网内数据聚合路由协议[J]. J4, 2015, 37(01): 48-55.
[11]	程友清，余少华. IPv6网络中一种基于路由协议的PMTU发现机制[J]. J4, 2013, 35(2): 43-48.
[12]	鞠兴隆1，段友祥1，马成1，修南海1，鞠海燕2. 一种Web服务使用者体验时间的动态更新方法[J]. J4, 2013, 35(12): 120-125.
[13]	魏文红1，李清霞2，蔡昭权3. 一种基于桶结构的单源最短路径算法[J]. J4, 2012, 34(4): 77-81.
[14]	王璨，骆坚，张大方，黎文伟. 一种基于移动性的无线传感器网络分簇路由协议[J]. J4, 2012, 34(3): 6-12.
[15]	刘樑骄1，李仁发1，李哲涛1,2，乐光学1,3. 一种高效的多媒体无线传感器网络地理路由算法[J]. J4, 2010, 32(12): 1-4.