一种基于自适应信息素蒸发系数的WSN蚁群路由算法

王 恭， 孙铭阳， 孙汇阳， 滕子铭

(1.东北电力大学 自动化工程学院，吉林 吉林 132012； 2.北京电子科技学院 密码科学与技术系，北京 100070； 3.吉林大学 通信工程学院，吉林 长春 130012)

0 引言

无线传感器网络(wireless sensor network，WSN)是由一系列具有感知、计算和无线通信能力的节点组成的无线网络，可以使用户对特定的环境和场合进行数据采集、处理和传输。在实际的应用当中，无线传感器网络受到其中各节点的计算能力、无线通讯能力、储存能力和能量供给能力等诸多限制，这就要求各个节点在传输信息时，要充分合理地利用有限的能量，提高能量的使用效率，从而延长无线传感器网络的生存时间。综上所述，选取合适的路由算法来提高节点在信息传输的能量使用效率，成为近年来无线传感器网络的重要研究内容。

蚁群算法是由Dorigo等[1]提出的仿生寻优算法，该算法具有正反馈和较强的鲁棒性等特点，在解决路径规划问题时效果较好。基于蚁群算法的路由协议被提出后，引起了各方学者的广泛关注。

Gravett等[2]提出的DAR被动路由算法，限制前向蚂蚁包只使用信息素浓度作为选择下一跳节点的概率，后向蚂蚁在回到源节点的过程中释放信息素浓度为常量，从而节省在传输中损耗的能量，达到较小网络开销的目的，但因为后向蚂蚁更新的信息素为非真实值，导致选择下一跳概率不准确。Bean等[3]提出了一种ARA路由算法，将各节点中的信息素浓度储存在路由表中，通过多次迭代不断更新在各节点中的信息素浓度，从而影响蚂蚁包在选择下一跳节点的概率。在该路由算法中，除汇聚节点以外，其余节点自身携带能量是有限的，当数据包多次经过某一节点时，节点因能量损耗会过早进入休眠状态，下一代蚂蚁无法再次经过该节点，因为其在选择节点时收敛过于迅速，从全局的角度来看容易使得网络陷入局部最优。李宪强等[4]提出一种精英蚁群算法，将每一次算法迭代中最优个体的信息素保留到下一代中以提高搜索效率，但是如果算法初期留存的信息素不够具有代表性，会导致算法寻优精度较差。

Maheshwari等[5]提出的LEACH低功耗自适应集簇分层型路由算法，与传统的通用多条协议相比，适用于低能耗网络，但该算法在一定程度上增加了算法复杂度，导致收敛速度较慢。Camilo等[6]提出的EEABR伪随机路由算法采用伪随机的方式来发现目标路径，通过预估下一跳节点剩余能量，来影响下一跳节点概率，可加快算法的收敛，并减小网络开销，但过快的收敛速度很容易使搜寻路径陷入局部最优，从而影响了算法的准确性。Sun等[7]提出的EEABR路由算法解决了原有蚁群算法在传输数据时对节点能量的过量损耗等问题，但没有考虑因缩短蚂蚁包存放的路径信息，导致蚂蚁包在传输过程中易生成蚁群环路的现象，从而导致节点多余的能量损耗。

为避免数据在节点间反复回传，发生蚁群环路和信息素增量计算不准确，导致节点能量开销增大、影响网络生命周期等问题，本文在EEABR算法的基础上，提出了一种基于自适应信息素蒸发系数的改进蚁群路由算法APECARA(adaptive pheromone evaporation coefficient based ant colony routing algorithm)。该算法在前向蚂蚁数据包中添加生存时间、前向蚂蚁数据包源地址和序列号，避免数据包回传问题，有效削弱蚁群环路现象，同时改进原有算法的信息素公式，提高信息素公式准确性，从而在延长网络生命周期的同时，达到有效均衡无线传感器网络中各节点能量的目的[8-9]。

1 系统模型

1.1 数学模型

在WSN中，确定任意两节点间是否存在有效链路[11]可以用式(1)表示：

(1)

假设在WSN中只存在唯一汇聚节点z，z∈V，源节点表示为w∈ {V- {z}}。

1.2 EEABR路由算法

EEABR算法[6]将优化的重点放在如何降低节点能量消耗，通过减少节点存储ID数量[12-13]，降低节点能耗开销，提升网络寿命，以取得全局最优解。

在无线传感器网络中，每间隔一段时间在各个节点发出一个数据包，即前向蚂蚁数据包k，其访问过的节点都会以节点标识的形式储存在邻居列表中。前向蚂蚁数据包k从源节点出发，更新沿途经过路径和节点的信息素浓度，最终到达汇聚节点。汇聚节点接收到数据包后，利用信息素公式并把计算后的信息素通过储存在后向蚂蚁数据包中的方式，将数据传送回源节点。通过一次完整的蚂蚁包收发过程，标志着源节点到汇聚节点的信息素浓度更新完成。

前向蚂蚁选择下一跳节点的概率为

(2)

式中：Pk(r,s)为前向蚂蚁数据包k在r节点时选择s节点作为下一跳节点的概率；T(r,s)为储存在节点r和节点s路径上的信息素浓度，被储存在邻居列表中；Mk为蚂蚁数据包k当前经过所有节点的集合；E(u)为节点u的可见性函数；E(s)为节点s的可见性函数，即

(3)

式中：Eini为节点初始能量值；es为节点实际能量值，当节点s损耗的能量越大，节点s作为下一跳节点的概率越低。

当汇聚节点接收到前向蚂蚁数据包后，随即生成后向蚂蚁数据包，节点间的路径信息素浓度Tk(r,s)按式(4)进行更新：

Tk+1(r,s)=(1-ρ)Tk(r,s)+ΔTk(r,s)。

(4)

式中：ρ为蚂蚁包走过路径上的信息素蒸发系数；Tk(r,s)为蚂蚁数据包k从节点r到节点s途径路径上的信息素浓度；ΔTk(r,s)为信息素增量。

EEABR路由算法计算信息素增量ΔTk(r,s)如式(5)所示：

(5)

2 改进路由算法APECARA

在EEABR路由算法中，将蚂蚁包分别定义为蚂蚁数据包和Hello数据包。WSN中各个节点通过广播Hello数据包建立和维护与之对应的邻居列表，利用蚂蚁数据包传输数据和进行路径优化。本文提出的APECARA算法将在蚂蚁数据包和节点邻居列表中添加TTL(蚂蚁数据包生存时间)、pkt_src(前向蚂蚁数据包源地址)和seq(前向蚂蚁数据包序列号)，增加前向蚂蚁数据包的序列号和源地址，可有效减少在传输数据时产生的蚁群环路效应；改进原有信息素蒸发系数和信息素增量公式，解决中继节点因能量消耗，过早进入休眠的问题，提高网络节点能量均衡性和路径寻优准确性。

2.1 削弱蚁群环路效应

在无线传感器网络中，相邻的几个节点在传输蚂蚁数据包时，同一数据在相同几个节点传输多次，形成蚁群环路效应，严重影响了能量传输效率，造成不必要节点能量损耗。

图1分别为两种环路网络，节点A、D生成的数据包发生数据回传现象，将被锁定在局部网络中，二者的剩余能量将远低于WSN中其余节点平均能量，致使陷入环路的节点过早进入休眠状态，从而造成不必要的能量浪费，最终影响寻优结果。

图1 网络环路Figure 1 Network loop

针对在WSN中出现的蚁群环路效应，本文通过对蚁群环路效应的分析，重构了前向蚂蚁数据包包头结构和后向蚂蚁数据包包头结构。添加前向蚂蚁数据包序列号seq和前向蚂蚁数据包源地址pkt_src并对蚂蚁数据包生存时间TTL进行约束。

前向蚂蚁数据包包头结构由pkt_src、seq、E_s、E_m、Fd、Fromsrc_len和TTL等组成。其中pkt_src和seq分别为前向蚂蚁数据包源地址和序列号，E_s为该数据包途径中继节点消耗的全部能量，E_m为该数据包经过的所有中继节点中损耗能量最低值，Fd为该数据包经过的节点数，Fromsrc_len[14-15]为该数据包走过路径长度，TTL表示为该数据包的生存时间。TTL限制前向蚂蚁数据包生存时间，每经过一个节点TTL值减小1，当TTL=0时，前向蚂蚁数据包被放弃。通过添加pkt_src和seq到前向蚂蚁数据包，可以有效避免数据在临近节点反复回传：在发生或将要发生回传现象时，蚂蚁数据包头中的组合项生效，使接收端节点感知到已经收发过此数据包，因此发送端节点会将数据优先传输给未有标识项的其他节点，最终达到削弱网络环路的目的。

邻居列表通过Hello包维护和更新，用于记录邻居节点的信息，该表结构由Neigh_addr、pheromone、Neigh_eng和hops组成。其中Neigh_addr为邻居节点地址，pheromone为邻居节点与当前节点路径上的信息素浓度，Neigh_eng为当前邻居节点所具有的能量，hops为前向蚂蚁数据包途径中继节点的个数。

后向蚂蚁数据包包头结构由pkt_src、E_i、E_a、pheromone、Next_haddr和TTL组成。其中E_i为节点初始能量，E_a为经过路径的平均能量。

2.2 修正信息素更新公式

在蚁群路由算法的一次迭代中，当多个蚂蚁数据包经过同一节点时，该节点的路由数增加，伴随着节点能量损耗加快，该节点会过早地进入休眠状态，同时加快了蚁群路由算法的收敛速度，最终影响到寻优路线的准确性，更容易获得局部最优解。

为使网络中节点能量更加均衡，本文在式(4)的基础上，改进了信息素蒸发系数ρ，将其重新定义为自适应信息素蒸发系数，并得到全新的信息素更新公式：

δ=ρ(1+lgn)；

(6)

Tk+1(r,s)=(1-δ)Tk(r,s)+ΔTk(r,s)。

(7)

式中：δ为自适应信息素蒸发系数；n为节点路由数，当n增加时，自适应信息素蒸发系数值δ增加，信息素持久函数(1-δ)减小，节点r到节点s的信息素浓度Tk(r,s)减小，从全局的角度来看，降低了下一次蚂蚁数据包选择该节点的概率，从而平衡WSN中节点能量，获取更理想的全局最优路径。

在计算信息素增量ΔTk(r,s)时，现有的EEABR路由协议与基本的蚁群路由协议的区别在于传统的路由算法在设计时，疏忽对各节点能量损耗的考量而更倾向于对路径的寻优。这样设计的好处在于各节点剩余能量充沛时，往往可以得到最佳的路径。但是在实际数据传输过程中使同一节点多次传输数据可能导致该节点能量过度损耗，会过早进入休眠状态，从而影响最终路径的优化。

(8)

(9)

3 APECARA路由算法流程

Step1广播Hello数据包。在APECARA路由算法运行的初期，各节点广播Hello数据包来搭建临近节点的相互关系，将每条相邻路径上的信息素浓度设置为1，为计算下一跳概率做好准备。

Step2发送前向蚂蚁数据包。由源节点向下一跳节点发送前向蚂蚁数据包，该数据包每经过一个中继节点时都按式(2)计算下一跳中继节点概率，同时把访问过的中继节点储存在邻居列表中，前向蚂蚁数据包发送流程如图2所示。

图2 前向蚂蚁数据包发送流程Figure 2 Flow chat of forward ant package transmit

Step3汇聚节点向源节点发送后向蚂蚁数据包。如图3所示，前向蚂蚁数据包到达汇聚节点后，该节点随即生成后向蚂蚁数据包，该数据包中的信息素浓度按照式(7)进行更新，完成信息素更新后的后向蚂蚁数据包返回到源节点时，该数据包随即死亡，标志着一次蚂蚁数据包的收发完成。

图3 后向蚂蚁数据包发送流程Figure 3 Flowchat of backward ant package transmit

4 仿真实验及算法结果对比

为验证APECARA算法改进后的有效性，对改进后的算法进行仿真实验，并与现有的典型蚁群路由算法EEABR、ARA进行对比，通过实验得出相应的数据和曲线，并分析本文算法的性能。

4.1 实验环境及相关参数

本文实验环境采用MATLAB R2016a搭建仿真平台，仿真环境设置为10 m×10 m的封闭、无干扰的正方形区域内部署100个节点。无线传感器网络为同构静态网络，拓扑结构采用平面网状结构，其他仿真参数如表1所示。部署结果如图4所示，其中正方形节点为源节点，圆形节点为中继节点，五角星形节点为汇聚节点，细实线代表各节点间的链路，粗实线代表改进算法收敛后的最短路径。

表1 仿真实验参数设置Table 1 Parameters settings of simulation experiment

图4 节点分布图Figure 4 Distributed node graph

4.2 仿真分析

4.2.1 网络能量消耗

图5 节点消耗能量Figure 5 Energy consumption of the node

从图6可以看出，本文提出的改进算法，在迭代初期对于节点平均剩余能量的大小并未有明显优势，这是因为改进的算法为了削弱路径中出现蚂蚁环路效应，在前向蚂蚁数据包中添加了生存时间、源地址和序列号3种标识，增加了节点发送数据的开销。随着仿真实验的进行，改进算法的节点平均剩余能量明显低于EEABR和ARA算法的节点平均剩余能量，这是由于本文改进算法考虑了路径上节点的路由数和前向蚂蚁数据包途径节点损耗能量，提高了下一跳概率的准确性，避免了网络中生成冗余节点，降低了节点传输数据开销的同时延长了网络寿命。

图6 节点平均剩余能量Figure 6 Average remaining energy of the node

4.2.2 路径曲线收敛速度

路径收敛速度表明了各算法的寻优能力。在图7中，本文提出的改进算法的最短路径与ARA相比缩短了5.7%。在初始迭代时改进算法的收敛速度与EEABR和ARA算法相比较慢，这是因为本文改进的算法中提出了自适应信息素蒸发系数这一概念。从全局的角度来看，这是为了防止网络中同一节点的路由数过多，造成单一节点能量损耗过大，使节点过早陷入休眠状态，但同时也会提高数据包选择更远的节点作为下一跳节点的概率，故在算法计算初期，收敛速度较慢。随着算法迭代次数的增加，引入的自适应信息素蒸发函数提高了下一跳概率的准确性，使网络中节点能量更加均衡，达到了获取全局最优的目的。

图7 路径收敛曲线Figure 7 Convergence curve of the path

4.2.3 网络生存周期

仿真实验将网络中剩余节点数和节点死亡数作为评判网络生命周期优劣的重要考量参数。

因上述仿真实验中，3种算法均在100次迭代内各自完成收敛，故图8分别对比了3种算法在各自完成第100次迭代时的节点死亡数目，从图8中可以看出，在网络中ARA算法和EEABR算法的节点死亡数均高于本文提出的改进算法，其中ARA算法收敛迅速，造成死亡节点的自身路由数目较多，单一节点能量过度损耗，导致网络中死亡节点数较多，网络生存周期较短。

图8 节点死亡数目Figure 8 Number of node deaths

为了进一步验证本文提出的改进算法的网络生命性能，仿真实验对比各算法不同迭代次数对应的死亡节点数，如图9所示，在ARA算法和EEABR算法中，节点首次死亡分别出现在第28次迭代和第41迭代时，而改进算法节点首次死亡出现在第58次迭代。由实验可知，两种对比算法的首次节点死亡时间均早于本文的改进算法。随着算法迭代的终止，APECARA算法的剩余节点数均高于EEABR和ARA算法。这说明APECARA算法延长了网络生存周期。

图9 剩余节点数目Figure 9 Number of survived nodes

5 结论

本文在深入研究典型蚁群路由算法的基础上，对EEABR路由算法进行了研究与分析，提出了改进蚁群路由算法(APECARA)来解决无线传感器网络中的蚁群环路效应、能量分布不均和网络生命周期较短等问题。通过在前向蚂蚁数据包中添加生存时间、源地址和序列号，同时改进了信息素更新公式，引入节点路由数和数据包途径节点损耗能量，平衡了网络中节点能量分布。通过仿真实验的对比与分析可知，改进算法的寻优最短路径较对比算法缩短了5.7%，算法终止迭代时，剩余节点数均高于对比算法。证明改进后的蚁群路由算法可以有效削弱蚁群环路效应，在兼顾网络中节点能量均衡性的同时延长了网络生命周期。未来的主要工作将侧重研究启发因子α和期望启发因子β对信息素及下一跳概率函数的影响，以提出自适应的启发因子和期望启发因子，从而进一步提升整个网络的性能。