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

随着许多多媒体在高速网络中的应用,多播路由问题成为越来越重要的课题。多播路由问题在计算机网络中是著名的Steiner树问题,同时也是NP完全问题。该文提出了一种基于遗传算法的多播路由优化算法,采用可变长度染色体(多播树)和基因(路径)应用于编码问题。该算法在满足带宽和时延约束条件下寻找代价最小的多播树。仿真实验证明该算法能快速找到最优解,收敛速度快,可靠性高,能够满足多媒体网络对实时性的要求。

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

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.