第二章网络覆盖分解.ppt

当指令中心向网络发送一个监视区域查询消息时，连通传感器覆盖的目标是选择最小的连通传感器节点集合并充分覆盖网络区域。 * 当指令中心向网络发送一个监视区域查询消息时，连通传感器覆盖的目标是选择最小的连通传感器节点集合并充分覆盖网络区域。 * * 连接性随机覆盖方法 连接性随机覆盖方法 分布式最优地理密度控制算法 覆盖结构协议 设计目标：确保网络的连接性，保证节点间相互通信 分布式最优地理密度控制算法(OGDC，Optimal Geographical Density Control)。该算法假设在任何时刻，节点可能处于以下3个状态中的一种：未决定、开和关。网络初始化时，随机激活若干个无线传感节点。而后这些节点将在网络中广播“能源开”的信息，同时将其自身状态设置为开。所传递的信息包含两部分：①发送者的位置；②下一个工作节点的位置与方向。网络中每个节点都保留邻近节点的信息列表。 2连接性随机覆盖方法 覆盖结构协议(CCP，Coverage Configuration Protocol)是另一种用于优化网络连接性的网络协议。该协议能动态组织网络，为各类应用提供不同的覆盖度。为提高算法运算速度，每个节点都包含周围节点的信息列表，并周期性的发送信息以广播自身的位置和状态。 2. 连接性随机覆盖方法 点覆盖 该算法要覆盖的目标：是一些离散的目标点.在点覆盖算法中,每一个目标点都要能够被至少一个传感器节点所覆盖 随机性点覆盖 确定性点覆盖 要求每个目标在任意时间内都能至少被一个无线传感器节点监测 最大化传感器节点集合的数量 研究目标：采用最少数量的无线传感器节点对确定的目标点集进行监测 假设所有传感器具有相同的感知范围通信范围=感知范围 2.2.3无线传感网络的边界覆盖 1．边界覆盖模型I 当前研究的边界覆盖问题包含两种边界覆盖模型。 第一种模型为：在一个区域中布置了无线传感节点，已知一个要穿过该区域物体的起始和终止位置，测定该物体的最大突破路径(MBP，Maximal Breach Palh)和最大支持路径(MSP，Maximal Support Path)。MBP和MSP分别与最差和最优覆盖相关，分别对应于使路径中的每个点与最近的无线传感节点之间的距离最大(最小)的情况。实验证明，MBP位于Voronoi图线上，MSP位于Delaunay三角测量线上。 “最大突破路径” 和“最大支撑路径”分别使得路径上的点到周围最近传感器的最小距离最大化及最大距离最小化。这两种路径分别代表了无线传感器网络最坏（不被检测概率最小）和最佳（被发现的概率最大）的覆盖情况。 如果各个三角形的外接圆内部都不再含有其它传感器节点，表示无线传感器网络的Delaunay三角图。 Delaunay三角图各个有共享边的三角形外接圆的圆心相连就构成了无线传感器网络的Voronoi图。 最大突破路径查找过程 由于Voronoi图中的线段具有到最近的传感器节点距离最大的性质，因此最大突破路径一定是由Voronoi图中的线段组成。最大突破路径查找过程如下: ①根据各节点的实际地理位置产生节点网络分布图(假设每个节点的位置己知)； ②基于各节点的位置生成网络Voronni图。(有成熟的几何算法支持图的生成)每一条边到它最近的传感器节点之间的距离被赋予一个权重，这个权重就是一个距离值。为以后的比较作准备; ③在最小和最大的权重之间执行二进制查找算法:首先给出一个参考权重标准，这个参考权重要考虑所有权重的分布形式。最好找处于中间位置的权重。然后进行宽度优先查找(breadth一first一search)，检查是否存在一条从F到I的路径，满足路径上线段的权重都比参考权重标准要大。如果路径存在，则增加参考权重标准来缩小路径可选择的线段数目，否则就降低参考权重标准； ④最后得到一条从F到I的路径，也就是最大突破路径。 2．边界覆盖模型Ⅱ 第二种边界覆盖问题模型是基于目标暴露的模型。该模型假设当测量距离增加时无线传感器节点的测量精度随之下降，除此之外，测量时间(即目标暴露时间)也是一个很重要的因素。通常测量时间越长，对应的测量精度也越高。无线传感器节点的二维感知模型可定义为： (2-1) 式中，d (s，p)为传感节点s与点p间的欧式距离； 和k是传感节点的相关参数。 无线传感器网络覆盖控制算法与协议 1.节能覆盖 由为了延长网络寿命，在保持覆盖性能的一前提下，减少工作节点数，即让冗余节点处于低能耗的休眠状态如何延长网络的整体生存时间，也就是WSN的“寿命”问题。最初的想法就是让一部分节点先工作，其他