Abstract: This paper studies the bandwidth, delay, delay jitter, and packet loss constrained least-cost multicast routing problem which is known tobe NP-complete, and presents a heuristic genetic algorithmic to solve the problem. Variable-length chromosomes (routing strings) and their genes(nodes) have been used for encoding the problem. The crossover operation that exchanges partial chromosomes (partial-routes) at positionalindependent crossing sites and the mutation operation maintain the genetic diversity of the population. The proposed algorithm can cure all theinfeasible chromosomes with a simple repair operation. Crossover and mutation together provide a search capability that results in improved qualityof solution and enhanced rate of convergence. Computer simulations have verified that this algorithm is efficient and effective.

摘要： 研究了带宽、延时、延时抖动和分组丢失率约束以及费用最小的QoS多播路由优化问题,提出了一种启发式遗传算法。该算法采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题。交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性。该算法采用简单维护操作维护好所有的不可行的染色体。交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性。计算机仿真实验证明该算法快速有效,可靠性高。

关键词: 多播路由, QoS, 路由优化, 遗传算法

CLC Number: 

• TN915.04