基于遗传算法的多约束QoS组播路由优化算法  

An Optimization Algorithm for Multiple Constrained QoS Multicast Routing Based on Genetic Algorithms

作　　者：李美莲[1] 曾建潮[2] 

机构地区：[1]中北大学计算机科学与技术系,太原030051 [2]太原科技大学系统仿真与计算机应用研究所,太原030024

出　　处：《计算机工程与应用》2005年第23期125-128,168,共5页Computer Engineering and Applications

摘　　要：在计算机网络中,随着大量新兴多媒体实时业务的应用,组播路由问题成为越来越重要的课题。组播路由问题在计算机网络中是著名的Steiner树问题,同时也是NP完全问题。目前许多研究者在单约束(特别是延时约束)组播路由中取得了较好的成果,但对于多约束Qos组播路由方面的研究相对比较少。论文提出了一种基于遗传算法的多约束组播路由优化算法,该算法在满足带宽、延时、延时抖动和包丢失率约束条件下寻找代价最小的组播树,文中描述了一种适应于研究Qos组播路由的网络模型。最后通过仿真实验证明该算法操作简单、搜索速度快、效率高且具有较强的实用性和鲁棒性。As the demands for quality of service（Qos） by multi-service in computer networks are rapidly increasing,the issue of multicast routing has become more and more important.The muhicast routing problem in computer networks is also known as the famous Steiner tree problem which has been shown to be NP-complete.Presently many researchers had studied the single constrained muhicast problem,especially the delay constrained muhicast problem,but the multiple constrained multicast problem has been such less studied.This paper proposes a novel multiple-constraint multicast routing optimization algorithm based on Genetic Algorithms,which can find the least-cost multicasting tree with the bandwidth,delay,delay jitter and packet loss-constrained,and describes a network model for researching the routing problem.Finally simulations verify that this algorithm has simple operation,fast convergence speed，high reliability,stronger practicality and robustness。

关 键 词：组播路由 QOS 路由优化 遗传算法 STEINER树 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]