基于蚁群算法的网络负载均衡的研究与实现

引言

蚁群算法(AntColonyOptimization,ACO)是模拟蚁群寻找食物的一种生物启发式算法⑴，通过研究图论来寻找优化路径。针对网络资源管理中路径负载、路由选择、集群并行计算等研究课题，将网络流量工程与蚁群算法相结合,提出基于蚁群算法的网络流量负载均衡和路由选择优化的新方法。

流量负载均衡与路由选择优化，一直都是网络资源优化研究中的重要课题⑵；云网络集群和分布式并行计算，是当前网络发展和研究的前沿课题。本文研究的目标就是把海量服务请求合理地分配到现有网络资源，避免网络拥塞瓶颈，提高网络服务质量(QoS)。网络流量的负载均衡如图1所示。

1  蚁群算法概述

1.1  蚁群算法

蚁群算法是继模拟退火算法、基因遗传算法、禁忌搜索算法、人工神经网络算法之后的又一种搜索算法,主要应用于复杂组合问题的搜索优化其。该算法具有智能搜索、正反馈、全局优化、快速求解，以及稳健性、分布式计算、易于与其它算法结合等优点。

1.2  算法基本原理

蚁群算法是通过蚁群间信息素的动态交互(即蚁群内信息素相互增强，蚁群间信息素相互减弱)来建立数学模型，模拟蚁群寻找食物的一种搜索算法。

蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却极其复杂。一群蚂蚁通过彼此之间的相互协作，能够很容易从蚁巢出发去找到食物源，并且所经过的路径最短。人们通过大量的研究发现，蚂蚁个体之间是通过在其走过的路径上留下一种可称之为“信息素(Pheromone)w的物质来进行信息传递。后到的蚂蚁遇到信息素时，检测出该物质存在量的多少，并且根据信息素的浓度来指引自己前进的方向。同时，随着时间的推移，信息素会逐渐消减，路径的长短和路径上蚂蚁的多少对路径上残余信息素的强度产生影响，反过来信息素的强弱又指引其它蚂蚁前进的方向。因此，路径上走过的蚂蚁越多，则后来蚂蚁选择

该路径的概率越大，这就构成了蚂蚁群体行为表现出的一种信息正反馈机制蚂蚁个体间就是通过这种信息交流来快速搜索到食物源。

图1    网络流量的负载均衡

蚁群从蚁巢到达食物源的过程中,外界环境是不断变化的，如信息素的浓度、障碍物等。蚂蚁觅食过程中释放的信息素具有三点特性：

首先是具有挥发性，随着时间的流逝，路径上的信息素会逐渐减弱。

其次是具有随机性，对下一步路径的选择是随机的。

另外，就是具有启发性,路径上的信息素越多，被选中的概率就越高。

1.3   蚁群算法的数学模型

为了模拟蚂蚁的行为，以求解N个城市的旅行商问题(TravelingSalesmanProblem,TSP)为例。已知有N个城市，寻找一条访问两个城市之间的最短路径。设蚁群中蚂蚁数量为m,城市/和j之间的路径

式中，蚂蚁总数m等于N个城市在t时刻蚂蚁数量BiCt)之和。

Ttj(t)表示t时刻在i〜j路径&顼残留的信息量。初始时刻，在各条路径上的信息量相等，设乌(0)=C(C为常数，初始化时通常取为0)。蚂蚁Kfe=1,2,…)在运动过程中，根据各路径上的信息量浓度大小决定转移方向，t时刻蚂蚁&由位置/转移到j的概率P$(t)：

式中，rejected；.={k}表示蚂蚁k已经走过，下一步不会途经的城市集合，即禁忌表;allowed*={N—k}表示蚂蚁方还没有走过,下一步可能会途径的城市集合，即候选表-rejectedjs)表示禁忌表中的第s个元素；乌(t)表示蚂蚁后在t时刻在城市i到j的路径上捕获的信息素强度，其大小可由路径上残留的信息素、当前蚂蚁k释放的信息素和信息素本身挥发剩余量综合确定;入”1)表示蚂蚁后在t时刻由城市/到j的期望程度(亦称可见度)，其值可根据某种启发式算法确定。当相。)>0时，表示邻域，处的蚂蚁京在t时刻按概率P§(t)移至邻域j的可能性；当Ai;(t)<0时，邻域/处的蚂蚁及做邻域搜索,其搜索半径为r(此值可由实验得出)；a,/3分别表示蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用，它们是控制信息素强度与可见度相对重要性的参数。可见，转移概率是期望程度(即可见度)和信息素强度的综合权衡的结果。

人工蚁群系统与真实蚂蚁系统不同，为了使人工蚁群系统更加智能与高效，还需使其具有一定的记忆功能，用rejected*O=1,2,…)记录蚂蚁k目前已途经过的城市。但是随着时间的慢慢推移，先前释放留下的信息素浓度会逐渐挥发消逝。设信息素浓度的保留系数为p(0<p<1)，它体现了信息素强度的频繁性和持久性;而1—p表示信息素的消逝程度。经过时间间隔，蚂蚁完成一次循环搜索，路径上信息素浓度可按下式计算：

式中，△在表示蚂蚁k在本次循环时间间隔内，在路径eg边上留下的新增信息素量;而爲"函)表示全部蚂蚁m={1,2,…}在本次循环时间间隔内，在路径边上留下的信息素浓度之和；q(t十△[)表示i-j路径上信息素浓度的总和，其中△者可表示为：

式中，n表示蚂蚁k在本次循环中所漫游的城市数目(n≤N)。

综上所述，式(1)〜式(6)中出现的a，B，p,Q等参数根据实际用途与领域，用试验的方法确定g(t),乌表达式可根据具体问题而定。由于上述过程是一个递推过程，易在计算机上编程实现,其停止条件可以用固定循环次数或者当进化趋势不明显时停止。

2  基于蚁群算法的网络负载均衡

2.1  数学建模的基本思想

通过模拟蚁群释放出的信息素这个纽带,可以抽象出表1所列的模型假设。

表1    蚁群算法的假设模型

2.2  蚁群算法的设计原理

假设各节点间的初始信息素强度都相等，将m只蚂蚁置于m个源节点。

初始时刻，m只蚂蚁位于加个源节点，N个节点的信息素强度相同。

每次循环前，检验是否满足终止条件。如果满足终止条件，则停止移动;如果不满足终止条件，则按照下列的转移规则进行移动。

在剩余未走过的节点集合中，随机选择一个路由节点,按照转移概率和转移规则进行移动，直到完成一次搜索结束。

转移到下一个节点后，如果此节点为目标节点，则显示访问成功,返回请求服务信息;如果此节点为源节点，则重新初始化,按步骤(3)进行。

按照信息调整规则，在本次搜索结束后，对各节点间的信息素进行更新调整，为下一次的转移做准备。

重复步骤(2),如满足终止条件，则终止搜索，标记显示搜索路径与搜索时间；如果不满足终止条件，则重复步骤(3)〜(5),直到满足终止条件为止*。

图2所示是根据蚁群算法设计的基本流程图。

2.3  基于蚁群算法实现负载均衡的编程设计

蚁群算法是对自然界蚂蚁觅食过程的抽象，通过建立数学模型，在电脑上模拟实现。事实上，每只蚂蚁并不需要知道整个世界的信息，它们只需要关心自身附近很小范围内的信息，根据捕获的局部信息，利用几条简单的规则进行判断与决策。这样，在蚁群这个集体里,复杂性的行为就会凸现出来，抽象成简单规则。蚁群算法的设计就是把复杂问题抽象成简单的数学模型,抽象设计遵循以下六条规则：

图2    蚁群算法的基本流程

2.3.1  搜索范围

蚂蚁观察的范围为一个抽象的方格世界,蚂蚁转移参数为速度半径(初始化为3),这样蚂蚁观察到的范围就是一个3X3的方格世界，转移到下一个路由节点的距离在这个范围之内。

2.3.2  环境变化

蚂蚁所在的环境在电脑模拟中是一个虚拟的世界,其中有障碍物、有别的蚂蚁、还有信息素。信息素有两种，一种是找到食物洒下的食物信息素，另一种是找到蚁巢后蚂蚁洒下的蚁巢信息素。每只蚂蚁都仅能感知它范围之内(3X3)的邻近区域。同时，随着时间的流逝，环境让信息素以一定的速率逐渐消减。

2.3.3  觅食规则

每只蚂蚁在能感知的范围内寻找是否有食物，如果有就直接过去;否则看路径上是否有信息素，比较哪一点的信息素强度最大，蚂蚁就朝哪个方向转移;同时蚂蚁也会以小概率犯错误，即并不是每次都理想地往信息素最多的节点移动。蚂蚁找窝的规则和上面一样，不同的是仅对窝的信息素做出反应，而对食物信息素没反应。

2.3.4  转移规则

蚂蚁都朝向信息素最多的方向转移，当周围没有信息素指引时，它会继续自己原来的轨迹，惯性地移动下去。同时，蚂蚁在运动的方向上也会有一个随机的小扰动。为了预防蚂蚁原地转圈，它会记住自己的历史轨迹，尽量避开已走过的节点，从而遍历新节点。

2.3.5  避障规则

如果蚂蚁要移动的方向有障碍物挡住，它会随机地选择一个其它方向，并且在信息素强弱的指引下做出智能判断和选择。

2.3.6  释放信息素规则

蚂蚁在刚找到食物或蚁巢时会散发更多的信息素,并随着它走远的距离，释放出的信息素会越来越少;随着时间的流逝，残留的信息素也会慢慢消失。

基于蚁群算法原理,在计算机上编程模拟实现：最大信息素:蚂蚁初始时拥有的信息素总量。

消失的速度：随着时间的流逝，路径上的信息素慢慢挥发、消减的速度。

错误概率：蚂蚁做出移动选择，不仅需要根据信息素强度的大小，而且自身也有一个随机的小扰动，错误概率越大，表示蚂蚁越有独立性与创新性。

速度半径：蚂蚁一次搜索过程中转移的最大距离，也就是蚂蚁能感知的最大范围。

记忆能力：记录蚂蚁刚刚走过的路由节点信息，这样能够避免蚂蚁原地转圈、避免重复。

初始时，蚂蚁从蚁巢出发，寻找食物，找到食物后再返回蚁巢，蚁群遇到路障后的转移规则如图3所示。

图3    蚂蚁遇到路障的转移规则

由图3可见，当无路障时，蚂蚁根据路径上信息素浓度和自身随机的移动规则，继续转移；

遇到单路障时，蚂蚁根据信息素浓度大小和随机选择综合确定，绕过路障继续转移。

而当遇到多个路障时，蚂蚁遵循单路障规则，然后绕过路障继续转移。

人工蚁群和自然界蚁群的相似之处在于,两者优先选择的都是含“信息素”浓度较大的路径，选择路径时会有一个小扰动，这样在较短的路径上会聚集较多的信息素。

2.4  基于蚁群算法实现负载均衡的编程设计流程图蚁群算法实现负载均衡的编程设计流程图如图4所示。

Start

图4    用蚁群算法实现负载均衡的程序流程图

3  实验结果与性能分析

3.1  单服务器下基于蚁群算法的网络路由选择基于蚁群算法的基本原理可用C语言在计算机上编程，以模拟网络环境。

图5所示是基于蚁群算法的单服务器下的网络路由选择方法，图5中的内容描述如表2所列。

表2    单服务器下的网络路由选择

图5(a)：开始1s时，蚁群都集中于蚁巢H及其附近区域，即将进行食物路径的遍历搜索。

图5(b)：14s后，正在进行路径遍历搜索，搜索

2012年/第2期物联网技术61\

达到食物目标节点的最优路径。

图5(c)：42s后，已经基本完成遍历搜索，并在全局范围内找到了最优路径。

图5    单服务器下的网络路由选择

上述实验结果表明，蚁群算法具有智能搜索、全局优化的特性，利用正反馈机制可以快速地寻找到最优路径。

3.2  多服务器下基于蚁群算法实现流量负载均衡

基于蚁群算法来实现多服务器的网络负载流量均衡的研究实验结果如图6所示。图中的内容描述如表3所列。

图6    多服务器下的流量负载均衡

表3    多服务器下的负载均衡选择

图6(a)：开始1s时，蚁群都集中于蚁巢H及其附近区域，即将进行食物路径的遍历搜索。

图6(b)：19s后，正在进行遍历搜索时，蚂蚁首先搜索到最近的食物，并根据蚂蚁的需求与食物本身的多少，综合考虑后做出是否需要寻找下一处食物的抉择。

图6(c)：33s后，由于红色的食物不能满足蚂蚁的需求，即分担过载(标记成f),于是蚂蚁需要寻找下一处的服务器(即白色食物F),以达到负载均衡。

图6(d)：44s后，蚂蚁在红色食物F(f)和白色食物F等多处食物处寻找食物，以满足自身的需求，缓解单一食物处的需求压力，从而达到了负载均衡访问。

3.3  实验结果分析与研究结论

为了提升访问的效率和速度，可以提出设置多台服务访问终端，并作镜像处理,如此就可以在地理位置、访问时间、服务质量等方面,使访问得到极大的优化与改善。实现网络流量负载均衡的方法有多种，但是从当前的应用技术和实际实施看，采取在不同的地理位置配置多台服务终端设备来实现服务请求的及时响应是主流技术。因此,本文从这个角度出发，采用C语言在计算机上编程模拟实现了网络环境下的网络流量负载均衡的研究与实现，并取得了良好的实验效果。

通过对实验结果的分析表明，蚁群算法具有智能搜索、全局优化、稳健性与正反馈等优点，能够在较短的时间内寻找到最优路由，使服务请求得到最快的服务响应。

3.4  实验的改善方法及其研究扩展

本实验采取在不同的地理位置，配置多台服务终端，从硬件角度考虑，设计并实现了网络服务请求的及时响应,并取得了良好的实验效果。

本实验从软件的角度考虑,充分利用蚁群算法正反馈的特性，对一台或多台服务器访问，选择较为合适的路径，同样也达到网络流量负载均衡的良好效果。

4  蚁群算法的发展前景

多年来世界各地研究工作者对蚁群算法也进行了精心研究和应用开发,该算法已被大量应用于网络路由选择、机器人协作求解、分布式集群计算、大规模数据挖掘等前沿领域。

以蚁群算法为代表的群智能已成为当今分布式

人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法已越来越多地被应用于企业的运转模式的研究。英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验,群智能还被应用于工厂生产计划的制定和运输部门的后勤管理，美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转机能。鉴于群智能广阔的应用前景,美国和欧盟均于近几年开始出资资助基于群智能模拟的相关研究项目，并在一些院校开设群体智能的相关课程。在国内，国家自然科学基金“十五”期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。

5  结语

目前,蚁群算法在启发式方法范畴内已逐渐成为一个独立的分支,在有关国际会议上多次作为专题加以讨论。随着研究的深入，蚁群算法将广泛应用于网络路由选择、分布式计算和搜索组合优化，展现出勃勃生机和广阔的发展前景。