一种基于A<sup>*</sup>算法的多径寻由算法

doi:10.3724/SP.J.1146.2012.00983

摘要
图/表
参考文献
相关文章 (2)

全文: PDF (244 KB)
输出: BibTeX | EndNote (RIS)

摘要随着网络通信量的急剧增长，多径传输应用日渐普遍。多径寻由算法是实现多径传输的基础。该文结合路径相似度目标和启发式方法，提出一种新的基于A*算法的多径寻由算法，称为MA^*算法。该文为该算法设计了一种新的代价估计函数，通过理论分析证明了该代价估计函数的可行性。利用网络拓扑生成工具对MA*算法进行了仿真实验，并与其他多径寻由算法进行了分析比较。实验结果表明，MA*算法能以较低的搜索次数获取多条路径代价和路径相似度合理的路径；另外通过合理调整惩罚参数，可以取得路径代价和路径相似度的平衡。MA*算法以更小的开销实现了一种更为通用的多径寻由算法，能够应用在更广泛的多径传输环境。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	赵奇
	赵阿群

关键词 ：网络通信, 多径寻由, 路径相似度, A^*算法, 代价估计函数

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 achieved through reasonable adjustment of the punishing parameter. The MA^* algorithm can be applied to wider multi-path transmission environments as a more common multi-path routing algorithm.

Key words： Network communication Multi-path routing Path similarity A^* algorithm Evaluation function

收稿日期: 2012-07-27

PACS:

TP393

基金资助:

国家自然科学基金(61071077)和中央高校基本科研业务费专项资金(2012JBM025)资助课题

通讯作者: 赵阿群 E-mail: aqzhao@bjtu.edu.cn

引用本文:

赵奇, 赵阿群. 一种基于A^*算法的多径寻由算法[J]. 电子与信息学报, 2013, 35(4): 952-957. Zhao Qi, Zhao A-Qun. A Multi-path Routing Algorithm Base on A^*Algorithm. , 2013, 35(4): 952-957.

链接本文:

http://jeit.ie.ac.cn/CN/10.3724/SP.J.1146.2012.00983 或 http://jeit.ie.ac.cn/CN/Y2013/V35/I4/952