PL 0 +10 α lg( d
d 0 )+ X σ , 范兴刚 徐俊超 车志聪 叶文豪
(浙江工业大学计算机科学与技术学院 杭州 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) 根据概率栅栏覆盖模型，采用的匈牙利算法选择构建栅栏的最优目标位置，建立概率栅栏.
假设在长度为 L 、宽度为 W 区域中，随机部署 N 个节点.节点具有移动能力，节点能够获知自身地理位置信息.需要在这个区域中形成概率栅栏.研究栅栏问题之前，有3点假设：
1) 采用概率感知模型且是全向感知；
2) 假设入侵者路径是垂直的；
3) 传感器能够感知位置，具有移动能力.
定义1. 概率覆盖模型.概率覆盖模型中，距离传感器节点 d 处的事件感知概率(即感知概率)为
PL d = P tx - P rxd =
PL 0 +10 α lg( d d 0 )+ X σ ,
式(1)为指数节点损耗模型，式(2)为中间参数， P tx 是发送节点的功率； P rxd 在距离 d 接收功率； PL 0 在参考距离 d 0 处的路径损耗； α 传输损耗指数； X σ 均值为0的高斯随机数； γ 能够接收到的最小功率， P d 表示距离传感器节点 d 处的事件感知概率.
在概率覆盖模型下，一个事件的感知概率是附近多个传感器联合感知的结果.在计算感知概率时，可以融合节点感知信息，得到事件的联合感知概率，2个节点的联合感知概率为
如果在一个点的目标联合感知概率大于等于感知概率阈值(用 P min 表示)，就认为这个位置的目标被感知.根据式(1)～(3)求得 P min 对应的感知半径 r min .例如图1中，点 C 在节点 A 和节点 B 的联合感知下，感知概率为 P min ，且2个节点对点 C 的感知概率相等，将 P min 代入式(4)，得到一个节点对点 C 的感知概率为 
和这个概率对应的感知半径为 r s ， r s 和 r min 的关系如图1(a)和式(5)所示：
r s = r min + dis .
各个参数采用默认数值，如果 P min =0.95，则 
m .
Fig. 1 Probabilistic barrier model
图1 概率栅栏模型
定义2. 栅栏感知距离.栅栏中的节点对入侵者路径进行感知，路径上满足概率阈值的最小感知距离称为栅栏感知距离.例如图1中经过点 C 的垂直入侵者，只有在点 C 满足感知概率阈值要求.有2条入侵路径，分别是经过点 C 和点 G .经过点 C 的栅栏感知距离为 
经过点 G 栅栏感知距离为 
则这条栅栏的感知距离为 
栅栏感知距离越长，监控效果越好.
为了描述方便，常用参数如表1所示:
Table 1 The Parameters
表1 相关参数
2.1 概率栅栏
在0-1感知模型下，不管发生的事件距离远近，只要在一定的范围内，一定以概率1被感知.与0-1模型不同，概率模型下距离节点越远，感知概率越小.而且事件不是被一个节点单独的覆盖，而是被多个节点联合覆盖，事件的覆盖率是多个节点联合感知的结果.假设距离节点为 r min 的区域得到探测概率 P min .在0-1感知模型下，大于 r min 的区域得到的感知概率肯定小于 P min ，即使有邻居节点的作用，感知概率也不会增加.而在概率感知模型下，由于感知区域内邻居节点的影响，大于 r min 的区域得到的探测概率可能大于 P min .
定理1. 如果采用定义1所示的概率感知模型，在2个节点的连线上，发生在2个节点的中间事件的联合感知概率最小.
证明. 对于2个传感器，一个传感器对某目标点的感知概率为 P 1 ，另一个节点对同一目标点的感知概率为 P 2 ，则目标点的联合概率:
P =1-(1- P 1 )(1- P 2 )⟹ P = P 1 + P 2 - P 1 × P 2 .
令 P ( z )= P d ，若已知2节点之间距离为 l ，则设节点1位于(0,0)处，节点2位于( l ,0)处. P 1 ( z )= 
表示节点1对其正右方 d 处目标点的感知概率 
是常数.节点2的对同一目标点的概率函数为 
表示节点2对其正左方( d — x )处的感知概率. 
则2个节点对目标点的联合概率为
P ″( d )>0，因为 P ′( z )在(0, d )上单调递增，又因为 d = l 2时，有 P ′( d )=0，所以 P 在 d 2时最小.
证毕.
根据这个定理，只要2个节点中间的联合感知概率满足概率阈值的要求，2个节点的整条连线就满足概率阈值的要求，这条连线就是概率栅栏.
Fig. 2 The united detection probability
图2 联合感知概率
我们设计了一个仿真，进一步说明这个问题.概率参数采用和文献[15]一样的值，分别为 γ =-27.85， P tx =32， σ =4， α =2， PL 0 =-50， d 0 =1 000， X σ =147.476， r s =6， A min =114 m 2 .假设 P min =0.95，则 r min = 6.2 m， P 1 =0.776， r s =9.26 m， dis = r s - r min =3.1 m，2个节点连线上的概率变化如图2(a)所示， l 表示2个节点之间的距离.图2(a)仿真结果如下:当 l =2 r s =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.仿真结果表明，在不同的距离下，都是在 l 2处，联合感知概率最小;2个节点之间的距离越小，2个节点之间的联合感知概率越大.
2.2 感知距离的影响
如定义2所示，感知距离是指概率栅栏对入侵者路径的最短感知长度.如图1(b)中，节点 A 和 B 形成概率栅栏，假设入侵者路径是垂直的，线段 
就是栅栏的感知距离.只有整条 都满足感知概率的要求，整个感知距离才能满足概率阈值的要求.根据概率式(4)，点 C 和 D 都满足.由于在线段 上的其他任意点(点 F )距离节点的距离都小于节点到 C 的距离.也就是节点 A 对这个节点 E 的感知概率大于节点 A 对点 C 的感知概率.节点 B 对 F 的感知概率也大于节点 B 对点 C 的感知概率，所以位置 F 的联合感知概率也满足概率阈值.同样的道理，线段 每个点都满足概论阈值要求.也就是在定义2所示的概率栅栏模型下，只要以 r s 为半径的概率感知圆的相交区域的竖直弦大于等于感知距离的要求，整条概率栅栏都满足感知距离的要求.
若2节点之间距离为 l ，则设节点1位于(0,0)处，节点2位于( l ,0)，概率函数 
表示节点1对其右方( d , y )处(如图1(b)所示，0≤ y ≤ w 2)目标点的
感知概率 
表示节点2对同一目标点的感知概率 
用和定理1同样的方法，可以证明在( l 2, y )获得最小的联合感知概率.
在同图2(a)同样的参数下，不同感知距离对2个节点之间的联合感知概率影响如图2(b)所示. w 表示感知距离 
两个节点的坐标分别为(0,0)，( l ,0).横坐标是点( d , w 2)的横坐标，0≤ d ≤ l .纵坐标是这个点的联合感知概率.图2(b)仿真结果如下.当 w =2 m时，在 y =1这条直线上在 d =9.21 m即点(9.21，1)位置取得最小值0.95.当 w =6 m时，在 y =3这条直线上，在 d =8.76 m即点(8.76，3)位置取得最小值0.95；当 w =10 m时，在 y =5这条直线上，在 d =7.79 m即点(7.79，5)位置取得最小值0.95；当 w =12 m时，在 y =6这条直线上在 d =7.05 m即点(7.05，6)位置取得最小值0.95；在 w =6 m，在 d =8.35 m取得最小值0.974.仿真结果表明，在不同的感知距离下，都是在 
处，即2个节点的中垂线上，联合感知概率最小，而且最小概率都是0.95.
这是假设入侵者路径是垂直情况下的分析，如果入侵者路径是任意的，感知距离肯定大于垂直路径的情况.而且在垂直入侵路径的感知距离满足概率阈值的情况下，任意入侵路径的感知距离也满足最小概率阈值的要求.
根据前面的分析，我们提出虚拟感知半径和二元概率栅栏覆盖模型.
定义3. 虚拟感知半径.如果概率阈值为 P min ，感知距离要求为 w ，2个节点的联合感知概率如式(4)所示，如果这个联合感知概率满足概率阈值的要求时，一个节点对应的感知半径为 r s .则 
称为感知距离要求为 w 时的节点虚拟感知半径.这也是在概率阈值 P min 、感知距离 w 下单个节点的最大感知半径.
定义4. 二元概率栅栏覆盖模型. 如果以2个节点的位置为圆心、 r 为半径的2个圆相切，那么这2个节点的连线形成概率栅栏覆盖.没有感知距离要求的概率栅栏如图1(a)所示.左边界到节点 A 的距离为 r min ，节点 A 和节点 B 之间的距离为2 r s .则穿过水平线段 
的入侵者都会被概率感知 
就是水平概率栅栏.有感知距离要求的概率栅栏如图1(b)所示.
定义5. 最少节点的概率栅栏(probabilistic barrier of minimum node， PBMN).假设 w <2 r min ，如果区域中存在一个从左到右传感器节点集合 S ={ s 1 , s 2 ,…, s m }( m ≤ N )，满足式(6)～(8).则这个节点集合形成一条水平概率栅栏 PBMN. 式(6)中， x 1 , x 2 ,…, x m 分别是节点 s 1 , s 2 ,…, s m 的横坐标.式(7)表明，区域的左边界与第1个节点以 r min 为半径的感知圆相切，区域的右边界与最后1个节点以 r min 为半径的感知圆相切.式(8)表明，任意2个水平相邻节点距离为 
满足最小感知距离的要求.当 w =0时，2个节点之间距离为2 r s .
x 1 ≤ x 2 ≤…≤ x m -1 ≤ x m ;
定理2. 满足式(6)～(8)的节点集合是一条满足感知距离要求的水平概率栅栏，且是用最少节点构成的概率栅栏.
证明. 由式(6)可知，这个节点集合有 m 个节点，按照横坐标大小从左到右排列.式(7)表明，第1个节点的坐标为 
它的满足感知概率阈值的感知圆与左边界相交，相交区域的弦为 w .入侵者被第1个节点感知的距离为 w ，由于 w <2 r min ，穿过第1个节点左半圆的入侵者被感知距离大于等于 w .式(8)表明，第1个节点与第2个节点的距离为 这2个节点以 r s 为半径的感知圆相交区域的弦为 w ，根据定理1，在第1个和第2个节点之间的最小感知距离为 w ，也满足感知距离的要求.依次类推，从左边界开始，第1个节点，一直到第 m 个节点都满足感知距离的要求.用与左边界同样的方法也可以证明第 m 个节点和右边界之间的区域也满足感知距离的要求.所以由式(6)～(8)定义的节点集合是一条满足感知距离要求的水平概率栅栏.
Fig. 3 Probabilistic barrier of minimum node
图3 最少节点的概率栅栏
由定义3可知，在感知距离要求下，每个节点的感知半径为 r ，式(8)表明，任意2个相邻节点的距离为2 r ，也就是组成栅栏的每个节点都达到了最大感知能力.没有一个节点是冗余的，少一个节点就不能形成栅栏.所以这也是用最少节点组成的概率栅栏.
证毕.
在图3(a)中，圆表示以 r s 为半径的感知圆.有4个节点集合，集合1,3是概率栅栏.栅栏1由13个节点构成，栅栏3用了10个节点，节点之间的距离正好是2 r s ，构成概率栅栏PBMN.如果集合2的节点进行有限的移动也可以形成PBMN.我们研究的问题就是：在区域 A 中，移动节点密度不同的情况下，如何高效构建概率栅栏PBMN.
Wang等人 [10] 提出要构建 K -栅栏覆盖，以节点为顶点、节点的最近距离为权值，构建有向图，选择2个端点，运用Dijkstra算法 [17] 求2点间的最短路径.这个最短路径上的节点就是栅栏基准位置.大于节点的节点虚拟感知半径 r s 的2个节点之间需要移动节点修补，从而构成栅栏.我们称这种方法为RVSB算法，这种方法可以形成概率栅栏，但会消耗大量的节点.
另一方面，根据感知概率阈值求出节点最大感知半径 
将监控区域进行划分为相同大小的子矩形区域.再对监控区域网格划分，网格的内切圆半径为2 r .如果子区域内，某一行网格上，每一个网格有且仅有一个节点，则节点两两相切.根据定义4，这一行上的节点形成一条PBMN.再利用匈牙利算法 [13] 对目标位置和移动节点进行最佳匹配；对于缺少移动节点的子区域，利用附近区域的移动节点进行修补；水平相邻的子区域之间通过竖直栅栏连接起来，形成概率栅栏覆盖.这就是最少节点的概率栅栏构建算法(construction of probabilistic barrier of minimum node, CPBMN).
本文使用的参数定义如表1所示.参数详细解释如图3所示， l g =6， w g =5，子区域 A i 2 左侧区域的基准栅栏行 C i 1 =3，针对 t =1，竖直栅栏目标列 VG 1 =( vg 1 , vg 2 )， p =2， l g + p =8.
CPBMN算法的伪代码如算法1.
算法1. CPBMN算法.
输入: P min , N , K , V , L , w ;
输出: 概率栅栏、总能耗、平均能耗.
根据 P min 按照式(1)～(8)计算 r min , r s ,虚拟感知半径 r ;
把整个区域按边长为2 r 的网格进行网格化；
把整个区域分成 K × V 子区域，
For 每一个子区域
获得子区域的节点集合 N i j ;
For 每一行 t
p =0;
If 左边子区域存在栅栏
End If
t + p 个网格和 N i j 个节点按照匈牙利算法
进行最佳匹配;
计算每一行的移动距离之和;
End For
移动距离之和最小的行为栅栏行;
相应的节点移动到相应的位置形成栅栏;
End For
If 子区域中移动节点数目小于栅栏需求
调度附近剩余移动节点修补栅栏，形成概率 栅栏;
End If
计算总移动距离和平均移动距离，并输出结果.
3.1 CPBMN算法的基本步骤
CPBMN算法具体步骤为：
Step1. 初始化.
根据给定的 P min 确定节点的 r min ， r s ，再根据感知距离 w ，确定节点的虚拟感知半径 r .
Step2. 区域的网格划分.
对区域网格化，每一个网格的边长为2 r 进行子区域划分，得到 K × V 个子区域.进一步获得子区域的节点集合 N i j (1≤ i ≤ K ;1≤ j ≤ V )、以网格为单位的子区域的长度 l g 和宽度 w g .
Step3. 确定概率栅栏的目标位置.
针对每一个子区域，确定概率栅栏的目标位置.
Step3.1. 确定每一行的目标网格.
Step3.1.1. 对于水平第1个子区域 A s 1 ，第1个目标网格的坐标为 x 1 = r min ，第2个目标网格为 x 2 = x 1 +2 r .
Step3.1.2. 如果在子区域 A i j 左侧子区域 A s ( j -1) 中，栅栏所在的行为 C i ( j -1) ，对于第 t 行网格 
则选取相应的竖直栅栏目标网格 VG t (如图3(b)所示)， t 行的目标网格为 G t =( g 1 , g 2 ,…, g tm -1 , g tm )，其中 t m = l g + p .如果子区域中移动节点数目小于基准栅栏需求，直接选取与左侧子区域一样的基准栅栏行 C i j = C i ( j -1) .
Step3.1.3. 水平最后1个子区域 A s 1 中，最后1个目标网格的坐标大于等于 L - r min .
Step3.2. 计算每一行的移动距离.
对于区域 A i j 的第 t 行的 G t 按照式(4)进行矩阵赋值操作.运用匈牙利算法，得出节点最小总移动距离 D t .
Step3.3. 选取子区域概率栅栏的目标位置.
选取总移动距离 D t 最小的行作为子区域的基准网格栅栏行 C i j (如图3所示).
Step4. 形成概率栅栏.
选定的移动节点移动到对应的目标位置形成概率栅栏.
Step5. 栅栏修补.
如果子区域中移动节点数目小于基准栅栏需求，调度附近剩余移动节点修补栅栏，形成概率栅栏.
Step6. 输出结果.
计算总移动距离和平均移动距离，并输出结果.
3.2 算法的复杂分析
在子区域 A sz 中，传感器节点的个数为 N i j .在这个区域中，可能形成1-栅栏的目标位置最大个数为 l g + w g -1，只要 N i j ≥ l g + w g -1，子区域就能形成PBMN.整个区域要形成 K -栅栏，目标位置的最大个数为( l g + w g -1)× K × V ，也就是说在修补策略下，只要节点总个数 N ≥( l g + w g -1)× K × V ，CPBMN就一定能形成强 K -栅栏.
在子区域 A sz 中，传感器节点的个数为 N sz ，则有 
N .在这个区域中，可能形成1-栅栏的目标位置最大个数为 
，则要计算每一个目标位置与每一个节点的距离，时间复杂度为 O ( N i j ×( l g + w g )× w g ),匈牙利算法的复杂度为 O (( l g + w g ) 2 N i j ),则一个区域的复杂度为 O (( l g + w g ) 2 N i j )，共有 K × V 个子区域，累加可以得到算法总的复杂度为 
由于每个节点都要与中心节点通信，这里的通信开销为 O ( N )，中心节点把结果通知给移动节点，通信开销最多为 O ( N )，总的通信开销为 O ( N ).分区域以后，节点只需要与分区域的中心节点通信，假设节点均匀分布，这时候通信开销仅为 
很显然分区以后，计算和通信开销都大大降低.
本文运用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.3 V 值的影响
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 感知距离的影响
本文主要研究概率 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-dimensional K -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．Constructing K -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. 2D K -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. Achieving K -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
Fan Xinggang, Xu Junchao, Che Zhicong, and Ye Wenhao
(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023)
Abstract： 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. The K -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.
Key words： 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