一种高效的有向栅栏修补算法*

王森一,范兴刚,王友好,陈 伟

(浙江工业大学计算机科学与技术学院,杭州 310023)

有向传感器,如视频传感器,红外传感器,超声波传感器等,在诸多领域有着广泛的应用,如可将传感器节点部署在重要管道沿线以监视针对管道的破坏活动,或者部署在敌营周边监视敌方的兵力部署和武器配备情况等。在上述列举的应用中,有向传感器节点被部署于宽度小于感知半径的狭长的带状区域内,对监控区域的移动目标进行检测,这种技术被称为栅栏覆盖,栅栏覆盖是有向传感网络一个研究热点[1-4]。

许多学者致力于有向栅栏覆盖构建的研究。Ssu等人[5]选择静态节点组建栅栏,初始节点选择最优的中继节点向左右两个方向延伸栅栏,直到边界。陶丹等人[6]提出一种用最少的转动角度实现强1-有向栅栏的方法。王林等人[7]采用图论找到最小旋转角度强栅栏覆盖路径,再通过贪婪算法寻找连接路径形成栅栏。Cheng等人[8]提出D-TrBR算法,利用节点的转动能力,分布式构建栅栏。该算法选择具有最大栅栏贡献的转动节点,选择转动能耗最小的转动方向,有效构建有向栅栏覆盖。该算法充分利用节点的转动能力有效构建栅栏。以上是利用节点的转动能力构建栅栏,在利用节点的移动能力构建栅栏方面,Wang等人[9]研究了混合有向网络的栅栏覆盖,根据静态节点之间的距离构建权重栅栏图WBG,再运用顶点不相交的路径算法选择K-栅栏路径,后才用匈牙利算法选择最优节点连接,行成栅栏。此算法利用图论的方法找到移动距离最小的节点构建栅栏,但是该算法的复杂度高,耗费时间长。根据节点之间的邻居关系,范兴刚等人[10-11]选择能耗最少的节点分布式构建有向强栅栏,此算法中,单个节点的最大贡献也只是感知半径,都没有考虑感知角度较大时,如何利用增大的感知区域构建栅栏。为了充分利用节点的转动能力和运动能力,车志聪等人[12]提出一种基于目标圆的分布式有向强栅栏构建方法。为了利用最少的节点构建栅栏,范兴刚等人[13]提出基于有向节点选择框的有向强K-栅栏覆盖构建算法DSBCSB。这些算法可以有效构建栅栏,Tian等人[14-15]研究了如何延长栅栏寿命,先构建多条栅栏,再周期轮换调度栅栏,多条栅栏轮流工作,来延长网络寿命。

以上这些创造性的工作,都没有考虑栅栏空洞问题。如图1,节点A、B、C组成有向栅栏,在运行过程中,节点C因能量耗尽而死亡,导致栅栏出现空洞。栅栏空洞降低栅栏覆盖质量。如果废弃整条栅栏,又会浪费能量。本文研究栅栏空洞的性质,利用周围邻居节点对其进行能量高效的分布式修补,从而提高栅栏覆盖质量,延长网络寿命。

图1 栅栏空洞

本文余下章节安排如下:第1节描述网络模型。第2节详细介绍栅栏空洞修补的理论分析。第3节详细介绍栅栏空洞修补算法。第4节通过仿真实验对提出的算法进行性能评估。第5节总结全文并介绍下一步工作。

1 相关模型和定义

[13],有向传感器节点方向可调感知模型可以采取四元组表示,其中P=(x,y)表示节点的位置坐标,r表示节点的感知半径,β表示节点的感知方向,为相对于x正半轴的方向角,取值范围为0≤β≤2π。α表示节点的感知角度。

有向栅栏是满足以下要求的一个节点集合:①集合只有一个起始节点和一个终止节点;②起始节点与监控区域左边界至少有一个交点,终止节点与监控区域右边界至少一个交点;③起始节点终止节点只与一个节点相连;④除了这两个节点之外,其余的节点都与两个节点相连,一个是它的父节点,一个是它的中继节点(也称子节点)。

研究有向栅栏修补问题之前,有如下假设:

①节点可以转动到任意方向,也可以移动。所有节点的转动能耗和移动功耗均相同,单个传感器节点每转动180°耗能为1.8 J,每移动1 m耗能为3.6 J。

②栅栏中,所有节点的监控能耗相等。

③入侵者随机进入监控区域,在其入侵路径上的栅栏节点消耗能量。如图1所示,入侵者进入节点A、B和C组成的栅栏时,只有节点C消耗能量。

定义1栅栏空洞 节点覆盖区域由无数个覆盖点组成,一个栅栏死亡节点的父节点覆盖区域内的覆盖点与其子节点覆盖区域内覆盖点的最短距离就是栅栏空洞。

定义2转动修补区域 栅栏空洞

定义3有向节点运动能耗 有向节点运动能耗由移动能耗和转动能耗组成。移动能耗是指有向移动节点运动到目标位置的能耗,转动能耗是指节点转动到目标感知方向的能耗。

定义4栅栏寿命 从栅栏形成时刻算起,到出现栅栏节点死亡,且这个死亡节点形成的空洞不再被修补为止,这段时间称为栅栏寿命。

定义5节点密度 节点的数量与区域面积的比值为节点密度。节点密度对栅栏的形成有重要的影响,后面的仿真会进一步分析节点密度对栅栏的影响。

我们研究的问题就是:针对栅栏运行过程中可能出现的有向栅栏空洞,如何分布式地找到转动修补区域,调度移动节点,以最少的运动能耗修补有向栅栏空洞。

2 理论分析

2.1 转动修补区域

图2 修补过程

定理以栅栏空洞的端点为圆心,r为半径的两圆相交区域,和两个三角形外接圆区域的差(也就是图2(a)中阴影区域)即为转动修补区域。

总之,在这个阴影区域内任意节点,到栅栏空洞两个端点的距离小于节点感知半径,与这个空洞两端形成的角度小于感知角度。根据扇形的几何性质,这个节点只要经过旋转,一定可以完全修补栅栏空洞。证毕

转动修补区域内的任意一个节点,不需要移动,只需要转到就可以形成栅栏。转动修补区域外的节点,则需要移动和转动才能完成栅栏修补。如图2(b)中的节点S只需要转动就可以修补栅栏,而节点R需要移动到点L,再转动才能修补栅栏。

当感知角度不变时,转动修补区域随着临近死亡节点的父节点和子节点之间的距离的增大而减少,当这个距离等于r时,转动修补区域变成两个端点(如图2(c)所示)。

2.2 节点的修补目标位置和目标方向

根据上面的定理,转动修补区域内的节点,不需要移动,只要转动就可以修补栅栏空洞,因此其修补时的目标位置就是其初始位置。如图2(b)中的节点S的目标位置就是其初始位置。对于转动修补区域外部的节点,目标位置在转动修补区域上。如图2(b)中的节点R,它的目标位置为点L,它移动到点L,再经过转动就可修补栅栏空洞。

对于目标位置在转动修补区域内的节点,设其与左端点的连线方向角为θl,与右端点的连线方向角为θr。如图2(b)中的点L,θl、θr分别为LB、LD的方向角。图2(b)黑色的虚扇形表示节点感知方向为θr+α/2,扇形区域的一条边与LD重合,另一条边在LB的左侧。图2(b)黑色的虚扇形节点感知方向为θl-α/2,扇形区域的一条边与LB重合,另一条边在LD的右侧。节点可以顺时针或者逆时针旋转,两个可能的感知方向中,能耗较少的转动方向为实际转动方向。

综合起来,节点修补目标位置位于栅栏空洞BD下方时,目标方向可用式(1)计算。如果位于上方,节点的目标感知方向为式(2)。

(1)

(2)

(3)

(4)

2.3 修补能耗

节点转动能耗如式(5)所示,总能耗为转动能耗和移动能耗之和,如式(6)所示,其中,dnin为节点与目标位置的直线距离,如图2(b)所示,dnin表示节点R的初始位置与目标位置L的欧式距离。

Er=|βt-β|*Jr

(5)

(6)

2.4 栅栏寿命

假设一条栅栏由Nb个节点组成,第i个节点的能量为Ei,栅栏节点的单位能耗为em,栅栏初始寿命如式(7)所示。

(7)

3 基于转动修补区域的高效的有向栅栏修补算法

3.1 算法的基本思想

要修补栅栏空洞,移动节点可以移动到死亡节点的原位置,转动到原感知方向修补栅栏。这个方法简单直观,但可能会导致较大的能耗。为了充分利用节点的转动能力高效修补栅栏,先根据几何知识,找到栅栏空洞的转动修补区域,确定周围移动节点修补空洞的目标位置和目标方向;再选择能耗最少的节点移动到目标位置,从而有效修补有向栅栏,这样的修补过程称为基于转动修补区域的高效栅栏修补算法EBarR(Effective Barrier repairing scheme based RRR)。

3.2 算法具体过程

为了描述方便,采用表1所示的变量,算法伪代码如图3所示。

表1 变量及意义

图3 算法伪代码

栅栏修补算法EBarR的基本步骤如下:

Step 1 计算栅栏寿命

按照式(7),计算栅栏寿命。

Step 2 找到栅栏空洞

Step 3 确定转动修补区域。

如果d

Step 3.1 确定节点目标位置

对于转动修补区域内部节点,其目标位置就是本身初始位置,对于外部节点,其目标位置仍在转动修补区域,而且移动距离最小。如图2(b)所示,节点R的目标位置为转动修补区域上的位置L。

Step 3.2 确定节点目标方向

计算移动节点目标位置与左端点的连线方向角θl,与右端点的连线方向角θr。并根据式(1)或者式(2)确定目标方向。

Step 3.3 确定节点能耗

按照式(5)计算节点的转动能耗,按照式(6)确定节点的总能耗。

Step 3.4 确定修补节点

总能耗最少的节点修补栅栏。

Step 4 只有两个目标位置时

如果d=r,两个端点就是修补节点的目标位置按照式(3)、式(4)确定目标方向,确定其运动修补能耗,选择运动修补能耗最少的节点移动到相应的目标位置,转动到相应的目标方向,修补栅栏。

Step 5 直接由父节点选择修补节点

如果d>r,先由父节点选择中继节点组建栅栏,再回到Step 2。

Step 6 输出结果

栅栏修补运行后,按照式(7)计算修补后的栅栏寿命,计算修补总能耗,平均能耗,最大能耗,输出结果。

3.3 算法的复杂度分析

假设栅栏空洞的个数为H,冗余移动节点的数目为O(Nm+2),分布式修补策略时间复杂度为O(H*Nm)。临近死亡节点需要广播覆盖空洞,移动节点都要广播自己的优先级结果,所以通信复杂度为O(Nm+1)。

4 仿真结果

本文运用MATLAB 7.0对此算法进行仿真,每组实验数据采用重复500次独立实验取平均值的方式获得。如果没有特别指明,实验的默认参数如表2所示。当修补节点数量达到Nr时,算法停止运行。

表2 实验参数

4.1 栅栏修补实现

在默认参数下,栅栏修补结果如图4所示。初始栅栏如图4(a)所示,经过一段时间运行,出现的栅栏空洞如图4(b)所示。图4(c)表示采用EBarR算法进行修补后的结果。蓝色节点组成初始栅栏,15个绿色扇形是修补节点的初始位置,15个红色扇形是节点修补栅栏后的位置,其中,7个转动修补,8个移动加转动修补。图4表明,EBarR算法可以有效修补栅栏空洞。

图4 栅栏修补结果

4.2 节点密度影响

在不同节点密度下,运用NSDBC算法[10]生成有向栅栏,入侵者随机进入感兴趣区域。入侵者路径上的节点产生数据,传输数据,消耗5 J的能量。节点初始能量为100 J,节点剩余能量小于10 J为临近死亡节点,需要对其产生的空洞进行修补。修补节点数达到15时的能耗和寿命如图5～图8所示。其中,“10,EBarR算法”表示节点半径为10,采用EBarR算法对产生的空洞进行修补。

图5 节点密度VS节点总能耗

图6 节点密度VS节点平均能耗

图7 节点密度VS节点最大能耗

图8 节点密度VS栅栏寿命

由于随着密度的增加,转动修补区域的节点数量增加,仅通过转动就可以栅栏空洞的节点数量增加,原来需要通过移动修补的栅栏空洞只需要转动就可以得到修补,使得修补能耗下降,导致修补总能耗随着节点密度的增加而减少,而栅栏寿命随着节点密度的增加而加大。随着节点半径的增加,节点感知区域增大,转动修补区域相应增大,原来需要移动才能修补的节点变成仅靠转动就可以修补栅栏空洞,降低了修补能耗。因此,随着节点半径的增加,节点修补总能耗也在下降。由于节点要通过移动才有可能到达临近死亡节点的原位置,而在EBarR算法中,这些节点很有可能只需要调整感知方向,就可以修补栅栏。因此,EBarR算法要比移动到原位置的修补算法节省能量,降低修补总能耗。

由于修补增加了栅栏节点,使得栅栏中最低能量节点变成了能量较大的节点。相比与原栅栏,修补后的栅栏寿命显著增大。由于EBarR算法尽可能利用节点的转动能力修补栅栏,有效降低了修补能耗。采用EBarR算法修补后的栅栏寿命要大于移动到原位置修补的栅栏寿命。

4.3 修补节点数的影响

修补节点数是指修补节点的数量,其影响如图9 所示。结果表明,修补后的栅栏寿命显著增加,因为栅栏修补以后,栅栏中能量最小的节点及时得到补偿,根据式(7),栅栏寿命也相应增加。如果原来栅栏里的节点按照能量大小排序,小的在前,大的在后。由于栅栏寿命是由栅栏中能量最小的节点决定,Nr个栅栏节点被替换后,网络寿命由原来栅栏里第Nr+1个节点决定。所以修补节点数量越多,栅栏寿命越大。由于随着修补节点数的增加,移动到临近死亡节点的原位置的节点数相应增加,而这些节点很有可能只要转动感知方向,就可以修补栅栏。因此,EBarR算法要比移动到原位置的修补算法节省能量,从而增加网络寿命。

图9 修补节点数VS栅栏寿命

图10 感知角度VS栅栏寿命

4.4 感知角度的影响

感知角度的影响如图10所示。仿真结果表明,随着感知角度的增大,栅栏寿命变化不大。这是因为虽然随着感知角度的增大,转动修补区域变大,导致修补能耗降低。但它的剩余能量要比其他节点能量多。而且栅栏寿命栅栏由能量最小的节点决定,与剩余能量较多的修补节点无关。

4.5 与传统方法的比较

[15],先生成2条栅栏,两条栅栏周期轮换工作称为SCAN算法。同样条件下,生成一条栅栏,按照EBarR算法对栅栏进行修补。

同样分布60个节点,一边形成两条栅栏(一条30个)。一边形成一条栅栏(30个节点)再用剩余节点(30个)按EBarR算法修补栅栏。栅栏寿命结果如图11所示。仿真结果表明,相比SCAN算法,EBarR修补算法有效增加了网络寿命。

这是因为,在修补过程中,一旦有节点剩余能量过低就会有另外一个节点来修补替换它,而且EBarR修补算法尽量采用节点的转动能力,修补能耗较少。

图11 不同算法VS栅栏寿命

5 结论

本文主要研究有向强栅栏修补问题,提出EBarR修补算法,利用节点之间的邻居关系,找到栅栏空洞;构造栅栏空洞的虚拟圆和外接圆,找到转动修补区域;确定修补目标位置和目标感知方向,分布式选择能耗最小节点修补栅栏空洞,延长网络寿命。仿真结果证明,EBarR修补算法可以节能高效地修补有向栅栏空洞,延长栅栏寿命。

本文只对长方形区域的有向栅栏修补进行了研究,环形、直线型区域的栅栏如何修补下一步要研究的内容之一。概率感知模型是更符合实际的感知模

型,如何节能高效地构建和维护概率栅栏也是下一步要研究的内容。

[1] Tao D,Wu T. A Survey on Barrier Coverage Problem in Directional Sensor Networks[J]. IEEE Sensors Journal,2015,15(2):876-885.

[2] K Wu F,Gui Y,Wang Z B,et al. A Survey on Barrier Coverage with Sensors[J]. Frontiers of Computer Science,2016,10(6):968-984.

[3] 陶丹,马华东. 有向传感器网络覆盖控制算法[J]. 软件学报,2011,22(10):2315-2332.

[4] 李靖,王汝传,黄海平,等. 有向传感器网络覆盖控制策略[J]. 通信学报,2011,32(8):118-127.

[5] Ssu K F,Wang W T,F K W,et al.K-Barrier Coverage with a Directional Sensing Model[J]. International Journal on Smart Sensing and Intelligent Systems,2009,2(1):75-93.

[6] Tao D,Tang S J,Zhang H T,et al. Strong Barrier Coverage in Directional Sensor Networks[J]Computer Communications,2012,35(8):895-905.

[7] 王林,刘文远,王琳,等. 基于有向传感器网络的强栅栏覆盖优化策略[J]. 小型微型计算机系统,2014,35(4):740-745.

[8] Cheng C F,Tsai K T. Distributed Barrier Coverage in Wireless Visual Sensor Networks with β-qom[J]. IEEE Sensors Journal,2012,12(6):1726-1735.

[9] Wang Z B,Liao J L,Cao Q,et al. Achievingk-Barrier Coverage in Hybrid Directional Sensor Networks[J]. IEEE Transactions on Mobile Computing,2014,13(7):1443-1455.

[10] 范兴刚,任勇默. 一种基于邻居节点运动的分布式有向强栅栏构建算法[J]. 计算机研究与发展,2017,54(1):221-231.

[11] 任勇默,范兴刚. 一种有向传感器网络栅栏覆盖增强算法[J]. 传感技术学报,2015,28(7):1051-1057.

[12] 车志聪,范兴刚. 一种基于目标圆的有向强栅栏构建算法[J]. 传感技术学报,2016,29(3):390-396.

[13] 范兴刚,王超. 一种基于选择框的有向K-栅栏构建算法[J]. 计算机学报,2016,39(5):946-960.

[14] Tian J,Zhang W,Wang G. Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks[J]. Group,the Conference of PDCS,2012:22-29.

[15] Tian J,Zhang W,Wang G,et al. 2Dk-Barrier Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks[J]. Computer Communications,2014,4(3):31-42.