第章拓扑控制课件

第2章 拓扑控制 第2章 拓扑控制 2.1 概述概述 2.2 功率控制功率控制 2.3 层次型拓扑次型拓扑结构控制构控制 2.4 启启发机制机制 2.5 传感器网感器网络的覆盖控制的覆盖控制 2.6 小小结 第2章 拓扑控制 2.1 概概 述述在无线传感器网络中，传感器节点在最大通信半径下的网络连接关系称为“物理拓扑”。在传感器节点被抛撒后，网络的物理拓扑就是固定的。在满足网络覆盖率和连通性的前提下，通过信息交互、功率控制等手段，剔除物理拓扑中节点间不必要的物理通信链路，建立逻辑链路后形成的网络连接关系，我们称为“逻辑拓扑”。由物理拓扑生成逻辑拓扑的过程，称为无线传感器网络的“拓扑控制”。第2章 拓扑控制 无线传感器节点是体积微小的嵌入式设备，由能量有限的电池供电，其处理能力、存储能力和通信能力相对较弱。除了设计能量高效的链路层协议、路由协议和应用层协议外，还要设计优化的网络拓扑控制机制。由于传感器节点数量众多、成本要求低廉、分布区域广泛，而且部署区域环境复杂，有些区域甚至人员不能到达，因此为传感器节点补充能源是很困难的。如何高效地使用能量、使网络生存周期最大化是传感器网络面临的首要挑战。传感器网络拓扑控制目前主要的研究问题是在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节点选择，剔除节点之间不必要的无线通信链路，生成一个高效的数据转发的网络拓扑结构。第2章 拓扑控制 对于自组织的无线传感器网络而言，拓扑控制对网络的性能影响非常大。良好的逻辑拓扑结构能够提高路由协议和MAC协议的效率，为数据融合、时间同步和目标定位等很多方面奠定基础，有利于节省节点的能量来延长整个网络的生存时间。所以，拓扑控制是传感器网络中的一个基本问题，同时也是研究的核心问题之一，因而对它的研究具有十分重要的意义，主要表现在以下几个方面：(1)延长网络寿命。传感器节点一般采用电池供电，能耗是网络设计中需要考虑的最主要的因素之一，而拓扑控制的一个重要目标就是在保证网络连通性和覆盖率的条件下，尽量降低网络能耗，延长网络生存周期。第2章 拓扑控制(2)减少节点通信负载，提高通信效率。传感器节点的分布密度一般较大，通过拓扑控制技术中的功率控制技术，可以选择节点的发射功率，合理调节节点的通信范围，使得节点在连通性和网络通信范围之间取得一个平衡点。(3)辅助路由协议。在无线传感器网络中，只有活动的节点才能进行数据转发，而拓扑控制可以确定由哪些节点作为转发节点，同时确定节点之间的邻居关系。(4)选择数据融合策略。无线传感网络中，为了减少通信负载，通常选择一些节点先对周围节点的数据进行融合，再进行转发，而在拓扑控制中，将就如何合理、高效地选择融合节点这一问题进行研究。第2章 拓扑控制(5)采用冗余节点。由于传感器节点本身所固有的脆弱性，不能保证节点一直持续正常的工作，所以在设计时需要采用冗余技术对网络进行拓扑控制，以保证网络的覆盖率和连通度。拓扑控制研究的问题是：在保证一定的网络连通质量和覆盖质量的前提下，一般以延长网络的生命期为主要目标，通过功率控制和骨干网节点选择，剔除节点之间不必要的通信链路，兼顾通信干扰、网络延迟、负载均衡、简单性、可靠性、可扩展性等其他性能，形成一个数据转发的优化网络拓扑结构。传感器网络用来感知客观物理世界，获取物理世界的信息。客观世界的物理量多种多样，不可穷尽，不同的第2章 拓扑控制 传感器网络应用关心不同的物理量，不同的应用背景对传感器网络的要求也不同，它的硬件平台、软件系统和网络协议必然会有很大差别。不同的应用对底层网络的拓扑控制设计目标的要求也不尽相同。下面介绍拓扑控制中一般要考虑的设计目标。(1)覆盖。覆盖是对传感器网络服务质量的度量，即在保证一定的服务质量的条件下，使得网络覆盖范围最大化，提供可靠的区域监测和目标跟踪服务。根据传感器节点是否具有移动能力，WSN覆盖可分为静态网络覆盖和动态网络覆盖两种形式。Voronoi图是常用的覆盖分析工具。动态网络覆盖利用节点的移动能力，在初始随机部署后，根据网络覆盖的要求实现节点的重部署。静态网络覆盖将在后面具体介绍，其中虚拟势场方法是一种重要的部署方法。第2章 拓扑控制(2)连通。传感器网络的规模一般很大，所以传感器节点感知到的数据一般要以多跳的方式传送到汇聚节点，这就要求拓扑控制必须保证网络的连通性。有些应用可能要求网络配置达到指定的连通度，有时也讨论渐近意义下的连通，即当部署的区域趋于无穷大时，网络连通的可能性趋于1。(3)网络生命期。一般将网络生命期定义为直到死亡节点的百分比低于某个阈值时的持续时间，也可以通过对网络的服务质量的度量来定义网络的生命期，我们可以认为网络只有在满足一定的覆盖质量、连通质量、某个或某些其他服务质量时才是存活的。最大限度地延长网络的生命期是一个十分复杂的问题，它一直是拓扑控制研究的主要目标。第2章 拓扑控制(4)吞吐能力。设目标区域是一个凸区域，每个节点的吞吐率为b/s，在理想情况下，则有下面的关系式：其中，A是目标区域的面积，W是节点的最高传输速率，是圆周率，是大于0的常数，L是源节点到目的节点的平均距离，n是节点数，r是理想球状无线电发射模型的发射半径。由上式可知，通过功率控制减小发射半径和通过休眠调度减小工作网络的规模，可以在节省能量的同时，在一定程度上提高网络的吞吐能力。(2-1)第2章 拓扑控制(5)干扰和竞争。减小通信干扰、减少MAC层的竞争和延长网络的生命期，这三者的意义基本是一致的。对于功率控制而言，网络无线信道竞争区域的大小与节点的发射半径r成正比，所以减小r就可以减少竞争；对于休眠调度而言，可以使尽可能多的节点处于休眠状态，减小干扰和减少竞争。(6)网络延迟。网络延迟和功率控制之间的大致关系是当网络负载较小时，由于高发射功率减少了源节点到目的节点的跳数，因此降低了端到端的延迟；当网络负载较大时，节点对信道的竞争是激烈的，低发射功率由于缓解了竞争而减小了网络延迟。第2章 拓扑控制(7)拓扑性质。对于网络拓扑的优劣，很难给出定量的度量。因此，在设计拓扑控制策略时，往往只是使网络具有一些良好的拓扑性质。除了覆盖性、连通性之外，对称性、平面性、稀疏性、节点度的有界性、有限伸展性等，也都是希望网络具有的性质。除此之外，拓扑控制还要考虑负载均衡、简单性、可靠性、可扩展性等其他方面的性质。第2章 拓扑控制 2.2 功功 率率 控控 制制传感器网络中，节点发射功率的控制也称功率分配问题。节点通过设置或动态调整节点的发射功率，在保证网络拓扑结构连通、双向连通或者多连通的基础上，使得网络中节点的能量消耗最小，从而延长整个网络的生存时间。当传感器节点部署在二维或三维空间中时，传感器网络的功率控制是一个极难的问题。因此，试图寻找功率控制问题的最优解是不现实的，应该从实际出发，寻找功率控制问题的实用解。针对这一问题，当前学术界已经提出了一些解决方案，其基本思想都是通过降低发射功率来延长网络的生命期。第2章 拓扑控制 2.2.1 基于基于节点度的功率控制点度的功率控制基于节点度的算法是传感器网络拓扑控制中功率控制方面的问题。一个节点的度数是指所有距离该节点一跳的邻居节点的数目。基于节点度算法的核心思想是给定节点度的上限和下限需求，动态调整节点的发射功率，使得节点的度数落在上限和下限之间。基于节点度的算法利用局部信息来调整相邻节点间的连通性，从而保证整个网络的连通性，同时保证节点间的链路具有一定的冗余性和可扩展性。本地平均算法(Local Mean Algorithm，LMA)和本地邻居平均算法(Local Mean of Neighbors algorithm，LMN)是两种周期性动态调整节点发射功率的算法，它们之间的区别在于计算节点度的策略不同。第2章 拓扑控制 2.2.2 基于方向的功率控制基于方向的功率控制微软亚洲研究院的Wattenhofer和康奈尔大学的Li等人提出了一种能够保证网络连通性的基于方向的CBTC算法。其基本思想是：节点选择最小功率Pu,，使得在任何以u为中心且角度为的锥形区域内至少有一个邻居。而且，当5/6时，可以保证网络的连通性。麻省理工学院的Bahramgiri等人又将其推广到三维空间，提出了容错的CBTC算法。基于方向的功率控制算法需要可靠的方向信息，因而需要很好地解决到达角度问题，另外节点需要配备多个有向天线，因此对传感器节点提出了较高的要求。第2章 拓扑控制 2.2.3 基于基于邻近近图的功率控制的功率控制伊利诺斯大学的Li和Hou提出的DRNG(Directed Relative Neighborhood Graph)和DLMST(Directed Local Minimum Spanning Tree)是两个具有代表性的基于临近图理论的功率控制算法。基于临近图的功率控制算法的基本思想是，设所有节点都使用最大发射功率发射时形成拓扑图G，按照一定的邻居判别条件q求出该图的临近图G，G中的每个节点以与自己所临近的、最远的通信节点来确定发射功率。这是一种解决功率分配问题的近似解法，考虑到由于无线传感器网络中两个节点形成的边是有向的，为了避免形成单向边，一般在运用基于临近图的功率控制算法形成网络拓扑以后，第2章 拓扑控制 还需要进行节点之间边的增删，以使最后得到的网络拓扑是双向连通的。在无线传感器网络中，基于临近图功率控制算法的作用是使节点确定自己的邻居集合，调整适当的发射功率，从而在建立一个连通网络的同时使得能量消耗最低。经典的临近图模型有RNG(Relative Neighborhood Graph)、GG(Gabriel Graph)、DG(Delaunay Graph)、YG(Yao Graph)和MST(Minimum Spanning Tree)等。DRNG是基于有向RNG的，DLMST是基于有向局部MST的。DRNG和DLMST能够保证网络的连通性，在平均功率和节点度等方面具有较好的性能。基于临近图的功率控制一般需要精确的位置信息。下面简单介绍DRNG算法和DLSS(Directed Local Spanning Subgraph)算法。第2章 拓扑控制 DRNG算法和DLSS算法是两种从临近图观点考虑拓扑问题的算法，是一种较早提出的功率控制算法，两者均以经典的临近图RNG和LMST等理论为基础，全面考虑了连通性和双向连通性问题。首先有如下定义：(1)边有向，即(u,v)和(v,u)是两组不同的边；(2)d(u,v)表示节点u和v间的距离，ru表示节点u的通信半径。可达邻居为u以最大发射半径可以到达的节点集合，由节点u和以及这些节点之间的边构成了可达邻居子图。第2章 拓扑控制 由节点u和节点v构成边的权重函数满足如下关系：第2章 拓扑控制 在DRNG算法和DLSS算法中，节点都需要知道其他一些节点的必要信息，因此需要一个信息收集阶段：每个节点以最大的发射功率广播“HELLO”消息，该消息至少包括自身的身份标识号(ID)和自身位置，然后，节点通过收到的“HELLO”消息确定自己可以达到的邻居集合。在DRNG算法中，没有明确的步骤，只给出确定邻居节点的条件，如图2-1所示，如果节点u和v满足ru，而且不存在另外其他节点p同时满足、和rp时，节点v则被选为节点u的邻居节点，所以，DRNG算法为节点u确定了邻居集合。第2章 拓扑控制 在DLSS算法中，假设节点u及其可达邻居集合，将p到所有可达邻居节点的边以权重为标准按升序排列；依次取出这些边，直到u与所有可达邻居节点相连通或者通过其他节点连通；最后，与u直接连通的节点构成u的邻居集合。从图论的观点看，DLSS算法等价于基础上的本地最小生成树的计算。经过DRNG或DLSS算法后，节点u确定了自己的邻居集合，然后将发射半径调整为最远邻居节点的距离，进一步通过对拓扑图的边进行增删，使得网络达到双向连通。第2章 拓扑控制 图2-1 DRNG算法 第2章 拓扑控制 DRNG算法和DLSS算法着重考虑了网络的连通性，充分利用了邻居图理论，是无线传感器网络中的经典算法，二者以原始网络拓扑双向连通为前提，保证优化后的拓扑也是双向连通的。此外，微软亚洲研究院的Wattenhofer等人提出的XTC算法对传感器节点没有太高的要求，对部署环境也没有过强的假设，因此提供了一个面向简单、实用的研究方向。XTC算法代表了功率控制的发展趋势，下面将详细加以介绍。第2章 拓扑控制 2.2.4 XTC算法算法XTC算法的基本思想是用接收信号的强度作为RNG中的距离度量，XTC算法可分为如下三步。(1)邻居排序：节点u对其所有的邻居计算一个反映链路质量的全序。在中，如果节点在节点的前面，则记为，节点u与越早出现在中的节点之间的链路，其质量越好。(2)信息交换：节点向其邻居广播自己的，同时接收邻居节点建立的。第2章 拓扑控制(3)链路选择：节点按顺序遍历，先考虑好邻居，再考虑坏邻居。对于u的邻居v，如果节点u没有更好的邻居，使得 ，那么u就和v建立一条通信链路。XTC算法不需要位置信息，对传感器节点没有太高的要求，适用于异构网络，也适用于三维网络。与大多数其他算法相比，XTC算法更简单，更实用。但是，XTC算法与实用化要求仍然有一定的距离，例如，XTC算法并没有考虑到通信链路质量的变化。第2章 拓扑控制 2.3 层次型拓扑次型拓扑结构控制构控制在传感器网络中，传感器节点的无线通信模块在空闲状态时的能量消耗与在首发状态时的相当，所以只有关闭节点的通信模块，才能大幅度地降低无线通信模块的能量开销。因此可考虑依据一定的机制选择某些节点作为骨干网节点，打开通信模块，并关闭非骨干节点的通信模块，由骨干节点构建一个联通网络来负责数据的路由转发，这样既保证了原有覆盖范围内的数据通信，也在很大程度上节省了节点能量。在这种拓扑管理机制下，网络中的节点可以划分为骨干网节点和普通节点两类，骨干网节点对周围的普通节点进行管辖。这类算法将整个网络划分为相连的区域，一般又称为分簇第2章 拓扑控制 算法。骨干网节点是簇头节点，普通节点是簇内节点。由于簇头节点需要协调簇内节点的工作，负责数据的融合和转发，能量消耗相对较大，所以分簇算法通常采用周期性地选择簇头节点的做法以均衡网络中节点的能量消耗。层次型拓扑结构具有很多优点，例如，由簇头节点担负数据融合的任务，减少了数据通信量；有利于分布式算法的应用，适合大规模部署的网络；由于大部分节点在相当长的时间内关闭了通信模块，所以显著地延长了整个网络的生存时间等。第2章 拓扑控制 2.3.1 LEACH算法算法LEACH(Low Energy Adaptive Clustering Hierarchy)算法是一种自适应分簇拓扑算法，它的执行过程是周期性的，每轮循环分为簇的建立阶段和稳定的数据通信阶段。在簇的建立阶段，相邻节点动态地形成簇，随机产生簇头；在数据通信阶段，簇内节点把数据发送给簇头，簇头进行数据融合并把结果发送给汇聚节点。由于簇头需要完成数据融合、与汇聚节点通信等工作，所以能量消耗大。LEACH算法能够保证各节点等概率地担任簇头，使得网络中的节点相对均衡地消耗能量。第2章 拓扑控制 LEACH算法选举簇头的过程如下：节点产生01之间的随机数，如果这个数小于阈值T(n)，则发布自己是簇头的消息。在每轮循环中，如果节点已经当选过簇头，则把T(n)设置为0，这样该节点不会再次当选为簇头。对于未当选过簇头的节点，则将以T(n)的概率当选。随着当选过簇头的节点数目增加，剩余节点当选簇头的阈值T(n)随之增大，节点产生小于T(n)的随机数的概率随之增大，所以节点当选簇头的概率增大。当只剩下一个节点未当选时，T(n)=1，表示这个节点一定当选。T(n)可表示为(2-2)第2章 拓扑控制 其中，P是簇头在所有节点中所占的百分比，r是选举轮数，r mod(1/P)代表这一轮循环中当选过簇头节点的个数，G是这一轮循环中未当选过簇头的节点集合。节点当选簇头以后，通过发布消息告知其他节点自己是新簇头。非簇头节点根据自己与簇头之间的距离来选择加入哪个簇，并告知该簇头。当簇头接收到所有的加入信息后，就产生一个TDMA定时消息，并且通知该簇中所有节点。为了避免附近簇的信号干扰，簇头可以决定本簇中所有节点所用的CDMA编码。这个用于当前阶段的CDMA编码连同TDMA定时一起发送。当簇内节点收到这个消息后，它们就会在各自的时间槽内发送数据。经过一段时间的数据传输，簇头节点收齐簇内节点发送的数据后，运行数据融合算法来处理数据，并将结果直接发送给汇聚节点。第2章 拓扑控制 经过一轮选举过程，我们可以看到如图2-2所示的簇的分布，整个网络覆盖区域被划分为五个簇，图中黑色节点代表簇头。可以明显地看出经LEACH算法选举出的簇头的分布并不均匀，这是需要改进的方面。第2章 拓扑控制 图2-2 簇的分布 第2章 拓扑控制 2.3.2 TopDisc算法算法TopDisc(Topology Discovery)算法是基于最小支配集理论的经典算法。它首先由初始节点发出拓扑发现请求，通过广播该消息来确定网络中的骨干节点(distinguished nodes)，并结合这些骨干节点的邻居节点的信息形成网络拓扑的近似拓扑。在这个近似拓扑形成之后，为了减少算法本身引起的网络通信量，只有骨干节点才对初始节点的拓扑发现请求作出相应的反应。为了确定网络中的骨干节点，TopDisc算法采用的是贪婪算法。具体地讲，TopDisc提出了两种类似的方法：三色法和四色法。第2章 拓扑控制 在三色法中，节点可以处于三种不同的状态。在TopDisc算法中，分别用白色、黑色、灰色表示三种节点：(1)白色表示尚未被发现的节点，或者说是没有接收到任何拓扑发现请求的节点；(2)黑色表示骨干节点(簇头节点)，负责相应地拓扑发现请求；(3)灰色表示普通节点，至少被一个标记为黑色的节点覆盖，即黑色节点的邻居节点。在初始阶段，所有节点都被标记为白色，算法由一个初始节点发起，算法结束后所有节点都将被标记为黑色或者灰色(前提假设整个网络拓扑是连通的)。第2章 拓扑控制 TopDisc采用两种启发方法来使得每个新的黑色节点都尽可能多地覆盖还没有被覆盖的节点：一种是节点颜色标记方法；另一种是节点转发拓扑发现请求时，将会故意延时一段时间，延时时间的长度反比于该节点与发送拓扑发现请求到该节点的节点之间的距离。三色法的详细步骤描述如下：(1)初始节点被标记为黑色，并向网络广播拓扑发现请求。(2)当白色节点收到来自黑色节点的拓扑发现请求时，将被标记为灰色，并在延时时间TWB后继续广播拓扑发现请求。TWB反比于它与黑色节点之间的距离。第2章 拓扑控制(3)当白色节点收到来自灰色节点的拓扑发现请求时，将在等待时间TWG后标记为黑色，但如果在等待周期又收到来自黑色节点的拓扑发现请求则先优先标记为灰色；同样，等待时间TWG反比于该白色节点与灰色节点之间的距离。不管节点被标记为灰色还是黑色，都将在完成颜色标记后继续广播拓扑发现请求。(4)所有已经被标记为黑色或者灰色的节点，都将忽略其他节点的拓扑发现请求。第2章 拓扑控制 为了使得每个新的黑色节点都尽可能多地覆盖还没有被覆盖的节点，TopDisc采用了反比于节点之间距离的转发延时机制。其合理性简单地解释为：理想情况下，节点的覆盖范围是半径为无线电发射半径的圆。于是，单个的节点所能覆盖的节点数目正比于其覆盖面积和局部的节点部署密度。对于一个正在转发拓扑发现请求的节点，它所能覆盖的新的节点(还没有被任何节点覆盖)则正比于它的覆盖面积与已经覆盖的面积之差。如图2-3所示，假设节点a是初始节点，根据步骤(1)它被标记为黑色，并广播拓扑发现请求。节点b和节点c收到来自节点a的拓扑发现请求，根据步骤(2)被标记为灰色，并各自等待一段时间后广播拓扑发现请求。第2章 拓扑控制 假设节点b比节点c距离节点a更远，即节点b的等待时间更短，于是节点b先广播拓扑发现请求。节点d和节点e收到来自节点b的拓扑发现请求，根据步骤(3)各自等待一段时间，节点a已经被标记为黑色，根据步骤(4)它会忽略节点b的拓扑发现请求。假设节点d比节点e距离节点b更远，则节点d比节点e更有可能标记为黑色，此处假设节点d和节点e都因为等待周期内没有收到来自黑色节点的拓扑发现请求而标记为黑色。注意，在标记为黑色的两个节点之间存在一个中介节点(图中为节点b)同时被这两个黑色节点覆盖，这归因于三色法的内在性质。第2章 拓扑控制 图2-3 三色法示意图 第2章 拓扑控制 可以看出，三色法所形成的簇之间存在重叠区域。为了增大簇之间的间隔，减少重叠区域，TopDisc算法同时也提出了四色法。顾名思义，节点可以处于四种不同的状态，分别用白色、黑色、灰色和深灰色表示。前三种颜色代表的含义跟三色法相同，增加的深灰色表示节点收到过拓扑发现请求，但不被任何标记为黑色的节点覆盖。与三色法类似，在初始阶段，所有节点都被标记为白色，算法由一个初始节点发起，算法结束后所有节点都将被标记为黑色或者灰色(前提假设整个网络拓扑是连通的，注意最终没有标记为深灰色的节点)。四色法的详细步骤描述如下：第2章 拓扑控制(1)初始节点被标记为黑色，并向网络广播拓扑发现请求。(2)当白色节点收到来自黑色节点的拓扑发现请求时，将被标记为灰色，并在延时时间TWB后继续广播拓扑发现请求。TWB反比于它与黑色节点之间的距离。(3)当白色节点收到来自灰色节点的拓扑发现请求时，将标记为深灰色并继续广播拓扑发现请求，然后等待一段时间(同样与距离成反比)。如果在等待期间收到来自黑色节点的拓扑发现请求，则改变为灰色，否则它自己成为黑色。第2章 拓扑控制(4)当白色节点收到来自深灰色节点的拓扑发现请求时，等待一段时间(同样与距离成反比)。如果在等待期间收到来自黑色节点的拓扑发现请求，则改变为灰色，否则它自己成为黑色。(5)所有已经被标记为黑色或者灰色的节点，都将忽略其他节点的拓扑发现请求。第2章 拓扑控制 如图2-4所示，假设节点a是初始节点，根据步骤(1)它被标记为黑色，并广播拓扑发现请求。节点b收到来自节点a的拓扑发现请求，根据步骤(2)被标记为灰色，并各自等待一段时间后广播拓扑发现请求。节点c和节点e都接收到来自节点b的拓扑发现请求，根据步骤(3)，被标记为深灰色，继续广播拓扑发现请求启动计时器(即等待一段时间)。节点d收到来自节点c的拓扑发现请求，根据步骤(4)等待一段时间，假设这段时间内没有收到来自标记为黑色节点的拓扑发现请求，于是节点d标记为黑色，并广播拓扑发现请求。假设节点c在等待期间收到了节点d的拓扑发现请求，则被标记为灰色。假设节点e在等待期间没有收到任何来自标记为黑色节点的拓扑发现请求，则被标记为黑色。第2章 拓扑控制 图2-4 四色法示意图 第2章 拓扑控制 与三色法相比，四色法形成的簇数目更少，簇与簇之间的重叠区域也更小。但是可能形成一些孤立的标记为黑色的节点(如图2-4中的节点e)，不覆盖任何灰色节点。虽然三色法和四色法所形成的黑色节点数目相当，但四色法中传输的数据量要少一些。TopDisc算法利用图论中的典型算法，提出了一种有效方法来构建网络的近似拓扑，是分簇算法中的经典算法。它是一种只需要利用局部信息、完全分布式的、可扩展的网络拓扑控制算法，不过也存在有待改进的地方，如算法开销偏大，另外没有考虑节点的剩余能量。第2章 拓扑控制 2.3.3 GAT算法算法GAT算法是一种依据节点的地理位置进行分簇，并对簇内的节点选择性地进行休眠的路由算法。其核心思想是：在各数据源到数据目的地之间存在有效通路的前提下，尽量减少参与数据传输的节点数，从而减少用于数据包侦听和接收的能量开销。它将无线传感器网络划分成若干个单元格(簇)，各单元格内任意一个节点都可以被选为代表，代替本单元格内所有其他节点完成数据包向相邻单元格的转发。被选中的节点成为本单元格的簇头节点；其他节点都进行休眠，不发送、接收和侦听数据包。第2章 拓扑控制 GAT算法通常分为两个阶段：第一阶段为虚拟单元格的划分。节点根据其位置信息和通信半径将网络区域划分为若干个虚拟单元格，并保证相邻单元格中的任意两个节点都可以直接通信，假设节点已知整个监测区域的位置信息和本身的位置信息，节点可以通过计算得知自己属于哪个单元格。第二阶段为虚拟单元格中的簇头节点的选择。节点周期性地进入休眠和工作状态。从休眠状态唤醒后与本单元内其他节点进行信息交换，以此确定自己是否需要成为簇头节点，每个节点处于发现、活动以及休眠三种状态。在网络初始化时，所有节点均处于发现状态，每个节点通过发送 第2章 拓扑控制 广播消息通告自己的位置和ID等信息，然后每个节点将自身的定时器设置为某个区间内的随机值Td，一旦定时器超时，节点发送消息声明其进入活动状态，成为簇头。节点如果在定时器超时前收到来自同一单元格内其他节点成为簇头的声明，则说明自己在这次簇头竞争中失败，从而进入休眠状态。成为簇头的节点设置定时器Ta来设置自己处于活动状态的时间。在Ta超时前，簇头节点定期广播自己处于活动状态的信息，以抑制其他处于发现状态的节点进入活动状态；当Ta超时后，簇头节点重新回到发现状态，处于活动状态的节点如果发现本单元格出现了更适合成为簇头的节点，会自动进入休眠状态。第2章 拓扑控制 由于节点处于侦听状态时也会消耗很多热量，所以让节点处于休眠状态成为传感器拓扑控制算法中常见的方法，GAF算法的优点是在节点密集型分布的网络中使部分节点处于休眠状态，节省了网络总能耗。但GAF算法没有考虑移动节点的存在。实际应用环境中，簇头节点很容易从一个单元格移动到另一个单元格，从而造成某些单元格内没有节点转发数据包，最终造成大量丢失的数据包和重复转发的数据包，导致了总能耗的增加。第2章 拓扑控制 2.4 启启 发 机机 制制传感器网络通常是面向应用事件驱动的网络，骨干网节点在没有检测到事件时不必一直保持在活动状态。在传感器网络的拓扑控制算法中，除了传统的功率控制和层次型拓扑控制两个方面之外，也提出了启发式的节点唤醒和休眠机制。该机制能够使节点在没有事件发生时设置通信模块为休眠状态，而在有事件发生时及时自动醒来并唤醒邻居节点，形成数据转发的拓扑结构。这种机制的引入，使得无线通信模块大部分时间都处于关闭状体，只有传感器模块处于工作状态。由于无线通信模块消耗的能量远大于传感器模块所消耗的能量，所以这种机制进一步节省了能量开销。启发机制重点在于解决节点在休眠状态和活动状态之间的转换问题，不能独立地作为一种拓扑结构控制机制，需要与其他拓扑控制算法结合使用。第2章 拓扑控制 2.4.1 STEM算法算法STEM(Sparse Topology and Energy Management)算法是一种低占空比的节点唤醒机制。该算法采用双信道，即监听信道和数据通信信道。具体地讲，STEM算法又分为STEM-B(STEM-BEACON)算法和STEM-T(STEM-TONE)算法。在STEM-B算法中，当一个节点想给另外一个节点发送数据时，它作为主动节点先发送一串唤醒包。目标节点在收到唤醒包后，发送应答信号并自动进入数据接收状态。主动节点接收到应答信号后，进入数据发送阶段。第2章 拓扑控制 在STEM-T算法中，节点周期性地进入侦听阶段，探测是否有邻居节点要发送数据；当一个节点想要与某个邻居节点进行通信时，它就发送一连串的唤醒包，发送唤醒包的时间长度必须大于侦听的时间间隔，以确保邻居节点能够收到唤醒包，紧接着节点就直接发送数据包。STEM-T算法比STEM-B算法更简单、实用。STEM算法适用于类似环境监测或者突发事件监测等应用场合，实验证明，节点唤醒速度可以满足应用的需要。但是在STEM算法中，节点的休眠周期、部署密度以及网络的传输延迟之间有着密切的关系，要针对具体的应用要求进行调整。第2章 拓扑控制 2.4.2 ASCENT算法算法ASCENT(Adaptive Self-Configuring sEnsor Networks Topologies)算法着重于均衡网络中骨干节点的数量，并保证数据通路的畅通。当节点在接收数据时发现丢包严重，就向数据源方向的邻居节点发出求助消息；节点探测到周围的通信节点丢包率很高或者收到邻居节点发出的帮助请求时，它就主动由休眠状态变为活动状态，帮助邻居节点转发数据包。第2章 拓扑控制 运行ASCENT算法的网络包括触发、建立和稳定三个主要阶段。触发阶段如图2-5(a)所示，在汇聚节点与数据源节点不能正常通信时，汇聚节点向它的邻居节点发出求助信息；建立阶段如图2-5(b)所示，当节点收到邻居节点的求助消息时，通过一定的算法决定自己是否成为活动节点，如果成为活动节点，就向邻居节点发送通告消息，同时这个消息是邻居节点判断自身是否成为活动节点的因素之一；稳定阶段如图2-5(c)所示，数据源节点和汇聚节点间的通信恢复正常，网络中活动节点个数保持稳定，从而达到稳定状态。第2章 拓扑控制 图2-5 ASCENT算法的3个阶段 第2章 拓扑控制 ASCENT算法使得网络可以随具体应用要求而动态地改变拓扑结构，并且节点只根据本地的信息进行计算，不依赖于无线通信模块、节点的地理分布和路由协议等。但ASCENT算法只是提出了网络中局部优化的一种机制，还需要对更大规模的节点分布进行改进，并加入负载平衡技术等。第2章 拓扑控制 2.5 传感器网感器网络的覆盖控制的覆盖控制覆盖是对传感器网络服务质量的度量，即在保证一定的服务质量条件下，使得网络覆盖范围最大化，提供可靠的区域监测和目标跟踪服务。根据传感器节点是否具有移动能力，WSN覆盖问题可分为静态网络覆盖和动态网络覆盖两种形式。静态网络覆盖又分为区域覆盖(area coverage)、点覆盖(point coverage)和栅栏覆盖(barrier coverage)。区域覆盖研究对目标区域的覆盖(监测)问题；点覆盖研究的是对一些离散的目标点的覆盖问题；栅栏覆盖研究运动物体穿越网络部署区域被发现、检测的概率问题。区域覆盖一直是研究的重点，这里我们主要介绍几种区域覆盖的控制算法。第2章 拓扑控制 2.5.1 基于虚基于虚拟势场力的力的传感器网感器网络区域覆盖控制区域覆盖控制虚拟势场力是把网络中每一个移动节点看做一个虚拟的带电粒子，相邻节点之间同时存在排斥力和吸引力两种相互作用力。由于受势场斥力的作用，传感器节点迅速扩展开来；由于受势场引力的作用，传感器节点之间的距离不会无限扩大；两者共同作用，使网络最终达到平稳状态，此时整个无线传感器网络覆盖区域可以达到最大化。在自组织过程中，节点并没有真正移动，而是先由簇首计算出虚拟路径，然后指导簇内节点进行一次移动，以节省能量。第2章 拓扑控制 在无线传感器网络布局优化过程中，各无线传感器节点根据其所受合力的大小和方向移动相应距离，直至达到受力平衡状态或可移动距离的上限位置。假设传感器节点si所受虚拟力为，无线传感器节点sj对节点si的力为；和分别为障碍物和热点区域对无线传感器节点si的作用力，则存在如下关系：(2-3)第2章 拓扑控制 式中为无线传感器节点间的相互作用力，既有引力，也有斥力。虚拟势场力算法采用距离阈值dth来调整无线传感器节点间的相互作用力的属性，当dij大于dth且小于节点的通信半径C时，两者间的作用力为引力；当dij小于dth时，作用力为斥力。与dij的关系如式(2-4)所示：(2-4)第2章 拓扑控制 式中为传感器节点si、sj之间的虚拟势场力；kA、kR分别为引力和斥力系数，主要用于调节虚拟势场力算法布局优化后无线传感节点的疏密程度，它们都是正值，一般凭经验确定；为节点si到sj的方位角。第2章 拓扑控制 考虑到节点从受力到运动为一个加速过程，故节点受力后在x轴和y轴上的位移分别为式中vx，vy分别表示节点在x轴和y轴的移动速度，ax、ay分别表示节点在x轴和y轴的加速度，为时间步长。(2-5)(2-6)第2章 拓扑控制 根据公式(2-5)、公式(2-6)可得节点在x、y轴的迁移位置分别为 式中Fxy为作用于节点的虚拟力，Fth为预定义的虚拟力阈值，当虚拟力小于虚拟力阈值时，则可认为该节点已达到稳定状态，不需要再移动。(2-7)(2-8)第2章 拓扑控制 图2-6(a)和图2-6(b)分别为利用虚拟力对10个和70个传感器节点进行覆盖控制的仿真图，从仿真图可以看出，节点很好地部署在监测区域中，使得网络覆盖率的增大最大化。值得注意的是，最终覆盖率除了受网络中节点数量的影响，还受到距离阈值dth及虚拟引力系数和斥力系数的影响。当dth过小或者虚拟引力系数过大时，节点分布较密集，网络覆盖率无法得到保证；当dth过大或者虚拟斥力系数过小时，节点分布过疏，连通度无法得到保证，从而会形成探测盲区。因此需要采用优化算法进行系数优化，在此不作讨论。第2章 拓扑控制 图2-6 算法仿真 第2章 拓扑控制 2.5.2 基于市场竞争行为的无线传感器网络连接与覆盖算法节点部署受环境影响，有时因为节点部署不慎，可能导致部分节点丧失行动能力，而它的传感与通信功能仍然保持正常。在自组织的时候，如果不考虑这些节点，显然会造成浪费；如果考虑这些节点，则只能采用带约束条件的虚拟力的方法，当移动节点靠近这些失去行动能力的节点时会受到排斥。然而，此方法在某些特殊情况下，不能达到令人满意的效果，检测目标中可能会出现不能覆盖的区域。图2-7展示了这样一个例子。图中，除了位于右下角的一个传感器以外，其余节点均失去了行动能力，这个具有行动能力的传感器因为受到其他节点的排斥，无法进入中间的未覆盖区域。第2章 拓扑控制 图2-7 未覆盖区域 第2章 拓扑控制 基于市场竞争行为的无线传感器网络连接与覆盖算法就是通过研究人类社会的市场竞争行为，提出地用于无线传感器网络连接与覆盖问题的控制算法。该方法把传感器网络中的节点类比为市场竞争中的经济主体，把目标监测区域类比为经济资源，把对传感器网络所做的优化配置类比为市场竞争行为对经济资源的优化配置。将人类社会经济活动中通过市场竞争实现资源的优化配置的方法应用到无线传感器网络的节点部署，降低了节点的计算量、移动距离及信息复杂度，提高了无线传感器的行动效率，并间接达到了省电的目的。第2章 拓扑控制 网络采用簇结构，簇内任意两个节点均可以通过多跳的方式进行通信，而簇间不能通信。对于每一个独立的簇，其配置过程可分为三步进行：(1)实现动、静态的分离。静态传感器虽然不能移动，但其用于感测与通信的能量高于动态传感器(移动会消耗能量)；在人类经济活动领域内，大型企业与小型企业相比较，虽然具有规模优势，但是在竞争中缺乏灵活性。以上两者之间具有很好的类比性。因此，在我们的算法中，把静态传感器定义为“大型企业”，把动态传感器定义为“小型企业”，每一个传感器的有效覆盖面积为该企业所获取的“经济资源”。第2章 拓扑控制(2)簇的内部调整。我们知道在资源有限的情况下，大型企业依靠其规模优势，总是能够优先占有部分资源，其不能占有的资源将在小型企业间通过竞争得到分配，而竞争失败的小型企业能够利用其灵活性去寻找新的资源。同样的道理，我们可以在保证子网络不分裂的基础上，使用最少的动态传感器来补充静态传感器所不能覆盖的区域，从而将尽可能多的动态传感器解放出来，用于网络的扩张。第2章 拓扑控制 图2-8(a)演示了这样一个过程，S1、S2、S3、S4、S5、S6表示静态传感器，它们的感测范围用实线的圆表示，M1、M2、M3、M4、M5、M6表示可移动传感器，它们的感测范围用虚线的圆表示。M1被优化配置到M1，其感测范围用带三角形的圆线表示。为保证网络不分裂，M2与M3保持位置不变。M1、M2、M3和所有的静态传感器构成了一个“准静态传感器覆盖范围”，构成“准静态传感器覆盖范围”的传感器将不再参与向外扩张。M4、M5、M6则是被解放出来的可移动传感器，它们将参与向外扩张。第2章 拓扑控制 图2-8 簇的自组织行为 第2章 拓扑控制(3)簇的向外扩张。参与向外扩张的传感器的感测范围与内部调整后形成的“准静态传感器覆盖范围”的相对位置关系必然处于如下三种类型中的一种。A类：完全在“准静态传感器覆盖范围”之外，如图2-8(a)中的M4；B类：部分在“准静态传感器覆盖范围”之内，如图2-8(a)中的M5；C类：完全在“准静态传感器覆盖范围”之内，如图2-8(a)中的M6。独立子网络向外扩张，如图2-8(b)所示，在确保网络不分裂的前提下，对A类传感器进行优化配置，使网络有效覆盖面积最大，并将A类传感器原先所在位置的信息发布给C类传感器，作为C类传感器移动的指导信息。第2章 拓扑控制 C类传感器根据A类传感器发布的指导信息，按照整体能耗最省的原则规划到达A类传感器原先所在位置的路径。若优化前，网络中C类传感器数目少于A类传感器数目，则优化结果为网络中只包含A类传感器与B类传感器，此时在确保网络不分裂的前提下，对B类传感器进行优化调整，则可使该子网络有效覆盖面积最大。若优化前网络中C类传感器数目多于A类传感器数目，则优化结果为网络中只包含C类传感器与B类传感器，此时在确保网络不分裂的前提下，可以移动B类传感器使其转变为A类传感器，采用前述方法即可实现子网络的配置。第2章 拓扑控制 在扩张过程中，部分簇将因为距离的拉近而能够互相通信，此时需要动态调整簇结构。一旦两个独立簇能够通信，则立即中断原配置操作，将两个簇合并为一个新簇，并重新对它进行配置。当配置结束后，可令部分冗余节点进入休眠状态，从而节省整个网络的能耗。如图2-9(a)所示，我们把目标区域定为长为16 m、宽为14 m的二维平面矩形区域，在这个区域中随机撒入5个半径为1 m的静态节点，同时在矩形中心区域撒入57个半径为0.5 m的动态节点。在此基础上，假定目标区域未被节点覆盖的空白节点为所要争夺的资源，运行本算法后，得到了很好的布置效果，如图2-9(b)所示。第2章 拓扑控制 图2-9 自组织前后覆盖率对比第2章 拓扑控制 为了进一步检验本算法的优劣，我们在动态节点布置基本稳定的时候，模拟节点能量耗尽或故障的情形，随机去掉6个动态节点，观察网络的再组织能力，检验其鲁棒性、抗毁性和灵活性，结果如图2-10(a)所示。同时，我们全程绘制了WSN配置过程的网络覆盖率曲线，从覆盖率的角度定量分析算法的优劣，如图2-10(b)所示。第2章 拓扑控制 图2-10 鲁棒性实验 第2章 拓扑控制 从图2-10(a)可以看出，WSN在失去6个节点的情况下，本算法仍可以使网络尽可能的填补缺失节点的空白，并较好地完成任务。从图2-10(b)可以看出，本算法可以迅速优化网络配置，使覆盖率在较短的时间内上升至97%左右；当节点减少时，覆盖率骤然降低，但在本算法的作用下，网络可以得到再配置，覆盖率可以重新上升到一个较高的程度。第2章 拓扑控制 2.6 小小 结目前，传感器网络拓扑控制研究有了初步进展，研究人员一方面从Ad Hoc网络方面借鉴了宝贵的经验；另一方面针对传感器网络自身的特点，提出了形式多样、侧重点不同的拓扑控制算法。在功率控制方面提出了以邻居节点度为参考依据的LMN算法和LMA算法以及利用邻近图思想生成拓扑结构的DRNG算法和DLSS算法；在层次型拓扑控制方面提出了以LEACH、TopDisc和GAT等为代表的分簇算法。除了功率控制和层次型结构这两个传统的研究方向之外，还引入了启发式的节点唤醒和休眠机制，在数据消息中捎带拓扑控制信息的机制等。第2章 拓扑控制 但是，大多数的拓扑控制算法还只是停留在理论研究阶段，没有考虑实际应用的诸多困难。拓扑控制还有许多问题需要进一步研究，特别是需要探索更加实用的拓扑控制技术。以实际应用为背景、多种机制相结合、综合考虑网络性能将是拓扑控制研究的发展趋势。