稳定的最短路径树及其构造算法

J4 ›› 2016, Vol. 38 ›› Issue (03): 418-424.

稳定的最短路径树及其构造算法

杨晓花1,2，武继刚1,2，史雯隽1,2，赵国栋1,2

（1.天津工业大学计算机科学与软件学院，天津 300387;
2.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京 100190）

收稿日期:2015-03-17 修回日期:2015-05-21 出版日期:2016-03-25 发布日期:2016-03-25
基金资助:
国家自然科学基金(61173032);计算机体系结构国家重点实验室开放课题(CARCH201303）

A construction algorithm of the stable shortest path tree

YANG Xiaohua1,2,WU Jigang1,2,SHI Wenjun1,2,ZHAO Guodong1,2

（1.School of Computer Science and Software，Tianjin Polytechnic University，Tianjin 300387;
2.State Key Laboratory of Computer Architecture，
Institute of Computing Technology，Chinese Academy of Sciences,Beijing 100190,China）

Received:2015-03-17 Revised:2015-05-21 Online:2016-03-25 Published:2016-03-25

摘要/Abstract

摘要：

构建最短路径树是动态网络研究的重要问题之一。在动态网络中，当边状态发生变化时会引发最短路径树动态的重新构建，反复地计算不仅消耗大量时间，也会导致最短路径树的频繁变化。提出一种稳定的最短路径树构造算法，使得构造的路径树在动态网络上更稳定，即更新最短路径树所需的操作数更少。该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中，从而能够高效地减少边变化带来的操作。实验结果表明，与传统的动态最短路径树算法相比，该算法可以得到更稳定的最短路径树，并且更新时间减少了5724%，结点更新次数降低了436%。

关键词: 最短路径树；动态网络；重新构建；稳定的

Abstract:

Constructing the shortest path tree is an important problem in dynamic networks, in which the changed edges will lead to dynamic reconstruction of the shortest path tree. Repeated calculation not only consumes a lot of time, but also results in frequent changes of the shortest path tree. We propose an algorithm for constructing the stable shortest path tree, which takes fewer update operations on nodes. The algorithm updates the shortest path tree by excluding the unstable edges so as to effectively reduce the number of the update operations. Experimental results show that compared with traditional dynamic network shortest path tree algorithms, the proposed algorithm can generate relatively more stable shortest path tree. The update time is improved by 57-24%, and the number of update operations on nodes is reduced by 43-6%.

Key words: shortest path tree；dynamic network；reconstruct;stable

杨晓花1,2，武继刚1,2，史雯隽1,2，赵国栋1,2. 稳定的最短路径树及其构造算法[J]. J4, 2016, 38(03): 418-424.

YANG Xiaohua1,2,WU Jigang1,2,SHI Wenjun1,2,ZHAO Guodong1,2. A construction algorithm of the stable shortest path tree [J]. J4, 2016, 38(03): 418-424.

参考文献［23］

［1］	Das S K,Tripathi S,Burnwal A P.Fuzzy based energy efficient multicast routing for adhoc network［C］∥IEEE 2015 3rd International Conference on Computer,Communication,Control and Information Technology （C3IT）,2015:15．
［2］	Lee H J,Nam J C,Seo W K,et al.Enhanced PRoPHET routing protocol that considers contact duration in DTNs［C］∥Proc of IEEE 2015 International Conference on Information Networking （ICOIN）,2015:523524．
［3］	Zhao M,Yang Y.Bounded relay hop mobile data gathering in wireless sensor networks［J］.IEEE Transactions on Computers,2012,61（2）:265277．
［4］	Wang P,Hunter T,Bayen A M.Understanding road usage patterns in urban areas［R］.Scientific Reports,2012,2.doi:10.1038/srep1001．
［5］	Barthelemy M,Bordin P,Berestycki H,et al.Selforganization versus topdown planning in the evolution of a city［R］.Scientific Reports,2013,3．doi:10.1038/srep02153.
［6］	Alaskar M,Vodanovich S,Shen K N.Evolvement of information security research on employees behavior:A systematic review and future direction［J］.Environment,2015,1（11）:42414250．
［7］	Estrada E,VargasEstrada E.How peer pressure shapes consensus,leadership,and innovations in social groups［R］.Scientific Reports,2013,3．doi:10.1038/srep02905.
［8］	Wei D J,Liu Q,Zhang H X,et al.Boxcovering algorithm for fractal dimension of weighted networks［R］.Scientific Reports,2013,3．doi:10.1038/srep02153.
［9］	Zhang H,Wang J,Wang Z,et al.Modedependent stochastic synchronization for markovian coupled neural networks with timevarying modedelays［J］.IEEE Transactions on Neural Networks and Learning Systems,2015,26(11):114．
［10］	Chabini I.Discrete dynamic shortest path problems in transportation applications:Complexity and algorithms with optimal run time［J］.Journal of the Transportation Research Board,1998,1645（1）:170175．
［11］	Dijkstra E W.A note on two problems in connexion with graphs［J］.Numerische Mathematik，1959,1（1）:269271．
［12］	Bellman R.On a routing problem［J］.Quarterly Appl Math,1958,16:8790．
［13］	Wang X,Ran C.Dynamic path planning algorithm based on timedependent road network［C］∥Proc of the 2012 3rd Global Congress on Intelligent Systems,2012:222225．
［14］	Qu H,Yi Z,Yang S X.Efficient shortestpathtree computation in network routing based on pulsecoupled neural networks［J］.IEEE Transactions on Cybernetics,2013,43（3）:9951010．
［15］	Yen C C,Yeh M Y,Chen M S.An efficient approach to updating closeness centrality and average path length in dynamic networks［C］∥Proc of 2013 IEEE 13th International Conference on Data Mining （ICDM）,2013:867876．
［16］	Zhu X,Luo W,Zhu T.An improved genetic algorithm for dynamic shortest path problems［C］∥Proc of 2014 IEEE Congress on Evolutionary Computation （CEC），2014:20932100．
［17］	Iyas N,Javaid N,Iqbal Z,et al.AAEERP:Advanced AUVaided energy efficient routing protocol for underwater WSNs［C］∥Advanced Information Networking and Applications (AINA),2015:7783．
［18］	Nawaz W,Khan K U,Lee Y K.Core analysis for efficient shortest path traversal queries in social graphs［C］∥Proc of 2014 IEEE 4th International Conference on Big Data and Cloud Computing （BdCloud）,2014:363370．
［19］	Xiao B,Cao J,Shao Z,et al.An efficient algorithm for dynamic shortest path tree update in network routing［J］.Journal of Communications and Networks,2007,9（4）:499510．
［20］	Bao Xiaoxuan. The application of bus query analysis of shortest path algorithm［J］.Digital Technology &Application,2013(11):105．(in Chinese)
［21］	Zhang Boliang,Zhang Ruichang,Guan Jihong.A survey on shortest path algorithms in road networks［J］.Computer Applications and Software,2014,31（10）:19．(in Chinese)
［22］	Wang Huan,Zhang Yan,Chen Xu.Research and implementation of the open source pgRouting shortest path algorithm based on WebGIS［J］.Geomatics & Spatial Information Technology,2015,38（2）:8184．(in Chinese)
［23］	Niu Zhipeng. An improved shortest path algorithm based on traffic network［D］.Beijing:Peking University,2012:150．(in Chinese)
［24］	Jing N,Huang Y W，Rundensteiner E A.Hierarchical encoded path views for path query processing:An optimal model and its performance evaluation［J］.IEEE Transactions on Knowledge and Data Engineering,1998,10（3）:409432．
	附中文参考文献：
［20］	包小玄.公交查询中的应用最短路径算法分析的探索［J］.数字技术与应用,2013(11):105．
［21］	张波良,张瑞昌,关佶红.道路网上最短路径算法综述［J］.计算机应用与软件,2014,31（10）:19．
［22］	王欢,张雁,陈旭.基于开源pgRouting的WebGIS最短路径算法实现研究［J］.测绘与空间地理信息,2015,38（2）:8184．
［23］	牛志鹏.一种改进的基于交通网络最短路径算法［D］.北京:北京大学,2012:150．