基于量子遗传算法的网络拥塞控制路由算法研究

刘 锂

（成都理工大学工程技术学院，四川 乐山 614000）

量子遗传算法是量子算法与遗传算法结合而成的，该算法将量子机制引入到常规遗传算法中，弥补了量子算法与遗传算法收敛度低、适应度低等缺点，由于该算法具有量子算法的内在并行性特征，被应用到多个领域中均获得了成功。随着网络的快速发展，当网络储存资源达到极限时，经常会发生网络拥塞问题，会改变原有的网络拓扑结构，对网络通信性能造成一定的影响。网络拥塞控制路由算法成为解决网络拥塞的有效手段，但是传统算法在应用过程中具有较差的适应性，已经无法满足网络拥塞路由控制需求，所以提出基于量子遗传算法的网络拥塞控制路由算法，提高算法的使用度，对提高网络消息成功投递率、降低网络延迟具有重要的应用价值。

1 基于量子遗传算法的网络拥塞控制路由算法

1.1 引入量子遗传算法搜索路由

通常网络的拓扑结构为G=（V，E），其中V表示网络节点集合，E表示网络节点链路集合，网络对于任意一条路由的选择主要依靠4种度量定义，包括延时函数、宽带函数、费用函数、延时抖动函数；对于任意一个网络节点的控制也是通过定义4种度量，包括延时函数、费用函数、延时抖动函数、节点包丢失率函数[1]。在应用量子遗传算法对网络路由进行搜索之前，先需要根据网络的宽带约束条件对网络拓扑结构进行处理，对网络中所有节点进行编号，再删除不满足网络约束条件的边，以此形成一个符合宽带约束条件的连通网络。

节点编码是量子遗传算法搜索网络路由的首要步骤，网络节点编码是否合理将直接关系到算法的搜索效率，此次采用两个量子态叠加态的编码方法，假设网络中存在n个符合路由要求的节点，由路由节点的数量来确定量子比特的长度。

以arfi表示量子比特的值，btai表示刀a值，next表示下一个量子比特。该编码指针长度等于路由节点数量，通过以上方法对每一个染色体进行编码，包含所有网络路由目的节点，有助于提高网络的收敛性。

对染色体量子比特编码后，需要对初始种群进行测量，由于上文设计的编码是多维的，而对网络拥塞路由搜索操作都是对1，2字符串进行操作的，所以需要先把量子遗传的编码映射成二进制编码，再随机产生一个[1，2]数，当随机产生的数值大于概率幅时，则初始种群测量结果为2，否则为1[2]。对所有初始种群测量结果进行适应度检验，通过对初始种群中每个网络节点的适应值来进行筛选，适应度函数公式：

公式（1）中，ω1是关于网络分组丢失率的权重值；f(d)为针对分组丢失的罚函数；ω2是关于网络路由延迟的权重值；f(c)为针对网络延迟的罚函数；ω3是关于网络延迟抖动的权重值；f(h)为针对网络延迟抖动的罚函数。将适应度最佳的测量结果的初始种群作为下一步演化的目标值，该初始种群中的网络路由作为搜索结果输出。

量子遗传算法搜索流程：（1）令搜索时间为零，设定种群规模。（2）对种群实施量子交叉，得到交叉后的种群。（3）对种群中每个量子个体进行测量，得到译码后的量子集合。（4）运用适应度函数计算出量子个体的适应度值，令量子集合中适应度值大于1的量子个体作为新的种群，返回到步骤（1）进行重新量子遗传[3]。量子遗传算法的循环深入，使网络路由逐渐收敛于最优解，扩大网络路由搜索空间。

1.2 实现网络拥塞控制路由

上文利用量子遗传算法搜索出的路由只是符合网络延迟、网络延迟抖动、网络分组丢失条件，而网络拥塞产生的原因最主要是网络宽带对路由影响，所以要在量子遗传算法搜索到的路由集合中选择出受宽带约束最小的网络路由。此次利用KMB方法，在应用过程中实际是寻找网络中的Steiner点。网络中存在若干个节点，但仅存在一个Steiner点，该点到所有节点的距离和最小，网络路由穿过Steiner点说明受网络宽带约束最小。具体应用过程：（1）求出量子遗传算法搜索结果中各个路由的路径距离，两两节点间为最小代价路径。（2）对原有网络构造进行处理，生产新的网络拓扑构造。

公式（2）中，Vn表示量子遗传算法计算得到的网络节点集合；En表示量子遗传算法计算得到的网络节点链路集合，其中的每一条边是Vn中两个节点之间的最短路径；（3）在新的网络拓扑结构中，节点与节点之间距离最短，且用符合Steiner点条件的链路替换原有网络拓扑结构中节点与节点之间最短路径，以此完成网络拥塞路由控制，实现基于量子遗传算法的网络拥塞控制路由算法设计。

2 对比实验

2.1 实验设计

本次实验以Visual C++8.0作为编程工具，在CPU为Celeron3.10 GHz，内存为128 MB的计算机上进行仿真。

为了保证结果的有效性，实验中网络所有路由节点的延时、延时抖动、分组丢失等方面约束条件相同，并且采用一个四元组来定义网络中的延迟、延迟抖动、宽带、分组丢失，具体实验参数设定如表1所示。

表1 实验参数

2.2 实验结果

此次实验选取网络中一个小空间内部署较多的节点，并且令网络节点拥有较少的储存空间，将网络消息产生速率和大小调高，网络会在最快的时间内表现出拥塞。运用此次设计算法与传统算法对该网络路由进行控制，对比两种算法的适应度，实验结果如图1所示。

图1 两种算法适应度对比

可以看出，运用此次设计算法产生的网络路由比传统算法计算得到的网络路由适应度更高。两种算法在对网络拥塞控制路由的过程中都表现出一定的随机性，但是随着迭代次数的增高，传统算法计算得到的路由适应度逐渐下降，而对此次设计算法影响并不大，依然能够对路由进行有效控制，由此证明此次设计算法可以满足网络拥塞路由控制需求。

3 结语

在已有研究的基础上，本团队将量子遗传算法应用到网络拥塞控制路由算法中，形成一种新的算法，该算法具有较高的收敛性和适应性，对保持网络稳定运行具有重要的应用价值。由于时间有限，虽然取得了一定的研究成果，但也存在一些不足之处，对于网络拥塞控制路由算法的研究有待更加深入的探讨，比如，改进算法的终止条件等，以期为该方面研究提供参考依据。