基于剩余能量的局部更新路由算法*

2019-12-20侯向丹杨聪敏刘洪普

传感器与微系统 2019年1期

侯向丹，杨聪敏，刘洪普

(1.河北工业大学计算机科学与软件学院，天津 300400；2.河北省大数据计算重点实验室，天津 300400)

0 引言

无线传感器网络(wireless sensor networks,WSNs)的广泛定义是指由大量体型小、成本相对较低，但处理能力和能量受限的普通无线传感器节点组成的网络[1,2]。WSNs的发展过程中，根据汇聚节点的移动性主要分为两大方向，即静态传感器网络与动态传感器网络，静态传感器网络中汇聚节点的位置是固定不变的，如经典的LEACH协议。动态传感器网络中的汇聚节点在工作过程中是可以移动的，比如λ-flooding协议就是比较经典的基于移动Sink的路由算法[3]。基于动态传感器网络的研究中，关于最短路径树的局部拓扑结构更新成为了新的研究方向。

目前，已经有很多基于局部拓扑结构的路由算法被提出，效果比较好的协议包括AVRP[4],ERouA[5],λ-flooding[6]等,这些算法的整体思想是在整个网络部署区域内构建不同数量的最短路径树，在AVRP协议中虽然构建了多棵最短路径树，但每次更新路由时都是更新整棵树的路由，能量消耗依然很大。λ-flooding协议中，虽然提出了对最短路径树进行局部更新，但只适用于一个移动Sink的情况，使用时局限性很大。ERouA协议中改进了λ-flooding协议的单移动Sink问题，是一个基于局部路由更新的多移动Sink算法。以上协议在一定程度上有效延长了网络的寿命，但在工作过程中没有考虑节点的剩余能量问题[7]，如果某个节点的剩余能量很少，却由于筛选条件单一被选为虚拟汇聚节点或者中间节点，那么很快此节点就会由于能量耗尽而死亡，进一步导致网络生命周期结束[8]。

综合AVRP,λ-flooding,ERouA 3种算法的特点，本文在ERouA算法的基础上提出一种基于剩余能量的局部更新路由算法(RE-RouA)，将节点的剩余能量融入到算法过程中，在算法的虚拟汇聚节点选取阶段、数据收集树的构造阶段、路由更新阶段均进行了有效的改进。

1 协议算法的目标与设计

1.1 算法目标

RE-RouA算法的目标是在保证网络延时不变的基础上延长节点的死亡时间，延长网络的生命周期。具体从以下3方面对ERouA进行改进：1)在选取虚拟汇聚节点阶段增加选择条件，利用加权函数选出最优虚拟汇聚节点；2)在数据收集树构造阶段，将节点剩余能量与阈值进行比较，为节点选择合适的位置；3)在路由更新阶段增加了触发更新的条件，并提出相应的更新方案。

1.2 算法设计

RE-RouA算法主要包括4个阶段：虚拟汇聚节点的选取；数据收集树的构造；路由更新；数据传输。

1.2.1 虚拟汇聚节点选取

虚拟汇聚节点的主要作用是将普通节点的数据收集后转发给移动汇聚节点，或者将移动Sink的命令进行下发，起到一个临时汇聚节点的作用。

ERouA算法在选取虚拟汇聚节点时只参考了节点的信号强弱，选出信号最强的节点作为虚拟汇聚节点，RE-RouA算法将节点的剩余能量与信号强弱共同作为选取虚拟汇聚节点的参考条件，采用加权函数的方式进行选取，使得整个算法得到了进一步优化。

RE-RouA中虚拟汇聚节点的选取条件主要有2个：1)节点有足够多的剩余能量，因为虚拟汇聚节点在工作过程中需要接收来自邻居节点的大量数据，且转发这些数据，将会使虚拟汇聚节点的能量消耗比普通节点大得多，所以保证所选节点有足够的剩余能量可供使用就显得尤为重要。2)要确保所选节点与其相对应的移动Sink之间的距离不要太远，否则会失去算法的优化意义。因此，RE-RouA算法提出采用加权函数来平衡这两个因素的权重，找到一个合适的权值系数，从而得到一个效果较好的平衡点。

虚拟汇聚节点的选取流程如图1所示。

图1 选择虚拟汇聚节点流程

其中，i为移动会聚集点，移动汇聚节点的个数可以任意选取，为方便说明本文假设i=1，2，3；j为节点i的邻居节点且j=1，2，…，n；dis(i，j)为移动会聚节点i到节点邻居节点j的距离，用距离表示节点j的信号强弱，距离与信号强弱成反比；E(j)为节点j的剩余能量；F(i，j)为i与j的适应度值，且F(i，j)=αdis(i，j)+βE(j)；α，β为实验系数。

1.2.2 数据收集树构造

ERouA算法中建树的方法是在每一个数据收集域中投放一个移动汇聚节点，如图2所示为一棵数据收集树，对应一个移动汇聚节点。ERouA算法中某节点将被作为叶子节点或中间节点是随机的，但由于中间节点所需的能量更多，同时为了延长网络的使用寿命，RE-RouA算法提出将节点的剩余能量也作为一个节点选取的特征。即构造数据收集树时以所选出的虚拟汇聚节点为根节点，所有节点均实时计算自己的剩余能量，并与能量阈值θ1进行比对，若剩余能量大于θ1，则该节点在构造最短路径树时可作为中间节点，否则该节点只能作为叶子节点进行数据收集。

RE-RouA算法将剩余能量较大的节点放在了数据收集树的中间节点位置。剩余能量小的节点放在叶子节点位置，与ERouA算法中只考虑距离的构建方法相比，该算法可有效延长网络寿命。

图2 数据收集树模型

1.2.3 路由更新

在ERouA算法的数据收集域中，移动汇聚节点在一定时间间隔内不能收到虚拟汇聚节点反馈的ACK包时，移动Sink会重新选择新的虚拟汇聚节点，此时新一轮的局部路由更新将被触发。但由于数据收集树的中间节点要为叶子节点以及其他中间节点进行数据收集转发，所以能量消耗会较大，如果中间节点的剩余能量较少，会加速节点死亡，导致网络生命周期受影响。RE-RouA算法增加了局部更新的触发条件以及更新方法。当中间节点的能量不足时同样会触发路由更新，经过局部调整将此中间节点放到叶子节点。具体过程如下：将数据收集树的中间节点的剩余能量与能量阈值θ2进行比较，若节点的剩余能量小于能量阈值θ2，同样会触发局部的路由更新，这是本文提出的第二个触发局部更新的条件，目的是确保中间节点的剩余能量可以完成中间转发的任务，保证网络的寿命。在路由局部更新阶段如果更新是由虚拟汇聚节点的改变所触发的，则采用ERouA中的方法进行更新。具体算法为：

1)while nodeireceiving a routing update packet from nodejdo

2)if KNTv(j,v)+d(i,j)

3) if((dTu(v,u)+dTu(i,u))/(KNTv(j,v)+d(i,j)))>λthen

4) KNTv(i,v)←KNTv(j,v)+d(i,j)

5) Pi←j

6) Forwarding the routing update packet to its neghbors

7) else

8) Discard the routing update packet

9) end if

10)else

11) Discard the routing update packet

12)end if

13)end while

如果是由中间节点k的剩余能量不足触发的局部更新，将按照本文提出的方法进行更新，此时需要分两种情况进行更新。若中间节点k的子节点全部都是叶子节点，则此节点k与其子节点一起作为其父节点的新的子节点。若中间节点k的子节点还有后继节点，则将此节点k的非叶子子节点作为其父节点的新的子节点，节点k与其叶子子节点一起作为其父节点的叶子节点。

在路由更新阶段，本文将ERouA算法进行了扩展与完善，在其基础上增加了更新条件与算法，使算法整体得到有效优化。

1.2.4 数据传输

在数据传输阶段，每个数据收集域分别进行各自的收集传输，叶子节点将自身收集到的数据沿着数据收集树向上传播到他的父节点，各中间节点不仅收集子节点发来的数据，同时也要收集自己的数据，进行转发。直到将数据发送到虚拟汇聚节点，由虚拟汇聚节点转发给移动Sink，进一步传递到用户处进行处理分析。

2 算法仿真

2.1 仿真环境

本文使用MATLAB 进行试验仿真，在200 m×200 m的仿真区域内随机投放200个传感器节点，并且设置3个移动Sink进行数据收集，每个节点的初始能量设置为0.5 J。

2.2 仿真结果与分析

本文使用MATLAB 进行仿真实验，将RE-RouA算法与ERouA，λ-flooding，AVRP 3种算法进行了对比。

如图3所示，随着实验轮数的增加死亡节点数呈递增趋势，本文算法在相同轮数的情况下死亡节点数最少，节点全部死亡的时间最晚，且初次出现死亡节点的时间最晚，综合比较本文算法在延长网络生命周期方面效果较好。由于WSNs的传感器节点能量是固定不可再生的，尤其是在环境恶劣的情况下更换电池更为困难，所以提高网络的寿命在WSNs研究中尤为重要。本文在提高网络寿命方面有着较好效果。