第3章WSN拓扑结构、覆盖技术资料课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,课件制作人：谢希仁,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计算机网络,课件 制作人：谢希仁,*,第,3,章,WSN,拓扑控制与覆盖技术,掌握,WSN,拓扑结构的分类,了解,WSN,拓扑控制,了解,WSN,功率控制,掌握层次性拓扑结构控制方法,了解启发机制,了解覆盖理论基础,了解传感器网络的覆盖控制,第3章WSN 拓扑控制与覆盖技术掌握WSN拓扑结构的分,3.1,网络拓扑结构,无线传感器网络的网络拓扑结构是组织无线传感器节点的组网技术，有多种形态和组网方式。,按照,其组网形态和方式,分，有集中式、分布式和混合式。无线传感器网络的,集中式,结构类似移动通信的蜂窝结构，集中管理；无线传感器网络的,分布式结构,，类似,Ad Hoc,网络结构，可自组织网络接入连接，分布管理；无线传感器网络的,混合式结构,包括集中式和分布式结构的组合。,按照,节点功能及结构层次,分，无线传感器网络通常可分为平面网络结构、分级网络结构、混合网络结构，以及,Mesh,网络结构,3.1网络拓扑结构无线传感器网络的网络拓扑结构是组织无,3.1.1,平面网络结构,如图,3-1,所示，平面网络结构是无线传感器网络中最简单的一种拓扑结构，具有如下特点：,（,1,）所有节点为对等结构；,（,2,）这种网络拓扑结构简单，易维护，具有较好的健壮性，,（,3,）由于没有中心管理节点,3.1.1平面网络结构如图3-1所示，平面网络结构是无线传感,3.1.2,分级网络结构,如图,3-2,是分级网络结构,(,也叫层次网络结构,),：,特点：网络分为上层和下层两个部分，上层为中心骨干节点，下层为一般传感器节点。,3.1.2 分级网络结构 如图3-2是分级网络结,3.1.3,混合网络结构,如图,3-3,是混合网络结构：,特点是：,1,，网络骨干节点之间及一般传感器节点之间都采用平面网络结构；,2,，网络骨干节点和一般传感器节点之间采用分级网络结构。,3.1.3 混合网络结构 如图3-3是混合网络结,3.1.4 Mesh,网络结构,从结构来看，,Mesh,网络是规则分布的网络。,如图,3-4,所示，通常只允许和节点最近的邻居通信；,如图,3-5,所示，网络内部的节点一般都是相同，因此,Mesh,网络也称为对等网。,3.1.4 Mesh网络结构 从结构来看，Mesh网络是,Mesh,网络结构最大的优点：,是尽管所有节点都是对等的地位，且具有相同的计算和通信传输功能。,如图,3-6,所示，采用分级网络结构技术可使,Mesh,网络路由设计要简单得多，由于一些数据处理可以在每个分级的层次里面完成，因而比较适合于无线传感器网络的分布式信号处埋和决策。,3.1.4 Mesh,网络结构,Mesh网络结构最大的优点：是尽管所有节点都是对等的地位，,从技术上来看，基于,Mesh,网络结构的无线传感器具有以下,特点,。,(1),由无线节点构成网络：这种类型的网络节点是由一个传感器或执行器构成且连接到一个双向无线收发器上；,(2),节点按照,Mesh,拓扑结构部署，网内每个节点至少可以和一个其它节点通信；,(3),支持多跳路由：,(4),功耗限制和移动性取决于节点类型及应用的特点。,(5),存在多种网络接入方式，可以通过星型、,Mesh,等节点方式和其它网络集成。,3.1.4 Mesh,网络结构,从技术上来看，基于Mesh网络结构的无线传感器具有以下特点。,3.2,拓扑控制,3.2.1,概述,拓扑控制技术是无线传感器网络中的基本问题。动态变化的拓扑结构是无线传感器网络最大特点之一，因此拓扑控制策略在无线传感器网络中有着重要的意义，它为路由协议、,MAC,协议、数据融合、时间同步和目标定位等很多方面奠定了基础。,MAC,层可以提供给拓扑控制算法邻居发现等消息，如图,3-7,所示。,3.2拓扑控制3.2.1概述,3.2.2,拓扑控制的意义,研究具有十分重要的意义，主要表现在以下五个方面：,(1)网络寿命，,(2)减少节点通信负载，提高通信效率，,(3)辅助路由协议，,(4)数据融合策略选择，,(5)节点冗余,3.2.2拓扑控制的意义研究具有十分重要的意义，主要表现在以,3.2.3拓扑控制设计目标,拓扑控制中一般要考虑的设计目标有如下几个方面。,1.覆盖,2.连通,3.网络生命期,4.吞吐能力,5.干扰和竞争,6.网络延迟,7.拓扑性质,3.2.3拓扑控制设计目标拓扑控制中一般要考虑的设计目标有如,3.3功率控制,传感器网络中节点发射功率的控制也称功率分配问题。,1.基于节点度的功率控制,2.基于方向的功率控制,3.基于邻近图的功率控制,4.XTC算法,3.3功率控制传感器网络中节点发射功率的控制也称功率分配问题,3.4 层次性拓扑结构控制方法,层次型拓扑结构具有很多优点，例如，由簇头节点担负数据融合的任务，减少了数据通信量；分簇式的拓扑结构有利于分布式算法的应用，适合大规模部署的网络；由于大部分节点在相当长的时间内关闭通信模块，所以显著地延长整个网络的生存时间等。,1.LEACH算法,3.4 层次性拓扑结构控制方法层次型拓扑结构具有很多优点，例,2.GAT算法,GAT算法是一种依据节点的地理位置进行分簇，并对簇内的节点选择性的进行休眠的路由算法。其核心思想是：在各数据源到数据目的地之问存在有效通路的前提下，尽量减少参与数据传输的节点数，从而减少用于数据包侦听和接收的能量开销。它将无线传感器网络划分成若干个单元格(簇)，各单元格内任意一个节点都可以被选为代表，代替本单元格内所有其他节点完成数据包向相邻单元格的转发。被选中的节点成为本单元格的簇头节点；其他节点都进行休眠，不发送、接收和侦听数据包。,GAT算法通常分为虚拟单元格的划分和虚拟单元格中簇头节点的选择两个阶段。,(1)虚拟单元格的划分。,(2)虚拟单元格中的簇头节点的选择。,2.GAT算法GAT算法是一种依据节点的地理位置进行分,3.5启发机制,在传感器网络的拓扑控制算法中，除了传统的功率控制和层次型拓扑控制两个方面之外，也提出了启发式的节点唤醒和休眠机制。该机制能够使节点在没有事件发生时设置通信模块为睡眠状态，而在有事件发生时及时自动醒来并唤醒邻居节点，形成数据转发的拓扑结构。,1.STEM算法,STEM(sparse Topology and Energy Management)算法是一种低占空比的节点唤醒机制。该算法采用双信道，即监听信道和数据通信信道。具体地讲，STEM算法又分为STEM-B(STEM-BEACON)算法和STEM-T(STEM-TONE)算法。,在STEM-B算法中，当一个节点想给另外一个节点发送数据时，它作为主动节点先发送一串唤醒包。目标节点在收到唤醒包后，发送应答信号并自动进入数据接收状态。主动节点接收到应答信号后，进入数据发送阶段。,在STEM-T算法中，节点周期性地进入侦听阶段，探测是否有邻居节点要发送数据；当一个节点想与某个邻居节点进行通信时，它就发送一连串的唤醒包，发送唤醒包的时间长度必须大于侦听的时间间隔，可以确保邻居节点能够收到唤醒包，紧接着节点就直接发送数据包。所以STEM-T比STEM-B更简单实用。,STEM算法适用于类似环境监测或者突发事件监测等应用，经实验证明，节点唤醒速度可以满足应用的需要。但是在STEM算法中，节点的睡眠周期、部署密度以及网络的传输延迟之间有着密切的关系，要针对具体的应用要求进行调整。,3.5启发机制在传感器网络的拓扑控制算法中，除了传统的功率控,2.ASCENT算法,运行,ASCENT算法的网络包括触发、建立和稳定三个主要阶段。触发阶段如图3-12(a)所示，在汇聚节点与数据源节点不能正常通信时，汇聚节点向它的邻居节点发出求助信息；建立阶段如图3-12(b)所示，当节点收到邻居节点的求助消息时，通过一定的算法决定自己是否成为活动节点，如果成为活动节点，就向邻居节点发送通告消息，同时这个消息是邻居节点判断自身是否成为活动节点的因素之一；稳定阶段如图3-12(c)所示，数据源节点和汇聚节点间的通信恢复正常，网络中活动节点个数保持稳定，从而达到稳定状态,2.ASCENT算法运行ASCENT算法的网络包括触发、建,3.,6,覆盖,3.6.1覆盖理论基础,覆盖问题是无线传感器网络配置首先面临的基本问题，因为传感器节点可能任意分布在配置区域，它反映了一个无线传感器网络某区域被监测和跟踪的状况。,在现有的研究成果当中，很多都是致力于解决传感器网络的部署和监测及覆盖与连接的关系等方面问题。另外，也有一些研究致力于特定的应用需求，但其核心思想都是与覆盖问题有关的。,3.6 覆盖3.6.1覆盖理论基础,无线传感器网络覆盖相关的两个计算几何问题,(,三角形、圆,),。,第一个就是艺术馆问题,(Art Gallery Problem),。设想艺术馆的业主想在馆内放置照相机，以便能够预防小偷盗窃。关于实现这个想法存在两个问题需要回答：首先就是到底需要,多少台相机,；其次，这些相机应当放置在,哪些地方,才能保证馆内每个点至少被一台相机监视到。假定相机可以有,的视角而且可以极大速度旋转，相机可以监视任何位置，视线不受影响。,3.6.1覆盖理论基础,无线传感器网络覆盖相关的两个计算几何问题,(三角,问题优化要实现的目标就是,所需相机的数目应该最小化,，在这个问题当中，艺术馆通常建模成一个二维平面的简单,多边形,。一个简单的解决办法就是将多边形分成不重叠的,三角形,，每个三角形里面放置一个相机。通过,三角测量法,将多边形分成若干个三角形，这样可以实现任何一个多边形都可被 个相机所监视到，这里,n,表示多边形所包含的三角形的数目。这也是最糟糕情况下的最佳结果。,3.6.1覆盖理论基础,问题优化要实现的目标就是所需相机的数目应该最小化，在这个,如图,3-7,所示是将一个简单多边形用,三角测量法拆分,的例子，放置两个监视相机足以覆盖整个艺术馆。尽管这个问题在二维平面可以得到,最优解,，然而扩展到三维空间，这个问题就变成了,NP-hard,问题了。,图,3-7,多边形的三角测量法及监视相机的位置配置,NP-hard,问题,:,NP,是指非确定性多项式（,non-deterministic polynomial,，缩写,NP,）。所谓的非确定性是指，可用一定数量的运算去解决,多项式时间,内可解决的问题。,NP,问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。相应的，若,NP,中所有问题到某一个问题是,图灵,可归约的，则该问题为,NP,困难问题,3.6.1覆盖理论基础,如图3-7所示是将一个简单多边形用三角测量法拆分的例子，,另外一个与无线传感器网络覆盖相关的几何问题是,圆覆盖问题,，即在一个平面上最多需要排列多少个相同大小的圆，才使其能够完全覆盖整个平面。换个角度说，也就是给定了圆的数目，如何使得圆的半径最小。,A,Heppes,和,J,B,M,Melissen,实现了矩形平面的圆最优覆盖问题，分为最多用,5,个圆和,7,个圆,来完成覆盖两种情况。如图,3-8,所示给出了一个,7,个圆最优覆盖的一个例子。,图,3-8,用,7,个圆实现最优覆盖的样例,3.6.1覆盖理论基础,另外一个与无线传感器网络覆盖相关的几何问题是,无线传感器网络的,覆盖问题,在本质上和上面的,几何计算问题,是一致的：需要知道是否某个特定的,区域被充分覆盖和完全处于监视,之下。就成本而言，配置的传感器节点的,数量,是非常重要的。在典型的无线传感器网络应用当中，,放置或配置,一些传感器节点来监视一个区域或点集。,3.6.1覆盖理论基础,无线传感器网络的覆盖问题在本质上和上面的几何计算问题是一,确定性配置和,非确定性的配置,(,随机配置,),1.,一些应用中可以选择传感器配置场地，如,定点,部署和配置，这种方式称为,确定性配置,；,2.,而另外一些应用,(,如