基于遗传算法的多约束QoS单播路由算法*

彭璐，何加铭

（1.宁波大学信息科学与工程学院，浙江 宁波 315211；2.宁波大学通信技术研究所，浙江 宁波 315211；3.浙江省移动网应用技术重点实验室，浙江 宁波 315211）

1 引言

目前，互联网的本质是一种无连接的网络[1-2]，传统的网络只提供一种尽力而为的服务。然而，一方面随着网络的急剧发展，人们对网络传输容量、质量、实时性的要求越来越高，传统的网络已经不能满足用户的需求；另一方面，网络带宽资源日益趋紧，目前的网络很难同时满足多种应用要求，尤其是数据传输容量与实时性的要求。如此有限的网络带宽资源如何适当地被网络系统使用，确保得到最大数据传输量的同时不以丢失传输速率为代价成了一项重要的任务。

为了解决上述问题，QoS机制[3-4]应运而生。它旨在保证服务质量，在网络多媒体等方面有着广泛的应用。该机制主要涉及多约束路由选择问题，而该问题为NP-完备问题[5]，这种问题难以用传统的算法解决。GA（Genetic Algorithm，遗传算法）[6]是一种模仿自然选择的过程（优胜劣淘、适者生存）和遗传的机理（交叉和变异）来寻找最优解的启发式搜索，它具有收敛性好、鲁棒性强、潜在并行性等特点，使得节点QoS路由选择问题简单、有效。

对于QoS路由问题，文献[7]针对多点投递和单点投递情况提出一种基于遗传算法的QoS路由选择策略，但是该算法采用一种二进制编码方案，需要对解空间和编码空间进行转换，增加了算法的复杂度，而且伴随着网络节点增多，解空间迅速增大，这也增加了搜索空间，使得算法效率急剧降低。文献[8]提出一种基于带宽时延约束的QoS单播路由算法，但是只考虑一种单一的QoS参数即时延。文献[9]提出一种带约束的多目标服务质量路由算法，通过对QoS参数的限制条件进行阐述，找到了一条满足QoS的路由，但是该算法通过适应度函数计算适值，同时约束了带宽和丢包率，把时延和代价同时作为目标函数，且没有经过预处理，这不仅使得计算过程过于复杂，而且还增加了算法运行时间。文献[10]提出一种单播多约束的遗传算法，但是算法的交叉和变异操作由于没有经过修复，容易产生无效路径即不存在解。

针对以上问题，本文提出一种基于改进遗传算法满足多约束QoS单播路由的算法，在满足带宽、时延、丢包率和延时抖动的约束条件下，寻找出一条花费最小的路径。该算法具有较好的收敛速度，并且通过实验证明得到的解（最优路径）是全局最优的，较好地提高了QoS满意率。

2 网络模型与问题描述

网络模型定义为图G(N,E)。用N={n1,n2,...,nn}表示节点集合，用E 表示链路集合，每条链路记作(u,v)∈E，包含参数：网络链路带宽B(u,v)、链路时延d(u,v)、链路费用c(u,v)、丢包率l(u,v)、延时抖动j(u,v)，给定源节点s和目的节点d，网络带宽约束Band、时延约束Delay、丢包率约束Loss、延时抖动约束Jitter。多约束QoS单播路由就是寻找满足给定约束的从源节点到目的节点代价最小的路径。对于从源节点s 到目的节点d 的路径记作P(s,d)（由多条链路(u,v)组成），则问题可转化为以下优化问题：

3 基于改进遗传算法的QoS路由算法

3.1 编码

本算法采用一种可以直接被用于遗传操作的编码方案，即路径序号编码，它对于网络节点以数字顺序编号，按照路径中节点出现的顺序，依次记录节点编号作为群体中的一条染色体。该算法直接用解空间作为编码空间，无需进行编码空间转换，简化了算法操作步骤，节省了运行时间，提高了运行效率。

3.2 初始种群

在种群初始化时，加入一个预处理环节，对给定网络拓扑结构进行遍历，把链路带宽与给定限制带宽对比，将小于给定约束的链路作为不可达链路，同时从拓扑结构中去除这段链路，获得一个新的拓扑结构图，经过筛选的拓扑图可能不是连通的。如果得到的拓扑图是非连通的，且源节点和目的节点不在同一连通子图里，则无法提供服务。假设筛选后得到的满足带宽约束的网络拓扑结构是连通的，那么以下研究将不再考虑带宽约束条件。带宽约束筛选的过程，通过保留符合带宽限制的路径，不仅减少QoS参数中带宽这一限制条件，大大方便了算法设计，而且对原有的网络空间进行缩减，减少编码空间，使算法性能得到了进一步优化。

采用随机深度优先搜索算法进行种群初始化，该算法的基本思想是：以源节点为起始节点，随机选择1个邻接节点作为下一节点，连接这2个节点，判断下一节点是否为目的节点，如果不是则把下一节点作为起始节点重复上述操作，直至下一节点是目的节点，在重复上述操作的过程中要确保网络中的每个节点最多在路径中出现一次，这样才能保证得到的路径是无环且有效的[11-12]。通过完成上述操作将得到所有可能解集即初始种群，但是该种群是不满足约束条件的。

3.3 适应度函数计算

遗传算法通过对每一代个体评估来决定该个体是被抛弃还是遗传到下一代种群，而这个评估过程的实现是通过使用适值函数计算一个适应值来确定的。这样适应度函数的设计将直接影响到该遗传算法的收敛速度及是否会陷入局部最优解，设计的函数应能体现个体性能，满足多QoS约束且花费较小的个体性能好，则其对应的适应值应该大；反之，不满足约束或者花费较大的个体则适应值应该尽可能小。在自然选择过程中，适应度指的是生物对当前环境适应能力的大小，一般适应度高的其生存能力强，反之则容易被自然选择所淘汰，这就是常说的优胜劣淘机制。而遗传算法是对自然机制的模拟，同理适应度高的个体被选中的概率就大，反之则容易被淘汰。

本算法的适应度函数定义为：

其中，α 为正实系数，Fd、Fl、Fj分别为fd、fl、fj的正加权系数（Fd+Fl+Fj=1），分别表示延时、包丢失率和延时抖动在约束函数中所占的比重，即该性能的限制条件。取值如下：

Φ(Z)是定义的一个惩罚函数，用来度量QoS参数的满足程度。当在约束范围之内时，r 值为1，否则值为r ∈(0,1)。r 是定义的一个惩罚因子，如果r 选取太小，则会造成过重惩罚，使得那些适值小的个体直接被淘汰，永久不会被选择，这样将导致算法解陷入局部最优；如果选取太大，则惩罚太轻，起不到加快收敛的作用。因此，考虑到实际情况，根据违反的程度进行惩罚，即违反程度越大则惩罚力度就越大。r取值公式如下：

其中，constraint 表示给定约束值，reality 表示实际值（每条路径时延、延时抖动、丢包率的值）。

这是本文提出的一种新惩罚制度，通过加强对不满足约束条件个体的惩罚力度，加快优胜劣淘的速度，快速寻到最优解。

3.4 选择

选择算子的优劣是影响算法收敛性的直接因素，本遗传算法采用结合最佳个体保存法和赌轮法的选择算法，即首先选出N 个精英（适应度最高）个体作为最佳个体（本算法中N 取1），选中的个体将无需直接参与形成下代群体的交叉和变异操作，这就使得每代的最优解在进化的过程中不会被破坏。种群中余下的其他个体则使用赌轮法执行选择。

3.5 交叉

现在常用的交叉方法之一就是单点交叉，本算法将其进行改进之后再使用，主要过程是：对于完成选择得到的染色体（种群个体），首先分别在其上面选择2个点，并判断这2个点是否是起始或者目的节点序号，如果是则重新选择，直到选中的节点非源和目的节点；然后确定交换位置（交叉点前或者交叉点后），本文选取交叉点之后；最后将2个染色体以1的概率互相替换交叉点之后的链路，得到2个新的染色体，即下一代个体（新源到目的节点的路径）。

3.6 变异

依据优胜劣淘的思想，通过上述适值计算、选择、交叉过程得到最优个体即最优解可能是局部最优而不是全局最优，这将导致“早熟”现象的产生。使用变异操作通过随机改变染色体中点（路径中节点序号）可以避免这种现象的产生，确保了种群的多样性。对于交叉完成得到的新子女个体以概率进行变异，若变异概率太大则会影响种群的真实性，若太小则不能达到目的，因此变异概率通常是0.1或者更小，这样可以使算法很快跳出局部最优解靠向全局最优解。变异方式如下：

（1）判断当前路径是否是无效路径（不存在链路或者循环链路）。

（2）如果是无效链路，则使用上述选择出直接进行遗传的“最佳路径”来替换这条无效路径。

本变异算法通过替换不仅避免了“早熟”现象，而且通过路径替换确保了路径的有效性，使得种群变得有效，提高了种群质量，从而加快了算法的收敛速度。

4 算法分析与仿真结果

该算法仿真工具选取MATLAB，采用Waxman提出的方法[13]来进行实验网络的生成，这个方法能够产生一个具有实际性能的随机网络图，它的中心思想是：在一个确定区域随机产生N 个节点，通过使用欧拉公式来计算2个节点间距离，任意2个节点i 和j 之间的连接依照一定概率实现，公式如下：

其中，dis(i,j)表示节点i 和节点j之间的距离，Lmax是任意两点间的最大距离。α 和β 是介于(0,1)之间的参数，在实验中分别取0.3和0.4，则得到如图1所示的节点网络结构模型。图中链路的带宽约束、时延约束、丢包率约束、延时抖动约束分别为20、100、0.05、25，链路的度量参数带宽、时延、丢包率和延时抖动、费用分别在[10,100]、[0,50]、[0,0.01]、[0,15]、[5,25]内随机产生，源点和终点在网络拓扑图中随机产生。对仿真结果的评价主要分析算法的可行性和收敛性。为了保证数据的准确性和稳定性，每个数据点都是经过100次随机实验后统计平均得出的。

图1 节点网络结构模型

以上面生成的网络模型为例进行实验。设定进化代数generation为20，交叉率为1，变异率为0.1，源节点为1，目的节点为12，种群规模由初始遍历的路径个数而定。在实验中，网络节点数分别取13、33、53、73、93，而目的节点数始终固定为12，得到如图2所示的结果。

图2 不同规模收敛时参数变化对比图

由图2可知，QoS参数曲线都在限制曲线（粗线）的下方，因此每代收敛得到的最优解都满足QoS约束，证明了本算法的可行性。为了进一步验证算法的有效性，本文又做了扩展性实验，比较该算法和传统遗传算法。对每种算法都重复执行100次，得到如图3所示的算法运行时间对比图。

由图3可知，在运行时间上，本算法明显优于传统遗传算法。在93个节点网络中执行遗传算法操作，得到如图4所示的结果。

图3 算法运行时间对比图

由图4 可知，本遗传算法在第二代收敛，传统遗传算法在第四代收敛。本算法具有较好的收敛性，并且在收敛时，本遗传算法的QoS参数值曲线在传统遗传算法的上方，这说明本算法的最优解优于传统遗传算法的最优解。

图4 2种算法QoS参数变化图

综合以上分析可知，本算法是可行的，并且较传统遗传算法有更好的性能。

5 结束语

本文针对QoS单播路由问题，设计了一种改进遗传算法满足多QoS约束的单播路由算法。该算法具有以下特点：

（1）初始种群时引入带宽约束，淘汰不满足带宽约束的路径，减少搜索空间，提高搜索效率；基于路径编码，简化了编码操作，去掉了复杂的解码过程。

（2）计算适值时，引入新的动态惩罚机制，依据违反程度来进行惩罚，更好地保证了优胜劣淘的思想。

（3）变异算子使用一种新的“最佳路径”变异方式，更好地保证了种群的有效性。

实验表明，该单播路由算法是可行有效的且适用于大规模网络，并在时间性能和收敛性上都优于传统遗传算法。目前本算法只对单播路由进行研究，接下来将在组播路由优化中进行进一步研究。

[1] S Andrew Tanenbaum. Computer Networks[M]. 4th ed. Prentice & Hall, 1996: 85-86.

[2] C Baransel, W Dobosiewicz, P Gburzynski. Routing in Multihop Packet Switching Networks: Gbps Challenge[J]. IEEE Network, 1995(2): 38-61.

[3] 李香善,苏子义. Web服务组合QoS最优化问题研究[J]. 计算机科学与应用, 2014,4(3): 50-58.

[4] Baolin Sun, Shangchao Pi, Chao Gui, et al. Multiple Constraints QoS Multicast Routing Optimization Algorithm in MANET Based on GA[J]. Progress in Natural Science, 2008,18(3): 331-336.

[5] Zheng Wang, Jon Crowcroft. Quality-of-Service Routing for Supporting Multimedia Applications[J]. IEEE Journal on Selected Areas in Communications, 1996,14(7): 1228-1234.

[6] 陈国良,王煦法,庄镇泉,等. 遗传算法及其应用[M]. 北京: 人民邮电出版社, 1996: 3-5.

[7] 何小燕,费翔,罗军舟,等. Internet中一种基于遗传算法的QoS路由选择策略[J]. 计算机学报, 2000,23(11): 1171-1178.

[8] 李勇. 基于带宽时延约束的QoS单播路由算法[J]. 计算机技术与发展, 2011,21(3): 128-131.

[9] 崔逊学,林闯. 一种带约束的多目标服务质量路由算法[J]. 计算机研究与发展, 2004,41(8): 1368-1375.

[10] R Leela, N Thanulekshmi, S Selvakumar. Multi-Constraint Qos Unicast Routing Using Genetic Algorithm (MURUGA)[J]. Applied Soft Computing Journal, 2011,11(2): 1753-1761.

[11] 刘萍,冯桂莲. 图的深度优先搜索遍历算法分析及其应用[J]. 青海师范大学学报: 自然科学版, 2007(3): 41-44.

[12] Pranay Chaudhuri. A Self-Stabilizing Algorithm for Minimum-Depth Search of Graphs[J]. Information Sciences, 1999,118(1-4): 241-249.

[13] Bernard M Waxman. Routing of Multipoint Connections[J]. IEEE Journal on Selected Areas in Communications, 1988,6(9): 1617-1622.★