一种基于A算法的多径寻由算法.pdfVIP

第35 卷第4 期 电 子 与 信 息 学 报 Vol.35No.4 2013 年4 月 Journal of Electronics Information Technology Apr. 2013 一种基于A*算法的多径寻由算法 赵 奇 赵阿群* (北京交通大学计算机与信息技术学院 北京 100044) 摘 要：随着网络通信量的急剧增长，多径传输应用日渐普遍。多径寻由算法是实现多径传输的基础。该文结合路 径相似度目标和启发式方法，提出一种新的基于A*算法的多径寻由算法，称为MA*算法。该文为该算法设计了一 种新的代价估计函数，通过理论分析证明了该代价估计函数的可行性。利用网络拓扑生成工具对 MA*算法进行了 仿真实验，并与其他多径寻由算法进行了分析比较。实验结果表明，MA*算法能以较低的有哪些信誉好的足球投注网站次数获取多条路径 代价和路径相似度合理的路径；另外通过合理调整惩罚参数，可以取得路径代价和路径相似度的平衡。MA*算法 以更小的开销实现了一种更为通用的多径寻由算法，能够应用在更广泛的多径传输环境。 关键词：网络通信；多径寻由；路径相似度；A*算法；代价估计函数 中图分类号：TP393 文献标识码： A 文章编号：1009-5896(2013)04-0952-06 DOI: 10.3724/SP.J.1146.2012.00983 A Multi-path Routing Algorithm Base on A* Algorithm Zhao Qi Zhao A-qun (School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China) Abstract: With the rapid growth of network traffic, applications of the multi-path transmission are becoming more popular. The multi-path routing algorithms are the base to implement multi-path transmission. In this paper, a new Multi-path routing algorithm based on the A* algorithm called MA* algorithm is proposed which combining the path similarity objective with the heuristic method. A new evaluation function construction method is devised for the MA* algorithm, which is proved to be feasible through theoretical analysis. The simulation experiments are carried out to compare the MA* algorithm with other multi-path routing algorithms applying network topology generation tool. The results show that the MA* algorithm can acquire multiple paths with reasonable path cost and path similarity at quite low search times. In addition, the balance of path cost and path similarity can be