基于改进蚁群算法的WSN分簇路由协议的研究

陈 鹏，王向文，孙 充

(上海电力大学电子与信息工程学院，上海 200000)

1 引言

无线传感器网络(Wireless Sensor Network， WSN)是由大量随机分布的微型传感器节点组成的复杂网络系统，可用于接收、处理和传输数据，其应用范围也从原先的军事领域逐渐扩展到工农业生产、环境监测、医学等其它领域之中。然而，这些传感器节点是由其自身携带的电源供电的，由于其体积小，所携带的能量有限，对其充电又十分的不便，所以常常因为某些节点的能量耗尽导致整个网络无法正常运行，严重影响了网络的生命周期。

针对此类问题提出较为经典的是LEACH协议[1]，该协议通过节点产生的随机数与阈值的比较竞选出簇头节点，簇内节点将采集到的数据传输给簇头节点融合后，簇头节点再以单跳的方式将数据转发给基站节点。协议分为分簇和数据传输两个阶段，在分簇阶段由于阈值计算公式过于简单，簇头选择具有很大的随机性，这可能会导致能量不足的节点成为簇头，且簇头分布的密集程度不合理，整个网络的能耗处于不平衡的状态。对此胡峰松[2]等人充分考虑了节点的能量和位置因素，提出了一种能耗相对均衡的多跳路由算法，一定程度上优化了簇头的能耗，延长了网络的寿命。杜永文[3]等人利用模糊算法综合考量节点剩余能量和与基站的距离来计算节点的竞争力，最后根据节点的竞争力采用非均匀分簇方法进行簇首选择。吉正询[4]等人按照节点的剩余能量将网络划分为标准区和警惕区，在不同区域有不同的阈值，节点成为簇头的概率也不同，但由于没有考虑距离的因素，容易出现簇头节点分布过于密集的情况。陈相睿[5]等人将最优簇头个数的概念引入阈值计算公式，同时兼顾了能量和距离的因素使得簇头的分布更加合理。在数据传输阶段传统LEACH协议表现的不足在于传输方式的单一性，许多节点能耗过快死亡大都因为距离基站较远但与基站直接通信，所以建立一条节点到基站的最优传输路径对提高WSN网络的寿命显得至关重要。蚁群算法(Ant Colony Optimization， ACO)在解决路径规划问题上具有良好的表现，近年来国内外学者也在经典蚁群算法的基础上提出了许多优化算法。童孟军[6]等人提出的EEABR(Energy-efficient ant-base routing)算法考虑了节点能量和蚂蚁经过的跳数等因素，优化了信息素增量公式，但由于该算法只保存蚂蚁最近访问的两个节点的信息，易造成蚂蚁环路，无法解决网络的能耗均衡问题。肖铖[7]等人在EEABR算法的基础上改进了启发因子的计算公式，有效地解决了单路径路由节点能耗不均衡的问题。喻小惠[8]等人在状态转移函数中加入适应度因子，使得节点密集度较高的节点成为蚂蚁下一跳的概率增加，但他并没有考虑角度因子，无关路径的访问增加了节点的能耗。金永贤[9]等人将分簇机制和蚁群算法相结合，提出了一种多径路由协议MRPCAC，引入了最优路径选取函数，并在启发式因子计算公式中加入了能量和角度因子，减少了无关路径的访问次数，加快了算法的收敛速度，但算法运行后期容易因信息素的堆积陷入局部最优。

根据上述情况，本文针对LEACH协议表现出的缺陷，在分簇阶段，充分考虑节点的能量、节点到基站的距离和节点的密集程度三个因素，优化簇头的选举机制；在数据传输阶段，通过改进蚁群算法寻找最优传输路径。将伪随机规则加入到状态转移函数中，利用动态挥发系数防止信息素堆积引起算法的局部收敛，同时优化信息素更新规则和启发式因子公式，缩小了蚂蚁的寻径范围。实验表明，本文所提算法能有效均衡网络能耗，提高网络的生命周期。

2 系统模型

2.1 WSN网络模型

无线传感器网络可视为一个二维平面，平面内有一个用于接收所有节点信息的固定基站和n个随机分布的用于采集信息的传感器节点。若v1表示第一个传感器节点，则V=(v1，v2，…，vn，vsink)代表所有节点的集合，其中vsink表示基站节点。节点之间的链路关系可以表示为E=(e1，e2，…，en)，则整个网络的数学模型可以用G=(E，V)表示。为了使算法便于实现，本文提出了如下假设：

1)网络中的节点随机分布且一旦确定位置将不再发生位移。

2)每个节点携带的能量相同且可以根据信号的强度判断节点间的距离。

3)节点的发射功率可以视情况自我调节。

2.1 能耗模型

无线传感器网络节点的能量主要消耗在接收数据和输出数据[10]。

相距为d的两个传感器节点每传输kbit数据所消耗的能量

(1)

节点每接收kbit数据所消耗的能量

Ereceive(k)=k×Eelec

(2)

式中，Eelec是每处理单位数据时电池的耗能；εfs和εamp是两个不同传输模型下的能耗参数；d0为距离阈值，当节点间的距离小于阈值d0时，采用自由空间传输模型，否则使用多路径衰减信道模型。阈值d0的计算公式

(3)

3 改进算法

3.1 分簇阶段

传统的LEACH算法依靠节点产生的随机数与阈值比较决定簇头的与否，而阈值计算公式的值仅与轮数r一个变量相关，因此簇头的分布呈现出很大的随机性。部分区域簇头分布过于密集，剩余能量不足的节点被选为能耗较大的簇头节点等现象对网络的寿命造成极大的影响。因此本文充分考虑节点的能量、到基站的距离以及节点的密集程度，重新构造阈值计算公式T’(n)

(4)

式中，p为簇头节点数占总节点数的比例；r为轮数；Eres为节点i的剩余能量；E0为节点i的初始能量；dtoBS-i为节点i到基站的距离；dto-BS-i-max为节点到基站的最大距离；Nalive为网络中尚未死亡的节点个数；Ni指的是与节点i相距不超过设定半径R的节点个数。

经过改进后的阈值计算公式使得剩余能量占比较高、距离基站较近、邻居节点较多的节点更容易担任簇头，完成簇内与基站之间的数据传输。

在簇头节点选定后，簇头节点向全网络发射广播信号，信号随着距离的增加会逐渐减弱，普通节点根据信号的强弱选择簇头节点并进行入簇。

3.2 数据传输阶段

传统LEACH协议无视距离的远近统一与基站直接进行数据传输，这使得距离基站较远的节点因能耗过大提前死亡，直接影响了网络的正常运行。本文簇内数据传输采取了与LEACH协议一样的单跳方式，而簇头节点与基站之间的数据传输通过改进蚁群算法找寻最佳传输路径。

3.2.1 改进状态转移公式

算法运行的初期，在每条路径上信息素和启发信息都差不多的情况下，蚂蚁很难依靠这些信息做出下一跳的判断，需要一段时间信息素的积累才能避免蚂蚁在进行下一跳选择时的盲目性，故而算法收敛速度较慢。其次，随着算法的推进，蚂蚁越发偏向于最优路径，使得最优路径上的节点因访问次数过多消耗大量的能量而提前死亡，严重影响了网络的生命周期。针对此问题，本文提出一个伪随机原则对状态转移函数进行一定的改进

(5)

式中，q为一个取值在[0，1]的随机数；q0为一个取值在[0，1]的常数；τij(t)为t时刻节点i与节点j路径上信息素的含量；ij(t)为启发函数；α和β分别为信息启发因子和启发函数因子。在蚂蚁每次选择下一跳节点之前，先随机产生一个随机数q与q0比较，若q≤q0，则选择[τij(t)]α[ij(t)]β值最大的节点作为蚂蚁的下一跳，否则按照式(6)进行下一跳的选择

(6)

通过改进的状态转移公式，一方面算法能够在较短时间内收敛于最优解的附近，另一方面是在一定程度上实现了蚂蚁的分流，使得最优路径上的节点不会被过于频繁地访问而消耗太多的能量，从而有效延长了网络的寿命。

3.2.2 改进信息素因子

在传统的蚁群算法中，各个节点的初始信息素浓度均为0，每一只蚂蚁在到达目的节点后都会形成一条可行的路径，并在该条路径上留下信息素，后续蚂蚁会选择信息素浓度较高也就是更多蚂蚁曾经过的路径。这样的正反馈机制势必造成浓度较高的路径信息素增长速度更快，最优路径上的节点被访频率过高而提前死亡。同时非最优路径上的信息素不能得到有效的供给，由于挥发系数的存在会变得越来越少，从而导致某些能量充足的路径被荒废，算法陷入了局部最优。为了引导蚂蚁进行恰当的分流，使整个网络的能耗相对均衡，从而得到更接近于全局最优的解，对此本文将结合能量因子优化信息素的更新方式。

首先，针对某条路径上信息度浓度过高的问题，本文给定了一个阈值τmax，修改后的信息素计算公式

(7)

(8)

3.2.3 改进挥发系数

随着算法的推进，仍不可避免某些路径上信息素堆积而造成的局部最优问题。ρ作为信息素挥发系数，它值的大小也代表了信息素消散的速度。在传统的蚁群算法中，ρ为一个常数，通过对ρ作如下改进

ρ(k)=ρ0·(2-e-λk)

(9)

式中，ρ0是信息启发因子的基本值；λ是一个取值在[0，1]的常数；k代表算法迭代的次数。通过修改后的挥发系数ρ(k)随着算法迭代次数k的增加会越来越大。在算法运行初期，ρ(k)较小，信息素挥发速度较慢，蚂蚁可以更有效的依靠信息素浓度的高低进行路径的选择；算法运行到后期，ρ(k)也会逐渐增大，信息素的挥发速度相较之前会有明显的提升，有效避免了算法后期因信息素堆积引起的局部收敛问题。

3.2.4 改进启发函数

(10)

这种计算方法有失全面性，在蚂蚁进行下一跳选择时，会造成部分蚂蚁选择与sink节点相反的方向，产生大量无关路径。对此，本文引入角度因子对启发函数做出改进

(11)

(12)

式中，λ1，λ2是常数，其大小代表距离和角度在计算启发函数时的权重；θ是节点i与sink节点、节点i与节点j两条连线的夹角，如图1所示；dij，dis，djs分别对应三个节点间的距离。

图1 角度因子θ示意图

通过修改后的启发函数综合考虑了距离和角度的因素，当节点间距离dij和角度θ都比较小时，启发函数ij(t)的值才会较大，蚂蚁选择该节点作为下一跳的概率才会较大，由此有效缓解了蚂蚁的反向寻径问题，无关路径的减少也为节点省下了大量的能量，有效延长了网络的寿命。

4 实验结果与分析

为检验本文算法的实际效果， 在MATLAB平台对LEACH协议[11]、HEED算法[12]和本文算法进行仿真，通过节点平均能耗、节点能耗的波动性和网络寿命三个方面的分析对比验证本文算法的有效性。仿真环境为一个100m×100m的平面区域，区域内随机分布100个初始能量和性能都相同的传感器节点，基站位于区域的中心(50，50)，每个节点每一轮都向下一个节点传输4000bits的数据，蚂蚁数量为50只。仿真参数的设置见表1。

表1 仿真参数设置

由于在实际生产应用中传感器节点的设置并不会非常密集，所以往往部分节点的提前死亡就会出现网络不能完全覆盖的问题，此时网络已经失去了正常工作的能力，因此比较最后一个节点的死亡时间是毫无意义的。在此，本文规定以第一个节点的死亡时间作为网络寿命的评判标准。图2为三种算法在相同环境下，节点存活数量与轮数之间的关系。由图可见LEACH协议和HEED算法分别在第110轮和第140轮出现首个死亡节点，而本文算法在进行到第235轮才出现首个死亡节点，网络寿命明显延长。

图2 网络存活节点数与轮数的关系

网络寿命的延长很大原因在于节点本身能耗的降低，图3显示了三种算法下节点平均能耗的对比图。由图分析可得：LEACH协议和HEED协议节点的平均能耗大约在9.1mJ和8.4mJ，而本文算法中节点的平均能耗仅约6.6mJ，这是因为本文算法对信息素因子、挥发系数和启发函数的改进使得蚂蚁更快收敛于最优解，避免了许多无关路径的访问，减少了许多不必要的能量消耗。

图3 节点平均能耗对比

同时，本文算法也在簇首选举公式和蚂蚁的寻径条件中充分考虑了能量因素，使得整个网络的能耗更加均衡，避免了某些节点某些时刻能耗过快的问题，延长了首个节点的死亡时间，从而提高了整个网络的生命周期，图4为三种算法前100轮节点能耗的折线图，从图中可以清晰地看出本文算法不仅在能耗上相较于另外两种算法更低，而且节点的能耗也相对而言更加稳定。

图4 前100轮节点能耗

5 结语

本文针对传统LEACH协议的不足，在分簇阶段考虑了能量、距离和节点密集程度等因素优化了阈值计算公式，使得簇首的分布更为合理。蚁群算法在寻径问题中的良好表现刚好适用于数据传输阶段的路径规划，出于对降低能耗延长寿命等要求的考虑，本文对蚁群算法做出了一定的改进：在状态转移公式中引入伪随机原则，改进信息素更新方式，利用动态挥发系数，在启发函数中引入角度因子。仿真表明，本文算法可以有效降低节点的能耗，延长网络的寿命。