第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就可以减少竞争。睡眠调度显然也可以通过使尽可能多的节点睡眠来减小干扰和减少竞争。2161/AWbitssLnr第五章拓扑控制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问题更为复杂。这个结论从理论上告诉我们，试图寻找功率控制问题的最优解是不现实的，应该从实际出发，寻找功率控制问题的实用解。针对这一问题，当前已提出了一些解决方案，其基本思想都是通过降低发射功率来延长网络的生命期。下面是几个典型的解决方案，分别代表了目前功率控制的几个典型的研究方向。4O(n)第五章拓扑控制（1）与路由协议结合的功率控制伊利诺斯大学的Narayanaswamy等人提出并实现了一种简单的将功率控制与路由协议相结合的解决方案COMPOW[20]。其基本思想是：所有的传感器节点使用一致的发射功率，在保证网络连通的前提下，将功率最小化。COMPOW建立各个功率层上的路由表，在功率层上，通过使用功率交换HELLO消息建立路由表，所有可达节点都是路由表中的表项。COMPOW选择最小的发射功率，使得与具有相同数量的表项，其中，是最大发射功率。于是，整个网络都使用公共的发射功率。在节点分布均匀的情况下，COMPOW具有较好的性能。但是，一个相对孤立的节点会导致所有的节点使用很大的发射功率，所以在节点分布不均的情况下，它的缺陷是明显的。Kawadia和Kumar提出的CLUSTERPOW[25]是对COMPOW的改进。当转发一个包到目的节点d时，CLUSERPOW选择出现d的最低层次的路由表，设为，然后，以功率而不是将其发送到下一跳节点。在CLUSTERPOW中，分簇是隐含的，且不需要任何簇头节点，分簇通过给定功率层的可达性来实现，分簇的层次由功率的层次数来决定，分簇是动态的、分布的。CLUSTERPOW的主要缺陷是开销太大。iPiPRTcomPcomPRTmaxPRTmaxPminPRTminPiPminPcomP第五章拓扑控制（2）基于节点度的功率控制具有代表性的基于节点度算法有柏林工业大学的Kubisch等人提出的LMA和LMN[26]等。基于节点度算法的基本思想是：给定节点度的上限和下限，每个节点动态地调整自己的发射功率，使得节点的度数落在上限和下限之间。但是，基于节点度数的算法一般难以保证网络的连通性。（3）基于方向的功率控制微软亚洲研究院的Wattenhofer和康奈尔大学的Li等人提出了一种能够保证网络连通性的基于方向的CBTC算法[27]。其基本思想是：节点选择最小功率，使得在任何以为中心的角度为的锥形区域内至少有一个邻居。作者证明了当时，可以保证网络的连通性。麻省理工学院的Bahramgiri等人又将其推广到三维空间，提出了容错的CBTC[28]。基于方向的算法需要可靠的方向信息，因而需要很好地解决到达角度问题，节点需要配备多个有向天线，因而对传感器节点提出了较高的要求。u,Puu5/6第五章拓扑控制（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代表了功率控制的发展趋势，本章将详细加以介绍。G'第五章拓扑控制2．睡眠调度功率控制通过降低节点的发射功率来延长网络的生存时间，但却没有考虑空闲侦听时的能量消耗和覆盖冗余。事实上，无线通信模块在空闲侦听时的能量消耗与收发状态时相当，覆盖冗余也造成了很大的能量浪费。所以，只有使节点进入睡眠状态，才能大幅度地降低网络的能量消耗。这对于节点密集型和事件驱动型的网络十分有效。如果网络中的节点都具有相同的功能，扮演相同的角色，就称网络是非层次的或平面的，否则就称为是层次型的。层次型网络通常又称为基于簇的网络。下面分别介绍非层次网络和层次型网络的具有代表性的睡眠调度算法。第五章拓扑控制（1）非层次型网络的睡眠调度算法非层次型睡眠调度的基本思想是：每个节点根据自己所能获得的信息，独立地控制自己在工作状态和睡眠状态之间的转换。它与层次型睡眠调度的主要区别在于：每个节点都不隶属于某个簇，因而不受簇头节点的控制