一种能耗优先的WSN路由空洞修复方法研究*

陶建林,方 凯,苗春雨,叶章龙*

(1.浙江工业职业技术学院,浙江 绍兴 312000;2.衢州学院电气与信息工程学院,浙江 衢州 324000;3.浙江师范大学数理与信息工程学院,浙江 金华 32100)

无线传感器网络主要功能是数据采集和转发,由于无需布线、成本低、精度高等特点使其被广泛应用于生产生活中的各个领域。如在林业方面,传感器网络被用于感知环境数据;在工业方面,传感器网络采集设备状态数据和生产环境数据;在环保方面,传感器网络采集环境数据传输至服务器端进行监测等[1-4];由于传感器网络中采集终端数量庞大,数据在转发过程中不同节点负载不同,负载重的节点能量容易提前耗尽,从而形成网络路由空洞。空洞附近的传感器节点在传输数据时需要绕过空洞,大大增加了数据转发跳数,不利于网络的长期生存。

目前在WSN空洞修复方面的研究已经取得丰厚的成果,其中主要是针对区域覆盖研究中的空洞修复,即派遣移动节点到空洞位置,利用新增节点的感知区域完成空洞的感知覆盖。如张清国等人提出了一种基于蜂窝结构的覆盖优化算法,利用蜂窝结构计算移动节点的候选目标位置完成空洞修复[4]。穆天圆等人提出一种基于Voronoi图的蜂群优化算法指导网络空洞的修复,通过评价空洞大小代替轮盘赌选择方式来实现跟随蜂的开采过程,达到混合网络最优覆盖的效果[5]。刘洲洲等人提出一种基于混合粒子群优化算法的空洞修复方案,将模拟退火算法和粒子群优化算法融合得到一种混合算法,该方法能够有效求解空洞修复问题[6]。Khalifa B等人提出一种分布式的网络空洞修复方法,综合考虑节点间覆盖冗余度、剩余能量和移动距离三种因素,选择最优节点进行空洞修复[7]。Ying X等人通过研究节点调度方法和三角形覆盖修复方法,降低网络能量消耗,延长了网络的生存时间[8]。Rafiei A等人研究了基于Voronoi和虚拟力的节点重定位算法用于修复网络空洞,实验结果表明该方法能够有效修复网络空洞[9]。

上述大量的研究都重点关注无线传感器网络的感知覆盖空洞修复问题,但感知空洞修复的理论很难应用在网络路由空洞修复问题上,即使强行套用理论也会导致路由空洞修复的能耗和复杂度提高,对路由空洞修复问题是极不利的。

网络路由空洞是指某些传感器节点死亡后该位置无中继节点为其他节点转发数据,从而导致数据传输中断或增加了传输代价。本文研究的路由空洞修复问题首先提出两种路由空洞查找方法,然后提出一种路由空洞能否被完全修复的判断方法,最后利用匈牙利算法派遣可移动节点完整空洞修复,本文提出的方法能够保证修复路由空洞过程中可移动节点消耗的能量总和最少。

1 相关模型与假设

该章节首先介绍本文后续研究过程中使用到的相关模型,包括路由空洞模型、节点通讯能耗模型和可移动节点移动能耗模型,然后介绍了相关假设。

1.1 相关模型

1.1.1 路由空洞模型

随着传感器网络的运行,不同节点转发数据的负载不同,负载重的传感器节点单位时间内的能耗高,而负载轻的节点单位时间内的能耗较低,因此整个网络中会出现能耗梯度。当某些能耗高的节点能量耗尽后,就会形成路由空洞,如图1中节点4、5、6、8所示。在没出现网络空洞时,传感器节点1、2、3的数据转发路径如下所示:

节点1:1→4→5→6→7→Sink

节点2:2→4→5→6→7→Sink

节点3:3→8→6→7→Sink

当出现路由空洞以后,传感器节点4、5、6、8能量耗尽,无法承担中继节点的角色,因此数据在网络中转发难度会增加,节点1、2、3的数据转发路径发生变化,如下所示:

节点1:1→9→10→11→12→7→Sink

节点2:中断传输

节点3:中断传输

传感器节点1虽然能调整转发路径,但需要绕过空洞,转发的次数明显增加,而节点2、3无法将数据转发至Sink节点,因此路由空洞对传感器网络的整体性能具有毁灭性的破坏。图1中网络路由空洞可用集合Vh={4、5、6、8}表示。

图1 路由空洞模型图

1.1.2 节点通讯能耗模型

传感器节点间通讯能耗模型如图2所示,该通讯能耗模型能够科学的描述节点通讯过程中的能量消耗。节点数据的发送和接收能耗如式(1)、式(2)所示,发送数据过程中主要能耗产生在信号发射器和信号放大器两个部件,且发送能耗与发射距离、数据包大小相关。数据接收能耗主要产生在信号接收电路。

图2 节点通讯能耗模型

(1)

Erx=kEd

(2)

式(1)、式(2)中Ee表示发射电路和接收电路处理1 bit数据的能耗;k表示发送或接收数据包的大小;εamp1、εamp1表示信号放大电路将信号放大的倍数;d表示发送节点与接收节点的欧氏距离;D表示一个距离界限,如式(3)所示。

(3)

式中:hr、ht分别表示接收节点和发送节点的天线距离地面高度;λ为电磁波波长;L为常数。

1.1.3 节点移动能耗模型

利用可移动传感器节点对网络路由空洞进行修复,其能量消耗主要发生在移动过程中且消耗的能量与移动距离呈正比,移动1 m消耗的能量约为3.6 J[10-11]。

1.2 相关假设

①传感器节点采用电池供电,能量消耗完后无法更换电池或从外界获得能量。

②可移动节点和静态节点按一定比例随机均匀部署,且初始时刻可移动节点不参与网络数据采集和转发工作,仅供后续空洞修复使用。

③无线传感器网络中的节点已经通过定位算法或GPS等技术手段获得了物理坐标。

④网络中静态传感器的初始能量为Es,可移动传感器节点的初始能量为Em,最大可移动距离为R,两种传感器节点的通讯半径相同且都为r。

⑤传感器网络每隔固定时间进行一次数据采集,且本文的研究以参考文献[12]的能耗均衡链路式路由协议为背景,进行路由空洞修复以及对整个网络的性能进行分析。

2 路由空洞定位

当出现网络路由空洞后,需要定位空洞中能量耗尽的传感器节点(即死亡节点),才能派遣可移动节点对路由空洞进行修复。本文提出2种网络空洞的定位方法,如下所示:

①如果传感器节点本身可以获取电池的剩余能量,则可将剩余能量值传输至服务器端,服务器端可根据节点的剩余能量值判断即将产生或已经产生的路由空洞。

②如果传感器节点无法获取电池的剩余能量,此时定位路由空洞相对复杂。网络在初始运行时刻,服务器端记录能够正常传回数据的传感器节点编号集合N0和传感器节点的数据传输路径集合Path={P1,P2,P3…Pi…Pm},Pi表示节点i的数据传输路径,m为集合N0的元素总数。当网络采集t轮数据后,服务器端重新统计能正常传回数据的节点编号集合为Nt,此时可计算出无法正常传回数据的传感器节点编号Nd,如式(4)所示。

Nd=N0-Nt

(4)

无法正常传输数据至服务器端的节点可能包含两种情况:(a)该节点能量耗尽;(b)该节点数据传输路径中某些节点能量耗尽导致传输中断。对应到数据传输路径Pi上可分为2种情况,如图3所示。

图3 数据传输路径图

表1 路由空洞定位与修复方法

3 路由空洞修复

第2章节介绍了2种路由空洞定位方法,这2种方法都可在实际的无线传感器网络中实现。本章介绍利用可移动节点修复路由空洞,如图4所示,路由空洞由节点n1～n5组成,通过派遣v1～v5可移动节点到死亡节点位置,替代死亡节点的数据采集和中继功能,即可修复空洞。如果基于最近原则派遣可移动节点,则5个可移动节点的移动距离之和不一定最短的,因为最近派遣方法容易陷入局部最优问题。为使修复路由空洞的代价之和最小,且在可移动节点移动距离和数量都有限的情况下尽可能修复空洞,研究了一种空洞修复判断方法和可移动节点最优派遣方法。

图4 空洞修复过程图

3.1 空洞修复判断

可移动节点数量和移动距离都有限,并不一定网络中所有死亡节点都可被移动节点替换,因此在修复空洞前需要研究一种路由空洞能否被移动节点完全修复的判断方法。当可移动节点与死亡节点之间的距离d小于等于可移动节点的最大移动距离R时,该可移动节点可用于替换死亡节点。

假设网络路由空洞为{n1,n2,n3},如图5所示。当可移动节点的最大移动距离为R时,可移动到死亡节点n1、n2、n3的移动节点集合分别表示为S1={v1,v2}、S2={v2}、S3={v3,v4,v5},当同时满足以下三个条件时,能够完全修复路由空洞。

图5 修复判断方法图

①|S1∪S2∪……St|≥t,t为路由空洞中死亡节点总数。

②Si≠Ø,1≤i≤t。

③|Seti∪Setj| ≥ 2,1≤i,j≤t,i≠j。

基于上述方法,如果判断传感器网络路由空洞内所有死亡节点都可被移动节点替换,则可完成路由空洞的完全修复,但在不能完全修复的情况下,尽最大可能修复死亡节点。

3.2 最优派遣

匈牙利算法一般用于人员最优指派问题,假设w个工人去完成w个任务,每个工人可同时能做若干种任务,但每个任务只能派遣1个工人,而每个工人对不同任务的熟练程度不同,即完成时间不同。匈牙利算法能够最优的指派人员去做相应的工作,使完成所有工作花费的时间总和最短。将可移动节点派遣修复路由空洞问题类比到人员指派问题,派遣x个可移动节点去修复y个死亡节点,且x与y的值不一定相等,因此利用“加边补零法”对传统的匈牙利算法进行改进,使之适用于不完全指派问题[13-16]。本文的路由空洞修复问题可分为三种情况,分别是xy,如图6中(a)、(b)、(c)所示。

图6 移动节点与修复位置情况图

(5)

式中:Cost(1,1)=d1,表示可移动节点v1移动到死亡节点n1的代价为d1,Cost(1,2)=+∞表示可移动节点v1无法移动到死亡节点n2处,因此代价是无穷大。Cost(2,1)=0、Cost(2,2)=0表示虚拟节点移动到死亡节点n1和n2的代价都为0。

图6(b)中路由空洞存在2个死亡节点n1和n2,且可移动节点数量也为2,可移动节点v1可以移动到n1位置,距离为d1,而不能移动到n2位置(超出可移动节点的最大可移动距离R),因此规定v1移动到n2的距离为+∞;节点v2可同时移动到n1和n2位置,距离分别是d2和d3,利用移动节点与死亡节点的距离作为路由空洞修复的代价,构建匈牙利算法的代价矩阵,如式(6)所示。

(6)

图6(c)中路由空洞存在2个死亡节点n1和n2,而可移动节点有3个,因此需要虚拟一个死亡节点,如图中虚拟死亡节点n′所示。根据“加边补零法”,所有可移动节点与虚拟死亡节点n′的距离都为0,假设可移动节点与死亡节点的距离大于移动节点的最大移动距离R时,该移动节点与死亡节点的距离为+∞。构建的匈牙利算法代价矩阵如式(7)所示。

(7)

针对上述三种情况,构建相应的匈牙利代价矩阵后,根据传统的匈牙利算法步骤即可得到最优的可移动节点派遣方法,使得所有可移动节点派遣到死亡节点位置后移动距离之和最短,从而实现修复路由空洞能耗最低的目的。

4 仿真实验

通过仿真实验验证本文提出的路由空洞修复方法(RVREP)各方面的性能,实验采用i7处理器、8 G内存的PC机为硬件环境,MATLAB仿真平台为软件环境。在初始时刻将静态传感器节点和可移动传感器节点均匀的部署到长、宽都为250m的正方形区域中。传感器网络中的节点按照参考文献[12]提出的能耗均衡链路式路由协议进行数据采集和传输(因为该方法在碰到路由空洞时会合理的选择其他转发路径),其中Sink节点位于部署区域上边缘的正中间。实验过程中随机的从网络中选择num个节点作为死亡节点(即形成网络路由空洞),实验相关参数如表2所示。由于在路由空洞方面的研究较少,更重要的是本文算法自身性能的验证,因此采用贪婪算法GREEDY进行对比,该方法在修复路由空洞时,派遣距离死亡节点最近的可移动节点。

4.1 路由空洞修复率

当路由空洞大小固定的情况下(即死亡节点数量固定),随着网络中部署的可移动节点数量增加,理论上路由空洞被完全修复的概率会逐渐提高。本实验研究路由空洞大小固定时,被完全修复的概率与可移动节点数量之间的关系。首先在部署区域中均匀部署150个静态传感器节点,然后随机部署mn个可移动节点,接着随机选择30个静态节点进入休眠状态模拟网络路由空洞,利用可移动节点对路由空洞进行修复。100次独立重复实验的平均结果如图7所示,横坐标为部署的可移动节点数量,纵坐标为路由空洞被完全修复的概率。本文提出的RVREP方法可基于3.1小节的方法判断路由空洞能否被完全修复。

表2 实验参数表

图7 可移动节点数量结果图

实验结果表明随着部署区域中可移动节点数量增加,本文提出的RVREP方法和贪婪算法GREEDY的完全修复率都快速提高,当可移动节点增加到一定数量时,完全修复率提高速度变缓,因为在初始时刻,修复路由空洞的可移动节点非常紧缺,所以修复率提高速度较快,而当可移动节点数量较多时,可移动节点数量趋于饱和,因此随着可移动节点数量继续增加,完全修复率提高速度逐渐变慢。且RVREP方法的完全修复率一直都高于GREEDY方法,当可移动节点数量为70个时,RVREP方法的路由空洞完全修复率已经达到了95%左右,而GREEDY方法仅为69%左右,因为RVREP方法在修复空洞前会综合考虑空洞附近的可移动节点,实现最优调配,而GREEDY方法只派遣距离最近的可移动节点,会陷入局部最优问题,导致其他死亡节点不能被修复。

当部署区域内可移动节点数量为90个时,网络路由空洞大小发送变化,则完全修复率也会发生变化,路由空洞越大,则完全修复率越低。实验结果如图8所示,横坐标为路由空洞大小,用死亡节点数量表示,纵坐标为完全修复率。

图8 路由空洞大小结果图

图9 平均能耗图

实验结果表明当可移动节点数量固定时,随着路由空洞大小增加,完全修复率会降低。当路由空洞大小相同时,RVREP方法的完全修复率高于GREEDY方法,主要原因是RVREP方法中采用匈牙利算法修复路由空洞,在尽可能修复的前提下实现最优派遣,而GREEDY方法修复空洞极易陷入局部最优。

4.2 路由空洞修复能耗

可移动节点修复路由空洞过程中消耗的能量越低,则移动节点替代死亡节点后剩余的能量越多,越有利于传感器网络的长期生存。为验证空洞修复能耗,在部署区域中均匀部署150个静态传感器节点,同时部署的可移动节点数量大于等于100个,路由空洞大小为30(即路由空洞由30个死亡节点组成),该条件确保了RVREP方法和GREEDY方法的路由空洞完全修复率达到100%左右(可见4.1小节实验)。可移动节点的移动能耗基于第1节的节点移动能耗模型计算,实验结果如图9所示,横坐标为可移动节点数量,纵坐标为每个可移动节点修复路由空洞的平均能耗。

实验结果表明随着可移动节点数量增加,完全修复路由空洞的平均能耗逐渐减低,因为可移动节点数量增加,修复相同的路由空洞所需要移动的平均距离逐渐减低,因此对应的能耗也呈降低趋势。且本文提出的RVREP方法的平均能耗低于GREEDY方法,因为RVREP方法能够确保修复路由空洞的移动距离之和最短,而GREEDY方法仅保证修复单个死亡节点的移动距离最短,但不能确保修复整个路由空洞移动节点的移动距离总和最短。同时随着可移动节点数量增加,两种方法的能耗趋于接近,因为可移动节点数量增加,密度也会增加,会导致死亡节点附近有足够的可移动节点用于修复,因此两种方法的差距逐渐降低。

4.3 网络生存时间

当传感器网络中大量节点死亡后,网络的路由结构会发生巨变,导致某些路由空洞附近的传感器节点数据传输中断、另外一些节点的数据转发负载加重。这对整个网络的能耗均衡性是巨大的破坏,最终导致传感器网络的生存时间大大降低。本实验以能耗均衡链路式路由协议为背景,分析网络的生存时间。由于传感器网络每隔固定时间进行一轮数据采集,因此在数据采集过程中所有节点的能耗相同,因此忽略采集能耗,但数据传输过程中每个节点的能耗不同,本文利用第1章节介绍的节点通讯能耗模型进行传感器网络通讯能耗分析。在部署区域中均匀部署150个静态传感器节和100个可移动传感器节点,在路由空洞大小为40的情况下,实验对比了不同修复率情况下的传感器网络生存时间(以传感器网络数据采集轮数表示)。对路由空洞进行一定比例的修复后,随着网络的运行,新产生的死亡节点数量达到网络中静态传感器节点的10%(不包括修复前已死亡的传感器节点),则认为网络死亡。实验结果如表3所示。

表3 网络生存时间表

实验结果表明在不修复路由空洞(修复率为0%)的情况下,传感器网络能够采集2 496轮的数据,而当路由空洞被修复20%的情况下,传感器网络在死亡前能够采集3 054轮数据,当路由空洞被修复为40%时,传感器网络采集了3 662轮数据,当路由空洞被修复60%时,能够采集4 218次,而路由空洞被完全修复时,能够采集5 747次。路由空洞被完全修复后传感器网络的生存时间比不修复延长了2.3倍。

5 总结

本文提出了一种能耗优先的WSN路由空洞修复方法,首先定位出死亡节点,由死亡节点组成路由空洞,然后提出一种路由空洞能否被完全修复的判断方法,最后利用改进的匈牙利算法派遣可移动节点完成对路由空洞的修复。实验结果表明提出的路由空洞修复方法能够有效的完成空洞修复并延长了传感器网络的生存时间。后续工作将进一步研究如何利用尽可能少的可移动传感器节点完成路由空洞的修复。