用改进的遗传算法解决多约束QoS单播路由问题

在Internet网络中由于多媒体通信的需要,QoS路由技术已经成为研究的热点。本文通过对多约束QoS单播路由问题的研究,在已有遗传算法解决方案的基础上,提出一种改进的遗传算法。改进后的遗传算法综合考虑QoS单播路由中延时、延时抖动、带宽、丢失率等因素,并根据网络连接特性和带宽限制,在种群的初始化、染色体的交叉和变异等操作中,对个体中基因的选择进行指导,并加入去除循环、削减路由开销等操作,使得多条件约束下的路由选择效率更高。最后给出实验举例,并通过与现有算法性能比较,表明改进的遗传算法能快速、有效地解决多约束QoS单播路由选择问题,并适用于大规模的网络系统。

An Improved Genetic Algorithm to Solve Multi-constrained QoS-based Unicast Routing Problem

On the Internet,QoS-based routing has become the hot technique in order to fulfill the requirements of multimedia communication.In this paper,some research on the multi-constrained QoS-based uincast routing has been done and an improved genetic algorithm has been brought forward to solve this NP-complete problem.Considering the factors like delay,delay jitter,bandwidth and packet loss ratio in the network,genes in each chromosome have been supervised in the process of initialization,crossover and mutation.In addition,some other special skills have been used to help delete loops in route or reduce the cost of route.Therefore,the proposed algorithm can conver very quickly and find the optimal routing of a faster speed.In the end,some experimental results have been presented which prove the efficiency of the algorithm.This improved genetic algorithm can also be used in the large-scale network.