摘要
研究了带宽延时受限、费用最小的QoS组播路由问题 ,并提出了一种解决该问题的免疫算法 .免疫算法的核心在于免疫算子的构造 ,而它又是通过接种疫苗和免疫选择两个步骤来完成的 .根据QoS组播路由问题 ,给出了免疫疫苗选取与免疫算子构造的具体方法 .将免疫算法应用于组播路由选择 ,是通过在基于遗传算法的组播路由选择的基础上引入免疫算子来实现的 .该算法采用的进化算子简便、高效 .仿真实验表明 ,该算法不仅有效可行 ,而且较好地解决了标准遗传算法中出现的退化现象 。
Abstract The bandwidth-delay-constrained least-cost multicast routing problem is known to be NP-complete, and the immune algorithm to solve the problem is proposed. The problem can be formulated as finding a minimum cost Steiner Tree, which satisfies the constraints above mentioned. Firstly, the links with a bandwidth less than the bandwidth requirement are removed, thus the remained links in the refined graph must satisfy the bandwidth constraint. Then the immune algorithm is adopted to solve the minimal multicast tree with delay constraint. The core of the immune algorithm lies on constructing the immune operator that is realized by vaccination and immune selection. The strategies and the methods of selecting and constructing a vaccine for the problem. Immune algorithm for multicast routing introduces the in mime operators to genetic algorithms for multicast routing. This algorithm properly deals with the degeneration in conventional genetic algorithms, therefore increases the convergence speed. This algorithm can meet the real-time requirement in multimedia communication networks. Especially in large-scale networks, it reduces the computational time greatly. Computer simulations have shown that its convergence and search speed is faster and its efficiency is higher than other algorithms.
出处
《计算机学报》
EI
CSCD
北大核心
2003年第6期676-681,共6页
Chinese Journal of Computers
基金
国家自然科学基金 ( 60 0 730 5 3
60 1330 10 )资助
