1、无线传感网络讲义(Wireless Sensor Network)第四章 无线传感网络覆盖控制 主要内容主要内容 1 1无线传感器网络覆盖算法设计无线传感器网络覆盖算法设计思路及性能评价标准思路及性能评价标准无线传感器网络覆盖算法分类无线传感器网络覆盖算法分类 3 3 4 4典型的无线传感器网络覆盖算法与协议典型的无线传感器网络覆盖算法与协议 2 2无线传感器网路覆盖感知模型无线传感器网路覆盖感知模型主要内容主要内容 1 1无线传感器网络覆盖算法设计无线传感器网络覆盖算法设计思路及性能评价标准思路及性能评价标准无线传感器网络覆盖算法分类无线传感器网络覆盖算法分类 3 3 4 4典型的无线传感器
2、网络覆盖算法与协议典型的无线传感器网络覆盖算法与协议 2 2无线传感器网路覆盖感知模型无线传感器网路覆盖感知模型无线传感器网络覆盖算法设计思路及性能评价标准无线传感器网络覆盖算法设计思路及性能评价标准无线传感器网络覆盖无线传感器网络覆盖算法设计思路及性能评价标准算法设计思路及性能评价标准研究的目的:(1)使待检测区域中的每一点都至少在一个传感器节点的覆盖范围内。(2)在保证覆盖要求的基础上，同时减少网络节点能量消耗、延长网络寿命。 节点部署方式 网络节能 传感与通信距离 网络可扩展无线传感器网络无线传感器网络节点部署有两种节点部署有两种,即确定性部署和即确定性部署和随机部署随机部署无线传感器网
3、络往无线传感器网络往往节点硬件平台资往节点硬件平台资源首限、网络节点源首限、网络节点数量巨大、实际应数量巨大、实际应用的环境条件复杂用的环境条件复杂且大多不允许对且大多不允许对“失效失效”节点进行节点进行电池更换。电池更换。在设计覆盖算法需在设计覆盖算法需要考虑节点的传感要考虑节点的传感和通信距离。和通信距离。保证网络的可扩展保证网络的可扩展性是无线传感器网性是无线传感器网络覆盖技术的另一络覆盖技术的另一项关键需求。项关键需求。无线传感器网络覆盖技术无线传感器网络覆盖技术 1 1无线传感器网络覆盖算法设计无线传感器网络覆盖算法设计思路及性能评价标准思路及性能评价标准无线传感器网络覆盖算法分类无
4、线传感器网络覆盖算法分类 3 3 4 4典型的无线传感器网络覆盖算法与协议典型的无线传感器网络覆盖算法与协议 2 2无线传感器网路覆盖感知模型无线传感器网路覆盖感知模型无线传感器网络覆盖感知模型节点的感知范围是一个以节点为圆心，节点的感知范围是一个以节点为圆心，以感知距离为半径的圆形区域，只有以感知距离为半径的圆形区域，只有落在该圆形区域内的点才能被该节点落在该圆形区域内的点才能被该节点覆盖，数学表达式为：覆盖，数学表达式为：此模型简称为此模型简称为0-1模型，即当监控对象模型，即当监控对象处在节点的感应区域时，它被节点监处在节点的感应区域时，它被节点监控到的概率恒为控到的概率恒为1，而当监控
5、对象处在，而当监控对象处在感应区域之外时，它被监控到的概率感应区域之外时，它被监控到的概率恒为恒为0。布尔感知模型布尔感知模型节点的圆形感知范围内，目标被感知节点的圆形感知范围内，目标被感知到的概率并不是一个常量，而是由目到的概率并不是一个常量，而是由目标到节点间距离、节点物理特性等诸标到节点间距离、节点物理特性等诸多因素决定的变量。多因素决定的变量。、节点不存在邻居节点、节点不存在邻居节点、节点存在邻居节点、节点存在邻居节点概率感知模型概率感知模型1, ( , ),0, ( , )ijd i jrpd i jr节点节点i对监测区域内目标对监测区域内目标j的感知概率有的感知概率有如下如下3种定
6、义形式：种定义形式：1( , )1 ( , )122e1, ( , ),e, ( , ),0, ( , )1, ( , ),1( , )0, ( , )d i jijd i jrijijpd i jrprd i jrd i jrd i jrpd i jd i jr由于邻居节点的感应区域与节点自身由于邻居节点的感应区域与节点自身的感应区域存在交叠，所以如果节点的感应区域存在交叠，所以如果节点j落在交叠区域内，则节点落在交叠区域内，则节点j的感知概率的感知概率会受到邻居节点的影响。假设节点会受到邻居节点的影响。假设节点i存存在在N个邻居节点个邻居节点n1，n2，nN，节，节点点i及邻居节点的感知区
7、域分别记为及邻居节点的感知区域分别记为R(i)，R(n1)，R(n2)，R(nN)，则，则这些感知区域的重叠区域为：这些感知区域的重叠区域为：假设每个节点对目标的感知是独立的，假设每个节点对目标的感知是独立的，根据概率计算公式，根据概率计算公式，M中任一节点中任一节点j的的感知概率计算式：感知概率计算式：12( )( )()()NMR iR nR nR nIIIL I11(1)(1)kNjijn jkGpp 无线传感器网络覆盖技术无线传感器网络覆盖技术 1 1无线传感器网络覆盖算法设计无线传感器网络覆盖算法设计思路及性能评价标准思路及性能评价标准无线传感器网络覆盖感知模型无线传感器网络覆盖感知
8、模型 2 2 4 4典型的无线传感器网络覆盖算法与协议典型的无线传感器网络覆盖算法与协议 3 3无线传感器网络覆盖算法分类无线传感器网络覆盖算法分类无线传感器网络覆盖算法分类按照无线传感器网络节点不同配置方式确定性覆盖随机性覆盖根据无线传感器网络不同覆盖目标面覆盖点覆盖栅栏覆盖面覆盖算法的目标是在大量冗余的节点中寻找能够覆盖同样区域大小并保证网络连通的节点集合。同时获取最长的网络生存周期及能量高效性也是面覆盖算法在设计时需要兼顾的目标。点覆盖算法要覆盖的目标是一些离散的目标点.在点覆盖算法中,每一个目标点都要能够被至少一个传感器节点所覆盖.栅栏覆盖考察了目标穿越网络时被检测或是没有被检测的情况
9、,反映了给定的无线传感器网络所能提供的传感、监视能力。目标是找出连接出发位置和离开位置的一条或多条路径，使得这样的路径能够在不同模型定义下提供对目标的不同传感/监视质量。随机覆盖考虑在网络中传感器节点随机分布且预先不知道节点位置的情况下,网络完成对检测区域的覆盖任务;动态网络覆盖则是考虑一些特殊环境中部分传感器节点具备一定运动能力的情况,该网络可以动态完成相关覆盖任务.基于网格的目标覆盖是指当地理环境情况预先确定时，使用二维（也可以是三维）的网格进行网络的建模，并选择在合适的格点配置传感器节点来完成区域/目标的覆盖；确定性网络路径/目标覆盖同样也是考虑传感器节点位置已知情况，但这类问题特别考虑
10、了如何对穿越网络的目标或其经过的路径上各点进行感应与追踪。无线传感器网络覆盖技术无线传感器网络覆盖技术 1 1无线传感器网络覆盖算法设计无线传感器网络覆盖算法设计思路及性能评价标准思路及性能评价标准无线传感器网络覆盖感知模型无线传感器网络覆盖感知模型 2 2 4 4无线传感器网络覆盖算法分类无线传感器网络覆盖算法分类 3 3典型的无线传感器网络覆盖算法与协议典型的无线传感器网络覆盖算法与协议 轮换活跃/休眠节点的Self-Scheduling覆盖协议 最坏与最佳情况覆盖 暴露穿越覆盖 轮换活跃/休眠节点的Self-Scheduling覆盖协议 最坏与最佳情况覆盖 暴露穿越覆盖 轮换活跃/休眠节
11、点的Self-Scheduling覆盖协议 最坏与最佳情况覆盖 暴露穿越覆盖典型的无线传感器网络覆盖算法与协议 轮换活跃/休眠节点的Self-Scheduling覆盖协议 最坏与最佳情况覆盖 暴露穿越覆盖 于网格的覆盖定位传感器配置算法 圆周覆盖 连通传感器覆盖 基于网格的覆盖定位传感器配置算法 圆周覆盖 连通传感器覆盖 基于网格的覆盖定位传感器配置算法 圆周覆盖 连通传感器覆盖 基于网格的覆盖定位传感器配置算法 圆周覆盖 连通传感器覆盖传感器节点及目标点都采用网格形式配置，传感器节点采用布尔覆盖模型，并使用能量矢量来表示格点的覆盖。单击如图所示，网络中的各格点都可至少被一个传感器节点所覆盖（
12、即该点能量矢量中至少一位为1），此时区域达到了完全覆盖。例如，格点位置8的能量矢量为（0，0，1，1，0，0）。在网络资源受限而无法达到格点完全识别时，就需要考虑如何提高定位精度的问题。而错误距离是衡量位置精度的一个最直接的标准，错误距离越小，则覆盖识别结果越优化。圆周覆盖归纳为决策问题：目标区域中配置一组传感器节点，看看该区域是否满足K覆盖，即目标区域中每个点都至少被K个节点覆盖。考虑每个传感节点覆盖区域的圆周重叠情况，进而根据邻居节点信息来确定是否一个给定传感器的圆周被完全覆盖。当指令中心向网络发送一个监视区域查询消息时，连通传感器覆盖的目标是选择最小的连通传感器节点集合并充分覆盖网络区域
13、。连通传感器覆盖的分布式贪婪算法执行过程是：首先从M中最新加入的候选节点开始执行，在一定范围内广播候选路径查找消息（CPS）；收到CPS消息的节点判断自身是否为候选节点，如果是，则单播方式返回发起者一个候选路径响应消息（CPR）；发起者选择可以最大化增加覆盖区域的候选路径；更新各参数，算法继续执行，直到网络查询区域可完全被更新后的M所覆盖。采用轮换“活跃”和“休眠”节点的Self-Scheduling覆盖协议可以有效延长网络生存时间，该协议同时属于确定性面/点覆盖和节能覆盖类型。协议采用节点轮换周期工作机制，每个周期由一个Self-Scheduling阶段和一个Working阶段组成。在Sel
14、f-Scheduling阶段：各节点首先向传感半径内邻居节点广播通告消息，其中包括节点ID和位。节点检查自身传感任务是否可由邻居节点完成，可替代的节点返回一条状态通告消息，之后进入“休眠状态”，需要继续工作的节点执行传感任务。在判断节点是否可以休眠时，如果邻居节点同时检查到自身的传感任务可由对方完成并同时进入“休眠状态”，就会出现如图3-22所示的“盲点”。为了避免“盲点”的出现，每个节点在进入“休眠状态”之前还将等待Tw时间来监听邻居节点的状态更新。最坏与最佳情况覆盖算法考虑如何对穿越网络的目标或其所在路径上各点进行感应与追踪，体现了一种网络的覆盖性质。 Meguerdichian等定义了“
15、最大突破路径”（Maximal Breach Path）和“最大支撑路径”（Maximal Support Path），分别使得路径上的点到周围最近传感器的最小距离最大化及最大距离最小化。显然，这两种路径分别代表了无线传感器网络最坏（不被检测概率最小）和最佳（被发现的概率最大）的覆盖情况。暴露穿越覆盖同时属于随机节点覆盖和栅栏覆盖的类型。如前所述，“目标暴露”（Target Exposure）覆盖模型同时考虑时间因素和节点对于目标的“感应强度”因素，更为符合实际环境中，运动目标由于穿越网络时间增加而“感应强度”累加值增大的情况。暴露穿越覆盖算法提出了一种数值计算的近似方法来找到连续的最小暴露路
16、径：首先，将传感器网络区域进行网格划分，并假设暴露路径只能由网格的边与对角线组成；之后，为每条线段赋予一定的暴露路径权重；最后，执行Djikstra算法得到近似的最小暴露路径。 未来展望 当前无线传感网络覆盖算法还有许多问题与挑战需要解决，概括如下： 1. 完善感知模型种类。目前使用的传感器节点感知模型有限，不能适用于实际无线传感网络环境下感知模型多样化需要。此外，目前节点感知模型大多没有考虑实际无线信道中出现的通信干扰，是一种理想模型。大量的覆盖控制算法都是在理想的模型下设计的，而在真实的环境中，无线传感节点及其传输范围可能不同，因此需要研究更多的异类网络的感知覆盖模型。 2.提供移动性的支
17、持。在多数情况下，传感器节点是随机布设的，而传感器节点通常被认为没有移动能力，所以可能遗漏被监测的区域。目前，无线传感网络覆盖控制理论与算法大都假定传感节点或者网络是静态的，但在战场等应用场景中，可能需要节点或网络具有移动性。这就要求节点具有移动能力，弥补网络形成的覆盖漏洞。因此，新的覆盖控制理论与算法需要提供对移动性的支持。 未来展望 3.传感器还有一些性能可以利用，如调整探测半径或探测区域不是圆，而是一个角度范围或者不规则形状。此外，如何利用无线传感网络覆盖控制理论与各种算法，开发和设计更多结合无线传感网络覆盖控制的应用。 4.当传感器节点应用于战场或空间探索时，还要考虑与现实更加接近的三维世界下的建模与节能覆盖方案，即如何针对具体的无线传感网络三维空间应用设计出有效的算法与协议，这些问题都有待进一步研究和设计。 5.无线传感网络覆盖控制的性能评价标准的设置。无线传感网络覆盖控制策略及算法的应用，有助于有效控制网络节点能量、提高感知服务质量和延长整体生存时间，但另一方面也会带来网络相关传输、管理、存储和计算等代价的提高。因此，无线传感网络覆盖控制的性能评价标准对于分析一个覆盖控制策略及算法的可用性与有效性至关重要。
