视频传感器网络覆盖控制(Coverage Control)问题研究概述

admin

传感器网络的覆盖控制问题，可以看作是在传感器网络节点能量、无线网络通信带宽、网络处理能力等资源普遍受限情况下，通过网络传感器节点放置以及路由选择等手段，最终使传感器网络的各种资源得到优化分配，进而使感知、监视、传感、通信等各种服务质量得到改善。如何根据不同的应用监测需要，对传感器网络进行不同级别的覆盖控制就成了传感器网络中一个基本但亟待解决的问题。给定一个传感器网络，覆盖控制也可以一般性地总结为通过各个传感器节点协作而达到对监视区域的不同管理或感知效果。
与覆盖控制问题直接相关的是传感器节点的感知模型，设计合理的感知模型是研究传感器网络覆盖控制的理论基础和必要手段。目前，传感器网络主要有两种基本感知模型：

   

• 布尔感知模型(Boolean Sensing Model)：节点的感知范围是一个以节点为圆心，半径为其感知距离(由节点硬件特性决定)的圆形区域。只有落在该圆形区域内的点才能被该节点覆盖，目标被感知的概率均取值为“1”，参见图1(a)。   
  
• 概率感知模型(Probabilistic Sensing Model)：在节点的圆形感知范围内，目标被感知到的概率并不是个常量，而是由目标到节点间距离、节点物理特性等诸多因素决定的变量。图1(b)中颜色深浅来表示目标被感知的概率的大小；离节点越远，颜色越浅，目标被感知的概率也就越小。
  

(a)布尔感知模型                                         (b)概率感知模型
图1  两种全向感知模型示意图

上述模型属于简单理想化的感知模型，不能很好地适用于实际传感器网络环境对感知模型多样化的需要。比如，对温度、湿度等传感器节点而言，它们对环境的感知能力是全方位的；然而，对视频传感器节点而言，它对环境的感知受“视角”的限制，是具有方向性的。可以说，视频传感器节点的方向性感知是区别于其它传感器节点的最显著特征。
针对视频传感器节点的上述特征，研究人员先后设计出更为通用的节点感知模型。根据节点感知能力范围，传感器网络模型又可分为：

   

• 全向感知模型(Omni-Directional Sensing Model)：节点的感知范围是一个以节点为圆心，半径为其感知距离(由节点硬件特性决定)的圆形区域，参见2(a)；   
  
• 有向感知模型(Directional Sensing Model)：节点的感知范围是一个以节点为圆心，半径为其感知距离，且与视角相关的扇形区域，参见2(b)。
  

(a)                                                                (b)
图2 感知模型示意图

作为传感器网络的一个重要问题，覆盖控制研究引起了国内外研究学者的广泛关注，并针对不同覆盖需求研究出一系列有效方法。覆盖问题的起源可追溯到艺术馆走廊监控问题(Art Gallery Problem)。不同的应用对覆盖有不同的解释和要求。通常可分为区域覆盖、点覆盖和栅栏覆盖三种。

   

• 区域覆盖
  

区域覆盖是最为常见的一种覆盖问题，主要用于对某个区域实施监测。通常所说的覆盖即指区域覆盖。理想情况下，即要求目标区域内的每一点至少被一个传感器节点所覆盖；其现实意义在于实现目标区域的最大化覆盖，如图3(a)所示。目前，较为成熟的区域覆盖方法是从优化节点调度，延长网络寿命的角度出发，采用轮换“活跃”和“休眠”节点的节能覆盖方案。而此节能覆盖方案的关键就是要在保证一定网络区域覆盖要求的条件下，最大化轮换节点集合数目。另外，考虑遗漏或薄弱区域的覆盖不充分问题，将移动节点引入传感器网络覆盖控制中，通过对原有的节点部署进行动态调整，实现动态适应实际需求的覆盖过程。

   

• 点覆盖
  

点覆盖只需对目标区域内的有限个离散目标进行监测，研究目的在于保证每个目标在任意时刻至少被一个传感器节点所覆盖。如图3(b)所示。当大规模密集型传感器节点随机部署时，上述区域覆盖问题也可用点覆盖近似表示。前提是网络规模大、节点分布密集，可通过覆盖每个传感器位置来近似给定区域内所有点的覆盖。因此，点覆盖研究方法与区域覆盖研究方法相类似，不同点在于：点覆盖只需要邻居节点集合信息；而区域覆盖则还需要几何/方向等方面的数据。

   

• 栅栏覆盖
  

在目标监测应用中，人们通常关心某个移动目标沿任意轨迹穿越节点的部署区域时被监测到或没被监测到的概率，这类问题属于“栅栏覆盖”，如图3(c)所示。这类覆盖问题的目标是找出连接初始位置和目的位置的一条或多条路径，使得这样的路径在不同模型定义下提供对目标的不同传感/监视质量。目前主要的解决方法是，定义“最大突破路径”(Maximal Breach Path)和“最大支撑路径”(Maximal Support Path)，分别使得路径上的点到周围最近传感器的最小距离最大化以及最大距离最小化；进而采用Voronoi图和Delaunay三角测量技术来完成最大突破路径和最大支撑路径的构造和查找。

图3  覆盖分类

按照传感器网络节点不同部署方式，我们又可将传感器网络覆盖问题分为确定性覆盖和随机性覆盖两类。

   

• 确定性覆盖
  

确定性覆盖指在传感器网络的状态相对固定或传感器网络环境已知的情况下，可以根据预先配置的传感器节点位置确定网络拓扑情况或增加关键区域的传感器节点密度。此时的覆盖控制问题，是一种特殊的网络或路径规划问题。典型的确定性覆盖有确定性区域/点覆盖、基于网格的目标覆盖和确定性网络路径/目标覆盖三种类型。确定性区域/点覆盖是指已知节点位置的传感器网络要完成目标区域或目标点的覆盖，其中，与确定性区域/点覆盖相关的一个著名计算几何问题为艺术馆走廊监控问题。基于网格的目标覆盖是指当地理环境情况预先确定时，利用二维(或三维)的网格对网络进行建模，位于网格交叉点上的传感器节点实现区域/目标的覆盖。这是一种最为典型的均匀覆盖方式。确定性网络路径/目标覆盖特别考虑了如何对穿越网络的目标或其经过的路径上各点进行感应与追踪。

   

• 随机性覆盖
  

在大多数实际应用环境中，传感器网络情况不能预先确定；另外大部分的确定性覆盖给网络带来的对称性与周期性特征，掩盖了某些网络拓扑的实际特性。再加上传感器网络自身拓扑动态变化，导致采用确定性覆盖在实际应用中具有很大的局限性，不能适用于战场等危险或其它环境恶劣的场所。因此，我们需要进一步对节点随机分布在传感区域而预先没有得到自身位置的情况进行讨论，即研究传感器网络随机性覆盖问题。
目前，传感器网络的随机性覆盖已成为传感器网络覆盖控制的一个热点问题，此类问题大致可分为随机节点覆盖和动态网络覆盖两类。
随机节点覆盖考虑在传感器网络中节点随机分布且节点位置未知的条件下，网络完成对监测区域的覆盖任务。目前关于此类问题的研究内容最为多见。 有别于一般传感器节点一经部署位置固定不变，动态网络覆盖则考虑部分传感器节点具备一定运动能力，主要应用于节点密度稀疏或部分节点能量不足的监测场景中。该类网络可以动态完成相关覆盖任务，也称作移动辅助覆盖。
视频传感器节点的方向性感知特性给解决视频传感器网络覆盖控制问题带来了全新的技术挑战。在传统传感器网络中积累的研究成果不能直接应用于视频传感器网络，迫切需要设计新方法予以解决。
目前，基于有向感知模型的覆盖控制研究尚处于起步阶段。作为一种与监测应用密切相关技术，视频传感器网络中覆盖控制问题已不仅仅是单纯的覆盖含义，更与能量节约、目标探知、路径规划等具体应用紧密相关联。按照视频传感器网络相关应用属性，我们可以将视频传感器网络中覆盖控制问题的理论研究分为以下三类：

   

• 能量节约：主要机理是将冗余节点分成多个不交叉的集合，各集合能够独立提供连续、有效的监测服务。   
  
• 目标探知：在合理利用网络现有资源的基础上，实现视频传感器网络对监测区域的覆盖优化，以获得尽可能高的目标探知概率。   
  
• 路径规划：这是一类与覆盖控制密切相关的应用，采用网络动态覆盖控制方案，随时改变对某些感兴趣区域或目标路径的覆盖程度。
  

在实际应用中，视频传感器节点(如普通摄像头、PTZ摄像头、广角摄像头等)则具有的多种不同感知能力，它们赋予视频传感器网络覆盖控制研究以新的涵义。我们总结了以视频传感器网络为基础的监测系统所广泛采用的覆盖控制策略，并进行分类说明，参见表1。