基于改进蚁群算法的无线传感网络路由算法研究

张文柱，孔维鹏，高 鹏，孙瑞华

(西安建筑科技大学 信息与控制工程学院，西安 710055)

0 引言

无线传感网络(wireless sensor network，WSN)通常由大量相对较小的节点组成，每个节点配备有传感设备。大多数传感网络使用无线通信，节点通常由电池供电，且不可更换，一旦中断，将对网络的传输造成很大影响。WSN由传感器节点和汇聚节点组成。传感器节点负责收集和转发数据，汇聚节点在本地分析数据并将数据转发到基站(BS)。无线传感网络与有线传感网络的关键区别在于，无线传感网络中的传感器节点仅依赖于自己的电池，因此功率、能耗、计算能力、储存资源都是有限的[1]。所以如何降低网络的能量消耗，延长网络生命周期成为该领域的重中之重。

针对上述问题，已经有许多专家学者对目前的路由算法进行改进，文献[2]提出的ARA算法是最早将蚁群算法应用到移动自组织网络中，该算法减少了数据包类型，在节点信息素低于某个值时自动进入休眠状态以减少不必要的能量消耗，但是该方法会产生冗余节点，增加算法的复杂度并产生无关路径。随后提出的IARA算法考虑到了邻域冗余节点并进行筛选，并用角度和距离来限制节点间的传输，避免了无关路径的产生，但是该算法在路径决策时，增加了算法复杂度，收敛速度较慢。文献[3]提出了基于改进蚁群算法的分簇路由协议LEACH-VA，它利用几何关系将蚂蚁的数据包结构、信息素更新规则进行改进，并在簇内运用多跳的路由传输方式，而且前向蚂蚁具有收集跳数和所经过路径对其他路径的负反馈条件，综合多因素来调整路由，得到全局最优解。但该算法存在频繁的动态分簇导致能量消耗过多。文献[4]提出一种基于蚁群算法的能量有效路由协议EEABR，将节点平均剩余能量和跳数加入到信息素增量中进行信息素更新。但是在信息素更新过程中，离Sink节点较近或者一些节点分布密集的区域存在频繁的数据传输，仅仅靠增量公式的计算更新信息素不够精确而且会消耗更多的能量。而且由于数据包中只有两条节点的信息，容易形成环路，不利于能量的均衡。IEEABR针对EEABR存在的问题进行改进，分别定义前向蚂蚁和后向蚂蚁的数据结构；启发函数中加入邻域节点的剩余能量，增加了高能量节点成为下一跳节点的概率；前向蚂蚁和后向蚂蚁采用不同的信息素更新，使后续蚂蚁优先选择剩余能量较高的节点。但是由于信息素的更新是一个正反馈过程，这会导致大量蚂蚁聚集在最佳路径导致节点能量消耗过高而死亡，而非最优路径上的信息素浓度逐渐降低，出现荒废路径且有充足能量。

综合考虑多种路由算法，本文提出一种新的基于改进蚁群算法的路由算法。在网络结构方面，加入网络分隔带和搜索角，并结合节点剩余能量，共同限制下一跳节点的转移概率；同时改进启发函数，加入能量影响因子，增强算法寻优，避免陷入局部最优；在信息素更新方面，引入阈值机制并设立最优路径权重值来寻找最优路径。

1 无线传感网络模型

1.1 网络模型

为了简化无线传感网络的节点，对每个节点进行以下假设：

假设监测区域为一个二维平面区域，N个传感器节点随机分布在该区域，且只有一个基站。任何一个节点都能被监测到，并且拥有唯一的ID号：1,2,3,4,5,n,同时与Sink节点构成一个集合N={n1,n2,n3…,sink}。每个传感器节点的通信半径、感知半径、初始能量都是相同的，节点被部署后，网络拓扑结构将不再发生变化。在信息传输过程中，传感器节点与Sink节点将不会有能量补充，且Sink节点具有无限的能量。用于发送和接收信息的的无线链路是对称的[5-6]。

1.2 数学模型

无线传感网络可以被看成一个赋权无向图，由式(1)表示出：

G=

(1)

其中：V表示无线传感网络的节点集合，E表示无线传感网络的通信链路集合。

V可以具体表示为：

V={v1,v2,…,vn,vsink}

(2)

上式中，表示无线传感网络的Sink节点，其他节点用表示。

E可以具体表示为：

E={e1,e2,e3,…,en}

(3)

假设无线传感网络的节点有效传输距离为，代表传感器节点a、b之间的距离，E将进一步表示为：

E={ei|D(va,vb)≤R0,va,vb∈V}

(4)

在无线传感网络中通过以下公式来判断两个节点之间的有效链路是否存在，可表示为：

(5)

式(5)中，当i，j之间存在在有效链路时表示为1，否则表示为0。

1.3 能耗模型

对于能量有限的无线传感网络，节点能耗主要集中在节点的发送和接收状态下，WSN的路由算法设计与信道能量损失模型密切相关[7]，因此本文采用的能耗模型如下。

其中，节点i到节点j传输数据过程中消耗能量的具体公式如下：

(6)

其中：d是通信距离，k的单位bit，是节点发送数据包的长度；Eelec指收发电路的功耗系数，εfs和εamp分别是自由空间和多径衰减信道模型功率放大器的能耗系数；d0为阈值，由以下公式表示：

(7)

节点收发1 kb数据传感器节点的能耗为：

Erv(k,d)=k*Eelec

(8)

由以上公式可以看出，数据传输过程中消耗的能量主要由传输距离和经过的节点数目决定。

2 改进的WSN路由优化模型

2.1 基本蚁群算法介绍

蚁群算法(ant colony algorithm，ACA)是通过观察自然界中蚂蚁的觅食行为而启发产生的群智能算法[8]。大量的蚂蚁会从不同的路径去寻找食物，寻径过程中每只蚂蚁会释放信息素来记录走过路径的信息，后续的蚂蚁会更倾向于选择信息素浓度较高的路径，这样源节点和目的节点之间的较短路径由于经过的蚂蚁数量较多会有更高的信息素浓度，所以经过大量的蚂蚁寻径，就会产生一条最优路径。该算法所具有的自组织性、并行性和正反馈性适用于在无线传感网络中寻找最佳路由。

在无线传感网络中，假设节点的个数为n，蚂蚁的个数为m，采用蚁群算法对WSN进行优化，主要算法步骤如下。

1)假设当前寻径蚂蚁为k，此时蚂蚁正位于i节点，它转移到下一节点j的概率为Pij(t)，公式如下：

(9)

(10)

其中:dij表示节点i和节点j之间的距离。

2)当蚂蚁k完成觅食之后，需要更新它所经过路径的信息素浓度，用公式可以表示为:

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

(11)

(12)

上式中，ρ表示信息素的蒸发系数，且ρ∈[0-1],1-ρ则表示信息素持久性系数，信息素的浓度会随着时间的推移不断蒸发，从而调节路径上的信息素浓度平衡。其中，信息素浓度更新采用蚁周系统[9](Ant-cycle System)，是在蚂蚁到达目的后进行信息素浓度的调整，即

(13)

式中，Q为常数，Lk表示蚂蚁k在此次寻径过程中的路径总长度。

2.2 改进蚁群算法的设计

基础蚁群算法的局部寻优能力较强，但全局搜索能力较差。当算法运行一段时间后，会出现停滞不前，且搜索速度也会相应的降低。为了提升最佳路径的搜寻速度，在其已有优势的基础上进行改进，来获得性能更好的蚁群算法。

2.2.1 网络分隔带和搜索角

经典蚁群算法里蚂蚁的下一跳由转移概率函数决定，这种概率取决于下一跳节点对蚂蚁的启发作用、信息素浓度[10]。信息素会随着时间的增加而慢慢挥发，为了及时利用这些信息素，降低网络延迟造成的转移概率不确定性，在蚁群路由优化算法中提出网络分隔带的概念[11]，使寻径蚂蚁能够有目的地寻找下一跳节点，其原理如图1所示。

图1 网络分隔带原理图

假设处于n层的节点i为源节点，它在选择下一跳节点时，只能从当前层n或者邻近层n+1、n-1内的节点进行选择。i的邻近节点只有A，B，C，D，E，F，和j等节点。按照以上规则，i的下一跳节点只能从邻近层的节点中选取，如A，B，C，D，E，F和j等而不能选择G节点。这样能够使寻径蚂蚁尽可能的向Sink节点靠拢，减少不必要的跳数和消耗的能量。

然而，只依赖网络分隔带蚂蚁无法精确的选择最优路径，因为在下一跳节点选取的时候并没有考虑该节点是否靠近Sink节点，所以有可能选择与Sink节点相反方向的节点。所以在网络分隔带的基础上，提出搜索角的概念。其原理如图2所示。

图2 搜索角原理图

图2中，采用源节点i到Sink节点的连线与源节点i到下一跳节点连线的夹角，与距离因子共同限制下一跳的选择，来选择最佳路径方向。夹角通常限制在，角度越小，则寻径蚂蚁从源节点到目的节点之间的距离越接近直线，这样更容易找到最优路径，能量消耗也更少。从图中可以看出θ1最小，那么j节点作为下一跳节点的概率就更大。

2.2.2 改进启发函数

基本蚁群算法早期用来解决旅行商(TSP)问题，仅仅考虑节点之间的距离因素[12]。但是将该算法应用到无线传感网络中，不仅要考虑距离因素，传输方向和剩余能量也要考虑到其中，需要综合以上因素来改进蚁群算法。本文将重新定义新的启发函数，如下公式所示：

(14)

其中:R为节点通信半径；ei为节点i的剩余能量；Ei为节点i的初始能量；ej为节点j的剩余能量；Ej为节点j的初始能量；θ是节点i到Sink节点的连线与节点j到Sink节点的连线的夹角；γ1、γ2、γ3分别代表上式中三项的权重值。θ角的定义由2.2.1给出，如图2所示，搜素角越小，下一跳节点越接近Sink节点，避免了节点回旋，产生不必要的路径。

上式中，改进的启发函数不仅把下一跳节点的能量考虑进去，同时也考虑了发送节点的能量，除此之外，将发送节点的剩余能量与节点之间的传输距离相结合，共同限制下一跳。当节点i的剩余能量很小的时候，距离节点i更近的点将会有更高的概率被选中为下一跳节点，j节点的剩余能量大小和θ角对启发函数的影响力就会减小。由于γ2和γ3的设置值不同，当节点i的剩余能量较多时，j节点的剩余能量和θ角的大小对启发函数的影响力会更高。在无线传感网络工作的初始阶段，各个节点的初始能量都很充足，能量因素对节点的选择影响较小，改进后的启发函数对寻径蚂蚁进行方向限制，减少经过的节点数目，降低传输消耗的能量。

2.2.3 改进能量影响因子

基础蚁群算法中，寻径蚂蚁在确定下一跳时会考虑信息素浓度和路径启发因子，但是没有将节点的能量对路由选取的影响考虑进去，这样会使部分关键节点过早消耗完能量，降低网络性能，缩短网络生命周期[13]，因此在基础蚁群算法中，加入能量影响因子ω，公式如下：

(15)

上式中，ω表示了节点能量对转移概率的影响，E0、Ej分别代表了节点的初始能量和当前剩余能量。由公式可知，节点当前的剩余能量越高，能量影响因子就小，随着网络的运行，节点能量逐步被消耗，能量影响因子变大，蚂蚁下一跳受能量因素影响的概率也逐步变大。

把能量因子引入到转移概率公式中去，如下式所示：

(16)

(17)

以上两个公式分别是先验路径和变异路径选择的概率公式，其中，α、β、γ分别代表信息素浓度、启发函数、能量影响因子的权重系数，系数越大说明下一跳转移的概率受该项的影响越大。其中，q是寻径蚂蚁在选择下一跳节点之前产生的一个随机数，且q∈(0,1]q0∈[0,1]。当q≤q0时，则选择[τij(t)]α[ηij(t)]β[ωis(t)]γ中最大的节点作为下一跳，若q>q0，则按照公式(17)进行下一跳的选择。对于α、β、γ的取值，应该综合考虑，不能有一个因子为零，否则该算法将无法收敛，太大或太小都会影响算法的收敛速度，而且更容易陷入局部最优，当前两项的值较大时，可以酌情降低其系数，将转移重心放在能量因子上，权衡整个网络的每个影响因素。

2.2.4 改进信息素更新规则

在经典蚁群算法中，每个节点的初始信息素浓度均为零，当前向蚂蚁从源节点到目的节点完成信息传输时，目的节点也就是Sink节点会根据寻径蚂蚁所携带的信息计算蚂蚁经过的不同路径长度和路径信息素浓度，把结果反馈给后向蚂蚁，完成信息素的更新。当后向蚂蚁回到源节点时，算法完成一次路径寻优，后向蚂蚁消失，同时产生新的前向蚂蚁进行下一轮的路径寻优，如此循环该过程，直至达到算法设置的最大迭代次数，找到最优路径[14]。

但是由于经典蚁群算法的信息素更新是一个正反馈过程，当前向蚂蚁搜索到最短路径后，那么该条路径上的信息素浓度会增高，会有更多的蚂蚁选择该路径，从而造成最佳路径拥堵，使路径上的节点过早消耗完能量而死亡，而非最佳路径上的信息素浓度逐渐降低，随着算法的进行，导致路径荒废但节点能量却很充足[15-18]。此时算法将会陷入局部最优，导致算法出现过早停滞，为了解决此问题，本文将建立阈值机制来影响信息素浓度的大小，且同时考虑路径的长度，跳数和节点的剩余能量等因素。具体如下所示：

(18)

(19)

参数τmax表示信息素的阈值，Y代表信息素强度，m是蚂蚁的总个数，Lm表示第m只蚂蚁走过的路径，ρ是信息素蒸发系数，ρ∈[0,1]。每次寻优过后，每只寻径蚂蚁各自对应着一条走过的路径，本文将提出一个能够选择最佳路径的权重公式计算所有寻径蚂蚁走过的路径，该公式如下：

(20)

3 改进蚁群算法的流程

3.1 改进蚁群算法的实现步骤

本文提出的改进蚁群算法的实现步骤如下。

Step1:初始化各项参数。在t=0时刻，设置节点初始能量为E0，信息素浓度τij，迭代次数为N=0，运行最大迭代次数为Nmax。

Step2:把m只蚂蚁随机部署在n个节点，直至遍历完这n个节点，每只蚂蚁都有自己的禁忌表tabuk，且每只蚂蚁的tabuk里放置不同的初始地点。

Step3:迭代次数按照N=N+1进行。

Step4:寻径蚂蚁遵循K=K+1进行路径寻优。

Step5:根据网络分隔带、搜索角和节点剩余能量等因素，寻找下一跳节点的最佳路径范围。若产生的随机数q≤q0，则按照下一跳节点概率公式(16)进行节点j转移；否则按照公式(17)转移，其中j∈allowedk。

Step6:更新节点的禁忌表tabuk。

Step7:如果k

Step8:利用公式(20)计算走过路径对应的最优路径度量值。

Step9:继续执行Step4—Step8，直到m只蚂蚁到达Sink节点。

Step10:每轮迭代结束后，比较各路径上的最优路径度量值，将最大返回值所对应的路径当成最优路径，并利用公式(18)、(19)进行信息素更新。

Step11:继续执行Step2～Step10，直到迭代次数N

Step12:输出最优路径。

3.2 改进蚁群算法流程图

改进蚁群算法实现的流程图如图3所示。

图3 改进蚁群算法流程图

4 实验仿真与结果分析

本文改进的蚁群算法的仿真实验选择在Matlab2014b环境中进行，并与IEEABR算法，和IARA算法进行对比。为了确保仿真结果的稳定性与可靠性，取多次仿真结果的平均值。分别从路径的平均跳数、节点平均能量消耗、网络生命周期等3个方面进行对比分析。仿真参数如表1所示，仿真环境设置为100 m＊100 m的区域，随机分布150个节点。

1)路径平均跳数：

路径平均跳数显示了算法的寻优能力，图4显示了IARA算法、IEEABR算法和改进的蚁群算法的平均路径条数的趋势对比图。随着迭代次数的增加，平均跳数渐渐减小并趋于稳定，从图中可以看出，改进蚁群算法的平均跳数始终低于IARA和IEEABR算法，在迭代初始阶段，IEEABR算法和IARA算法的跳数降低较为明显，且收敛速度也相对较快，但是最终的收敛跳数维持在一个较高的水平，这样对网络资源的占用会更高。而本文提出的改进蚁群算法的最终收敛跳数则明显低于以上两种算法，这说明该算法能够减少丢包率，提高网络传输效率，减少路径堵塞。

表1 仿真参数设置

图4 路径平均跳数的对比

2)节点平均能量消耗：

网络节点的平均能量消耗直接影响了整个网络的生命周期，节点能量消耗越小，则网络生命周期越长。图5显示了3种算法的节点平均能量消耗随着仿真时间变化的仿真结果。从图中可以看出，本文提出的改进蚁群算法随着仿真的进行，平均能量消耗始终低于EEIBR和AIRA算法，这得益于本算法考虑到节点能量对转移概率的影响，将节点之间的距离与剩余能量相结合，同时限制了传输方向，避免节点回旋传输，产生与最佳路径偏差较远的路径。

图5 节点平均能耗随的对比

3)网络生命周期：

仿真实验将第一个网络节点的死亡时间定义为网络周期，通过增加节点数量，来对比各算法的网络生命周期。如图6所示，当网络节点数量相同时，EEABR和IARA算法的第一个节点死亡时间总是低于本文所提出的算法，这说明改进的蚁群算法能够有限的延长网络生命周期。这是因为该算法中同时考虑节点剩余能量、路径长度和跳数，同时建立一个能够选择最优路径的权重公式去更新信息素，避免了冗余节点的产生，延长了网络生命周期。

图6 网络生命周期的对比

5 结束语

本文在经典蚁群算法的基础上，提出改进的蚁群算法来解决无线传感网络的路由能耗问题，从网络结构、启发函数、能量因子、信息素更新规则等方面进行改进，解决蚁群算法在无线传感网络中出现局部最优、能量消耗过多、节点过早死亡等问题。仿真实验表明，改进后的蚁群算法能够有效均衡能量消耗，提高节点存活数量，延长了网络生命周期。