蚁群算法在网络路由中的应用

彭歆筠

（长江大学 计算机科学学院,湖北 荆州 434023）

1 现状

动物界的智能行为一直都是科学家灵感的源泉，近年来，群居的昆虫表现出来的集体智能吸引了研究者的注意。科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但是它们却可以解决许多复杂的问题。蚁群算法就是利用群集智能解决组合优化问题的典型例子。蚁群算法是由意大利学着Dorigo等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式随机搜索算法，蚁群算法具有并行性，鲁棒性，正反馈性等特点，蚁群算法最早成功应用于解决著名的旅行商问题（TSP）、车间任务调度问题（JSP）、网络路由等许多复杂的组合优化问题。

生态学家发现蚂蚁在寻找食物时总是可以找到食物源到巢穴之间的最短路径，这是因为蚂蚁在搜寻食物源的时候，能在其走过的路径上释放一种蚂蚁特有的信息素，可以将信息传递给其它蚂蚁并影响其对路径的选择。当蚂蚁碰到一个还没有走过的路口时就随机地挑选一条路径前行，并释放与路径有关的信息素，通常蚂蚁会以较大概率选择信息素浓度高的路径，并加强该路径的信息素浓度，而其它路径张的信息素浓度就会随时间衰减，最终蚂蚁能找到一条从食物源到巢穴的最短路径。

2 蚁群算法与QoS路由

网络路由方面的研究主要通过两个途径来提高服务质量（quality of service,QoS）:一条途径是节点控制；另一条途径是整个网络或局部网络控制。节点控制在单节点或单链路完成，主要控制业务对单节点共享资源的占用；整个网络或局部网络控制通常通过对路由与信令的控制达到对业务流和业务连接在网络中传输的直接控制。因为路由直接关系到网络性能，所以QoS路由成为解决QoS问题的核心技术之一，也是当今网络技术领域内的一个研究热点。

QoS路由的任务就是在网络中寻找一条路径，使其能满足带宽、时延、时延抖动和费用的限制。上述问题可以利用蚁群算法来解决。

（1）问题描述，可将网络模型表示为一个有向图G=（V,E）,其中V是图中所有交换节点组成的集合，E是图中所有边的集合，每一条边表示相邻两节点间的直达通信路径。一般的，假定相邻两节点间最多仅有一条边。同时，假定B(l)表示链路l的可用带宽，对于一个路由请求,路由算法如果能够找到一条具有小费用的路径，同时满足如下4个条件，则此路由请求W就可接受。

①在W的路由的每条路径l上，带宽可用限制为

②在w的路由上，端到端时延限制为

③在w的路由上，端到端丢失率限制为

这里只考虑由于节点缓存器溢出引起的丢失。

④在目的节点，端到端时延抖动限制为

式中，Bw、Dw、Lw、Jw分别表示 QoS 要求的带宽，时延、丢失率和时延抖动限制；DN表示节点处理时延，DN:V→R+；DL表示链路时延，且DL:E→R+；V1表示ω路由的节点集合；E1表示ω的路由链路LR是节点丢失率，且DV表示在目的节点d的节点时延变化其中R+是正实数集合。

（2）算法设计。假设平面QoS蚁群路由算法中有m只蚂蚁，并且采用了全局和局部信息素更新规则。①状态转移规则。位于节点r的第i只蚂蚁依据下述规则来选择节点s;如果有，q≤q0，有

否则，有

采用此定义来实现蚂蚁状态的转移可保证寻找优化路径时避免陷入局部最优解。

② 信息素的局部更新规则，对于第i只蚂蚁，如果节点r,s是该蚂蚁所选路径上的两个相邻节点，则信息素pheromone（i，r，s）用公式（7）来调节；否则，不调节。

若没有局部更新，所有蚂蚁将在前一次的最好路径的有限相邻区域内搜寻。

③信息素的全局更新规则，对于第i只蚂蚁，如果节点r,s是该蚂蚁所选路径上的两个相邻节点，则信息素pheromone（i，r，s）按公式（8）

否则，按公式（9）调节

为了定义公式（8）中的限制函数F,首先引入几个符号定义：如果节点r是第i只蚂蚁所选路由的节点，则Nri=1，否则Nri=0；如果从节点r到节点s的边是第i只蚂蚁所选路由的边，则 Prsi=1 否则 Prsi=0；LBrs、LCrs、和 LDrs分别表示从节点 r到节点s的边的带宽、费用和时延；NDr和NLr分别表示节点r的处理时延和丢失率。由此，可将限制函数F定义为

如果 Z<0,H(Z)=0；否则，H(Z)=Z0

式中，V表示网络的节点数目；A、B、C分别表示带宽可用限制、端到端时延限制和端到端丢失率限制，且为正实数；F1表示费用限制；F2表示QoS限制。

根据上述的定义，如果所选路由的总费用小，同时QoS限制也满足要求，那么最优蚂蚁所选路由的各链路上的信息素应该增加更多。为了进一步提高算法的收敛性能，这里做了以下两点改进：①在蚁群算法迭代中不考虑时延抖动，而是在算法执行前进行处理；②通过删除带宽小于需求带宽的链路，把网络过滤成一个新的简单网络，因此在F函数中设A=0。

QoS蚂蚁路由算法的具体步骤如下：①如果NDV(d)>Jw，那么退出；否则，跳转到第（2）步。②通过删除带宽小于需求带宽的链路，把网络滤成一个新的简单网络。③初始化网络拓扑中各边的相应信息素。④从蚁巢开始放出m只蚂蚁去寻找食物源，在第一个时间单位，每只蚂蚁从节点集合中随机地选择一个节点，然后各蚂蚁通过重复应用状态转移规则来选择各自的路径。在选路径的过程中，如果蚂蚁在到达目的节点前就死亡，另外一只和死亡的蚂蚁的同类的蚂蚁重新放出来代替死亡的蚂蚁，重新开始选择从源节点到目的节点的路径。当某只蚂蚁成功地完成路由选择后，该蚂蚁所选路由各路径上的信息素根据局部更新规则进行更新。⑤对所有的蚂蚁重复第（4）步，直到m只蚂蚁都完成了第（4）步。⑥选择建立了最小费用并满足QoS限制的路由的蚂蚁，然后使用全局更新规则对该蚂蚁所选的路由的各路径上的信息素进行更新。⑦重复第（4）（6）步，直到获得满意的结果。

3 结语

蚁群算法问世至今已有近二十年的时间，从最初的最短路径问题，逐步发展为一个优化工具。蚁群算法具有很强的发现最优解的能力，该算法不仅利用了正反馈原理，而且是一种本质并行的算法，不同个体之间不断进行信息交流和传递实现协作。

蚁群算法在网络方面的应用尤为重要，本文介绍了蚁群算法在平面网络QoS路由中的应用，分析了算法设计和执行的过程。从带宽、时延、时延抖动和费用等关键因素出发，结合蚁群算法的状态转移规则、信息素局部更新规则、信息素全局更新规则来分析QoS路由问题。根据蚁群算法的思想在网络中寻找一条最优路径，实现网络传输的快速、准确，直接提高网络性能。在进行路由运算时，就可以减少大量的运算和运算时间。同时，蚁群在工业控制和生命科学等若干领域也有典型应用，从目前的应用情况来看，蚁群算法在智能优化应用领域具有极强的适应性和生命力。

[1]李世勇.蚁群优化算法及其应用研究进展[J].计算机测量与控制，2003，(12).

[2]姜长园.蚁群算法的理论及应用[J].计算机时代，2004，(6).

[3]赵天男,王晓红.蚁群算法及其应用研究[J].软件导刊，2010，(6).

[4]张学敏,张航.基于改进蚁群算法的最短路径问题研究[J].自动化技术与应用，2009，(6).

[5]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.

[6]李世勇.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.