基于遗传算法的带宽-时延约束多播路由优化算法  

A Multicast Routing Optimization Algorithm with Bandwidth and Delay-Constrained Based on Genetic Algorithm

作　　者：孙宝林[1] 李腊元[1] 

机构地区：[1]武汉理工大学计算机学院

出　　处：《计算机工程与应用》2004年第11期30-33,共4页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(批准号:60172035;90304018);湖北省自然科学基金资助项目(编号:2000J154);湖北省教育厅重点科研项目(编号:2003A002);武汉科技学院基金资助项目(编号:20032418)

摘　　要：随着许多多媒体在高速网络中的应用,多播路由问题成为越来越重要的课题。多播路由问题在计算机网络中是著名的Steiner树问题,同时也是NP完全问题。该文提出了一种基于遗传算法的多播路由优化算法,采用可变长度染色体(多播树)和基因(路径)应用于编码问题。该算法在满足带宽和时延约束条件下寻找代价最小的多播树。仿真实验证明该算法能快速找到最优解,收敛速度快,可靠性高,能够满足多媒体网络对实时性的要求。Due to the advent of many new multimedi a applications in high speed networks,the issue of multicast routing has become more and more important.The multicast routing problem in computer networks is a lso known as the Steiner tree problem which has been shown to be NP-complete.T his paper proposes a new multicast routing optimization algorithm based on Genet ic Algorithms ,variable-length chromosomes(multicast tree)and their genes(r outing strings)have been used for encoding the problem.It can find the low-co st multicasting tree with bandwidth and delay constraints.The simulation result s show that the proposed algorithm is able to find a better solution,fast conve rgence speed and high reliability.It can meet the real-time requirement in multimedia communication networks.The scalability and the performance of the al gorithm with increasing number of network nodes are also quite encouraging.

关 键 词：多播路由 QOS 路由优化 遗传算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]