覆盖问题是无线传感器网络配置首先面临的基本问题，因为传感器节点可能任意分布在配置区域，它 反映了一个无线传感器网络某区域被监测和跟踪的状况

研究目的:

• 使待检测区域中的每一点都至少在一个传感器节点的覆盖范围内
• 在保证覆盖要求的基础上，同时减少网络节点能量消耗、延长网络寿命

覆盖算法设计思路及性能评价标准

• 节点部署方式：确定性部署、随机部署
• 网络节能：无法对“失效”节点进行电池更换
• 传感与通信距离：在设计覆盖算法需要考虑节点的传感和通信距离
• 网络可扩展：保证网络的可扩展性是无线传感器网络覆盖技术的另一项关键需求

覆盖感知模型

布尔感知模型

节点的感知范围是一个以节点为圆心，以感知距离为半径的圆形区域，只有落在该圆形区域内的点才能被该节点覆盖，数学表达式为：
$$p_{ij}=\{\begin{array}{ll}1,& d(i,j)\le r\\ 0,& d(i,j)>r\end{array}$$
此模型简称为0-1模型，即当监控对象处在节点的感应区域时，它被节点监控到的概率恒为1，而当监控对象处在感应区域之外时，它被监控到的概率恒为0

概率感知模型

节点的圆形感知范围内，目标被感知到的概率并不是一个常量，而是由目标到节点间距离、节点物理特性等诸多因素决定的变量

在节点 i 不存在邻居节点的前提下，节点 i 对监测区域内目标 j 的感知概率有 3 种定义形式：(d(i,j)=0时，节点感知概率为1)

在节点 i 存在邻居节点的前提下，由于邻居节点的感应区域与节点自身的感应区域存在交叠，所以如果节点 j 落在交叠区域内，则节点 j 的感知概率会受到邻居节点的影响

假设节点 i 存在 N 个邻居节点 n1，n2，…，nN ，节点 i 及邻居节点的感知区域分别记为R(i)，R(n1)，R(n2)，…，R(nN)，则这些感知区域的重叠区域为：
M=𝑹(𝒊)⋂𝑹(𝒏𝟏)⋂𝑹(𝒏𝟐)⋂…𝑹(𝒏𝑵)

假设每个节点对目标的感知是独立的，根据概率计算公式，M中任一节点j的感知概率计算式：

无线传感网络覆盖算法分类

• 按照配置方式

  • 确定性覆盖

    • 确定性区域/点覆盖：指已知节点位置，完成目标区域或目标点覆盖（案例：圆周覆盖）
    • 基于网格的目标覆盖：指当地理环境情况预先确定时，使用二维（也可以是三维）的网格进行网络的建模，并选择在合适的格点配置传感器节点来完成区域/目标的覆盖
    • 确定性网络路径/目标覆盖：同样也是传感器节点位置已知，但特别考虑了如何对穿越网络的目标或其经过的路径上各点进行感应与追踪

  • 随机性覆盖

    随机覆盖考虑在网络中传感器节点随机分布且预先不知道节点位置的情况下，网络完成对检测区域的覆盖任务

    动态网络覆盖则是考虑一些特殊环境中，部分传感器节点具备一定运动能力的情况，该网络可以动态完成相关覆盖任务

• 根据覆盖目标

  • 面覆盖

    面覆盖算法的目标是在大量冗余的节点中寻找能够覆盖同样区域大小并保证网络连通的节点集合

    同时获取最长的网络生存周期及能量高效性也是面覆盖算法在设计时需要兼顾的目标

    可进一步分为单覆盖和多覆盖

  • 点覆盖

    • 点覆盖算法要覆盖的目标是一些离散的目标点
    • 在点覆盖算法中，每一个目标点都要能够被至少一个传感器节点所覆盖

  • 栅栏覆盖

    • 栅栏覆盖考察目标穿越网络时被检测或是没有被检测的情况，反映了给定的无线传感器网络所能提供的传感、监视能力
    • 目的：找出连接出发位置和离开位置的一条或多条路径，使得这样的路径能够在不同模型定义下提供对目标的不同传感/监视质量

典型的WSN覆盖算法与协议

• 基于网格的覆盖定位传感器配置算法

  传感器节点及目标点都采用网格形式配置，传感器节点采用布尔覆盖模型，并使用能量矢量来表示格点的覆盖

  网络中的各格点都可至少被一个传感器节点所覆盖（即该点能量矢量中至少一位为1），此时区域达到了完全覆盖

  【举例】位置8的能量矢量为（0，0，1，1，0，0）

  

  在网络资源受限而无法达到格点完全识别时，就需要考虑如何提高定位精度的问题。而错误距离是衡量位置精度的一个最直接的标准，错误距离越小，则覆盖识别结果越优化

• 圆周覆盖

  圆周覆盖归纳为决策问题：目标区域中配置一组传感器节点，看该区域是否满足 K 覆盖，即目标区域中每个点都至少被 K 个节点覆盖

  考虑每个传感节点覆盖区域的圆周重叠情况，进而根据邻居节点信息来确定是否给定传感器的圆周被完全覆盖、

  传感器节点圆周被充分覆盖等价于整个区域被充分覆盖

  【举例】传感器节点S圆周的覆盖情况：

  

• 连通传感器覆盖

  算法通过选择连通的传感器节点路径来得到最大化的网络覆盖效果
  该算法同时属于连通路径覆盖及确定性面/点覆盖

  当指令中心向网络发送一个监视区域查询消息时，连通传感器覆盖的目标是选择最小的连通传感器节点集合并充分覆盖网络区域

• 轮换活跃/休眠节点的覆盖协议

  采用轮换“活跃”和“休眠”节点的Self-Scheduling覆盖协议可以有效延长网络生存时间，该协议同时属于确定性面/点覆盖和节能覆盖类型

  协议采用节点轮换周期工作机制，每个周期由一个Self-Scheduling阶段和一个Working阶段组成

  Self-Scheduling阶段：各节点首先向传感半径内邻居节点广播通告消息，其中包括节点ID和位置，节点检查自身传感任务是否可由邻居节点完成，可替代的节点返回一条状态通告消息，之后进入“休眠状态”，需要继续工作的节点执行传感任务

  在判断节点是否可以休眠时，如果邻居节点同时检查到自身的任务可由对方完成并同时进入“休眠状态”，就会出现“盲点”

  为避免“盲点”的出现，每个节点在进入“休眠状态”之前还将等待Tw时间来监听邻居节点的状态更新

• 最坏与最佳情况覆盖

  最坏与最佳情况覆盖算法考虑如何对穿越网络的目标或其所在路径上各点进行感应与追踪，体现了一种网络的覆盖性质

  Meguerdichian等定义了“最大突破路径”和“最大支撑路径”，分别使得路径上的点到周围最近传感器的最小距离最大化及最大距离最小化

  这两种路径分别代表了无线传感器网络最坏（不被检测概率最小）和最佳（被发现的概率最大）的覆盖情况

• 暴露穿越覆盖

  暴露穿越覆盖同时属于随机节点覆盖和栅栏覆盖的类型

  “目标暴露”覆盖模型同时考虑时间因素和节点对于目标的“感应强度”因素，更为符合实际环境中，运动目标由于穿越网络时间增加而“感应强度”累加值增大的情况