一种WSN三维覆盖空洞动态检测与修复算法

郝占军,徐宏文,党小超,段 渝

(1.西北师范大学 计算机科学与工程学院,兰州 730070; 2.甘肃省物联网工程研究中心,兰州 730070)

0 概述

无线传感器网络(Wireless Sensor Network,WSN)是一种具有自组织性、可靠性、可移动性且节点间可以相互通信的无线覆盖网络[1]。目前,关于二维平面覆盖策略的研究已经取得较多成果,应用于实际场景的三维空间覆盖策略也逐渐引起学者们的关注。研究三维环境下的空间覆盖策略的目的是解决现实生活中如安防部署、森林火灾检测以及水下动态检测等问题[2-3]。

在部署无线传感器网络节点时,由于外部因素的限制,难以在目标区域中对初始节点进行均匀部署,会出现很多的覆盖空洞从而导致通信受阻。为了提高整体网络覆盖和通信能力,针对不同类型的覆盖空洞,需要利用移动节点对其进行修补[4]。文献[5]在混合传感器网络中针对部分节点失效导致的覆盖空洞问题,提出一种鲁棒的空洞修复算法。该算法模拟鱼群运动模式,利用移动节点完成覆盖空洞修补,提高了网络覆盖率。文献[6]为了避免网络覆盖空洞对网络性能的影响,提出一种基于移动节点的覆盖空洞修补算法,并验证了该算法的高覆盖率和低冗余度。文献[7]针对网络中存在大量冗余移动节点,提出一种移动节点补偿方法(DAVM),其充分利用冗余资源实现网络全覆盖,但该方法不适用于网络中存在少量移动节点的情况。文献[8-10]分析移动节点部署问题,最小化移动节点移动距离从而完成目标覆盖和网络连通。以上文献主要针对二维平面覆盖进行了深入研究。文献[11]为了实现三维空间目标最大化覆盖,提出一种三维空间目标自主覆盖算法,其使用虚拟力来减少重叠覆盖并修复覆盖空洞。文献[12]为了加强网络服务质量,建立新的三维感知模型,提出一种三维覆盖增强算法,该算法通过优化调节使冗余节点均匀分布在监测区域,提高了对监测区域的覆盖率。

近年来,为了提高网络覆盖率,较多学者在覆盖控制研究中引入移动节点,将其与静态节点一起部署,形成一种混合节点部署的传感器网络。本文提出一种三维覆盖空洞动态检测与修复算法,建立三维感知模型对网络中存在的覆盖空洞进行检测,当检测到覆盖空洞时,选择覆盖空洞周围的冗余移动节点完成覆盖空洞修复,从而提高整体网络覆盖率。

1 三维空间覆盖模型及相关定义

1.1 三维空间覆盖的优化问题描述

在对三维空间目标区域进行覆盖时,将普通节点和移动节点混合后随机部署在目标区域,但随机部署会出现节点分布不均匀的问题。为了达到三维空间目标区域的覆盖要求,需要对传感器网络中存在的覆盖空洞进行动态检测与修复,以提高网络覆盖率,实现对三维空间目标区域的有效监测。

对目标区域进行网格划分是二维区域覆盖部署研究中的常用方法,其原理是将目标覆盖区域按一定的形状进行划分,得到若干小规模的网格区域,通过划分的方法可以更好地提高覆盖率并降低能耗。受二维平面覆盖网格划分的启发,本文将网格划分拓展到三维空间,设定覆盖目标区域D是一个三维立体空间,先对其进行立方体网格划分,如图1(a)所示,再在该三维空间目标区域内随机抛洒N个混合传感器节点以进行覆盖部署,如图1(b)所示。

图1 三维覆盖区域划分示意图

针对本文算法建立三维空间理论覆盖模型,假设如下:

1)静态节点和移动节点构成混合传感器网络。

3)传感器节点具有相同通信半径R和感知半径r,且R≥2r。

1.2 三维空间覆盖模型建立

常见的感知模型主要应用于二维平面覆盖,为了满足实际场景的需求,本文构建三维覆盖模型,采用基于误警率的感知模型。设网络中移动节点si的位置坐标为(xi,yi,zi),将被监测目标区域D划分成m×n×w个立方体网格,其中,用P表示立方体内的一点,且点P的位置坐标为(x,y,z),则点P与传感器节点si之间的距离为:

(1)

假定整个环境网络具有高斯白噪声,信号在传播过程中按固定的损耗因子γ和传播因子衰减,信号传播损耗与1/rγ成比例关系,γ的值由环境因素决定[13]。信号在室内自由传播时,γ通常为2或4。假设所有节点均具有相同的能量etr,对于节点i,从目标节点所接收的能量为:

(2)

其中,M1和M0分别表示目标在位和目标缺失的情况,Dti为目标(xt,yt,zt)与传感器节点(xi,yi,zi)之间的距离,ni是均值为0、方差为σ2的高斯噪声,β定义为:

(3)

在M1状态下,目标经过的行程2r=2Dti。因此,对于第i个传感器,M1状态下的探测概率为:

(4)

同理,在M0状态下的探测概率为:

(5)

Neyman-Person准则追求误警率PF最小而探测概率PD最大。设定可以接受的误警率为PF=α,则可得到:

(6)

式(6)即为支持误警率的Neyman-Person概率探测模型。其中,φ( · )为标准高斯累积分布函数。

定义1(三维覆盖率) 被节点完全覆盖的空间区域大小与总的需要覆盖的目标空间区域大小的比值称为三维覆盖率。本文三维空间覆盖率的计算借助网格划分的方法,将被监测的覆盖空间区域划分成大小相等的立方体网格,计算每个立方体网格受到的覆盖率,累加每个立方体的覆盖率可以求得总的三维空间覆盖率。

定义2(三维联合探测概率) 在三维空间目标监测区域中,任意一个立方体网格被有效覆盖的概率是多个传感器节点共同作用的效果,因此,整个网络对任意一个立方体网格的联合探测概率Uk(P)可定义为:

(7)

其中,Pi为任意传感器节点i的探测概率,φ表示满足条件的节点集合,dk,i为监测点k与节点i之间的距离,dc为节点之间的通信距离。本文通过联合探测概率的定义计算监测区域内每个立方体网格的三维联合探测概率,以确定目标空间的覆盖率并判定其是否满足三维覆盖要求。

定义3(节点移动最短距离) 在无线传感器网络中利用冗余移动节点修复覆盖空洞,移动节点的移动距离与整个网络的总能耗成正比,为了降低整体网络能耗,需要根据式(12)～式(15)计算移动节点的最短移动距离。

定义4(冗余节点) 在三维空间覆盖目标区域随机部署传感器节点时,由于节点分布不均,同一个目标节点同时被多个节点监测,且某个节点监测区域可以由其他几个节点代替,则称该节点为冗余节点。通过整体覆盖网络中节点间的互相通信可以判断该节点是否为冗余节点。

定义5(移动节点利用率) 在随机部署的混合传感器网络中,静态节点和移动节点按一定比例混合,其中移动节点具有移动性,其主要作用是用来修复网络的覆盖空洞,但部分移动节点也会充当静态节点。修复覆盖空洞的移动节点数与总移动节点数的比值称为移动节点利用率。

2 三维覆盖空洞的动态检测与修复算法

2.1 三维空间覆盖空洞描述

在三维立体空间随机部署节点时,由于外部因素的限制,网络中会出现覆盖空洞[14]。空洞是由周围多个节点形成的一个闭合空间,如图2所示,周围节点之间也存在覆盖冗余。感知节点1与覆盖空洞有2个边界端点W和S,即覆盖空洞边缘端点。设覆盖空洞周围有n个边缘节点,Vi表示节点i感知范围的体积大小,Vh表示覆盖空洞的体积大小。

图2 三维空间覆盖空洞示意图

2.2 三维空间覆盖空洞动态检测

针对覆盖空洞检测问题,本文建立三维空间覆盖模型,提出一种三维覆盖空洞动态检测与修复算法。假设立方体网格中任意一个节点M是覆盖空洞的边缘节点,为了检测该覆盖空洞,需要根据边缘节点M找到构成该覆盖空洞的所有边缘节点,并计算覆盖空洞的边缘弧和边缘端点[15]。随机选取2个相邻节点N和M,节点M与节点N的坐标分别为(xM,yM,zM)、(xN,yN,zN),两者距离为d(M,N),则节点N和节点M的方向角αNM由式(8)表示:

(8)

节点N与节点M重叠部分之间所形成的夹角θNM由式(9)表示:

(9)

节点N与节点M对应的边缘端点由式(10)表示:

(10)

检测覆盖空洞需要找到任意传感器节点M的所有邻居节点集合S={A,B,C,D,…},相对应的覆盖方向夹角集合为K={θAM,θBM,θCM,θDM,…},则方向夹角集合K所对应的弧都不是边缘弧,可以根据其补集求出对应的空洞角。根据式(8)～式(10),由每个边缘节点的空洞角、边缘弧和边缘端点就可以找出该覆盖空洞。循环执行上述方法,直至检测出所有的覆盖空洞[16-17]。

当检测到立方体网格中存在覆盖空洞时,算法调用覆盖空洞周围的冗余移动节点修复覆盖空洞。根据计算所得的移动方向和移动距离在三维空间中移动节点。首先确定移动节点的移动方向,在被检测到的覆盖空洞周围冗余节点中随机选择一个移动节点,并标记为P,该移动节点P与覆盖空洞边缘所形成的关联点为Pa和Pb,其中,节点P、关联点Pa和Pb的坐标分别为(x,y,z)、(x1,y1,z1)和(x2,y2,z2)。

通过构造三维空间坐标向量来确定移动节点P的移动方向,如式(11)所示:

(11)

由三维空间向量公式可知,通过构造三维空间向量的方法就可以确定所选移动节点P的移动方向。在构造向量Vr的过程中,会出现图3所示的2种情况,即假设向量Va和Vb的夹角为θ,则θ存在2种可能:θ<π和θ>π。当θ<π时,节点移动的方向为正确方向;当θ>π时,节点移动的方向为向量Vr的反方向;当θ=π时,节点不发生移动。

图3 节点移动方向判断示例

为了使所选移动节点完成对覆盖空洞的修复,首先确定移动节点的移动方向,然后通过节点移动后的位置与先前邻居节点的距离来确定节点的移动距离。同时,当节点移动到最优位置时需要考虑2个问题,一是保证移动节点移动后不会造成新的覆盖空洞,二是适当地选择移动节点的个数以免造成过度的覆盖冗余[18]。

在计算移动节点的移动距离时,假设节点的移动距离为d,向量Vr和VMC的夹角为θ1,当NC=RC时,覆盖率取得最大值,节点C的坐标记为(x3,y3,z3),节点M与节点C的距离由式(12)表示:

(12)

向量VMC的计算如式(13)所示:

VMC=(x3-x)i+(y3-y)j+(z3-z)k

(13)

夹角θ1的计算如式(14)所示:

(14)

如图4所示,根据三角形性质可得|MC|=d1,|MN|表示移动距离为d,NC=RC,则移动距离的计算如式(15)所示:

(15)

图4 移动距离计算示意图

通过以上步骤即可得到随机选取的移动节点P的移动方向Vr和移动距离d。在移动节点移动到覆盖空洞位置后,整体更新覆盖空洞修复信息,继续在覆盖空洞周围寻找新的冗余移动节点P′,重新初始化相关参数,再次执行上述方法进行覆盖空洞的修复。经过数次迭代后,当找不到合适的移动节点或所有覆盖空洞已被修复,结束覆盖空洞修复过程。

2.3 算法描述

本文三维覆盖空洞动态检测与修复算法流程如图5所示。

图5 三维覆盖空洞动态检测与修复算法流程

算法步骤具体如下:

步骤1初始化N个混合传感器节点,并对三维空间目标区域进行立方体网格划分。

步骤2设置感知模型的误警率参数,采用联合探测概率模型探测每个立方体网格的覆盖率。

步骤3在每个立方体网格中随机选择一个传感器节点X,其坐标为(x,y,z),找出节点X的所有邻居节点,构成集合N={n1,n2,…,nx}。

步骤4根据覆盖空洞动态检测算法计算出选定节点X的边缘节点、边缘弧和空洞角,从节点X的所有邻居节点集合N中找出该覆盖空洞的边缘节点。对这些边缘节点继续计算其边缘端点、边缘弧和空洞角,以检测覆盖空洞。

步骤5当检测到覆盖空洞后,选择空洞周围冗余移动节点,根据移动方向和移动距离逐个修复覆盖空洞。

步骤6重复步骤4和步骤5,循环至覆盖空洞完全修复。

步骤7依据目标区域信息监测要求,判断整体覆盖率是否达标,若是,转步骤8;否则转步骤4。

步骤8结束算法。

2.4 算法分析

2.4.1 三维覆盖率分析

本文目的是通过修复三维空间目标区域覆盖空洞,提高整体网络覆盖率。网络覆盖率可由式(16)计算得到:

(16)

其中,C(A)为三维空间整体网络覆盖率,P为立方体网格中的任意点,m为所有节点个数,n为探测点的个数,d(si,P)表示节点si到节点P的距离,ci(A)为三维空间中任意节点在整个网络中的覆盖率,cP(si)表示点P处的覆盖率,0≤cP(si)≤1。在检测到覆盖空洞后,移动节点根据计算出的移动方向和移动距离进行覆盖空洞修复。移动节点si与覆盖空洞中心k之间的距离为:

(17)

在实际移动过程中,移动节点si到覆盖空洞中心k的距离也会发生变化,具体如下:

d(si,k)′=d(si,k)+diri

(18)

由式(18)减去式(17)得到:

(19)

2.4.2 能耗分析

本文算法整体能耗由检测网络覆盖空洞、收发信息和节点移动的能耗组成。设E1为动态检测覆盖空洞的能耗,E2为节点收发信息的能耗,E3为节点移动的能耗,则整体网络能耗E的计算公式为:

E=E1+E2+E3

(20)

设Ei表示移动节点i移动单位距离的能耗,移动总能耗E3为:

(21)

3 实验结果与分析

3.1 仿真环境与参数设置

为验证本文三维覆盖空洞动态检测与修复算法在覆盖效果和能量消耗等方面的性能[20],采用MATLAB2015b软件进行仿真。无线传感器网络的部署环境是100 m×100 m×100 m的立方体区域,初始条件下传感器节点随机部署,各仿真参数如表1所示。

表1 仿真参数设置

3.2 性能分析

对本文算法的主要性能进行验证分析,在算法运行不同次数时,覆盖空洞检测率随节点个数变化的曲线关系如图6所示。

图6 覆盖空洞检测率随节点个数的变化曲线

由图6可知,当传感器节点个数在0～90内变化时,算法执行不同迭代次数时覆盖空洞检测率相同;当节点个数在90～210内变化时,算法迭代次数不同,覆盖空洞的检测率发生很大变化,迭代次数为120次和150次时的覆盖空洞检测率明显高于迭代次数为100次时的检测率;当节点个数在210～300内变化时,3种迭代次数的空洞检测率都在逐步增大。通过实验结果可以看出,当节点个数为300个、迭代次数为150次时,覆盖空洞检测率达到92%以上,满足了整体覆盖空洞检测率要求。

在调用移动节点对覆盖空洞进行修复时,覆盖空洞修复率随算法迭代次数的变化曲线如图7所示。

图7 覆盖空洞修复率随迭代次数的变化曲线

由图7可知,在前60次算法迭代时,由于存在大量的冗余节点,3种情况的覆盖空洞修复率都在平缓上升,变化幅度不大,其中,移动节点数目为90个时空洞修复率略高于其他2种情况;在60次～110次迭代时,移动节点个数越多,覆盖空洞修复率增长得越快;在110次～150次迭代时,3种情况的修复率稳定增长。通过实验对比可以看出,当算法迭代150次、移动节点数目为90个时,可以很好地完成覆盖空洞修复,从而达到整体网络覆盖空洞修复要求。

为了达到覆盖要求且节省成本,需要传感器网络静态节点与动态节点比例适中。不同移动节点比例时三维覆盖率随节点个数的变化关系如图8所示。由图8可知,当传感器节点个数在200个以内时,随着节点个数的增加,三维覆盖率也逐渐增加,但移动节点所占比例对覆盖率的影响不够明显;当节点个数从200个增加到300个时,移动节点占比越高,覆盖率增加得越快;当节点个数为300个、移动节点占比为30%时,三维覆盖率达到95%,完成了对三维目标区域的覆盖。

图8 三维覆盖率随传感器节点个数的变化曲线

在整个网络能耗中,最主要的是移动节点的移动能耗。在不同移动节点个数情况下,每个移动节点的能耗随算法迭代次数的变化曲线如图9所示。

图9 节点能耗随算法迭代次数的关系曲线

由图9可知,算法迭代前60次时,调用覆盖空洞周围冗余移动节点修复覆盖空洞,节点移动距离大致相同,因此,移动节点的个数对节点能耗影响不大。随着算法迭代次数的增加,越来越多的空洞被检测到,在修复这些空洞时,需要大量的移动节点移动较远的距离,因此,每个节点能耗增大。通过实验对比可以看出,当移动节点个数为90个时,既可以满足覆盖要求又可以最大程度地节省能耗。

3.3 本文算法与相似算法的对比

为了进一步验证本文算法的性能,经对比分析后,选择三维覆盖中常用的经典粒子群算法(PSO)和文献[21]中提出的二维平面CPA算法,与本文算法在覆盖率、移动节点利用率和移动能耗等方面进行对比分析。3种算法较为相似,目的都是使用移动传感器节点对覆盖空洞进行修复,提高整体网络的覆盖率和连通性,从而更有效地监测目标区域。

图10所示为3种算法移动节点利用率随移动节点个数的变化关系曲线。从图10可以看出,在初始阶段,随着移动节点数量的增加,逐渐出现节点冗余现象,3种算法节点利用率都呈平缓的下降趋势;当移动节点数量大于25时,PSO算法和CPA算法移动节点利用率出现了大幅下降,而本文算法的节点利用率则下降比较缓慢;当移动节点数量大于45时,3种算法的移动节点利用率又出现了平稳的下降现象;当移动节点个数为90个时,完成了对目标覆盖空洞的最大化覆盖。本文算法总体的移动节点利用率高于PSO算法和CPA算法,其总体使用节点更少。

图10 移动节点利用率随移动节点个数的变化曲线

图11所示为3种算法覆盖率随迭代次数的变化曲线关系。从图11可以看出,在初始阶段,随着算法迭代次数逐渐增加,覆盖率也在稳步增大,PSO算法的覆盖率一直略高于其他2种算法;当迭代次数在50次～70次之间时,3种算法的覆盖率都出现了明显的上升波动,本文算法的覆盖率超过了其他2种算法;当迭代次数在70次～120次之间时,随着迭代次数的增加,3种算法的覆盖率都在稳步大幅增加;当迭代次数达到150次时,本文算法率先达到了网络整体覆盖率要求。通过对比实验可以看出,本文算法在相同迭代次数下可以更快地达到覆盖率要求,从而节省算法运行的时间。

图11 覆盖率随迭代次数的变化曲线

在整个无线传感器网络中,不仅要达到覆盖要求,还要节省网络能耗[22]。3种算法的移动能耗率随移动节点个数的变化曲线如图12所示。从图12可以看出,在0～30个移动节点范围内,移动节点的移动距离短,3种算法的移动能耗都较小;当节点个数在30个～60个内时,节点个数增加的同时移动距离也在逐渐增多,3种算法的节点能耗都在增加,但本文算法的节点能耗明显低于其他2种算法;当节点个数从60个增加到90个时,PSO算法节点移动能耗率大幅升高,CPA算法节点移动能耗率次之,本文算法移动能耗率较低。因此,本文算法移动节点能耗率相对较低,其网络寿命更长。

图12 移动能耗率随移动节点个数的变化曲线

4 结束语

为了对三维空间目标区域进行有效监测,本文提出一种三维覆盖空洞动态检测与修复算法。通过采用基于误警率的联合探测概率模型检测每个立方体网格的覆盖率,动态检测三维部署区域所有覆盖空洞并移动覆盖空洞周围的冗余移动节点以修复覆盖空洞,从而使目标区域网络连通。实验结果表明,本文算法可以达到整体网络覆盖要求,其节点利用率和覆盖率等性能优于PSO和CPA算法,整体网络能耗较低。但本文算法存在移动能耗过高和灵活性较低等不足,下一步将优化算法性能以解决移动能耗问题。