一种QoS 平面蚁群路由算法的设计与实现

蔡文哲，王斌君

(中国人民公安大学网络安全保卫学院，北京 102623)

0 引言

网络路由问题的研究常常通过以下2 个途径来提高服务质量［1］(Quality of Service，QoS):1)网络节点控制;2)全网或局域网络控制。网络节点控制针对单个节点或单链路，主要用于控制业务对单节点共享资源的占用;全网或局域网络控制常常利用对路由的控制来实现对业务流的控制。因为路由直接关系到网络性能，所以有效的QoS 路由［2］选择方案成为解决QoS 问题的一个关键技术，在网络技术领域内也是一个研究热点。

在实际网络中选择出一条合适的路径，使它符合一定的网络费用、网络延迟、延迟抖动和网络带宽的限制是QoS 路由的一项根本任务。Wang Zheng 等［3］证明了如果QoS 路由至少包含2 个限制时，它是一个NP-C 问题［4］。传统的路由算法［5］很难有效地解决NP-C 问题，但基于改进的自适应蚁群算法［6］却提出了一种行之有效的解决方案。

为了研究的方便，本文QoS 路由研究的对象设定为平面网络路由［7］，即所有的网络路由器都处于同一级之内的网络，一般称之为平面网络路由。

1 网络路由问题描述

通常用有向图G=(V，E)表示网络模型［8］，有向图中V 是指节点的集合，E 是指边的集合，每条边是相邻2 节点间的信息交换路径。一般情况下，假定任意2 相邻节点间的边数最多只有一条。此外，设B(l)是网络链路的实际带宽，针对某个网络路由请求w，当能够找出不止一条费用较小的路径，而且满足下面几个条件时，就接受该网络路由请求w。

对于网络路由请求w，每条路径l 的可用带宽都被限制为:

B(l)≥Bw(1)

对于网络路由请求w，点到点的网络延迟被限制为:

对于网络路由请求w，点到点的网络丢失率被限制为:

在本文中，研究的对象是那些因为网络节点缓存器溢出所导致的数据包丢失。

对于网络中的目的节点，点到点的网络延迟抖动被限制为:

在式(1)～式(4)中，Bw表示网络带宽限制;Dw表示网络延迟限制;Lw表示网络丢失率限制;Jw表示网络延迟抖动限制;DN 表示网络节点处理延迟，且DN:V→R+;DL 表示网络链路延迟，且DL:E→R+;V1表示网络路由请求w 的节点集合;E1表示网络路由请求w 的路径集合;LR 表示网络节点丢失率，且LR:V→R+∪{ 0} ;DNV 表示网络目的节点的延迟变化，且DNV:V→R+∪{ 0}，其中R+表示正实数集。

2 平面QoS 蚁群路由算法设计

自适应蚁群算法的信息素更新策略对算法的整体性能有很重要的影响。K.C.Abbaspour［9］等曾提出，在蚁群算法实际运行之前进行一个预处理阶段，该阶段开始并不使用信息素，通过预处理找出一定数量的路径，然后再从其中找出部分路径，并在算法开始前对信息素进行初始化，这样可以获得比较好的效果。但是目前对该方面的研究相对比较少，所以信息素更新策略值得深入的研究。而本文就是通过对信息素更新策略的改进设计了一种平面QoS 蚁群路由算法。

假设在平面QoS 蚁群路由算法中蚂蚁的个数是m，并且本算法采用的信息素更新策略［10］是全局和局部相结合的复合更新策略。另外，本算法采用以下的状态转移策略:

现假定第i 只蚂蚁在节点r 上，那么它将根据以下策略来选择下一个节点s:

当q ≤q0时，则:

否则:

采用以上状态转移策略，蚂蚁找到的路径常常是局部最优路径。

1)局部信息素更新策略。

如果蚂蚁i 选择的2 个节点(r，s)在它行走的路径中是相邻的，那么此时的信息素变为phe(i，r，s)，见公式(7);如果2 个节点不相邻，那么信息素就不用更新。

其中α0是一个常数。

如果信息素没有得到局部的更新，那么所有蚂蚁将根据历史最优路径在其邻近域内进行下一步搜寻。

2)全局信息素更新策略。

如果蚂蚁i 选择的2 个节点(r，s)在它行走的路径中是相邻的，那么此时的信息素则根据式(8)进行更新;如果2 个节点不相邻，那么信息素则根据式(9)进行更新。

其中α1是一个常数。

对公式(8)中的限制函数F 进行定义，当节点r位于蚂蚁i 所选择行走的路径中时，，否则0;当边(r，s)位于蚂蚁i 所选择行走的路径中时，=1，否则;假定LBrs、LCrs和LDrs表示的含义分别是蚂蚁行走路径中边(r，s)的可用带宽、费用和网络延迟，NDr表示节点r 的处理延迟，NLr表示节点r的网络丢失率。此时，限制函数F 可以表示为:

在式(11)～式(16)中，V 是网络节点的个数;A是可用带宽限制;B 是点到点的延迟限制;C 是点到点的网络丢失率限制;F1是费用可用限制;F2是QoS限制，并且它们都是正实数。

根据以上对限制函数的定义可知，当蚂蚁所选路径的总体费用最小，且QoS 的延迟限制也符合相应要求时，最优路由中的各条路径上的信息素的增加值会更大。由于本算法的收敛性还有待提高，所以笔者在这方面做了改进:

1)在迭代过程中，对网络延迟抖动所带来的影响不予考虑，并且在执行算法之前对其做相应预处理;

2)对实际网络进行简化处理，比如删除部分带宽比较小的链路，从而形成一个新的简化网络，所以令F 函数中的A=0。

该算法的详细步骤如下:

1)当DNV(d)＞Jw时，算法结束;否则，转执行第2)步。

2)对实际网络进行简化处理，删除部分带宽比较小的链路，从而形成一个简化网络。

3)对网络结构中每一条链路边的信息素进行初始化赋值。

4)起初安排一定数量的蚂蚁去觅食，假设蚂蚁初始数量为m。在首个单位时间内，每一只蚂蚁在网络节点集合内随机挑选某个节点作为下一节点，然后每只蚂蚁根据状态转移策略对自己的路径进行选择。在选择路径的过程中，当蚂蚁在觅食途中死亡时，则用另外一只同样类型的蚂蚁来代替此蚂蚁，并对从起始节点到目的节点的路径重新进行选择。如果某一只蚂蚁挑选出一条到目的节点的完整路由，则根据局部信息素更新策略对此路由中的信息素进行相应更新。

5)对第4)步执行m 次，直到所有蚂蚁都对各自信息素进行了相应更新。

6)对所有蚂蚁选择出的m 个路由进行挑选，选择出满足QoS 限制而且费用最小的路由，然后根据全局信息素更新策略对该路由中所有路径上的信息素进行相应更新。

7)不断对第4)～6)这3 步骤进行重复执行，直到获得满足一定条件的路由方案。

根据以上设计的平面QoS 蚁群路由算法，本文设计了平面QoS 蚁群路由选择系统。该系统的具体工作流程表述如下，根据不同的具体问题设置相应的参数，并根据一定的初始化策略，确定蚂蚁的初始位置。然后蚂蚁可以不断地利用状态转移策略，寻找新路径。在寻找路径的同时，蚂蚁也通过局部信息素更新策略对已访问路径上的信息素浓度不断地进行修改。当所有蚂蚁都寻找到了它们的路径，则找出这些路径中的最优路径，并利用全局信息素更新策略再次修改该路径上的信息素浓度。这些状态转移策略可以使蚂蚁受信息素信息和启发信息的指导，向着信息素浓度更高的路径爬行。简言之，这些策略可以使更多的蚂蚁来选择更好的路径。平面QoS 蚁群路由选择系统具体的设计流程如图1 所示。

图1 平面QoS 蚁群路由选择系统设计流程图

本文利用TSP 问题对平面QoS 蚁群路由选择系统的性能进行了验证，从平均迭代次数、平均运行时间、平均最优解等几个方面对基本自适应蚁群算法、文献［11］和文献［12］的算法与本文改进后的平面QoS 蚁群算法进行比较。最后在MATLAB 进行仿真实验，结果如表1 所示。

表1 TSP 问题各算法性能比较表

由表1 可知，改进后的平面QoS 蚁群算法的平均运行时间与其他算法相比明显都要短，也就是说它具有很强的收敛性;另外，与基本的自适应蚁群算法相比，改进后的平面QoS 蚁群算法的平均迭代次数有明显减少。改进后的算法能够在保持较低的平均迭代次数和较短的平均运行时间的同时，也可以得到和其他算法几乎相同的平均最优解。综上可知，改进后的平面QoS 蚁群算法拥有比一般自适应蚁群算法更好的实际运行性能。

3 路由性能分析

实际网络拓扑［13］如图2 所示，网络节点用点〈ndl，lr，dv〉表示，ndl 代表节点网络延迟，lr 代表节点丢失率，dv 代表节点延迟变化。网络链路用边〈cost，bw，ldl〉表示，cost 代表费用，bw 代表带宽，ldl 代表链路延迟。

图2 网络的拓扑及其参数

假定有3 个单播路由请求［14］(1，6)、(2，6)和(3，8)，它们的Bw=70，要求是:Dw=8，Lw=10-5，现对图2 中的实际网络拓扑结构进行简化处理，如图3所示。

图3 简化网络及其参数

设置m=20，∂0=0.075，∂1=0.085，cons=0.28，q0=0.92，A=0，B=15，C=30，信息素τ=150。在MATLAB 上对平面QoS 蚁群路由算法进行仿真实验［15］，最终结果如表2 所示，本次实验的平均迭代次数只有105 次。

表2 平面QoS 蚁群路由算法的仿真实验结果

最后对表2 中的路由请求额外进行了1 000 次的实验仿真，结果发现其中有913 次可以找到表2 相应路由，87 次可以找到比较优的路由，没有找不到路由的情况。综上可知，改进后的平面QoS 蚁群路由算法可以很好地完成路由寻优任务。

4 结束语

本文在自适应蚁群算法的基础上，对信息素更新策略进行了改进，采用局部与全局信息素更新策略相结合的方法，形成平面QoS 蚁群路由算法。为了提高收敛性，还对该路由算法进行一定的改进，最后将其成功应用于网络路由问题，并通过仿真实验验证了它的性能。仿真实验结果表明，改进后的平面QoS蚁群路由算法在求解比较复杂的网络路由问题时具有很强的优越性，不仅迭代次数少而且还具有较高的最优解几率。可以很好地解决平面QoS 网络路由问题，是一种有效的快速路由选择方案。

［1］孔宇彦，姚金涛，张明武.Ad Hoc 网络基于寿命估算MMAS 的QoS 组播路由优化算法［J］.小型微型计算机系统，2015，36(1):44-48.

［2］葛连升，江林，秦丰林.QoS 组播路由算法研究综述［J］.山东大学学报(理学版)，2010，45(1):55-65.

［3］Wang Zheng，Crowcroft J.Quality-of-service routing for supporting multimedia applications［J］.IEEE Journal on Selected Areas in Communications，1996，14(7):1228-1234.

［4］张素兵，吕国英，刘泽民，等.基于蚂蚁算法的QoS 路由调度方法［J］.电路与系统学报，2000，5(1):1-5.

［5］贾云富，秦勇，段富，等.蚁群算法及其在路由优化中的应用综述［J］.计算机工程与设计，2009，30(19):4487-4491.

［6］郑慧君，张巍，滕少华.基于改进蚁群的无线传感器网络路由［J］.计算机应用研究，2010，27(1):99-100.

［7］王子君，赵卫国，王利英，等.基于人工免疫-蚁群算法的平面QoS 路由模型［J］.河北工程大学学报(自然科学版)，2007，24(3):76-79.

［8］胡小兵，黄席樾，张著洪.一种新的自适应蚁群算法及其应用［J］.计算机仿真，2004，21(6):108-111.

［9］Abbaspour K C，Schulin R，Genuchten M T.Estimating unsaturated soil hydraulic parameters using ant colony optimization［J］.Advance in Water Resources，2001，24(8):827-841.

［10］颜晨阳，张友鹏，熊伟清.一种新的蚁群优化算法信息素更新策略［J］.计算机应用研究，2007，24(7):86-88.

［11］赖智铭，郭躬德.基于自适应阈值蚁群算法的路径规划算法［J］.计算机系统应用，2014，23(2):113-118.

［12］邵创创，董尚阳.一种自适应蚁群算法的研究及仿真［J］.中国科技博览，2013(28):488-488.

［13］顾军华.基于蚂蚁算法的QoS 组播路由问题求解［J］.河北工业大学学报，2002，31(4):19-24.

［14］向虹佼，吕光宏，明丽洪.基于蚁群系统的QoS 单播路由算法［J］.电子科技，2014，27(1):53-56.

［15］陈冰梅，樊晓平，周志明，等.求解旅行商问题的Matlab蚁群仿真研究［J］.计算机测量与控制，2011，19(4):990-992.