视频传感器网络覆盖问题

摘要：视频监控已经被广泛应用于各种场景，为安全防卫提供了有效信息。综述视频传感器网络中覆盖问题的相关研究。视频传感器网络具有有向传感器网络的一般特征。考虑到监测对象通常有面部朝向属性，视频传感器网络的感知模型又不同于一般的有向传感器网络的感知模型。根据感知模型是否考虑监测目标的朝向，分别介绍视频传感器网络中的点覆盖、区域覆盖和栅栏覆盖问题的典型算法。此外，讨论了目前研究存在的问题以及未来可能的研究方向。

关键词：视频传感器网络；目标覆盖；区域覆盖；栅栏覆盖；全视角覆盖

0引言

近些年来，无线传感器网络不仅在学术上被广泛研究，而且也引起了工业界的极大重视，逐步走向实际应用，其应用需求也呈现出多样化。随着摄像头制造水平的提高，成本逐渐降低，使得其被嵌入到无线传感器网络节点中构成视频传感器网络（Visual Sensor Network， VSN或 Videobased Wireless Sensor Network， VWSN）成为可能。视频传感器网络就是由一定数量的具备拍摄视频图像功能的节点通过无线通信方式自组织的网络系统，用来感知、采集和处理网络覆盖区域中目标对象的信息。视频传感器网络提供的图像信息相对来说更加丰富和精确，常常被用于环境监控、目标定位与追踪、智能家居和远程医疗监控等。

在无线传感器网络中，覆盖问题是一个重要的基础研究问题。覆盖问题研究如何放置及调度传感器节点工作使得无线网络区域的信息可以被有效地感知。覆盖问题常与传感器节点的部署与工作调度、网络连通性和能量有效等研究相关。大多数无线传感器网络中，传感器节点感知的信息不具有方向性，如温度、湿度信息等，因此，研究覆盖问题时通常假定传感器的感知区域为以传感器节点所在位置为中心的圆形。视频传感器网络中，节点所感知到的目标图像不仅与其放置位置相关，还与其放置的角度和摄像头的拍摄参数密切相关。相同位置条件下，摄像头的拍摄角度不同，捕获的视频信息相差很大，这使得视频传感器网络的感知模型与传统传感器网络的感知模型存在很大差别，也对视频传感器网络中的覆盖问题的研究提出了新的挑战。

目前，研究视频传感器网络覆盖问题的大多数文献把视频传感器网络看作是一种有向传感器网络，只单纯地考虑摄像头的位置和角度，以最大化覆盖率、低成本、网络连通性、能量有效、鲁棒性等为目标设计算法。而在某些实际应用中，如要监控非法入侵者，如果只拍摄到入侵者的背影不能满足监控的需求，因此文献[1]把目标的面朝方向考虑进来，提出了全视角覆盖问题。本文将阐述近年来关于视频传感器网络覆盖问题的最新研究成果，介绍不同感知模型下相关的点覆盖、区域覆盖和栅栏覆盖等算法，期望能为展开这一领域研究工作提供有价值的参考。

1视频传感器网络

1.1视频传感器网络的感知模型

传感器的感知模型从物理模型角度看，有全向模型和有向模型两种，从数学模型角度描述，有二值模型和概率模型。全向模型的感知区域是传感器周围360°范围内的信息，有向模型的感知区域是一个扇形区域。传感器是否感知到目标的信息，只有是和不是两种情况时，即为二值模型，这种模型也是大多数传感器网络使用的理想模型，目标落在感知区域内就认为可以感知到信息，否则不能感知；而在实际应用中，由于一些干扰因素，即使目标位于感知区域内，也可能感知不到，因此，是否感知到信息用概率模型描述更为准确，这个概率可能是目标和传感器节点间的距离等因素的函数。视频传感器网络中，视频传感器的感知区域通常是一个扇形区域，按感知模型是否高考目标面朝方向，可以分为以下两种：

1）与目标朝向无关的感知模型。

视频传感器网络中，与目标朝向无关的感知模型和传统的有向传感器的感知模型类似，感知区域在二维空间上可以表示为一个扇形区域。如图1所示，其中P表示视频传感器的位置，R表示扇形区域的半径，α表示感应视角，视频感知区域（Field of View， FoV）由P、R、α决定。更实际的，考虑到如果目标距离摄像头过近，拍摄的图像不能辨识目标，所以在这个扇形区域内，我们用D表示目标与视频传感器的最近距离，则视频感知区域由P、R、α和D决定。与目标朝向无关的感知模型没有考虑探测目标的面朝方向，只要目标位于感知区域内，就认为可以感知到目标。

1）传感器的部署方式。

与传统的传感器网络类似，视频传感器网络中节点的部署方式也有两种：确定性部署（DeterministicDeployment）和随机部署（RandomDeployment）。确定性部署中每个传感器节点的位置和朝向是预先设定的；随机部署中，节点的位置和朝向都是随机放置的，如在某些应用中，节点通过飞机撒放的方式随机部署。确定性部署中，研究节点的部署策略时，通常要最小化遮挡区域和节点覆盖的重叠区域，使得用最少的节点数目保证覆盖的最大化。随机部署以及有冗余的确定性部署中，通常研究节点的工作调度策略，来延长传感器网络工作时间；或者假定节点的工作方向可旋转，通过调度节点工作方向实现能量有效、覆盖率最大等目标。

2）传感器的感知模型。

如1.1节所介绍的，视频传感器网络中，视频节点的感知模型有两种：与目标面朝方向无关感知模型和与目标朝向有关的感知模型。研究覆盖问题时，首先要根据应用场景需求，确定感知模型的类型。

3）应用需求和问题目标。

以能量有效为需求的覆盖问题通常通过部署节点或调度节点的工作时间和工作方向优化能量使用。以连通性为需求[5]的研究考虑在保证覆盖的同时，如何保证传感器网络内任何一对工作节点间有至少有一条通信链路。以容错鲁棒性为需求的研究考虑网络内有某个节点失效时，如何保证整个网络依然正常工作，一般通过kcoverage来实现网络的容错性[6]。上述问题的优化目标可以是最大化网络寿命、最小化覆盖间隙、最小化所选取的传感器节点数目或最小化能量消耗。视频传感器网络中，可以通过有计划地部署传感器节点，调度传感器的工作时间，旋转视频传感器节点的方向，采用可移动的视频传感器节点等方法来实现优化目标。

3视频传感器网络的典型覆盖控制算法

按覆盖的需求，传感器网络覆盖问题大致可分为三类[7-8]：目标（点）覆盖（targetcoverage）[9-14]、区域覆盖（areacoverage）和栅栏覆盖（barriercoverage）。下面介绍不同感知模型下视频传感器网络的覆盖控制问题的典型算法。

3.1目标（点）覆盖

目标覆盖研究如何部署和调度传感器节点，使得监控区域内的目标至少被一个传感器节点覆盖。因为目标在区域内离散分布，所以目标覆盖也被称作点覆盖。目前关于视频传感器网络的文献均是基于与目标朝向无关的感知模型。由于与目标朝向无关的感知模型与普通意义上的有向传感器网络的感知模型相同，一些针对有向传感器网络的覆盖控制算法同样适用于与目标朝向无关的感知模型的视频传感器网络。下面介绍几种均不考虑目标面朝方向的典型目标控制算法，它们的应用需求和优化目标各不相同。

Ai等[15]是研究有向传感器网络目标覆盖的先驱，提出了MCMS（MaximumCoveragewithMinimumSensors）问题，即给定m个目标，n个有向传感器节点随机部署在监控区域中，每个传感器有p个工作方向，如何用最少的传感器节点覆盖最多的目标。作者证明了MCMS问题是NP COMPLETE问题，并用整数线性规划（IntegerLinearProgramming，ILP）形式化的表示了这个问题。文中还提出了多项式时间内的集中式贪婪算法（CentralizedGreedyAlgorithm，CGA）和分布式贪婪算法（DistributedGreedyAlgorithm，DGA）。CGA是一个迭代的过程，每次迭代过程都优先选取可以覆盖目标数目最多的传感器节点及其相应的工作方向。DGA中，每个节点指定一个优先权值并与两倍感知半径内的邻居比较优先权值的大小，优先权值大的优先选择工作方向，每次选择工作方向的原则也是尽可能覆盖最多的目标。虽然CGA的优化性能比DGA好，但是DGA通信量和计算复杂度低，更适合实际应用。

为了延长网络的生命周期，Cai等[16]提出了MDCS（MultipleDirectionalCoverSets）问题，把传感器节点的工作方向组织为一组不相交的覆盖集，每个覆盖集可以覆盖监控区域内的所有目标，通过覆盖集轮流工作达到网络生命周期最大化的目标。作者证明了MDCS问题以及DCS（DirectionalCoverSet）问题是一个NP COMPLETE问题，把MDCS问题形式化为混合整数规划（MixedIntegerProgramming，MIP）问题，然后松弛整数约束把MIP问题变为线性规划（LinearProgramming，LP）问题并提出三种启发式算法：Progressive算法、Prog Resd算法和Feedback算法。随后，Cai等[17]也研究了DCS问题，把可以覆盖所有目标的传感器的工作方向的集合称作覆盖集（CoverSet），提出了一个集中式算法DCS Greedy和一个分布式算法DCS Dist来调度传感器节点的工作方向找到覆盖集。

Han等[18]研究了保证连通覆盖的有向传感器节点的部署问题，首先针对连通的点（目标）覆盖（ConnectedPoint CoverageDeployment，CPD）问题展开讨论，即如何放置最少的传感器节点并保证连通覆盖。因为已被证明为NP HARD问题的GSC（GeometricSectorCover）问题是CPD问题子问题，Han等[18]提出了两种GSC问题的近似算法。

Fusco等[19]扩展了传统的有向传感器的覆盖问题，研究了如何选择最少数目的传感器节点并指定节点的工作方向，使得目标或区域在给定T内被覆盖k次（SelectingandOrientingD sensorsforkCoverage，SODkC）。文献[19]证明了SODkC问题是NP HARD问题，提出了一种基于贪婪策略的近似算法。

考虑到网络中传感器节点数目有限，或者受部署的限制，在某一时刻可能不能完全覆盖所有目标，受到扫描覆盖（sweepcoverage）的启发，文献[20]创新性地提出了间歇覆盖目标的问题，即目标不是持续被传感器节点所覆盖，而是在一个周期内保证被覆盖一次。对每个目标来说，相邻两次覆盖的时间间隔就是服务延迟。作者研究的主要问题就是怎样为每个传感器选择最优覆盖目标集，从而使最大的服务时延最小化。文中证明了这个问题是NP COMPLETE问题，并就是否考虑定向传感器的旋转时延两种情况对该问题进行研究，分别提出了集中式和分布式协议。

文献[21]考虑到传感器网络传输信息天线（A）和感知信息（S）均分为全向（O）和有向（D）两种，对传感器网络分为OAOS、DAOS、OADS和DADS四种情况，研究了保证连通的能量最小化覆盖算法。其中OADS、DADS也适用于视频传感器网络。作者对OADS、DADS提出了多对数近似比的算法。

3.2区域覆盖

区域覆盖要求监控区域内的每个点至少被一个传感器节点覆盖。下面按感知模型是否与目标朝向有关，介绍相关研究工作。

3.2.1基于与目标朝向无关的感知模型的区域覆盖

如果不考虑覆盖目标的面部朝向，视频传感器网络的区域覆盖等同于有向传感器网络下的区域覆盖，下面介绍相关的典型算法，各算法有各自的优化目标和应用需求。

文献[22]首先提出了有向传感器网络的概念，并基于视频传感器分析了有向传感器网络的覆盖模型，对于随机部署的定向传感器网络，给出了预测监测区域覆盖率的理论依据。然后，文章提出了一个满足给定覆盖率情况下，部署有向传感器节点来保证其连通性的算法。作者将有向传感器网络模型化为一个有向的通信图，即根据两个传感器节点是否在彼此通信范围之内来决定是否连边，进而分析通信图的连通性，并对一个随机部署的定向传感器网络提出了修复其通信图连通性的方法。随后，作者研究了有向传感器网络的区域覆盖问题，在文献[23]中首先对静态有向传感器网络中给定的覆盖率精确估算了所需要的传感器的数目，然后设计了一种区域覆盖优化算法，将网络分为若干个连通感知子图（SensingConnectedSub Graph，SCSG），然后采用分而治之的方法为每个SCSG构建多层凸壳集，调整节点感知方向，提出coverage enhancing算法最小化同一个凸壳内相邻节点重叠的感知区域，最大化覆盖区域。

文献[24]研究MDAC（MaximumDirectionalAreaCoverage）问题，即对于一个给定的区域A和一组定向传感器S，假定每个传感器都有P个感知方向，怎样对每个传感器至多选择一个感知方向使得所有传感器覆盖区域的集合最大。文献[24]证明了这个问题是NP COMPLETE的，并提出了一个分布式的贪心算法DGreedy，该算法根据感知邻居（如果两个传感器的感知扇区有交集则互为感知邻居）的数量来指定贪心优先级，感知邻居少的传感器优先确定工作扇区，感知邻居多的节点后确定工作扇区。

文献[25]为了平衡有向传感器网络中最大化网络生命时间和最小化覆盖间隙这两个有冲突的目标，研究了在生命时间受约束的情况下最小化覆盖间隙问题（MinimumCoverageBreachunderLifetimeConstraint，MCBLC）和在覆盖间隙受约束的条件下最大化网络生命时间问题（MinimumLifetimeunderCoverageBreachConstraint，MLCBC）。文章首先将MCBLC问题模型转化为整数规划形式，然后提出两个启发式算法（MCBLC G和MCBLC C 1），采取的方法是将传感器的所有可选扇形（对应其可选方向）组织成一组可以相交的扇形子集，其中每个扇形子集为可行的覆盖集，然后为这些覆盖子集分配工作时间，算法限定任何时间内只有一个可行覆盖集工作。基于MCBLC G（MCBLD Gl）算法，可以利用二分搜索技术得到MLCBC问题的算法。

文献[26]研究了视频传感器网络中最大化网络生命周期的问题。作者定义了一组地理上接近捕获相同或相似的场景的视频传感器节点为“语义邻居”，通过提取图像特征，分析比较来找到语义邻居。通过从语义邻居中选取冗余节点，使其适当地睡眠达到延长网络生命周期的目标。

以上区域覆盖均是基于二维空间的研究，Ma等[27]开展了三维空间覆盖问题的研究，提出在三维感知模型的基础上基于虚拟势场分析的区域覆盖增强算法。考虑到质心点受到合力作用后进行调整很难建立优化目标与调整参数之间的关系，无法实现最优化区域覆盖，文献[25]提出基于模拟退火（SimulatedAnnealing，SA）的SA ACE算法实现全局覆盖优化，通过建立能量函数，在优化算法实现过程中对优化质量和运行时间（即迭代次数）这两方面的性能进行折中，以获得在现有节点布局空间内的区域覆盖最优解.

3.2.2基于与目标朝向有关的感知模型的区域覆盖

文献[28]较早地提到了捕获监控目标的面部正面的意义和重要性，但只是从图像处理的角度解决如何估算监控目标面部朝向的问题，不是研究覆盖问题。考虑目标朝向的区域覆盖要求无论监控区域内的目标面朝任何方向，视频传感器都可以捕获到目标的正面，这与普通的有向传感器网络区域覆盖有很大不同，目前考虑目标朝向的区域覆盖的相关文献还比较少。

文献[1]考虑了视频传感器网络中监控区域内目标的面朝方向问题，首次提出了全视角覆盖区域的概念。作者首先定义了点的全视角覆盖（full viewcoverage），即对于一个给定的点P，无论位于点P的目标的面部朝向是哪个方向，总有一个视频传感器能覆盖它，也就是说，若P点的目标面部朝向与它和传感器形成的矢量之间的夹角小于一个参数φ，那么这个点就是被全视角覆盖的。而所谓全视角覆盖区域，就是这个区域里面的每一个点都满足全视角覆盖。作者在文献[1]中主要研究了如下几个问题：1）对于一个随机部署的视频传感器的有界区域，如何判定该区域是否全视角覆盖。2）对于一个摄像头传感器数量给定且随机分布的区域，其为全视角覆盖区域的概率。作者分析并给出了这个概率的下界。3）保证全视角区域覆盖的网络部署问题。文献[1]提出了一种基于四面体的确定型网络部署方法，在三角形顶点处部署摄像头传感器来获得全视角区域覆盖。

基于文献[1]的全视角覆盖概念，文献[29]研究了两种节点随机分布，均匀分布和泊松分布的视频传感器网络中，构成全视角覆盖的关键条件，分析得出了均匀分布情况下构成全视角覆盖的充分条件和必要条件，以及泊松分布情况下某个点达到全视角覆盖的充分条件和必要条件的概率。作者还考虑到了实际应用中网络的异构性问题，即摄像头节点的感知参数有差异的情况。

文献[2]也考虑了要监控到目标面部正面，但不是严格意义的基于与目标朝向有关的感知模型，作者的思路是通过使每个监控点有多于一个视频传感器覆盖来保证有更大的概率捕获到目标的面部正面。文献[2]提出了视频传感器网络的有向K覆盖（DirectionalKCoverage，DKC）问题，即如何在一个给定的监控区域A中布置尽可能少的视频传感器使得K覆盖的区域和区域A的面积比值大于一个设定的值。作者提出了一个数学模型来描述视频传感器数量，有效感知角度和有效K覆盖区域比例之间的关系，并且证明了这种模型的有效性。

3.3栅栏覆盖

栅栏覆盖的目标是保证当某个移动目标沿任意路径穿越监控区域时都能被所部署的传感器检测到。栅栏覆盖问题的研究大致分为两类：第一类是对随机部署的传感器网络区域，选择其中的某些传感器节点工作，对区域进行监控以形成栅栏，使得每个穿越传感器栅栏的目标都能被监测到；另一类是对于给定区域，确定传感器节点的部署密度，使得任意移动目标经过该区域的任何路径都能被监测到。下面介绍不同感知模型下这两类问题的研究。

3.3.1基于与目标朝向无关的感知模型的栅栏覆盖

Zhang等[30]研究了有向传感器网络的强栅栏覆盖问题。作者以最大化网络生命周期为目标，用图的方式模型化栅栏覆盖问题，并把该问题形式化为整数线性规划（ILP）问题，文章给出了两个基于最大流的集中式算法和一个分布式算法。最后，通过仿真实验评估算法性能与最优解很接近。文献[31]中研究了具有容错性的有向传感器网络的栅栏覆盖问题，提出了构造k栅栏覆盖的算法。

文献[32]提出了一种分布式算法——COBRA，它是最早研究无线视频传感器网络栅栏覆盖问题的算法，主要研究在一个部署了无线视频传感器网络的矩形区域中如何得到栅栏覆盖。其基本思想是：每个视频传感器根据它与邻居节点之间的几何关系来确定所有可能的栅栏线（如果两个视频传感器的覆盖区域有交集则可连边构建一条栅栏线），区域的两端是两个sink节点，算法的目标是从一个sink节点出发找到一条由栅栏线连接起来的路径到另一个sink节点，且该路径所经过的传感器节点最少，该线上的所有视频传感器节点即构成栅栏。

文献[33]研究监测目标的移动路径，并提出了一种基于虚拟势场的路径覆盖增强算法。文献[34]中，作者基于计算几何方法对最坏情况覆盖检测问题进行描述和定义，采用质心替代节点扇形感知区域构造Voronoi图，寻找最大突破路径，实现最坏情况覆盖检测。

Tao等[35]研究了对于已经部署好的有向传感器网络，改变节点工作方向构成强栅栏覆盖的问题。首先研究了一维强栅栏覆盖问题，并提出了一种最小数目传感器节点的多项式时间算法；然后，把问题扩展到二维空间，把问题模型化为DBG（DirectionalBarrierGraph）；接着判断是否有可能通过调整节点工作方向提供强栅栏覆盖，如果有，作者提供了能量有效的解，使所有节点需要旋转的角度的总和以及最大值最小。

3.3.2基于与目标朝向有关的感知模型的栅栏覆盖

因为摄像头能对一个目标从不同位置获得不同的视角，所以与目标朝向有关的感知模型下判定是否有效覆盖不能仅仅考虑摄像头的覆盖区域，还需要考虑监控目标的面部朝向，仅将摄像头传感器的感知区域结合起来不一定能形成一个有效的栅栏，因为有可能探测不到穿越栅栏的目标的面部正面图像，与目标朝向有关的感知模型的栅栏覆盖通过使用目标的面部朝向和摄像头的可视方向之间的夹角来衡量传感器感知目标图像的质量。

全视角模型的栅栏定义如下：给定一个矩形区域A，一边是入口，目的地在与之平行的另一边，一个视频传感器栅栏B是A中一个相连的区域，区域B内的每一个点都是全视角覆盖的并且每一条从入口到目的地的路径都会和B相交，那么B就形成了一个全视角覆盖的栅栏。

按感知模型、覆盖类型和优化目标的不同，表1总结了视频传感器网络中一些典型的覆盖控制算法。