无线视频传感器网络β-QoM目标栅栏覆盖构建算法

郭新明，刘 蕊，谢 飞，林德钰

（1.咸阳师范学院 计算机学院，陕西 咸阳 712000；2.贵州警察学院 计算机系，贵阳 550005；3.西安电子科技大学 前沿交叉研究院，西安 710071；4.西安市智能康复人机共融与控制技术重点实验室（西京学院），西安 710123；5.南昌大学 软件学院，南昌 330047）

0 引言

覆盖技术是确保无线传感器网络（Wireless Sensor Network，WSN）信息采集准确性和完整性的一项关键技术，也是WSN 服务质量的重要指标之一［1］。栅栏覆盖是WSN 的重要覆盖技术之一，主要用于检测非法穿越WSN 覆盖区域的入侵行为［2］。目标栅栏覆盖由Lalama 等［3］首次提出，主要研究大型监测对象周围环状区域中封闭栅栏的构建问题，是WSN 栅栏覆盖研究的一个新领域。

封闭栅栏的概念最早出现在文献［4］中，针对封闭环状区域的栅栏覆盖问题，假设封闭环状区域一定存在合法的断点，进而将它转换为非封闭区域的栅栏构建问题进行求解。文献［5］中针对环形WSN 中入侵行为合法性判定的问题，将从外向内被WSN 监测k次的入侵行为定义为非法入侵，在此基础上提出了一种强k栅栏构建算法，有效过滤了环形监测区域的非法入侵行为。文献［6］中针对三维空间中山地无线传感器网络的栅栏覆盖问题，提出了一种基于等位区域的环状栅栏构建算法，有效提高了复杂地貌环境下移动目标监测和轨迹追踪的质量。文献［7］中针对监测区的多目标栅栏覆盖问题，提出了一个分布式的启发式目标栅栏构建（Target-Barrier Construction，TBC）算法，将多个目标栅栏进行合并，形成包围多个目标的封闭栅栏，在降低栅栏成员数量和消息交换量方面取得了良好的效果。文献［8］中将WSN 监测区中的多目标栅栏覆盖问题抽象为求解平面内点集的凸包问题，并提出了多目标栅栏的最优合并算法，该算法能以极小成本实现WSN 中多目标的栅栏覆盖。文献［9］利用文献［8］中的成果实现了无人机杀虫灯（Insecticidal Lamp Unmanned Aerial Vehicles，IL-UAVs）的最优部署，实验结果表明该部署策略能胜任绿色农业害虫防治工作。文献［10］中针对存在部分天然屏障环境中的目标栅栏覆盖问题，利用凸包吸引（Convex Hull Attraction，CHA）算法在出口和入口处构建栅栏来实现对目标的封闭监测。针对目标栅栏构建，文献［4-10］中研究了全向感知模型的WSN 目标栅栏构建，但这些方法不适用于定向传感网络。

无线视频传感器网络（Wireless Visual Sensor Network，WVSN）是一种典型的定向传感网络，目前在WVSN 中构建目标栅栏的研究还相对较少。文献［3］中基于螺旋扫描的思想，设计了构建封闭视频栅栏的螺旋外围外覆盖（Spiral Periphery Outer Coverage，SPOC）和螺旋外围内覆盖（Spiral Periphery Inner Coverage，SPIC）算法，在监测对象周围的WVSN 中构建出监测非法入侵行为的封闭视频栅栏。文献［11］中针对可旋转WVSN 目标栅栏的构建问题，利用虚拟目标栅栏构建（Virtual Target-Barrier Construction，VTBC）算法实现WVSN 的目标栅栏覆盖，进而提出一个分布式粒子群优化（Distributed Particle Swarm Optimization，D-PSO）算法进一步优化视频栅栏的覆盖性能。文献［12］中针对存在视觉障碍环境中的封闭栅栏覆盖问题，提出了一种通过移动WVSN 中部分节点的方法围绕监测目标构建出具有避障功能的封闭栅栏。文献［3，11-12］中研究了WVSN 的目标栅栏构建问题，但却未对视频传感器捕获图像的质量作任何要求，因此往往由于捕获图像质量过低导致入侵检测失效。

为了改进WVSN 捕获图像的质量，文献［13-16］中要求构建的WVSN 栅栏捕获图像质量必须不小于β监测质量（βQuality of Monitoring，β-QoM），但这些方法构建的栅栏不封闭，无法围绕监测目标。在预警外敌入侵、保护珍稀野生动物等一些特殊应用环境中，要求在监测对象周边一定范围内部署大量视频传感器来获取清晰可辨认的入侵者图像。若能在监测对象周围建立封闭的、捕获图像宽度大于β的WVSN 栅栏，自然可以实现这类监测的需求。针对该问题，本文提出了一个无线视频传感器网络β-QoM 目标栅栏覆盖（Wireless visual sensor networkβ-QoM Target-Barriers coverage Construction，WβTBC）算法，显著改善了WSVN 入侵检测的质量。主要工作如下：

1）建立了视频传感器β-QoM 区的几何模型，并从理论上证明了质心进入视频传感器β-QoM 区的入侵者一定能被捕获到宽度不小于β的图像，为提高WVSN 入侵检测的质量提供了理论依据；

2）证明了WVSN 中围绕监测对象的最优β-QoM 目标栅栏覆盖是NP-hard 问题；

3）设计了一个构建无线视频传感器网络β-QoM 目标栅栏覆盖的启发式算法WβTBC，为WVSN 的非法入侵检测提供了一种新型解决方案。

1 网络模型及问题描述

1.1 网络模型

为了研究β-QoM 目标栅栏覆盖问题，本文定义了WVSN和入侵者的模型。WVSN 中所有视频传感器同构，除传感器位置和朝向不同外，其余参数均一致。视频传感器感知区域是一个夹角为γ感知半径为r的扇形区域，通信半径R≥2r，每个传感器均可以通过内置定位装置或定位算法获得自己的坐标位置（x，y）和视觉朝向d→，如图1 所示。WVSN 的部署范围是一个外圈边长为L，宽度为W的正方形环带区域，监测目标位于区域中心，WVSN 距离监测目标的安全距离不小于dsafe=(L-2W)/2，如图2 所示。在该环带区域内随机均匀部署n个视频传感器，传感器部署后，它的位置和视觉朝向均不发生改变。假设穿越WVSN 覆盖区的入侵者为任意方向宽度不小于β(β≪r)的凸多边形，它的最大内切圆圆心称为入侵者的质心，如图3 所示。显然，当入侵者内切圆的半径r≥β/2，它的任意方向的宽度均大于等于β。

图1 WVSN感知模型Fig.1 WVSN sensing model

图2 WVSN部署范围示意图Fig.2 Schematic diagram of deployment scope of WVSN

图3 入侵者几何模型Fig.3 Geometric model of intruder

定义1β圆。以入侵者的质心为圆心，以β/2 为半径的圆，称为入侵者的β圆（如图3 的虚线圆）。显然，入侵者的β圆与它的最大内切圆同心，且被它包含。

1.2 问题描述

WVSN 的主要监测任务是获取它的覆盖范围内移动对象的图像，传统的视频监控应用只关注WVSN 能否捕获到图像，而对捕获图像的宽度没有要求，因此在捕获图像宽度过窄的情况下WVSN 的监测功能将失效。本文假设只有当视频传感器捕获图像的宽度大于等于β时方可识别入侵对象。如图4 所示，入侵者沿虚线所示轨迹穿越WVSN，视频传感器S1和S2均抓拍到入侵者的图像，其中图像宽度w1>β，而w2<β，因此S1能通过捕获图像识别出入侵对象，而S2由于捕获图像宽度过小而无法识别。由此可见，β-QoM 是影响WVSN 监测质量的一个关键因素。

图4 视频传感器图像监测失效示意图Fig.4 Schematic diagram of visual sensor image monitoring failure

定义2 目标栅栏。视频传感器集合VS中所有传感器的感知区域联合构成了一个包围监测对象的封闭环路，对于任意穿越该环路的入侵行为，至少能被VS中一个视频传感器感知，则集合VS为监测对象的一个目标栅栏，如图5 所示。

图5 目标栅栏入侵行为检测示意图Fig.5 Schematic diagram of target-barrier intrusion behaviour detection

目标栅栏在进行入侵行为检测时，同样存在由于捕获图像宽度过小而导致的非法入侵行为漏检现象，因此WVSN 的目标栅栏覆盖仍需考虑捕获图像宽度的约束。

定义3β-QoM 目标栅栏。对于沿任意轨迹入侵监测对象的入侵者，若监测对象的一个目标栅栏中至少有一个视频传感器捕获的图像宽度大于等于β，那么该目标栅栏称为该监测对象的一条β-QoM 目标栅栏。

本文重点研究WVSN 中β-QoM 目标栅栏的构建问题，暂不考虑网络的能耗和通信效率。

2 β-QoM目标栅栏覆盖理论

2.1 单视频传感器的β-QoM图像捕获分析

由定义3 可知，β-QoM 目标栅栏对于任意入侵者至少存在一个视频传感器能捕获到宽度大于等于β的图像，因此需要研究视频传感器怎样才能捕获到β-QoM 的图像。

定义4 视频传感器β-QoM 区。视频传感器的扇形感知区域内，与两条边的距离大于等于β/2，且与传感器的距离小于等于的区域称为该视频传感器的β-QoM 区，如图6 阴影部分所示。

图6 视频传感器β-QoM区Fig.6 Visual sensor β-QoM region

定理1 若入侵者的质心进入视频传感器的β-QoM 区，那么该视频传感器一定能捕获到宽度大于等于β的入侵者图像。

证明 由图3 可知，入侵者的β圆被入侵者的凸多边形包裹，只要入侵者β圆的任一条直径线段出现在视频传感器的感知范围内，那么该视频传感器就一定能捕获到宽度不小于β的入侵者图像。

至此，可知质心在视频传感器β-QoM 区边界上的入侵者一定能被视频传感器捕获到不小于β的图像，而质心出现在视频传感器β-QoM 区内部时，该命题显然成立。证毕。

2.2 目标栅栏的β-QoM图像捕获分析

目标栅栏覆盖要求栅栏中所有视频传感器联合实现非法入侵行为检测，因此需要研究相邻视频传感器的β-QoM 图像捕获问题。

定义5β邻居。若视频传感器S1和S2的β-QoM 区相交，则传感器S1和S2互为β邻居。

定理2 若目标栅栏中所有相邻视频传感器互为β邻居，则该目标栅栏是β-QoM 目标栅栏。

证明 假设目标栅栏中所有相邻视频传感器互为β邻居，但该目标栅栏不是β-QoM 目标栅栏。

若目标栅栏不是β-QoM 目标栅栏，在目标栅栏上的某处一定存在一个薄弱点，从该薄弱点进入监测对象的入侵者不能被目标栅栏上的传感器捕获到宽度大于等于β的图像。这说明覆盖薄弱点的相邻视频传感器的β-QoM 区一定不相交，不具有β邻居关系，这与目标栅栏中所有相邻视频传感器互为β邻居矛盾。因此假设不成立，原命题成立。证毕。

2.3 WVSN最优β-QoM目标栅栏覆盖分析

资源受限仍然是WVSN 的重要特征，为了节约资源，延长网络生命周期，因此在WVSN 中组成β-QoM 目标栅栏的视频传感器应尽可能少。

定义6 最优β-QoM 目标栅栏覆盖。若WVSN 的传感器集合S={Si|i=1，2，…，n}的一个子集S'构成了一个围绕监测对象的β-QoM 目标栅栏覆盖，但不存在S的其他β-QoM 目标栅栏覆盖子集Z，使 |Z|<|S'|，那么称集合S'是监测对象的一个最优β-QoM 目标栅栏覆盖。

定理3 WVSN 中监测对象的最优β-QoM 目标栅栏覆盖是NP-hard 问题。

证明 对WVSN 的最优β-QoM 目标栅栏覆盖作如下转换。以监测对象中心为原点建立笛卡儿坐标系，将平面以原点为中心分成m个相等的角度空间，如图7 所示。

图7 最优β-QoM目标栅栏覆盖Fig.7 Optimal β-QoM target-barrier coverage

用aij表示第i个角度空间与第j个传感器间的覆盖关系，1 ≤i≤m，1 ≤j≤n。如果传感器j的感知区域与角度空间i的两条边相交，称角度空间i被传感器j覆盖。如式（1）所示。

用bij表示传感器i是否为传感器j的β邻居，1 ≤i≤n，1 ≤j≤n，如式（2）所示。

用xj表示传感器（j1 ≤j≤n）是否在β-QoM 目标栅栏中：

至此，WVSN 中监测对象的最优β-QoM 目标栅栏覆盖可以表示为如下的线性规划形式：

式（4）表示构成β-QoM 目标栅栏的传感器个数最少；式（5）表示每个角度空间至少被一个视频传感器覆盖；式（6）表示每个传感器只能有两个β邻居。如果将矩阵A和B定义为如下形式：

则式（4）～（7）可以表示成如下的矩阵形式：

其中：a为m维列向量；b、c、x为n维列向量。由式（10）～（13）可知，求解WVSN 中围绕监测对象的最优β-QoM 目标栅栏覆盖是NP-hard 问题［17］。证毕。

3 WβTBC算法设计

由定理3 可知，在WVSN 中构建监测对象的最优β-QoM目标栅栏覆盖是一个NP-hard 问题，因此无法在多项式时间内求得该问题的最优解，但可以通过设计多项式时间的启发式算法求得该问题的次优解。

3.1 算法设计思想

启发式算法是基于直观认识或经验构造的算法。由于WVSN 最优β-QoM 目标栅栏是满足捕获图像宽度要求的最少节点栅栏，因此最优β-QoM 目标栅栏实际上是一个最短环路问题，若能打破环路，就可用求最短路的方法在WVSN 中搜索最优β-QoM 目标栅栏的近似解。因此，求解的基本思想是先将WVSN 从监测目标的某一方向强制切断，然后用Dijkstra 算法［18］在开放的WVSN 区域搜索β-QoM 栅栏，最后将断点连接形成封闭栅栏。基于上述思想，首先根据节点间的β邻居关系建立网络的邻接矩阵，然后在WVSN 中随机找到一对β邻居节点（G，H），以H为起点以G为终点利用Dijkstra 算法找到一条最短路径，该路径上的节点序列即为一个β-QoM 目标栅栏。但该方法存在漏洞，如图8 所示，以S2为起点S1为终点搜索到了两条封闭的栅栏，一条包围了监测对象，而另一条由S2、S3、S4、S5、S1构成的封闭栅栏却没有包围监测对象，本文将这种没有包围监测对象的封闭栅栏称为假β-QoM 目标栅栏。

图8 假β-QoM目标栅栏Fig.8 Fake β-QoM target-barrier

存在β邻居关系的两个传感器节点的双向性是假β-QoM目标栅栏产生的主要原因。为了使β-QoM 目标栅栏能包围监测对象，需要对传感器间的β邻居关系进行单向性约束。

定义7 逆时针β邻居。以监测对象中心为原点，如果传感器S1和S2互为β邻居，且S1出现在S2的逆时针方向，那么S1是S2的逆时针β邻居，如图9 所示。

图9 逆时针β邻居Fig.9 Counterclockwise β neighbor

本文用MaxA（S）和MinA（S）分别表示传感器S覆盖区相较于监测对象中心的最大角和最小角。为简化逻辑，感知区域与X轴正方向相交的传感器最大角应大于360°，如图9（a）所示。一般认为如果视频传感器S1和S2的覆盖区相交，且MaxA（S1）>MaxA（S2），则S1是S2的逆时针β邻居，如图9（b）所示；如果β邻居中只有一个传感器的覆盖区域跨越X轴正方向，且满足MinA（S1）≤MaxA（S2）mod 360°

3.2 β-QoM目标栅栏构建算法描述

根据上述思想，本文设计了一种在WVSN 中求解β-QoM目标栅栏覆盖的启发式算法WβTBC，它的伪代码如下所示。

算法 WβTBC。

输入S（WVSN 中的视频传感器集合）；

输出BS（WVSN 的β-QoM 目标栅栏集合）。

3.3 时间复杂度分析

WβTBC 算法包含四个模块：模块一（第3）～5）行），清空所有传感器节点的逆时针邻居集，时间复杂度为O（n）；模块二（第6）～19）行），根据节点的逆时针β邻居关系建立网络的邻接矩阵，时间复杂度为O（n2）；模块三（第21）行），运行Dijkstra 算法的时间复杂度是O（n2）；模块四（第22）～33）行），在WVSN 中搜索β-QoM 目标栅栏，时间复杂度为O（n）。四个模块在逻辑上并列，因此算法WβTBC 的时间复杂度为最大值O（n2）。

通过分析可知，文献［3］中的算法SPOC 和SPIC 的时间复杂度至少是O（n3）；算法TBC 的时间复杂度为O（n）［7］。本文算法WβTBC 的时间复杂度优于算法SPOC 和SPIC，但是不及分布式算法TBC［7］。

4 仿真实验与结果分析

4.1 实验平台构建

本文使用Matlab 2012a 搭建β-QoM 目标栅栏覆盖的仿真实验平台，部署在监测对象周围的WVSN 采用随机均匀部署，实验平台的相关参数设置如表1 所示。

表1 实验平台的参数设置Tab.1 Parameter setting of experimental platform

4.2 仿真实验与数据分析

实验在WVSN 内部署视频传感器的数量从100 开始，步长为20，逐步递增至1 000。为了增强实验数据的可信度，同一部署规模拥有30 套不同的节点布局方案。按照已建立目标栅栏中的节点不再参与后续目标栅栏搜索的方法进行栅栏构建。图10 是部署规模为500，β=20 m 时，WβTBC 算法在WVSN 中找到的3 条相互独立的β-QoM 目标栅栏，图10（a）的栅栏1 长度（l构成栅栏的节点数）最短，因此栅栏1 是该布局下找到的最优β-QoM 目标栅栏。

图10 WβTBC算法仿真结果Fig.10 Simulation results of WβTBC algorithm

将WβTBC 算法分别与SPOC［3］、SPIC［3］和TBC［7］进行对比。由实验数据分析可知，在能成功构建栅栏的前提下，算法WβTBC 需要的节点数更少，且分别比算法SPOC、SPIC 及TBC 节省了大约23.3%、10.8%和14.8%的传感器节点，如图11 所示。因为WβTBC 使用Dijkstra 算法搜索最短β-QoM目标栅栏，而SPOC 和SPIC 的螺旋扫描策略主要关注栅栏的连通性，没有考虑栅栏长度的因素；TBC 构建的栅栏由4 个栅栏段拼接而成，由于没有对整个目标栅栏作进一步优化，因此构建的目标栅栏长度较大。WβTBC 的节点高效性提高了网络的节能效率，同时也延长了网络的生存时间。

图11 栅栏平均节点数对比Fig.11 Comparison of average nodes in barriers

然而，WβTBC 算法的栅栏构建成功率和平均构建栅栏数均低于SPOC 和SPIC，却高于TBC，如图12、13 所示。这是因为捕获图像的β宽度约束致使构建β-QoM 目标栅栏的视频传感器选择范围更小，因此WβTBC 构建栅栏的成功率和平均栅栏数比没有图像宽度要求的算法SPOC 和SPIC 偏低。TBC 算法由于构建目标栅栏需要在监测目标周围找到4 个初始节点，限制了目标栅栏的搜索范围，因此栅栏构建的成功率和平均栅栏数较低。图14 表明4 种算法首次成功构建栅栏的网络规模差距不大，而首次100%成功构建栅栏的网络规模差距较大。在β-QoM 的约束下，相较于TBC 算法，WβTBC 算法构建目标栅栏的效率更高。

图12 栅栏构建成功率对比Fig.12 Comparison of success rate of barrier construction

图13 平均构建栅栏数对比Fig.13 Comparison of average constructed barriers

图14 构建栅栏不同阶段的网络规模对比Fig.14 Comparison of network scales at different stages of barrier construction

WβTBC 在不同的β值下，算法性能也不尽相同。随着β值减小，构建β-QoM 目标栅栏的成功率随之增高（如图15 所示）。这是由于β值越小，视频传感器就可能拥有更多的逆时针β邻居，那么成功构建β-QoM 目标栅栏的概率就越大，自然栅栏构建的成功率会增高。另外，在网络覆盖面积不变的情况下，随着部署节点的增多，节点密度随之增大，致使节点的逆时针β邻居增多，提高了成功组建栅栏的几率，同时也减弱了β值对成功构建β-QoM 目标栅栏的影响。因此随着网络节点密度的增大，构建β-QoM 目标栅栏的成功率不断提高，而β值对成功构建栅栏的影响则逐渐减弱。

图15 不同β的β-QoM目标栅栏构建成功率Fig.15 Success rates of β-QoM target-barrier construction with different β

由图16 可知，β越小，构成β-QoM 目标栅栏的平均节点数越少；具有β邻居关系的两个节点就能拥有越大的距离。根据本文邻接矩阵的定义，欧氏距离越大的节点序列在Dijkstra 算法中更具优势，因此β值越小，形成β-QoM 目标栅栏的节点就可能越少。

图16 不同β的β-QoM目标栅栏平均节点数Fig.16 Average nodes of β-QoM target-barriers with different β

5 结语

本文针对WVSN 中目标栅栏因捕获图像宽度不足造成的入侵检测失效问题，提出了WβTBC 算法。实验结果表明，该算法能在WVSN 中构建β-QoM 目标栅栏，相较于SPOC、SPIC 及TBC，节点利用效率更高。在入侵者捕获图像宽度满足要求后，β值越小，WβTBC 构建β-QoM 目标栅栏的成功率越高，构成栅栏的节点越少，因此，在不影响入侵检测质量的情况下，β值应尽可能小。本文研究仅针对静态WVSN 环境，没有考虑动态WVSN 的应用环境，研究动态无线视频传感器网络β-QoM 目标栅栏的构建问题，将是下一步的重点工作。