◆像渐近覆盖一样，有时也讨论渐近意义下的连通，亦即当部署区域趋于 无穷大时，网络连通的可能性趋于1。 ◆功率控制和睡眠调度都必须保证网络的连通性，这是拓扑控制的基本要 求。
第五章 拓扑控制
3．网络生命期 网络生命期有多种定义。
一般定义：直到死亡节点的百分比低于某个阈值时的持续时间。
另一种定义：对网络的服务质量的某种度量的来定义。可以认为网络只有 在满足一定的覆盖质量、连通质量、某个或某些其他服务质量时才是存活的。
第五章 拓扑控制
5．干扰和竞争 ◆减小通信干扰、减少MAC层的竞争和延长网络的生命期基本上是一致的：
功率控制可以调节发射范围，睡眠调度可以调节工作节点的数量。
这些都能改变1跳邻居节点的个数(也就是与它竞争信道的节点数)。 ◆对于功率控制，网络无线信道竞争区域的大小与节点的发射半径r成正比， 减小r就可以减少竞争。 ◆睡眠调度也可以通过使尽可能多的节点睡眠来减小干扰和减少竞争。
◆特点：在节点分布均匀的情况下，具有较好的性能。但是，一个相对孤 立的节点会导致所有的节点使用很大的发射功率，所以在节点分布不均的情 况下，它的缺陷是明显的。 ◆Kawadia 和Kumar 提出了改进算法，但其主要缺陷是开销太大。
第五章 拓扑控制
（2）基于节点度的功率控制
◆基本思想是：给定节点度的上限和下限，每个节点动态地调整自己的发射 功率，使得节点的度数落在上限和下限之间。 ◆缺点：一般难以保证网络的连通性。 ◆具有代表性算法：柏林工业大学的Kubisch 等人提出的LMA 和LMN[26]等。
基于方向的算法需要可靠的方向信息，因而需要很好地解决到达角度问题， 节点需要配备多个有向天线，因而对传感器节点提出了较高的要求。
第五章 拓扑控制
（4）基于邻近图的功率控制
◆伊利诺斯大学的Li 和Hou 提出的DRNG 和DLMST[29]是两个具有代表性的 基于邻近图理论的算法。 ◆基本思想：设所有节点都使用最大发射功率发射时形成的拓扑图是G，按照 一定的邻居判别条件求出该图的邻近图 G' ，每个节点以自己所邻接的最远节点 来确定发射功率。 经典的邻近图模型：RNG(relative neighborhood graph)，GG(Gabriel graph)，DG(Delaunay graph)，YG(Yao graph)和MST(minimum spanning tree)等。 ◆DRNG算法是基于有向RNG 的，DLMST算法是基于有向局部MST 的。 ◆DRNG 和DLMST 能够保证网络的连通性，在平均功率和节点度等方面具有 较好的性能。 基于邻近图的功率控制一般需要精确的位置信息。 微软亚洲研究院的Wattenhofer等人提出的XTC算法对传感器节点没有太高的 要求，对部署环境也没有过强的假设，提供了一个面向简单、实用的研究方向， 代表了功率控制的发展趋势，教材有详细介绍。
第五章 拓扑控制
7．拓扑性质 ◆对于网络拓扑的优劣，很难直接根据拓扑控制的终极目标给出定量的度量。
◆在设计拓扑控制(特别是功率控制)方案时，往往退而追求良好的拓扑性质。
◆希望的拓扑性质：
连通性； 对称性； 平面性； 稀疏性； 节点度的有界性；
有限伸展性。
◆其他考虑的方面：负载均衡、简单性、可靠性、可扩展性等。 拓扑控制的各种设计目标之间有着错综复杂的关系。对这些关系的研究也是 拓扑控制研究的重要内容。
16 AW 1 bits / s 2 L nr
W ---- 节点的最高传输速率；
Δ ---- 大于0的一个常数； L ---- 源节点到目的节点的平均距离 n ---- 是节点数；
r ---- 理想球状无线电发射模型的发射半径。
可见：通过功率控制减小发射半径和通过睡眠调度减小工作网络的规模， 在节省能量的同时，可以在一定程度上提高网络的吞吐能力。
4
实际的功率控制问题比RA问题更为复杂。
◆结论：试图寻找功率控制问题的最优解是不现实的，应该从实际出发， 寻找功率控制问题的实用解。
◆当前已提出一些解决方案，基本思想：通过降低发射功率来延长网络的 生命期。
第五章 拓扑控制
功率控制典型解决方案：
（1）与路由协议结合的功率控制
◆伊利诺斯大学提出。
◆基本思想：所有的传感器节点使用一致的发射功率，在保证网络连通的 前提下，将功率最小化。
这些特点也决定了拓扑控制在WSN研究中的重要性，主要表现在： （1）拓扑控制是一种重要的节能技术； （2）拓扑控制保证覆盖质量和连通质量； （3）拓扑控制能够降低通信干扰、提高MAC(media access control)协议和路 由协议的效率、为数据融合提供拓扑基础； （4）拓扑控制能够提高网络的可靠性、可扩展性等其他性能。总之，拓扑控制 对网络性能具有重大的影响，因而对它的研究具有十分重要的意义。
第五章 拓扑控制
2．连通 ◆传感器网络一般是大规模的，所以传感器节点感知到的数据一般要以多 跳的方式传送到汇聚节点。 ◆这要求拓扑控制必须保证网络的连通性。 K-连通的概念：至少要去掉k个传感器节点才能使网络不连通。 也称网络的连通度为k。
拓扑控制一般要保证网络是连通(1-连通)的。
有些应用可能要求网络配置到指定的连通度。
◆ UDG的连通性是网络能够提供的最大连通性，因此，任何拓扑控制算法 生成的拓扑都是UDG的子图。
◆如果网络中的节点都具有相同的功能，扮演相同的角色，就称网络是非层次 的或平面的，否则就称为是层次型的。
层次型网络通常又称为基于簇的网络。
第五章 拓扑控制
（1）非层次型网络的睡眠调度算法
◆基本思想：每个节点根据自己所能获得的信息，独立地控制自己在工作 状态和睡眠状态之间的转换。 ◆与层次型睡眠调度的主要区别：每个节点都不隶属于某个簇，因而不受 簇头节点的控制和影响。
第五章 拓扑控制
5.2 拓扑控制设计目标与研究现状
5.2.1 拓扑控制的设计目标
1．覆盖
◆覆盖可以看成是对传感器网络服务质量的度量。在覆盖问题中，最重要 的因素是网络对物理世界的感知能力。 ◆覆盖问题分类：
区域覆盖 ---- 研究对目标区域的覆盖(监测)问题； 点覆盖 ---- 研究对一些离散的目标点的覆盖问题； 栅栏覆盖 ---- 研究运动物体穿越网络部署区域被发现的概率问题。
第五章ቤተ መጻሕፍቲ ባይዱ拓扑控制
拓扑控制研究形成等两个主流研究方向：功率控制和睡眠调度。 功率控制----为传感器节点选择合适的发射功率； 睡眠调度----控制传感器节点在工作状态和睡眠状态之间的转换。 根据节点的可移动与否(动态的或静态的)，和部署的可控与否(可控的或不可 控的)，传感器网络拓扑可以分为4类： （1）静态节点、不可控部署：
◆有时也讨论渐近覆盖。
渐近覆盖 ---- 当网络中节点数趋于无穷大时，完全覆盖目标区域的概率趋于1。 ◆对于已部署的静态网络，覆盖控制主要是通过睡眠调度实现的。
Voronoi图是常用的覆盖分析工具。
◆对于动态网络，可以利用节点的移动能力，在初始随机部署后，根据网络覆盖的要求 实现节点的重部署。 虚拟势场方法是一种重要的重部署方法。 覆盖控制是拓扑控制的基本问题。
◆功率控制和睡眠调度是延长网络生命期的十分有效的技术。
◆最大限度地延长网络的生命期是一个十分复杂的问题，它一直是拓扑控 制研究的主要目标。
第五章 拓扑控制
4．吞吐能力 设目标区域是一个凸区域，每个节点的吞吐率为λbits/s，在理想情况下， 则有下面的关系式：

其中： A ---- 目标区域的面积；
第五章 拓扑控制
5.2.2 拓扑控制的研究现状
◆拓扑控制的研究目标： 最大限度地延长网络的生命期。
◆两个研究方向：
功率控制和睡眠调度。 各种拓扑控制算法见下页表。
第五章 拓扑控制
第五章 拓扑控制
1．功率控制 ◆功率控制是一个十分复杂的问题。 希腊佩特雷大学(University of Patras)的Kirousis 等人将其简化为发射范 围分配问题[23]，简称RA(range assignment)问题，并详细讨论了该问题的 计算复杂性。 ◆设N={u1,…,un}是d(d=1,2,3)维空间中代表网络节点位置的点的集合， r(ui)代表节点ui的发射半径。RA问题就是要在保证网络连通的前提下，使网 络的发射功率(各节点的发射功率的总和)最小。 在一维情况下，RA 问题可以在多项式时间内解决；然而在二维和三维情 O(n ) 况下，RA 问题是NP 难的。
第五章 拓扑控制
6．网络延迟 ◆当网络负载较高时，低发射功率会带来较小的端到端延迟；
◆而在低负载情况下，低发射功率会带来较大的端到端延迟。
原因： ◆当网络负载较低时，高发射功率减少了源节点到目的节点的跳数，所以 降低了端到端的延迟； ◆当网络负载较高时，节点对信道的竞争是激烈的，低发射功率由于缓解 了竞争而减小了网络延迟。这是功率控制和网络延迟之间的大致关系。
对区域覆盖的研究较多。
◆ k-覆盖的概念 ---- 指目标区域中的任何一点都被k个传感器节点监测。 也称网络的覆盖度为k。 一般要求目标区域的每一个点至少被一个节点监测，即1-覆盖。
第五章 拓扑控制
◆讨论完全覆盖一个目标区域往往是困难的，所以有时也研究部分覆盖，包括：
部分的1-覆盖； 部分的k-覆盖。
第五章 拓扑控制
郑来波 山东大学信息学院通信研究所 办公室：信息学院北楼513 电话：88362208 Email: zhenglaibo@
第五章 拓扑控制
5.1 概述
WSN一般具有大规模、自组织、随机部署、环境复杂、传感器节点资源有限、 网络拓扑经常发生变化的特点。
这些特点使拓扑控制成为挑战性研究课题。
第五章 拓扑控制
2．睡眠调度 ◆功率控制通过降低节点的发射功率来延长网络的生存时间，但却没有考虑空 闲侦听时的能量消耗和覆盖冗余。 ◆无线通信模块在空闲侦听时的能量消耗与收发状态时相当，覆盖冗余也造成 了很大的能量浪费。 ◆节点睡眠能大幅度地降低网络的能量消耗，对于节点密集型和事件驱动型的 网络十分有效。