一种基于邻居节点运动的分布式有向栅栏构建算法

范兴刚 任勇默 车志聪 王 超

(浙江工业大学计算机科学与技术学院 杭州 310023)(xgfan@zjut.edu.cn)

一种基于邻居节点运动的分布式有向栅栏构建算法

范兴刚 任勇默 车志聪 王 超

(浙江工业大学计算机科学与技术学院 杭州 310023)(xgfan@zjut.edu.cn)

K-栅栏覆盖是有向传感器网络的研究热点之一.目前为止，很少从移动和转动能耗相结合考虑有向栅栏构建.提出一种基于邻居节点运动的分布式有向强栅栏构建方法(distributed directional strong barrier construction based on neighbor actuation, DBCNA).在形成栅栏的节点集合中，若在前一个感知区域内部存在节点，横坐标最大的节点就是节点的目标位置.如果感知区域内部没有节点，则令前一个节点正右方向一个半径距离处作为下一节点的目标位置.有向节点的目标感知方向由移动到该位置的移动节点的初始感知方向决定.若初始感知方向0≤β≤α2或2π-α2≤β≤2π，目标感知方向就是节点的初始感知方向；若α2≤β≤π，目标感知方向为β=α2；若π<β<2π-α2，目标感知方向为β=2π-α2.仿真结果证明了该栅栏构建方法比其他方法节省40%的节点，平均能耗降低了40%～50%，具有重要的理论与实际意义.

有向栅栏覆盖；目标位置；感知方向；下一个节点；运动能耗

有向传感器，如视频传感器、超声传感器和红外传感器等在诸多领域有着广泛的应用，如可将传感器节点部署在重要管道沿线以监视针对管道的破坏活动，以及在敌营周边布设无线传感器节点来监视敌方的兵力部署和武器配备情况等.在上述列举的应用中，有向传感器节点被部署于感兴趣区域的边界，对进入感兴趣区域的移动目标进行检测，这种技术被称为栅栏覆盖.如何实现栅栏覆盖是有向传感网络的一个研究热点[1].

利用节点的移动能力构建全向栅栏已有一些研究工作.班冬松等人[2]研究了全向移动传感器网络K-栅栏覆盖问题，提出了一种能量高效的栅栏覆盖构建算法CBIGB.王志波等人[3]研究了节点存在定位误差时的栅栏覆盖问题.贺诗波等人[4]多次移动节点构建栅栏覆盖.Saipulla等人[5]构建栅栏过程中，考虑了节点移动能力的有限性.在有向栅栏研究中，马华东等人[6]研究了最少的有向视频节点组建栅栏问题；Zhang等人[7]利用有向节点的转动能力构建强栅栏；Wang等人[8]选择有向节点组建视线栅栏，构建有向传感阵列监视入侵者；王志波等人[9-10]研究了混合有向网络的栅栏覆盖，根据网络拓扑构建权重栅栏图WBG，再运用顶点不相交的路径算法构造K-栅栏.以上这些方法都是集中式的，都需要知道整个网络的拓扑.Shih等人[11]研究了分布式栅栏构建算法，利用可能栅栏行中的邻居节点通过栅栏信息构建栅栏.陶丹等人[12]利用邻居节点的位置信息，选择具有最多邻居的节点构建栅栏.Zhang等人[13]等人研究了概率均值聚类在大数据环境下的应用.

利用附近节点之间的位置关系，可以选择最优的节点构建栅栏.我们研究了全向强栅栏构建，提出了PMNSB算法[14].Guvensan等人[15]基于移动能耗和转动能耗研究了有向网络的覆盖增强.在此基础上，本文研究如何利用节点之间的位置关系，调度节点的运动，节能高效地构建强K-栅栏覆盖，提出一种基于邻居节点运动的分布式有向强栅栏构建方法(distributed directional strong barrier construction based on neighbor actuation, DBCNA).在形成栅栏的节点集合中，按照从左到右的节点顺序，确定节点的目标位置，并选择能耗最少的节点移动到目标位置，构建有向强栅栏.

1 相关模型和定义

Fig. 1 Model of rotatable directional sensor 图1 可旋转有向传感器的传感模型

研究有向栅栏问题之前，有3条假设：

1) 所有传感器的感知半径和感知角度均相同.

2) 所有传感器的转动能耗和移动功耗均相同，参考文献[15]，传感器每转动180°耗能为1.8 J，每移动1 m耗能为3.6 J.

3) 传感器监视范围内的信号强度相同,且能在范围内以100%的可能性监测到事件.

定义1. 有向节点的目标位置.形成强栅栏的有向节点的目标位置坐标就是有向节点的目标位置.有向节点只要移动到这个位置才有可能形成栅栏.有向节点的目标位置由形成栅栏的前一个节点决定.

定义2. 有向节点的目标感知方向.移动到目标位置的有向节点的感知方向就是有向节点的目标感知方向.有向节点的目标感知方向由移动到该位置的移动节点的初始感知方向决定.

定义3. 有向节点运动能耗.有向节点运动能耗是指有向移动节点运动到目标位置的能耗，由移动能耗和转动能耗组成.第i(i≥2)个节点的转动能耗如式(1)所示，运动能耗如式(2)所示，其中的参数见后面的表1.式(1)标明，若0≤β≤α2，或者2π-α2≤β≤2π，则不进行转动；若α2≤β≤π，转至β=α2处；若π<β<2π-α2，转至β=2π-α2处.式(2)中，表示节点移动到目标位置的最小距离，移动能耗和转动能耗之和就是有向节点运动能耗.

(1)

(2)

定义4. 节点密度.节点是随机分布的，服从强度为γ泊松点分布，则γ称为节点密度.节点密度对栅栏的形成有重要的影响，后面的仿真会进一步分析节点密度对栅栏的影响.

定义5. 能耗标准差.假设组成栅栏的节点总个数是Nb，第i个节点的能耗为ei，平均能耗为Em，构建K条栅栏能耗标准差为D(K)，反映了构建栅栏的过程中节点的能量波动，反映了栅栏的持续寿命与稳定性.

(3)

有向强栅栏的定义见文献[10]的定义6，我们研究的问题就是：在狭长区域中随机部署的有向移动节点密度为γ的情况下，如何分布式地调度移动节点，以尽量少的运动能耗构建有向强栅栏覆盖.

2 分布式有向强栅栏构建算法(DBCNA)

王志波等人[9-10]根据感知区域内所有静态节点组成的网络拓扑结构构建加权图，采用顶点不重复的K条路径图论算法找到形成栅栏的目标位置，然后移动节点和这些目标位置进行最佳匹配，这需要全局拓扑信息，通信和开销较大，而且不适用于要减少通信和计算开销.PMNSB算法把构造K-栅栏这个复杂的问题分成小问题，先在小的子区域构造1MNSB，这些1-栅栏合起来就是强K-栅栏.但PMNSB算法不能用于有向强栅栏的构建，在有向栅栏中，有向节点感知不再是圆形而是扇形，单独的圆心不能确定一个有向节点的位置.而且PMNSB算法仅考虑节点的移动，没有考虑节点的转动，而转动节点是解决有向覆盖问题的主要方法.在此基础上，我们提出一种分布式基于邻居节点运动的分布式有向强栅栏构建算法(DBCNA).

2.1 理论分析

DBCNA算法的基本思想如下：运用节点之间的位置关系，在形成栅栏的节点集合中，按照从左到右的节点顺序，按照节点对栅栏贡献尽量最大原则，分布式地确定节点的目标位置，为了保证形成栅栏，节点的目标位置只与前一个节点有关，不仅如此，前一个节点还根据自己周围的节点分布情况，进一步确定运动到目标位置的移动节点，并选择能耗最少的节点移动到目标位置，从而构建有向强栅栏.

要形成栅栏，先依次找到目标位置，再由前一个节点选择最优的移动节点运动到目标位置，再调整这个节点的感知方向，形成栅栏.

Fig. 2 Selection of nodes图2 节点的选择

移动到目标位置的有向节点的感知方向就是有向节点的目标感知方向.有向节点的目标感知方向由移动到该位置的移动节点的初始感知方向决定.如果初始感知方向0≤β≤α2或者2π-α2≤β≤2π，则有向节点的目标感知方向就是节点的初始感知方向；如果α2≤β≤π，有向节点的目标感知方向为β=α2处；如果π<β<2π-α2，有向节点的目标感知方向为β=2π-α2.式(2)中，表示节点移动到目标位置的最小距离，移动能耗和转动能耗之和就是有向节点的运动能耗.如图2(a)和图2(c)所示，点C是节点的目标位置，由于节点C的初始感知方向为α2≤β≤π，则运动到目标位置点C的目标感知方向就是β=α2.如图2(b)和图2(d)所示，点C是节点的目标位置，由于节点C的初始感知方向为π<β<2π-α2，则运动到目标位置点C的目标感知方向就是β=2π-α2.

有向节点的目标感知方向，除节点1外，感知方向在[-α2,α2]之间.节点1的感知方向见2.2节.

2.2 算法的详细过程

参数的定义如表1所示:

Table 1 The Parameters

DBCNA算法步骤描述如下：

1) 确定栅栏形成区域

在投撒n个传感器完毕后(n为某个整数)，从纵坐标最大的节点开始(即最上方的节点，设为y1)，划分区域的上边界y=y1，将上边界正下方2r处直线y=y1-2r作为区域的下边界.依纵坐标从大至小的顺序向下，以此类推，直至划定完第n个区域.统计各个区间段内的节点个数，选取节点个数最多的区间段作为第1条栅栏形成的预选区域.

2) 确定有向强栅栏的节点1

选出预选区域中横坐标最小的节点.若其横坐标大于半径r，则先令其向左平行移动至横坐标等于半径，并用最少的转动能耗调整其感知方向，使其在[π-α2,π+α2]之间；若其横坐标小于半径r，判断扇形区域与左边界x=0是否有公共点.若已有公共点，不进行转动；若无公共点，选择需要转动角度较小的那个方向，转至其扇形区域恰与左边界x=0有一个公共点.该节点调度完毕后作为该条栅栏的节点1.

3) 确定节点2的目标位置并选择节点运动

根据文献[10]的定义1，判断剩余节点中是否有节点在节点1扇形区域内部.若有，选出扇形区域内横坐标最大的节点作为节点2，不进行移动,只将其按照式(1)调整方向角，并计算运动能耗.例如，在图3(a)中，节点A为节点1，圆心为B的虚扇形为节点2的目标位置，圆心为B的节点主要转动到虚线位置即成为构建栅栏的节点2.

Fig. 3 Selection of the second node图3 节点2的选择

定理1. 在感知区域内有1个节点的概率为P1=0.5γr2αe-0.5γr2α.

证毕.

若没有节点在节点1扇形区域内部，则将节点1扇形区域中横坐标最大的点作为节点2需要移动的目标位置，若此目标位置超出整个区域，则认为此次选择无效，重新将节点1自身的坐标作为节点2的目标位置.选定目标位置后，找出剩余所有节点中与目标位置之间欧氏距离最短的节点作为节点2，节点沿着最短路径移动至目标位置，并按照式(1)调整方向角.例如，在图3(b)中，节点A为节点1，圆心为B的虚扇形为节点2的目标位置，C为移动节点.

4) 以此确定其余所需节点的目标位置并选择节点移动

在节点i(i≥2)调度完毕后，若在其感知区域内部存在节点，横坐标最大的节点就是第i+1个节点的目标位置.如果感知区域内部没有节点，则令节点i(i≥2)正右方向一个半径距离处作为下一节点的坐标位置，然后选出剩余所有节点中与其欧氏距离最短的节点，将其沿最短路径移动至与目标位置重合.有向节点的目标感知方向根据定义2和式(1)确定.形成栅栏的有向节点的移动距离越小，算法的效率越高.

下面的定理2 说明了节点的移动距离和密度的关系.

定理2. 节点移动到目标位置，移动距离为1 m的概率为P=(1-P1)e-γ πγπ.

证毕.

5) 根据右边界位置确定形成第1条栅栏

6) 构建其余K-1条栅栏

若K>1，从剩余的区域段中找出节点个数最多的区域段(之前参与形成栅栏的节点不再计入)，重复步骤2～5，形成第2条栅栏.同理，依次形成第3条、第4条、……、第K条栅栏，算法结束.

DBCNA算法的伪代码如算法1所示：

算法1. DBCNA算法.

输入:N,K,J1,J2;

输出:K条栅栏、总能耗、平均能耗、最大能耗、栅栏节点数.

For (每一条需构建的栅栏)

选择节点数目最大的区域作为栅栏分区;

确定栅栏的第1个节点N1，坐标记作(x1,y1);

If (x1>r)

x1=r;

End If

End If

j=2;

While (栅栏右边界未接触区域右边界)

If (在传感器Nj-1的感知范围内存在其它传感器)

Nj=Nj-1感知范围内X坐标最大的传 感器;

Else

End If

j++;

End While

End For

计算总能耗、平均能耗、最大能耗、栅栏节点数.

2.3 算法的特点分析

如何降低栅栏形成过程中的能耗，是栅栏构建算法要重点考虑的问题.DBCNA算法通过以下措施降低能耗，高效构建栅栏：

1) 选择节点数最多、分布较为集中的区段作为栅栏的预选区域，这样可以使得节点在参与调度形成栅栏的过程中尽可能地减少移动距离，降低能耗.

Fig. 4 Distribution of node图4 节点分布图

3) 如果处在目标位置的节点工作方向在[-α2,α2]之间，则节点的感知方向不调整，否则转动尽量少的角度，调整为-α2，α2两者之一，使节点沿栅栏方向有最大感知距离.

形成栅栏的节点集合中，只有节点1的坐标可能是下一个节点的目标位置,其余节点若扇形区域内部没有节点，则下一个节点的目标位置都在感知圆弧上，这是因为DBCNA算法把其余节点的感知方向都转动到[-α2,α2]之间.

在栅栏形成的过程中，只要节点数量多于栅栏需要的节点数，即γLW≥βKLR，所以，只要节点密度，DBCNA算法就可以形成栅栏.β为经验参数，如图4所示，一般取1.1.

在栅栏形成的过程中，可能会出现部分节点的感知区域超出监测区域的情况.因此DBCNA算法要确保节点2的目标位置位于节点1监测区域内，从节点3开始，只要栅栏未形成完毕，目标位置一定处于监测区域内，即可保证栅栏形成过程的可连续性.

在栅栏形成过程中，设起始为n个节点，则需要先从n个节点中选中节点1，然后从n-1个节点中选出节点2，以此类推，直至栅栏形成完毕.因此在整体上，时间复杂度会随着所需节点的增加而增加.最坏情况：在形成K条栅栏的过程中，若出现最坏情况，则形成K条栅栏用尽了投撒区域内的全部n个节点.此时，时间复杂度为O(n2).

3 实验结果与分析

本文运用Matlab 7.0对此算法进行仿真，区域大小为300 m×200 m.每组实验数据采用重复50次独立实验取平均值的方式获得.如果没有特别指明，实验的默认参数为K=2，r=10 m，a=π3，γ=0.006，J1=3.6Jm，J2=1.8Jπ.目前为止，最新的有向栅栏构建算法研究是文献[10]，我们选取了其中的Strong Optimal算法、Strong Greedy算法与本文中的DBCNA算法进行了仿真比较.主要的性能参数是：形成栅栏的总能耗、平均能耗、节点数、单节点的最大能耗、能耗标准差(如定义5).默认情况下取100次实验的平均值.总能耗、平均能耗、能耗标准差越小，节点数越少，栅栏形成算法越高效，最大能耗越小，栅栏的寿命越长.

在默认参数下，给定相同的初始投撒结果，节点随机分布如图4(a)所示；DBCNA算法形成的栅栏如图4(b)所示；Strong Optimal算法形成的栅栏如图4(c)所示.DBCNA算法仅用60～70个节点就构建了2条栅栏，而Strong Optimal算法需要用110～125个节点才能构建2条栅栏，可见DBCNA算法显著提高了效率.相比Strong Optimal算法，DBCNA算法显著降低了需求的节点个数，可以用尽量少的节点达到同样的栅栏覆盖效果.而随机部署的节点可能互相重叠，在Strong Optimal算法中，先根据节点分布情况选择最佳的基准栅栏，基准栅栏中的节点不动，相邻节点之间的空洞与周围的移动节点形成最佳匹配，构建栅栏.

Fig. 5 The effect of node density图5 节点密度的影响

3.1 节点密度的影响

由于Strong Optimal算法、Strong Greedy算法对于节点数量的要求较高，在保证能形成栅栏的前提下，本文采用0.003作为起始节点密度进行仿真比较，其余实验参数均为默认参数.仿真结果如图5所示.从图5(a)中可以发现，随着节点密度的增加，3种算法的总能耗均呈显著性下降.从图5(b)中可以发现，DBCNA算法形成栅栏所需的节点数明显低于Strong Optimal算法与Strong Greedy算法形成栅栏所需的节点数.从图5(c)中可以发现，随着节点密度的增加，3种算法相应的平均能耗均呈显著性下降，但DBCNA算法对应的平均能耗始终明显低于Strong Optimal算法与Strong Greedy算法对应的平均能耗，大约降低了30%～40%.将图5(b)和图5(c)中的数据进行综合比较可以得出结论：由于节点的平均能耗明显比DBCNA算法中节点的平均能耗高，且形成栅栏所需的节点数明显多于DBCNA算法中形成栅栏所需的节点数，导致参与调度过程的节点中有节点耗能极高的可能性进一步增加，而在栅栏中耗能最高的节点耗能的高低直接决定栅栏寿命的长短.因此在栅栏形成完毕后，按照DBCNA算法形成栅栏的寿命明显高于按照Strong Optimal算法与Strong Greedy算法形成栅栏的寿命.图5(d)和图5(e)表明，节点的最大能耗与能耗标准差随着密度的增大而降低，密度越大，算法的差距越小.这是由于密度增大，可选择的移动节点增多，从而降低了最大能耗和能耗标准差.相比于Strong Optimal算法和Strong Greedy算法，DBCNA算法中节点的最大能耗、能耗标准差最大可降低32%，29%，这说明 DBCNA算法形成的栅栏寿命长、稳定性好.

Fig. 6 The effect of K图6 栅栏数K的影响

3.2 栅栏数的影响

栅栏数K的影响如图6所示.从图6(a)中可以看出，3种算法的节点总能耗均随K的增大而增大，当K>3时，随着K的增大，DBCNA算法的节点总能耗将越来越低于同等条件下Strong Optimal算法与Strong Greedy算法中的节点总能耗，当K=5时总能耗降低了25%左右.从图6(b)可以看出，随着K的增大，DBCNA算法形成栅栏所需的节点数随K的增长率明显低于同等条件下的Strong Optimal算法与Strong Greedy算法，当K不断增大时DBCNA算法形成栅栏所需节点数将越来越少于同等条件下的Strong Optimal算法与Strong Greedy算法.图6(c)表明，随着K的增大，DBCNA算法的节点平均能耗的上升趋势比Strong Optimal算法、Strong Greedy算法较为微弱，且上升幅度远低于Strong Optimal算法与Strong Greedy算法在同等情况下的上升幅度.图6(d)和图6(e)表明，随着K值的增大而缓慢增大，Strong Optimal算法和Strong Greedy算法的节点最大能耗都是指数增加的，而DBCNA算法的能耗标准差只是略有增加，基本保持不变.3种算法中，Strong Greedy算法的节点最大能耗增加幅度最大，DBCNA算法最小.这是因为随着K值的增大，移动的节点增多，单节点的最大能耗也会相应地增加，DBCNA算法局部选择最优的节点构建栅栏，故能耗标准差相差不大.相比于Strong Optimal算法和Strong Greedy算法，DBCNA算法的节点最大能耗可分别降低 35%，60%，能耗标准差最大可降低37%，50%.这说明DBCNA算法形成的栅栏寿命长、稳定性好.

Fig. 7 The effect of sensing angle图7 感知角度的影响

3.3 传感器感知角度的影响

由于传感器的感知角度发生变化时，会使得节点位于传感器扇形监测区域的几率发生变化.不同的传感器感知角度影响效果如图7所示.从图7中可以看出，感知角度增大时，节点位于扇形区域内部的几率也随之增大，导致形成栅栏所需的节点数也随感知角度的增大而增大；当K>1时，由于受到K的放大影响，形成栅栏所需的节点数在感知角度增大时的涨幅也会得到一定程度的放大.图7表明随着感知角度的增大，由于节点位于扇形区域内部的几率增加，平均能耗呈明显的下降趋势，且发生波动的频率与幅度不断减小.图7(d)和图7(e)表明，节点的最大能耗、能耗标准差基本不受感知角度的影响.

仿真结果表明，DBCNA算法显著降低了需求的节点个数,可以用尽量少的节点达到同样的栅栏覆盖效果.在Strong Optimal算法中，先根据节点分布情况选择最佳的节点构建基准栅栏，相邻节点之间的空洞与周围的移动节点形成最佳匹配，移动节点移动到相应的位置构建有向栅栏.而在DBCNA算法中，后一个节点由前一个节点决定.DBCNA算法不仅考虑了节点的移动，也考虑了节点的转动，减少了栅栏中节点之间的重叠面积.从而DBCNA算法结果要比Strong Optimal算法更优，形成的栅栏寿命长，稳定性好.

4 结束语

本文主要研究有向强栅栏覆盖问题，提出DBCNA算法，利用相邻节点之间的关系，按照从左到右的节点顺序，依次确定每一个节点的目标位置，前一个节点确定后一个节点的目标位置，并从附近节点中选择运动能耗最少的节点运动到目标位置，节点的目标感知方向由预定的移动节点决定，从而分布式构建有向强栅栏.仿真结果证明DBCNA算法可以用较少的节点高效节能地构建有向K-栅栏覆盖.

概率感知模型更符合实际情景，如何节能高效地构建概率栅栏是下一步要研究的内容.

[1]Tao Dan, Wu Tinyu. A survey on barrier coverage problem in directional sensor networks[J]. IEEE Sensors Journal, 2015, 15(2): 876-885

[2]Ban Dongsong, Wen Jun, Jiang Jie, et al. Constructingk-barrier coverage in mobile wireless sensor networks[J]．Journal of Software, 2011, 22(9): 2089-2103 (in Chinese)(班冬松, 温俊, 蒋杰, 等. 移动无线传感器网络k-栅栏覆盖的构建算法[J]. 软件学报, 2011, 22(9): 2089-2103)

[3]Wang Zhibo, Chen Honglong, Cao Qing, et al. Fault tolerant barrier coverage in wireless sensor networks[C]Proc of IEEE INFOCOM 2014. Piscataway, NJ: IEEE, 2014: 1869-1877

[4]He Shibo, Chen Jiming, Li Xu, et al. Cost-effective barrier coverage by mobile sensor networks[C]Proc of IEEE INFOCOM 2012. Piscataway, NJ: IEEE, 2012: 819-827

[5]Saipulla B Y, Liu G L, Xing X W, et al. Barrier coverage with sensors of limited mobility[C]Proc of ACM MobiHoc 2010. New York: ACM, 2010: 201-210

[6]Ma Huadong, Yang Meng, Li Deying, et al. Minimum camera barrier coverage in wireless camera sensor networks[C]Proc of IEEE INFOCOM 2012. Piscataway, NJ: IEEE, 2012: 217-225

[7]Zhang Li, Tang Jian, Zhang Weiyi. Strong barrier coverage with directional sensors[C]Proc of IEEE GlobeCom 2012. Piscataway, NJ: IEEE, 2009: 1-6

[8]Wang Yi, Cao Guohong. Barrier coverage in camera sensor networks[C]Proc of ACM MobiHoc 2011. New York: ACM, 2011: 3967-3974

[9]Wang Zhibo, Liao Jilong, Cao Qing, et al. Barrier coverage in hybrid directional sensor networks[C]Proc of IEEE MASS 2013. Piscataway, NJ: IEEE, 2013: 222-230

[10]Wang Zhibo, Liao Jilong, Cao Qing, et al. Achievingk-barrier coverage in hybrid directional sensor networks[J]. IEEE Trans on Mobile Computing, 2014, 13(7): 1443-1455

[11]Shih K P, Chou C M, Liu I H, et al, On barrier coverage in wireless camera sensor networks[C]Proc of the 24th IEEE ATMA. Piscataway, NJ: IEEE, 2010: 873-879

[12]Tao Dan, Chen Houjin. Strong barrier coverage detection algorithm for directional field of view sensor networks[J]. Journal of Beijing Jiaotong University, 2010, 35(5): 8-11 (in Chinese)(陶丹, 陈后金. 视角受限传感器网络强栅栏覆盖判定算法[J]. 北京交通大学学报， 2010, 35(5): 8-11)

[13]Zhang Qingchen, Chen Zhihui. A weighted kernel possibilistic c-means algorithm based on cloud computing for clustering big data[J]. International Journal of Communication Systems, 2014, 27(9): 1378-1391

[14]Wang Chao, Fan Xinggang, Wang Heng, et al. An effective realization scheme for strong K-barrier coverage in WSN[J]. Chinese Journal of Sensors and Actuators, 2015, 28(2): 227-233 (in Chinese)(王超, 范兴刚, 王恒, 等. 一种高效强K-栅栏覆盖构建算法[J]. 传感技术学报, 2015, 28(2): 227-233)

[15]Guvensan M A, Yavuz A G. Hybrid movement strategy in self-orienting directional sensor networks[J]. Ad Hoc Networks, 2013, 11(3): 1075-1090

Fan Xinggang, born in 1974. Associate professor and PhD. His main research interests include wireless sensor networks, parallel computing and machine learning.

Ren Yongmo, born in 1994. Undergraduate. His main research interests include wireless sensor networks.

Che Zhicong, born in 1995. Undergraduate. His main research interests include wireless sensor networks.

Wang Chao, born in 1993. Undergraduate. His main research interests include wireless sensor networks.

A Distributed Directional Barrier Construction Scheme Based on Neighbor Sport

Fan Xinggang, Ren Yongmo, Che Zhicong, and Wang Chao

(CollegeofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou310023)

K-barrier coverage is one of the hotspots in directional sensor network. However, there are few directional barrier construction schemes considering both movement and rotation until now. This paper proposes a distributed directional strong barrier construction based on neighbor actuation (DBCNA) to create directional barrier coverage with minimum actuation energy consumption, which is the total of mobility and motility energy consumption. It is just the preceding node that determines the target node location of the next node. If there is a node in the sensing region of the preceding node, the node with the largestXcoordinate is selected as the next node. If not, the point sensing radius distance from the preceding node in the horizontal direction is selected as the target location of the next node in barrier, of which the target working direction is determined by its original working direction. If this original sensing direction is in [α2,π] (αis the sensing angle), the target working direction of node isβ=α2. On the contrary, if this original sensing direction is in [π,2π-α2], the target working direction of node isβ=2π-α2. This paper also first adopts the maximum energy consumption of a single node and the mean square error of energy consumption to evaluate the performance besides energy consumption. Simulation results show this method can save 50% nodes and decrease 40%-50% mean energy consumption than other methods. This research has important theoretical and practical significance.

directional barrier coverage; target location; working direction; next node; actuation energy consumption

2015-06-09；

2016-02-16

国家自然科学基金项目(40241461,11405145) This work was supported by the National Natural Science Foundation of China(40241461, 11405145).

TP391