第2章拓扑控制

《第2章拓扑控制》由会员分享，可在线阅读，更多相关《第2章拓扑控制（80页珍藏版）》请在金锄头文库上搜索。

1、第2章 拓扑控制,2.1 概述 2.2 功率控制 2.3 层次型拓扑结构控制 2.4 启发机制 2.5 传感器网络的覆盖控制 2.6 小结,2.1 概 述 在无线传感器网络中，传感器节点在最大通信半径下的网络连接关系称为“物理拓扑”。在传感器节点被抛撒后，网络的物理拓扑就是固定的。在满足网络覆盖率和连通性的前提下，通过信息交互、功率控制等手段，剔除物理拓扑中节点间不必要的物理通信链路，建立逻辑链路后形成的网络连接关系，我们称为“逻辑拓扑”。由物理拓扑生成逻辑拓扑的过程，称为无线传感器网络的“拓扑控制”。,无线传感器节点是体积微小的嵌入式设备，由能量有限的电池供电，其处理能力、存储能力和通信能力

2、相对较弱。除了设计能量高效的链路层协议、路由协议和应用层协议外，还要设计优化的网络拓扑控制机制。由于传感器节点数量众多、成本要求低廉、分布区域广泛，而且部署区域环境复杂，有些区域甚至人员不能到达，因此为传感器节点补充能源是很困难的。如何高效地使用能量、使网络生存周期最大化是传感器网络面临的首要挑战。 传感器网络拓扑控制目前主要的研究问题是在满足网络覆盖度和连通度的前提下，通过功率控制和骨干网节点选择，剔除节点之间不必要的无线通信链路，生成一个高效的数据转发的网络拓扑结构。,对于自组织的无线传感器网络而言，拓扑控制对网络的性能影响非常大。良好的逻辑拓扑结构能够提高路由协议和MAC协议的效率，为数

3、据融合、时间同步和目标定位等很多方面奠定基础，有利于节省节点的能量来延长整个网络的生存时间。所以，拓扑控制是传感器网络中的一个基本问题，同时也是研究的核心问题之一，因而对它的研究具有十分重要的意义，主要表现在以下几个方面： (1) 延长网络寿命。传感器节点一般采用电池供电，能耗是网络设计中需要考虑的最主要的因素之一，而拓扑控制的一个重要目标就是在保证网络连通性和覆盖率的条件下，尽量降低网络能耗，延长网络生存周期。,(2) 减少节点通信负载，提高通信效率。传感器节点的分布密度一般较大，通过拓扑控制技术中的功率控制技术，可以选择节点的发射功率，合理调节节点的通信范围，使得节点在连通性和网络通信范围

4、之间取得一个平衡点。 (3) 辅助路由协议。在无线传感器网络中，只有活动的节点才能进行数据转发，而拓扑控制可以确定由哪些节点作为转发节点，同时确定节点之间的邻居关系。 (4) 选择数据融合策略。无线传感网络中，为了减少通信负载，通常选择一些节点先对周围节点的数据进行融合，再进行转发，而在拓扑控制中，将就如何合理、高效地选择融合节点这一问题进行研究。,(5) 采用冗余节点。由于传感器节点本身所固有的脆弱性，不能保证节点一直持续正常的工作，所以在设计时需要采用冗余技术对网络进行拓扑控制，以保证网络的覆盖率和连通度。 拓扑控制研究的问题是：在保证一定的网络连通质量和覆盖质量的前提下，一般以延长网络的

5、生命期为主要目标，通过功率控制和骨干网节点选择，剔除节点之间不必要的通信链路，兼顾通信干扰、网络延迟、负载均衡、简单性、可靠性、可扩展性等其他性能，形成一个数据转发的优化网络拓扑结构。传感器网络用来感知客观物理世界，获取物理世界的信息。客观世界的物理量多种多样，不可穷尽，不同的,传感器网络应用关心不同的物理量，不同的应用背景对传感器网络的要求也不同，它的硬件平台、软件系统和网络协议必然会有很大差别。不同的应用对底层网络的拓扑控制设计目标的要求也不尽相同。下面介绍拓扑控制中一般要考虑的设计目标。 (1) 覆盖。覆盖是对传感器网络服务质量的度量，即在保证一定的服务质量的条件下，使得网络覆盖范围最大

6、化，提供可靠的区域监测和目标跟踪服务。根据传感器节点是否具有移动能力，WSN覆盖可分为静态网络覆盖和动态网络覆盖两种形式。Voronoi图是常用的覆盖分析工具。动态网络覆盖利用节点的移动能力，在初始随机部署后，根据网络覆盖的要求实现节点的重部署。静态网络覆盖将在后面具体介绍，其中虚拟势场方法是一种重要的部署方法。,(2) 连通。传感器网络的规模一般很大，所以传感器节点感知到的数据一般要以多跳的方式传送到汇聚节点，这就要求拓扑控制必须保证网络的连通性。有些应用可能要求网络配置达到指定的连通度，有时也讨论渐近意义下的连通，即当部署的区域趋于无穷大时，网络连通的可能性趋于1。 (3) 网络生命期。一

7、般将网络生命期定义为直到死亡节点的百分比低于某个阈值时的持续时间，也可以通过对网络的服务质量的度量来定义网络的生命期，我们可以认为网络只有在满足一定的覆盖质量、连通质量、某个或某些其他服务质量时才是存活的。最大限度地延长网络的生命期是一个十分复杂的问题，它一直是拓扑控制研究的主要目标。,(4) 吞吐能力。设目标区域是一个凸区域，每个节点的吞吐率为 b/s，在理想情况下，则有下面的关系式： 其中，A是目标区域的面积，W是节点的最高传输速率，是圆周率，是大于0的常数，L是源节点到目的节点的平均距离，n是节点数，r是理想球状无线电发射模型的发射半径。由上式可知，通过功率控制减小发射半径和通过休眠调度

8、减小工作网络的规模，可以在节省能量的同时，在一定程度上提高网络的吞吐能力。,(2-1),(5) 干扰和竞争。减小通信干扰、减少MAC层的竞争和延长网络的生命期，这三者的意义基本是一致的。对于功率控制而言，网络无线信道竞争区域的大小与节点的发射半径r成正比，所以减小r就可以减少竞争；对于休眠调度而言，可以使尽可能多的节点处于休眠状态，减小干扰和减少竞争。 (6) 网络延迟。网络延迟和功率控制之间的大致关系是当网络负载较小时，由于高发射功率减少了源节点到目的节点的跳数，因此降低了端到端的延迟；当网络负载较大时，节点对信道的竞争是激烈的，低发射功率由于缓解了竞争而减小了网络延迟。,(7) 拓扑性质。

9、对于网络拓扑的优劣，很难给出定量的度量。因此，在设计拓扑控制策略时，往往只是使网络具有一些良好的拓扑性质。除了覆盖性、连通性之外，对称性、平面性、稀疏性、节点度的有界性、有限伸展性等，也都是希望网络具有的性质。除此之外，拓扑控制还要考虑负载均衡、简单性、可靠性、可扩展性等其他方面的性质。,2.2 功 率 控 制 传感器网络中，节点发射功率的控制也称功率分配问题。节点通过设置或动态调整节点的发射功率，在保证网络拓扑结构连通、双向连通或者多连通的基础上，使得网络中节点的能量消耗最小，从而延长整个网络的生存时间。当传感器节点部署在二维或三维空间中时，传感器网络的功率控制是一个极难的问题。因此，试图寻

10、找功率控制问题的最优解是不现实的，应该从实际出发，寻找功率控制问题的实用解。针对这一问题，当前学术界已经提出了一些解决方案，其基本思想都是通过降低发射功率来延长网络的生命期。,2.2.1 基于节点度的功率控制 基于节点度的算法是传感器网络拓扑控制中功率控制方面的问题。一个节点的度数是指所有距离该节点一跳的邻居节点的数目。基于节点度算法的核心思想是给定节点度的上限和下限需求，动态调整节点的发射功率，使得节点的度数落在上限和下限之间。基于节点度的算法利用局部信息来调整相邻节点间的连通性，从而保证整个网络的连通性，同时保证节点间的链路具有一定的冗余性和可扩展性。本地平均算法(Local Mean A

11、lgorithm，LMA)和本地邻居平均算法(Local Mean of Neighbors algorithm，LMN)是两种周期性动态调整节点发射功率的算法，它们之间的区别在于计算节点度的策略不同。,2.2.2 基于方向的功率控制 微软亚洲研究院的Wattenhofer和康奈尔大学的Li等人提出了一种能够保证网络连通性的基于方向的CBTC算法。其基本思想是：节点选择最小功率Pu, ，使得在任何以u为中心且角度为的锥形区域内至少有一个邻居。而且，当5/6时，可以保证网络的连通性。麻省理工学院的Bahramgiri等人又将其推广到三维空间，提出了容错的CBTC算法。基于方向的功率控制算法需要可

12、靠的方向信息，因而需要很好地解决到达角度问题，另外节点需要配备多个有向天线，因此对传感器节点提出了较高的要求。,2.2.3 基于邻近图的功率控制 伊利诺斯大学的Li和Hou提出的DRNG(Directed Relative Neighborhood Graph)和DLMST(Directed Local Minimum Spanning Tree)是两个具有代表性的基于临近图理论的功率控制算法。基于临近图的功率控制算法的基本思想是，设所有节点都使用最大发射功率发射时形成拓扑图G，按照一定的邻居判别条件q求出该图的临近图G，G中的每个节点以与自己所临近的、最远的通信节点来确定发射功率。这是一种解

13、决功率分配问题的近似解法，考虑到由于无线传感器网络中两个节点形成的边是有向的，为了避免形成单向边，一般在运用基于临近图的功率控制算法形成网络拓扑以后，,还需要进行节点之间边的增删，以使最后得到的网络拓扑是双向连通的。在无线传感器网络中，基于临近图功率控制算法的作用是使节点确定自己的邻居集合，调整适当的发射功率，从而在建立一个连通网络的同时使得能量消耗最低。经典的临近图模型有RNG(Relative Neighborhood Graph)、GG(Gabriel Graph)、DG(Delaunay Graph)、YG(Yao Graph)和MST(Minimum Spanning Tree)等。

14、DRNG是基于有向RNG的，DLMST是基于有向局部MST的。DRNG和DLMST能够保证网络的连通性，在平均功率和节点度等方面具有较好的性能。基于临近图的功率控制一般需要精确的位置信息。下面简单介绍DRNG算法和DLSS(Directed Local Spanning Subgraph)算法。,DRNG算法和DLSS算法是两种从临近图观点考虑拓扑问题的算法，是一种较早提出的功率控制算法，两者均以经典的临近图RNG和LMST等理论为基础，全面考虑了连通性和双向连通性问题。 首先有如下定义： (1) 边有向，即(u, v)和(v, u)是两组不同的边； (2) d(u, v)表示节点u和v间的距

15、离，ru表示节点u的通信半径。 可达邻居 为u以最大发射半径可以到达的节点集合，由节点u和 以及这些节点之间的边构成了可达邻居子图 。,由节点u和节点v构成边的权重函数满足如下关系：,在DRNG算法和DLSS算法中，节点都需要知道其他一些节点的必要信息，因此需要一个信息收集阶段：每个节点以最大的发射功率广播“HELLO”消息，该消息至少包括自身的身份标识号(ID)和自身位置，然后，节点通过收到的“HELLO”消息确定自己可以达到的邻居集合 。在DRNG算法中，没有明确的步骤，只给出确定邻居节点的条件，如图2-1所示，如果节点u和v满足ru，而且不存在另外其他节点p同时满足、和rp时，节点v则被

16、选为节点u的邻居节点，所以，DRNG算法为节点u确定了邻居集合。,在DLSS算法中，假设节点u及其可达邻居集合，将p到所有可达邻居节点的边以权重为标准按升序排列；依次取出这些边，直到u与所有可达邻居节点相连通或者通过其他节点连通；最后，与u直接连通的节点构成u的邻居集合。从图论的观点看，DLSS算法等价于基础上的本地最小生成树的计算。经过DRNG或DLSS算法后，节点u确定了自己的邻居集合，然后将发射半径调整为最远邻居节点的距离，进一步通过对拓扑图的边进行增删，使得网络达到双向连通。,图2-1 DRNG算法,DRNG算法和DLSS算法着重考虑了网络的连通性，充分利用了邻居图理论，是无线传感器网络中的经典算法，二者以原始网络拓扑双向连通为前提，保证优化后的拓扑也是双向连通的。 此外，微软亚洲研究院的Wattenhofer等人提出的XTC算法对传感器节点没有太高的要求，对部署环境也没有过强的假设，因此提供了一个面向简单、实用的研究方向。XTC算法代表了功率控制的发展趋势，下面将详细加以