基于遗传算法的优化QoS组播路由算法*

陈艳 李志远 马莉

(桂林航天工业学院 计算机科学与工程系，广西 桂林 541004)



基于遗传算法的优化QoS组播路由算法*

陈艳**李志远 马莉

(桂林航天工业学院 计算机科学与工程系，广西 桂林 541004)

随着网络宽带技术的快速发展，多媒体业务对服务质量(QoS)的要求越来越高，QoS组播路由也成为制约宽带技术发展的关键问题。为了提高通信网络的利用率和解决网络传输中QoS组播路由问题，提出了一种基于遗传算法的优化QoS组播路由算法。首先介绍了QoS组播路由的网络模型，然后详细阐述了优化QoS组播路由算法的设计，并通过仿真实验证明了该算法具有加快算法收敛速度，提高网络带宽利用率，降低网络拥塞等优点。

QoS; 组播路由；遗传算法

随着计算机通信网络和互联网应用的快速发展，网络的服务质量(QoS)越来越受到用户的关注，对于网络服务质量和网络带宽的利用率有了越来越高的要求，传统的通信方式以其点对点的连接、业务量小的劣势已无法满足当前网络应用的要求。多选择、多点接入、多连接的QoS组播路由技术已经成为通信网络中多媒体信息传输的关键技术。QoS组播路由算法直接影响网络传输的整体性能和效率，需要寻找满足QoS约束的代价最小树，即图论中的斯坦利最小树(Steiner树)即指定一个网络点集空间，求解将其中某些点互联后最短网络路径，这是一个NP-完全问题，这种问题很难用传统的算法解决。遗传算法(GA)是一种模拟自然界生物“优胜劣汰、适者生存”的进化过程，采用“交叉变异”的启发式搜索来寻找最优解，具有并行搜索、鲁棒性强、收敛性好等特点，是解决QoS组播路由问题的有效算法[1-2]。

目前将遗传算法应用到QoS组播路由中的算法很多，各种算法虽然在一定程度上解决了QoS组播路由的NP问题，但是随着网络应用的不断提升，网络规模大幅扩大，传统的基于遗传算法的QoS组播路由算法在收敛速度上越来越慢，且在网络带宽利用率要求越来越高的情况下，如何确保网络的服务质量，且能最大限度的提高网络利用率成为苛待解决的问题。基于这种应用背景，本文提出了一种基于遗传算法的优化QoS组播路由算法，算法中引入了空闲因子参数来加速收敛速度，提高算法路由路径的网络利用率，且对优化后的算法进行了算法扩展优化设计，极大的提高了QoS组播路由算法的有效性和实用性[3]。

1 原理介绍

1.1 QoS组播路由的现状

宽带IP技术的快速发展，多媒体业务的不断增多，使得组播方式的使用越来越广泛，如何满足业务的实时性要求和节省网络资源要求，QoS应运而生。在满足QoS约束的条件下，确保分组数据能发送到组播中所有成员的路径成为QoS组播路由的关键问题。求解实时性好的高效QoS组播路由问题演变为一个NP完全问题，难以用经典的最短路径优先算法对多约束问题进行求解。

遗传算法GA(Genetic Algorithms)是基于进化论原理发展起来的具有高效搜索能力的算法，遗传算法模拟生物进化过程，通过生物各个体的竞争、自然选择、杂交、变异等方式进行的一种“适者生存”的自然进化过程。虽然遗传算法是模拟的生物进化过程，实际上可以变化为某种优化问题的求解过程，遗传算法通过计算机技术模拟生物进化特征，从一组随机产生的初始“种群”中进行搜索，种群中的每个个体是问题的一个解，称为“染色体”，染色体在遗传算法后续迭代过程中不断的进化，通过适应度函数来决定染色体的好坏，从而产生下一代染色体。后一代染色体是通过前一代染色体进行杂交或者变异运算操作产生的，在产生过程中根据适应度值的大小来控制后代的规模，适应度值大的染色体被选中的概率大，通过选择部分后代，淘汰部分后代，保持种群的规模，经过遗传算法的若干次迭代进化后，最终会收敛出最好的染色体，该染色体就是经过遗传算法运算后，进化得出的最优解或者次优解[4-5]。

传统的求解QoS组播路由问题的方式都是围绕启发式算法来求解，当网络节点和链路数量不断增加时，启发式算法的计算时间代价会急剧增加，且效果很差。随着对遗传算法研究的不断深入，采用遗传算法来求解NP完全问题被证明效果很好，该方法同样适用于求解QoS组播路由问题。基于遗传算法的QoS组播路由算法成为当前研究的热点，传统基于遗传算法的QoS组播路由算法也存在很多的不足，如编解码过程复杂、算法收敛受限于网络规模、搜索空间过大导致算法运行效率低下等。根据传统基于遗传算法的QoS组播路由算法存在的缺点，储萍等提出了基于遗传算法的优化QoS组播路由算法，通过优化后的算法设计与实现来弥补传统算法收敛速度慢、执行效率低和网络利用不充分的问题[1]。

1.2 QoS组播路由网络模型

QoS组播路由网络可用强连通的无向图G(V,E)表示，其中非空集合V表示网络中节点集合,V={v1,v2,…,vn}；无向边集合E表示网络中两个网络节点间的双向链路集合,E={e1,e2,…,en},ei={|vi,vj∈V}。QoS组播路由网络对网络中组播源节点均能通过一条路径到达任意目的节点,每条链路都具有QoS属性,其中属性包括：带宽B(ei),延时D(ei)，延时抖动J(ei)，丢包率L(ei),空闲因子F(ei)。对于给定的源节点s和目的节点集合D={d1,d2,…,dn}，网络路径受QoS组播路由约束(带宽、延时、延时抖动、丢包率和空闲因子)，优化的QoS组播路由算法就是要寻找满足给定的QoS约束从源节点到目的节点网络利用率最高的最小代价路径。对于从源节点到目的节点的任意一条路径Pathij必须具有以下的性质：

B(Pathij)=Min(B(ei))

(1)

(2)

(3)

(4)

(5)

2 优化组播路由算法的设计

2.1 编码方式

遗传算法常见的编码方式有：二进制编码、有序串编码和结构式编码，基于遗传算法的优化组播路由算法采用结构式编码中的路由表编码表示法。采用路由表编码表示法具有遗传操作简单、染色体串长度较为固定(染色体串长度只与目的节点数有关，不会根据网络节点或链路数增加而增加)、优化后收敛速度快等优点。源节点s到每个目的节点都建立一张路由表，每张路由表记录源节点到目的节点的所有链路，每张路由表作为一个染色体。路由表编码表示法存在一些不合法的编码，但基于遗传算法的优化QoS组播路由算法进行了路径合法性设计，很好的规避了路由表编码的缺陷[2]。

2.2 适应函数

在遗传算法中，个体适应度值是直接反映个体繁殖能力的体现，它直接关系到繁殖后代的数量，适应函数是衡量种群中个体好坏的标准，个体的性能越好说明适应度函数的值越大，反之，个体性能差适应度值就会小。本算法适应度函数定义为：

f(P)=afB+bfD+cfJ+dfL+efF，其中

以上公式中，a、b、c、d、e分别是带宽、延时、延时抖动、丢包率和空闲因子在适度函数中所占的比例，它们的值根据具体应用来设置。bandwidth、delay、jitter、loss和free分别表示从源节点s到任何一个目的节点di的路径ei的带宽、延时、延时抖动、丢包率和空闲因子约束；B(ei)、D(ei)、J(ei) 、L(ei)和F(ei)分别表示路径的实际带宽、延时、延时抖动、丢包率和空闲因子；fb(x)、fd(x)、fj(x)、fl(x)和ff(x)分别为带宽、延时、延时抖动、丢包率和空闲因子的惩罚函数，当链路满足相应的约束条件时，惩罚值为1，否则惩罚值为kb、kd、kj、kl和kf，其中kb、kd、kj、kl和kf值的大小用来控制惩罚的力度。

2.3 遗传选择策略

遗传选择策略充分体现了自然界的“优胜劣汰”属性，从符合条件的群体中选择优良的个体，淘汰劣质个体。遗传选择策略将当前群体中的个体按与适应度值成正比的概率复制到新的群体中，使得低适应度值的个体趋向于被淘汰，高适应度值的个体趋于继续被选中。遗传选择策略的优劣关系到算法的收敛速度。

本算法的遗传选择策略采用了空闲因子辅助选择机制，在满足了标准的QoS约束后，通过空闲因子的大小来决定符合要求的个体。相对适应值的公式如下：

(6)

其中fi是群体中第i个个体的适应度值，N是群体的规模。每个个体的繁殖量为：Fi=free(yi*N),free(x)表示第i个个体空闲因子值。

计算出群体中每个个体的繁殖量，并形成一个临时的群体，根据空闲因子值的范围进行个体的筛选和交配得到下一代群体。这种采用空闲因子的选择策略将极大的提高现用网络的利用率，使得群体中满足条件的优秀个体得到繁衍。

2.4 交叉设计

交叉运算是将两个父代个体的部分基因进行替换重组产生新的个体，新的个体具有更好的适应度值，交叉运算使得算法具有有性繁殖能力。基于遗传算法的优化QoS组播路由算法采用单点交叉的方式，并引进空闲因子阈值F，当随机选出的父代个体fa与空闲因子值大于该阈值的个体fb时，进行单点交叉，产生下一代，确保了种群的多样性，防止近亲繁殖。

2.5 变异设计

变异操作可以保持群体的多样性，避免了求解过程陷入局部最优解，扩大遗传基因算法的搜索区域，基于遗传算法的优化QoS组播路由算法采用基因位取反变异，以一定的概率P将所选的个体的位取反变异。

2.6 合法性设计

基于遗传算法的优化QoS组播路由算法采用路由表编码表示，通过个体交叉、变异操作后，可能形成大量的环路路由，该类型的路由为非法路由，为了避免非法个体的产生，算法进行了合法性设计，当一个链路上出现相同节点时，需要将相同节点间的链路删除，剩余节点才能组成新的个体，实现了非法路由的剔除操作。

2.7 空闲因子设计

空闲因子作为提高网络带宽利用率和加速算法收敛的关键参数，在基于遗传算法的优化QoS组播路由算法中起着至关重要的作用，空闲因子的值为单位时间内链路当前空闲带宽占总带宽的比例值，空闲因子值越大说明该链路处于空闲度越高，在传统遗传算法中确保算法收敛的情况下，选择空闲因子值大的链路，将在很大程度上提高网络的利用率。

在优化算法中，空闲因子的引入对传统遗传算法的改进很大，引入的空闲因子需要设置梯度值和极限值，在优化算法的设计中，空闲因子是动态变化的，用户只需要根据实际情况给出一个极限值和梯度值，优化算法设计一个智能比对模块对可选路由网络节点进行识别，从满足QoS的路由节点中选中空闲因子值最大的节点进行交叉变异操作得到新的个体，从而加快传统遗传算法的收敛速度。

2.8 算法扩展优化设计

优化后的QoS组播路由算法和传统的QoS组播路由算法一样存在无法获得最优解的情况，基于遗传算法的优化QoS组播路由算法设计了算法的扩展优化功能，对于算法的实际应用背景，将决定在无法获得最优解的情况下，需要获取次优解或者有条件最优解，因此，在算法中加入了QoS约束自适应功能，当到达设定的最大迭代次数仍无法获得最优解的情况下，优化后的算法会对初始化过程中设置的次要QoS约束进行自适应梯度递减，降低次要QoS约束参数的值，使得算法再次进行迭代求解，根据初始化设定的算法重复寻解次数值，结束算法。

2.9 终止条件

基于遗传算法的优化QoS组播路由算法的终止条件与传统算法有很大的区别，传统算法一般采用最大进化代数和寻得最优解即退出算法运行，对于优化后的算法满足以下条件即终止运行：

1)算法在执行过程中求得最优解，算法终止运行。

2)算法在不启动扩展优化设计的情况下，算法使用空闲度遗传选择策略，在算法满足QoS约束的情况下，通过加入空闲因子策略加快算法的收敛速度，得到最优解，算法终止，退出运行；加入空闲因子策略无法获得最优解时，启用算法次优解求解模块，根据空闲因子梯度降低空闲因子值，当出现次优解时，算法终止运行；当启用算法次优解求解模块仍无法获得次优解，算法运行到最大进化代数后，进入算法扩展优化设计。

3)算法在初始条件下无法获得最优解时，算法通过扩展优化设计，根据设置的最大进化代数和次要QoS约束参数，算法执行该条件求得条件最优解即终止运行或算法执行完次要QoS约束，并完成最后的最大进化代数仍无法求得最优解即终止运行。

3 模拟仿真分析

为了证明基于遗传算法的优化QoS组播路由算法比传统的基于遗传算法的QoS组播路由算法具有更好的算法收敛性和实用性，且能提高网络带宽利用率，对两种算法进行了模拟仿真分析。实验中，算法采用C语言编程实现，基于遗传算法的优化QoS组播路由算法和传统的基于遗传算法的QoS组播路由算法在实现上基本相同，只是优化的算法中加入了空闲因子处理模块，在遗传选择策略中进行了优化处理，其他的实验参数(如：实验网络拓扑图、带宽约束、代价约束、时延约束、交叉概率、变异率等)保持相同。基于遗传算法的优化QoS组播路由算法选择的网络拓扑图如图1所示，传统的基于遗传算法的QoS组播路由算法的网络拓扑图如图2所示。

图1 优化算法网络拓扑结构图

图2 传统算法网络拓扑结构图

两种算法均选择源节点为①，目的节点为③、⑤、⑥、⑦，两种算法在运行过程中，选取交叉率均为0.6，变异率均为0.2,在图1、图2中均标注了各条链路的带宽约束、代价约束和时延约束，其中设置最小带宽为10，最小代价为2，最小时延为1。对于基于遗传算法的优化QoS组播路由算法加入了空闲因子值，设置空闲因子最低阈值为0.1，空闲因子智能梯度值为0.05。对于优化的算法在图1中采用(B，C，D，F)标识，对于传统算法在图2中采用(B，C，D)标识，两种算法均对全部链路进行了处理，通过QoS约束和合法性处理，基于遗传算法的优化QoS组播路由算法形成的合法路径集合如表1所示，传统的基于遗传算法的QoS组播路由算法形成的合法路径集合如表2所示。

表1 优化算法源节点到目的节点的路径集合

表2 传统算法源节点到目的节点的路径集合

通过当前网络拓扑图对两种算法合法路径的对比，基于遗传算法的优化QoS组播路由算法的合法路径集合比传统的基于遗传算法的QoS组播路由算法合法路径集合要小很多，小规模的实验网络拓扑说明：同等规模的网络拓扑，优化后的算法在经过合法性处理后执行效率比传统算法要高很多，算法的收敛速度更快。随着网络规模的不断增大，遗传算法中的染色体的基因也越来越长，算法执行的复杂度也会成倍增长，加入了空闲因子后的优化算法将大幅减少算法的执行复杂度，提升算法的执行效率，加快算法的收敛速度，且通过空闲因子提高网络带宽利用率。

由于基于遗传算法的优化QoS组播路由算法具有很强大的修复优化功能，特别是在无法获得最优解的情况下，求取有条件最优解。为了清晰简单的说明优化后的算法在性能上的优势，实验收集了100次两种算法在获得最优解情况下的时间统计，算法设定最大进化代数为100，每条路径的代价随机给出，实验数据采用100次试验的平均值，实心圆为优化后的遗传算法，空心圆为传统的遗传算法，具体情况见图3。

图3 规模时间统计图

通过对实验数据的分析，优化后的算法比传统的算法有更好的性能和收敛速度，对于同种规模的网络，优化后的算法收敛时间远远小于传统算法，由于没有配套硬件的支持，实验数据是通过软件处理获得的，在实际的应用中，硬件处理速度将获得更好的性能和收敛速度。空闲因子的值直接提高网络带宽的利用率，这项实验数据通过合法路径集的对比即可得出。

4 结束语

随着宽带技术的快速发展,网络应用对传输网络的要求也越来越高,大量的多媒体业务的涌现,使得用户对网络链路的实时性和服务质量要求也不断的提高,为了更好的解决这些问题,QoS组播路由问题成为了目前研究的一个热点课题,虽然该问题有了很多的研究成果,但目前仍没有发现一种有效的解决方案。QoS组播路由问题是一个NP完全问题，它的求解无法通过普通的路由算法来完成，传统的基于遗传算法的QoS组播路由算法在收敛速度、算法执行效率和网络利用率上都不尽如人意，在这种背景下，提出了一种基于遗传算法的优化组播路由算法，该算法对传统的基于遗传算法的QoS组播路由算法进行了优化改进，加入了空闲因子参数作为智能优化元素，不仅加快了传统算法的收敛速度，还很大程度的提高了网络带宽的利用率。在算法的设计过程中，对组播路由模型、QoS模型和遗传算法都进行了阐述，并对算法中编码方式、适应函数、遗传选择策略、交叉设计、变异设计、合法性设计、空闲因子设计和终止条件等核心部分进行了详细的描述，并通过仿真实验证明了基于遗传算法的优化QoS组播路由算法具有加快算法收敛速度，提高网络带宽利用率，降低网络拥塞等优点。目前基于遗传算法的优化QoS组播路由算法在执行过程中需要实时记录节点和链路的相关参数，并且对于记录的数据进行分析处理，实验过程采用的是计算机模拟路由节点的方式，在运行效率上远远落后于配套硬件运行的效率，随着算法的深入研究和网络产品硬件技术的快速发展，基于遗传算法的优化QoS组播路由算法也将具备很广阔的应用前景。

[1] 储萍,王康泰.基于极值遗传算法的QoS组播路由[J].计算机工程，2009,35(9):220-221.

[2] 金琼,周世纪,彭燕妮.基于改进遗传算法的QoS路由选择优化[J].计算机应用,2005,25 (2):256-258.

[3] 赵秀平,谭冠政.基于免疫遗传算法的多约束QoS组播路由选择方法[J].计算机应用， 2008,28(3):591-595.

[4] 郑金华.多目标进化算法及其应用[M]．北京：科学出版社,2007:20-55.

[5] 姚明海.改进的遗传算法在优化BP网络权值中的应用[J].计算机工程与应用,2013,49(24):49-54．

(责任编辑 陈葵晞)

广西自然科学基金项目《蚁群优化算法和粒子群算法混合建模求解组合优化问题研究》(2014GXNSFBA118286)；广西壮族自治区教育厅科研项目《基于遗传算法的QoS路由算法研究》(2013LX168)；《面向对象数据库在本体存储中的应用研究》(2013LX172)；2015年国家级大学生创新创业训练计划项目《基于互联网的数据侦听与智能分析系统》(201511825-007)。

TP393

A

2095-4859(2016)03-0309-06

**作者简介：陈艳，女，湖北荆州人。高级实验师。研究方向：计算机软件技术。