基于Tabu搜索的QoS多播路由快速优化算法-软件学报.PDF

1000-9825/2004/15(12)1877 ©2004 Journal of Software 软 件 学 报 Vol.15, No.12 ∗ 基于 Tabu 搜索的 QoS 多播路由快速优化算法 + 高 茜 , 罗军舟 (东南大学 计算机科学与工程系 网络室,江苏 南京 210096) A Tabu-Search-Based Fast QoS Multicast Routing Optimal Algorithm + GAO Qian , LUO Jun-Zhou (Network Laboratory, Department of Computer Science and Engineering, Southeast University, Nanjing 210096, China) + Corresponding author: Phn: +86-25 Fax: +86-25 E-mail:gq@, Received 2004-02-13; Accepted 2004-07-15 Gao Q, Luo JZ. A tabu-search-based fast QoS multicast routing optimal algorithm. Journal of Software, 2004,15(12):1877~1884. /1000-9825/15/1877.htm Abstract: The key problem of QoS multicast routing optimization algorithm is to build QoS constrained multicast tree. This is the most noted problem in computer networks as constrained minimum Steiner tree problem, which has also been shown as NP-complete. A fast multicast routing optimal algorithm with QoS constraints based on Tabu-search is proposed in this paper. It chooses delay and bandwidth as QoS parameters, can improve the search speed, and make a better solution by using the merits of Tabu-search. Simulation results with random network models show that TSQMA is faster, easier for implementation, and more suitable for large group scale. Key words: multicast routing; QoS; Tabu search 摘 要: QoS 多播路由算法的核心问题是建立满足 QoS 约束的多播树,这就是计算机网络中著名的受约束最小 Steiner 树问题,是一个NP 完全问题. 目前已有的启发式算法的时间复杂度大,不能获得最优解.提出了一个基于Tabu 搜索的QoS 多播路由选择快速优化算法,它选择延迟与带宽约束为QoS 参数,利用Tabu 搜索的集中性与广泛性并 存的优点,在提高搜索速度的同时可以更加接近最优解.仿真结果表明:该算法具有快速、易实施等特点,更加适合在 组规模比较大的情况下应用. 关键词: 多播路由;QoS;Tabu 搜索 中图法分类号: TP393 文献标识码: A ∗ Supported by the National Natural Science Foundation of China