入侵轨迹建模与WSN栅栏覆盖分段调度算法研究*

戴光麟，方　凯，戴国勇，徐　慧，毛科技

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

入侵轨迹建模与WSN栅栏覆盖分段调度算法研究*

戴光麟，方凯，戴国勇，徐慧，毛科技*

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

无线传感器网络栅栏覆盖在入侵检测方面发挥着重要作用，如何调度栅栏并延长网络的生存时间已成为重点研究问题。在无线传感器网络中设计合理的调度算法，分时激活传感器节点从而延长网络生存时间是大多数研究的方向，然而仅仅通过分时调度传感器节点已很难大幅度提高网络的生存时间。因此设计了一种分时与分段相结合的无线传感器网络栅栏调度算法，该算法通过分析入侵目标穿越传感器网络部署区域的行为特征，建立入侵目标的轨迹模型，该模型在保证栅栏对入侵目标具有较高检测率的情况下预测入侵目标可能穿越栅栏的区域并分段激活栅栏从而大大减少了传感器节点的能量消耗。最后仿真实验验证了本文算法与传统的分时调度算法相比能大幅度提高网络的生存时间。

无线传感器网络；入侵目标建模；调度算法；节能

EEACC：7230；6150Pdoi：10.3969/j.issn.1004-1699.2016.05.021

传感器节点的能量受限，如何延长网络的生存时间是关键问题［1］。无线传感器网络栅栏覆盖有着广泛的用途，其主要作用是监测试图穿越部署区域的入侵目标［2］。在生态方面，将栅栏部署在自然保护区边界可防止外来物种入侵。在林业保护方面，将栅栏部署在森林火灾区域边缘，可有动态检测火灾蔓延情况。在环保方面，将栅栏部署在工厂周围检测污染物质的扩散。

在军事方面，可将栅栏部署在阵地前沿已监测敌人的入侵等［3-5］。

目前无线传感器网络栅栏覆盖研究已取得丰厚的成果，如Kumar等人首次提出了强K-barrier和弱K-barrier覆盖的概念，并判断部署区域是否被强K-barrier覆盖［6］。Anwar Saipulla等人提出了利用权重有向图的最大流算法求解静态传感器网络中形成栅栏的数量［7］。在后续研究中又提出了line-based部署方式并使用最大流算法派遣移动节点修补栅栏间隙使得所有节点移动距离之和最小［8］。Tian J等人提出了二维K-栅栏覆盖问题，并将部署区域划分为子区域分别构建栅栏的思想［9］。Chen J等人利用概率感知模型，以入侵者的速度为限制条件，将入侵监测问题转化为网络最大流问题，并根据节点间距离和剩余能量，提出一种有界栅栏构造方法［10］。

为了延长栅栏生存时间，又提出很多栅栏调度算法，如Kumar等人研究了如何调度已经构建的栅栏形成强K-栅栏，使得栅栏中传感器节点的能量被充分利用从而延长网络的生存时间，提出了Optimal Sleep-Wakeup算法，该算法的结果是栅栏生存时间的理想上界［11］。Mostafaei H等人又提出了基于自动学习的LABC算法，并将该算法与Optimal Sleep-Wakeup进行对比［12］。罗卿等人提出了基于概率感知模型的方法，并在此基础上提出了一种栅栏覆盖控制算法，该算法借助分治法构造栅栏，并调度冗余节点达到延长网络寿命的目的［13］。然而这些算法并没有考虑入侵者的轨迹特征，由于在实际监测中，栅栏只有很短一段能检测到入侵者，其余栅栏都处于激活盲等状态，这会消耗大量的能量。

结合上述研究，本文提出了一种入侵模型预测下的WSN栅栏分段调度算法SSA（Segmented Scheduling Algorithm）。该方法通过分析入侵目标的行为特性，建立入侵目标的轨迹模型，预测入侵目标可能会穿越栅栏的位置，并有针对性的开启栅栏的某一段，以拦截的方式检测入侵目标。同时又分析了该方法的检测率以及网络生存时间。SSA算法通过牺牲较小的检测率能大幅度提高传感器网络的生存时间。

1　入侵模型

当入侵目标带有目的性的穿越某块带状区域时，往往会选择最短路径或者接近最短路径的轨迹进行穿越。如在军事上，入侵者想穿越阵地前沿的带状区域进行偷袭，不会在阵地前沿的区域内徘徊，最可能沿直线径直穿越。以垂直带状区域的方向为基准，偏离该方向的角度表示入侵角度。因此入侵者选择入侵角度的概率是不同的，入侵角度越小，被选择的概率越大，对应的穿越路径越短，越有利于偷袭。入侵角度越大，穿越的路径越长，消耗的时间越多，不利于偷袭。假设穿越速度均匀，影响穿越某块区域的最大因素是入侵的角度。但是在实际穿越某块区域的过程中，入侵角度的选择还要考虑环境因素的影响。

入侵者以一定角度x穿越已部署传感器节点区域，如图1所示，箭头表示入侵的方向。角度x的绝对值|x|越大，被选择作为入侵角的概率越低，|x|越小，被选择作为入侵角的概率越高。基于上述分析对入侵目标建立入侵模型，该模型综合考虑了入侵目标的穿越特性以及环境对入侵角选择的影响。该模型的入侵角度服从f（x）分布，如式（2）所示。式（2）中s为常数，表达式如式（1）所示。该模型的建立是以实际入侵穿越的情况为依据，因此具有较高的真实性。

图1　入侵角度图

通过概率密度函数f（x）可求得入侵角度x∈（-α，α）的概率P，求解过程如式（3）、式（4）所示。在本文后续章节中概率f表示分段激活的栅栏对入侵目标的检测率。

式（1）、式（2）、式（4）中r为影响因子（环境对入侵的影响因素），且r＞0。当入侵环境中障碍物较少时，r取值为r1，栅栏检测率为P1（α）。当入侵环境中障碍物较多时，r取值为r2，栅栏检测率为P2（α）。此时r的取值r1＜r2，对应的检测率P1（α）＞P2（α）。

2　调度算法及性能分析

2.1SSA调度算法

入侵目标穿越栅栏部署区域可能以直线的形式穿越也可能是非直线穿越，假设通过文献［8，14-16］等方法已经形成了n条强栅栏，栅栏间距离为d，栅栏长度为L，且d≤L，如图2所示。本文以调度n条栅栏形成强2-栅栏为例，分析了直线穿越和非直线穿越情况下的栅栏生存时间和检测率。

图2　入侵路径图

假设每条栅栏都由n个传感器节点均匀分布组成，节点间距离D=2R，其中R为传感器节点感知半径，每条栅栏都从1～n进行编号，相同编号的传感器节点横坐标相同。SSA调度算法首先将栅栏1中的传感器节点全部激活，如果节点编号为s的传感器节点检测到有目标入侵，则在满足检测率为P的情况下利用入侵模型计算出入侵角的范围α，然后激活栅栏2中传感器节点编号范围为（s-dtanα/（2R），s+dtanα/（2R））的栅栏，该段栅栏长度Ln=2dtanα。如图3所示。当栅栏1的能量耗尽，接着将栅栏2的传感器节点全部开启，栅栏3则分段式激活，以此类推，直到第m-1条栅栏的能量耗尽最后不能形成强2-栅栏为止，标志着整个传感器网络最终死亡。本文算法通过分段激活的方式检测入侵目标，当第1条栅栏检测到入侵目标后，以感知到入侵目标的节点作为入侵点，对其余条栅栏采取同样的分段激活策略，如图4所示，图中箭头表示入侵轨迹，圆点表示检测到入侵目标的传感器节点。具体的SSA调度算法如表1所示。

图3　栅栏分段激活图

图4　n-栅栏分段激活图

表1　SSA调度算法

2.2网络生存时间分析

利用SSA调度算法调度n条栅栏形成2-栅栏，假设每条栅栏有n个传感器节点成，传感器节点包含的能量为E，对应的生存时间为t，感知半径为F。传感器处于激活状态时单位时间内消耗的能量为e。分析传感器网络总共的生存时间以栅栏1、2为例。当入侵目标被栅栏2检测到的概率为F时，栅栏2中处于激活状态的栅栏长度为Ln，该段栅栏单位时间内总共消耗的能量为eb1，如式（5）所示。栅栏1总共消耗的能量为eb2，如式（6）所示。因此栅栏1消耗的能量是栅栏2的u倍，如式（7）所示。由于传感器节点能量与生存时间相对应，所以栅栏2的生存时间是栅栏1的u倍。

基于上述分析，可以计算出拥有m条强栅栏的传感器网络调度形成强2-栅栏其生存时间为T，如式（8）所示，简化后如式（9）所示。

2.3非直线穿越的检测率

利用公式（4）能方便的求出直线穿越栅栏部署区域的检测率，然而实际入侵目标并不一定沿直线穿越部署区域，因此本节研究当入侵目标以非直线穿越部署区域被栅栏2中激活的Ln段栅栏检测到的概率。如果入侵目标在相距为d的栅栏1和栅栏2之间有多次改变方向的行为，假设其改变方向的位置都在两条栅栏的均匀分割线上，如图5所示。以栅栏部署方向为x轴方向，以入侵点为原点建立横坐标系。

假设入侵目标在穿越部署区域过程中有z次改变方向（包括在栅栏1处的入侵方向），角度分别为α1、α2、α3…αz，且都满足f（x）分布，则入侵目标最后到达栅栏2的横坐标为y∈（-∞，+∞），如式（10）所示。

图5　非直线穿越图

由于z次改变方向是独立同分布事件，因此入侵目标被栅栏2中Ln段栅栏检测到的概率服从g（y）z分布，如式（12）所示，式（11）中f（a1，a2，a1…az）为z次事件的联合概率密度。所以入侵目标被Ln段栅栏检测到的概率Py如式（13）所示。由于概率密度函数f（x）比较复杂，本节只给出概率密度函数g（y）z的计算方法，并计算了z=1时的概率密度函数g（y）1，如式（14）所示。并以实验验证了入侵目标以非直线穿越比直线穿越部署区域被Ln段栅栏检测到的概率更高。

3　仿真实验

实验中设置栅栏长度L=1 000 m，栅栏间距离d=150 m，α∈（0，π/2）。传感器节点的能量为100 W，对应的生存时间t=24×60×60×7 s（一周），实验中Ln段栅栏是被激活的一段栅栏，如图3、图5所示。通过以下实验验证本文调度算法的性能。

3.1检测率

本次实验验证栅栏检测率是否与理论推导相符合。当栅栏1监测到入侵目标后，采取分段激活的策略，相应的激活栅栏2中的Ln段栅栏用于监测入侵目标。实验中影响因子r=0.5，分别验证了入侵次数为50次、100次、300、次1 300次的情况，实验结果如图6所示，横坐标为α，纵坐标为检测率P。

实验结果表明随着实验次数的增加，实际的检测率是渐渐趋向理论证明。入侵次数比较少时检测率波动比较大，当num=1 300次时，检测率的波动非常小且与理论推导基本吻合。当α趋近于π 2时，栅栏2的节点被全部激活，此时检测率P=1，实验结果验证了入侵角服从（fx）分布的检测率。

图6　直线穿越检测率图

3.2影响因子

入侵目标的入侵角度会受外界环境以及自身因素的影响，因此本文设计的入侵模型考虑了影响因子。本次实验验证影响因子对检测率的影响。当栅栏1监测到入侵目标后，采取分段激活的策略，相应的激活栅栏2中的Ln段栅栏用于监测入侵目标。由于入侵模型的概率密度函数f（x）是拱形函数，因此影响因子r的取值不同会严重影响栅栏的检测率。当SSA分段调度算法在实际应用中可根据入侵目标的特性和环境因素估计合适的影响因子。实验中研究r分别为0.25、0.5、1.0、2.0时对检测率的影响。

图7　影响因子图

实验结果如图7所示，横坐标为α，纵坐标为检测率P，每次实验都有3 000个目标穿越栅栏。实验结果表明r的值越小，被栅栏2中激活的栅栏检测到的概率越高。

3.3能量消耗

当入侵目标试图穿越栅栏部署区域时，根据SSA算法，首先会被全激活的栅栏1检测到，然后才会被部分激活的栅栏2检测到。本次实验研究全激活状态的栅栏和部分激活状态的栅栏的能量消耗。每次实验都有4 000个目标穿越栅栏，影响因子r=0.5，栅栏2监测一个入侵目标处于激活状态的时间维持180 s，然后才会将栅栏切换为睡眠状态。实验结果如图8所示，横坐标为α，纵坐标为两条栅栏消耗能量的倍数关系，Theory为理论分析的结果，由式（7）计算得到。Practice为实验得到的结果。

图8　能耗关系图

实验结果表明全激活状态的栅栏在监测入侵目标过程中消耗的能量远远大于部分激活状态的栅栏。从实验结果可以看出随着α增大，栅栏实际消耗能量与理论分析一致。但是实际的结果并非平滑曲线且α比较小的时候与理论分析的结果存在较大差异，这是因为当α较小时，α即使在增加，但处于激活状态的节点还是和α没改变之前是同一个传感器节点。α改变但处于激活状态的节点数量不变，能量消耗也就不会变，所以会出现图中的梯度下降的情况。

3.4生存时间

传感器网络的生存时间至关重要，本次实验研究SSA算法调度4条强栅栏形成强2-栅栏的网络生存时间，并与文献［11］最佳调度算法和文献［17］随机调度算法进行对比。其中文献［11］的最佳调度算法充分利用了传感器节点的能量，已经是传感器网络栅栏生存时间问题的上限。然而本文的方法通过牺牲较小的检测率能大幅度提高栅栏的生存时间。在保证检测率为90%的情况下与上述算法进行对比，实验中影响因子r=0.5，实验结果如图9所示，横坐标表示入侵的次数，纵坐标表示生存时间。

图9　生存时间图

图9中SSA Practice表示实验得到的结果，SSA Theory表示理论上的生存时间，可通过式（9）计算得到。实验结果表明在检测率为90%的情况下，SSA算法的网络生存时间远远大于最佳调度算法（Optimal Sleep-Wakeup）和随机调度算法（RIS）。因此在很多不要求检测率为100%的情况下使用SSA算法能大幅度延长网络的生存时间。

3.5非直线穿越情况下的检测率

入侵目标很大可能以非直线的形式穿越栅栏部署区域。本次实验研究曲线穿越情况下的栅栏检测率。实验中入侵目标多次在栅栏1和栅栏2之间改变入侵方向，改变方向的次数分别为0、1、3、5、15，栅栏2中激活的长度仍然为Ln，实验中影响因子r=0.5，实验结果如图10所示，横坐标为α，纵坐标为检测率P，每次实验都有3 000个目标穿越栅栏。

图10　非直线穿越检测率图

实验中cdnum=0表示入侵目标以直线形式穿越栅栏，实验结果表明入侵目标在穿越栅栏过程中改变方向的次数越多则被栅栏2中激活段栅栏检测到的概率越高。同时表明不管是沿直线还是非直线轨迹穿越栅栏部署区域，当入侵角范围属于（-α，α）时，栅栏检测率至少为P（α）。

4　总结

针对目前已提出的一些无线传感器网络栅栏调度算法并不能大幅度提高网络生存时间问题，本文提出了SSA算法，该算法在保证检测率的情况下分段激活并调度栅栏。与传统算法不同的是SSA算法通过牺牲较小的检测率能大幅度提高传感器网络的生存时间。但是该算法还是存在一定资源的浪费，如最后的栅栏不能被充分利用，以及该算法不能用于要求检测率为100%的场景中。后续工作将进一步研究入侵目标，建立更加完善的入侵模型，以此来提高栅栏的检测率，并设计更合理的调度算法。

［1］陈立建，周雪，雷艳静，等.一种基于功率控制的WSN自适应能量高效传输模式研究［J］.传感技术学报，2014，27（6）：835-841.

［2］任勇默，范兴刚，车志聪，等.一种有向传感器网络栅栏覆盖增强算法［J］.传感技术学报，2015，28（7）：1051-1057.

［3］Chen A，Kumar S，Lai T H.Designing Localized Algorithms for Barrier Coverage［C］//Proceedings of the 13th Annual ACM Inter⁃national Conference on Mobile Computing and NetworkingACM，2007：63-74.

［4］班冬松，温俊，蒋杰，等.移动无线传感器网络k-栅栏覆盖构建算法［J］.Journal of Software，2011，22（9）：2089-2103.

［5］郭新明.高效无线传感器网络强k-栅栏覆盖节能算法［J］.计算机应用，2013，33（8）：2104-2107.

［6］Kumar S，Lai T H，Arora A.Barrier Coverage with Wireless Sen⁃sors［J］.Wireless Networks，2007，13（6）：284-298.

［7］Saipulla A，Westphal C，Liu B，et al.Barrier Coverage of Line-Based Deployed Wireless Sensor Networks［C］//INFOCOM 2009，IEEE.IEEE，2009：127-135.

［8］Saipulla A，Westphal C，Liu B，et al.Barrier Coverage with Line-Based Deployed Mobile Sensors［J］.Ad Hoc Networks，2013，11（4）：1381-1391.

［9］Tian J，Zhang W，Wang G，et al.2D k-barrier Duty-Cycle Schedul⁃ing for Intruder Detection in Wireless Sensor Networks［J］.Com⁃puter Communications，2014，43（5）：31-42.

［10］Chen J，Li J，Lai T H.Energy-Efficient Intrusion Detection with a Barrier of Probabilistic Sensors：Global and Local［J］.Wireless Communications IEEE Transactions on，2013，12（9）：4742-4755.

［11］Kumar S，Lai T H，Posner M E，et al.Optimal Sleep-Wakeup Algo⁃rithms for Barriers of Wireless Sensors［C］//Broadband Communi⁃cations，Networks and Systems，2007.BROADNETS 2007.Fourth International Conference on.IEEE，2007：327-336.

［12］Mostafaei H，Meybodi M R.An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks［J］.Wireless Personal Communications，2014，77（3）：2099-2115.

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

［14］Chen D Z，Gu Y，Li J，et al.Algorithms on Minimizing the Maxi⁃mum Sensor Movement for Barrier Coverage of a Linear Domain［J］.Discrete&Computational Geometry，2012，50（2）：374-408.

［15］Eftekhari M，Kranakis E，Krizanc D，et al.Distributed Algorithms for B Arrier Coverage Using Relocatable Sensors［J］.Proceedings of the Annual Acm Symposium on Principles of Distributed Com⁃puting，2013：383-392.

［16］He S，Gong X，Zhang J，et al.Barrier Coverage in Wireless Sensor Networks：From Lined-Based to Curve-Based Deployment［C］//IN⁃FOCOM，2013 Proceedings IEEEIEEE，2013：470-474.

［17］Kumar S，Lai T H，Balogh J.on-Coverage in a Mostly Sleeping Sensor Network［J］.ProcAcm Mobicom，2004，14（3）：277-29.

戴光麟（1979-），男，汉族，浙江工业大学计算机学院讲师，博士研究生，主要研究方向为无线传感器网络；

方凯（1992-），男，汉族，浙江工业大学计算机学院硕士研究生，主要研究方向为无线传感器网络；

毛科技（1979-），男，汉族，浙江工业大学计算机学院副教授，博士，主要研究方向为无线传感器网络、数据挖掘，maokeji@ zjut.edu.cn。

Segmented Scheduling Algorithm of Barrier Coverage in Wireless Sensor Networks Based OnIntrusion Model*

DAI Guanglin，FANG kai，DAI Guoyong，XU Hui，MAO Keji*
（College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China）

Barrier coverage of Wireless Sensors Networks has played a vital role in intrusion detection.How to schedule the barriers and extend the network lifetime at last has become one of the key issues in this area.Most re⁃searches choose to focus on the point that how to design a reasonable scheduling algorithm in Wireless Sensor Sys⁃tem，which can extend the network lifetime by activating sensor nodes in a time-sharing system to some extent. However，only relying on the timed scheduling for sensor nodes can hardly extend the network lifetime sharply. Therefore，by combining time sharing with segmentation，we designed a scheduling algorithm of barrier in wireless sensor networks in this article.Based on the analysis to the behavior feature of intruders，the algorithm builds the re⁃lated trajectory model of intruders，predicts the area of barrier that intruders might traverse，and then activates barri⁃ers piecewise，which can not only reduce energy loss of sensor nodes greatly but ensure a higher detection rate of in⁃truders at the same time.The emulation experiment results finally proved our assumption that the algorithm combin⁃ing time sharing with segmentation can extend the network lifetime by a large margin，especially compared to the tra⁃ditional timed scheduling algorithm.

wsn；invasion target modeling；scheduling algorithm；energy saving

TP393

A

1004-1699（2016）05-0745-06

项目来源：国家自然科学基金项目（61379023）；浙江省自然科学基金项目（LQ12F02015）；浙江省公益性技术应用研究计划项目（2015C31066）；浙江省计算机科学与技术重中之重学科基金项目（ZC323014074）

2016-01-18修改日期：2016-02-22