摘 要： 给出了QoS路由选择问题的描述，提出了单点投递情况下，利用改进遗传算法解决受多个QoS约束的路由选择策略，并对该算法的性能进行了仿真分析。
关键词： 服务质量（QoS） QoS路由 遗传算法（GA） 单点投递
目前，Internet(Ipv4标准)基本上只能提供“尽力而为”的服务。而随着Internet商业化应用的飞速发展，对网络的服务质量（Quality of Service，QoS）提出了更高的要求。研究QoS路由问题就是对网络和业务QoS路由进行优化，在尽量减少资源消耗的基础上，合理分配网络的流量负荷，减少阻塞概率，同时有利于系统接入更多的业务。如果路由尺度是2个或多个加法性或乘法性QoS参数的任意组合，则这类路由问题属于NP完全问题[1]，用传统的穷举算法不能满意地解决问题，尤其是当网络规模很大时。
遗传算法（Genetic Algorithm，GA）是模拟生物群体进化过程，通过“优胜劣汰”法则保留优秀后代的一种新型优化算法。作为一种自适应、启发式的全局意义上的搜索算法，遗传算法具有很强的鲁棒性，并具有并行搜索，群体寻优的特点，已广泛用于解决具有NP难度的问题。运用遗传算法解决路由选择问题已有很多研究，如解决基于负载均衡的路由问题[3]、QoS路由问题[4]和时延费用最小问题[5]等。可以看出，同其他优化算法相比，利用遗传算法解决此类问题显得更为简单、有效。但采用一般的遗传算法解决QoS路由问题，容易收敛于局部解且在进行遗传算子（如交叉和变异）操作时染色体中会产生死遗传子，形成根本不存在的链路或造成循环链路，并且遗传算法本身还存在收敛速度和全局收敛性之间的矛盾。针对这些问题，本文对传统遗传算法进行了一些改进，并利用该算法解决多约束的QoS路由问题，取得了较好的效果。
1 多约束QoS路由问题模型
网络中的业务连接请求可表示为X=(x1，x2，……xn)，x1、x2、……xn分别对应带宽、时延、链路长度、跳数、丢包率、时延抖动等QoS要求。在单点投递的情况下，多约束QoS 路由选择问题就是在P中找出一条或多条代价最小、同时满足多个QoS 要求的路径P。
2 运用改进遗传算法优化多QoS路由
2.1 改进遗传算法
(1)在编码方式上，本文用一种树状结构来表示网络拓扑，并对树的重复部分进行了归并处理。这种搜索树包括了网络中所有节点且不会产生循环。基于这种网络搜索树采用固定长度进行编码，既降低了算法的复杂度，又可以使变异和交叉操作变得很容易。
(2)在交叉概率的选择上，保持一个固定的、相对较低的交叉概率，既可以极大地提高计算效率，又可以降低优良个体模式缺失的概率。
(3)在变异概率的选择上，采用自适应变异概率。在遗传算法中，变异算子pm的选择非常重要。pm过大，遗传算法的搜索过程就变成了随机过程；而pm过小，其产生新个体和抑制早熟现象的能力就会较差。此外，随着群体进化而趋于收敛时，pm不应一成不变，而应随着进化过程而逐步减小，从而使得遗传算法稳步收敛。本文自适应变异概率定义为：
式中，fmax(t)是t代种群中的最优个体适应度值； fmean(t)是第t代种群中的平均个体适应度值。
2.2 算法执行过程
(1)精简网络拓扑。删去不满足带宽约束的链路以简化网络，既可以简化算法设计的难度，又优化了算法的性能。
(2)构造搜索树。网络拓扑图如图1所示，图中的8个节点A为源节点，H为目的节点。构造网络搜索树的方法是：将源点A作为父节点，与其邻接的节点B、C、E作为A的子节点构造树；再分别以各子节点为父节点，与其邻接的节点作为子节点构造树，直到无邻接节点为止，最终生成一棵以A为顶点的搜索树。其原始搜索树如图2所示。对图2所示树中的重复枝节点进行归并整理形成新的搜索树。归并后的搜索树模型如图3所示。
(3)编码。对图3所示搜索树进行编号，分枝节点作为遗传子，表示网络路径节点，将遗传子并列构成染色体，表示网络的路径，得到搜索树编号列表如表1所示。遗传子是指各编号列中的队列值(如2编号列中的H、D、B、C)，染色体(个体)是各编号列中所取节点的组合。遗传子按如下规则进行编码：定义染色体的长度为9，如果染色体中含有某一节点，则将其编为1，否则为0。例如，对于路径A-B-D-E-C-F-G-H，排列中的节点分别出现在（0，1，4，7，8）处，其对应的编码为（1，1，0，0，1，0，0，1，1）。这样得到的染色体和网络中的路径一一对应。
(4)生成初始群体。初始群体中个体的产生采用随机深度优先搜索方法，搜索从源节点s开始，随机选择与之相连的下一节点，反复进行直至搜索到目的节点d为止。
(5)适应度函数。适应度函数是遗传算法中用来判断个体性能好坏的标准。本算法定义的适应度函数为：
其中，xi，j(i=1，2，……n；j=0，1，2，……m)用于表示带宽、时延、丢包率、时延抖动和成本等，w表示业务需求带宽。上式中用业务需求带宽与瓶颈带宽的比表示网络负载分布均衡程度，时延与成功率的比表示发包效率，成本与时延抖动的比表示时延抖动开销。可以看出，满足QoS约束且负载平衡的个体适应度小，不满足QoS约束的个体适应度大。
(6)选择操作。本算法的选择操作采用最佳个体保存法和赌轮选择法相结合的方法，即在群体交叉之前，先选出最佳个体（适应度小）直接复制到下一代群体，其余个体的选择采用赌轮选择法。
(7)交叉操作。通过赌轮选择法随机选择2个要交叉的父代个体，在2个体中搜索有相同编号的遗传子编码。如果该位置上遗传子编码均为1，则进行交叉，即互相交换遗传子，否则不进行交叉；如果符合条件的位置多于1个，则按从右往左顺序选择1个位置进行交叉。这样就能有效地扼制不存在的链路和循环链路的产生，保证新产生的个体是网络中的一条链路。
(8)变异操作。依据变异率，变异可在个体中遗传子编码为1的任意位置进行。如果在其位置上选择其他遗传子(如表1中，编号1的列中含有D、E，它们为逆遗传子)则生成新的个体。此时所生成的个体必定是网络中的一条链路。
2.3 算法描述
设定群体大小为Np，运行代数为Ng，则该算法可描述为：(1)删去网络拓扑中不满足带宽要求的链路。(2)构造搜索树并进行归并处理。(3)编码并随机生成初始群体。(4)计算适应度函数，将综合评价值最小的染色体复制到解集中。(5)进行遗传子操作，按照选择操作、交叉操作和变异操作方法，根据设定的交叉算子和式（1）求出的变异算子产生下一代种群。(6)如果运行代数超过了设定值，则转到步骤7，否则执行步骤4。(7)在解集中找出综合评价值最小的染色体作为解输出，若多个染色体的综合评价值相等，则选择w/xi，0值最小的染色体。算法结束。
3 算法性能分析
网络拓扑模型如图4所示。应用本算法对其进行仿真实验。假设源节点为A，目的节点为H，链路特性用五元组(x1，x2，x3，x4，x5)描述，分别表示带宽、时延、成功率(=1－丢包率)、成本和时延抖动。QoS路由要求为：所需带宽b＝2bps，最大时延d＝8μs，时延抖动j≤10μs，成功率≥80%，成本≤10，综合评价值≤1。编码长度为9位，群体大小为100，交叉概率为0.5，采用自适应变异概率，由式（1）得出，初始群体随机产生。
仿真结果如表2所示。由表2可以看出，第2、3个解的综合评价值最小，符合QoS要求且达到负载分布均衡，但第3个解的w/xi，0值最小，所以第3个解（路径A－C－E－H）为最优解。
4 结 论
本文在单点投递的情况下，利用改进的遗传算法求解具有多个QoS约束的路由选择问题。该算法主要有以下特点：（1）采用预处理机制，有效地减少了算法编码空间和搜索空间，提高了算法的搜索效率。（2）特殊的树结构编码，使染色体长度达到固定，简化了编码操作，省略了复杂的编码和解码过程。（3）通过对交叉操作和变异操作的改进，使算法迅速跳出局部最优解，使算法向全局最优的方向发展，同时加快了算法收敛的速度。（4）采用的综合评价指标，能满足多个QoS要求且负载分布均衡。
参考文献
1 Wang Z，Crow C J.Quality-of-service for Routing Supporting Multimedia Applications.IEEE Journal of Selected Areas in Communications，1996；14(7)
2 欧阳森，宋政湘，王建华等.一种快速收敛的遗传算法.计算机应用研究，2003；20(9)
3 栋朝雅晴，高井昌彰，佐藤羲治.一种适应负载分布均衡的 路由遗传算法.信息处理学会论文志，1998；39(2)
4 Xian G F，Zhou J，Jie Y W.QoS Routing Based on Genetic Algorithm.Computer Communications，1999；22(15)
5 Ravikumar C P，Bajpai R.Source-based Delay-bounded Multi-casting in Multimedia Networks.Computer Communications，1998；21(2)
6 何小燕，费翔，罗军舟等.Internet中一种基于遗传算法的QoS路由选择策略.计算机学报，2000；23(11)