基于免疫遗传算法的多约束QoS组播路由选择方法  

Approach for multiple constrained QoS multicast routing based on immune genetic algorithm

作　　者：赵秀平[1] 谭冠政[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机应用》2008年第3期591-595,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(50275150);高等学校博士学科点专项科研基金资助项目(20040533035)

摘　　要：以具有精英保留的免疫遗传算法(IGAE)为基础,提出了一种新的用来求解带宽、时延、时延抖动受限,费用最小的QoS组播路由选择问题的方法。首先采用预处理机制,将网络结构中不满足带宽约束的链路去掉,利用Dijkstra第k最短路径算法建立编码空间的备选路径集;然后采用基于路径的树结构编码来随机产生初始群体,使种群中的每个个体都代表组播路由问题的一个候选解;最后利用IGAE算法对种群进行优化,最终求得满足QoS要求的组播路由。仿真实验结果表明,该算法具有较好的性能,能以较快的速度搜索到满足QoS要求的费用最小的组播树。Based on the Immune Genetic Algorithm with Elitism （IGAE）, a new routing selection approach to solve QoS multicast routing problem with minimum cost and constrains of bandwidth, delay and delay jitter was proposed. Firstly, it used the preprocessing mechanism to get rid of the links that did not satisfy bandwidth constraint in network structure. And the k shortest paths＇ Dijkstra algorithm was utilized to establish the alternative path set of the algorithm coding space. Secondly, it generated the initial population of IGAE, using the tree structure coding based on the path. Thereby, each individual of the population represented a candidate solution to the multicast routing problem. Finally, IGAE algorithm was used to optimize the population. It ultimately obtained the muhicast routing meeting QoS requirements. The simulation results show that this proposed algorithm is highly efficient and it can find a multicast tree at the lowest cost and at fast convergence speed.

关 键 词：服务质量 组播路由 组括树 免疫遗传算法 精英保留策略 

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