改进的量子遗传算法在网络拥塞控制中的应用

王飞

摘 要： 当前以遗传算法为基础的网络拥塞控制方法对网络拥塞存在控制目标选取耗时，最优目标参数选取不均等问题，控制效果不佳。针对这一问题，结合量子计算的优点，提出一种基于改进量子遗传算法的网络拥塞控制算法，首先对网络拥塞的原理进行分析，建立QoS路由拥塞控制数学模型，将量子计算引入遗传算法进行改进，在静态旋转角的量子遗传算法的基础上，保证拥塞目标参数的选取准确性，给出算法的实现方法和具体流程。实验结果表明，该算法的搜索速度快、效率高、可以很好地优化网络性能，实现拥塞控制。

关键词： 网络拥塞控制； QoS路由； 量子遗传算法； 网络性能优化

中图分类号： TN915?34； TP391.9 文献标识码： A 文章编号： 1004?373X（2016）06?0033?04

Application of improved quantum genetic algorithm in control of network congestion

WANG Fei

（Henan Polytechnic Institute， Nanyang 473000， China）

Abstract： Since the current network access and congestion control method based on the genetic algorithm has poor control effect such as time?consuming target selection and optimal target's parameters selection， a network congestion control algorithm based on the improved quantum genetic algorithm is proposed in combination with the advantage of quantum computation. The principle of network congestion is analyzed. QoS routing congestion control mathematical model is established. The genetic algorithm， introducing quantum computation， is improved to guarantee the accuracy of the selection of congestion target parameters on the basis of the static rotation angle of quantum genetic algorithm. The implementation method and the specific process of the algorithm is given. The test results show that the algorithm has fast search speed and high efficiency， can optimize the network performance in a good way， and achieve the goal of congestion control.

Keywords： network congestion control； QoS routing； quantum genetic algorithm； network performance optimization

0 引 言

随着互联网技术的快速发展，网络资源被越来越多的用户所占用，当网络资源远远不能满足用户需求时，就会产生“拥塞”。网络拥塞现象最早出现在1986年10月，自此以后，人们在网络拥塞领域进行了大量的研究工作。1988年，Jacobson提出了基于TCP流的端到端网络拥塞控制算法[1]，1996年Raj Jain教授提出了ATM拥塞控制中的显式速率指示[2]；K.Ramakrishnan和S.Floyd提出了TCP/IP协议上的显式拥塞指示（ECN）方法[3?4]。近年来，随着智能仿生类优化算法的发展，人们在应用优化理论进行拥塞控制算法的分析和设计方面做了大量的工作，并取得了一定的进展。其中遗传算法（GA）凭借其并行搜索、鲁棒性强等优点，获得了广泛的应用；但是却存在收敛速度慢、易陷入局部最优等缺陷。

为了解决传统方法存在的问题，本文建立了QoS路由优化数学模型，将量子计算和遗传算法融合形成量子遗传算法（QGA）并应用到网络拥塞控制过程中，它将量子的矢量表达引入到遗传编码中，通过量子逻辑门实现染色体的更新操作，该算法可以用一条染色体同时表示多种状态的信息，具有收敛速度快、搜索效率高、能跳出局部最优等优点。通过对静态旋转角的量子遗传算法进行改进，并进行了仿真及性能分析。

1 QoS路由拥塞控制问题的提出

计算机网络异常庞大、复杂，为了研究各种网络拥塞控制算法，首先需要建立QoS路由拥塞控制数学模型。

任何网络都可以用加权图[G=（V，E）]表示，其中，V是网络中的交换节点集合；E是连接节点的链路集合。对于[?（i，j）∈V]，定义链路[E（i，j）]上的两个QoS参数：带宽[bi，j]和延迟[di，j]。设p为该网络中源节点s到目的节点d的一条路径，跳数为[h（p）]，其瓶颈带宽[B（p）=][min（bi，j?（i，j）∈p）]，延迟[D（p）=（i，j）∈pdi，j]。

若路径p上某业务量的请求带宽是B，则该业务量占用的网络资源消耗函数可表示为：

[R（p）=（i，j）∈pB×D（p）=h（p）×B×D（p）] （1）

式（1）表明：跳数越少、延迟越小的路径，消耗的网络资源越少。

对于[?E（i，j）∈p]，链路利用率[Ui，j=Bbi，j]，为了反映路径p上负载分布是否均衡，通常用链路利用率的方差表示，如下式所示：

[δ2=i=1nj=1n（Ui，j-U）2ρi，j] （2）

其中，[U=（i，j）∈pUi，jh（p）]为[Ui，j]的均值。

QoS路由拥塞控制的基本原则是：从给定的网络G中选取源节点s到目的节点d的路径p，在带宽、延迟等参数满足要求的前提下，应尽量消耗较少的网络资源，并尽可能使网络负载均衡分布，从而达到拥塞控制的目的。基于上述原则，本文建立的QoS路由拥塞控制数学模型是：在网络拓扑结构已知的情况下，对所选路径p中的QoS参数进行优化，使得：

[B（p）>BD（p）≤Dmin（R（p））min（δ2）] （3）

其中，D是业务量的请求延迟。

2 改进的量子遗传算法的提出

为了解决传统遗传算法的问题，结合量子计算的优势，将量子计算引入遗传算法中，通常采用量子位作为信息的载体。一个量子位可以表示0和1之间的任意叠加态，即：

[ψ=α0+β1] （4）

其中，[0]表示自旋向下态；[1]表示自旋向上态。[α]和[β]为两个复数，代表[0]和[1]出现的概率幅，并且满足：

[α2+β2=1] （5）

量子遗传算法采用的是量子位染色体表示法，如式（6）所示：

[xki=αk11βk11αk12βk12......αk1tβk1tαk21βk21αk22βk22......αk2tβk2t......αkm1βkm1αkm2βkm2......αkmlβkml] （6）

式中：[xki]表示第k代第i个个体的染色体；m为染色体的基因个数；l为每个基因的量子比特数。这种表示方法可以同时将多个状态用一个染色体来反映，从而使量子遗传算法具有更好的多样性和收敛性。

为了保持种群的多样性，QGA一般采用量子旋转门作用于各叠加态或纠缠态的基态，通过改变它们的概率幅去更新种群[5]。若[ζi=αiβi]、[ζ'i=α'iβ'i]表示更新前后染色体中第i个量子比特旋转门的概率幅，则量子旋转门的更新策略可以表示为：

[ζ′i=cosδi -sinδisinδi cosδiζi] （7）

式中[δi]为旋转角，其大小和方向由不同的调整策略来确定。

本文提出的改进量子遗传算法（IQGA）是在QGA的基础上引入了量子交叉操作、动态旋转门调整机制和量子变异操作。下面分别介绍IQGA中引入的这三种策略。

2.1 量子交叉操作

量子交叉操作通过暂时交换个体之间的部分基因，以生成高适应度值的新个体，从而极大地提高IQGA的搜索能力，实现过程如下：

（1） 随机排序种群中的所有个体；

（2） 采用均匀交叉的方法产生新种群，交叉概率的自适应调整公式为：

[pc=pc1-（pc1-pc2）（f′-favg）fmax-favg， f′≥favgpc1， f′

式中：[fmax]为群体中最优个体的适应度；[favg]为群体的平均适应度；[f′]为要交叉的两个个体中较大的适应度值；[pc1=0.9]，[pc2=0.7]。

2.2 动态旋转门调整策略

量子遗传算法是采用量子旋转门进行种群更新的，其中，量子旋转角[δ]是算法的关键，其旋转方向和角度大小会影响算法的收敛速度。

旋转角有静态和动态两种调整策略，本文采用一种自适应变化的量子旋转门调整策略，设[f′]为当前的适应度值，[favg]为群体的平均适应度值，[fmax]为群体中最大的适应度值，则旋转角[δ]按式（9）自适应调整：

[δ=mfmax-f'fmax-favg， f′≥favgn， f′

式中m，n的取值范围是[0.001π，0.05π]。

式（9）表明，当[f′]高于群体的平均适应度[favg]时，说明当前个体具有较好的性能，自适应调整旋转角，使其向着有利于当前群体的方向演化；当[f']低于群体的平均适应度[favg]时，说明当前个体性能不好，此时应对它采用较大的旋转角。这样既不影响群体的收敛性，又保证了其多样性。

2.3 量子变异操作

量子变异的作用是轻微打乱某个体的进化方向，以防止该个体陷入局部最优，从而提高整个算法的搜索能力。本文采用的量子变异操作实现过程为：

（1） 随机选定参与变异的个体；

（2） 按一定的概率确定个体中的变异位；

（3） 对变异位量子比特概率幅[α，β]进行非门运算，实现量子变异操作。

3 基于改进量子遗传算法的网络拥塞控制的应用

根据QoS路由优化数学模型和IQGA中的各种设置，可以给出算法的实现流程图，如图1所示。

算法实现步骤如下：

Step1：生成初始种群[X（k0）]。将全部染色体的量子比特编码[α0i β0i]都初始化为[12 12]，以使其全部可能状态的等概率叠加都表示出来。

Step2：测量初始种群中的个体，得到一组状态[P（t0）]。

Step3：计算各状态的适应度。根据QoS路由优化数学模型，构建适应度函数：

[fitness=1F=1a×R（p）+b×δ2] （10）

式中a和b是使目标函数F的两部分大致相等的正实数。

Step4：记录最优个体及其适应度，判断是否满足终止条件，若满足，则终止程序；否则，利用量子交叉、量子变异以及动态旋转门调整策略获取新的种群[X（k+1）]，并返回Step3。

4 仿真实例

4.1 参数设置

下面利用该算法对计算机网络进行仿真研究。仿真网络采用最常见的Waxman模型[6]，链路生成概率满足式（11）：

[p（i，j）=αexprand（0，L）Lβ] （11）

式中：[α]，[β]为模型参数；[L]为模型中距离最远的两节点之间的长度。仿真时，设网络节点N=8，[α=0.2]，[β=0.4]，链路可用带宽范围是[1.6，3.0]，延迟范围是[3，5]，生成的拓扑网络如图2所示。

假设节点3上的业务流cbr0请求带宽是1.6 Mb/s，节点4上的业务流cbr1请求带宽是0.8 Mb/s，二者共同流向目的节点1。为了避免产生网络拥塞，下面利用本文提出的改进量子遗传算法优化链路3?2和链路2?1上的QoS参数。参数设置如下：种群大小为60，交叉概率[pc1=0.9]，[pc2=0.7]，变异概率[pm]=0.01，迭代次数为100。

4.2 结果分析

优化前后业务流cbr0的传输情况如表1所示。可以看出，通过该网络链路的带宽、延迟参数进行优化，可以降低丢包率，防止出现网络拥塞。

为了进一步验证该算法的有效性，采用静态旋转角的量子遗传算法对该网络进行同条件优化。

可以看出：与QGA相比，本文所提的算法可以获得更好的最优解；同时，QGA在90代左右目标函数才达到稳定，而IQGA进行到40代左右目标函数就基本稳定了，因此改进的量子遗传算法具有更快的收敛速度，全局优化性能好。

5 结 语

针对网络拥塞现象，提出了一种避免网络拥塞的改进量子遗传算法。该算法在标准量子遗传算法的基础上引入自适应量子交叉和变异操作，并采用动态旋转门调整机制。仿真结果表明：该算法的收敛速度快、搜索效率高、可以满足QoS路由优化的要求，更适合用于大型网络的拥塞控制研究。

参考文献

[1] 赵广松，陈鸣.基于接收阈值的容延网络拥塞控制机制[J].软件学报，2013，24（1）：153?163.

[2] 张行功，郭宗明.率失真优化的无线多跳网络多路径选择算法[J].软件学报，2011，22（10）：2412?2424.

[3] 李国华，李建中，高宏.ε?近似和加权公平性保证的无线传感器网络拥塞控制算法[J].计算机学报，2011，34（11）：2197?2210.

[4] 金彦亮，杨宇航，张珠明，等.一种适用于无线网络的基于速率的端到端拥塞控制算法[J].上海大学学报（自然科学版），2010，16（6）：597?602.

[5] 余小华，陈瑛.一种新的无线传感器网络拥塞控制算法[J].计算机工程，2011，37（11）：108?110.

[6] 蒋波.网络中的拥塞避免控制模型的仿真分析[J].计算机仿真，2013（6）：275?278.