蚁群路由算法范文

蚁群路由算法范文（精选8篇）

蚁群路由算法 第1篇

双向数字电视业务的开发和发展,是广播电影电视的数字化和产业化的重要推动力量,对国家信息化、社会信息化和家庭信息化的进程发挥着重要的作用。IP网络以其技术成熟、设备稳定成为数字电视相关业务有效承载网络,如何在满足IP网络中QoS要求下进行路由选择,已成为路由算法研究的重要方向。传统的数据通信均采用单播或广播技术,造成主机与网络资源的过度浪费,带来了带宽的急剧消耗和网络拥挤问题。为了缓解网络瓶颈,要求计算机网络具备QoS组播通信能力[1]。

笔者采用一类新兴的模拟生物群体行为的蚁群优化算法进行QoS组播路由问题的求解。针对蚁群算法存在的计算时间长、易陷入局部最优解的缺陷,对蚂蚁的信息素更新策略,下跳节点选择策略进行了改进。

2 蚁群算法

2.1 基本蚁群算法及其改进

蚁群算法是一种新型模拟进化算法,属于随机搜索算法。Marco Dorigo等人根据蚂蚁搜索食物的过程与TSP问题的相似性提出了该算法[2,3]。该算法已在指派问题、调度问题、路径选择问题、着色问题等方面得到了广泛的探讨与应用,取得了令人满意的效果,文献[4]给出蚁群算法的基本原理。虽然蚁群算法发现较好解的能力很强、稳健性好且易于计算机实现,但也存在一些问题,针对算法的不足,笔者进行了3点改进。

1)信息激素更新方式

为了更快地找到接近最优解的可行解,增强算法的收敛性,改进算法中信息激素的更新方式,采取了在线延迟的精英策略更新方式,即蚂蚁完成一次循环后,将其分为遍历路径小于当前最优路径的、等于最优路径的和大于最优路径的3类。然后,采用精英策略,强化找到优于当前最优路径的蚂蚁对信息素浓度的影响,同时消减找到差于当前最优路径的蚂蚁对信息素浓度的影响。具体更新方式为

式中ek为信息素增量系数,Lbest记录当前的最优解。

完成信息激素更新后,将每条路径上的信息激素浓度限制在[τmin,τmax]之间,避免某些边上的信息激素过大,从而在一定程度上扩大解的搜索空间。

2)选择策略

为尽量避免出现早熟现象,根据转移概率通过转轮赌法选择方法从下步可选节点集中选出蚂蚁的下一步节点。转轮赌法的基本思想是个体被选中的概率取决于个体的相对适应度pi,即pi=fi/f总,其中i=1,2,,M,而pi为个体i被选中的概率,fi为个体i的适应度,f总为群体的累加适应度。

顺序累计群体内各个体的适应度,得相应的累计值Si,最后一个累计值为Sn(0

3)变参数

为尽量避免出现早熟现象,将常数项的信息素强度Q变成时变函数Q(t),在选路的开始阶段,Q初值可较小,这样网络中各路径信息素的增量也较小,可避免过早强烈的正反馈;在选路的后期阶段,可适当增大Q值,加快收敛速度。如果在一段时间内获得的最优解没有变化,说明搜索陷入了某极值解中,可能不是全局最优解,此时可采用强制机制减少要增加的信息素,使得其他路径上的信息素强度与极值解路径上的信息素强度差距不要过大,抑制正反馈影响,使其从局部极小值中跳出;若收敛速度过于缓慢,则可增大Q值。

2.2 改进蚁群算法性能测试

为了测试改进算法的性能,选择目标函数F1进行Matlab仿真实验。F1设置为max f(x,y)=xsin(4πx)-ysin(4πy+π+1),且x,y∈[-1,2]。仿真参数设置为:蚂蚁规模为50;迭代代数为50;信息激素的启发因子α为1;自启发量因子β为1;信息素挥发系数ρ为0.1;信息素强度Q满足

同时,信息素增量系数ek满足

F1为一个变峰、多变量、多极值点函数,且F1的函数值相差较大,峰值较密,常规的优化算法容易陷入局部最优解,不易获得全局最优解。从改进蚁群算法对二维函数F1寻优结果图可以看出,初始时刻蚂蚁随机分布在函数的各个点上,如图1所示。算法运行结束后,蚂蚁都聚集在函数的最高峰值处,如图2所示。改进后的算法能找到函数的全局最优解,最终仿真结果充分验证了算法的正确性。为了防止随机产生初始群体对仿真结果的影响,多次运行程序对F1进行仿真实验,算法每次都能找到全局最优解,也没有出现个别蚂蚁不收敛问题,即仿真图中蚂蚁的最终分布都达到算法理想效果。

3 基于改进蚁群算法的QoS组播路由算法

QoS组播路由的目的就是在分布的网络中寻找最优路径,要求从源节点出发,历经所有的目的节点,并且满足所有的约束条件,达到花费最小或特定的服务水平。暂忽略带宽、时延抖动和丢包率度量,则每条链路用二元组(cost,delay)表示,其中的元素分别表示链路的代价和链路时延。蚂蚁的转移概率为

式(7)中,j∈alowedk,alowedk表示蚂蚁k下一步允许选择的网络节点;η1ij=1/cij,cij表示节点i到j的费用,η2ij=1/dij,dij表示节点i到j的时延。α为信息启发式因子,β、γ为自启发式因子。信息素更新为

式中:ρ为挥发系数,ek为信息素增量系数,cost(e)为当前蚂蚁路径上的费用,Cbest记录当前蚂蚁路径的最小费用。

4 仿真分析

图3是仿真实验所使用的8节点的网络拓扑结构(同文献[5]),网络结构模型暂不考虑带宽、时延抖动和包丢失率,每个节点、每条链路都有用QoS度量表示的状态,节点状态可以折算到与节点相连的链路状态中,故这里将节点的度量值忽略不计。则其中各链路的特性可用二元组(cost,delay)描述。

仿真参数设置为:蚂蚁规模为10;迭代代数为31;信息激素的启发因子α为1;自启发量因子β为1;自启发量因子γ为1;信息素挥发系数ρ为0.062 5;信息素强度Q满足

上述参数都是通过大量仿真实验获得的,这样选取的参数可获得较好的结果。

设定到每个目标节点的时延约束条件Delaymax=7;其中源节点s为1,目标节点d为3,5,7。

通过Matlab语言编程,在P4 2.9,1 Gbit内存的计算机进行仿真试验,运行时间约为6.5 s。图4为找到的符合QoS要求且行走蚂蚁最多的路径及其相关参数值,其中图4a和4b的总体代价为10,图4c的总体代价为12。图5是最优组播数代价收敛曲线,最终收敛于10。经过试验,最大时延限制Delaymax=7时得到的最优组播树如图4b所示,其总体代价为10。

5 小结

首先提出了一种改进的蚁群算法,并对改进的算法进行了实例分析,仿真结果证明了算法在求解QoS组播路由问题中增强了收敛性,能有效抑制过早出现强烈的正反馈,避免出现早熟现象,收敛到全局最优解。随着数字电视双向点播业务量的不断增加,该优化算法运用于双向数字机顶盒网络组件中来解决数字电视双向点播IP通信网络中时间延迟和带宽约束问题,同时可提高网络系统的吞吐量,避免了网络拥塞。

参考文献

[1]HU G M,LI L M,AN H Y.Fast routing algorithm for group multicast with bandwidth reservation[J].Acta Electronica Sinica,2003,31(4):569-572.

[2]高海昌.智能优化算法求解TSP问题[J].控制与决策,2006,21(3):241-247.

[3]DORIGO M,GAMBARELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Trans.Evolutionary Computation,1997,1(1):53-66.

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

蚁群算法的运用及其优化分析 第2篇

蚁群算法没有强力的数学基础作为支撑，在实际运用中依然存在一些不足之处，希望有越来越多的人加入研究的行列，有越来越多的学者关注蚁群算法，推动蚁群算法的发展，更好地为人类的学习、工作、生活做贡献。

关键词：蚁群算法；蚁群算法的应用；粒子群算法；优化分析

中图分类号： TP301.6 文献标识码： A 文章编号： 1673-1069（2016）32-158-2

1 蚁群算法的提出

科学家们在研究群居性昆虫的时候发现，虽然它们单个只是简单的个体，但是它们一起合作却能一起完成复杂的工作。昆虫的这种群体生物智能特征，吸引了一些学者的目光。意大利学者M.Dorigo等人在研究蚂蚁的觅食过程中发现，蚂蚁似乎有一种本能，总能找到食物，总能找到巢穴与食物之间的最短路径。蚂蚁作为一种群居性昆虫，它们本身的视线很差，却能找到大量的食物。经过长期的观察与研究，于1991年M.Dorigo等人首次提出蚁群算法。

2 蚁群算法的应用

如今蚁群算法已经深入到我们生活的方方面面，在交通、智能、通信技术方面有着广泛的运用，在求解优化组合、网络路由问题、连续性空间优化问题、聚类分析、图像识别、电网故障分析等领域的应用已经取得了良好的效果。具体包括以下几种：

2.1 旅行商问题

蚁群算法最早是应用旅行商问题的解决，该问题的核心就是要求经过所有的城市，每个城市经过一次，还要返回到原来的出发点，这条线路要求是最短的。众多的实验研究结果表明，蚁群算法远远高于遗传算法、模拟退火法等其他优化算法。

2.2 二次分配问题

最开始的二次分配问题指的是，把m个工厂分配在m个城市，要求分配的时候所用的花费是最少的。这是蚁群算法在旅行商问题后的又一大应用。

2.3 车间任务调度问题

车间任务调度问题指的是一定数量的机器在一定的时间里完成一定的任务量，要求所有的机器同时运行，有序的操作，但所要的时间是最短的。

2.4 大规模集成电路问题

电路是错综复杂的，需要有一个点来支撑所有的电路，确保电路有序。

2.5 连续对象优化问题

蚂蚁一旦选择了一条目标，会一直向着目标前进，选择的路线是固定的，空间不是完整的，是分散的，局部的，若空间是线性的或非线性的连续空间，则相对较弱。使用蚁群算法解决连续对象优化问题，还要求信息素的浓度函数等循环过程。

3 蚁群算法的优化分析

蚁群算法是一种智能化算法，被广泛运用到各个方面，而且性能优良。但也看到蚁群算法要花费大量的时间，有时甚至会出现停滞的现象。在蚁群算法中起着关键作用的就是参数的选择，下面将基于粒子群参数优化，提出一种新的改进蚁群算法的算法。

粒子群优化算法通常也被称作粒子群算法、微粒群算法。这是一种模仿鸟类捕食的算法。鸟类在寻找食物的时候，目的是随机地，也是多样的，但区域里只有一块食物，并且它们也不知道食物在哪里。应如何找到食物，肯定是在食物附近的鸟类最先找到的，所以说在食物附近的鸟类是最有利的。这引起了一些学者的注意，由Kennedy等博士提出，认为这是一种群体智能。在粒子群算法中把区域里的每只鸟都看作是一个粒子。每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。在初始化中，一群随机无序的粒子，要通过迭代才能找到最优解。要想找到最优解，每个粒子在迭代时通过更新两个极值来更新自己的信息素。第一个得到的解就是粒子本身所要寻找的最优解，另一个极值就是相对于整个种群來说最优解。第一个就是另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。要想找到这两个最优值时，粒子要及时更新自己的速度和新的位置，根据如下的公式：

v[] = v[] + c1 * rand（） * （pbest[] - present[]） + c2 * rand（） * （gbest[] - present[]） （a）

present[] = persent[] + v[] （b）

v[] 是粒子的速度， persent[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand （） 是介于（0， 1）之间的随机数. c1， c2 是学习因子. 通常 c1 = c2 = 2.

程序的伪代码可以用如下的表示：

For each particle

____Initialize particle

END

Do

____For each particle

________Calculate fitness value

________If the fitness value is better than the best fitness value （pBest） in history

____________set current value as the new pBest

____End

____Choose the particle with the best fitness value of all the particles as the gBest

____For each particle

________Calculate particle velocity according equation （a）

________Update particle position according equation （b）

____End

While maximum iterations or minimum error criteria is not attained

利用粒子群優化蚁群算法的基本步骤：

步骤一：设立初始值，一定数量的粒子；

步骤二：将每个粒子所对应的参数值对应到相对应的蚁群算法中去，新的参数值会要求蚁群算法做出新的调整，在把这时的蚁群算法的参数值设定为初始值；

步骤三：根据蚁群算法的计算方式判断是优值还是差值；

步骤四：根据公式v[] = v[] + c1 * rand（） * （pbest[] - present[]） + c2 * rand（） * （gbest[] - present[]） （a）present[] = persent[] + v[] （b）改变粒子的速度和位置；

步骤五：若是得到的结果已经是最优解了，或者已经没有最优解了，则算法结束，反之，继续步骤二的操作。

信息素的更新决定了蚁群算法的求解质量。改进后的信息素只是用与每个粒子的一次移动，并且相互间是独立的，没有关联的，一旦结束后，所有的数据会消失掉，不会有所保留。粒子群优化算法作为一种启发式算法，具有下面的众多优点：

①描述简单，来自生活，理解起来也相对来说比较容易；

②相互间是独立的，打破了要求优化问题需要是连续性的问题；

③算法实施起来很容易，并且求解速度快；

④和其他的算法相比，不需要庞大的个体，小众的个体即可实现算法；

⑤大部分的参数是不需要去调整的，只有小部分的参数是需要去调整的；

⑥和其他算法相比，算法具有很强的收敛性；

⑦没有什么特殊的约束条件，个体间是独立的，不会影响到其他的粒子，具有很强的鲁棒性。

4 结束语

蚁群算法最先是用来解决旅行商问题，如今蚁群算法在各个方面被运用，得到了一定的效果。但是和遗传算法、模拟退火算法、微粒子算法相比，虽然得到的解更加优化，但是蚁群算法没有系统的分析方法，同时它的数学基础也不是很强大。在实际的操作过程中，参数的选取比较复杂。虽然在一些领域运用，但运用技术不成熟，还是习惯采用传统的方式。

参 考 文 献

[1] 石华瑀.改进的蚁群算法在实际VRP中的应用研究[D].山东大学，2012.

基于蚁群路由协议的局部修复算法 第3篇

当前网络通信环境复杂多变, 网络的拓扑结构不断地动态变化, 节点可以以任意速度和任意方式移动, 也可以随时加入或退出网络, 因此, 链路中断的情况会经常发生。能够有效地处理链路中断是对无线网络路由算法的根本要求, 尤其在数据传输过程中发生链路中断的话, 丢包率会很严重, 因此, 路由算法必须要能有效地解决这个问题。

按需路由协议通常由路由发现和路由维护两个阶段组成, 目前人们对于网络路由协议的研究主要集中于路由发现阶段, 而对路由维护的研究却比较少, 文献[1]提出了一种使用监听机制的修复方法, 使用监听到的邻居节点信息, 路径的节点成员在路由修复过程中可以做出更好的决策, 从而降低了很多能源消耗。文献[2]提出一种改进的AODV本地路由修复算法。通过路由修复阶段2hop_RREQ和NOTICE报文的传递, 将修复限制在断链的2跳范围内。文献[3]基于最优搜索方程提出了一种限制下一跳节点搜索区域的自愈方法。文献[1, 3]在一定程度上减少了修复控制开销, 但上述算法都是基于AODV路由算法的修复机制, 且发起路由修复的节点均是中断链路的上游节点, 都没有考虑发起修复的节点是否具有稳定性, 是否会引起链路的再次中断。

蚁群路由算法作为一种被广泛应用于路由协议设计的算法, 必须具有路由修复机制, 针对以上问题, 本文基于蚁群路由算法, 提出了一种具有一定稳定性的路由修复机制, 由于链路断裂可能是链路上游节点的移动而导致, 所以本文考虑失效链路的上游节点和上一跳节点的稳定性, 由稳定性高的节点作为修复节点, 并将修复节点的下两跳节点作为目的节点, 无需把修复限定在出错节点和目的节点之间, 从而缩短修复的时间, 减少控制开销。

1 蚁群路由算法

蚁群路由算法是蚂蚁通过在网络中的移动, 在经过的路径上遗留下信息素, 同时根据已有的信息素决定自己的选路, 是一种自适应算法[4], 它是通过交流信息逐步寻找到最优路径。

路由算法分为路由发现, 路由选择, 路由维护三个阶段[5]。此算法中蚂蚁分为两类, 前向蚂蚁和逆向蚂蚁。如图1所示, 前向蚂蚁的主要作用是完成路径的搜索, 并负责收集网络状态信息, 如带宽, 时延等, 每个节点按照概率独立转发前向蚂蚁。到达目的节点后注销前向蚂蚁并产生逆向蚂蚁。逆向蚂蚁主要负责信息更新, 前向蚂蚁把收集到的信息复制给逆向蚂蚁, 逆向蚂蚁沿着其相应的前向蚂蚁的原路返回, 并把网络信息传给每个经过的节点, 逆向蚂蚁每到一个节点更新网络状态信息和路由表信息, 到达源节点后注销该逆向蚂蚁, 这样一条路径就建立了。

2 蚁群路由的局部修复算法

2.1 局部修复算法

当链路断裂时, 已有的路由局部修复算法往往由失效链路的上游节点发起到目的节点的路由修复, 如图2所示, 源节点s发送数据到目的节点d, 当节点b和节点c之间的链路失效时, 由节点b发起到目的节点d的路由修复。节点b产生的前向修复蚂蚁, 到达目的节点后产生逆向蚂蚁, 并按原路径返回到节点b, 并更新路径上各节点的信息素值, 这样就建立了一条新的路径。

上述算法是由失效链路的上游节点直接面向目的节点查找新路由, 将导致一些无谓的路由发现, 增加控制开销和时延, 并且没有考虑发起路由修复节点的稳定性。

在无线网络中, 链路中断主要由节点软硬件错误、能量耗尽和节点的移动性这两种原因引起, 节点移动的情况又分为: (1) 失效链路上游节点移动引起链路中断; (2) 下游节点移动引起链路中断; (3) 上下游节点相背移动引起。针对第二种情况, 由失效链路的上游节点发起路由修复的成功率较高, 而第一和第三种情况, 如果上游节点继续按照原先的速度和方向移动, 那么很可能在短期内导致修复后的链路再次失效引起二次修复。因此局部修复的成功率很大程度上取决于上游节点的稳定性。如果上游节点处于移动状态, 链路失效可能是由于这个节点的移动导致的, 那么该节点并不适合发起路由修复。因此, 本文针对这种情况, 选取稳定度较高的节点发起路由修复。

假设在网络移动区域内随机分布了N个节点, 则t时刻网络拓扑可以用无向图G (t) =表示, 其中N={1, 2, , m}代表节点集合, E (t) ={e1, e2, , em}代表链路集合, 如果节点i和j之间存在边, 节点j就是节点i的邻居节点, 节点i的所有邻居节点构成i的邻居集, 记为:Ni (t) 。那么节点i的稳定度为[6]:

其中Ni (t1) 表示t1时刻节点i的邻居集, Ni (t2) 表示t2时刻节点i的邻居集。STAi反映了与节点i相关的链路的通断变化, STAi越大表示节点i越稳定;STAi越小表示节点i变化越剧烈。

本文中只考虑失效链路的上游节点和上游节点的上一跳节点, 比较这两个节点的稳定度, 由较高稳定度的节点发起路由修复。

在路由层, 每个节点要进行邻居节点管理, 每个节点每隔一定的时间会向所有的邻居节点发送一个HELLO包[7], 并且要求返回HELLO-ACK报文, 这样节点就可以记录所有邻居节点的个数, 将其放入邻居节点表中便于计算稳定度。因为HELLO包要比数据包小很多, 所以并不会显著增大开销。

失效链路的下游节点仍然保存着到目的节点的有效信息, 原始的局部算法并没有充分利用这些有效信息。并且失效链路的上游节点到目的节点的距离要大于发起路由修复的节点到其下两跳节点的距离, 因此原始算法的路由控制开销较大, 时延较长。所以, 本文将发起路由修复节点的下两跳节点作为目的节点进行修复。

如图3所示, 在路由层, 当检测到链路bc失效时, 比较节点b和上游节点a的稳定度, 如果节点a的稳定度大于节点b的稳定度, 前向蚂蚁按照禁忌表中记录的路由器顺序, 回溯至上游节点a, 并发起到下两跳节点即节点c的路由修复。如果节点b的稳定度大于节点a的稳定度, 则由节点b发起至下两跳节点e的路由修复, 这样既可以减少由于失效链路上游节点不稳定造成链路再次失效的情况, 又可以减少链路修复开销。

在已有的路由维护算法中, 局部修复在发起路由修复的节点和目的节点之间重新寻找一条路由, 会导致较长的时延和无线带宽的浪费。如果网络的规模扩大, 局部修复的控制开销和时延都会随之增加。改进的算法中, 修复范围限制在发起路由修复节点的下两跳范围内, 所以网络上传播的蚂蚁数量更少, 控制开销将大大较小, 寻路时间也更短。

2.2 路由控制包

蚁群路由算法中使用了前向蚂蚁和逆向蚂蚁, 分别用来寻找路径和更新所选路径上的信息素, 它们的格式基本相同只是功能不同, 类似于AODV路由算法中的路由请求RREQ和路由应答RREP[8]。

前向蚂蚁包格式如图4所示。

(1) 蚂蚁类型:值为1时, 表示为前向蚂蚁;值为2时, 表示为逆向蚂蚁。

(2) 源节点地址:前向蚂蚁开始搜索路径的起始节点地址。

(3) 标志位L:这是本算法新增加的标志位。当该标志置为“l”时, 表示此前向蚂蚁是前向修复蚂蚁, 用于小范围局部修复。当该标志置为“0”时, 表示此算法是原蚁群路由算法的前向蚂蚁。

(4) 目的节点地址:在原蚁群算法中, 表示路由请求的目的节点。本文对此标志做了修改:如果L标志被置“0”, 该项与原蚁群算法相同, 表示路由请求的是目的节点的地址。如果L标志被置“1”, 则该表项无效, 这时表示小范围路由请求目的地址是发起路由修复节点的下两跳节点的地址。

(5) 真正的目的节点地址:即下两跳节点的地址, 本协议新增加的表项。当L标志置“0”时, 该项信息无效, 接收节点不对该项进行处理。当L标志置“1”时, 该表项表示这次路由查找的真正目的节点地址, 即发起路由修复节点的下两跳节点地址, 对应于普通前向蚂蚁控制包中的目的节点地址。

逆向蚂蚁包格式如图5所示。

(1) 信息素增量:它是到达目的节点后计算的。所以前向蚂蚁中信息素增量的值为零, 逆向蚂蚁中信息素增量的值是在目的节点计算的, 并按原路径返回源节点并更新路径上各节点的信息素值。

(2) 下两跳节点地址:发起小范围局部修复需要节点保存下两跳节点地址, 发送逆向蚂蚁的节点, 把路由表中能够到达目的节点的下一跳地址复制到该项中, 当节点接受到该逆向蚂蚁包时, 将该内容复制到路由表的下两跳节点地址项中。该项是新增加的内容。

(3) 其表项代表的内容同前向蚂蚁包相同。

2.3 链路检测

蚁群路由算法的链路的检测方法可以分为路由层检测和MAC层检测两种。在路由层检测, 每一个节点都要进行邻居节点管理, 例如, 节点i每隔t秒向所有的邻居节点发送一个HEL-LO包, 并且要求返回HELLO-ACK报文, HELLO包机制不仅用来计算节点稳定性, 也可以进行链路检测, 如果在一定的时间内没有收到节点j的HELLO-ACK包, 就判断节点i和节点j之间的链路失效了。第二种方法是在MAC层检测链路中断, 通过数据报文单播失败来检测是最直接的, 例如, MAC层采用的IEEE802.11 DCF协议[9]。当节点i向节点j发送数据时, 同时要求节点j返回一个ACK帧, 当节点i没有收到ACK帧时, 就断定链路失效, 因此, 节点可以用MAC层的ACK帧代替路由层的HEL-LO-ACK包来检测链路中断。本文为了方便计算节点的稳定度, 采用路由层发送HELLO包的检测方法检测链路。

3 算法流程

在网络中, 当某节点需要一条路径到达某个目的节点时, 那么源节点检查路由表看是否有已经存在的路径信息。已经存在的路径信息是指在信息素表中, 到达目的节点的路径中有一条链路上的信息素值要高于其它链路上的信息素值。反之, 如果通向这一个目的节点的几条链路上的信息素值都一样, 则说明这几条链路上的信息素只在信息素蒸发时改变过, 没有前向蚂蚁爬过, 也没有逆向蚂蚁来更新信息素, 即到达目的节点的路径还没有建立, 如果没有, 它发起一个按需路由建立过程, 通过发送“L=0”的前向蚂蚁在网络中寻找一条通向目的节点的路径。

路径建立后进行数据转发, 当路由层检测到链路失效后, 进行“L=1”局部修复, 修复路由的过程描述如下:首先将数据报文放入缓存队列等待发送, 再判断失效链路上游节点和上一跳节点的稳定度, 由稳定的节点发起局部路由修复, 此时前向蚂蚁包格式中L设置为“1”, 表示目的地址为下两跳节点地址, 成功修复后, 后面的路径可继续按照有效的路径信息将数据报文发送到目的节点。产生的前向修复蚂蚁和普通的前向蚂蚁一样, 以同样的方式被转发。在中间节点k, 按照信息素浓度和启发式信息来计算下一跳节点的选择概率, 到达目的节点后产生逆向蚂蚁原路返回, 这样一条新的路径就建立了。流程如图6所示。

4 仿真分析

在仿真场景中, 20个节点在1 200 m1 200 m的矩形区域内移动, 节点采用Random Way Point运动模型, 选择一个源节点, 在区域内节点以速度V向目的节点移动, 到达一个节点后, 暂停一段时间后, 再向下一个节点移动, 直到到达目的节点。通信源是CBR流, 数据包大小为512 Byte, 每秒发送5个包, 节点移动速度V分别为1, 4, 8, 12, 18, 20 m/s, 暂停时间为50s, 路由层使用发送HELLO包机制[7], 每次仿真运行400 s。

本文从端到端的平均延迟、路由开销2个性能指标对本文改进的修复算法和原修复算法 (在出错节点和目的节点之间的修复算法) 进行了验证比较。

从图7中可以看出, 本文改进的局部修复算法所用的时延要比原修复算法所用的时延少, 因为当路由算法有路径修复机制时, 链路发生中断后, 数据包被存储在缓存队列中等待路径修复。原修复算法中, 修复算法所修复的路径是从失效链路上游节点到原目的节点之间的路径, 而本文改进的修复算法, 是将范围限定到发起路由修复节点的两跳范围内, 修复的路径要比原算法短很多, 所以存储在缓存队列中的数据包等待的时间就较短。特别是网络规模越大时, 效果越明显, 数据包等待路径修复的时间就越少, 所以本文修复算法比原修复算法减少了时延。

图8比较了两种路由算法的路由开销, 从图中可以看出, 原算法的路由开销明显大于本文改进后的修复算法的路由开销。一方面, 改进的修复算法在路由层增加了利用HELLO包计算稳定度的分组;另一方面, 改进的修复算法, 将修复范围限制在发起路由修复节点的下两跳的局部范围内, 大量减少了前向修复蚂蚁控制包的发送。但是HELLO包要比数据包小很多, 所以总的来说改进的局部修复算法与原修复算法相比降低了路由开销。

通过平均时延和路由开销两个方面的比较, 表明改进的局部修复算法比从失效链路的上游节点到目的节点的局部修复算法具有明显的优势, 不仅降低了路由修复的时延, 也明显减小了路由开销。

下面分别在节点个数为20、30、40、50和节点速度均为8 m/s的网络中, 选择源节点和距离源节点较远的目的节点, 分别对它们的平均端到端时延进行了仿真。

从图9中可以看出, 随着网络节点个数的增加, 本文改进修复算法所用的平均时延与原有算法所用的时延相差越来越大, 因此, 随着网络规模的扩大, 本文改进的修复算法比原有的修复算法就越有明显的效果。

数据分组发送成功率是指成功接收到的数据分组数与发送的数据分组总数的比值。下面分别在节点移动速度V分别为4、8、12、18、20 m/s的情况下, 对本文的修复算法和原修复算法的数据发送成功率进行了比较。

从图10中可以看出随着节点移动速度的增加, 由于链路出现故障的概率增大, 所以数据发送成功率呈现越来越低的趋势, 但是本文修复算法的数据发送成功率明显大于原修复算法的成功率, 因为本文的修复算法选择稳定性高的节点发起路由修复, 从而减少了由于链路再次中断而造成数据包丢失的情况。

5 结语

本文针对蚁群路由算法修复机制, 提出了一种改进的局部修复路由策略。在原始路由算法中, 局部修复的意义就在于把修复限定在出错节点和目的节点之间, 而改进之后的算法则更好诠释了“局部”的意义, 把修复范围缩短到节点两跳范围内, 并考虑了发起路由节点的稳定性。仿真结果表明, 把修复限定在失效链路的附近, 范围更小, 处理时间更短, 平均延迟更小, 并且降低了路由开销, 此外, 改进的局部修复算法的控制开销和时延都与网络的规模无关, 当网络规模越大, 路由跳数越多, 改进的局部修复算法就越有其优越性。

摘要：在无线网络中, 当由节点频繁移动而引起通信链路发生故障时, 路由协议需要对其进行修复, 才能保证正常通信。现有路由修复机制存在控制开销大和时延长的不足, 而且大多数为针对AODV (Ad Hoc On-demand Distance Vector Routing) 路由算法的修复, 难以充分保证链路性能, 并且存在链路重构后链路再次失效的缺点。基于此, 提出一种基于蚁群路由算法的局部修复算法。首先, 选取稳定性高的节点发起路由修复, 以降低链路修复后的不稳定;其次, 将修复范围限定在较小的局部范围内以减小控制开销和时延。仿真表明, 改进的路由局部修复算法明显地提高了链路的稳定性, 缩短了修复时间, 降低了路由开销。

关键词：前向蚁群,逆向蚁群,链路中断,路径修复

参考文献

[1]Sirilar J, Rojviboonchai K.OHO:OverHearing On-Demand Route Repair Mechanism for Mobile Ad Hoc Networks[C]//Electrical Engineering/Electronics Computer Telecommunications and Information Technology (ECTI-CON) , 2010:66-70.

[2]丁绪星, 吴青, 谢方方.AODV路由协议的本地修复算法[J].计算机工程, 2010, 36 (6) :126-128.

[3]秦丹阳, 马琳, 沙学军, 等.移动Ad Hoc网络中路由自愈的实现[J].哈尔滨工业大学学报, 2010, 41 (1) :46-50.

[4]Kasaei M J, Gandomkar M.Loss reduction in distribution network using simultaneous capacitor placement and reconfiguration with ant colony algorithm[C]//Power and Energy Engineering Conference (APPEEC) , 2010:1-4.

[5]肖百龙, 郭伟, 刘军, 等.移动自组网路由局部修复算法的研究[J].计算机研究与发展, 2007, 44 (8) :1383-1389.

[6]蔡一兵, 李海波, 李忠诚, 等.移动自组织网基于邻居变化率稳定路径选择方法[J].软件学报, 2007, 18 (3) :681-692.

[7]孙波.一种适用于Ad Hoc网络本地修复策略的改进与研究[D].武汉:武汉理工大学, 2011.

[8]Li Sudan, He Dan, Sun Zhili.A cost-aware multi-path routing protocol for multi-interface multi-channel manets[C]//Proceedings of the IADIS International Conferences-Informatics, 2011:83-90.

蚁群路由算法 第4篇

蚁群算法是一种群体智能算法,最初用于解决组合优化问题中的旅行商问题、二次分配等问题,并取得了较好的效果。蚁群算法具有分布式并行计算、自组织、正反馈的特点,且有较强的鲁棒性。由于无线传感器网络自身的特点,传统网络的路由协议不能很好地适用于无线传感器网络。许多学者都在集中研究开发基于蚁群算法的无线传感器网络路由算法[2,3,4]。我们在本文中提出一种改进的基于蚁群优化的路由算法,该算法避免了基本蚁群算法中的单一收敛,在控制网络拥塞和平衡能量消耗上也达到了很好的效果,延长了网络生命周期,实现无线传感器网络的路由优化目标。

1 基于蚁群优化的路由原理

1.1 蚁群算法原理

蚁群算法[5]是一种启发式算法,蚂蚁借助他们在通过了的路径上留下的信息素彼此通信。每个蚂蚁可以嗅到其它蚂蚁留下的信息素并通过信息素引导自己的移动方向,但信息素会随著时间的流逝而挥发。因此,路径的长度和经过这条道路径的蚂蚁个数会影响信息素的浓度。另一方面,信息素的浓度将引导蚁群中其他蚂蚁的移动方向,如果有很多蚂蚁经过这条道路径,那么其它的蚂蚁选择这条路径的概率将会很高。这在蚁群系统中构成了一种信息素正向反馈机制。

近几年,生物启发算法已被广泛地应用到网络路由问题上,基于蚁群优化的路由算法对最大化网络生命周期有显著贡献。基于蚁群算法的路由算法一般分为两大类。一是Ant-Net算法,即通过正向蚂蚁和逆向蚂蚁的协作来取得最优路由,正向蚂蚁收集节点信息而由逆向蚂蚁根据这些信息来更新路由表。另外一种是蚁群控制算法,它以特殊的概率选择和更新路径。该算法只有一种蚂蚁,从源点出发到终点。当蚂蚁抵达终点时更新路由表。两种算法在网络变化中都具有较强的自适应性,并能迅速的建立最优路径。但是当他们更新路由表时有两个缺点:一个是节点瘫痪,这是由于网络延迟,节点能量消耗过快引起的。另一个是因广播通信中更多的蚂蚁需要协同工作而消耗过多的能量。

为了达到结果最优和适应无线传感网络,在文献[6]中,提出了均衡节点的能量消耗的蚁群算法路由协议,他们利用蚂蚁算法建立最优路由路径。文献[7]中作者提出了基于蚁群系统的网络能量平衡路由算法。文献[8]实现了多蚁群路由算法。

1.2 基本蚁群路由算法

我们将无线传感器网络的拓扑结构模拟成一个无向图G(N,A),N是节点集,A是路径集。在初始化过程中,图中所有的路径都被给定一个信息素值。当搜索活动开始,蚂蚁会随机的在候选的节点集中选择一个并开始搜寻过程中。在这个搜寻过程中,蚂蚁倾向于选择具有较高浓度的信息素路径的下一个节点。当所有的蚂蚁都完成了他们的搜寻过程,更新全局信息素。这意味着所有路径上信息素会蒸发掉一部分,每一个蚂蚁根据能量消耗参数更新它通过的路径上的信息素。如果能量消耗参数低,这条路径上的信息素减少的就会很少。随后蚂蚁会选择一个新的节点重新开始搜索过程。

我们假设一些蚂蚁在节点n,蚂蚁k根据概率Pk(n,d)访问下一个节点d。Pk(n,d)公式如下:

在公式(1)中,Ω代表信息素大小,Γ代表从源点到目的地的距离的倒数,Xk(n)表示蚂蚁还没有访问过的节点集,ε是调整能量消耗和信息素之间关系的一个常数。全局信息素的更新根据公式(2):

ΔΩk(n,d)由公式(3)表示:

这里,Ek是蚂蚁k完成路由路径搜索的能量消耗。

从上面的描述我们可以知道,所有的蚂蚁通过具有最高信息素的路径到达目的地。因此,如果一条路径可以引导蚂蚁到达目的地,这条路会涌现大量的蚂蚁,最后我们会把这个路径作为热路径。在无线传感器网络中,这种热路径并不一定是一个用来转发数据包的最佳选择。因为在这个路径上数据包可能会拥塞、甚至导致部分网络崩溃的结果。而且热路径会缩短网络的生命周期。

2 基于蚁群优化的无线传感网络路由算法

为了达到平衡负载这个目的,我们不得不改进基本的蚁群算法。新算法能让数据包通过不同的路由路径来转发,收敛速度更快,避免了单一收敛。在新方法中,我们将标记不同的数据包流使他们通过不同的通道转发。为此我们引进多蚁群之间的竞争机制,结合节点能量的变化来达到负载均衡的目标。因为每一个蚁群都有他们自己的信息素,我们将每个蚁群标记不同的信息素以作为他们的蚁群划分。一旦不同的信息素出现在同一转发路径上时,所有的信息素会被迅速蒸发掉。这意味着,不同的蚁群的信息素相互抑制。因此,这就导致了这个转发路径上蚂蚁的数量将会越来越少。

我们定义m个蚂蚁的蚁群为A1,A2,,Am-1,Am,每个蚂蚁的信息素为Ω1,Ω2,,Ωm-1,Ωm。蚂蚁Ai停留在节点n,根据概率Pik(n,d),蚂蚁Ai将访问下一个节点d。

这里Ω代表每条路径上信息素的量,Γ代表从源点到目的地的距离的倒数,Xik(n)表示蚂群Ai中蚂蚁k没有访问过的节点集,ε是调整能量消耗和信息素之间关系的一个常数,值设置为2。φi,d是蚁群Ai中蚂蚁k的信息素能量操作因子:

Ed表示蚁群Ai中蚂蚁k将要访问的下一个节点的能量消耗,Uk(n)表示蚁群Ai中蚂蚁k将要访问的下一个节点集合。

公式(4)中,谆j是当蚁群Ai和其他蚁群有相同推进方向时候的抑制概率因子:

公式(6)表明在搜索传输路径过程中,如果两个蚁群Ai和Aj在同一路径上,这两个蚁群会相互抑制,最后导致这个路径上的两种蚁群的蚂蚁数目都减少。然而,这种数据流平衡不能使网络快速的稳定。在任何一个蚁群系统中,当选择一个路径的概率发生了变化,选择另一个相关路径作为下一个路径的概率也将更新。所以更新概率应该要满足下式:

在公式(7)中,我们以节点n作为源节点,并且所有的候选转发节点都有他们自己的转发概率,概率和为1。因此,在调整一个转发节点概率后,所有转发节点的概率都需要重新计算,也就是要动态的调整概率。

从公式(4)中可以看到,当所有的蚁群相互竞争最优路径时,他们都服从来自于转发节点的能量消耗最小的约束条件。也就是为了达到当蚁群算法收敛于最优解的同时平衡节点间的能量消耗的目标。与此同时,我们的算法将避免所有的蚁群收敛于同一个全局最优解,更避免了通信拥塞并延长了网络生命周期。全局信息素的更新公式(8):

这里的Eik表示当蚂蚁k完成路由路径搜寻后的能量消耗。在公式(8)中,λi表示改进后的信息素挥发因子,这个因子能由公式(10)计算:

εij是信息素抑制参数。在我们的算法中,我们使用信息素抑制参数来计算在两个蚁群竞争过程中的信息素的挥发程度和在竞争中蚂蚁减少的数量。

3 实验与分析

我们把改进的算法和基本蚁群算法做了实验比较。实验结果统计图如下:

图1是模拟基本蚁群算法的实验结果,显示随着时间的推移不同路径上的蚂蚁的数目。结论:在路径BD上,蚂蚁的数量急剧增加。然而,路径BC和BE上的蚂蚁数目的远低于BD上的。图2显示的是改进算法的实验结果,可以看到在最优路径BD上,蚂蚁的数量得到了控制并相对于基本蚁群算法有明显的减少。另一方面,在路径BC和BE上,蚂蚁的数量也显著增加,这可以达到平衡网络负载这个目标。我们还对节点D在改进的算法和基本蚁群算法关于能源消耗上做了比较。从图3中可以看到采用基本蚁群算法时,节点D的能量消耗显著;相反,改进的算法在负载平衡上很有效,节点D则保留了更多的能量。

新算法结合了多蚁群的信息素释放机制和节能策略,还引进多蚁群之间的竞争机制以避免算法的单一收敛,解决了无线传感器网络路由过程中节点能量消耗和拥塞控制问题,能够达到更好的负载平衡能力,并延长了网络生命周期。

4 结束语

WSN具有广阔的应用前景,但是由于节点能量,处理能力,储存空间以及带宽等的限制,它的大规模应用还是存在许多需要克服的问题,设计一个满足需要的高效的路由算法是目前面临的一个主要问题。在本文中,我们提出一种新的基于蚁群优化的无线传网络的路由算法。新算法对基本蚁群算法进行了改进。引入多蚁群之间的竞争机制来解决局部最优解的问题和避免早熟现象。同时,结合节点的能量消耗问题,实现负载平衡。算法对延长网络的生命周期具有很明显的效果。

参考文献

[1]李晓维,徐勇军,任丰原,等.无线传感器网络技术[M].北京:北京理工大学出版社,2007.

[2]M.Dorigo and L.Gambardella,“Ant colony system:a cooperative learning approach to the traveling salesman problem,”IEEE Trans.On Evolutionary Computation,Vol.1,pp.53-66,Apr.1997.

[3]G.Chen,T.D.Guo,W.G.Yang and T.Zhao,“An improved ant based routing protocol in wireless sensor networks,”Proc.of International Conference on Collaborative Computing:Networking.Applications and Worksharing,pp.1-7.Nov.2006.

[4]L.Juan.S.Chen and Z.Chao,“Ant system based anycast Routing in wireless sensor networks,”Proc.of the International Conference on Wireless Communications,Networking and Mobile Computing(WiCom2007),pp.2420-2423,Sept2007.

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

[6]杨靖,熊伟丽,徐保国.无线传感器网络中基于蚁群算法的路由算法[J].计算机工程,2009,35(6):4-6.

[7]刘徐迅,曹阳,等.一种无线传感器网络能量平衡路由[J].华中科技大学学报,2008,36(2):95-98.

一种基于蚁群优化的分簇路由算法 第5篇

无线传感器网络(Wireless Sensor Network，简称WSN)是由大量低成本且具有数据处理和无线通信能力的传感器节点通过自组织方式形成的一种新型网络。与传统网络不同，传感器网络节点的能量非常有限，全部由自带电池供给，在感知数据的同时，还要承担路由的功能，为邻居节点转发数据[1]。基于此，如何设计有效的路由算法，节约各节点有限的电池能量，并尽可能地延长整个网络的生命周期，已经成为无线传感器网络发展亟待解决的关键问题。

低能量自适应分簇路由[2,3](Low-Energy A-daptive Clustering Hierarch，简称LEACH)是在WSN中最早提出的一个分簇路由协议，该算法使用分簇来延长网络的生命周期，但该算法的簇头选择机制比较随机，每轮产生的簇头没有确定的数量和位置，网络中的簇头分布在覆盖区域内非最优化，并且簇头直接与基站通信能耗较大，实际应用中很难平衡节点的能量消耗。LEACH定义了“轮”(round)的概念，每轮由簇的形成阶段和簇的稳定工作两个阶段组成。针对LEACH协议在簇的形成阶段中簇头选择机制的随机性，本文提出了一种新的簇头选择机制，该机制可以保证每轮产生的簇头数目相对固定。针对LEACH协议簇的稳定工作阶段簇头直接与基站通信消耗大量能量的不足，大量的研究工作者都考虑使用多跳路由算法。文献[4]提出了一种基于蚂蚁算法的分布式数据汇集路由算法(DADC)，该算法的基本思想是通过一组称为“蚂蚁”的人工代理寻找到达基站的最优路径，并利用蚂蚁算法的正反馈效应达到数据汇集的目的。但该算法不能解决网络中的能量负载平衡的问题。文献[5]提出了通过修改蚁群优化(Ant Colony Optimization,ACO)的PARA算法，它将节点能量水平和传输距离引入ACO的信息素增量公式，使ACO较好地适应于WSN的路由协议。但该算法没有考虑全网能量均衡使用的问题。本文根据蚁群优化算法(Ant Colony Optimization,ACO)及无线传感器网络分簇路由算法的特点，将ACO应用于WSN分簇路由的簇间路由机制中。总之，本文在LEACH协议的基础上，对其簇头选择机制和簇头与基站的通信都做出了相应改进，仿真结果显示，该分簇路由算法提高了簇头节点的能量高效使用，平衡了网络能量消耗，延长了网络的生命周期。

1 LEACH路由协议的描述和分析

1.1 LEACH路由协议基本思想

LEACH协议是第一个基于分簇的无线传感器路由算法。该算法基本思想是:以循环的方式随机选择簇首节点，将整个网络的能量负载平均分配到每个传感器节点中。簇头形成一个更高层次的网络并集中管理簇中的成员。成员节点不必维持复杂的路由信息，从而达到降低网络能源消耗、提高网络整体生存时间的目的。其形式的网络拓扑结构图1所示。

1.2 LEACH路由协议的工作过程

在LEACH路由算法中定义了“轮”(round)的概念，每轮由簇的形成阶段和稳定的数据传输两个阶段组成。为了减少资源开销，通常稳定的数据传输阶段持续时间相对较长。

(1)簇建立阶段

每一个无线传感器网络节点随机生成[0,1]随机数，如果选定的随机数小于某一个阈值T(n)，那么该传感器节点成为簇头节点。T(n)的计算如下:

其中，p为每一轮中簇头节点在全部网络节点中所占百分数，r为目前进行的选举轮数，G为最近1/p轮循环中没有成为过簇头的节点集合。从公式(1)可以知道，当r=0时，每个节点成为簇头的概率为p;当r=(1/p)-1时，T(n)=1，剩余未担任过簇头的节点都将成为簇头。

当某传感器节点被选为簇头后，其就向整个网络广播告知自己成为簇头的消息，其他非簇头节点收到消息后，根据与各簇头节点之间的信号强度决定所加入的簇，如果认为应该加入该簇，那么就向该簇头发送加入簇的请求。然后，簇头节点采用TD-MA方式为本簇内所有节点分配传输数据的时间间隙。

(2)稳定数据传输阶段

进入稳定工作阶段后，非簇头节点在属于其时间间隙内，通过利用CSMA/MAC协议向其簇头发送数据，而在不属于自己的时间间隙内则切换到睡眠状态，节省能量。簇头节点接收来自成员节点采集的数据后，将所有信息进行融合后发送到基站，在稳定传输阶段持续一定的时间后，LEACH路由算法又开始新一轮的分簇阶段。

1.3 LEACH路由协议的缺陷

尽管与其他路由算法相比，LEACH协议有优秀的表现，但是它仍存在很多的不足，例如:

(1)簇头选择采用随机的方式，因此每一轮簇头的数目是不固定的。然而簇头节点在整个网络中担当十分重要的角色。如果簇头数目过少，那么一个簇所覆盖的区域会过大，非簇头节点到簇头节点的距离较远，传输数据造成的能量损耗就会增大，这样不利于延长节点寿命。若簇头数目过多，一方面簇头所消耗的能量要远远大于非簇头节点，会导致整个网络的节点在每轮中总的耗能增大;另一方面簇头数目过多会导致数据融合的效率降低产生过多不必要的数据融合。

(2)在簇头节点的选择上，没考虑节点的剩余能量问题，这样可能会导致距离基站较远或剩余能量较少的节点被选为簇头，造成簇头节点的分布不均匀或节点过早死亡。

(3)频繁的选举簇头，需要大量的广播消息，增大了节点的能量消耗。

(4)所有节点的簇内通信及簇头节点与基站通信都用单跳的方式，造成距离基站较远的簇头节点由于通信距离过长，耗能较多而尽早消耗完自身能量，造成网络分割，且单跳通信方式使算法的扩张性受到限制，不适合在大规模的传感器网络中应用。

2 基于蚁群优化的改进LEACH协议

综合以上LEACH算法的不足，本文提出的算法主要针对LEACH协议的缺点(1)和缺点(2)对其进行改进。改进后的算法也分为簇的形成阶段和稳定的数据传输两个阶段。

2.1 簇的形成阶段

针对LEACH协议每轮产生簇头数目不固定的缺陷，本文提出了两种方法来改进LEACH的簇头选择机制[6]。其中一个方法是使用随机时间而非随机数来选择簇头，并且选择k个(k是在该轮中最优簇头数目，本文把它选为存活节点的5%)时间最小的节点作为簇头，该方法可以保证每轮选出的簇头节点数目是个固定值。另一个方法是控制簇头节点的位置，簇头节点之间的距离不能小于d(d是一个理论值，并且通过公式(2)计算其值)，因此可以保证所有簇头不会分布在一个集中的位置。

其中，x、y分别是传感器网络区域的长和宽，π的值是3.14,k是传感器网络簇头节点的数目，α是在(1,2)之间的常数，这里把它的值选为1.7。

在起始阶段，节点不再产生随机数，而是产生一个随机时间t。每一个节点内部有一个定时时钟，当该时钟到达时间t，它将会判断该节点是否当选过簇头。如果它担任过簇头，它将不能参与簇头节点的竞争;如果没有担任过簇头，它将会判断接受到的簇头广播消息的数量是否小于k，如果大于k，在该轮它将不能成为簇头节点，否则，该节点将判断其到所有现存簇头之间的距离是否大于d。在簇头选择过程中，簇头节点将会公布它成为簇头的广播消息，当其他节点接收到该广播消息后，它们将会根据该消息的信号强度计算其到簇头之间的距离，并且记录其最小值。如果该最小值比d大，该节点将会成为簇头，否则将成为普通节点。簇头节点的选择过程如图2所示。

簇首确定以后，其他节点根据接收到的信号强度来决定从属的簇，并且通知相应的簇首。当簇首接到该消息时，它使用TDMA时序为传感器节点安排时间槽来传递数据，于是簇就形成了。

2.2 稳定的数据传输阶段

簇的路由阶段的主要工作是转发数据，为了在簇间实现多跳通信，并且减少远离基站的簇头能量消耗，使用蚁群优化去发现簇间的最优路径。簇头通过最优路径去转发数据来减少能量消耗，并延长网络生命周期。

2.2.1 蚁群优化算法

为了简化无线传感器网络的路径问题，可以把网络看成是一个不定向的加权连接图，G=(V,E)指n个节点的不定向图，其中n=∣V∣，V是网络的节点集合，E是在节点间的连接集合(假设网络中每一对节点最多只有一个连接)。每条边的信息素值是τij。蚁群优化被用来在图G中找到一条从节点Vs到目的节点Vd的最小能量消耗的路径，同时将能量消耗平衡考虑进来[7]。

(1)状态转变的可能性规则

通过分析蚁群算法，对不同节点来说为了获得一个相对平衡的能量消耗，本文修改了状态转变的可能性公式。

在节点Vi的蚂蚁k根据选择可能性选择下一跳节点，基本的蚁群优化的等式方程式如下:

其中，Ni指蚂蚁k在通信范围内允许通往下一个节点的集合，τij(t)是边e(Vi,Vj)在t时刻的信息素强度。α、β是系统参数，它们可以控制信息素和启发式值的相对重要性。ηij(t)可以从以下两式得到:

其中，Ej(t)是选定的节点Vj在t时刻的剩余能量，d(i,j)是节点Vi和Vj之间的距离，d(i,s)和d(j,s)是节点Vi和Vj到节点Vs之间的距离。λ1、λ2、λ3是加权系数。

公式(3)表明，蚂蚁找到的路径是受信息素、节点当前能量以及每一节点和基站之间的距离这些因素影响的。正是由于这些因素的影响，促使向最优解决方案聚集，同时平衡了节点之间的能量消耗。因此能量消耗是相对均匀的，并且高效地延长了整个网络的生命周期。

(2)信息素更新规则

当蚂蚁k从节点Vi到节点Vj通过边e(Vi,Vj)，在边e(Vi,Vj)的信息素更新被修改如下:

其中，ρ是信息素挥发系数，0<ρ<1，λ是加权系数，d(i,j)是节点Vi和Vj之间的距离，Ei和Ej是选择的节点Vi和Vj的剩余能量。

2.2.2 依据蚁群优化算法的簇内路由设计

(1)算法规则

一是蚂蚁携带包含目前单跳书和目前爬行路线信息。

二是蚂蚁通过可能性计算公式(3)-(5)搜索下一跳节点。

三是当蚂蚁移从节点Vi移向Vj时，通过公式(6)-(7)来更新信息素。

四是如果蚂蚁在单跳后发现了基站，该蚂蚁退出搜索。

五是当蚂蚁移向非目的节点，并且不能选择下一跳，然后退出搜索，搜索将不会在该路径上通过该节点。

六是对蚂蚁来说，停止搜索的条件是基站被搜到了或超出了限制的跳数。

(2)算法设计

步骤1状态初始化:放置k只蚂蚁到每个簇头，初始化跳数Jnum=1，迭代数Rmax=C(常数)，设置并初始化三个矩阵Tabu、R_best和A_city,Tabu用来存储和记录生成的路径，R_best用来存储簇头的最优路径，A_best用于存储访问过的节点，信息素矩阵Tabu被初始化为矩阵(n,n)。

步骤2插入访问节点到A_city，每只蚂蚁通过规则二搜索下一步，并且更新A_city和Tabu。

步骤3通过规则三更新访问过路径上的信息素值。

步骤4通过规则四、五、六决定每只蚂蚁是否满足迭代终止条件。如果该蚂蚁没有满足这些条件，然后返回步骤2继续该搜索算法，直到满足这些条件，然后保存目前的最优解决方法。

3 算法仿真及分析

3.1 能量模型和参数

本文使用与文献[8]相同的能量模型，并且无线传递模型可以根据节点之间的距离控制传递能力的大小。本文使用Matlab软件对本文提出的算法和LEACH算法进行对比仿真，特定的仿真环境为:在该网络中，200个传感器节点被随机分布在200*200的区域内，基站的坐标为(100,350),PacketLength=4000,ctrPacketLength=100,EDA=0.5nJ/bit,Eelec=50nJ/bit,do=εfs/εmp，εfs=10pJ/(bit*m2),Eo=0.5J，α=2，β=2，λ1=2，λ2=1，λ3=1，ρ=0.2，εmp=0.0013pJ/(bit*m4)。

3.2 仿真结果分析

为使仿真结果更合理，本文做了1000次的仿真，仿真结果为1000次仿真的平均值。

3.2.1 每轮产生簇头数目对比

图3显示了本文新算法和LEACH算法每轮产生簇头数目的对比。在LEACH算法中，每轮产生的簇头数目在7到14之间随机变动;在本文新提出的算法中，簇头数目相对比较稳定。在本文新算法中，由于簇头数目为存活节点数目的5%，随着轮数的增加，存活节点数目逐渐变少，簇头节点的数目也渐渐变少。

3.2.2 无线传感器网络存活节点数目对比

图4显示了传统LEACH算法和本文提出的新算法每轮存活的节点数目对比。从图4仿真结果可以看出，当网络运行到620轮时本文提出的新算法存活节点仍为200个，而当网络运行到120轮时传统LEACH算法就出现了第一个节点死亡的情况，且生存节点曲线明显优于传统LEACH算法。传统LEACH算法在运行到1258轮时，几乎所有节点都已死亡，没有节点存活，而本文新算法依然有20个左右的节点存活。这表明该本文算法很大程度上延长了整个网络的生存周期。传统LEACH算法存活节点数目之所以快速减少，是因为传统LEACH算法的簇头选择机制具有随机性，产生的簇头数目不固定，并且分布不均匀，同时簇头直接和基站进行通信，导致节点能量消耗过快。

3.2.3 平均能量消耗对比

本文新算法和LEACH算法的平均能量消耗仿真结果如图5所示。从图5可以知道，本文新算法的平均能量消耗比LEACH算法要少，有效地利用了传感器节点的能量，节约大量的能量，能量消耗大大降低。

对比结果表明，本文新算法能够使网络消耗的能量更加均匀地分配到所有传感器节点中，从而使无线传感器网络的生命周期得到延长。这是因为在LEACH算法的通信过程中，每一个簇头节点均与基站节点直接进行通信，离基站节点比较远的节点，会消耗更多的能量，这样远距离簇头节点能量的显著下降，导致无线传感器网络能量极不均衡，网络生命周期极短。而本文新算法将无线传感器网络簇头节点均匀分布于在整个无线传感器网络中，使网络的负载更加均衡。其次本文算法采用蚁群优化实现多跳路由来传输数据，这样数据每次传输的距离就短，消耗的能量就少，节点能量能够充分的利用，延长了每一个传感器节点的生存时间。

4 结束语

本文提出了一种新的簇头选择机制，该机制可以保证每轮选出的簇头节点数目比较固定，并且解决了簇头分布不均匀问题。其次本文算法将蚁群优化应用到簇间路由通信中，实现多跳路由来传输数据。仿真结果表明，本文新算法与传统LEACH算法相比具有很大优越性，减低了平均能量消耗，延长了网络生命周期。今后的工作重点是多跳通信模型中路由策略的选择。

摘要：在无线传感器网络路由协议的研究中,能量高效是其首要设计目标。传统LEACH协议产生簇头数目比较随机,并且簇头直接与基站通信导致能量消耗过快。在分析传统和改进LEACH路由协议的基础上,提出了一种簇头数目固定的簇头选择机制,解决了簇头分布不均匀的问题。并且将蚁群优化算法应用到无线传感器网络的路径选择中,利用蚁群的动态适应性和寻优能力,在簇头与基站之间形成一条最优路径进行通信。在Matlab平台下对新提出的算法进行仿真测试实验,实验结果表明,相对于LEACH路由协议,该算法降低了平均能量消耗,延长了网络的生命周期。

关键词：无线传感器网络,能量消耗,LEACH协议,簇头数目,蚁群优化

参考文献

[1]宋飞.无线传感器网络安全路由机制的研究[D].合肥:中国科学技术大学,2009.

[2]HE INZELMAN W,CHANDRAKASAN A,BALAKR ISHNAN H.Energy-efficient communication protocol for wireless sensor networks[C]//Proc of Hawaii International Conference on System Sciences Washington DC:IEEE Computer Society,2000:175-187.

[3]Heinzalman W,Chandrakasan A,Balakrishnan H.An Application Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[4]李闻,林亚平,童调生.传感网络中一种基于蚂蚁算法的分布式数据汇集路由算法[J].小型微型计算机系统,2005,26(5):788-792.

[5]王青正,闵林,郭拯危.基于蚁群优化的无线传感器网络能耗均衡路由算法[J].计算机应用研究,2009,26(12):4716-4723.

[6]Wang Yao,Liu Quan-li,Gao Guan-gen,et al.An Improved LEACH Protocol with Determined Number and Fair Distribution of Cluster Heads[C].International Conference on System Science and Engineering,2012:568-572.

[7]Jiang Du,Liang Wang.Uneven Clustering Routing Algorithm for Wireless Sensor Networks Based on Ant Colony Optimization[C].IEEE Computer Research and Development(ICCRD),2011:67-71.

蚁群路由算法 第6篇

在智能交通系统中车辆导航系统占据重要地位, 通过地图查询、路线规划、自动导航来确定车辆最优行驶路线, 为出行旅游者提供最优路线。车辆导航技术是多学科交叉的结晶, 结合了导航卫星以及目标定位技术等。为了解决动态路由问题, 学者提出了很多算法, 如Dijkstra算法、A*算法等。上世纪90年代蚁群优化 (Ant Colony Optimization) 算法由意大利学者M.Dorigo等人最早提出。由于蚁群算法有较强的自适应性、鲁棒性, 在寻优路径中取得了一系列较好的实验结果。本文基于蚁群算法对路由选择进行研究, 同时避免在路由选择过程中陷入局部极值。

2 路由选择问题的蚁群优化算法

路由选择问题是运筹学、组合优化等领域中一个著名的难题, 由于其NP难题性质, 迄今尚未能彻底解决。目前求解这类问题的主要方法有模拟退火算法[1,2]、遗传算法[3]、启发式搜索法、Hopfield神经网络算法[4]等。下面简单介绍蚁群基本算法。

设某交通网络中有m辆车, 每辆车有以下特征:车辆根据以地点距离和路段上外激素的数量为变量的概率函数选择下一个地点 (设τ (t) 为t时刻路段e (i, j) 上外激素的强度) 。规定车辆不允许转到刚刚到过的地点, 有禁忌表控制 (设tabus表示第s辆车的禁忌表, tabus (k) 表示禁忌表中第k个元素) 。它完成周游后, 车辆在它每一条访问的路段留下外激素。

2.1 导航系统选择下一路段规则

初始时刻, 各条路段上的信息激素相等, 设τij (0) =C (C为常数) 。车辆s (s =1, 2, …, m) 在运动过程中, 根据各条路段上信息量决定转移方向, psij (t) 表示在车辆s由点i转移到地点j的概率。

其中alloweds={0, 1…, n-1}-tabus表示车辆s下一步允许选择的交通地点, tabus (s=1, 2, …, m) 用于记录车辆s当前所走过的地点, 集合tabus随着进化过程做动态调整。 ηij表示路段 (i, j) 的能见度, 利用启发式算法算出, 一般取, dij表示地点i与地点j之间的距离。α表示轨迹的相对重要性, β表示能见度的相对重要性。

2.2 信息更新规则

设ρ表示信息的持久性。1-ρ理解为信息衰减度。随着时间的推移, 以前留下的信息逐渐消失, 用参数1-ρ表示轨迹信息消逝度, 经过n个时刻, 车辆完成一次循环, 各路径上信息量要根据以下公式调整:

△τsij表示第s辆车在本次路由中留在路段上ij的信息量, ∆τij表示本次路由路段ij上的信息量增量, Ls表示第s辆车路由路径的长度, Q常数。

2.3 车辆导航系统路由蚁群算法的基本步骤

(1) 初始化迭代步数nc←0 以及τij和∆τij的值, 将m辆车随机置于n个地点上;

(2) 将各辆车的初始出发点置于当前解集中, 对每辆车s (s= 1, 2, ..., m) , 按概率pkij移至下一地点j, 将地点j置于当前解集;

(3) 计算各车辆行驶的路径长度Ls (s = 1, 2, ..., m) , 记录当前的最好解;

(4) 按更新方程修改轨迹强度;

(5) nc←nc+1;

(6) nc<预定的迭代次数且无退化行为 (即找到的都是相同解) 则转 (2) ;

(7) 目前最好解。

3 实验仿真

参数设置:迭代步数nc ≤ 200;

假设从出发地到目的地途经31 座城市, 这31 座城市加上出发地和目的地都是相互连通的, 这31 座城市分别编号1, 2, 3, ......, 31, 它们坐标依次定义如下:

B=[1300 2300;3630 1310;4170 2240;3712 1399;34881535;3326 1556;3238 1229;4196 1004;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;37151678;3918 2179;4061 2370;3780 2212;3676 2578;40292838;4263 2931;3429 1908;3507 2367;3394 2643;34393201;2935 3240;3140 3550;2545 2357;2778 2826;23702975];

利用Matlab对以上述蚁群算法进行仿真结果如图1。

通过算法求得途中这31 座城市最优路径为:1, 15 , 14, 12, 13, 11, 23, 16, 5 , 6, 7, 2, 4, 8, 9, 10, 3, 18, 17, 19, 24, 25, 20, 21, 22, 26, 28, 27, 30, 31 , 29。从上图可以看出当算法迭代次数超过75次后, 最优路径长度已经基本保持不变了, 求得为1.5590e+004。

参考文献

[1]王凌.智能优化算法及其应用[M].北京:清华大学出版社, 2001:195-211.

[2]高国华, 沈林成, 常文森.求解TSP问题的空间锐化模拟退火算法[J].自动化学报, 1999, 25 (3) :425-428.

[3]谢胜利, 唐敏, 董金祥.求解TSP问题的一种改进的遗传算法[J].计算机工程与应用, 2002, 38 (8) :58-60.

蚁群路由算法 第7篇

网络优化问题是一类特殊的组合优化问题, 属于NP难问题。对于此类NP问题, 传统运筹学的优化方法显得无能为力, 寻找、研究、应用启发式智能化的优化方法显得尤为重要。蚂蚁算法就是其中一种有效的启发式智能优化算法[1,2,3,4,5]。

许多学者把蚁群算法应用到路由优化和负载平衡中以解决问题。如文献[4]把局部信息素和全局信息素的更新规律应用到多路路由中, 局部更新机制从而提高了收敛速度, 优化了网络效率, 仿真试验证明都能够较快的找到路由。但该方法在路径求解中的精度和效率受到一定的限制。

根据网络路由优化的最优路径求解问题, 本文提出一种基于改进的蚁群算法的网络优链路搜索方法。利用蚁群的正反馈性, 依据信息素浓度随机且有效选取下一个节点, 快速选出最短路径。实验结果表明, 本文方法与原始蚁群算法相比能够达到较高的精度要求, 并减少了时间损耗, 提高了传输效率。

1 蚁群算法与原理

1.1 蚁群算法的定义

蚁群算法 (antcolonyoptimization, ACO) , 又称蚂蚁算法, 是一种用来在图中寻找最优路径的技术。它最早出现在1992年Marco Dorigo的博士论文里, 其灵感来源于蚂蚁在寻找食物过程中发现路径的行为[5]。

蚂蚁在觅食的过程中, 能够分为搜索食物和搬运食物两个环节, 每个蚂蚁在运动过程中都将会在其所经过的路径上留下信息素, 而且能够感知到信息素的存在及其强度, 比较倾向于向信息素强度高的方向移动, 同样信息素自身也会随着时间的流逝而挥发, 显然某一路径上经过的蚂蚁数目越多, 那么其信息素就越强, 以后的蚂蚁选择该路径的可能性就比较高, 整个蚁群的行为表现出了信息正反馈现象。蚁群算法示意图如图1、2所示。

1.2 蚁群算法实现流程

假设有m只蚂蚁, 将它们随放入到n个城市当中。bi (t) 表示t时刻位于城市i的蚂蚁个数, 那么蚂蚁的总数目计算公式:

di j为点i和点j之间的距离 (i, j=l, 2, 3, …, n) 。ηβi j:表示由点i转移到点j的期望程度, 一般采用, τi j (t) 表示t时刻在ij连线上残留的信息素含量, 在初始时刻, 设下τi j (t) =C (C为常数, 代表未开发路径 (不含信息素的路径分支) 对蚂蚁的吸引度, C越大, 则需要越高的信息素浓度来影响蚂蚁的下一步选择。

实验表明, 当α≈2, C≈2时, 该概率模型与实际相符, 在各条路径上信息量相等。蚂蚁k在运动过程中, 根据各条路径上的信息量决定转移方向。

Pki j (t) 表示在`时刻蚂蚁k由节点i转移到节点j的概率, 由式子看出di j越小, 则ηi j越大。P ki j (t) 也就越大。在t时刻蚂蚁由位置i转移到位置j的概率为:

禁忌表tabuk (k∈1, 2, …, m) 来记录蚂蚁k目前已经走过的点[5,6,7,8]。

其中, α是一个正的常量, 表示蚂蚁选择路径的过程中受信息素的影响程度。

信息启发式因子α是一个正的常量, 表示蚂蚁选择路径的过程中受信息素的影响程度。太大的α会过度增大信息素的影响, 尤其是初期随机的信息素浓度, 从而会导致算法快速收敛到次优路径。与真实蚂蚁蚁群不同, 人工蚁群具有一定的记忆功能, 用其中ρ表示信息素的保留率, 随着时间的推移, 以前留下的信息逐渐消逝, 用参数 (1一ρ) 表示信息消逝的程度, 经过N个时刻, 蚂蚁完成一个循环。

蚁群每完成一次环游, 各路径上的信息素含量调整公式:

ρ的取值范围为ρ奂 (0, 1) , 可以防止信息素的无限积累。其中Δτi j表示本次循环中留在路径上ij的信息量。Δτki j表示第k只蚂蚁在本次循环中留在路径上ij的信息量, 代表相应的路径的优良度。

根据信息素更新策略的不同, 多戈里给出了如下所示的三种不同模型[8]。

ant-cycle模型为:

ant-quantity模型:

ant-density模型:

Lk为第k只蚂蚁在本次路径搜索中所途经路径的总长度。Q是指蚂蚁在搜索时在所经过的路径上释放的信息素总量。

信息素总量Q较大时, 正反馈性能得到加强, 己经遍历过的路径上信息素的累积速度将加快, 算法的收敛速度也会加快。

试验证明求解TSP问题时, 后两者模型中, 蚂蚁每次从前面的一个节点移动到下一个节点后, 就马上对刚才所经过路径进行信息素更新, 这种在搜索过程中单体进行的更新属于局部更新。

由于ant-cyde算法采用信息素全局更新的策略, 较其他算法能较好的克服蚁群算法的缺陷, 而且性能优于另外两种算法, 因此它就取代另外两种蚁群算法被称枷system了[8]。算法的具体步骤如下:

(1) 初始化。设置初始时间t=0、最大迭代次数NCmax=200, Δτi j (0) =0, Δτi j (0) =c, 将m只蚂蚁随机放入n个点当中; (2) 设置循环; (3) 蚂蚁以概率P ki j (t) 选择点, 下一个点j; (4) 移动蚂蚁到下个点j, 并保存点j, 更新tabuk; (5) 若遍历完m只蚂蚁, 则转到第6步, 否则转到 (3) ; (6) 更新每条路径上的信息量; (7) 若达到最大迭代次数则循环结束, 输出结果, 否则转到 (2) 。

2 改进的蚁群算法

由于传统蚁群算法利用随机选择策略, 使得进化速度较慢, 针对蚁群算法加速收敛与早熟、停滞现象等的矛盾, 在结合前人研究的基础上, 本文将提出对蚁群算法的改进称为精英策略[9]。

基本思想是:在每次循环结束后即对所有已经发现的最优解给予额外的信息素增强, 其目的是为了使到目前为止所找出的最优解在下一次循环中对蚂蚁更具有吸引力[8,9]。

在实际解决问题的时候, 很多情况下并不需要找到最精确的那个最优解, 而是要在尽量短的时间内找到比较接近最优解的可行解。正反馈正是强化了蚂蚁选择路径的学习能力, 将尽量多的蚂蚁吸引到目前找到的较优路径上来。

设每次迭代后, 第k只蚂蚁对于其经过路径上的信息素浓度改变为:

为了更快地找到接近最优解的可行解, 增强算法的收敛性, 在每一次迭代后, 将蚂蚁分为3类:遍历路径小于当前最优路径的、等于最优路径的和大于最优路径的。然后, 采用精英策略, 强化找到优于当前最优路径的蚂蚁对信息素浓度的影响, 同时消减找到差于当前最优路径的蚂蚁对信息素浓度的影响。将式 (7) 修改为:

设当前记录的最优解为best L:

经实验证明, ek设置合理, 可以稳定地在非常短的时间内达到较接近最优解的可行解。ek取不同参数值时对收敛速度的影响, 即其能够得到的最优解及所经历的迭代次数。

3 实验与分析

在实际网络路由传输数据报文时, 对最佳路径的选择更为复杂, 需要综合考虑带宽、费用、时延、差错率等因素, 在本文设计中为了简化算法, 以各节点之间的物理距离作为相应链路的时延来对待, 这样并不失正确性, 算出的最短路径长度就是链路时延的大小, 并以此来更新信息素的值。

改进的蚁群算法求解TSP问题的实验结果如下图:其中, 红色线为改进算法;蓝色线为原始蚁群算法。

从图中大致可以得出数据, 运用改进蚁群算法的精英策略求解速度比蚁群算法提高了约40% (横向指标) , 最优解的精度提高了约30% (纵向指标) 。

采用本文提出方法进行网络路由优化的仿真结果如图4所示。从仿真实验可以看出:采用本文方法进行路由优化具有较好的收敛性, 且蚁群算法中各个参数的作用是相互制约又紧密联系的, 其中对算法性能起着主要作用的是信息启发式因子、期望启发式因子和信息残留等三个参数。总信息量Q对算法性能的影响则需要依赖于三个参数的配置以及对算法模型的选取。

4 结论

为提高网络路由优化算法的性能, 提出一种基于改进的蚁群算法的路由搜索方法。在原始蚁群算法基础上, 利用信息表的增强, 根据正反馈性进行最优解的搜索。实验结果表明, 提出的方法在满足精度要求的同时减少了时间损耗。

摘要：随着网络日趋复杂, 网络路由优化问题成为一个难点。本文针对在不同网络如何保证服务质量的问题, 提出基于蚁群算法的网络优链路搜索算法。利用蚁群的正反馈性, 依据信息素浓度随机且有效选取下一个节点, 快速选出最短路径。仿真结果表明, 提出方法与原始蚁群算法相比, 在路径求解速度中提高了约40%, 最优解的精度提高了约30%, 改善了网络的传输效率。

关键词：路由优化,蚁群算法,最短路径,精英策略

参考文献

[1]王剑, 李平, 杨春节, “蚁群算法的理论和应用”, 机电工程, 2003 (5)

[2]Quan Gan;Qiong Qiong Sun.Research on the QoS Routing Protocol Based on ACO Algorithm.Applied Mechanics and Materials.2013.Vol.336-338.pp:1818-1822

[3]朱庆保, 杨志军, 基于变异和动态信息素更新的蚁群优化算法·软件学报, 2004 (2) .

[4]霞“MAX-MIN蚂蚁系统算法及其收敛性证明, I, 计算机工程与应用, 2006 (8.)

[5]侯文静, 马永杰, 等.求解TSP的改进蚁群算法.计算机应用研究, 2010, 6:2087—2089.

[6]孙力娟, 王良俊, 王汝传.改进的蚁群算法及其在TSP中的应用研究[J].通信学报, 2004 (10) :111-117

[7]Luneque Silva Junior;Nadia Nedjah;Luiza de Macedo Mourelle.Routing for applications in NoC using ACO-based algorithms.Applied Soft Computing.2013.Vol.13 (5) .pp:2224-2231

[8]屈建伟.QoS多播路由算法及仿真研究[D].武汉理工大学, 2005

蚁群路由算法 第8篇

本论文采用全动态组网技术,利用蚁群算法和令牌机制,提出一种高效、可靠的中继路由搜索算法,使得系统中每个节点都可以自动成为中继节点,保证系统长期稳定可靠,完全免维护。

1 电力载波自动抄表系统的网络拓扑结构

目前,大部分AMRS都采用分布式体系结构,它是一个基于星型和树型混合拓扑结构的典型低压电力线载波通信网络[5],其中计算机管理中心与集中器之间采用星型连接结构;集中器与电表之间采用树型拓扑结构。在理想的状态下,连接在同一根总线上的集中器和电表之间是可以直接通信的,并且通信的距离没有限制。另外由于低压配电网三相之间的衰减较大[11],在没有相间耦合器的情况下,低压配电网三相之间可以看作并列且相对独立的逻辑关系[6],因此研究其中某一相的逻辑拓扑结构具有代表意义。

2 蚁群算法在电力载波抄表系统中的算法描述

蚁群算法是模仿自然界中蚂蚁寻食路径的一种仿生算法,采用正反馈机制实现分布式全局优化[8]。蚂蚁在寻食过程中通过遗留的信息素帮助蚁群进行消息的传递,指导其他蚂蚁的运动方向,使得某一路径上的蚂蚁数越多,信息素值就越大,后面的蚂蚁选择该路径的机会就越大,最终收敛于最优路径上[9,10]。根据电力线载波通讯网络的特点,结合蚁群算法,提出一种基于蚁群算法的自动路由组网算法。

2.1 自动路由组网算法

第一层子网:

组网的初始阶段,集中器向n个节点发送探索数据包(即人工蚂蚁),假设有m个节点收到探索数据包(1mn),这些节点发送应答数据包给集中器,集中器记录各应答数据包,并根据收到数据包的先后顺序分配相应逻辑地址及优先等级(越往后收到的数据包其优先等级值越小)。已经获得逻辑地址的节点将不再参与新地址的分配。集中器路由表记录m个节点的逻辑地址及优先等级,定义m个节点的网络层次为1,第一层子网组网结束。

第二层子网:

对于剩余的n-m个节点,由于集中器发送的探索数据包无法直接到达这些节点,利用第一层子网中的各节点作为中继节点实现第二层网络组网。集中器发送组网数据包给第一层网络中所有节点,通过m个节点向剩余n-m个节点发送组网信息,假设一级子网中某一节点x1成功联系到剩余节点g1,g2(1g1,g2n-m),x1记录g1和g2信息,并将路径信息返回给集中器,集中器刷新路由表并且分配g1,g2相应的逻辑地址;。第二层网络组网结束后,集中器的路由表记录一级和二级网络中各节点的逻辑地址及相关的路由信息,规定这些节点的网络层次为2。

第三层及以后的组网方法:

可以参考第二层组网方法,直到集中器搜索到全部节点且路由表记录n个节点逻辑地址和路由信息,初始化组网结束,其形成的逻辑拓扑结构如图2。

因此,在初始化组网后可以得到以下结论:设集中器记录形成一级网络节点个数为y1(1y1n),二级子网的网络节点个数为y2,并且通过二级网络连接的三级网络节点个数为y3,,当所有的节点都组网成功后,有

2.2 具体组网算例

设某相系统由1个集中器和16个节点组成。利用蚁群算法自组网络后,可以构成如图2所示的结构。集中器发送探索数据包分别被5,6,7,8等4个节点监听到,四个节点向集中器发送应答数据包,集中器接收应答数据包,在路由表中记录它们的相关信息分配相应的逻辑地址并且定义4个节点的网络层次为1;第二步,集中器发送组网信息给一级子网中的节点,各节点转发信息给剩余的11个节点,其中5联系到15,5记录15的相关信息,并将结果转发集中器,集中器分配15相应的逻辑地址并在路由表中记录路径信息。通过一级子网中4个节点的信息转发,分别联系到15,16,17,18等4个节点,集中器定义这些节点的网络层次为2,第二层子网产生;重复上面步骤,搜索第三层网络中的节点,,直到集中器对16个节点都搜索完毕,初始化组网结束。集中器和每一个节点都存储相关的路由链表,记录该节点所管辖的所有节点的物理地址和逻辑地址以及网络层次,路由表的长度和复杂度由网络节点个数和网络层次数目决定。图3表示为在经过蚁群算法实现自动网络后形成的三相电力线通信网络逻辑拓扑结构。

2.3 蚁群算法在自组网络中出现的问题

1)由于电力线载波是使用扩频通信的调制方式,通信时载波频率相同,因此线路上只能有一组节点在通信,如果不加以改进直接使用蚁群算法会产生载波冲突问题[12];(2)节点上的CPU运算能力有限,不易使用CSMA/CD等技术在节点上解决载波冲突问题[13,14],因此引入令牌机制。

3 引入令牌机制的改进蚁群算法

3.1 令牌机制

令牌法(Token Passing)又称许可证法,它利用单向令牌作为介质访问控制的方法。在低压配电网中通过一个单向令牌帧作为网络传送数据的“令牌”(许可证),如果网络中某一节点要发送信息包,该节点只有获得令牌才能传输数据。

3.2 改进算法

3.2.1 组网的初始阶段

组网的初始阶段,集中器向n个节点发送探索数据包,设k个节点(1kn)收到探索数据包后这些节点将网络信号强度和物理地址等相关信息返回给集中器,集中器按照应答数据包到达的先后顺序和信号强度分配相应的逻辑地址和优先等级(最先收到信息并且信号强度最强的节点其优先等级最高)。对于剩余的n-k个节点,集中器发令牌给优先等级最高的节点x1,由该节点在规定的时间片内作为中继节点对剩余的n-k继续组网,当时间片结束,集中器收回令牌,并对连接到的节点分配逻辑地址记录其路由信息;然后集中器继续对优先级次之的节点发送令牌,继续组网,直到所有的节点都分配相应的逻辑地址,组网的初始阶段完成。

3.2.2 网络优化算法

第一步:簇头诞生

集中器向一级子网中所有节点发送“竞选簇头”数据包,各节点返回网络信号强度、历史抄送概率等相关信息给集中器,集中器比较这些信息,若某一节点信息值大于规定的阈值,就将该节点定义为簇头,否则释放该一级子网节点,并在接下来的时间段内选择加入某一个簇。设集中器在n个节点的网络中定义了t个簇头(1tn,tk),记录这些簇头的相关信息及优先等级并且发送“竞选成功”信息包给t个簇头,获得簇头标志的节点具备组网的权利。

第二步:簇的形成

集中器发令牌给优先等级最高的簇头节点x1,在规定的时间片内,该簇头获得组网的权利,它发送“重新加入簇”数据包告知其下所有节点,非簇头节点根据与簇头的网络信息强度决定是否加入或放弃该簇头,若信息值大于某个阈值,则加入该簇头,否则放弃而投入其他簇头。设在剩余n-t个节点中有y个节点(1yn-t)响应x1,x1根据接收到的节点的先后顺序将应答信息顺序返回集中器,集中器记录x1下所有可以连接到的节点,分配相应的逻辑地址并刷新路由表,当时间片结束后,集中器收回令牌,第一个簇产生。对于其它的簇头,其组网方法与簇头X1的方法一样。当所有簇头组网结束后,集中器检查所有节点是否都入网。,继续该步骤,优化网络,保证所有节点入网并且数据都能成功抄送。图4表示经过竞选后产生的分簇网络模型。

3.3 网络重构算法

第一种情况:设某一簇头x1发现其下某一节点h无法联络。x1向集中器发送异常消息,由集中器判决并发起局部网络重构消息:

步骤1:集中器向所有簇头发出网络重构消息。

步骤2:各簇头节点接收该消息,获得令牌后在规定的时间片内转发重构消息,避免信道冲突,记录簇内成员的逻辑地址并报告集中器。

步骤3:设有若干个簇头获得节点h的相关信息并返回集中器,集中器根据各簇头反馈的信息值比较其大小,筛选网络信号强度最大的簇头作为其上级,分配相应的逻辑地址,完成该丢失节点的网络重构。

第二种情况:设集中器无法抄收某一簇头x1以及其下所有节点的相关信息(假设共有k个节点),集中器向各簇头节点发送局部网络重构消息:

步骤1:集中器收回x1的簇头权力,发送“竞选簇头”的消息给k个节点,按照簇形成的方法进行局部网络的重新组网,竞选出新的簇头,通过新的簇头连接其它的节点。

步骤2:集中器记录新簇的所有信息,若发现还有节点没有组网成功,发送异常消息给其它的簇头,通过其他簇头连接节点,直接所有节点都入网成功。

由于电力线高噪声、高衰减、高时变[12]等特点,任何时候系统中的任何节点都可能发生路由失败而导致网络重构。经过网络重构算法后的路由都是节点间信号强度综合指数为最大值的路由。理论上,随着节点路由重构算法的逐步进行,网络内节点的路由将得到优化。

4 结论

1)本文分析了电力线载波自动抄表系统的网络特性,提出了基于蚁群算法的自动路由算法来实现动态组网,使得在集中器下建立树型拓扑结构通信网络成为可能。

2)受电力线载波使用扩频通信的调制方式以及节点上CPU运算能力有限等限制,引入令牌机制来解决节点上载波冲突问题。只有获得令牌的节点才能自动组网。

3)通过竞争机制筛选网络信号强度强的节点作为簇头,搜索最优路径,使得在组网过程中中继节点数目相应减少,收敛到最优路径的速度有所提高。

4)组网过程中存在节点丢失等问题在不影响其它节点抄送情况下可以利用局部网络重构的方法来解决。当节点数目较多时,会导致延时,但是对于时时性要求不高的抄表系统,以一定的时间消耗为代价来获得通信的可靠性是必要的。

由于电力线载波通信网络规模较大,通常情况下集中器所辖范围内会连接1000个左右节点,为了保证自动抄表的可靠性和完整性,自组网络是必要的。文中提出的算法可能不是很精确,但是反映了载波通信的基本特性,对后续的工程应用及进一步研究提供参考。

摘要：电力线载波自动抄表系统具有物理拓扑结构复杂多变和电力线高噪声、高衰减、高时变[11]等特点,使得在自动抄表过程中出现漏抄、错抄等现象,为提高电力线载波通信系统可靠性,在蚁群算法的基础上利用令牌机制方法使得在自动组网过程中避免信道冲突,系统中的每个节点都能成为中继节点,保证通信网络的可靠性和有效性。