具有个体记忆的蚁群算法与网络QoS路由研究* 1

王文国，刘　洋

(曲阜师范大学 信息科学与工程学院，山东 日照 276826)



具有个体记忆的蚁群算法与网络QoS路由研究* 1

王文国，刘洋

(曲阜师范大学 信息科学与工程学院，山东 日照 276826)

摘要：QoS路由算法的目的是在网络中找到满足一定带宽、延时、延时抖动和丢包率等约束要求的路由，该问题是NPC问题。受自然蚂蚁启发，假设人工蚂蚁具有短期记忆能力，使其选择路径时可把最近迭代搜索到的解与自己过去搜索的最优最差解进行比较，动态调整其路径选择过程。蚁群信息素的变化则采用较优解路径更新策略，以加快算法的收敛。蚂蚁将根据搜索到解的情况，判断是否陷入局部最优，若是则改变路径信息素量上下限的大小，使算法跳出局部最优。仿真实验证明，改进的蚁群算法在解决QoS路由选择问题时，能够获得比基本蚁群算法与最大-最小蚂蚁系统更优搜索性能。

关键词：蚁群算法;QoS路由选择;蚂蚁个体记忆;动态选择

0引言

随着计算机网络的发展，传统尽力而为的服务已不能满足各种网络业务的需求。特别是网络中多媒体的应用对带宽、延时、延时抖动、丢包率等参数提出了严格要求[1]。网络服务质量(QoS)就是提供用户能够满足业务需求的、一致的、可预计的数据交付服务。网络服务质量路由(QoSR)算法目的是在网络中搜索最佳路由，该路由满足带宽、延时、延时抖动、丢包率等条件。由于包含两个或两个以上不相关可加或可乘性参数的路由选择问题是NPC问题[2]，传统路由算法无法在有效时间内找到最优解，因而启发式搜索算法成为解决多约束QoS路由问题的有效途径[2-5]。

作为解决NPC问题的有效方法之一，人工蚁群算法可以用于优化QoS路由选择问题[3]。作为一种分布式算法，该算法通过蚂蚁之间的相互协作来寻求最优解，并通过蚂蚁释放的信息素作为蚂蚁之间交流的媒介。蚂蚁释放信息素的量与它搜索到解的质量有关：搜索到解的质量优，则释放的信息素量多；反之则少。蚁群算法还具有并行性、鲁棒性，易与其他算法相结合等优点，但也存在收敛速度慢，易停滞于局部最优解的缺点。该算法具有正反馈性，搜索到较优解蚂蚁释放的信息素量多，这对后来的蚂蚁搜索起到了导向作用。蚁群算法初期之所以收敛慢是由于在迭代初期，各路径信息素量少并且信息素的分布不能体现解的优劣程度，此时算法的正反馈较弱，需要经过一段时间的迭代搜索，各路径信息素的差别才能体现出来。易收敛于局部最优也是由于蚁群算法的正反馈性，导致某些路径上信息素的量过大，蚂蚁在以后的路径选择中失去了多样性。目前已有多种人工蚁群算法的改进版本：如文献[4]采用遗传算法初期收敛快的特点，用收敛初期形成的较优解来初始化算法初期路径上信息素的量，算法后期利用蚁群算法的正反馈性来求解最优，加快算法的收敛速度。文献[5]通过路上经过的蚂蚁数量的聚度来动态调整路径选择的概率范围，调和算法的收敛速度与搜索的广度。文献[6]采用多个种群的蚂蚁同时运行，采用路径信息素的熵作为种群中蚁群算法进行程度的量，对不同进化程度的种群进行交流来克服单一蚁群算法出现的进化停滞现象。文献[7]将两个路径的相似度作为一种参数，算法的运行过程中，使算法朝着与全局最优解路径相似度高的方向进化，提高了搜索到解的质量。文献[8]采用粒子群算法来确定蚁群算法的参数，从而使蚁群算法获得较好的性能。

在本文改进的蚁群算法中，蚂蚁的状态转移规则不仅依赖于路径信息素量的外部环境，而且与蚂蚁自身的搜索状态有关。每只蚂蚁能够保存自己搜索到的最优解与最差解。蚂蚁在接下来的路径选择中，将根据自己的搜索状态与外界信息素的因素自主决定边的选择策略，克服蚂蚁因面对同一环境信息而造成的选择性单一，从而缓解蚁群算法的停滞现象。在信息素更新方面，只更新本轮迭代中较佳状态的蚂蚁搜索到解的各条边上的信息素量与本轮循环最优解的各条边上的信息素量。

1基本蚁群算法模型

蚁群算法利用蚂蚁之间的交流来寻找最优解。蚁群算法中单个蚂蚁并不具有智能性，而通过蚂蚁释放的信息素作为蚂蚁之间交流的媒介，促进蚂蚁之间的协作，使蚂蚁朝着最优解的方向进行搜索。算法本身主要包括路径选择部分与信息素的更新部分。

1.1路径选择公式

蚂蚁k在t时刻由i节点选择j节点的概率公式为：

(1)

(2)

式中，ηij(t)为期望值启发函数，其值为路径(i,j)距离的倒数。τij(t)为t时刻路径(i,j)上信息素的量，allowk为蚂蚁待选路径的集合，α为信息素启发因子，表示信息素在路径选择中所占的重要程度，β为期望值启发因子，表示期望值在路径选择中的重要程度。

1.2信息素更新公式

τij(t+1)=(1-ρ)*τij(t)+Δτij(t)

(3)

(4)

(5)

式中，ρ为信息素挥发系数，Δτij(t)为路径(i,j)信息素的增量，Q为信息素总量，Lk为蚂蚁k搜索解的适应度值。本文信息素的更新方式为蚂蚁进行遍历完成后进行更新，更新信息素量的大小反映了全局解的优劣。

路径选择公式表示解的构造过程，信息素更新公式体现了解的反馈信息。信息素更新公式决定了蚂蚁在此后的搜索过程中选择路径的情况，而路径选择公式决定了信息素需要更新的路径。这两个公式相互作用，形成了蚁群算法搜索解的过程。

2改进的蚁群算法模型

基本蚁群算法在构造解的过程中，更多的依赖于路径上信息素的量与期望启发函数。这些因素都是外部因素，任何一只蚂蚁在选择路径时，面对的外部环境都是一样的。由于蚁群算法的正反馈性，当路径上的信息素量越来越大时，蚂蚁在此后的选择过程中，失去了随机性，大量的蚂蚁会选择同一条路径，于是搜索到的路径解失去了多样性。此时算法容易陷入局部最优解。

本文假设每只蚂蚁能够保存自己搜索到的最优解与最差解。蚂蚁在接下来的路径选择中，将根据自己的搜索状态以及外界信息素分布情况综合决定路径的选择，从而克服蚂蚁因面对同一环境信息而造成的选择单一性，进一步缓解蚁群算法的停滞现象。

2.1路径选择公式

蚂蚁k在t+1轮搜索中，路径选择公式为：

(6)

(7)

μ1>10<μ2≤1λ≥1

(8)

(9)

(10)

2.2信息素更新公式

(12)

(13)

(14)

当蚂蚁走完所有的路径时，进行信息素的更新，Lk为蚂蚁k构造解路径的适应度值，本文中Lk越小越优。

本文采用最大最小蚂蚁系统[9]将路径上的信息素量设置在一定的范围之内。设信息素量的范围为[τmin,τmax]。当路径上的信息素更新完毕后，按照以下公式对路径上的信息素量进行调整。

(15)

蚂蚁k解的构造过程中，根据上轮迭代循环搜索到的解的适应度值与自己搜索到存储的值相对比。当上轮循环搜索到解优于自己搜索到的最优解，蚂蚁在本次循环状态转移时，只考虑边上信息素量的因素，即所有蚂蚁搜索的经验。若候选的节点属于自己搜索到最优路径的一部分，则加大选择此节点的概率；其他节点将减少被选择的概率。此时，每只蚂蚁搜索的范围将集中到自身搜索到的最优解附近。这样将搜索区域集中到某一区域，避免搜索区域过大而造成的无效搜索。

若蚂蚁上轮搜索到解差于蚂蚁自身己搜索到的最差解，在本次循环蚂蚁进行状态转移时，若候选边属于自己搜索到最差路径的一部分，将不选择该边；其他边按照信息素量与期望启发值乘积所占的比例进行概率搜索。

若蚂蚁上轮搜索到解处于自己搜索到最优解与最差解之间，蚂蚁状态转移公式按照基本蚁群算法的状态转移策略，此时蚂蚁会依靠信息素作为蚂蚁之间交流的中间桥梁进行搜索。

当所有的蚂蚁完成一次搜索后，进行信息素的更新。信息素的更新采用较优路径更新策略。较优路径包括两部分：(1)当前迭代最优解的路径；(2)蚂蚁在当前迭代搜索到解的路径比自己最优解更优的路径。路径(1)信息素的更新能够使局部最优路径信息素保留住，使以后蚂蚁的搜索方向集中于较优方向。路径(2)信息素的更新，能够使本次搜索成绩较好的蚂蚁之经验在群体之间进行交流，有利于在下一次的迭代搜索中发现更好的解。

设第t轮迭代搜索后得到的当前迭代最优解为Literbest(t)，第t轮迭代搜索完成时，算法已搜索到的最优解为Lgbest。若Literbest(t)

τmin=τmin*(1+θ1)

(16)

τmax=τmax*(1-θ2)

(17)

0<θ1<1 , 0<θ2<1

按照上述改进后的蚁群算法，蚂蚁在构造解的过程中，首先通过纵向比较，与自己的搜索到的最优最差解进行对比，动态地选择路径计算公式，以加强或减弱蚁群算法的正反馈性；然后通过与其它蚂蚁之间的横向交流，加强蚂蚁之间相互协作，使算法向着最优解方向进化。

3改进蚁群算法在QoS路由选择中的应用

3.1多约束QoS路由数学模型

计算机网络可以抽象成带权图G(V,E), 其中V为网络中节点(路由器，交换机)的集合，E为网络中链路的集合。不失一般性，设该图为无向图。图中的每个节点的属性为：代价，延时，延时抖动，丢包率；链路的属性为：代价，带宽，延时，延时抖动。设网络中的源节点为s, 目的节点为d，s∈V，d∈V。定义源节点s到目的节点d的代价、延时、延时抖动、丢包率，带宽属性如下：

代价：

延时：

延时抖动：

带宽：

BandWidth(R(s,d))=min{BandWidth(e),e∈R(s,d)}

其中n为节点，e为链路。

QoS路由选择问题如下：以s为源节点，d为目的节点。在网络中找到一条路由R(s,d)，使之满足以下条件：

其中D，Dj，Pl，B为保障服务质量所需的延时，延时抖动，丢包率，带宽要求。QoS路径选择问题即在保障服务质量要求下，所求路由的代价最小。

3.2改进蚁群算法在QoS路由选择中的应用

将m只蚂蚁放于网络中的源节点s，各只蚂蚁按照各自的寻路公式进行选择路径，直到找到目的节点d。设蚂蚁k找到的一条路由为Routek，该路由的使用度函数值为Lk，Lk定义如下：

Lk=Cost(Routek)*{φD(Delay(Routek))*

φDj(Delay_jitter(Routek))*φPl(Pl(Routek))}

(18)

(19)

(20)

(21)

其中rd,rdj,rpl,分别为惩罚系数，rd>1，rdj>1,rpl>1。适应度函数使用惩罚函数，对不符合服务质量要求的解路由，其适应度值加大，以形成劣质解。

算法过程如下：

第二步： 将m只蚂蚁放在源节点s，t=t+1,设置蚂蚁序号k=1。

第三步 蚂蚁k按照上次搜到的解，选择合适的路径选择公式，选择下一节点j。

若j=d，则k=k+1，蚂蚁k本次搜索完毕，转向第三步。

若j≠d且j∉φ，则蚂蚁k继续搜索，转向第三步。

若j≠d且j∈φ，蚂蚁k无法选择下一路径，本次搜索无效，将蚂蚁放在源节点s，转向第三步。

第五步：更新本次迭代路径上信息素的量，根据式(15)调整路径信息素量。

第六步：根据Literbest(t)，Lgbest判断算法是否陷入局部最优。若陷入局部最优，根据式(16)，式(17)调整τmin，τmax。转向第二步。

第七步：若t=Nc，则输出最优值，算法结束。

4仿真实验分析

仿真实验平台采用MatLab7.8, 采用改进的Salam网络拓扑随机生成算法，生成网络拓扑见图1。

图1　网络拓扑

网络中各参数设置如下：节点数量N=40, 网络中各节点的参数范围如表1所示。

表1　参数取值范围

设仿真实验参数如下：蚂蚁数量m=20，α=1，β=2，ρ=0.1，Q=10，τmin=0.01，τmax=1，μ1=2，μ2=0.4，λ=2，θ1=0.01，θ2=0.01，迭代最大次数Nc=200。网络服务质量各参数[B,D,Dj,Pl]要求为[40 Mb/s,100 ms,40 ms,10e-3]。以下对5个路由请求进行仿真实验，分别采用基本蚁群算法，最大-最小蚁群算法，本文改进的蚁群算法进行实验，每个实验运行200次，相关实验结果总结在表2、表3、表4中。

表2　基本蚁群算法实验结果

表3　最大-最小蚁群算法实验结果

表4　本文改进的蚁群算法实验结果

由表2，表3，表4可以看出，基本蚁群算法，最大-最小蚁群算法，本文改进蚁群算法都能取得最优解。本文改进蚁群算法多次实验所求解方差比基本蚁群算法与最大-最小蚁群算法小，说明改进算法比基本蚁群算法与最大-最小蚁群算法稳定，每次实验所求解的差别不大。改进蚁群算法所求最优解的比率比基本蚁群算法高，并且所求解的平均值比基本蚁群算法优，说明我们改进的蚁群算法寻优性能好于基本蚁群算法。通过改进的蚁群算法与最大-最小蚁群算法的实验结果做对比，改进蚁群算法搜索性能优于最大-最小蚁群算法。

以路由请求，源节点s=4，目的节点d=33, 服务质量约束要求如上实验为例，分别运行以上三种算法，得到的最优代价进化曲线图如图2所示。

图2　三种算法最优解进化曲线

由三种算法最优代价进化曲线可以看出，基本蚁群算法陷入了局部最优解，改进蚁群算法与最大-最小蚁群算法收敛到全局最优解。由于改进蚁群算法在运行过程中路径信息素上下限会改变，导致其收敛速度稍慢于最大-最小蚁群算法。

5结语

本文提出了一种改进的蚁群算法，使蚂蚁在构造解的过程中，将路径上的信息素，期望值等外部因素与自身的搜索状态相结合：上次迭代循环搜索状态佳的蚂蚁在本次搜索选择转移的边时，将在自己搜索到的最优解附近进行搜索，力图获取更优的解；上次迭代搜索状态差的蚂蚁在本次搜索路径选择时，将避开自己搜索到的最差解，提高蚂蚁在当前迭代循环中搜索到解的质量。仿真实验表明具有个体记忆的蚁群算法能够获得比最大-最小蚂蚁系统与基本蚁群算法更优的搜索性能。

参考文献：

[1]Crawley E, Nair R, Rajagopalan B and Sandiek H. A Frameework for QoS-based Routing in the Internet[S], RFC no.2386, Internet RFC, Aug.1998.

[2]WANG Z, Crowcroft J. Quality-of-Service for Routing Supporting Multimedia Applications[J]. IEEE Journal of Selected Areas in Communications, 1996;14(7):1228-1234.

[3]刘洋,王文国. 差异化密集蚁群算法与网络QoS路由选择[J]. 通信技术，2015,48(08)：949-953.

LIU Yang, WANG Wen-guo. Differentiated Dense Ant Colony Algorithm and Network QoS Routing Selection[J].Communications Technology, 2015, 48(08): 949-953.

[4]杨原. 基于群智能优化算法的QoS组播路由算法研究[D]. 西安：西安科技大学，2014.

YANG Yuan. Research on QoS Multicast Routing Algorithm based on Swarm Intelligence Optimization Algorithm[D]. Xi′an: Xi′an University of Science and Technology, 2014.

[5]陈峻,沈洁,秦玲等. 基于分布均匀度的自适应蚁群算法[J]. 软件学报, 2003,14(08):1379-1387.CHEN Ling, SHEN Jie, QIN Ling, et al. An Adaptive Ant Colony Algorithm based on Equilibrium of Distribution[J]. Journal of Software,2003,14(08):1379-1387.

[6]邓可,林杰,张鹏. 基于信息熵的异类多种群蚁群算法[J]. 计算机工程与应用, 2008,44(36):16-19.

DENG Ke, LIN Jie, ZHANG Peng. Multiple Heterogeneous Ant Colonies Algorithm based on Information Entropy[J].Computer Engineering and Applications, 2008, 44(36):16-19.

[7]张鹏,林杰,邓可.一种基于路径相似度的蚁群算法[J]. 计算机工程与应用，2007,43(32):28-33.

ZHANG Peng, LIN Jie, DENG Ke. Ant Colony Algorithm based on Similarity of Paths[J].Computer Engineering and Application,2007,43(32):28-33.

[8]姜秋霞. 混合蚁群算法及其应用研究[D]. 上海：同济大学，2008.

JIANG Qiu-Xia. Research on Hybrid Ant Colony Algorithm and Its Application[D]. Shanghai: Tongji University,2008.

[9]Stutzle T, HH Hoos. MAX-MIN Ant System[J]. Future Gener. Comput. Syst, 2001,16(8):889-914.

Ant Colony Algorithm with Individual Memory and Its Application in QoS Routing

WANG Wen-guo, LIU Yang

(Dept. of Info. Science & Engineering, Qufu Normal University, Rizhao Shandong 276826, China)

Abstract：QoS routing aims to find a route satisfying restraint requirements of bandwidth, delay, delay jitter, and packet-loss rate in modern network. Artificial ant colony algorithm is one of the effective methods to solve QoS routing problems. Similar to real ants in nature, artificial ants with short term memory could compare current search result with its best/worst paths in the past, and then adjust its selection behavior dynamically. Simulation with Matlab indicates that the modified ant colony algorithm could acquire better searching performances as compared to the basic ant colony algorithm and max-min ant system.

Key words：ant colony algorithm; QoS routing; individual memory; dynamic selection

doi:10.3969/j.issn.1002-0802.2016.05.011

* 收稿日期：2015-12-20；修回日期：2016-04-02Received date:2015-12-20；Revised date：2016-04-02

基金项目：国家人事部高层次留学人员回国工作资助项目(No.200461)

Foundation Item：National High Level Talents Attracting Program of China(No.200461)

中图分类号：TP311

文献标志码：A

文章编号：1002-0802(2016)05-0563-06

作者简介：

王文国(1960—)，男，博士，教授，主要研究方向为网络与信息安全;

刘洋(1981—) 男，硕士，主要研究方向为计算机网络。