计算机工程

• 移动互联与通信技术 • 上一篇    下一篇

动态网络中一种高效的最短路径树维护算法

韦玉科,王守翔   

  1. (广东工业大学 计算机学院,广州 510006)
  • 收稿日期:2015-12-14 出版日期:2017-01-15 发布日期:2017-01-13
  • 作者简介:韦玉科(1965—),女,副教授、博士,主研方向为网络拓扑结构、图像处理、智能信息处理;王守翔,硕士研究生。
  • 基金项目:
    广东省科技计划项目(2014A040402007)。

An Efficient Maintenance Algorithm for Shortest Path Tree in Dynamic Network

WEI Yuke,WANG Shouxiang   

  1. (School of Computer Science and Technology,Guangdong University of Technology,Guangzhou 510006,China)
  • Received:2015-12-14 Online:2017-01-15 Published:2017-01-13

摘要: 现有的动态最短路径树算法在某些边的权值频繁变化时,会造成动态网络中的最短路径树频繁更新,而且当网络中的路由器毁坏或增加新的路由器时,该算法难于应用到构造最短路径树中。针对上述问题,提出一种最短路径树的维护算法。对权值频繁变化的边进行处理,避免将其加入到最短路径树中,减少最短路径树的更新次数,当网络中的路由器毁坏或者增加时,通过减少冗余边的入队操作,对网络中的最短路径树进行维护。实验结果表明,与高效的最短路径树动态更新算法相比,该算法的更新时间效率更高。

关键词: 动态网络, 最短路径树, 路由器, 动态最短路径树算法, 维护算法

Abstract: The reported Dynamic Shortest Path Tree(DSPT) algorithm can result in frequent update of the Shortest Path Tree(SPT) in dynamic network when the weight of some edges frequently change.And when a router is destroyed or a new router is added into the network,the algorithm is not applicable for constructing the SPT.Aiming at the above problems,an effective maintenance algorithm for SPT is proposed,which can greatly reduce the update of the SPT through dealing with the frequently changed weight of some edges by excluding the unstable edges from the SPT.At the same time,when a router is destroyed or added into the network,the SPT can be effectively maintained in the network through reducing the redundant edge enqueue operation.Experimental results show that compared with efficient dynamic algorithm for computation of SPT,the algorithm’s update time is more efficient.

Key words: dynamic network, Shortest Path Tree(SPT), router, Dynamic Shortest Path Tree(DSPT) algorithm, maintenance algorithm

中图分类号: