一种有向传感器网络栅栏覆盖增强算法*

任勇默，范兴刚，车志聪，王 超

（浙江工业大学计算机科学与技术学院，杭州 310023）

一种有向传感器网络栅栏覆盖增强算法*

任勇默，范兴刚*，车志聪，王 超

（浙江工业大学计算机科学与技术学院，杭州 310023）

K-栅栏覆盖是有向传感器网络覆盖控制的研究热点之一。提出一种基于邻居节点运动的有向强栅栏构建算法（NSDBC）。在形成栅栏的节点集合中，按照从左到右的节点顺序，依次确定每一个节点的目标位置，前一个节点确定后一个邻居节点的目标位置，后一个节点的选取仅与前一个节点有关。后一个节点从前一个节点附近节点中选择能耗最少的节点运动到目标位置，从而构建有向强栅栏。仿真结果证明了该栅栏构建方法能够用较低能耗和较少节点构建有向栅栏。本文的研究对提升无线传感器网络的性能具有重要的理论与实际意义。

有向栅栏覆盖；NSDBC；目标位置；邻居节点；运动能耗

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

栅栏覆盖目前已有一些研究工作［2-14］。Kumar定义了强栅栏，弱栅栏［2］；曹莹莹将影响栅栏覆盖生命期的因素描述为一个多目标优化问题［3］；杨涛运用栅栏构筑算法DPA，构筑多条栅栏，实现多栅栏覆盖［4］；罗卿在概率性感知模型基础上，提出一种栅栏覆盖控制算法，调度传感器使冗余节点睡眠，达到减少能耗和延长网络寿命的目的［5］；Li L研究了无线传感器网络（WSN）一维K-覆盖问题，分析kcoverage比例、全k-coverage概率和部分k-coverage概率［6］；班冬松研究了全向移动传感器网络K-栅栏覆盖问题，提出了一种能量高效的栅栏覆盖构建算法CBIGB［7］；Jie Tian研究了两维的栅栏覆盖［8］。

马华东研究了视频传感器网络中的，最少的有向视频节点组建栅栏问题［9］；陶丹研究如何调整有向节点的感知方向组建有向强栅栏的问题［10］；Zhang等研究转动有向节点的构建强栅栏［11］；Zhibo Wang研究了混合有向网络的栅栏覆盖［12］，根据网络拓扑构建权重栅栏图WBG，再运用顶点不相交的路径算法构造K-栅栏。Amac基于移动能耗和转动能耗，研究了有向网络的覆盖增强［13］。张美燕研究了最大K有向覆盖问题，设计了一种分布式启发式算法，在一跳邻居范围内对传感器节点的感知方向进行协同调度，使得目标集合被有向K覆盖的时间最大［14］。

利用附近节点之间的位置关系，可以选择最优的节点构建栅栏。我们研究了全向强栅栏构建，提出了PMNSB算法［15］。在此基础上，本文研究如何利用节点之间的位置关系，调度节点的运动，节能高效的构建强K-栅栏覆盖，提出一种基于邻居节点运动的有向强栅栏构建算法（Distributing Directional Strong Barrier Construction Based on Next Node Sports，NSDBC）。本论文的主要贡献如下：根据周围邻节点信息，分布式的确定节点的目标位置，并选择运动能耗最少的节点移动到目标位置，构建有向强栅栏。

本文余下章节安排如下：第1节描述网络模型。第2节详细介绍分布式有向强栅栏构建方法（NSDBC）。第3节通过仿真实验对提出的算法进行性能评估。第4节总结全文并介绍下一步工作。

1 相关模型和定义

有向传感器节点方向可调感知模型可以采取四组表示＜P,r,a,β＞，如图1所示。其中P=（x,y）表示节点的位置坐标，r表示节点的感知半径，β表示节点在t时刻的工作方向（或感知方向），取值范围为0≤β≤2π，α表示节点的感知角度，为相对于x正半轴的方向角。则当α=2π时，此时有向感知模型则变成了全向感知模型，是有向感知模型的一个特例。

图1 可旋转有向传感器的传感模型

研究有向栅栏问题之前，有如下假设：

①所有传感器的感知半径和感知角度均相同。

②所有传感器的转动功率和平地上的单位距离功耗均相同。

③传感器监视范围内的信号强度相同，且能在范围内以100%的可能性监测到事件。

定义2 有向节点运动能耗 有向节点运动能耗是指有向移动节点运动到目标位置的能耗，由移动能耗和转动能耗组成。第i（i≥2）个节点的转动能耗如式（1），运动能耗如式（2）所示，其中的参数见表1，式（1）标明，若0≤β≤α/2，或者2π-α/2≤β≤2π，则不进行转动；若α/2≤β≤π，转至β=α/2处；若π＜β＜2π-α/2，转至 β=2π-α/2处。式（2）表明移动能耗和转动能耗之和就是有向节点运动能耗。

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

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

2 基于邻居节点运动的有向强栅栏构建算法（NSDBC）

Zhibo Wang考查区域内的所有静态节点组成的网络拓扑结构，采用顶点不重复的K条路径的图论算法找到形成栅栏的目标位置，然后移动节点和这些目标位置进行最佳匹配，这需要全局拓扑信息，通信和开销较大，而且不适用于要减少通信和计算开销，PMNSB算法把构造K-栅栏这个复杂的问题分成小问题，先在小的子区域构造1MNSB，这些1-栅栏合起来就是强K-栅栏。但PMNSB算法不能用于有向强栅栏的构建，在有向栅栏中，有向节点感知不再是圆形，而是扇形，单独的圆心不能确定一个有向节点的位置。而且PMNSB算法仅考虑节点的移动，没有考虑节点的转动，而转动节点是解决有向覆盖问题的主要方法。在此基础上，我们提出一种分布式基于邻居节点运动的有向强栅栏构建算法（distributing directional strong barrier construction based on next node sports，NSDBC）。

2.1 算法的基本思想

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

2.2 算法具体过程

NSDBC算法伪代码如图2所示，参数的定义如表1所示。

图2 NSDBC算法伪代码

NSDBC算法具体步骤如下：

步骤1 确定栅栏形成区域。

在投撒传感器完毕后，分别统计各个区间段0≤y≤2r、2r≤y≤4r、4r≤y≤6r、…、2nr≤y≤W内的节点个数（n为某个整数，且W-2nr≤2r）。选取节点个数最多的区间段作为第1条栅栏形成的预选区域，若出现个数并列最多的区间段，则选取其中纵坐标方差最小的区间段作为预选区域。这是因为区间段内节点纵坐标方差小时，栅栏在纵向上发生的偏离程度更小，栅栏位置更为稳定。

步骤2 确定有向强栅栏的第一个节点。

表1 参数定义

步骤3 确定第二个节点的目标位置，并选择节点运动。

判断剩余的所有节点中，是否有节点在第1个节点扇形区域内部。若有，选出扇形区域内横坐标最大的节点（即最靠右的节点）作为第2个节点，不进行移动。只将其按照式（1）调整方向角，并计算运动能耗。例如，在图3（a）中，节点A为第一个节点，圆心为B的虚扇形为第二个节点的目标位置，圆心为B的节点主要转动到虚线位置即成为构建栅栏的第二个节点。若没有节点在第1个节点扇形区域内部，则先判断第1个节点对应的扇形区域中，节点自身的坐标、对应扇形区域的两个端点坐标、弧上的中点坐标这4个坐标中哪个点对应的横坐标最大，将其中横坐标最大的点作为第2个节点需要移动的目标位置，若选出的目标位置超出矩形检测区域，或出现同时有2个点横坐标并列最大的情况，则认为此次选择无效，重新将第1个节点自身的坐标作为第2个节点的目标位置。选定目标位置后，找出剩余所有节点中与目标位置之间欧氏距离最短的节点作为第2个节点，并沿着最短路径移动至目标位置，并按照式（1）调整方向角，并记录总能耗E=E+E2。例如，在图3（b）中，节点A为第一个节点，圆心为B的虚扇形为第二个节点的目标位置，C为移动节点。

图3 第二个节点的选择

图4 节点的选择

步骤4 确定其余所需节点的目标位置，并选择节点移动。

在第i（i≥2）个节点调度完毕后，若在其感知区域内部存在节点，横坐标最大的节点就是第i+1个节点的坐标。例如，在图4（a）中，节点A中，节点C的横坐标比节点D大，则节点C的坐标就是下一个节点的坐标，圆心为C的虚扇形就是第i+1个节点的目标位置。如果感知区域内部没有节点，则令第i（i≥2）个节点正右方向一个半径距离处作为下一节点的坐标位置，然后选出剩余所有节点中与其欧氏距离最短的节点，将其沿最短路径移动至与目标位置重合，并按式（1）方法调整方向角。例如，在图4b中，节点A中没有节点，则节点A的正右方向一个半径距离处端点B作为下一个节点的坐标位置，节点C的距离端点B最近，则圆心为B的虚扇形为下一个节点的目标位置。则节点C运动到目标位置。统计当前的运动总能耗E=E+Ei。

步骤5 形成第1条栅栏。

步骤6 构建其余K-1条栅栏。

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

2.3 算法的理论分析

由于在形成栅栏的过程中，需要通过减少节点移动距离和转动角度来降低能耗，从而延长栅栏的寿命。因此需在投撒节点完毕之后，选出一个节点个数最多，且分布较为集中的区域段作为栅栏的预选区域，分布式地调度附近节点形成栅栏。这样可以使得节点在参与调度形成栅栏的过程中尽可能地减少移动距离，降低能耗。

在转动过程中，NSDBC算法可以在移动完毕后，将转动能耗降至最低，使栅栏长度得到最大限度的增长。同时能够用较少的节点构建栅栏，从而在一定程度上降低对投撒密度的要求，节约节点，降低通信开销。

在栅栏的形成过程中，若有节点处于已调度完毕节点扇形区域的内部，则为了较大程度上节省该节点的能耗，同时尽可能地延长栅栏的已有长度，NSDBC算法选取扇形区域内最靠右的节点。由于传感器节点的横坐标在x轴方向上服从随机分布，因此在已知有节点处于扇形区域内部的情况下，该节点横坐标的期望值应为扇形区域对应节点的横坐标+r/2（由于有多个节点同时位于同一个扇形内部的几率极低，在这里忽略不计，仅考虑只有一个节点位于扇形区域内部的情况）。又因为单个传感器节点每转动π耗能为1.8 J，每移动1 m耗能为3.6 J，所以为了节省该节点的能耗，NSDBC算法对区域内节点仅进行转动，期望在栅栏已有长度基础上增加r 2的长度。

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

在时间复杂度方面，由于计算一个节点的运动能耗所花费的时间一定，考虑在最坏情况下，有大量的节点落在扇形区域内，恰巧使用了投撒区域内全部的节点形成了K条栅栏，在栅栏形成过程中，设总共有n个节点，则需要从这n个节点中选中第1个节点，然后从n-1个节点中选出第2个节点，以此类推，直至栅栏形成完毕，时间复杂度为：O（n2）。

3 仿真结果

本文运用Matlab7.0对此算法进行仿真，每组实验数据采用重复50次独立实验取平均值的方式获得。参考文献［13，15］，实验的默认参数如表2所示，其中单个传感器节点每转动180∘耗能为1.8 J，每移动1 m耗能为3.6 J。

我们选取了文献［12］中的strong optimal算法、strong greedy算法与本文中的NSDBC算法进行了仿真比较。

表2 实验参数

在默认参数下，给定相同的初始投撒结果，节点随机分布如图5所示。

图5 节点随机分布图

NSDBC算法的形成的栅栏如图6所示，strong optimal算法的形成的栅栏如图7所示。

图6 NSDBC算法

图7 Strong optimal算法

3.1 节点密度的影响

由于strong optimal算法、strong greedy算法对于节点数量的要求比较高，在保证能形成栅栏的前提下，本文采用0.003作为起始节点密度进行仿真比较，其余实验参数均与表2中的默认参数一致。仿真结果如图8～图10所示。

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

图9 节点密度VS形成栅栏所需的节点数

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

从图8中可以发现，随着节点密度的增加，3种算法所对应的总能耗均呈显著性下降，在节点密度较低的情况下，NSDBC算法的总能耗明显低于strong optimal算法和strong greedy算法。从图9可以发现，NSDBC算法形成栅栏所需的节点数明显低于strong optimal算法与strong greedy算法形成栅栏所需的节点数。从图10中可以发现，随着节点密度的增加，三种算法相应的平均能耗均呈显著性下降，但NSDBC算法对应的平均能耗始终明显低于strong optimal算法与strong greedy算法对应的平均能耗。将图9和图10中的数据进行综合比较可以得出结论：由于节点的平均能耗明显比NSDBC算法中节点的平均能耗高，且形成栅栏所需的节点数明显地多于NSDBC算法中形成栅栏所需的节点数，导致参与调度过程的节点中，有节点耗能极高的可能性进一步增加，而在栅栏中耗能最高的节点耗能的高低直接决定栅栏寿命的长短。因此在栅栏形成完毕后，按照NSDBC算法形成栅栏的寿命明显高于按照strong optimal算法与strong greedy算法形成栅栏的寿命。

3.2 栅栏数的影响

栅栏数K的影响如图11～图13所示。从图11中可以看出，三种算法的节点总能耗均随K增大而增大，当K＞3时，随着K的增大，NSDBC算法的节点总能耗将越来越低于同等条件下strong optimal算法与strong greedy算法中的节点总能耗。

图11 栅栏数VS节点总能耗

从图12可以看出，随着K的增大，NSDBC算法形成栅栏所需的节点数随K的增长率明显低于同等条件下的strong optimal算法与strong greedy算法，当K不断增大时，NSDBC算法形成栅栏所需节点数将越来越少于同等条件下的strong optimal算法与strong greedy算法。图13表明，随着K的增大，而NSDBC算法的节点平均能耗的上升趋势比于strong optimal算法、strong greedy算法较为微弱，且上升幅度远低于strong optimal算法与strong greedy算法在同等情况下的上升幅度。

图12 栅栏数VS形成栅栏所需的节点数

图13 栅栏数VS节点平均能耗

3.3 传感器感知角度的影响

由于传感器的感知角度发生变化时，会使得节点位于传感器扇形监测区域的几率发生变化。不同的传感器感知角度影响效果如图14～图16所示。

图14 感知角度VS总能耗

图15 感知角度VS形成栅栏所需的节点个数

图16 感知角度VS节点平均能耗

从图15可以看出，感知角度增大时，节点位于扇形区域内部的几率也随之增大，导致形成栅栏所需的节点数也随感知角度的增大而增大，当K＞1时，由于受到K的放大影响，形成栅栏所需的节点数在感知角度增大时的涨幅也会得到一定程度的放大。

图16表明随着感知角度的增大，由于节点位于扇形区域内部的几率增加，平均能耗整体上呈明显的下降趋势，且发生波动的频率与幅度不断减小。

4 结论

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

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

［1］ 任彦，张思东，张宏科.无线传感器网络中覆盖控制理论与算法［J］.软件学报，2006，17（3）：422-433.

［2］ Kumar S，Lai T H，Arora A.Barrier Coverage with Wireless Sensors［C］//Proc of the 11th Annual International Conference on Mobile Computing and Networking.2005，284-298.

［3］ 曹莹莹，黄刘生，朱立才，等.一种协作的异构传感器最优栅栏覆盖模型［J］.小型微型计算机系统，2012，33（11）：2457-2462.

［4］ 杨涛，慕德俊.无线传感器网络多栅栏覆盖构建算法研究［J］.弹箭与制导学报，2012，32（2）：173-176.

［5］ 罗卿，林亚平，王雷，等.传感器网络中基于数据融合的栅栏覆盖控制研究［J］.电子与信息学报，2012，34（4）：825-831.

［6］ Li L，Zhang B，Zheng J.A Study on One-Dimensional k-Coverage Problem in Wireless Sensor Networks［J］.Wireless Communications and Mobile Computing，2013，13（1）：1-11.

［7］ 班冬松，温俊，蒋杰，等.移动无线传感器网络K-栅栏覆盖的构建算法［J］.软件学报，2011，22（9）：2089-2103.

［8］ Jie Tian，Zhang Wensheng，Wang Guiling，et al.2D k-Barrier Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks［J］.Computer Communications，2014，4（3）：31-42.

［9］ Ma H，Yang M，Li D，et al.Minimum Camera Barrier Coverage in Wireless Camera Sensor Networks［C］//Proc IEEE INFOCOM，Orlando，FL，USA，2012：217-225.

［10］Tao D，Tang S，Zhang H，et al.Strong Barrier Coverage in Directional Sensor Networks［C］//Comput Commun，2012，35（8）：895-905.

［11］Zhang L，Tang J，Zhang W.Strong Barrier Coverage with Directional Sensors［C］//ProcIEEEGlobeCom，Honolulu，HI，USA，2009：1-6.

［12］Wang Zhibo，Liao Jilong，Cao Qing，et al.Achieving k-Barrier Coverage in Hybrid Directional Sensor Networks［J］.IEEE Transactions on Mobile Computing，2014，13（7）：1443-1455.

［13］Amac Guvensan，Gokhan Yavuz.Hybrid Movement Strategy in Self-Orienting Directional Sensor Networks［J］.Ad Hoc Networks，2013，11（3）：1075-1090.

［14］张美燕，蔡文郁.无线视频传感器网络有向感知K覆盖控制算法研究［J］.传感技术学报，2013，26（5）：728-733.

［15］王超，范兴刚.一种高效强K-栅栏覆盖构建算法［J］.传感技术学报，2015，28（2）：227-233.

任勇默（1994-），男，本科生，主要研究领域为无线传感器网络；

范兴刚（1974-），男，副教授，工学博士，研究领域为传感器网络，网络通信、实时通信，分布式实时系统的设计，xgfan@ zjut.edu.cn；

车志聪（1995-），男，本科生，主要研究领域为无线传感器网络；

王 超（1993-），男，本科生，主要研究领域为无线传感器网络。

An Distributing Scheme for Directional Barrier Coverage Enhancing in DSN*

REN Yongmo，FAN Xinggang*，CHE Zhicong，WANG Chao
（College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China）

K-barrier coverage is one of the hot spot in directional wireless sensor network.This paper proposes a distributing directional strong barrier construction scheme based on next node sports（NSDBC）to create directional barrier coverage with lower energy consumption.It is only the previous node that determines the next target node position for barrier；the target node position is constituted by the coordinate of center and working direction of sensing sector.The previous node finds node in its vicinity that moves to target next node location with minimum moving energy consumption and adjusts its working directional to target direction with minimum rotating energy consumption. Simulation results show this method could effectively constitute K-barrier coverage，and enhance the coverage performance of DSN.This research has important theoretical and practical significance.

directional barrier coverage；NSDBC；target position；neighbor node；sports energy consumption EEACC：7230

TP273

A

1004-1699（2015）07-1051-07

10.3969/j.issn.1004-1699.2015.07.019

项目来源：“十二五”国家科技支撑计划项目（2012BAD10B01）

2015-02-19 修改日期：2015-05-13