WSN中基于改进蚁群的能量优化路由算法

蒋占军,周 涛,杨永红

(兰州交通大学 电子与信息工程学院,兰州 730070)

0 概述

无线传感器网络(Wireless Sensor Network,WSN)由大量的微型节点组成,其依靠微电池供电,组网灵活、成本较低,广泛应用于野外监测、抗震救灾等场景中。然而,大部分节点分布在荒野地区,一般情况下无法及时更换[1],一旦节点损坏,将对网络产生重大影响,特别是当关键节点因能量耗尽而失效时,会出现“热点”问题,网络的连通性被破坏而进入瘫痪状态。因此,降低节点能耗、优化网络路由,从而延长网络寿命是亟待解决的一个问题。

针对上述问题,国内外专家学者对原有的路由协议提出许多优化方案。然而,与传统的路由协议相比,WSN通过节点间的主动探索来完成通信任务,但节点的计算和存储能力有限,只能存储相邻节点的路由信息。生物智能算法因其能有效地完成WSN中的分簇与路径规划任务而受到广泛关注。其中最具有代表性的是基于蚁群优化(Ant Colony Optimization,ACO)的WSN路由算法,其利用蚁群的智能功能高效地在复杂的网络拓扑中找到最优路径。此外,ACO具有正反馈、分布式并行计算机制和鲁棒性强等特点,在WSN中易于实现。因此,研究人员通常使用ACO来解决WSN路由中的能量利用问题。

ARA(Ant-based Routing Algorithm)[2]是最早将ACO应用到移动自组织网络中的被动式多路径路由算法。该算法通过减少数据包类型,在节点信息素低于某个阈值时进入休眠模式以节约能量,但节点间存在不必要的网络开销和时延。IARA(Improved Ant-based Routing Algorithm)[3-4]对ARA中的冗余邻居节点进行筛选,采用角度因子和距离因子限制搜索方向,避免无关路径的产生,但该算法的节点计算复杂度高、收敛速度慢。LEACH-VA(Low-Energy Adaptive Clustering Hierarchy Voronoi Algorithm)[5]是一种基于分层结构的路由协议算法,其纯粹利用几何关系改进蚂蚁包的数据结构和信息素更新规则,在簇内运用多跳的路由方式进行传输,引入寻径蚂蚁收集跳数信息以及所经路径对其他路径的负反馈条件,综合多方面因素规划路由,得到全局最优解。但是,LEACH-VA算法存在频繁的动态分簇,导致能量浪费。ARAMA(Ant Routing Algorithm for Mobile Ad-hoc)[6]利用梯度值对节点中的路由表进行更新,其缺点是在大型网络中,随着每个蚂蚁的记忆列表变长,节点间传输蚂蚁包的能耗会增加。EEABR(Energy-Efficient Ant-Base Routing)[7]将节点平均能量水平与蚂蚁经过的跳数引入ACO的信息素增量公式中,并在节点上将蚂蚁携带的信息进行融合,可减少节点传输的数据量。但是,EEABR在蚂蚁靠近Sink节点等较为密集的区域时存在频繁的数据转发,若单纯通过加减运算进行更新,其结果不够准确且消耗的能量较多。此外,由于蚂蚁包中只存放2条节点ID信息,易形成蚂蚁环路,不利于全网能量均衡。IEEABR(Improved Energy-Efficient Ant-Base Routing)[8]在设计报文时,分别定义了2类蚂蚁的数据结构,将邻居节点的剩余能量引入蚂蚁路径的链路启发信息公式中,减少在寻路过程中选择能量较小的下一跳节点概率。在信息素更新公式方面,IEEABR的寻径蚂蚁与回退蚂蚁使用不同的更新公式,引导后来的蚂蚁选择能量较大的邻居作为下一跳。IEEABR的缺点在于ACO中的信息素更新是一个正反馈过程,蚂蚁完成最短路径的搜索后会聚集在该路径上,造成最佳路径节点能量耗尽而过早死亡,而非最佳路径的信息素浓度释放量不断减小。同时,随着时间推移,该算法会导致路径荒废但节点能量充足。

本文在IEEABR算法的基础上,提出一种增强型的能量优化路由算法E-EEABR。在寻找下一跳节点时综合距离带、搜索角度和距离因子3个因素选取下一跳节点,利用激励策略使最优路径周围的剩余能量充足,并通过跳数较少的节点来均衡负载过重的“热”节点的传输任务。此外,采用一种含能量因子的伪随机比例规则策略优化概率转移函数,降低“热”节点失效的概率,以增强算法的寻优能力。

1 蚁群算法原理

ACO算法是指WSN中的源节点通过发送人工蚂蚁来模拟自然界中的蚂蚁。人工蚂蚁在寻找食物的过程中,通过分泌高浓度的信息素来吸引更多的蚂蚁加入到寻径路径中,然后利用算法的正向反馈机制找出一条到达食物的最优路径。在ACO算法中,蚂蚁分为寻径蚂蚁和回退蚂蚁2类。蚂蚁寻径原理如图1所示。

图1 蚂蚁寻径示意图Fig.1 Schematic diagram of ant path finding

假设在WSN寻径的初始阶段,节点个数为m,蚂蚁个数为n,寻径蚂蚁k从源节点出发,通过式(1)所示的状态概率转移公式选择下一跳节点。式(2)表示蚂蚁k对下一跳节点的期望值,一般来讲,距离dij(见式(3))越小,蚂蚁对下一跳的期望值越大。寻径蚂蚁通过彼此间的自主探索,在经过多个节点后抵达Sink节点,然后在Sink节点消亡,生成回退蚂蚁。回退蚂蚁沿着信息素浓度最大的路径回到源节点,完成一次寻径过程。在该过程中,各路径在初始化时被赋予了相同的信息素浓度τij(t)=C且其会以一定的速度挥发。在回退蚂蚁返回更新的信息素时,各路径由于自身距离、剩余能量等因素存在差异,导致计算的信息素增量也不相同,得到较优解的路径拥有的信息素浓度更高,吸引更多的蚂蚁,而剩余路径的信息素则不断挥发。ACO的这种正反馈机制使得蚂蚁可以不断探索最优路径。

(1)

(2)

(3)

目前,蚁群算法基本模型有3种,其信息素更新策略各不相同,主要差别在于Δτij(t)求法不同[9]。本文采用蚁量(Ant-Quantity,AQ)模型,按照式(4)～式(6)进行信息素更新,使路径上的每个节点都能生成一个相应的路由表,其中包含该节点到下一跳节点的相应信息。

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

(4)

(5)

(6)

2 ACO的作用

在ACO算法中,蚂蚁根据信息素浓度、能量等启发式信息来规划最优路径[10]。将ACO应用到WSN中是为了利用ACO的自组织性、正反馈性和鲁棒性等,降低路由过程中的能量消耗[11]。在WSN中引入ACO的原因主要有以下4点:

1)节点能量有限

WSN中的节点能量、存储容量有限,运算资源相对匮乏,在设计WSN路由协议时,需优先考虑路由过程中的节点能耗与负载均衡问题。将ACO引入到WSN路由中,利用其群体智能特征可自主地寻找最优路径,节省节点能量,平衡网络负载。此外,ACO算法简单,更容易实现。

2)自组织网络

WSN的传感器节点通过飞机播撒的方式投放到野外环境中,随机性强且各节点之间无固定的中心,需根据野外环境、拓扑规则以及路由算法,在无人监管的条件下,自主生成一个网络,完成各项任务。ACO中的蚂蚁通过正向反馈原则逐步探索,获取最优路径。在寻径蚂蚁找到最优路径后,会吸引更多的蚂蚁参与到该路径中,可以在得到最优路径的同时,提高节点能量的利用率。

3)网络结构的动态性

WSN中的节点由于能量耗尽或不能及时更换,导致部分节点死亡,加上通信环境和应用场景的变化等因素,使得WSN的拓扑结构会经常发生变化,ACO利用其本身的鲁棒性,能够很好地应对这一情况。在网络拓扑发生变化时,蚂蚁采用启发式的路径搜索方式,及时做出调整并再次寻找最优路径,其适应性较好且反应速度较快。

4)多跳传输

多跳传输是通过多个节点的协助转发到达Sink节点,这种通信方式能够有效地利用全网络资源,尽可能以低能耗、短时延在复杂的拓扑中找到最优路径。在多跳传输的过程中,如何选择合适的下一跳节点是路由算法中影响能耗的一个重要问题。在WSN中引入ACO算法,可以根据节点信息素、剩余能量等因素来进行决策,经过多轮执行后,逐渐接近最优路径,减少寻找最优路径的时间和能耗,平衡网络负载。

3 E-EEABR算法

3.1 网络距离带和搜索角度

在经典的蚁群算法中,蚂蚁下一步的转移由状态转移概率函数决定,该函数取决于下一跳节点对蚂蚁的启发作用和信息素浓度,而信息素浓度的使用导致在寻径后期易陷入局部最优路径[9]。此外,无线传感器节点数量巨大且随机分布,节点会因能量耗尽而失效,同时会有新节点加入通信过程中,使得WSN的网络拓扑经常性发生变动。因此,若蚂蚁在寻找下一跳节点时没有明确的目的,则既浪费了节点能量又延长了寻径时间[10]。为了充分利用有限的节点能量和当前的信息素浓度,在蚁群路由优化算法中引入距离带的概念[11],优化蚂蚁寻找下一跳节点的方式,避免节点的盲目转发,其原理如图2所示。

图2 距离带示意图Fig.2 Schematic diagram of distance band

在图2中,假设处于n层的节点i为源节点,它在选择下一跳节点时,限定只能选择当前层n或邻近层n-1、n+1内的节点,则其邻近节点只有节点A～节点F和节点j。按照上述规则,节点i的下一跳节点只能选择邻近层节点,即节点A～节点F和节点j,而不能选择节点G,即将远离源节点i的节点排除出去。同时,该方法可减少蚂蚁向Sink节点转移的跳数和能耗。由于节点A距离Sink节点较远,节点i下一跳的重点选择对象集中在节点B、节点C、节点D、节点E、节点F和节点j。

然而,依靠距离带只能决定下一跳节点的选择区域,并不能确定最佳路径的方向。现有的蚁群优化算法在选取下一跳节点时,并没有考虑该节点是否靠近Sink节点,导致寻径蚂蚁有时会选择与Sink节点相反的方向,产生无关路径,浪费节点能量。因此,在距离带的基础上引入搜索角度的概念,具体原理如图3所示。

图3 搜索角度示意图Fig.3 Schematic diagram of search angle

本文通过计算源节点i到Sink节点的连线与源节点i到下一跳节点连线的夹角,结合角度因子和距离因子来确定最佳路径方向。搜索角度一般限制在0°～90°,θ越小表示蚂蚁从源节点i到Sink节点的距离越接近直线,在寻径过程中,节点越靠近源节点i到Sink节点间的直线,能量消耗越少,则其成为下一跳节点的概率越大。从图2可以看出,0°<θ1<θ2<θ3<θ4<90°,其中,θ1最小表示节点j成为下一跳节点的可能性最大。

3.2 改进的路径启发函数

虽然上述方案能够精确引导蚂蚁寻找下一跳节点,但是当多个候选节点的角度和距离相差不大时,节点之间会出现回旋式跳转以及能耗不均等问题。尤其是Sink节点附近的“热”节点相比其他位置的节点,更容易因负载过重而导致出现能量“热区”。当这些节点的能量耗尽后,网络的连通性被严重破坏,出现“热点”问题,使网络进入瘫痪状态。“热点”问题的出现在一定的程度上降低了ACO自身的搜索速度和收敛速度,网络的生存周期也受到影响[12]。

为有效地解决Sink节点附近“热”节点的失效问题,本文采用一种激励策略,筛选出能量较低且距离较远的“热”节点,并禁止其加入到传输路径中。同时,把剩余的能量充足且距Sink节点较近的节点加入到传输路径中,以均衡“热”节点的平均剩余能量,延长网络的生存时间。该策略的主要原理如图4所示。

图4 激励策略示意图Fig.4 Schematic diagram of incentive strategy

(7)

假设D、E、Sink节点处在网络节点能量传输负载过重的“热区”中,并且节点D和节点E是利用距离带、搜索角度和距离因子筛选出来的距离Sink节点最近的“热”节点,当节点D、节点E与Sink节点的距离较近时,会存在能耗不均和回旋式跳转等问题。

图5 节点激励值更新示意图Fig.5 Schematic diagram of incentive value update of node

从上述分析可以得出,本文提出的激励值策略与原始ACO算法通过信息素浓度与启发函数的大小进行交流相比,蚂蚁更倾向于更新短路径上的信息。同时,该策略使得蚂蚁之间的交流除了依靠信息素之外,还会参考访问过的节点信息,从而能够平衡Sink节点周围的整体能量水平,促进蚂蚁之间的交流,加快算法的收敛速度。

为更好地利用激励值,避免由于“热”节点的失效而出现网络空洞现象,引导蚂蚁更趋向于Sink节点,本文提出的优化信息素启发公式如下:

Ωi,Sink=di,j+dj,Sink

(8)

(9)

3.3 状态转移公式改进

在WSN路径建立的初始阶段,各路径信息素和启发函数的作用区分不明显,导致信息素对路径建立的作用很小,寻径蚂蚁难以在短时间内搜索到一条到Sink节点的最优路径。大多数现有的改进算法在确定下一跳节点的概率时,只考虑源节点与候选节点的距离以及信息素浓度2个方面,并没有考虑候选节点的剩余能量大小、是否与Sink节点同径等因素,造成长度较短且剩余能量充足的路线被大量蚂蚁频繁访问,节点能量损耗严重,失效节点数目增多[13]。

针对上述问题,本文引入一个含能量因子的伪随机比例(见式(10)和式(11))估测策略来优化状态转移公式[14],使得蚂蚁能够在算法初期各路径信息素和启发信息作用不明显的情况下,快速集中到概率最大的路径上,提高算法的收敛速度。同时,平衡最优路径上节点能量较少但蚂蚁频繁访问的节点的能耗,延长网络寿命,避免算法出现过早停滞的现象[15]。

(10)

(11)

其中,q是寻径蚂蚁在选择下一跳节点之前产生的一个随机数,且q∈(0,1],q0∈[0,1],α、β、γ分别是信息素浓度、启发函数和能量影响因子的权重系数,其数值越大,说明该项被重视的程度越高,Ei(t)表示源节点i的剩余能量,Ej(t)表示候选节点j的剩余能量。若蚂蚁在当前节点产生的随机数q满足q≤q0,则选择[τij(t)]α[ηij(t)]β[κij(t)]γ最大的节点作为下一跳,否则按照式(12)选择下一跳。

(12)

在改进的状态转移函数中,寻径蚂蚁在寻找下一跳节点时,首先根据距离带和搜索角的规则,对源节点附近的节点进行筛选,然后考虑下一跳节点的信息素浓度、剩余能量等影响因素。通过上述两个步骤,进一步优化节点概率选择,避免网络延时、不必要的能耗和局部最优等问题。寻径蚂蚁能够根据自身位置与下一跳节点之间的关系进行自适应调节,使得下一跳能量充足且距离Sink节点较近的节点加入到蚂蚁的最优路径中,避免由于最优路径上节点负载过重导致出现网络瘫痪的问题。

3.4 信息素更新规则改进

寻径蚂蚁从源节点出发到达Sink节点后,Sink节点会根据寻径蚂蚁包携带的信息,计算蚂蚁经过的路径长度以及路径中的信息素浓度,并将计算结果反馈给回退蚂蚁,完成信息素更新。当回退蚂蚁到达源节点后,一次完整的蚂蚁包收发过程结束,同时算法完成一次路由优化,源节点将回退蚂蚁消亡并生成新的寻径蚂蚁进行下一轮的路径寻优,如此重复循环此过程,直至达到算法设置的最大迭代次数,找到最优路径[16]。

然而,从ACO的生物特性上讲,蚂蚁的信息素更新是一个正反馈过程,蚂蚁在完成最短路径搜索后,利用释放的信息素吸引大量蚂蚁加入此路径,造成该最“佳”路径的节点能量耗尽而过早死亡[17]。此外,从算法运行的角度来讲,传统ACO的信息素采用累加的方式,不断地增加上一轮找到的最优路径上的信息素浓度,导致算法容易陷入局部最优,而不是全局最优。特别地,对于Sink节点附近分布比较密集的“热”节点来讲,虽然它们的信息素浓度以一定的速度挥发,但信息素增加次数高于挥发量[18],且网络节点的能量充足。此时,距离Sink节点最近的非最佳路径会成为蚂蚁进行下一跳的最佳路径。同时,源节点到Sink节点的路径上还存在能耗不均、网络全局活跃度低等问题,而在Sink节点附近的“热区”内,存在路由跳数较多、节点间隔较小的路径,影响Δτk的准确性[19]。

本文利用节点能量与平均能量的偏离值作为信息素增量公式的参考因子。当偏离值较大时,增加的信息素会相应地减少,使得回退蚂蚁能够自适应地进行调整,避免源节点在发送下一轮蚂蚁包时加入到能量相差过大的路径中。具体计算过程如下:

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

(13)

(14)

其中,Fdk表示寻径蚂蚁的能量消耗,σk(s)表示回退蚂蚁k从Sink节点回到源节点时,源节点的能量es与路径平均能量Eavg k的偏离值,σk(s)的计算过程如下:

σk(s)=(es-Eavg k)2

(15)

信息素函数的增量计算如下:

(16)

通过对信息素公式进行优化,使得通过路径上节点剩余能量较大时积累的信息素增多[20],从而有效避免路径上能量较少的节点因负载过重而失效,同时提高对非最佳路径的信息素补偿,有效地解决全局网络的能量均衡问题。

4 算法流程

4.1 具体实现步骤

本文E-EEABR算法的具体实现步骤如下:

步骤1初始化各项参数。在t=0时刻,设置节点的初始能量为E0,初始信息素浓度τij(0)=0,迭代次数为N=0,允许最大迭代次数为Nmax。

步骤3蚂蚁按照k=k+1搜寻路线。

步骤6判断蚂蚁是否到达Sink节点,即k

步骤7继续执行步骤1～步骤6,直到k只蚂蚁都能到达Sink节点。

步骤8判断区域内蚂蚁可能经过的路径,如果有蚂蚁,则利用式(13)和式(14)进行信息素更新。

4.2 改进的E-EEABR算法流程

本文改进的E-EEABR算法流程如图6所示。

图6 E-EEABR算法流程Fig.6 Procedure of E-EEABR algorithm

5 仿真结果与分析

本文在Matlab 2016a环境下进行仿真,并将E-EEABR算法与IEEABR算法、IARA算法进行对比。为了确保仿真结果的稳定性与可靠性,取多次仿真结果的平均值,并分别从路径平均跳数、节点平均能量消耗、网络能耗方差、网络生命周期4个方面验证E-EEABR算法的有效性。本文使用First-order Radio Model(FRM)能量传输模型。仿真参数设置如表1所示,传感器节点在100 m×100 m区域内随机分布,蚂蚁遍历次数Nmax=30。

表1 仿真参数设置Table 1 Simulation parameter settings

5.1 路径平均跳数

路径跳数可以反映算法中蚂蚁寻找最优路径的能力。图7给出3种算法平均路径跳数的变化趋势。可以看出,IEEABR、IARA和E-EEABR算法分别在第25跳、第18跳和第13跳时达到收敛,说明E-EEABR算法相比其他2种算法,能够降低数据包的丢失率,提高数据的传输效率。

图7 路径平均跳数对比Fig.7 Comparison of average hop counts of paths

5.2 节点平均能量消耗

网络生存周期与总能量消耗成反比,网络节点的总能耗越小,网络生存周期越长。图8给出3种算法的节点平均能量消耗的仿真结果。可以看出,E-EEABR算法的节点平均能量消耗最少,这是因为该算法在计算下一跳节点的转移概率之前,采用含能量因子的伪随机比例规则策略对下一跳节点进行筛选,避免了对无关路径的搜索,减少冗余节点的网络开销和能量的传输损耗。IEEABR算法和IARA算法在选择下一跳节点时重点关注与下一跳节点的距离以及剩余能量的大小,导致蚂蚁在寻径时产生大量的无关路径,增大节点能量的损耗[20]。

图8 节点平均能量消耗对比Fig.8 Comparison of average energy consumption of nodes

5.3 网络能耗方差

在WSN中,由于节点随机分布、环境复杂多样,因此网络区域内各节点能耗也不尽相同。对于新部署的网络或者某些由于大量节点失效而必须重新部署的区域,必须要考虑整体节点的均衡程度。能耗方差常用来反映WSN整体节点的均衡情况,网络能耗的方差越小,表示网络区域内的能耗越均衡。本文从E-EEABR的30轮遍历结果中随机抽取10轮的节点总能量损耗,然后对3种算法的能耗方差进行对比,结果如图9所示。

图9 网络能耗方差对比Fig.9 Comparison of variance of network energy consumption

可以看出,E-EEABR算法的方差最小,其主要原因是另外2种算法在寻找下一跳时,可能会选择那些距离较远且与最优路径偏差较大的节点,导致大量无关路径产生,能量损耗较大。此外,IEEABR和IARA算法采用累加的信息素更新方式,蚂蚁寻径过程经常陷入局部最优,能耗均衡性差,而E-EEABR算法中的蚂蚁在寻找下一跳节点时,综合考虑候选节点的剩余能量、距Sink节点的偏离角度等因素,并在信息素更新公式中添加σk(s),当下一跳节点与最优路径相差较大时,可以及时修正该节点的信息素浓度,优化路径上节点能量与跳数的关系,在一定程度上均衡网络能耗。

5.4 网络生存周期

将网络区域内的节点数量从100递增到500,每次增加100个。定义首个节点死亡的时间为网络生存周期,网络生存周期的结果对比如图10所示。可以看出,当节点数量一定时,E-EEABR算法出现首个节点死亡的时间比其他2种算法晚,说明其对网络的生存周期有延长作用。这是因为E-EEABR算法改进了信息素公式,对最优路径上的节点进行了筛选。同时,E-EEABR算法的首个节点死亡的时间波动幅度不大,其网络扩展性和鲁棒性较好,而其他2种算法没有对运行路径上的低能节点采取维护措施,导致首个节点的死亡时间提前,网络生存周期缩短。

图10 网络生存周期对比Fig.10 Comparison of network lifetime

6 结束语

本文在EEABR算法的基础上,提出改进蚁群的能量优化路由算法E-EEABR。综合考虑距离带、搜索角度和距离因子3个因素,精确选取下一跳路由,利用激励策略均衡负载过重的“热”节点的传输任务,通过伪随机比例规则优化概率转移函数,增强算法的寻优能力。仿真结果表明,E-EEABR算法能够有效均衡全局网络能耗,延长网络生存周期。然而,本文的仿真环境设置较为理想化,未考虑其他因素,如针对Sink节点的逐跳回溯追踪攻击等的影响,下一步可对WSN的安全机制进行研究,以提高传输可靠性。