基于遗传操作的延迟和度约束的多播路由启发式算法

基于遗传操作的延迟和度约束的多播路由启发式算法 Degree-Delay-Bounded Heuristic Algorithm Based on Genetic Operations for Multicast Routing 陈琳 1 first-author 杨志云 1 徐正全 1 武汉大学测绘遥感信息工程国家重点实验室,湖北,武汉,430079 武汉大学测绘遥感信息工程国家重点实验室,湖北,武汉,430079 基于启发式思想的简单性和路径相似性原理,采用遗传算法的交叉和变异操作,提出了一种快速的满足延迟和度约束的最小费用多播路由树的生成算法（DDCMRA）,以解决直接修改延迟约束或者度约束多播路由算法时寻优时间长、并且可能导致部分目的节点因不能满足延迟或者度约束而不能加入多播的问题.仿真结果显示,该算法获得的多播路由树满足延迟和度约束,费用较少,运行时间接近CSPT和RA算法.该算法也为动态多播路由树生成和网络负载平衡提供了一种方法. Delay constraint is a significant constrained factor in constructing multicast routing tree and degree constraint takes multicasting ability of switch or router into account and can keep networks load balancing, so there is realistic meaning in investigating delay-degree-constrained multicast routing algorithms for next generation communication networks. This paper proposes an effective and efficient delay-degree-constrained multicast routing algorithm （DDCMRA） using the simplicity of heuristic algorithm, similarity principle of paths and crossover/mutation operations （but not genetic algorithm）. Simulation result shows the proposed algorithms perform with less tree cost and time of finding near-optimal tree, the performance of this algorithms is better than that of the other similar algorithms. This proposed approaches also provide a method for dynamic multicast routing and keep load balancing. 多播路由 度约束 延迟约束 遗传操作 multicast routing degree constraint delay constraint genetic operation TP393 武汉市科技攻关项目资助（20031003021） 2004-03-01 2021-04-01 3