第3章WSN拓扑结构、覆盖技术PPT课件.ppt

第三章WSN拓扑控制和复盖技术，了解WSN拓扑分类了解WSN拓扑控制了解WSN电源控制分层结构控制方法了解复盖理论了解传感器网络的复盖控制，第1，计算机网络课件作者：xieren，0103010网络拓扑，无线传感器网络的网络拓扑是以各种形式和网络方法构成无线传感器节点的网络技术。根据网络的形式和方法，有集中式、分布式和混合式。无线传感器网络的集中式结构类似于移动通信的蜂窝结构，是集中管理的。与AdHoc网络结构类似的无线传感器网络的分布式结构允许自配置网络访问连接、分布式管理。无线传感器网络的混合结构包括中央结构和分布式结构的组合。根据节点功能和分层结构，无线传感器网络一般可以分为平面网络结构、分层网络结构、混合网络结构和Mesh网络结构、2、课件制作人：xiexiren、3.1.1平面网络结构。如图3-1所示，平面网络结构是无线传感器网络中最简单的拓扑结构，具有以下特征：(1)所有节点都是对等结构。(2)该网络拓扑简单、易于维护、稳定性好，(3)没有中央管理节点，因此，课件制作人：xiexiren，3.1.2层次网络结构，图3-2是层次网络结构(也称为层次网络结构)。特征：网络分为上层和下层，上层是中央主干节点，下层是常规传感器节点。4，课件制作人：xiexiren，3.1.3混合网络结构，图3-3是混合网络结构。特征：1、网络主干节点间和常规传感器节点间的平面网络结构；2、网络主干节点和常规传感器节点之间应用分层网络结构。5，课件作者：xiexiren，3.1.4Mesh网络结构，从结构上看，Mesh网络是规则分布的网络。如图3-4所示，通常只允许与节点最近邻居进行通信。如图3-5所示，网络内部的节点通常相同，因此Mesh网络也称为对等网络。6，课件作者：Xie xiren，Mesh网络结构的最大优点是所有节点都在同等位置，但计算和通信传输功能相同。使用分层技术(如图3-6所示)，Mesh网络路由设计变得简单多了。部分数据处理在每个分层结构内执行，因此更适合于无线传感器网络中分布式信号的埋地和决策。3.1.4Mesh网络结构，7，课件作者：xiexiren，技术上基于Mesh网络结构的无线传感器具有以下特征：(1)网络配置为无线节点：此类型的网络节点由传感器或执行器组成，并连接到双向无线收发器。(2)节点根据Mesh拓扑进行部署，网络中的每个节点至少可以与一个其他节点通信。(3)多级跳路由支持：(4)功率限制和移动性取决于节点类型和应用程序特性。(5)有多种网络访问方法，可以通过星形、网状等节点与其他网络集成。3.1.4Mesh网络结构，8，课件作者：xiexiren，3.2拓扑控制，3.2.1概述拓扑控制技术是无线传感器网络的基本问题。动态变化拓扑是无线传感器网络的最大特征之一，因此拓扑控制策略在无线传感器网络中具有重要意义，并为路由协议、MAC协议、数据融合、时间同步和目标定位等多个方面奠定了基础。MAC层可以在拓扑控制算法邻居搜索等消息中提供，如图3-7所示。9，课件作者：xiexiren，3.2.2拓扑控制的含义在以下五个方面非常重要：(1)网络寿命，(2)降低节点通信负载，提高通信效率，(3)辅助路由协议，(4)选择数据融合策略，(5)节点冗馀，10，课件制作人：xiexiren，3.2.3拓扑1.服务范围2。连接3 .网络寿命4。吞吐量5。干涉和竞争6。网络延迟7。拓扑特性，11，课件制作人：xiexiren，3.3功率控制，传感器网络中节点发射功率的控制称为功率分配问题。1.基于节点的电源控制2。基于方向的电源控制3。基于邻接图的功率控制4。XTC算法，12，课件作者：xiexiren，3.4层拓扑控制方法，分层拓扑在群集头节点中承担数据融合操作，减少数据流量，等等。基于群集的拓扑有助于分布式算法的应用，适用于大型部署网络。大部分节点会在相当长的时间内关闭通信模块，从而大大延长整个网络的生存时间等。1.LEACH算法，13，课件作者：xiexiren，2 .GAT算法，GAT算法是一种路由算法，它根据节点的地理位置对群集进行分区，并有选择地使群集内的节点休眠。核心想法是，如果每个数据源有有效路径作为数据目标，则最大限度地减少参与数据传输的节点数，从而减少用于接收和接收包的能量开销。可以将无线传感器网络分割为单元(群集)，并代表单元内的所有节点完成到相邻单元的数据包传输。选定节点将成为此单元的群集头节点。其他节点在不发送、接收和接收数据包的情况下休眠。GAT算法通常分为两个阶段：虚拟单元的分割和虚拟单元的群集头节点选择。(1)虚拟单元的分隔。(2)选择虚拟单元的群集头节点。14，课件作者：谢锡仁，3.5灵感机制，在传感器网络的拓扑控制算法中，除了传统电源控制和分层拓扑控制两个方面外，还提出了启发式节点唤醒和休眠机制。该机制允许节点在未发生事件的情况下将通信模块设置为节能状态，在发生事件的情况下自动唤醒相邻节点，从而构成数据传递的拓扑结构。1.STEM算法sparsetophologyandnergymanagement(STEM)算法是一种低工作周期节点唤醒机制。算法使用接收信道和数据通信信道，即双通道。具体地说，STEM算法分为STEM-B(STEM-BEACON)算法和STEM-T(STEM-TONE)算法。STEM-B算法在一个节点尝试将数据传输到另一个节点时，首先将唤醒包字符串传输到活动节点。目标节点收到唤醒数据包后发送响应信号，并自动进入数据接收状态。活动节点收到响应信号后，进入数据传输阶段。在STEM-T算法中，节点定期进入接收等待阶段，检测是否有要传输数据的相邻节点。如果一个节点要与一个相邻节点通信，它将发送一系列唤醒数据包，发送的唤醒数据包必须比接收等待时间间隔长。然后，相邻节点可以接收唤醒数据包，并立即从下一个节点发送数据包。所以STEM-T比STEM-B简单实用。STEM算法适用于环境监视或突发监视等应用程序，实验证明节点唤醒速度满足应用程序的要求。但是，在STEM算法中，节点的睡眠周期、部署密度和网络的传输延迟之间存在着密切的关系，并根据具体的应用要求进行了调整。15，课件制作人：xiexiren，2 .ASCENT算法、运行ASCENT算法的网络包括三个主要阶段：触发、构建和稳定。触发步骤在聚合节点与数据源节点不能正常通信时请求相应相邻节点的帮助，如图3-12(a)所示。如设置步骤图3-12(b)所示，节点在收到来自相邻节点的帮助消息时，通过特定算法确定自己是否成为活动节点，如果成为活动节点，则向相邻节点发送通知消息，该消息是判断相邻节点是否成为活动节点的因素之一。稳定阶段如图3-12(c)所示，数据源节点和聚合节点之间的通信恢复正常，网络中的活动节点数稳定，稳定状态，16，课件制作人：xiexiren，3.6 coverage，3 . 6这是因为无线传感器网络的一个区域反映了被监控和跟踪的情况。现有的很多研究结果都致力于解决传感器网络的部署和监控以及复盖范围和连接问题。也有对特定应用程序需求的研究，但核心思想与覆盖问题有关。17，课件作者：Xie xiren，与无线传感器网络coverage相关的两个计算几何问题，(三角形，圆)。第一个是美术馆的问题。美术馆所有者设想，为了防止小偷盗窃，在博物馆内放置照相机。为了实现这个想法，我有两个问题。第一个究竟需要多少台照相机？其次，必须放置相机，以便每个点至少由一个相机监视。假设相机可以具有视角并以最大速度旋转，则相机可以在任何位置监视，视线不受影响。基于3 . 6 . 1 coverage理论，18，课件作者：Xie xiren，问题优化通常需要最小化建模为二维平面简单多边形所需的相机数。简单的解决方案是将多边形划分为非重叠三角形，并将摄影机放置在每个三角形内。通过三角剖分将多边形划分为多个三角形，以便一个多边形可以被摄影机监视。其中n表示多边形中包含的三角形数。这也是最坏情况下最好的结果。基于3 . 6 . 1 coverage理论，19，课件制作人：Xie xiren，图3-7显示了用三角剖分方法分割简单多边形的示例，并放置了足够复盖整个美术馆的两个监视相机。这个问题在二维平面上可以得到最佳解决方案，但是扩展到三维空间后，它就会成为NP-hard问题。图3-7多边形的三角剖分和监视相机的位置配置NP-hard问题：NP表示非确定性多项式(non-deterministicpolynomial，缩写NP)。不确定性是指用一定数量的运算解决多项式时间内可以解决的问题。NP问题一般来说，解决方案的准确性是“容易检查”的问题。在这里，“容易检查”意味着有多项式检查算法。因此，如果NP中的所有问题都可以作为图灵提交，则问题是，基于NP难度、3.6.1覆盖理论、20、课件制作人：xiexiren，与无线传感器网络复盖有关的另一个几何问题是圆复盖问题，即一个平面上最多需要几个相同大小的圆才能完全复盖整个平面。换个角度来说，给定圆的数量如何使圆的半径最小。A. heppes和J.B.M.Melissen实现了矩形平面中圆的最佳应用问题，复盖范围最多为5个圆和7个圆。图3-8所示的7个圆的最佳复盖范围示例。图3-8使用7个圆实现最佳复盖的示例，3 . 6 . 1 coverage的理论基础，21，课件制作人：xiexiren，无线传感器网络复盖问题实质上与上述几何计算问题一致。您需要知道特定区域是否完全被复盖和监视。配置的传感器节点数在成本方面非常重要。在典型的无线传感器网络应用程序中，放置或配置一些传感器节点以监视区域或点集。3.6.1基于复盖理论，22，课件作者：xiexiren，确定性配置和非确定性配置(随机配置)1。某些应用程序可以选择传感器配置站点，如定点部署和配置，这称为确定性配置。2.在某些其他应用中，例如在敌方区域或极端恶劣的环境下，只要随机放置(例如喷洒空气液滴)，就可以向监控区域发送足够数量的传感器节点，预计空投后完好的传感器将足以监视目标区域，这称为非固定配置或随机配置。如果可以选择分发站点，则肯定如何配置传感器。否则，该配置为随机配置。3.6.1基于复盖理论，23，课件作者：Xie xiren，在上述两种配置中，部署的传感器集合都希望彼此通信，或者直接或间接通过多跳通信。因此，通常配置的传感器集合除了复盖检测到的区域或点集外，还形成相互连接的网络。对于连接特性，必须知道传感器的通信半径，该连接复盖的充分必要条件满足清理1。清理1:如果传感器的密度(即单位区域中传感器的数量)有限，则这是包括连接性的充分必要条件。基于3.6.1覆盖理论，2