第第3 3章章WSN 拓扑控制与覆盖技术掌握WSN拓扑结构的分类了解WSN拓扑控制了解WSN功率控制掌握层次性拓扑结构控制方法了解启发机制了解覆盖理论基础了解传感器网络的覆盖控制3.13.1网络拓扑结构网络拓扑结构无线传感器网络的网络拓扑结构是组织无线传感器节点的组网技术，有多种形态和组网方式。按照其组网形态和方式分，有集中式、分布式和混合式。无线传感器网络的集中式结构类似移动通信的蜂窝结构，集中管理；无线传感器网络的分布式结构，类似Ad Hoc网络结构，可自组织网络接入连接，分布管理；无线传感器网络的混合式结构包括集中式和分布式结构的组合。按照节点功能及结构层次分，无线传感器网络通常可分为平面网络结构、分级网络结构、混合网络结构，以及Mesh网络结构3.1.1平面网络结构平面网络结构如图3-1所示，平面网络结构是无线传感器网络中最简单的一种拓扑结构，具有如下特点：（1）所有节点为对等结构；（2）这种网络拓扑结构简单，易维护，具有较好的健壮性，（3）由于没有中心管理节点3.1.2 3.1.2 分级网络结构分级网络结构 如图如图3-23-2是分级网络结构是分级网络结构( (也叫层次网络结构也叫层次网络结构) )： 特点：网络分为上层和下层两个部分，上层为中心骨干节点，下层为特点：网络分为上层和下层两个部分，上层为中心骨干节点，下层为一般传感器节点。一般传感器节点。 3.1.3 3.1.3 混合网络结构混合网络结构 如图如图3-33-3是混合网络结构：是混合网络结构： 特点是：特点是： 1 1，网络骨干节点之间及一般传感器节点之间都采用平面网络结构；，网络骨干节点之间及一般传感器节点之间都采用平面网络结构； 2 2，网络骨干节点和一般传感器节点之间采用分级网络结构。，网络骨干节点和一般传感器节点之间采用分级网络结构。 3.1.4 Mesh3.1.4 Mesh网络结构网络结构 从结构来看，从结构来看，MeshMesh网络是规则分布的网络。网络是规则分布的网络。 如图如图3-43-4所示，通常只允许和节点最近的邻居通信；所示，通常只允许和节点最近的邻居通信； 如图如图3-53-5所示，网络内部的节点一般都是相同，因此所示，网络内部的节点一般都是相同，因此MeshMesh网络也称为对等网。网络也称为对等网。 MeshMesh网络结构最大的优点：网络结构最大的优点：是尽管所有节点都是对等的地位，且具有是尽管所有节点都是对等的地位，且具有相同的计算和通信传输功能。相同的计算和通信传输功能。 如图如图3-63-6所示，采用分级网络结构技术可使所示，采用分级网络结构技术可使MeshMesh网络路由设计要简单得多，由网络路由设计要简单得多，由于一些数据处理可以在每个分级的层次里面完成，因而比较适合于无线传感于一些数据处理可以在每个分级的层次里面完成，因而比较适合于无线传感器网络的分布式信号处埋和决策。器网络的分布式信号处埋和决策。3.1.4 Mesh3.1.4 Mesh网络结构网络结构从技术上来看，基于从技术上来看，基于MeshMesh网络结构的无线传感器具有以下网络结构的无线传感器具有以下特点特点。(1)(1)由无线节点构成网络：这种类型的网络节点是由一个传感器或执行器构成且由无线节点构成网络：这种类型的网络节点是由一个传感器或执行器构成且连接到一个双向无线收发器上；连接到一个双向无线收发器上；(2)(2)节点按照节点按照MeshMesh拓扑结构部署，网内每个节点至少可以和一个其它节点通信；拓扑结构部署，网内每个节点至少可以和一个其它节点通信；(3)(3)支持多跳路由：支持多跳路由：(4)(4)功耗限制和移动性取决于节点类型及应用的特点。功耗限制和移动性取决于节点类型及应用的特点。(5)(5)存在多种网络接入方式，可以通过星型、存在多种网络接入方式，可以通过星型、MeshMesh等节点方式和其它网络集成。等节点方式和其它网络集成。3.1.4 Mesh3.1.4 Mesh网络结构网络结构3.2拓扑控制拓扑控制3.2.1概述概述 拓扑控制技术是无线传感器网络中的基本问题。动态变化的拓扑结构是无线传感器网络最大特点之一，因此拓扑控制策略在无线传感器网络中有着重要的意义，它为路由协议、MAC协议、数据融合、时间同步和目标定位等很多方面奠定了基础。 MAC层可以提供给拓扑控制算法邻居发现等消息，如图3-7所示。3.2.2拓扑控制的意义拓扑控制的意义研究具有十分重要的意义，主要表现在以下五个方面：(1)网络寿命，(2)减少节点通信负载，提高通信效率，(3)辅助路由协议，(4)数据融合策略选择，(5)节点冗余3.2.3拓扑控制设计目标n拓扑控制中一般要考虑的设计目标有如下几个方面。n1.覆盖n2.连通n3.网络生命期n4.吞吐能力n5.干扰和竞争n6.网络延迟n7.拓扑性质3.3功率控制n传感器网络中节点发射功率的控制也称功率分配问题。n1.基于节点度的功率控制n2.基于方向的功率控制n3.基于邻近图的功率控制n 4. XTC算法3.4 层次性拓扑结构控制方法n层次型拓扑结构具有很多优点，例如，由簇头节点担负数据融合的任务，减少了数据通信量；分簇式的拓扑结构有利于分布式算法的应用，适合大规模部署的网络；由于大部分节点在相当长的时间内关闭通信模块，所以显著地延长整个网络的生存时间等。n1. LEACH算法 2. GAT算法nGAT算法是一种依据节点的地理位置进行分簇，并对簇内的节点选择性的进行休眠的路由算法。其核心思想是：在各数据源到数据目的地之问存在有效通路的前提下，尽量减少参与数据传输的节点数，从而减少用于数据包侦听和接收的能量开销。它将无线传感器网络划分成若干个单元格(簇)，各单元格内任意一个节点都可以被选为代表，代替本单元格内所有其他节点完成数据包向相邻单元格的转发。被选中的节点成为本单元格的簇头节点；其他节点都进行休眠，不发送、接收和侦听数据包。n GAT算法通常分为虚拟单元格的划分和虚拟单元格中簇头节点的选择两个阶段。n(1)虚拟单元格的划分。n(2)虚拟单元格中的簇头节点的选择。3.5启发机制n在传感器网络的拓扑控制算法中，除了传统的功率控制和层次型拓扑控制两个方面之外，也提出了启发式的节点唤醒和休眠机制。该机制能够使节点在没有事件发生时设置通信模块为睡眠状态，而在有事件发生时及时自动醒来并唤醒邻居节点，形成数据转发的拓扑结构。n1. STEM算法nSTEM(sparse Topology and Energy Management)算法是一种低占空比的节点唤醒机制。该算法采用双信道，即监听信道和数据通信信道。具体地讲，STEM算法又分为STEM-B(STEM-BEACON)算法和STEM-T(STEM-TONE)算法。n在STEM-B算法中，当一个节点想给另外一个节点发送数据时，它作为主动节点先发送一串唤醒包。目标节点在收到唤醒包后，发送应答信号并自动进入数据接收状态。主动节点接收到应答信号后，进入数据发送阶段。n 在STEM-T算法中，节点周期性地进入侦听阶段，探测是否有邻居节点要发送数据；当一个节点想与某个邻居节点进行通信时，它就发送一连串的唤醒包，发送唤醒包的时间长度必须大于侦听的时间间隔，可以确保邻居节点能够收到唤醒包，紧接着节点就直接发送数据包。所以STEM-T比STEM-B更简单实用。nSTEM算法适用于类似环境监测或者突发事件监测等应用，经实验证明，节点唤醒速度可以满足应用的需要。但是在STEM算法中，节点的睡眠周期、部署密度以及网络的传输延迟之间有着密切的关系，要针对具体的应用要求进行调整。2. ASCENT算法n运行ASCENT算法的网络包括触发、建立和稳定三个主要阶段。触发阶段如图3-12(a)所示，在汇聚节点与数据源节点不能正常通信时，汇聚节点向它的邻居节点发出求助信息；建立阶段如图3-12(b)所示，当节点收到邻居节点的求助消息时，通过一定的算法决定自己是否成为活动节点，如果成为活动节点，就向邻居节点发送通告消息，同时这个消息是邻居节点判断自身是否成为活动节点的因素之一；稳定阶段如图3-12(c)所示，数据源节点和汇聚节点间的通信恢复正常，网络中活动节点个数保持稳定，从而达到稳定状态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覆盖理论基础 另外一个与无线传感器网络覆盖相关的几何问题是圆覆盖问题，即在一个平面上最多需要排列多少个相同大小的圆，才使其能够完全覆盖整个平面。换个角度说，也就是给定了圆的数目，如何使得圆的半径最小。AHeppes和JBMMelissen实现了矩形平面的圆最优覆盖问题，分为最多用5个圆和7个圆来完成覆盖两种情况。如图3-8所示给出了一个7个圆最优覆盖的一个例子。 图3-8用7个圆实现最优覆盖的样例3.6.1覆盖理论基础无线传感器网络的覆盖问题在本质上和上面的几何计算问题是一致的：需要知道是否某个特定的区域被充分覆盖和完全处于监视之下。就成本而言，配置的传感器节点的数量是非常重要的。在典型的无线传感器网络应用当中，放置或配置一些传感器节点来监视一个区域或点集。3.6.1覆盖理论基础 确定性配置和非确定性的配置(随机配置)1.一些应用中可以选择传感器配置场地，如定点部署和配置，这种方式称为确定性配置；2.而另外一些应用(如敌方区域或非常恶劣等人员不能到达的环境)，只能通过随机部署(如空投撒播方式)足够多的传感器节点到监视区域，希望空投后未遭破坏的传感器足以监视目标区域，这种方式称为非确定性的配置或随机配置。如果可以选取部署场地，可采用确定性的传感器配置方法；否则，该配置就是随机配置。3.6.1覆盖理论基础 在上面两种配置情况下，都希望部署的传感器集合能够彼此通信，或者直接或者间接通过多跳方式通信。 因此，除了要覆盖感应的区域或点集外，通常需要配置的传感器集合能够形成一个互联的网络。就连接特性而言，需要知道传感器的通信半径，其连接覆盖的充分必要条件，满足定理1。定理1：当传感器的密度(即单位区域的传感器数目)为有限时，是覆盖包含连接性的充分必要条件。3.6.1覆盖理论基础 X.Wang等人也证明了在 k 阶覆盖(每个点至少被 k 个传感器覆盖)和 k 阶连接性(配置传感器的通信图是k阶连接的)情况下的一个类似的结论，满足定理2。 定理2：当，一个凸区域的 k 阶覆盖必定包含了k 阶连接性。 注意到kl的k阶覆盖提供了一定的容错度，能够监视所有的点，只要不多于k-1个传感器故障或失效。凸区域:就是凸的区域。凸从几何上看就是图形是往外凸的，没有凹进去的地方。代数上是这样定义的：集合中任取两个点a，b，有t*a+(1t)*b仍属于这个集合，其中0t1。这个表达式的意思就是连接两个点a b的直线段还在集合中。这是凸的意思。区域就是连通的开集，也可以等价的说是道路连通的开集。所谓道路连通也很好理解，就是集合中的任意两个点有一条道路连接它们。3.6.1覆盖理论基础与覆盖问题直接相关的是传感器节点的感知模型。目前，无线传感器网络主要有两种基本感知模型。1布尔感知模型 2概率感知模型3.6.2覆盖感知模型3.6.3覆盖算法分类n1节点部署方式分类n 按照无线传感器网络节点的不同配置方式(即节点是否需要知道自身位置信息)，可以将无线传感器网络的覆盖算法分为确定性覆盖、随机覆盖两大类。n (1)确定性覆盖n (2)随机覆盖n2覆盖目标分类n 根据无线传感器网络不同的应用，覆盖需求通常不同。根据覆盖目标不同，目前覆盖算法可以分为面覆盖、点覆盖及栅栏覆盖。n (1)面覆盖n (2)点覆盖n (3)栅栏覆盖3.6.4典型覆盖算法n1基于网格的覆盖定位传感器配置算法n2圆周覆盖3.6.4典型覆盖算法3连通传感器覆盖 4轮换活跃/休眠节点的Self-Scheduling覆盖协议3.6.4典型覆盖算法5最坏与最佳情况覆盖6暴露穿越覆盖3.6.5覆盖能效评价指标1 1无线传感网络的覆盖指标无线传感网络的覆盖指标由于无线传感器网络中节点布置的固有冗余性，网络覆盖评价采用了可靠由于无线传感器网络中节点布置的固有冗余性，网络覆盖评价采用了可靠度的概念。对一定区域，若在度的概念。对一定区域，若在t t时刻处于时刻处于n n个节点测量范围内，该区域综合个节点测量范围内，该区域综合可靠度可靠度表示为表示为 (2-4)(2-4) 式中，式中，r ri (i (t t) )表示第表示第i i个节点的测量可靠度。个节点的测量可靠度。 待测区域中待测区域中所有综合可靠度所有综合可靠度大于测量可靠性要求的区域称为大于测量可靠性要求的区域称为有效测量区域有效测量区域。用用解析方法计算解析方法计算随机布置无线传感网络的有效测量区域非常复杂，因此采用随机布置无线传感网络的有效测量区域非常复杂，因此采用数值数值计算方法计算方法，将待测区域网格化，单元格简化为点，计算各点的综合可靠度，统计，将待测区域网格化，单元格简化为点，计算各点的综合可靠度，统计满足测量可靠度要求的单元格面积，得到有效测量区域面积数值解。将有效测量满足测量可靠度要求的单元格面积，得到有效测量区域面积数值解。将有效测量区域面积占待测总面积的比例定义为覆盖指标区域面积占待测总面积的比例定义为覆盖指标C C。2无线传感器网络的能耗指标n无线信号在传播过程中随着无线信号在传播过程中随着传播距离增加而发生衰减传播距离增加而发生衰减，采用自由空间模，采用自由空间模型型计算传播损耗计算传播损耗如下：如下： (2-5)(2-5) 式中，式中，L Lp p为路径损耗；为路径损耗；D D为传播距离；为信号波长。为传播距离；为信号波长。n针对无线信号传播过程，假设无线传感器网络通信能耗模型为：运行发针对无线信号传播过程，假设无线传感器网络通信能耗模型为：运行发送器或接收器的无线花费为送器或接收器的无线花费为E Eelec=50nJ/bitelec=50nJ/bit，发送放大器实现容许放大，发送放大器实现容许放大倍率的无线花费为倍率的无线花费为E Eamp=100pJ/bit mamp=100pJ/bit m-2-2。n二维空间内，坐标分别为二维空间内，坐标分别为( (x xi i，y yi i) )、( (x xj j，y yj j) )的无线传感节点的无线传感节点i i、j j，通信，通信时信号时信号传播距离传播距离计算如下：计算如下： (2-6) (2-6) n若节点若节点i i向向j j发送发送长度为长度为k k bit bit的数据包，则的数据包，则节点节点i i能耗能耗为：为： (2-7)(2-7)n节点节点j j接收接收此数据包的能耗为：此数据包的能耗为： (2-8)(2-8)n 节点节点i i与与j j节点，进行一次数据包传输所消耗的节点，进行一次数据包传输所消耗的总能量总能量为：为： (2-(2-9)9) 式式(2-9)(2-9)说明说明两节点相距较远时两节点相距较远时，直接传输数据会，直接传输数据会消耗较大能量消耗较大能量，采用，采用多多跳通信跳通信则可节省能量。则可节省能量。2 2无线传感器网络的能耗指标无线传感器网络的能耗指标移动目标跟踪移动目标跟踪是无线传感网络的重要应用领域之一，针对移动目标是无线传感网络的重要应用领域之一，针对移动目标跟踪的无线传感网络跟踪的无线传感网络覆盖能效覆盖能效问题更具实用价值，也更富有挑战性。通问题更具实用价值，也更富有挑战性。通常无线传感节点对进入网络的移动目标进行测量，并将收集到的目标信常无线传感节点对进入网络的移动目标进行测量，并将收集到的目标信息传达给位于网络中央的中心节点。为了尽可能降低通信耗能，各节点息传达给位于网络中央的中心节点。为了尽可能降低通信耗能，各节点均需采用能耗最低的均需采用能耗最低的路径向中心节点传送数据路径向中心节点传送数据。2无线传感器网络的能耗指标3.7传感器网络的覆盖控制n1.基于虚拟势场力的传感器网络区域覆盖控制3.7传感器网络的覆盖控制2.基于市场竞争行为的无线传感器网络连接与覆盖算法作业n查阅拓扑控制技术的相关资料。