一种基于模拟退火方法的多约束QoS组播路由算法  

A Multi-Constrained QoS Multicast Routing Algorithm Based on Simulated Annealing

作　　者：张琨[1] 王珩[1] 刘凤玉[1] 

机构地区：[1]南京理工大学计算机科学与技术系,南京210094

出　　处：《计算机科学》2005年第5期41-45,共5页Computer Science

基　　金：国家自然科学基金(编号:60273035);国家高技术研究发展计划(编号:2001AA113161);国防科工委应用基础基金(编号:J1300D004)

摘　　要：研究了带宽、时延及时延抖动约束最小代价的QoS组播路由问题,提出一种利用模拟退火方法解决该问题的QoS组播路由算法SABDMA。该算法通过选择合适的模拟退火参数迭代求解,以获得满足QoS约束的最小代价组播树。同时,为避免搜索区域的扩大和计算时间的增加,根据时延和时延抖动的关系,提出采用“路径交换”策略在可行解范围内构造邻域集。仿真结果表明该算法具有可行、稳定、收敛快的特点;能根据组播应用对QoS的限制要求,有效地构造代价较低的组播树,具有较强的实时性。This paper studies bandwidth-delay and delay variation constrained least-cost QoS multicast routing prob- lem, and proposes a QoS multicast routing algorithm (SABDMA) based on simulated annealing to solve this prob- lem. The algorithm selects proper parameters about simulated annealing, and finds least-cost multicast tree satisfying QoS constraints. In addition, to avoid enlargement of search area and increase of computing time, we put forward a 'paths-switching' strategy. It constructs neighbor set in the range of feasible solutions according to the relationship between delay and delay variation. A large number of simulations demonstrates that the algorithm has characteristics of feasibility, stability and rapid convergence, and it can effectively construct multicast tree with lower cost according to QoS request, and has better real-time property.

关 键 词：组播路由算法 模拟退火方法 多约束 时延抖动约束 最小代价 QOS组播 QOS约束 路由问题 迭代求解 计算时间 搜索区域 仿真结果 组播树 可行解 实时性 构造 带宽 交换 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]