改进蚁群算法的环境能源采集型WSN多目标路由研究

曹 迪，谢敏杰，黄霆豪，雷艳静，李 伟，周加峰

1(浙江工业大学 计算机科学与技术学院，杭州 310023)

2(英国利物浦大学 电气工程系，利物浦 英国)

1 引 言

无线传感器网络是一种分布式传感网络，它由大量可以感知和检查外部世界的传感器节点自组网组成.由于其应用场景不断扩展，以及无线传感器网络节点规模不断增加，使得采用传统电池供电方式的传感器网络节点维护成本变得更加高昂，而能源采集为无线传感器网络的供能提供了一个新的解决方案[1].随着微能源采集技术MEH(Micropower Energy Harvesting)的逐步成熟[2]，越来越多的研究将能源采集技术应用于无线传感器网络中，从而延长整体网络的工作寿命.

目前针对能源采集型无线传感器网络的主要研究方向有：能源的收集模型，能源的优化调度，数据路由，拓扑管理和设备控制等[3-6].其中，路由在优化能源效率方面发挥着重要作用，进而使得网络寿命得以延长[7,8].然而，对于环境能源采集型无线传感器网络来说，设计合适的路由协议面临更多的挑战.这些挑战来自于相较传统无线传感器网络更加复杂多变的外部环境.其外部环境能源在空间分布方面，以及时间变化方面都存在随机性，使得对节点采集功率的预测难以实现.其次，网络节点模型发生了改变.节点本身除了传输数据外，还兼顾采集能量的充放电及存储，其物理模型变得更加复杂.因此，设计复杂度低、自适应性强和易于维护的路由协议，可以为能源采集型无线传感器网络实现稳定自供电提供基础保障.

目前针对环境能源采集型无线传感器网络路由算法的研究主要集中在节点从外界环境吸收能量的速率大于等于节点消耗能量速率的前提下实现最大化网络吞吐量.文献[9-11]将损耗感知的概念加入到传统WSN路由协议中，将无线传感器网络的能量损耗分为路由消耗和电池过充损耗两个部分，通过综合分析节点的能量损耗状态决定数据包的路由路径，降低了网络路由的能量损耗.考虑到能源采集型无线传感器网络面临环境能源分布不均匀的问题，文献[12，13]将节点的能源采集功率作为影响因素之一加入到路由设计之中，使得无线传感器网络对外部环境能源变化具备了一定的自适应性.但由于外界环境变化的随机性，通过设计统一模型难以应对各个节点所处环境差异大的问题，其自适应性仍然存在较多局限.

启发式算法具备通过个体或全局状态在随机的群体中寻得最优解的特性，所以采用启发式算法设计路由对于应对各节点所处环境的变化具有优异作用.其中文献[14]将节点能量水平和传输距离结合到蚁群路由协议中，提出了EEABR路由算法，各个节点通过向sink节点发送前进蚂蚁，并将路径中的中继节点记录在数据包中，待前进蚂蚁到达sink节点后，进行路径适应值计算，并通过后向蚂蚁进行路径上的信息素更新.该路由协议可以更好的适应网络中节点能量状态的变化，并找到最优路径，但其前进蚂蚁路径试探的过程是全局的，并且存在盲目性，使得算法收敛较慢并造成不必要的能量浪费.ACOHCM在经典蚁群路由的基础上结合了最小跳算法，对路径搜索集进行了筛选，并在信息素更新方案上进行了改进，使得蚁群算法的收敛速度变得更快，有效降低了路径搜索阶段的能量消耗[15].但针对能源采集型无线传感器网络存在能量波动无法预测的问题，仍然没有成熟的应对方法.

针对以上问题，本文采用能源采集型无线传感器网络节点的能量状态信息，对蚁群路由进行了改进，改进后的蚁群路由ESMACO(Energy state Multi-objective ant colony optimization)通过设计能量波动状态的光传播筛选算法EFLPS(Energy fluctuate light Propagation Selecting)，在综合评估网络节点能量状态的前提下，有效减少蚁群路径搜索的节点范围.ESMACO路由算法进一步针对能源采集型WSN路由中的多目标平衡优化问题，提出了新的启发因子及信息素更新策略，使得改进后的算法在能耗、能量均衡及网络生存期多个维度得到协调优化.改进后的路由算法实现了路由路径搜索的快速收敛，并且在有效降低网络功耗的同时使得网络节点能量均衡度得到提升，使得无线传感器网络长期保持稳定自供电.

2 系统模型

2.1 能源采集型WSN网络模型

环境能源采集无线传感器网络是一种自组织网络，由多个分布式无线传感器节点和一个sink节点组成.传感器节点可以从周围环境中收集能源，并进行环境感知；进一步对采集数据在节点进行基本计算，并通过无线电发射机与通信范围内节点进行通信.传感器节点从目标区域采集到的数据，最终通过路由转发到sink节点，并上传到服务器作进一步深度处理，在我们的算法中的网络模型具备以下5个特征：

1)所有传感器节点符合随机分布规律，任意两个节点均不在同一位置.

2)所有传感器节点的坐标位置已知，且sink节点了解整个网络的拓扑信息.

3)所有传感器节点同构，且节点的初始状态都相同.

4)所有传感器节点均可以从周围环境中采集能源，其各自的采集功率因环境变动而变动.

5)sink节点具备无限能源，且一直保持接收状态.

2.2 节点能源采集模型

本文采用混合能源采集形式，其混合能源采集系统框架如图1所示，其中外部环境能源的采集方式有电磁感应，光电效应，温差取电等不同方式.混合后能源的采集功率并非是多个单能源采集功率的简单算术叠加，而是多能源之间相互取舍后，对混合能源最大功率点的逼近所得.为了提高能量的转化及使用效率，需通过带有MPPT(Maximum Power Point Tracking)跟踪功能的功率管理单元PMU(Power Management Unit)对混合能源的最大功率点进行跟踪[16].

图1 混合能源采集系统框架

由于网络中不同地理位置的节点，在某个特定时刻的采集功率是不同的，并且同一个节点在不同时段的采集功率也是不同的.所以本文采用HPi_t(Harvesting Power)表示节点i在t时刻的采集功率，其单位为毫瓦.

2.3 路由能量消耗模型

在无线传感器网络中，数据发送所消耗的节点能量远远高于数据接收(包括数据处理和数据接收)所消耗的能量，因此，研究主要集中在数据发送的能量消耗上.我们主要参考文献[17]中对数据传输的能量损耗估算模型，其中，发送节点的能量消耗包括运行电子设备(包括数据接收)和发送模块的功放能耗，而接收节点的能量消耗，为运行电子设备(包括数据接收)的功耗.因此，发送kbit数据到距离为d的接收节点，其能量损耗为：

ETγ(k,d)=ETγ-elec(i,j)+ETγ-amp(k,d)=k(Eelec+εfsd2)

(1)

其中ETγ-elec为运行电子设备的能耗，包括传感器模块的数据采集以及MCU对数据的计算处理，ETγ-amp为无线模块发送数据的功耗，其功耗大小与数据包大小及传输距离相关，及数据越多，传输距离越远能耗越高.

数据接收节点由于其数据接收功耗远低于数据发送功耗，与其他电子设备运行处于同一级别能耗数量级，因此将接收节点的能耗用运行电子设备的能耗进行归一化表示，其接收kbit能耗公式为：

ERe(k)=ERe-elec(k)=kEelec

(2)

2.4 能量波动项

区别于传统的无线传感器网络，基于环境能源采集的无线传感器网络，节点中存储的能量会随着节点外部环境变化以及工作状态在时间和空间上呈现波动性.

本文将传感器节点IDi通信范围内，所有节点的能量状态，归一化表示到同一平面，称为节点IDi视角中的能量波动平面.通过采用锂电池的荷电状态SOC(State of charge)以及能源采集功率HPi_t作为衡量节点能量波动性的参数指标.SOC主要反映锂电池的剩余容量,其数值上定义为剩余容量占电池容量的比值,常用百分数表示.根据锂电池的充放电特性，在充放电前期以及后期开路电压与SOC呈明显的线性对应关系，但是在充放电的中期开路电压处于一个稳定状态，因此难以直接使用开路电压转换为节点能量状态，而需要进行估算修正处理[18].常用的SOC估算方法有开路电压法、内阻法、负载电压法、线性模型法等.

根据文献[19]中支配等级排序的方法，通过将节点IDi通信范围内所有节点的两个参数，采集功率HPi_t和SOCi进行归一化处理后，作为共同衡量当前节点周边能量波动的指标.具体方法：首先，将当前节点IDi通信范围内各节点的SOCi和采集功率HPi_t进行归一化处理后分别作为能量波动平面的X轴值和Y轴值(由于HPi_t和SOC都是线性变量，因此本文忽略其个体拥挤距离计算的步骤).

进一步，如图2所示将节点IDi通信范围内的节点分别向X轴和Y轴作垂线，若节点与坐标轴所围成的矩形内不包含任何其他相邻节点，则该节点的支配等级Grade为0；若节点与坐标轴所围成的矩形内包含其他节点，则取包含节点中支配等级最大的节点，将其支配等级值Grade+1后作为该节点的支配等级.支配等级Grade值越大，表示该节点的能量状态在当前节点IDi的能量波动平面中的优秀程度越高.

图2 能量波动平面

根据节点IDi能量波动平面计算得出所有通信范围内节点的支配等级后，进一步的，可根据通信范围内各节点对应的坐标位置，进一步得到节点的能量波动分布图，如图3所示.其中四角星号代表节点IDi所在位置，并以节点IDi作为圆心，以最大通信距离作为半径，标记在通信范围内所有相邻节点的支配等级Grade值及坐标位置，共同组合成节点IDi的能量波动分布图，该图可作为衡量对应区域网络能量平衡的指标，用于节点下一跳路由节点的评价参数之一.进一步重复该动作，构建网络中所有同构节点相对应的能量波动分布图.

图3 通信范围内节点能量波动分布图

3 ESMACO路由概述

3.1 网络拓扑建立

网络拓扑建立的具体实现方法是：从汇聚节点sink开始，携带节点自身层次号level、ID、坐标位置、及SOC和HPi_t，按照下述机制遍及整个网络：

1)通过从sink开始向外广播，广播数据包内容包括节点自身的层次号level、ID、坐标位置及SOC和HPi_t.其中sink节点的level值为0.

2)接收到广播的节点将该数据包的源节点记录在通信范围内节点的集合中，并判断有无新路由信息，若有则更新其路由信息数据表，进一步判断源节点level值与本节点level大小.

3)若源节点的level值小于本节点level，则将源节点的level值加一作为本节点level值，并继续向外广播.

4)若源节点的level值大于本节点level，则只更新路由信息.

3.2 路由候选集筛选

本节提出了一种基于能量波动状态的光传播转发候选集筛选算法EFLPS(Energy fluctuate light PropagationSelecting).根据上文所述的能量波动平面，将节点IDi通信范围内的节点根据其对应的支配等级分级.进一步的使用EFLPS算法对节点IDi能量波动分布图内节点进行筛选，算法示意如图4所示.

图4 EFLPS筛选算法示意图

其中(xi，yi)是当前节点IDi坐标，(xj，yj)是待筛选节点坐标，(xo，yo)是sink节点坐标，B为可视角大小，运算过程中可视角大小可变化，可视角上限值为B_max，A为源节点到sink节点的向量IO与源节点到邻节点向量IJ的夹角，R是节点通信范围半径.

可视角B及可视角的上限B_max的初始化阈值可根据无线传感器网络所处的外部环境进行调整，当无线传感器网络外部环境能量越充足，可视角的初始化阈值可相应减小，以提高路径搜索速度；当无线传感器网络能量不充足时，可视角的初始化阈值可相应加大，以提高更优解得出的概率.

源节点到sink节点的向量IO与源节点到邻节点向量IJ的夹角A：

(3)

∠A=

(4)

EFLPS算法伪代码如算法1所示.

算法1.能量波动光传播筛选算法EFLPS

输入：通信范围内节点路由信息Node(SOC，HP，x，y，ID)，可视角B，可视角上限值B_max

输出：符合条件的节点集合EFLPS()

1.初始化Node数组及B、B_max

2.根据支配排序方法计算Node各节点Grade值，保存至Node数组

3.计算源节点到Sink向量IO与源节点到邻节点向量IJ的夹角A,保存至Node数组

4.计算Node数组中Grade最大值，保存为Grade_max

5.while(EFLPS()!=NULL)

6.fori=Grade_max；i>-1；i--do

7. 筛选出Grade=i的节点

8.forj=B;j

9.if数组Node中存在A

10. 节点保存至EFLPS()；break；

11.else

12.continue；

13.endfor

14.endfor

15. 输出周围无节点；break；

16.end

3.3 路由发现机制

路由发现机制由蚁群算法进行实现，其中蚁群算法的概率转移主要有两个关键部分决定，即路径上的信息素浓度以及启发因子.本节根据能源采集型WSN节点特有的能量波动特性，提出了基于能量波动性的启发因子，可以使得网络能量均衡性得到优化，并提升采集能源的利用率.

3.3.1 启发函数

蚂蚁从节点i转移到节点j的期望程度用启发函数ηij表示：

(5)

3.3.2 路径概率选择

蚂蚁的概率选择采用传统的轮盘算法：

(6)

3.3.3 信息素更新

考虑到能源采集型无线传感器网络的路由优化目标不是单一的，需要同时对能量利用的高效性以及整个网络能量分布的均衡性进行优化，因此在信息素更新的方式上，参考文献[19]中对多目标问题优化的方法，分别将优化目标归一化表示为3个最大化目标函数：

1)若所有i∈(1，2，3)，都有fi(ma)≥fi(mb)成立.

2)且存在i∈(1，2，3)，使得fi(ma)>fi(mb)成立.

3)则称ma路径支配mb.

若蚂蚁所经过路径不支配任何其他路径，则该路径的优秀程度最低，则该路径的路径等级RGm(Route Grade)为0，若蚂蚁m的路径支配多个其他路径，则将支配路径中最大的路径等级加1后作为该路径的RG值，其中RG值越大则路径的优秀程度越高.

因此路径的中继节点越少，该路径的能量消耗越小；路径中节点的平均SOC和采集功率越大，则所选节点的能量状态越好，这样的改进方式不仅可以保证能源采集传感器网络能耗的节约，并且同时提高了采集能源的有效利用效率和网络节点能量的分布均衡度.

其信息素更新公式如公式(7)、公式(8)所示，其中：λ1，λ2，λ3为多目标的归一化系数.

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

(7)

(8)

(9)

(10)

3.4 ESMACO路由算法实现

在ESMACO路由算法的实现过程中，主要包括3个步骤，即网络信息初始化、网络拓扑生成和路由查找.首先通过sink节点进行广播扩散建立整体网络拓扑结构.进一步在路由发现机制中，对所有同构节点采用以下3步进行路径探索：第一步采用候选集筛选算法EFLPS筛选出蚁群探索候选节点集合EFLPS().第二步根据公式(6)计算得出下一跳节点ID，并对蚂蚁位置进行更新.最后重复上述两部，直到得出前往下一跳节点IDi的最优路径m.进一步地根据多目标优化信息素更新方法，通过计算每只蚂蚁的路径等级RGm，获得反向更新路径信息素浓度，通过迭代输出最优路径.

算法2.能源状态多目标蚁群路由算法ESMACO

1.初始化(荷电状态SOC，采集功率HP，可视角阈值B，可视角上限值B_max，节点的通信半径R)

2.网络拓扑生成(包含周围节点的ID，SOC，HP，坐标)

3.while(路由发现)

4.fornode i=1 to Number_of _Nodesdo

5.foriter=1 to Number_of _Iterationdo

6.forant=1 to Number_of _Antsdo

7. 根据EFLPS算法筛选出下一跳节点候选集

8. 根据公式(6)蚁群转移概率P得出中继节点ID

9. 更新蚂蚁当前位置

10.endfor

11. 根据多目标优化方法计算各蚂蚁路径等级RG

12. 结合各路径等级值，通过公式(7)、公式(8)计算反向更新路径信息素浓度

13.endfor

14. 从迭代中选出最优路径

15.endfor

16.输出最佳路由路径

17.end

4 实验仿真与分析

4.1 仿真设置

为了评估ESMACO算法的性能，在MATLAB中对WSN环境及网络运行进行了仿真.在我们的模拟网络中，区域面积为100m×100m，生成200个节点随机分布于区域中，假设sink节点位于整个区域的中心.

其中所有普通节点的初始能量C相同，各节点采集功率HP的变化规律及变化范围，通过设计的混合低频电磁场及太阳能采集的无线传感器自供电系统在不同环境中采集所得.混合低频电磁场及太阳能采集的无线传感器自供电系统实验平台如图5所示，其中光电转化模拟环境，采用84.5mm×55mm的单晶硅光伏板在不同的光照强度下进行；磁电转化模拟环境，采用内部为强导磁材质的紧密缠绕工型螺线圈，在亥姆霍兹线圈发生的不同强度的匀强磁场中进行.

图5 混合能源采集供电系统

算法中其余各参数的优选值均由实验所得，具体数值如表1所示.

表1 仿真参数表

4.2 路由收敛速度分析

在无线传感器网络中，由于节点的能量有限，以及动态的网络拓扑，因此至关重要的是，路由协议需以低成本计算出最佳路径.所以路由算法的收敛速度快慢和搜索成功率高低，是重要的评价指标.经过实验，比较几种算法的收敛速度，包括经典的ACO，EEABR，ACOHCM[14，15]和ESMACO.这4种算法分别运行100次，每种算法的平均迭代次数如图6所示.结果表明ESMACO算法平均经过20次迭代后找到最优解；ACOHCM算法平均经过38次迭代后找到了最优解，而EEABR则需要102次迭代，经典算法ACO则平均需要170次迭代.因此，证明就收敛速度而言，ESMACO算法优于其他3种算法.

图6 路由收敛速度对比图

ESMACO算法收敛速度的提高主要包括以下两个原因.一方面，通过使用EFLPS算法对周围节点进行筛选，大大减少了蚁群搜索集合的元素个数.另一方面是因为信息素更新的方式采用了，多目标优化支配排序的方法，在多目标平衡优化的基础上，使得最优路径的信息素浓度增加更快，进一步使得算法收敛更快.

进一步的由于算法收敛速度的提升，可以大幅度降低路由探索阶段的能量浪费，从而将能量更多的用于数据上传，提高网络能量利用率.

4.3 网络能量均衡度分析

在能源采集型的无线传感器网络中，由于节点外部采集环境的随机性使得各个节点的采集功率变化，并且相互之间的差异较大，如果各节点的能量水平SOC变化较大，则会引起路由路径的频繁变动.间接的提高了路由维护的能量消耗，以及降低了网络的稳定性.因此无线传感器网络各节点SOC的均衡度至关重要.

通过比较几种算法在不同的网络规模下，各节点SOC的方差值，以用于比较网络能量的均衡度，包括经典的ACO，EEABR，ACOHCM[14，15]和ESMACO.这4种算法分别在相同网络规模及外部环境条件下模拟运行200天，每种算法的节点SOC方差变化如图7所示.结果表明经典蚁群算法随着运行时间，节点能量均衡度逐渐变差；EEABR 和ACOHCM算法也随着时间节点能量均衡度慢慢变差，但由于这两个算法中考虑到了能量的因素，所以其均衡度优于经典ACO算法；ESMACO算法的方差最小,可长期保持在100以内，因为ESMACO算法在启发函数中不仅考虑了节点的SOC，同时也考虑了节点的采集功率，并且在信息素更新方式上也使用了多目标优化的方法，使得在优化网络能效的同时也对网络能量均衡度进行很好的优化.并且可以从图中看出，ESMACO算法在网络能量均衡度变差的情况下，自适应的进行了调整，使得节点SOC方差自适应的逐渐减小.

图7 网络能量均衡度对比图

网络各节点之间的能量均衡，可以进一步的说明，能源充足的节点更多的分担了网络数据路由任务，即提高了整个网络的能量利用率.

5 总 结

无线传感器节点节能技术近年来已成为传感器网络方向研究的热点，采用能量采集技术，利用环境中的微弱能量对无线传感器节点进行能量补充，是提高无线传感器节点使用寿命的重要手段.本文针对能源采集型的无线传感器网络外部环境差异大且随机性强的问题，提出了一种改进蚁群算法的多目标优化路由算法.通过设计能量波动状态的光传播转发候选集筛选算法EFLPS减少蚁群搜索的节点范围，显著提高了路由算法的收敛速度.并通过结合多目标优化支配排序的方法，提出了新的启发因子及信息素更新策略，使得蚁群路由算法可以在能耗和能量均衡两方面得到协调的优化，使得改进后的蚁群路由ESMACO不仅提高采集能源的有效利用率及功耗的优化，且使得网络节点之间能量均衡度较好，使得无线传感器网络可以保持长期的稳定自供电.在未来的工作里，本文可进一步在能量管理模型上做出相应分析，结合无线传感器节点的低功耗设计进一步优化节能效果，同样可以扩展到多节点的无线传感器网络中进行网络整体优化.