一种概率栅栏覆盖模型及其构建算法

范兴刚 徐俊超 车志聪 叶文豪

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

一种概率栅栏覆盖模型及其构建算法

范兴刚 徐俊超 车志聪 叶文豪

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

K-栅栏覆盖是有向传感器网络的研究热点之一.概率感知模型要比0-1模型更贴近实际.而基于概率感知模型的栅栏覆盖还鲜有研究.根据感知概率阈值和感知距离要求，确定节点的虚拟半径.提出一种二元概率栅栏覆盖模型.在这个模型中，相邻2个节点的虚拟感知圆两两相切.在此基础上提出了最少节点的概率栅栏构建算法(construction of probabilistic barrier of minimum node, CPBMN).首先根据二元概率栅栏模型确定节点的目标位置，再通过匈牙利算法选用移动距离之和最少的移动节点移动到目标位置形成栅栏覆盖，缺少移动节点的子区域，选择附近区域的剩余移动节点修补形成1-栅栏覆盖.水平相邻的2个子区域之间构建竖直栅栏，这些子区域的概率1-栅栏合起来构成整个区域的概率K-栅栏覆盖.仿真结果证明：该方法能够有效形成概率栅栏，最多比其他栅栏构建算法节省70%能耗.

无线传感器网络；概率感知模型；栅栏覆盖；虚拟半径；感知距离

无线传感器网络在诸多领域有着广泛的应用，如可将无线传感器节点部署在污染源周围检测致命化学物的扩散、将无线传感器节点布撒在森林边缘以监测火灾发生和火情蔓延情况或放置在重要管道沿线以监视针对管道的破坏活动以及在敌营周边布设无线传感器节点来监视敌方的兵力部署和武器配备情况等.在上述列举的应用中，传感器节点被部署于宽度小于感知半径的狭长带状区域内，对监控区域的移动目标进行检测，这种技术被称为栅栏覆盖，可以对入侵者进行监控、提高网络安全，是覆盖控制的主要研究内容之一[1].

栅栏覆盖目前已有一些研究工作.Kumar等人[2]定义了强栅栏、弱栅栏;曹莹莹等人[3]将影响栅栏覆盖生命期的因素描述为一个多目标优化问题;杨涛等人[4]研究了栅栏构筑算法DPA构筑多条栅栏，实现多栅栏覆盖;罗卿等人[5]采用概率性感知模型，提出一种栅栏覆盖控制算法，调度传感器使冗余节点睡眠，达到减少能耗和延长网络寿命的目的;Li等人[6]研究了无线传感器网络(WSN)1维K-coverage问题，分析K-coverage比例、全K-coverage概率和部分K-coverage概率;秦宁宁等人[7]提出了一种兼顾安全和时效2种性能的启发式轨迹算法，对划分轨迹的准确性进行了研究;班冬松等人[8]研究了全移动传感器网络K-栅栏覆盖问题，提出了一种能量高效的栅栏覆盖构建算法CBIGB;Tian等人[9]研究了2维的栅栏覆盖;Wang等人[10]研究了有向网络的栅栏覆盖.

以上研究都是在0-1感知模型下的栅栏研究.有些学者利用概率感知模型研究覆盖性能.孟凡治等人[11]采用联合感知模型研究了节点通信范围多级可调的无线传感器网络的覆盖质量和连通性;卢云宏等人[12]对概率感知模型下的栅栏覆盖进行研究，利用相邻节点的数据融合技术，提出了一种可以监测移动目标小于临界速度的优化部署策略;He等人[13]分析了同步和异步睡眠模式下传感器网络的覆盖率和连通率;Milan等人[14]研究了移动节点在覆盖兴趣点的过程中，如何保持和基站之间的连通性;Zorbas等人[15]在概率感知模型下，通过构建网络的主连通集(CDS)，选择目标的覆盖集的方法增加网络的生存期;Chen等人[16]研究了沿着任意路径的入侵者的概率感知延迟.目前为止，还没有利用节点的移动能力构建概率栅栏的研究.

如何利用节点的概率模型构建概率栅栏仍是一个难点，有如下问题需要解决：在概率感知模型下，当传感器节点距离事件中心的距离越近，感知概率越大，距离越远，传感器对这个事件感知概率越小.对目标的感知概率是多个节点联合感知的结果，如何构建概率栅栏是要解决的一个问题；另一方面，一个节点对移动目标的感知距离越大，感知效果越好.如何在构建满足感知距离要求的概率栅栏是要解决的定一个问题.传感器节点的能量有限，如何用尽量少得能耗高效构建概率栅栏也是需要解决的问题.本文在解决上述问题的基础上，主要研究如何用尽量少的节点形成概率栅栏覆盖，有3点贡献：

1) 构建了二元概率栅栏覆盖模型；

2) 研究了栅栏感知距离对构建栅栏的影响；

3) 根据概率栅栏覆盖模型，采用的匈牙利算法选择构建栅栏的最优目标位置，建立概率栅栏.

1 相关模型和定义

假设在长度为L、宽度为W区域中，随机部署N个节点.节点具有移动能力，节点能够获知自身地理位置信息.需要在这个区域中形成概率栅栏.研究栅栏问题之前，有3点假设：

1) 采用概率感知模型且是全向感知；

2) 假设入侵者路径是垂直的；

3) 传感器能够感知位置，具有移动能力.

定义1. 概率覆盖模型.概率覆盖模型中，距离传感器节点d处的事件感知概率(即感知概率)为

PLd=Ptx-Prxd=
PL0+10αlg(dd0)+Xσ,

式(1)为指数节点损耗模型，式(2)为中间参数，Ptx是发送节点的功率；Prxd在距离d接收功率；PL0在参考距离d0处的路径损耗；α传输损耗指数；Xσ均值为0的高斯随机数；γ能够接收到的最小功率，Pd表示距离传感器节点d处的事件感知概率.

在概率覆盖模型下，一个事件的感知概率是附近多个传感器联合感知的结果.在计算感知概率时，可以融合节点感知信息，得到事件的联合感知概率，2个节点的联合感知概率为

rs=rmin+dis.

Fig. 1 Probabilistic barrier model图1 概率栅栏模型

2 理论分析

为了描述方便，常用参数如表1所示:

Table 1 The Parameters表1 相关参数

2.1 概率栅栏

在0-1感知模型下，不管发生的事件距离远近，只要在一定的范围内，一定以概率1被感知.与0-1模型不同，概率模型下距离节点越远，感知概率越小.而且事件不是被一个节点单独的覆盖，而是被多个节点联合覆盖，事件的覆盖率是多个节点联合感知的结果.假设距离节点为rmin的区域得到探测概率Pmin.在0-1感知模型下，大于rmin的区域得到的感知概率肯定小于Pmin，即使有邻居节点的作用，感知概率也不会增加.而在概率感知模型下，由于感知区域内邻居节点的影响，大于rmin的区域得到的探测概率可能大于Pmin.

定理1. 如果采用定义1所示的概率感知模型，在2个节点的连线上，发生在2个节点的中间事件的联合感知概率最小.

证明. 对于2个传感器，一个传感器对某目标点的感知概率为P1，另一个节点对同一目标点的感知概率为P2，则目标点的联合概率:

P=1-(1-P1)(1-P2)⟹P=P1+P2-P1×P2.

P″(d)>0，因为P′(z)在(0,d)上单调递增，又因为d=l2时，有P′(d)=0，所以P在d2时最小.

证毕.

根据这个定理，只要2个节点中间的联合感知概率满足概率阈值的要求，2个节点的整条连线就满足概率阈值的要求，这条连线就是概率栅栏.

Fig. 2 The united detection probability图2 联合感知概率

我们设计了一个仿真，进一步说明这个问题.概率参数采用和文献[15]一样的值，分别为γ=-27.85，Ptx=32，σ=4，α=2，PL0=-50，d0=1 000，Xσ=147.476，rs=6，Amin=114 m2.假设Pmin=0.95，则rmin= 6.2 m，P1=0.776，rs=9.26 m，dis=rs-rmin=3.1 m，2个节点连线上的概率变化如图2(a)所示，l表示2个节点之间的距离.图2(a)仿真结果如下:当l=2rs=18.5 m时，在d=9.26 m取得最小值0.95;在l=16.7 m，在d=8.35 m取得最小值0.974;在l=15.4 m，在d=7.7 m取得最小值0.985;在l=13.9 m，在d=6.95 m取得最小值0.994.仿真结果表明，在不同的距离下，都是在l2处，联合感知概率最小;2个节点之间的距离越小，2个节点之间的联合感知概率越大.

2.2 感知距离的影响

这是假设入侵者路径是垂直情况下的分析，如果入侵者路径是任意的，感知距离肯定大于垂直路径的情况.而且在垂直入侵路径的感知距离满足概率阈值的情况下，任意入侵路径的感知距离也满足最小概率阈值的要求.

根据前面的分析，我们提出虚拟感知半径和二元概率栅栏覆盖模型.

x1≤x2≤…≤xm-1≤xm;

定理2. 满足式(6)～(8)的节点集合是一条满足感知距离要求的水平概率栅栏，且是用最少节点构成的概率栅栏.

Fig. 3 Probabilistic barrier of minimum node图3 最少节点的概率栅栏

由定义3可知，在感知距离要求下，每个节点的感知半径为r，式(8)表明，任意2个相邻节点的距离为2r，也就是组成栅栏的每个节点都达到了最大感知能力.没有一个节点是冗余的，少一个节点就不能形成栅栏.所以这也是用最少节点组成的概率栅栏.

证毕.

在图3(a)中，圆表示以rs为半径的感知圆.有4个节点集合，集合1,3是概率栅栏.栅栏1由13个节点构成，栅栏3用了10个节点，节点之间的距离正好是2rs，构成概率栅栏PBMN.如果集合2的节点进行有限的移动也可以形成PBMN.我们研究的问题就是：在区域A中，移动节点密度不同的情况下，如何高效构建概率栅栏PBMN.

3 概率K-栅栏覆盖构建算法

Wang等人[10]提出要构建K-栅栏覆盖，以节点为顶点、节点的最近距离为权值，构建有向图，选择2个端点，运用Dijkstra算法[17]求2点间的最短路径.这个最短路径上的节点就是栅栏基准位置.大于节点的节点虚拟感知半径rs的2个节点之间需要移动节点修补，从而构成栅栏.我们称这种方法为RVSB算法，这种方法可以形成概率栅栏，但会消耗大量的节点.

本文使用的参数定义如表1所示.参数详细解释如图3所示，lg=6，wg=5，子区域Ai2左侧区域的基准栅栏行Ci1=3，针对t=1，竖直栅栏目标列VG1=(vg1,vg2)，p=2，lg+p=8.

CPBMN算法的伪代码如算法1.

算法1. CPBMN算法.

输入:Pmin,N,K,V,L,w;

输出: 概率栅栏、总能耗、平均能耗.

根据Pmin按照式(1)～(8)计算rmin,rs,虚拟感知半径r;

把整个区域按边长为2r的网格进行网格化；

把整个区域分成K×V子区域，

For 每一个子区域

获得子区域的节点集合Ni j;

For 每一行t

p=0;

If 左边子区域存在栅栏

End If

t+p个网格和Ni j个节点按照匈牙利算法

进行最佳匹配;

计算每一行的移动距离之和;

End For

移动距离之和最小的行为栅栏行;

相应的节点移动到相应的位置形成栅栏;

End For

If 子区域中移动节点数目小于栅栏需求

调度附近剩余移动节点修补栅栏，形成概率 栅栏;

End If

计算总移动距离和平均移动距离，并输出结果.

3.1 CPBMN算法的基本步骤

CPBMN算法具体步骤为：

Step1. 初始化.

根据给定的Pmin确定节点的rmin，rs，再根据感知距离w，确定节点的虚拟感知半径r.

Step2. 区域的网格划分.

对区域网格化，每一个网格的边长为2r进行子区域划分，得到K×V个子区域.进一步获得子区域的节点集合Ni j(1≤i≤K;1≤j≤V)、以网格为单位的子区域的长度lg和宽度wg.

Step3. 确定概率栅栏的目标位置.

针对每一个子区域，确定概率栅栏的目标位置.

Step3.1. 确定每一行的目标网格.

Step3.1.1. 对于水平第1个子区域As1，第1个目标网格的坐标为x1=rmin，第2个目标网格为x2=x1+2r.

Step3.1.3. 水平最后1个子区域As1中，最后1个目标网格的坐标大于等于L-rmin.

Step3.2. 计算每一行的移动距离.

对于区域Ai j的第t行的Gt按照式(4)进行矩阵赋值操作.运用匈牙利算法，得出节点最小总移动距离Dt.

Step3.3. 选取子区域概率栅栏的目标位置.

选取总移动距离Dt最小的行作为子区域的基准网格栅栏行Ci j(如图3所示).

Step4. 形成概率栅栏.

选定的移动节点移动到对应的目标位置形成概率栅栏.

Step5. 栅栏修补.

如果子区域中移动节点数目小于基准栅栏需求，调度附近剩余移动节点修补栅栏，形成概率栅栏.

Step6. 输出结果.

计算总移动距离和平均移动距离，并输出结果.

3.2 算法的复杂分析

在子区域Asz中，传感器节点的个数为Ni j.在这个区域中，可能形成1-栅栏的目标位置最大个数为lg+wg-1，只要Ni j≥lg+wg-1，子区域就能形成PBMN.整个区域要形成K-栅栏，目标位置的最大个数为(lg+wg-1)×K×V，也就是说在修补策略下，只要节点总个数N≥(lg+wg-1)×K×V，CPBMN就一定能形成强K-栅栏.

4 实验结果与分析

本文运用Matlab7.0对此算法进行仿真，如果没有特别指明，实验的默认参数如表2所示.为了体现CPBMN算法在传感器节点的使用数量和移动距离上的优势，我们对3种算法CPBMN，CBIGB[9]，RVSB[10]进行性能比较.在保证能形成栅栏的前提下，相对较少的节点分布更能体现出各算法的优劣性，因为0.005的节点密度不能使CBIGB形成6栅栏覆盖，因此此处我们选择0.006作为节点分布的密度.

Table 2 Default Values表2 默认参数

影响栅栏构建的主要参数是最小感知概率、节点数N、栅栏数K、参数V.我们进一步详细分析这些参数对栅栏形成的影响，所有的实验结果都是50次实验的平均值.评价指标是形成K-栅栏的节点数、总移动距离和平均移动距离3个指标.形成K-栅栏节点数越少，说明算法的效率越高，由于移动会消耗能量，总移动距离越少，整个网络的耗能就越少，网络的工作时间就越长.平均移动距离越小，节点的能耗越均匀.

4.1 感知概率阈值的影响

最小感知概率的影响如图4所示.由图4可以看出随着最小感知概率的增加，3种算法总移动距离、平均移动距离、栅栏需求的节点数都在增加，CPBMN算法的性能明显优于其他2种算法，3个指标都是CPBMN算法最低，在低密度下总移动距离CPBMN算法比CBIGB算法、RVSB算法分别低71%，38%；平均移动距离分别低45%，56%；节点数分别相差47%，40%.

Fig. 4 The affection of detection probability threshold 图4 感知概率阈值的影响

4.2 栅栏数的影响

栅栏数K值影响如图5所示.由图5可以看出，随着栅栏数的增加，3种算法的3个指标都增加，形成1-栅栏、4-栅栏，CPBMN算法需要总移动距离分别为60 m，2 200 m，平均距离分别为15 m，20 m；CBIGB算法需要总移动距离分别为1 800 m，4 800 m，平均距离分别为20 m，32m.K的增大导致相应子区域内可选择的传感器节点数量减少，使得平均移动距离和总移动距离变大.

Fig. 5 The effect of barriers图5 栅栏数的影响

CPBMN算法用最少的节点生成K-栅栏，形成1-栅栏、4-栅栏，CPBMN算法分别需要节点个数为30，110，CBIGB算法分别需要节点个数为82，150个.所以同样的节点数，CPBMN算法形成的栅栏数最多.CBIGB算法形成的栅栏数最少，当K增加到4时，CBIGB算法形成4-栅栏覆盖的概率小于1；当K增加到5时，基本无法再形成栅栏覆盖，说明CBIGB算法对区域内的传感器节点数量要求比较高.

4.3V值的影响

V值对CPBMN算法的仿真结果影响如图6所示.在节点密度为0.004时，当V值分别为2，3，4，形成2-栅栏需要的总移动距离分别为2 000 m，2 500 m，2 700 m，平均移动距离分别为17 m，18 m，18 m.V越大子区域越小，子区域内的节点数目就越少，使得节点的选择变少，有可能会增加总移动距离和平均移动距离；另一方面，V越大导致水平方向上的子区域增多，因此一整条栅栏中基准栅栏位置的选择增大，能一定程度降低总移动距离和平均移动距离.但当节点密度较少时，不同的V的取值对于移动距离的影响很小.

Fig. 6 The effect of V values图6 V值的影响

4.4 感知距离的影响

感知距离的影响如图7所示.由图7可知，随着感知距离的增加，3个算法的移动距离、节点数量都在增加，但是，CPBMN效果最好，移动距离最少，需要的节点数量也最少.要提高栅栏的监控质量，就要增加节点数量.CPBMN算法的总移动距离比CBIGB算法、RVSB算法低71%，50%，平均移动距离低44%，60%，节点数分别相差48%,41%.

Fig. 7 The effect of detecting distance图7 感知距离的影响

5 结束语

本文主要研究概率K-栅栏覆盖构建方法CPBMN.先根据概率模型得到节点的虚拟感知半径，根据虚拟半径确定形成概率栅栏的目标位置.移动节点移动到此位置形成概率栅栏.水平相邻的2个子区域通过竖直栅栏连接起来.仿真结果证明，CPBMN可以用最少的节点，高效节能地构建概率栅栏，栅栏形成以后，如何节能高效地工作是下一步要研究的内容.

[1]Ren Yan, Zhang Sidong, Zhang Hongke. Theories and algorithms of coverage control for wireless sensor networks[J]. Journal of Software, 2006, 17(3): 422-433 (in Chinese)(任彦, 张思东, 张宏科. 无线传感器网络中覆盖控制理论与算法[J]. 软件学报, 2006, 17(3): 422-433)

[2]Kumar S, Lai T H, Arora A. Barrier coverage with wireless sensors[J]. Wireless Networks, 2007, 13(6): 817-834

[3]Cao Yingying, Huang Liusheng, Zhu Licai, et al. Optimal collaborated heterogeneous sensor barrier coverage model[J]. Journal of Chinese Computer Systems, 2012, 33(11): 2457-2462 (in Chinese)(曹莹莹, 黄刘生, 朱立才, 等. 一种协作的异构传感器最优栅栏覆盖模型[J]. 小型微型计算机系统, 2012, 33(11): 2457-2462)

[4]Yang Tao, Mu Dejun. Study on multi-barriers construction in wireless sensor networks[J]. Journal of Projectiles, Rockets, Missiles and Guidance, 2012, 32(2): 173-176 (in Chinese)(杨涛, 慕德俊. 无线传感器网络多栅栏覆盖构建算法研究[J]. 弹箭与制导学报, 2012, 32(2): 173-176)

[5]Luo Qing, Lin Yaping, Wang Lei, et al. Barrier coverage control based on data fusion for wireless sensor network[J]. Journal of Electronics & Information Technology, 2012, 34(4): 825-831 (in Chinese)(罗卿, 林亚平, 王雷, 等.传感器网络中基于数据融合的栅栏覆盖控制研究[J]. 电子与信息学报, 2012, 34(4): 825-831)

[6]Li Lei, Zhang Baoxian, Zheng Jun. A study on one-dimensionalK-coverage problem in wireless sensor networks[J]. Wireless Communications and Mobile Computing, 2013, 13(1): 1-11

[7]Qin Ningning, Zhang Lin, Shan Xiuming, et al. A heuristic track strategy for wireless sensor networks[J]. Journal of Electronics & Information Technology, 2008, 30(3): 707-711 (in Chinese)(秦宁宁, 张林, 山秀明, 等. 无线传感器网络启发式移动轨迹策略的研究[J]. 电子与信息学报, 2008, 30(3): 707-711)

[8]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)

[9]Tian Jie, Zhang Wensheng, Wang Guiling. 2DK-barrier duty-cycle scheduling for intruder detection in wireless sensor networks[J]. Computer Communications, 2014, 43(3): 31-42

[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]Meng Fanzhi, Wang Huanzhao, He Hui. Connected coverage protocol using cooperative sensing model for wireless sensor networks[J]. Acta Electronica Sinica, 2011, 39(4): 772-779 (in Chinese)

(孟凡治, 王换招, 何晖. 基于联合感知模型的无线传感器网络连通性覆盖协议[J]. 电子学报, 2011, 39(4): 772-779)

[12]Lu Yunhong, Guo Zhongwen. Optimized deployment strategy of barrier coverage based on probability sensing model[J]. Journal of Software, 2014, 25(Suppl 1): 85-92 (in Chinese)(卢云宏, 郭忠文. 一种概率感知模型的栅栏覆盖优化部署策略[J]. 软件学报,2014, 25(增刊1): 85-92)

[13]He Shibo, Chen Jiming, Sun Youxian. Coverage and connectivity in duty-cycled wireless sensor networks for event monitoring[J]. IEEE Trans on Parallel and Distributed Systems, 2012, 23(3): 475-482

[14]Milan E D, Tahiry R, David S R. Covering points of interest with mobile sensors[J]. IEEE Trans on Parallel and Distributed Systems, 2013, 24(1): 32-43

[15]Zorbas D, Tahiry R. Prolonging network lifetime under probabilistic target coverage in wireless mobile sensor networks[J]. Computer Communications, 2013, 36 (9): 1039-1053

[16]Chen Jiming, Li Junkun, Lai T H. Energy-Efficient intrusion detection with a barrier of probabilistic sensors: Global and local[J]. IEEE Trans on Wireless Communications, 2013, 12(9): 4742-4755

[17]Tutte W T. Graph Theory[M]. London: Aambridge Mathematical Press, 2010

A Probabilistic Barrier Coverage Model and Effective Construction Scheme

Fan Xinggang, Xu Junchao, Che Zhicong, and Ye Wenhao

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

Barrier coverage is one of hot spots in the wireless sensor network. The probabilistic sensing model is closer to the actual situation than 0-1 sensing model. However, there is seldom study about probabilistic barrier coverage. This paper mainly studies virtual radius according to the probabilistic sensing model and the demand of detecting distance. And this paper also proposes the binary probabilistic barrier coverage model in which the neighbor virtual sensing circles are tangent. The CPBMN (construction of probabilistic barrier of minimum node) is also proposed based on this probabilistic barrier model. Firstly, the optimal target locations are determined by the binary probabilistic barrier coverage mode. Secondly, the Hungary algorithm selects the corresponding optimal mobile nodes to shift its target location. Thirdly, the vertical barriers between two horizontal adjacent probabilistic barrier segments are created. TheK-probabilistic barriers in the whole area are created by combining these 1-probabilistic barriers in each subarea together. Simulation results show our method can effectively constitute probabilistic barrier coverage. Compared with other methods, it can decrease 70% energy consumption.

wireless sensor network; probabilistic sensing model; barrier coverage; virtual sensing radius; detecting distance

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

Xu Junchao, born in 1995. Undergraduate. His main research interest is wireless sensor network.

Che Zhicong, born in 1995. Undergraduate. His main research interest is wireless sensor network.

Ye Wenhao, born in 1996. Undergraduate. His main research interest is wireless sensor network.

2015-12-23；

2016-04-13

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

TP391; TP393.09