WSN巡逻式强栅栏调度算法研究*

毛科技,施伟元,杨志凯,周贤年,戴光麟,夏 明

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

WSN巡逻式强栅栏调度算法研究*

毛科技,施伟元,杨志凯,周贤年,戴光麟,夏 明*

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

无线传感器网络栅栏覆盖研究已取得丰厚成果。提出一种巡逻式栅栏调度算法,该算法将栅栏均匀分为若干子栅栏,依次轮流激活子栅栏,激活的子栅栏工作一段时间后进入休眠状态,然后下一条子栅栏由休眠进入激活状态。因此子栅栏的轮流激活形成了栅栏的巡逻状态,当入侵者穿越栅栏时有很大概率会被巡逻子栅栏检测到。在确保栅栏检测率的情况下使得栅栏的生存时间得到大幅度延长。文中计算了在理论情况下的栅栏检测率,最后通过实验验证了该算法的准确性和可靠性。

WSN;巡逻栅栏;生存时间;检测率

无线传感器网络(WSN)被广泛应用于各个领域[1-2],其中无线传感器网络栅栏覆盖主要应用于入侵者检测,将WSN栅栏部署在需要检测区域,当入侵者试图穿越栅栏时就会被检测到。如在国防应用中,将栅栏部署在边境线可以探测非法越境者。在环保方面,将栅栏部署在污染源周围可检测污染物的扩散情况。在林业保护方面,将栅栏部署在森林火灾现场可检测火灾蔓延情况等[3-4]。然而目前的电池技术使得传感器节点的能量被很大程度的限制了。如何延长传感器网络的生存时间是关键问题。

为了延长WSN栅栏的生存时间,栅栏的加强算法、修复算法和调度算法成为重点研究问题。在栅栏加强和修复方面,如Anwar Saipulla[5]等人提出一种2阶段算法修补栅栏间隙,使死亡的栅栏重新工作。第1阶段,FIND-GAPS算法查找栅栏间隙,第2阶段MEND-GAPS算法修复栅栏。Xu B[6]等人研究了入侵者的历史数据,分析栅栏中某些传感器节点有较大的概率检测到入侵者,然后将移动节点移动到这些易受攻击的位置加强栅栏,从而防止因为某些节点能量消耗过多而导致栅栏提早死亡。Park T[7]等人提出了一种寻找栅栏瓶颈区域,并在瓶颈区域内增加传感器节点的算法,从而延长了传感器网络的生存时间。在栅栏调度方面的研究如Kumar[8]等人提出了Optimal Sleep-Wakeup调度算法,该算法通过分析栅栏的生存时间,组合成若干组k-栅栏,使得栅栏的能量被充分利用,从而达到k-栅栏生存时间最大化。Mostafaei H[9]等人提出了基于自动学习机的LABC算法,并将该算法与文献[8]中提出的算法进行对比,证明该算法与文献[8]中的算法趋于接近。Kim K S[10]等人提出了Duty-Cycle Scheme调度算法,该算法通过轮流调度多条栅栏,使得在保证一定检测率的情况下延长了网络的生存时间。Luo H[11]等人提出了CIBC调度算法,大大延长了网络的生存时间。Kim D[12]等人提出了在静态节点和移动节点混合下的栅栏生存时间最大化算法。文献[13-18]等都研究了在不同情况下的延长栅栏生存时间的方法。

并非所有的WSN栅栏应用中都需要100%的检测率,因此本文提出了一种巡逻式的栅栏调度算法PSA(Patrol Scheduling Algorithm),该算法将栅栏均匀分割为若干子栅栏,子栅栏循环激活,形成一种巡逻状态,入侵者试图穿越栅栏时有很大概率会被巡逻栅栏检测到。该算法在确保一定检测率的情况下实现栅栏生存时间的大幅度提高。

1 巡逻式栅栏调度模型

本章节1.1小节介绍了栅栏调度模型的相关假设,1.2小节具体介绍栅栏调度算法。本文假设栅栏已经由文献[19]等栅栏构建算法构建完成。

1.1 相关假设

假设1 栅栏中传感器节点的能量,感知半径都相同,且节点能量只有在激活状态时才会消耗,处于激活状态的节点能量消耗相同。

假设2 节点的感知模型是布尔模型,当入侵者进入节点感知范围内就可被节点检测到。节点检测到入侵者后可直接与Sink节点通讯,无需通过其他传感器节点进行转发。

假设3 栅栏的休眠和唤醒无需外部信号参与,栅栏形成后已经在节点内部设置相关key,利用key节点可主动进行休眠和唤醒,所以节点的状态切换不消耗能量。

假设4 入侵者在穿越栅栏的过程中视为一个点,不考虑入侵者的实际体积,且入侵轨迹为任意角度的直线。

1.2 栅栏调度算法

巡逻式栅栏调度算法通过将一段整体的栅栏均匀分割为若干子栅栏,在生存周期内的任意时刻都有一条子栅栏处于激活状态,且子栅栏的循环切换形成栅栏的巡逻状态。如图1所示。

图1 栅栏分割图

栅栏均匀分为α段,初始时刻栅栏处于休眠状态,随机激活一条子栅栏Subi,如图1中i=2。子栅栏Subi激活后运行t时间进入休眠状态,t如式(1)所示,同时子栅栏Subi+1由休眠转为激活状态。当Subα由激活转为休眠状态时,Sub1由休眠转为激活状态。依次循环切换子栅栏状态直到节点能量耗尽。所有子栅栏都激活一次则完成一次巡逻。

(1)

式中:T为节点处于激活状态总共能运行的时间,β表示巡逻次数,当完成β次巡逻后节点能量刚好耗尽。

2 1-barrier分析

本小节分析1-barrier巡逻式调度算法的检测率和栅栏生存时间。由于该检测率与入侵者穿越栅栏的时间有关,因此2.1小节计算穿越时间。2.2小节结合2.1小节的穿越时间计算栅栏总体的检测率。2.3小节计算在确保一定检测率的情况下栅栏延长的生存时间。

图2 穿越路径图

2.1 入侵穿越时间

假设入侵者穿越感知区域的速度为v,且可能以任意角度θ和任意位置x穿越某个节点的感知区域,如图2所示。

图2中,le(θ,x)表示节点感知范围内穿越路径的长度,如式(2)所示:

(2)

式中:R为节点感知半径,0≤θ≤π,-R≤x≤R。

由于θ和x是相互独立的随机变量,且x∈[-R,R]的任意值等概率,θ∈[0,π]的任意值等概率,因此x的概率密度函数f(x)如式(3)所示,θ的概率密度函数g(θ)如式(4)所示。

(3)

(4)

计算le(θ,x)的平均值leavg,如式(5)所示,利用泰勒级数可求得leavg的近似值如式(6)所示。

(5)

(6)

式中:R表示节点感知半径。

利用leavg可计算入侵者的平均穿越时间ct,如式(7)所示。

(7)

图3 栅栏检测图

2.2 平均检测率

入侵者被栅栏检测到可分为2种情况:(1)入侵者被某条正处于激活状态的子栅栏检测到。(2)入侵者在休眠的栅栏处试图穿越,但在入侵者离开感知范围前休眠的子栅栏激活了。第2种情况如图3所示。图3(a)表示入侵者尚未被检测到,图3(b)表示入侵者被检测到。

第1种情况的栅栏检测率p1如式(8)所示。

(8)

式中:α表示子栅栏的数量。

第2种情况的栅栏检测率p2如式(9)所示。

通过将最危险剖面Ⅱ-Ⅱ导入MIDAS/GTS中，并根据表1数据对各种材料属性进行定义.模型为二维数值分析模型，尺寸大小为170 m×80 m，共划分为8 864个单元，15 623个节点.分别设置桩界面接触与锚索界面接触来模拟抗滑桩与土体、预应力锚索与土体的相互作用.同时将教学楼与幼儿园等建筑荷载等效为均布荷载作用在坡体上.最危险Ⅱ-Ⅱ剖面有限元网格模型如图3所示.

(9)

综上所述,整条栅栏的平均检测率P为p1、p2之和,如式(10)所示。

(10)

从式(10)可以看出当α值越小时,表示栅栏被分割为子栅栏的数量越少,则每条子栅栏的长度越长,对应检测率越大。β越大时,T/β越小,表示子栅栏状态切换的越快,巡逻速度越快,因此对应的检测率越大。

2.3 延长的生存时间

当所有子栅栏能量都消耗完后,认为该栅栏死亡。子栅栏每次激活状态持续的时间为T/β,则完成一次巡逻需要时间为(αT)/β,因此栅栏的生存时间为αT。如果不将栅栏分割为子栅栏,而是全部激活栅栏中所有节点,则栅栏的生存时间为T。所以巡逻式栅栏的生存时间比整条栅栏都激活延长了(α-1)T。

2.4 栅栏复杂度

栅栏中的传感器节点与远程服务器可相互直接通讯,栅栏的长度为L,将栅栏分为α条子栅栏,每条子栅栏的长度为L/α,假设以栅栏的最左端传感器节点为原点,建立一维坐标系,如图1所示,栅栏中每个传感器节点向服务器报告自身的坐标信息,服务器根据传感器节点的横坐标、栅栏的长度和分割子栅栏的数量,给传感器节点分配其所属的子栅栏编号(编号为S1、S2、S3、…、Sα)。子栅栏的循环激活调度由服务器控制,服务器可向需要激活的子栅栏中的传感器节点发送激活或休眠命令、从而控制子栅栏的激活与休眠。如当服务器需要激活子栅栏Sub1时,可向所属子栅栏编号为S1的传感器节点发送激活命令,此时子栅栏Sub1中的传感器节点都激活。综上所述,在服务器端算法的复杂度非常低,仅为O(α)。

3 k-barrier分析

假设在栅栏部署区域内存在k条栅栏,k条栅栏同时进行独立的巡逻式栅栏调度。则入侵者穿越k条栅栏的检测率Pk如式(11)所示。

Pk=1-(1-P)k

(11)

式中:P表示一条栅栏在巡逻式调度算法下的检测率,可由2.2小节计算得到。

在保证k条栅栏检测到入侵者的概率不小于Pth时,Pk≥Pth,则每条栅栏的检测率P如式(12)所示:

(12)

巡逻式调度算法同时调度k条栅栏,则k条栅栏的生存时间为αT。而按照传统的栅栏调度方法,如首先调度栅栏1,栅栏1所有的传感器节点都处于激活状态,当栅栏1能量耗尽后再调度栅栏2,直到所有栅栏能量都耗尽。这种方法栅栏总共能生存的时间为kT。因此巡逻式调度算法比传统的方法能延长k条栅栏的生存时间为(α-k)T。

4 仿真实验

实验中栅栏长度L=1 000m,总共有k=4条栅栏。传感器节点的最大生存时间t=24×60×60×7s(一周)。实验中的检测率为4条栅栏总共的检测率,实验结果为200次实验的平均结果。

图4 穿越路径长度图

4.1 入侵轨迹平均长度

本次实验验证入侵者穿越以某个节点为圆心的感知区域的平均穿越路径长度leavg。实验中入侵者以任意角度θ∈(0,π)穿越一条栅栏,实验结果如图4所示。横坐标表示传感器节点感知半径,纵坐标表示平均穿越长度leavg。

实验结果表明随着感知半径R的增大,平均穿越路径长度leavg呈线性增长。且本文2.1小节计算的穿越路径平均长度与实验结果符合。

4.2α、β对检测率的影响

本次实验n=4,节点感知半径R=20m,入侵者速度为1m/s。α表示将栅栏分割为子栅栏的数量,α越小表示子栅栏数量越少,每条子栅栏对应的长度越长。T/β表示子栅栏每次处于激活状态的时间。α、β的取值在定义域内,定义域可见2.2小节。本次实验结果为4条栅栏同时采用巡逻式调度算法对入侵者的检测率,结果如图5所示,横坐标为α,纵坐标为检测率Pk。

图5 检测率图

实验结果表明β越大,对应的检测率越高,因为β越大,T/β越小,每条子栅栏处于激活状态的时间越短,对应的巡逻速度越快,因此检测到入侵者的概率越大。检测率随着α增大而减小,因为α越大,子栅栏的长度越小,因此栅栏的检测率越小。同时实验结果也表明了本文理论推导与实验结果相符合。

图6 穿越速度影响图

4.3 穿越速度对检测率影响

入侵者的穿越速度对本文算法有重要影响,理论上穿越速度越快,则栅栏检测到入侵者的概率越低。本次实验中α=4,节点感知半径R=20m,入侵者穿越速度为1m/s～7m/s,以1m/s递增,实验结果如图6所示,横坐标表示穿越速度,纵坐标表示检测率。

实验结果表明随着穿越速度增加,检测率减小。而且检测率随着β增大而增大,因为β越大,在一次栅栏巡逻中子栅栏处于激活的时间越短,则子栅栏的巡逻速度越快,所以检测率越大。

4.4 栅栏生存时间

实验验证栅栏检测率在90%以上时,巡逻式栅栏调度算法(PSA)和传统调度方法在栅栏生存时间上的差异。实验中β=33 833,k=4,节点感知半径R=20m,入侵者速度为1m/s。结合4.2小节的实验,检测率大于90%时α的取值分别为4、5、6、7、8、9、10。实验结果如图7所示,横坐标为α,纵坐标为栅栏生存时间。

图7 栅栏生存时间图

实验中传统的方法如第4小节介绍。实验结果表明在保证检测率大于90%的情况下,随着α增大,栅栏的生存时间也越长。且本文的栅栏调度算法(PSA)的生存时间远远超过传统的栅栏调度算法。

5 总结

无线传感器网络栅栏调度算法对延长栅栏生存时间至关重要。本文提出了巡逻式栅栏调度算法(PSA),该算法在保证一定检测率的条件下轮流激活子栅栏进行巡逻。与以往算法不同之处在于本文算法考虑了一条栅栏内部的子栅栏调度,没有全部激活栅栏,从而达到延长栅栏生存时间的目的。但是本文算法还是有不足之处,比如当入侵者速度非常快时,本文调度算法的检测率将有所下降。后续工作将进一步研究传感器节点在概率模型下的巡逻式栅栏调度算法的性能。

[1]ChenM,GonzalezS,VasilakosA.BodyAreaNetworks:ASurvey[J].MobileNetworksandApplications,2011,16(2):171-193.

[2]Liu L,Xia F,Wang Z,et al. Deployment Issues in Wireless Sensor Networks[J]. 2005,3794:239-248.

[3]Chen A,Kumar S,Lai T H. Designing Localized Algorithms for Barrier Coverage[C]//International Conference on Mobile Computing and Networking,MOBICOM 2007,Montréal,Québec,Canada,September. 2007:63-74.

[4]班冬松,温俊,蒋杰,等. 移动无线传感器网络k-栅栏覆盖构建算法[J]. 软件学报,2011,22(9):2089-2103.

[5]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.

[6]Xu B,Zhu Y,Kim D,et al. Strengthening Barrier-Coverage of Static Sensor Network With Mobile Sensor Nodes[J]. Wireless Networks,2016,22(1):1-10.

[7]Park T,Shi H. Extending the Lifetime of Barrier Coverage by Adding Sensors to a Bottleneck Region[C]//2015 12th Annual IEEE Consumer Communications and Networking Conference(CCNC). IEEE,2015:537-542.

[8]Kumar S,Lai T H,Posner M E,et al. Optimal Sleep-Wakeup Algorithms for Barriers of Wireless Sensors[C]//International Conference on Broadband Communications,Networks and Systems,2007. Broadnets. DBLP,2007:327-336.

[9]Mostafaei H,Meybodi M R. An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2014,77(3):2099-2115.

[10]Kim K S,Jin G W. Maximizing the Lifetime of a Sensor Network with Barrier Coverage[M]//Green and Smart Technology with Sensor Applications. Springer Berlin Heidelberg,2012:347-354.

[11]Luo H,Du H,Kim D,et al. ImperfectionBetter Than Perfection:Beyond Optimal Lifetime Barrier Coverage in Wireless Sensor Networks[C]//International Conference on Mobile Ad-Hoc and Sensor Networks. IEEE Computer Society,2014:24-29.

[12]Kim D,Wang W,Son J,et al. Maximum Lifetime Combined Barrier-Coverage of Weak Static Sensors and Strong Mobile Sensors[J]. IEEE Transactions on Mobile Computing,2016.

[13]Kim H,Kim D,Li D,et al. Maximum Lifetime Dependable Barrier-Coverage in Wireless Sensor Networks[J]. Ad Hoc Networks,2016,36(P1):296-307.

[14]Cobb J A. Improving the Lifetime of Non-Penetrable Barrier Coverage in Sensor Networks[C]//IEEE,International Conference on Distributed Computing Systems Workshops. IEEE,2015:1-10.

[15]DeWitt J,Patt S,Shi H. Maximizing Continuous Barrier Coverage in Energy Harvesting Sensor Networks[C]//2014 IEEE International Conference on Communications(ICC). IEEE,2014:172-177.

[16]Yang H,Li D,Zhu Q,et al. Minimum Energy Costk-Barrier Coverage in Wireless Sensor Networks[C]//International Conference on Wireless Algorithms,Systems,and Applications. Springer-Verlag,2010:80-89.

[17]戴光麟,方凯,戴国勇,等. 入侵轨迹建模与WSN栅栏覆盖分段调度算法研究[J]. 传感技术学报,2016,29(5):745-750.

[18]毛科技,方凯,戴国勇,等. 基于改进蚁群算法的无线传感器网络栅栏覆盖优化研究[J]. 传感技术学报,2015(7):1058-1065.

[19]He S,Gong X,Zhang J,et al. Barrier Coverage in Wireless Sensor Networks:From Lined-Based to Curve-Based Deployment[C]//INFOCOM,2013 Proceedings IEEE. IEEE,2013:470-474.

APatrol Strong Barrier Scheduling Algorithm in WSN*

MAOKeji,SHIWeiyuan,YANGZhikai,ZHOUXiannian,DAIGuanglin,XIAMing*

(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

The research of barrier coverage of Wireless Sensors Networks has achieved rich results. We proposed a patrol barrier scheduling algorithm,in this algorithm the barrierwas divided into several sub-barriers,and took turns to be activated;the activated sub-barrier would enter a dormant state after working a period,and then the next sub-barrier by dormancy into the activated state. So the sub-barrier activation in turn form the fence patrol state,when the intruder through the fence would be a great probability patrol fence is detected. Under the condition of ensure the detection rate of barrier made barrier greatly prolong survival time. In this paper,we calculated the theory in the case of barrier detection rate,finally the veracity and reliability of the algorithm is verified by experiment.

WSN;patrol barrier;survival time;detection rate

毛科技(1979-)，男，汉族，浙江工业大学计算机科学与技术学院副教授，博士，主要研究方向为无线传感器网络、大数据分析，maokeji@zjut．edu．cn；施伟元(1994-)，男，汉族，浙江工业大学计算机科学与技术学院硕士研究生，主要研究方向为无线传感器网络、大数据分析，ftamsir@sina．com； 夏 明(1981-)，男，汉族，浙江工业大学计算机科学与技术学院副教授，博士，主要研究方向为物联网、无线传感器网络，xiaming@zjut．edu．cn。

项目来源:国家自然科学基金项目(61401397,61379023);浙江省公益性技术应用研究计划项目(2015C31066)

2017-04-24 修改日期:2017-06-06

TP393

A

1004-1699(2017)08-1240-06

C:7230

10.3969/j.issn.1004-1699.2017.08.019