一种水面WSN弱栅栏覆盖方法研究*

陶建林,苗春雨,吴鸣旦

(1.浙江工业职业技术学院,浙江 绍兴 312000;2.浙江师范大学数理与信息工程学院,浙江 金华 321004;3.杭州安恒信息技术有限公司网络空间安全学院,杭州 310051)

无线传感器网络栅栏覆盖在入侵监测方面发挥着重要的作用,如将栅栏部署在湖面,可有效监测污水的扩散;将栅栏部署在军事阵地前沿,可有效监测敌人入侵等[1-2]。一般将传感器节点随机的部署在狭窄的带状区域中,将区域一分为二,其作用是有效的监测目标是否由一个区域穿越到另一区域中,这种技术称为无线传感器网络栅栏覆盖[3-4]。

在无线传感器网络栅栏覆盖领域的研究已取得丰厚的成果。栅栏覆盖分为强栅栏覆盖和弱栅栏覆盖[5]。在强栅栏覆盖方面,Wang Z等人基于异构传感器节点,提出一种基于簇的方向栅栏图构建栅栏,并派遣可移动节点完成栅栏间隙修复,实现代价最小化[6]。Silvestri S等人提出一种强k-栅栏自主覆盖方法(MobiBar),该方法能利用设备的协调性和自我部署能力达到覆盖要求,从而使栅栏能够自主应对外界因素的影响[7]。由于在构建栅栏时一般通过定位系统或定位方法获得传感器节点位置信息,但位置信息存在误差,针对该问题Wang Z等人提出一种节点位置容错的栅栏覆盖方法,通过分析位置误差对栅栏覆盖的影响,利用容错加权栅栏图完成栅栏构建,该栅栏构建方法更符合实际应用场景[8]。在弱栅栏覆盖方面的研究相对较少,如Li L等人研究了一种弱K-栅栏覆盖方法,准确的判定带状区域是否为弱K-栅栏覆盖,并讨论了考虑边界情况和不考虑边界情况的覆盖率问题[9]。Sadeghi H等人将栅栏覆盖问题转为一维离散问题进行分析,提出一种基于顺序的贪婪算法(OGA),实现最优弱栅栏覆盖[10]。Dobrev S等人通过研究最小化可移动节点数量、最小化平均移动距离和最小化移动的最大距离3个指标优化传感器网络弱栅栏覆盖,完成弱栅栏覆盖[11]。

在水面部署栅栏具有重要的意义,目前大量的研究都是针对陆地场景构建栅栏而很少考虑水面栅栏覆盖,水面与陆地场景不同的是在水面部署的传感器节点会受外界因素(风、浪)干扰产生漂移情况,因此水面栅栏构建和维护的难度较高。本文提出一种水面WSN弱栅栏覆盖方法,能有效克服节点漂移对栅栏产生的影响,实现水面上稳定的弱栅栏覆盖。

1 相关模型与假设

1.1 相关模型

①传感器节点采用二元感知模型,以节点为圆心,感知半径为r,当监测目标进入感知范围内,传感器节点能够监测到目标的概率为1,否则为0,如式(1)所示,静态传感器节点和可移动传感器节点的感知半径相同。

(1)

式中:o表示传感器节点,t表示监测目标,d(o,t)表示传感器节点与监测目标的欧氏距离,Po,t表示节点监测到目标的概率。

②在陆地上可移动节点移动1 m消耗的能量为3.6(J)[12-13],在水中可移动节点移动1m消耗的能量为3.6-C(J),C为常数。

③弱栅栏覆盖模型如图1(a)所示,当监测目标沿任意与部署区域正交的穿越路径穿越时,至少能被一个传感器节点所感知。而在水面区域,传感器节点可能被水波冲击而产生漂移,导致栅栏出现间隙,监测目标从该间隙穿越而不被栅栏感知,如图1(b)所示,节点Ni、Nj发生漂移,监测目标可通过Pa和Pb之间的区域而不被栅栏所监测。

1.2 相关假设

①传感器节点上搭载运动感知传感器(加速度计),能准确感知节点是否发生位移。

②传感器节点能利用GPS或定位算法获得自身位置[14-15]。

③传感器节点可直接与Sink节点进行通讯,如目前比较先进的LoRaWAN、NB-iot等传感器网络。

④假设水中没有障碍物,可移动节点在能量充足的情况下不限制移动距离。

⑤算法选择在水面比较平静的情况下构建栅栏,因此在栅栏构建过程中,节点不会发生位置漂移。

图1 弱栅栏水面覆盖图

2 弱栅栏构建方法

水面弱栅栏构建主要分为两个步骤:①搜索覆盖区域,构建分段栅栏;②利用可移动节点将相邻子栅栏连接,完成整条栅栏的构建。

2.1 分段构建栅栏

在水面随机均匀部署一定数量的传感器节点,包括静态和可移动传感器节点,由于节点分布存在随机性,因此在节点部署后,区域中某些位置已经形成了较短的弱栅栏。该小节介绍如何构建已经存在的子栅栏,具体算法如表1所示。

表1 子栅栏构建过程表

子栅栏构建过程:首先建立部署区域坐标系,横坐标为X,纵坐标为Y,然后按节点横坐标x由小到大进行排序,分别编号为n1,n2,n3,…,nnum,传感器节点ni的坐标可表示为(xi,yi),节点ni和nj之间的横坐标距离di,j如式(2)所示。从节点n1开始构建栅栏,判断与节点n2之间的横坐标距离d1,2是否小于等于2r,如果是,则将节点n1和n2加入Set数据结构B1中(Set数据结构会自动丢弃重复值)。接着沿X轴增大方向判断与节点n2横坐标距离最近的传感器节点n3,如果d2,3≤2r,则将节点n2、n3存入B1中。算法继续迭代直到发现节点n6和n7之间的横坐标距离d6,7>2r,则完成一条子栅栏的构建,B1={n1,n2,n3,n4,n5,n6}表示一条子栅栏,如图2(a)、2(b)所示。

di,j=|xi-xj|

(2)

完成栅栏B1构建后,以节点n7为起始节点,继续构建子栅栏B2,如图2(b)所示,直到完成部署区域内所有的子栅栏构建,如图2(c)所示。

图2 弱栅栏分段构建图

图3 子栅栏拼接图

2.2 子栅栏拼接

2.1小节完成了部署区域中子栅栏的构建,而子栅栏之间存在间隙,如果利用可移动节点移动到子栅栏之间,将子栅栏进行拼接即可完成弱栅栏的构建。在子栅栏构建过程中首先要寻找到栅栏间隙处的待修复位置,传感器节点移动到这些待修复位即可完成子栅栏的拼接,如图3所示。图中子栅栏B1和B2之间存在间隙Gap(B1,B2),可移动节点1和2移动到间隙中的待修复位即可完成两条子栅栏的拼接。

由于部署区域中可移动节点数量有限,为保证弱栅栏构建的成功率,应可能少的使用可移动节点完成子栅栏的拼接。拼接子栅栏所需要的最少可移动节点数量如式(3)所示。

numm=「(|xj-xi|-2r)/(2r)⎤

(3)

式中:numm为拼接子栅栏所需的最少可移动节点数量,xi为子栅栏B1最右端节点的横坐标,xj为子栅栏B2最左端节点横坐标,r为传感器节点感知半径。

根据式(3)得到拼接两条子栅栏最少需要的可移动节点数量,然后将间隙Gap(B1,B2)均匀划分为numm+1,总共有numm条均匀分割线,这些分割线又称为待修复位划分线,因此待修复位置可以在待修复位划分线的任何位置,只需要将可移动节点移动到所有的待修复位划分线上,即可完成弱栅栏的构建,如图3所示。

确定了子栅栏的待修复位置后,需要在部署区域中选择冗余的可移动传感器节点完成栅栏构建工作。由于可移动节点已经参与到子栅栏的构建过程中,因此在子栅栏拼接阶段选择冗余的可移动传感器节点。冗余节点即去掉该节点不影响原本子栅栏的完整性,如图4中可移动节点mn的感知范围在横坐标上的投影能被子栅栏B1中其他传感器节点在横坐标上的投影完全覆盖,因此去除节点mn并不会使子栅栏B1被破坏,在算法执行时,从两条子栅栏间隙Gap(B1,B2)的两侧开始查找冗余可移动节点,从而确保查找到的冗余节点距离间隙更近。

图4 冗余节点选择图

为降低可移动节点移动过程中的能量消耗,采用匈牙利算法派遣冗余的可移动传感器节点到待修复位置,使得拼接子栅栏过程中可移动节点移动的距离之和最短。匈牙利算法用于任务指派问题,如指派a个工人完成a个任务,每位工人对每种收费情况不同,匈牙利算法派遣工人可以使完成所有任务的代价最小。假设可移动传感器节点在水面不限移动距离,利用匈牙利算法派遣可移动节点到待修复位置,如果可移动节点的数量M小于待修复位置数量G,则不能完成弱栅栏的构建。如果M大于等于G,则需要虚拟处M-G个待修复位置,所有可移动节点到虚拟待修复位置的距离都为0。根据上述规则改进匈牙利算法,使之适用于WSN节点派遣问题。使用匈牙利算法最重要的是构建代价矩阵,假设拼接子栅栏B1和B2,从间隙左侧开始寻找子栅栏B1中的冗余可移动节点m1和m2,从间隙右侧搜寻到子栅栏B2中的冗余节点为m3,且每个冗余节点到待修复位划分线的横坐标距离可根据节点位置计算得到,则匈牙利算法的代价矩阵如式(4)所示,根据代价矩阵即可计算出最佳的节点派遣方式,使得连接子栅栏B1和B2的可移动节点移动距离之和最小。当所有的子栅栏都被拼接后,则完成了该区域的弱栅栏构建。

(4)

式中:矩阵第三列都为0,因为待修复位置只有2个,而有3个可移动节点能够移动到待修复位置,因此需要虚拟一个待修复位置,所有冗余可移动节点到待修复位置的距离都为0。

图5 可移动节点移动距离图

3 栅栏维护

在水面部署栅栏与陆地上有较大的不同,水面部署栅栏,在受外风、波浪等外界因素的影响,即使是静态传感器节点也可能发生漂移,因此水面部署的栅栏需要进行难度更高的维护工作,主要包括监测栅栏中某些节点是否产生了位置漂移而使得栅栏出现间隙,以及间隙出现后的修复工作。

图6 栅栏冲击图

4 仿真实验

实验采用i5处理器、8G内存的PC,在MATLAB环境中进行仿真。将静态传感器节点和可移动传感器节点混合后随机均匀地部署在一个长为100 m,宽为1 000 m的水面带状区域中,传感器节点的感知半径r=30 m。

4.1 子栅栏构建

传感器节点随机部署在区域中已经形成了一些子栅栏,而在节点没有覆盖到的位置存在间隙。理论上部署的传感器节点数量越多,则区域中存在的间隙越少,则所有间隙的长度总和越短。实验验证传感器节点数量与栅栏间隙总长度之间的关系,实验中静态传感器节点占60%,可移动节点占40%,结果如图7所示,横坐标为传感器节点数量,纵坐标为栅栏间隙总长度(m)。

图7 栅栏间隙长度图

实验结果表明随着部署区域中传感器节点数量则增加,栅栏间隙的长度逐渐降低。因为传感器节点增加,部署后形成子栅栏的数量越多,则对应的间隙长度会逐渐减少。当部署的传感器节点数量大于60个时,栅栏间隙的长度随着节点数量增加减小的非常缓慢,因此随着节点数量增加,冗余节点的数量增加的越来越快,实验结果表明在部署区域中部署60个节点时最合适。当部署100个传感器节点后,栅栏间隙的长度之和接近0。

4.2 栅栏构建成功率

栅栏的构建概率与部署的传感器节点数量有关,还与可移动节点的比例相关。理论上部署的传感器节点数量越多,栅栏构建的成功率越高;可移动节点比例越高,栅栏构建的成功率越高。实验结果如图8所示,横坐标为部署的传感器节点总数量,纵坐标为栅栏的构建概率,实验分别验证不同数量传感器节点以及静态、动态传感器节点不同比例对栅栏构建率的影响。由于最近在无线传感器网络弱栅栏覆盖方面的研究较少,因此选择参考文献[16]提出的方法进行对比,该方法具有较高的性能。

实验结果表明随着部署传感器节点数量增加,栅栏构建概率先快速增加,当部署数量达到一定值时,栅栏构建的成功率缓慢增加,因为在初始阶段,部署传感器节点后,已经能构成弱栅栏,而当节点数量到达一定值后,大量的节点为冗余节点,不能大幅度提高栅栏构建概率。在部署传感器节点数量相同时,随着静态节点占比增加,则栅栏成功构建的概率逐渐减低,因为静态节点比例增加,可移动节点的比例降低,可移动节点比例越低,则栅栏间隙不能被完全的修复拼接,从而导致栅栏成功构建的概率降低。且本文提出的弱栅栏覆盖方法的栅栏构建成功概率远高于参考文献[16]提出的弱栅栏覆盖方法,因为参考文献[16]提出的栅栏构建方法并没有采用可移动传感器节点。

当静态节点比例为20%、40%,部署节点数量为60个时,栅栏的修复率较高,且随着节点数量增加,栅栏修复率升高幅度逐渐平缓,因此部署60个节点时最合适。

4.3 栅栏构建能耗

能耗是栅栏构建过程中最重要的问题之一,低能耗的栅栏构建方法能够节约大量的能量,有利于延长后期栅栏的生存时间。在栅栏构建阶段主要的能量消耗是可移动节点的移动所产生的,根据第一小节,移动节点移动1 m消耗的能量为3.6-C(J),C为常数,实验中C=1(J)。实验结果如图9所示,横坐标为区域中部署传感器节点的数量,纵坐标为完成栅栏构建的能量消耗。

图9 栅栏构建能耗图

实验结果表明随着部署区域中传感器节点数量增加,构建栅栏消耗的能量逐渐降低,因为部署的传感器节点数量越多,则栅栏间隙的长度越短,因此需要的可移动节点数量越少,而且节点和数量越多,对应的可移动传感器节点密度越高,需要移动的平均距离越短,因此能量消耗越少。随着静态节点的比例增加,构建栅栏消耗的能量逐渐增加,因为可移动节点的比例降低,修复栅栏间隙时节点的平均移动距离增加,因此消耗的能量逐渐增加。

4.4 栅栏维护

在水面区域部署栅栏与陆地上存在较大的差异,水面干扰因素较多,需要栅栏能够自主检测是否被破坏,检测到栅栏被破坏后需要及时与服务器段进行通讯,启动栅栏修复方法修复被破坏的栅栏。实验验证栅栏维护方法的性能,在带状区域中总共部署100个传感器节点,实验结果如图10所示。

图10 栅栏修复成功概率图

图10(a)结果表明随着栅栏损坏长度的增加,栅栏修复成功的概率逐渐降低。当静态传感器节点的占比增加时,栅栏成功修复的概率降低,因为静态节点比例增加,可移动节点比例降低,能够被派遣修复栅栏间隙的可移动节点数量降低,因此栅栏修复率降低。

图10(b)为修复固定长度200 m的损坏栅栏实验结果,结果表明当修复固定长度的栅栏时,随着部署的节点数量增加,栅栏修复成功率也逐渐增加。当静态传感器节点的占比增加,则栅栏的修复率会降低。

5 总结

提出了一种水面弱栅栏覆盖方法,首先在水面部署区域内搜寻已经存在的子栅栏,然后提出子栅栏拼接方法,使栅栏拼接过程中可移动节点移动距离之和最短,从而降低了栅栏构建过程中的能量消耗,最后研究了水面弱栅栏维护方法,在传感器节点上搭载加速度传感器,主动监测节点位置是否发生漂移,并修复栅栏中出现的间隙。后续工作将进一步研究水面强栅栏覆盖方法。