基于服务质量的遗传蚁群融合算法应用研究*

潘晓君，张佑春

(安徽工商职业学院 1.信息工程学院；2.应用工程学院，合肥 231100)

基于服务质量的遗传蚁群融合算法应用研究*

潘晓君，张佑春

(安徽工商职业学院 1.信息工程学院；2.应用工程学院，合肥 231100)

随着网络的环境变得越来越复杂，数据包的转发也时常出现一些问题，诸如丢包、延迟、抖动等异常情况.为了更有效地增强网络路由性能，提出了一种将遗传算法与蚁群算法相融合的方法来提高数据包的转发效率，确保网络的服务质量.根据服务质量约束条件以及当前的最优路径对可选节点集进行优化，将遗传算法加入到蚁群算法的每一次迭代过程中,利用遗传算法全局快速收敛的优点,来加快蚁群算法的收敛速度,使求解过程中尽量避免陷入局部最优，增强了寻优的能力.实验结果表明，该算法在提高网络路由效率方面具有一定的理论价值和实际意义.

遗传算法；蚁群算法；服务质量

1 遗传算法与蚁群算法的基本原理

遗传算法由于具有可扩展性、很强的鲁棒性及快速的全局搜索能力等特点，可以很容易的和其它算法相结合，但遗传算法本身对于系统中的反馈信息利用不是很充分，当求解的范围比较大时，就会进行大量的无效的迭代运算，大大降低了算法的效率；同时，由于其初始信息素资源匮乏，导致该算法开始的时候非常慢[1].

蚁群算法具有很好的正反馈机制和高收敛特性，它运用蚂蚁的行走路径来表示待求解问题的可行解,并不依赖于具体的数学问题,具有非常强的全局优化能力,已经广泛应用于数据优化类的NP问题中[2-4].然而，蚁群算法自身也有一些缺陷,诸如易陷入局部最优、收敛速度较慢等.

2 基于服务质量的网络路由模型

基于服务质量的路由选择是向用户提供端到端的服务质量保证.服务质量指标主要包含丢包、延迟、抖动等,这些参数构成了服务质量路由选择的约束条件[5-6].基于服务质量的网络数据路由的目的就是在网络中寻找最优路径,要求从源节点出发,历经所有的目的节点,并且满足所有的约束条件,达到特定条件下的服务水平[7].

网络路由选择可以被抽象成为一个带服务质量约束的有向图.网络模型表示为赋权图G=(V,E),其中V是图中网络节点(诸如主机、交换机、路由器等)组成的集合,E是网络中数据链路的集合，其中的每一条边表示两节点间的可达路径.这里假定s∈V为源点,M∈{V-{s}}为终点.于是对于任一网络中的节点n∈V，定义了三种属性，分别为丢包率函数packet-loss(n)、延迟函数delay(n)、抖动函数jitter(n)，则对于给定的源点s∈V，终点集合M,节点t∈M,s与M组成的数据转发分层树T(s,M)则有如下关系:

(1)packet-loss(PT(s,t))=1-∏n∈PT(s,t)(1-packet-loss(n))；

(2)delay(PT(s,t))=∑e∈PT(s,t)delay(e)+∑n∈PT(s,t)delay(n)；

(3)jitter(PT(s,t)=∑e∈PT(s,t)jitter(e)+∑n∈PT(s,t)jitter(e)；

这里PT(s,t)为分层树T(s,M)上源点s到终点t的数据转发路径.

下面给出网络数据转发路径选择的约束条件，该条件定义如下：

(1)丢包率约束:packet-loss(PT(s,t)≤PLt;

(2)延迟约束:delay(PT(s,t))≤Dt

(3)抖动约束:jitter(PT(s,Mt)≤DJt;

其中,PL、tDt、Jt分别代表业务对网络丢包率、延迟、抖动的约束限制.

3 遗传蚁群算法的融合设计

由于单独的遗传算法和蚁群算法各自在寻求最优解的过程中，都存在一些缺陷，所以为了克服这些缺点，把两种算法结合起来，将其引入到网络路由选择的具体服务中综合考虑，以寻求寻求全局中的最优解.运用遗传算法具有的全局快速收敛与随机搜索等特性产生相关问题的初始信息素分布；利用蚁群算法的正反馈机制、并行性等特性来对相关问题进行求解，得出全局最优解，这里将遗传与蚁群相结合的算法称为遗传蚁群算法.

3.1 遗传算法求蚁群初始信息素

(1)初始种群的生成

服务候选集是以随机的方式生成，依次从每个服务候选集中随机选出具体服务组成的染色体，得到所需要的初始种群.

(2)算子的选择

采用最佳个体保留方法进行算法的选择.

(3)变异算子

变异结点是从当前的染色体中用随机的方法选择一个节点，但起始节点与目标节点被排除在外，从变异节点所对应的服务候选集中随机选择新的变异基因替换当前的基因.

3.2 利用蚁群算法求最优解

3.2.1 信息素更新规则

τij(t)表示在t时刻路径p(i,j)上的遗留的信息素，为了避免残留信息素过多引起的残留信息淹没启发式信息的问题，使蚂蚁能准确感知路径信息，我们规定在每只蚂蚁走完所有的服务节点后，对p(i,j)路径上的信息素进行全局更新：

zxy(t+n)=r*zxy(t)+Δzxy(t)

(1)

(2)

公式(1)、(2) 中Δzxy(t)表示本次循环中路径p(x,y)的信息素增量.

3.2.2 信息素约束规则

本文的信息素约束函数有如下关系：

(3)

本文采用信息素的约束函数关系来提高全局搜索能力，如公式(3)所示，也就是通过蚁群算法采用最小和最大信息素阈值来阻止因信息素过低而丧失路径选择的机率或者是因信息素过高而陷入局部最优.

3.3 遗传蚁群算法的流程

基于初始种群的生成方式、信息素更新以及约束规则，本文的遗传蚁群算法流程如图1所示.

图1 遗传蚁群算法流程

4 实验测试与性能分析

4.1 实验参数的设置

为了验证融合算法的有效性、稳定性及可行性，本文将该算法与传统的遗传算法与蚁群算法在网络服务中对数据的处理进行比较，实验的参数设定如表1所示.本文设定了三组服务候选集样本数据，如表2所示，其中包含90个基础服务，时间、价值、稳定性为网络服务所设定的属性参数.时间设置的范围T∈[5，35]，价值设置的范围在C∈[45，90]、稳定性范围在p∈[1.0，2.0]，这三个属性参数值都是随机生成的.本实验可以对参数进行适当的调整，均可以得到比较满意的结果.

表1 参数取值表

表2 服务候选集

4.2 实验测试与结果分析

(1)收敛性

如图2所示，相对于传统的遗传算法和蚁群算法，本文的遗传蚁群算法在寻求网络服务最优解的过程中，可以在较少的进化迭代次数内得出全局最优解，而不是局部最优解，该算法较好的克服了普通遗传算法得出的不是全局最优解，普通蚁群算法收敛性能不佳的问题，提高了网络数据转发的效率，增强了整个网络的性能. 从图2中看出，蚁群算法的收敛性能较差.

图2 遗传算法、蚁群算法与遗传蚁群算法收敛曲线

(2)代价

在相同条件下，三种算法的网络路由代价比较如图3所示，相对于传统的遗传算法和蚁群算法,本文的遗传蚁群算法的代价曲线波动不大，比较平滑，几乎每一代的遗传操作均能得到最佳网络路由，有比较好的收敛性，但由于该算法操作的时间复杂度较大,耗费的运算时间较长,计算量较大，从侧面也影响了算法的性能.而遗传算法的代价波动较大，说明寻找路径刚开始时,链路上的信息素信息非常匮乏.

图3 遗传算法、蚁群算法与遗传蚁群算法代价曲线

(3)延迟

在相同条件下，三种算法的网络路由延迟比较如图4所示，相对于传统的遗传算法和蚁群算法，本文的遗传蚁群算法和蚁群算法的延迟曲线相对比较平稳，表示能较快地找到最优解(或次优解)，而遗传算法相对来说延迟较大，不能很快找出最优解.

图4 遗传算法、蚁群算法与遗传蚁群算法代延迟曲线

(4)抖动

在相同条件下，三种算法的网络路由延迟比较如图5所示.相对于传统的遗传算法和蚁群算法,本文的遗传蚁群算法的抖动曲线比较平滑，抖动曲线起伏不大,表示在最优解附近波动.从图5中看出，遗传算法波动起伏较大，离最优解较远.

图5 遗传算法、蚁群算法与遗传蚁群算法抖动曲线

5 结束语

如何提高网络路由的效率，针对传统蚁群算法收敛性能不佳的问题，遗传算法得出的不是全局最优解，这里将这两种算法融合起来进一步增强数据包的转发效率.该算法采用蚁群算法的混合蚂蚁行为使初始路径差异化,根据服务质量约束条件以及当前的最优路径对可选节点集进行优化,将遗传算法加入到蚁群算法的每一次迭代过程中,利用遗传算法全局快速收敛的优点,来加快蚁群算法的收敛速度,使求解过程中尽量避免陷入局部最优，增强了寻优的能力.实验结果表明，该算法在提高网络路由效率方面具有一定的理论价值和实际意义.

[1] 马 炫,刘 庆.多组播路由问题的粒子群优化算法[J].计算机研究与发展,2013,50(2):260-268.

[2] 李 飞,易傅潇,王 浩.多QoS约束下的PSO云存储任务调度算法[J].计算机工程与设计,2015,36(7):1767-1770.

[3] 孔宇彦,姚金涛,张明武.Ad hoc网络基于GA-NCE的QoS组播路由优化算法[J].计算机应用研究,2014,31(8):2426-2429.

[4] 黄永青，张祥德，李旭东.交互式蚂蚁算法[J].控制与决策,2012,27(4):609-612.

[5] 周德荣.基于蚁群算法改进的AODV路由协议研究[J].西南师范大学学报(自然科学版),2014，39(11):75-80.

[6] 袁丽乔，杨喜旺，杨梦茹.基于BP分类的粒子群QoS路由算法研究[J].计算机工程与应用,2015,51(9):98-102.

[7] 夏 利,田东渭,张艳艳.网格和组播树结合的QoS路由[J].小型微型计算机系统,2014,35(4):720-722.

ApplicationofGeneticandAntColonyFusionAlgorithmBasedonQualityofService

PAN Xiao-jun1, ZHANG You-chun2

(1. School of Information Eng., 2. School of Applied Eng. Anhui Business Vocational College, Hefei 231100, China)

As the network environment becomes more and more complex, packet forwarding problems often arise, such as packet loss, delay, jitter and other anomalies. In order to enhance the performance of network routing more effectively, a method combining genetic algorithm with ant colony algorithm is proposed to improve the efficiency of data packet forwarding and to ensure the QoS of the network. According to the quality of service constraints and the current optimal path set to optimize the optional nodes, the genetic algorithm is added to each iteration of ant colony algorithm. The advantages of using genetic algorithm to accelerate the convergence, and the convergence speed of ant colony algorithm can avoid falling into a local optimal solution process, and enhance the ability of searching excellence. Experimental results show that the algorithm has certain theoretical value and practical significance in improving routing efficiency.

genetic algorithm; ant colony algorithm; quality of service

2017-05-17

安徽高校自然科学研究重点项目(KJ2017A761)；安徽省高校优秀青年人才支持计划重点项目(gxyqZD2016438)；安徽省质量工程项目(2016tszy012).

潘晓君(1978-)，男，讲师，硕士，网络工程师，研究方向：网络与信息安全.

TP393.02

A

1671-119X(2017)04-0030-05