多QoS约束条件下的多目标网络优化

明丽洪，吕光宏，向虹佼

(四川大学计算机学院，四川成都 610065)

网络规模的增大使得网络结构变得复杂，网络的承载业务已从单一数据业务转向语音、视频、图像等多种综合业务，数据流量的指数增长使得网络发生拥塞的概率增大，Internet尽力发送的服务机制已无法满足多媒体应用和各用户对网络传输质量的不同需要。这必然会对网络服务质量(Quality of Service，QoS)、全网资源调节、负载均衡及网络利用率提出更高的要求。遗传算法(Genetic Algorithm，GA)作为一种全局优化搜索算法，由于其具有自学习、并行性等特点，能较快的求解NP完全问题，最终得到较好的近似最优解而在网络规划和优化中得到广泛应用。在文献［2］中，运用遗传算法在OSPF路由中优化最短路径权值，以使网络拥塞最小。文献［3］中，提出了基于遗传算法的自适应路由方法能够快速决策路由。文献［4］中，运用多目标遗传算法对延迟、丢包率和网络费用3个目标函数进行了优化。仿真实验表明，该算法能获取满意结果。本文提出一种多QoS约束条件下基于遗传算法的多目标网络优化算法，该算法根据业务的QoS性质自适应地配置路径，产生一组最优非劣路径集合，其性能是在不同的目标之间取均衡。

1 问题背景

1.1 问题描述

假设将网络抽象为一个赋权图G(V，E)，其中V={v1，v2，…，vn}表示节点集，E={e1，e2，…，em}表示边集，n为节点数，m为边数。从源节点S到目的节点D的路径记作P，则服务质量(QoS)度量参数形式化表示如下

(5)瓶颈带宽bandwidth(P)=min(bekek)

假设用A={a1，a2，…，aj}表示网络中所有业务，对于任意业务ai(1≤i≤j)，业务流量为f(ai)，链路ek容量上限为υ(ek)，则链路ek总流量o(ek)定义为经过该链路的业务流量之和，即

链路利用率u(ek)定义为通过ek链路的总流量与ek链路容量上限的比值，即

1.2 多目标优化模型的建立

多目标优化存在着目标之间的相互冲突和目标值量纲的不统一，所以多目标优化的目的在于产生一组相互均衡的解方案，使得在满足约束条件的情况下这些解的各目标值相互非劣［1］。本文涉及到的目标函数有网络总费用、网络资源利用率方差和最大链路利用率，可分别用F1(A)、F2(A)和F3(A)来表示。其中，delay(ai)、hop(ai)、lost(ai)代表任意业务ai的延迟约束、跳数约束和丢包率约束。

多目标优化模型数学描述如下

其中

综合目标函数定义为

其中，w1，w2和w3代表3个目标函数的权重值，且满足

为统一量纲，在求解综合目标函数时需归一化处理，分别用各个子目标函数除以上一代个体子目标的最大值，其可分别用 F'1(A)、F'2(A)、F'3(A)表示，归一化处理后综合目标函数表示为

2 多QoS约束条件下的多目标优化算法

2.1 算法思想

首先采用多约束条件下的路径集预处理，为每个业务找出满足多QoS约束和流量约束的多条可行路径并编号，然后从每个业务路径集中随机抽取一个编号共同组成一条基因链，重复上述基因链生成方法获取初始种群，再运用遗传算法的选择、交叉和变异操作产生新个体，个体进化的方向是在满足多QoS约束和流量约束前提下，使得综合目标函数值最小，其目的是实现网络资源的有效利用，并提高网络的整体性能。

2.2 过程描述

基于上述思想和多目标优化模型，文中设计了一种基于遗传算法的多目标优化算法，其步骤如下

步骤1 初始化业务信息和网络拓扑信息。业务信息包括源节点、目的节点、带宽需求以及QoS信息(延迟、丢包率、跳数)。网络拓扑信息包括顶点信息(丢包率、延迟)和链路信息(源节点、目的节点、带宽、延迟、代价)。

步骤2 多QoS约束条件下的业务路径集预处理，计算出全网每个业务满足其QoS约束条件的路径集合。

本文使用Dijkstra算法产生多条从源点到目的节点的路径，然后判断这些路径是否满足业务对应的QoS约束和流量约束，若满足则加入业务路径集并编号，不满足则在相应路径的链路上增加代价值，再次运用Dikstra算法，直到获得的路径数量超出设定的上限值或连续使用Djistra算法超出设定的上限值时终止。由于Dijksta算法是根据变化的权重产生完整路径的，使用一次Djkstra算法只能产生一条最短路径，在本文中因多次使用Dijkstra算法，所以对权重的变化做了以下处理，将链路总流量乘以链路的费用作为链路代价，计算出业务从源到目的地的最短路径，并当该路径不满足多QoS约束和流量约束时，增加该路径上链路代价值。

步骤3 初始种群的生成。从每个业务的路径集中随机选取一个路径编号作为基因值，共同组成一条基因链，业务数量直接决定基因数量。初始种群的生成是在保证染色体不重复的条件下，按照设定的种群规模，重复上述基因链生成方式来获得。染色体的编码方式是采用整数编码，相比二进制编码而言更利于问题的描述。

步骤4 个体适应度值的计算。个体适应度值反应了个体适应环境能力的优劣，是遗传算法中评价个体优越的标准。本文适应度函数值设为

步骤5 算法迭代终止条件。算法迭代终止条件是通过公式(9)进行判断，其中求解精度ε的取值决定了算法迭代次数。这种通过调节求解精度来确定算法终止条件的方法更具一般性，相比于通过设置固定迭代次数作为终止条件的方法更为灵活。在式(9)中，fitnessbest(X)表示第X代的最佳个体适应度值，fitnessbest(X－a)表示第(X－a)代最佳个体适应度值，a为整数参数值，其取值不能大于种群大小

步骤6 遗传操作。遗传操作涉及选择、交叉和变异。选择的目的是用来重组或交叉个体，本文采用随机两两选择。

交叉是指从亲代群体中随机选择两个个体作为父个体，按照某种方式相互交换其部分基因，生成两个新的子代个体的过程。交叉操作的目的是提高遗传算法的搜索能力，以获得新的优良个体。交叉概率取值范围在0～1。本文通过依次比较每个基因位随机生成的概率值Pgen［i］与交叉概率的大小来实现两个配对个体在该点的部分基因互换，当个体基因位的随机概率值Pgen［i］大于交叉概率时进行基因互换。

变异用于产生新个体，使得遗传算法具有局部搜索能力并能保持种群的多样性，使算法向良性方向发展。变异概率取值范围0～1。

步骤7 爆破处理。爆破处理是当出现未成熟收敛或产生明显征兆时的一种应急措施，其在保留最佳个体的前提下，随机选择当前群体中β个个体，用相同数目完全随机生成的个体替代，以保持群体多样性，达到挣脱未成熟收敛，提高算法求解精度的目的。实施爆破处理的条件是，当代平均适应度值提高在γ以内时进行爆破处理。文中γ取值为5%。

步骤8 个体淘汰机制。个体淘汰的目的是对种群的规模大小进行控制，当种群大小超过阈值时，对种群中的个体进行排序并删除一些适应度值较低的个体。

2.3 算法实现流程

算法实现流程如图1所示。

图1 算法实现流程图

3 算法性能评价

仿真用到的网络是下一代国际互联网美国Abilene骨干。

仿真使用业务需求数据来源于“通信网络规划数据库——SNDlib”中提供的测试数据［5］。

表1 实验数据

遗传算法运行的基本参数设定:种群个数为800，变异概率为0.05，交叉概率为0.6。算法终止条件是ε =0.000 1，3 个目标函数的权重分配:w1=0.4，w2=0.3，w3=0.3。

3.1 求解精度对算法迭代次数的影响

传统遗传算法中通过设置固定迭代次数来终止算法运行，这种方式有失灵活性。假设在某些网络环境中，经过较少的迭代便可获得最优解，而算法设置了较高的迭代次数作为终止条件，这会增加算法的运行时间，因为迭代次数越多，算法所花费的时间也越多。而本文通过调节求解精度来确定算法终止条件的方式不失一般性，相比较为灵活。表2给出了在Abilene网络环境中求解精度对算法迭代次数的影响，表中数据表明:ε取值越小，算法求解精度越高，算法迭代次数呈现出缓慢增长趋势，且结果逐渐趋于稳定。当ε取0.000 1时，算法求解目标函数的结果较优。

表2 求解精度对算法迭代次数的影响

3.2 爆破处理对算法的影响

图2给出了算法使用爆破处理与未使用爆破处理情况下对最优个体的网络总费用目标函数值的影响。从图中变化趋势可看出，经过爆破处理得到结果要优于未经过爆破处理所得到的结果。这说明爆破处理能够增加种群的多样性，防止了算法陷入局部最优。

图2 爆破处理对最优个体的影响

3.3 多目标优化性能分析

从采集的业务需求中随机抽取50个实例，分别用Lingo软件的线性规划方法和本文的多目标优化算法进行求解。线性规划方法以最优网络总费用为目标，本文算法以网络总费用、链路利用率方差及最大链路利用率为目标，并将结果用三维图形呈现。

图3 网络总费用－链路利用率方差－最大链路利用率关系图

从图中数据分布可知，综合考虑网络总费用、链路利用方差和最大链路利用率3个目标函数时，本文算法获得的解集相对较为集中，其更靠近中心点，整体性能较优。而线性规划获得的精确解偏离中心点，只能单方面的获得网络总费用最优，而其他两个方面的性能则较差。

4 结束语

本文使用改进后的遗传算法求解多业务网络环境中的多目标优化问题。在满足各业务服务质量的基础上，以最佳形态均衡各子目标，最终获得了满意的解。

［1］催逊学，林闯.一种带约束的多目标服务质量路由算法［J］.计算机研究与发展，2004，41(8):1367 －1375

［2］PARDALOSP M.A genetic algorithm for the weight setting problem in OSPF routing［J］.Journal of Combinational Optimization，2002(6):299 －333

［3］BAROLLI L，SAWADA H，SUGANUMA T.A new qos routing approach for multimedia applications based on genetic algorithm［J］.IEEE CW，2002(6):289 －295.

［4］MOU D，BISWASG P，CHANDAN B.Optimization of multiple objectives and topological design of data network using genetic algorithm［C］.Guangzhou:RAIT，2012.

［5］LEELA R，THANULEKSHMI N，SELVAKUMAR S.Multiconstrain QoSunicast routing using genetic algorithm(MURUGA)［J］.Applied Soft Computing，2011(11):1753 －1761.

［7］ARIE M CA K，MANUEL K，CHRISTIAN R.On the robustness of optimal network designs［C］.Guilin:IEEE ICC，2011.

［8］CIDON I，ROM R，SHAVITT Y.Multi－ path routing combined with resource reservation［C］.Kobe:Proceedings of the IEEE INFOCOM 97，IEEECommunication Society，1997:92 －100.

［9］杨云，徐永红，李千目.一种QoS路由多目标遗传算法［J］.通信学报，2004，25(1):43 －51.

［10］凌永发，徐宗本.一种均衡网络流量的遗传算法［J］.计算机工程，2007，33(7):1 －3.