第5章 拓扑控制

第五章拓扑控制5.1概述WSN一般具有大规模、自组织、随机部署、环境复杂、传感器节点资源有限、网络拓扑经常发生变化的特点[1]。这些特点使拓扑控制成为挑战性研究课题。同时，这些特点也决定了拓扑控制在WSN研究中的重要性，其主要表现在以下几个方面：（1）拓扑控制是一种重要的节能技术；（2）拓扑控制保证覆盖质量和连通质量；（3）拓扑控制能够降低通信干扰、提高MAC(mediaaccesscontrol)协议和路由协议的效率、为数据融合提供拓扑基础；（4）拓扑控制能够提高网络的可靠性、可扩展性等其他性能。总之，拓扑控制对网络性能具有重大的影响，因而对它的研究具有十分重要的意义第五章拓扑控制目前，拓扑控制研究已经形成功率控制和睡眠调度两个主流研究方向[14]。所谓功率控制，就是为传感器节点选择合适的发射功率；所谓睡眠调度，就是控制传感器节点在工作状态和睡眠状态之间的转换。传感器网络拓扑可以根据节点的可移动与否(动态的或静态的)和部署的可控与否(可控的或不可控的)分为如下4类：（1）静态节点、不可控部署：静态节点随机地部署到给定的区域。这是大部分拓扑控制研究所作的假设。对稀疏网络的功率控制和对密集网络的睡眠调度是两种主要的拓扑控制技术。（2）动态节点、不可控部署：这样的系统称为移动自组织网络(mobileadhocnetwork，简称MANET)。其挑战是无论独立自治的节点如何运动，都要保证网络的正常运转。功率控制是主要的拓扑控制技术。第五章拓扑控制（3）静态节点、可控部署：节点通过人或机器人部署到固定的位置。拓扑控制主要是通过控制节点的位置来实现的，功率控制和睡眠调度虽然可以使用，但已经是次要的了。（4）动态节点、可控部署：在这类网络中，移动节点能够相互定位。拓扑控制机制融入到移动和定位策略中。因为移动是主要的能量消耗，所以节点间的能量高效通信不再是首要问题。因为移动节点的部署不太可能是密集的，所以睡眠调度也不重要。第五章拓扑控制5.2拓扑控制设计目标与研究现状5.2.1拓扑控制的设计目标1．覆盖覆盖可以看成是对传感器网络服务质量的度量。在覆盖问题中，最重要的因素是网络对物理世界的感知能力[15]。覆盖问题可以分为区域覆盖、点覆盖和栅栏覆盖(barriercoverage)[16]。其中，区域覆盖研究对目标区域的覆盖(监测)问题；点覆盖研究对一些离散的目标点的覆盖问题；栅栏覆盖研究运动物体穿越网络部署区域被发现的概率问题。相对而言，对区域覆盖的研究较多。如果目标区域中的任何一点都被k个传感器节点监测，就称网络是k-覆盖的，或者称网络的覆盖度为k。一般要求目标区域的每一个点至少被一个节点监测，即1-覆盖。第五章拓扑控制因为讨论完全覆盖一个目标区域往往是困难的，所以有时也研究部分覆盖，包括部分的1-覆盖和部分的k-覆盖。而且有时也讨论渐近覆盖，所谓渐近覆盖是指，当网络中的节点数趋于无穷大时，完全覆盖目标区域的概率趋于1。对于已部署的静态网络，覆盖控制主要是通过睡眠调度实现的。Voronoi图是常用的覆盖分析工具。对于动态网络，可以利用节点的移动能力，在初始随机部署后，根据网络覆盖的要求实现节点的重部署。虚拟势场方法是一种重要的重部署方法。覆盖控制是拓扑控制的基本问题。第五章拓扑控制2．连通传感器网络一般是大规模的，所以传感器节点感知到的数据一般要以多跳的方式传送到汇聚节点。这就要求拓扑控制必须保证网络的连通性。如果至少要去掉k个传感器节点才能使网络不连通，就称网络是k-连通的，或者称网络的连通度为k。拓扑控制一般要保证网络是连通(1-连通)的。有些应用可能要求网络配置到指定的连通度。像渐近覆盖一样，有时也讨论渐近意义下的连通，亦即当部署区域趋于无穷大时，网络连通的可能性趋于1。功率控制和睡眠调度都必须保证网络的连通性，这是拓扑控制的基本要求。3．网络生命期网络生命期有多种定义。一般将网络生命期定义为直到死亡节点的百分比低于某个阈值时的持续时间[17]。也可以通过对网络的服务质量的度量来定义网络的生命期[18]，可以认为网络只有在满足一定的覆盖质量、连通质量、某个或某些其他服务质量时才是存活的。功率控制和睡眠调度是延长网络生命期的十分有效的技术。最大限度地延长网络的生命期是一个十分复杂的问题，它一直是拓扑控制研究的主要目标。第五章拓扑控制4．吞吐能力设目标区域是一个凸区域，每个节点的吞吐率为λbits/s，在理想情况下，则有下面的关系式[19]：

其中，A是目标区域的面积，W是节点的最高传输速率，π是圆周率，Δ是大于0的常数，L是源节点到目的节点的平均距离，n是节点数，r是理想球状无线电发射模型的发射半径。由此可以看出，通过功率控制减小发射半径和通过睡眠调度减小工作网络的规模，在节省能量的同时，可以在一定程度上提高网络的吞吐能力。5．干扰和竞争减小通信干扰、减少MAC层的竞争和延长网络的生命期基本上是一致的。功率控制可以调节发射范围，睡眠调度可以调节工作节点的数量。这些都能改变1跳邻居节点的个数(也就是与它竞争信道的节点数)。事实上，对于功率控制，网络无线信道竞争区域的大小与节点的发射半径r成正比[20]，所以减小r就可以减少竞争。睡眠调度显然也可以通过使尽可能多的节点睡眠来减小干扰和减少竞争。第五章拓扑控制6．网络延迟当网络负载较高时，低发射功率会带来较小的端到端延迟；而在低负载情况下，低发射功率会带来较大的端到端延迟[21]。对于这一点，一个直观的解释是：当网络负载较低时，高发射功率减少了源节点到目的节点的跳数，所以降低了端到端的延迟；当网络负载较高时，节点对信道的竞争是激烈的，低发射功率由于缓解了竞争而减小了网络延迟。这是功率控制和网络延迟之间的大致关系。7．拓扑性质事实上，对于网络拓扑的优劣，很难直接根据拓扑控制的终极目标给出定量的度量。因此，在设计拓扑控制(特别是功率控制)方案时，往往退而追求良好的拓扑性质。除了连通性之外，对称性、平面性、稀疏性、节点度的有界性、有限伸展性(spannerproperty)等，都是希望具有的性质[22]。此外，拓扑控制还要考虑诸如负载均衡、简单性、可靠性、可扩展性等其他方面。拓扑控制的各种设计目标之间有着错综复杂的关系。对这些关系的研究也是拓扑控制研究的重要内容。第五章拓扑控制5.2.2拓扑控制的研究现状当前，拓扑控制的研究主要以最大限度地延长网络的生命期作为设计目标，并集中于功率控制和睡眠调度两个方面。下面分别予以介绍。各种拓扑控制算法的比较见表5-1。第五章拓扑控制1．功率控制功率控制是一个十分复杂的问题。希腊佩特雷大学(UniversityofPatras)的Kirousis

等人将其简化为发射范围分配问题[23]，简称RA(rangeassignment)问题，并详细讨论了该问题的计算复杂性。设N={u1,…,un}是d(d=1,2,3)维空间中代表网络节点位置的点的集合，r(ui)代表节点ui的发射半径。RA问题就是要在保证网络连通的前提下，使网络的发射功率(各节点的发射功率的总和)最小，也就是要最小化，其中，是大于2的常数。在一维情况下，RA问题可以在多项式时间内解决；然而在二维[12]和三维[11]情况下，RA问题是NP难的。实际的功率控制问题比RA问题更为复杂。这个结论从理论上告诉我们，试图寻找功率控制问题的最优解是不现实的，应该从实际出发，寻找功率控制问题的实用解。针对这一问题，当前已提出了一些解决方案，其基本思想都是通过降低发射功率来延长网络的生命期。下面是几个典型的解决方案，分别代表了目前功率控制的几个典型的研究方向。第五章拓扑控制（1）与路由协议结合的功率控制伊利诺斯大学的Narayanaswamy

等人提出并实现了一种简单的将功率控制与路由协议相结合的解决方案COMPOW[20]。其基本思想是：所有的传感器节点使用一致的发射功率，在保证网络连通的前提下，将功率最小化。COMPOW建立各个功率层上的路由表，在功率层上，通过使用功率交换HELLO消息建立路由表，所有可达节点都是路由表中的表项。COMPOW选择最小的发射功率，使得与具有相同数量的表项，其中，是最大发射功率。于是，整个网络都使用公共的发射功率。在节点分布均匀的情况下，COMPOW具有较好的性能。但是，一个相对孤立的节点会导致所有的节点使用很大的发射功率，所以在节点分布不均的情况下，它的缺陷是明显的。Kawadia

和Kumar提出的CLUSTERPOW[25]是对COMPOW的改进。当转发一个包到目的节点d时，CLUSERPOW选择出现d的最低层次的路由表，设为，然后，以功率而不是将其发送到下一跳节点。在CLUSTERPOW中，分簇是隐含的，且不需要任何簇头节点，分簇通过给定功率层的可达性来实现，分簇的层次由功率的层次数来决定，分簇是动态的、分布的。CLUSTERPOW的主要缺陷是开销太大。第五章拓扑控制（2）基于节点度的功率控制具有代表性的基于节点度算法有柏林工业大学的Kubisch

等人提出的LMA和LMN[26]等。基于节点度算法的基本思想是：给定节点度的上限和下限，每个节点动态地调整自己的发射功率，使得节点的度数落在上限和下限之间。但是，基于节点度数的算法一般难以保证网络的连通性。（3）基于方向的功率控制微软亚洲研究院的Wattenhofer

和康奈尔大学的Li等人提出了一种能够保证网络连通性的基于方向的CBTC算法[27]。其基本思想是：节点选择最小功率，使得在任何以为中心的角度为的锥形区域内至少有一个邻居。作者证明了当时，可以保证网络的连通性。麻省理工学院的Bahramgiri等人又将其推广到三维空间，提出了容错的CBTC[28]。基于方向的算法需要可靠的方向信息，因而需要很好地解决到达角度问题，节点需要配备多个有向天线，因而对传感器节点提出了较高的要求。第五章拓扑控制（4）基于邻近图的功率控制伊利诺斯大学的Li和Hou

提出的DRNG和DLMST[29]是两个具有代表性的基于邻近图理论的算法。基于邻近图的功率控制算法的基本思想是：设所有节点都使用最大发射功率发射时形成的拓扑图是G，按照一定的邻居判别条件求出该图的邻近图，每个节点以自己所邻接的最远节点来确定发射功率。经典的邻近图模型有RNG(relativeneighborhoodgraph)，GG(Gabrielgraph)，DG(Delaunaygraph)，YG(Yaograph)和MST(minimumspanningtree)等。DRNG是基于有向RNG的，DLMST是基于有向局部MST的。DRNG和DLMST能够保证网络的连通性，在平均功率和节点度等方面具有较好的性能。基于邻近图的功率控制一般需要精确的位置信息。此外，微软亚洲研究院的Wattenhofer等人提出的XTC[30]算法对传感器节点没有太高的要求，对部署环境也没有过强的假设，提供了一个面向简单、实用的研究方向。因为XTC代表了功率控制的发展趋势，本章将详细加以介绍。第五章拓扑控制2．睡眠调度功率控制通过降低节点的发射功率来延长网络的生存时间，但却没有考虑空闲侦听时的能量消耗和覆盖冗余。事实上，无线通信模块在空闲侦听时的能量消耗与收发状态时相当，覆盖冗余也造成了很大的能量浪费。所以，只有使节点进入睡眠状态，才能大幅度地降低网络的能量消耗。这对于节点密集型和事件驱动型的网络十分有效。如果网络中的节点都具有相同的功能，扮演相同的角色，就称网络是非层次的或平面的，否则就称为是层次型的。层次型网络通常又称为基于簇的网络。下面分别介绍非层次网络和层次型网络的具有代表性的睡眠调度算法。第五章拓扑控制（1）非层次型网络的睡眠调度算法非层次型睡眠调度的基本思想是：每个节点根据自己所能获得的信息，独立地控制自己在工作状态和睡眠状态之间的转换。它与层次型睡眠调度的主要区别在于：每个节点都不隶属于某个簇，因而不受簇头节点的控制和影响。（2）层次型网络的睡眠调度算法层次型网络睡眠调度的基本思想是：由簇头节点组成骨干网络，则其他节点就可以(当然未必)进入睡眠状态。层次型网络睡眠调度的关键技术是分簇。第五章拓扑控制5.3拓扑模型与拓扑控制算法5.3.1拓扑模型随机图理论在信息科学中被广泛地应用，UDG、RNG和MST等都是基于随机图理论的经典拓扑模型，很多的拓扑结构都是在它们的基础上演变而来的。从连通和抗干扰的角度对拓扑模型进行分类，如图5-1所示。第五章拓扑控制1．单位圆图(UDG)假定网络中N个节点构成了二维平面中的节点集V，所有节点都以最大功率工作时所生成的拓扑称为UDG(unitdiskgraph)。若所有节点最大的传输范围为1，无线节点在平面中就构成了一个UDG，当且仅当图中每对节点间的欧氏距离dis(u,v)≤1时，两个节点之间才有链路相连。UDG的连通性是网络能够提供的最大连通性，因此，任何拓扑控制算法生成的拓扑都是UDG的子图[48]。2．准规则单位圆图(QUDG)假设V、R是两个空间平面的节点集，且，设参数d∈[0，1]，则对称的欧氏图(V，E)被称为以d为参数的准规则单位圆图(QUDG)。图中对任意α，β∈V，若|αβ|≤d，则(α，β)∈E；若|αβ|>1，则(α，β)|E。在实际应用中，节点的发射功率会因为硬件或环境等各种原因而变化，所以QUDG是比UDG更接近实际的拓扑模型[8]。未经拓扑控制算法处理的UDG是非平坦的，非平坦图边的非顶点交叉现象将给信道带来干扰。为了对其作平面化处理，简化拓扑结构，许多UDG的近似子图算法被提了出来[5]。其中最具代表性的有Gabriel图(GG)、相关邻近图(RNG)和最小生成树(MST)。第五章拓扑控制3．Gabriel图(GG)在二维欧氏空间中，V为节点集，w,u,v∈V，w≠u≠v。连接GG中任意两个节点u和v，则以边d(u,v)为直径、通过节点u和v的圆内不包含其他任何节点。如果(dis(u,v))2≤min((dis(w,u))2+(dis(w,v))2),w≠u≠v，则说明d(u,v)为GG的一条边。在传输功率正比传输距离的平方时，GG是最节能的拓扑模型。4．相关邻近图(RNG)在二维欧氏空间中，V为节点集，任意两个节点间的边长小于或等于u、v分别与其他任意一节点的距离的最大值，即欧氏距离dis(u,v)≤max(dis(w,u),dis(w,v))，w,u,v∈V，w≠u≠v。若d(u,v)为RNG的一条边，则在分别以点u或v为圆心，以dis(u,v)为半径的两个圆R1和R2的交集I内不能有其他节点[6]，如图2所示。RNG是由GG产生的，RNG稀疏程度和连通性均介于MST与GG之间，优于MST，且冲突干扰优于GG，易于用分布式算法构造。第五章拓扑控制5．最小生成树(MST)MST是保持图连接所需的满足最小权值的链路子集。MST是RNG的子图，其特征是连通但不形成回路，任意两个节点均可以相互通信。每个节点出现在树上，链路总长度最小。构造MST有两种主要算法，即Kruskal和Prim算法。Kruskal算法总是选择剩余权值最小的边加入最小生成树；Prim算法则通过任意将节点加入最小生成树，同时仅将权值更小的边加入。6．其他常用的拓扑模型除了上面讨论过的几种模型外，Yao图(YG)、Voronoitessellation(VT)和Delaunaytriangulation(DT)也是常用的模型。YG分很多扇区，节点在扇区内选择最近的邻居进行通信，具有简单的分布式结构，节点的度较高；VT首先识别网络冗余节点，然后计算出可被关闭的冗余节点，最后由工作节点构建覆盖集；DT中点集V的一个三角剖分T只包含Delaunay边，具有最大化最小角、惟一性(任意四点不能共圆)等特性。第五章拓扑控制5.3.2拓扑控制算法1．平面网络中的拓扑控制—功率控制在平面网络中，所有的节点都是同构的，具有同样的硬件、同样的能力，完成同样的任务。在平面网络中拓扑控制最基本的方法是控制与一个节点通信的邻节点集。而这个问题与控制节点的发射功率有着密切的关系，所以一般称为功率控制。目前，对平面网络的拓扑控制研究方法主要分为两类：a)概率分析的方法，在节点按照某种概率密度分布的情况下，计算使拓扑满足某些性质(一般是连通性、覆盖率)所需要的最小发射功率和最小邻节点个数；b)计算几何方法，以某些几何结构为基础构建网络拓扑，以满足某些性质。第五章拓扑控制（1）概率分析方法一种基于几何随机图的类似算法；k-连通问题；将邻节点数控制在一定数量内的分布式算法；关于节点有不同最大发射范围的问题；功率控制和移动性的关系。（2）计算几何方法最小生成树(MST)；Gabriel图(Gabrielgraph,GG)；相关邻近图(relativeneighborgraph,RNG)；DRNG和DLMST是两个具有代表性的基于邻近图理论的算法；分布式公共功率协议COMPOW[61]，K-NEIGH协议[62]、XTC、CCP和SPAN等。第五章拓扑控制2．层次型网络中的拓扑控制结构研究无线传感器网络拓扑结构的另一种方法是在网络节点中形成一种层次关系，构成一个层次型的网络。目前主要有两种研究手段，即采用支配集的层次型网络和采用分簇结构的层次型网络。（1）采用支配集的层次型网络文献[66]介绍了两种集中式的例子。a)生成树结构；b)先构造一个不一定连通的支配集，然后在下一个阶段，把集合内的所有节点连接在一起。TopDisc算法中提出了两种具体的节点状态标记办法，分别称为三色算法和四色算法。（2）采用簇结构的层次