并行量子遗传算法在QoS组播路由中的应用  

Application of a Parallel Quantum Genetic Algorithm in Multicast Routing Optimization with QoS Constraints

作　　者：周志芳[1] 孙力娟[1] 郭剑[1] 饶林果[1] 

机构地区：[1]南京邮电大学计算机学院,江苏南京210003

出　　处：《计算机技术与发展》2008年第8期185-187,191,共4页Computer Technology and Development

基　　金：江苏省高技术研究计划(BG2005038);江苏省高校自然科学研究计划(04KJB520095);南京邮电大学青蓝计划资助项目(NY207084)

摘　　要：随着网络通信技术的发展和Internet的普及,性能出色的组播路由越来越重要。著名的组播路由Steiner树问题是NP完全问题,应采用启发式方法求解。文中在常规量子遗传算法中引入并行进化模型,提出了一种解决多约束QoS组播路由优化问题的算法。在满足带宽、时延约束条件下寻找代价最小的组播树,并合理安排节点负荷,减少通信开销。仿真实验结果表明本算法搜索速度快、全局寻优能力强,性能和效率优于常规量子遗传算法。Along with the developing of telecommunication technology and prevailing of the Intemet, multicast routing with excellent performance becomes more and more important nowadays. The notable multicast routing problem named Steiner tree problem is an NP- complete problem and should be solved by heuristic methods. In this paper, a parallel evolution model is introduced into general quantum genetic algorithm, and a new algorithm is proposed to solve multicast routing optimization problem with multiple QoS constraints. This new algorithm can search out minimum cost multicast tree satisfying bandwidth, delay-constraints while correctly arranging nodes＇ loads and decreasing communication spending. The simulation results show that this new algorithm has fast search speed and finer global search capacity. Its performance and efficiency is better than general quantum genetic algorithm.

关 键 词：组播路由优化 QOS 量子遗传算法 并行进化模型 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]