拓扑控制技术是无线传感器网络中的基本问题。 动态变化的拓扑结构是无线传感器网络最大特点之一，因此拓扑控制策略在无线传感器网络中有着重要的意义

目前，在网络协议分层中没有明确的层次对应拓扑控制机制，但大多数的拓扑算法是部署于介质访问控制层（MAC）和路由层（Routing）之间，它为路由层提供足够的路由更新信息，反之，路由表的变化也反作用于拓扑控制机制，MAC层可以提供给拓扑控制算法邻居发现等消息

拓扑控制的意义

• 影响整个网络的生存时间

  无线传感器网络节点一般采用电池供电,节能是网络设计主要考虑的问题之一

  拓扑控制的一个重要目标就是在保证网络连通性和覆盖的情况下，尽量合理高效的使用网络能量，延长整个网络的生命存时间

• 减小节点间通信干扰，提高网络通信效率

  无线传感器网络中节点部署看可能在某范围内很密集
  如果每个节点都以大功率进行通信，会加剧节点之间的干扰；
  若节点发射功率过小，又会导致网络的割裂，影响网络的连通性

• 为路由协议、时间同步提供基础

  在无线传感器网络中，只有活动的节点才能够进行数据转发，而拓扑控制可以确定由哪些节点作为转发节点，同时确定节点之间的邻居关系

• 影响数据融合

  无线传感器网络中的数据融合指传感器节点将采集的数据发送给骨干节点，骨干节点进行数据融合，并把融合结果发送给数据收集节点。而骨干节点的选择是拓扑控制的一项重要内容

• 弥补节点失效的影响

  传感器节点可能部署在恶劣的环境中，在军事应用中甚至部署在敌方区域中，所以很容易受到破坏而失效，这就要求网络拓扑结构具有鲁棒性以适应这种情况

拓扑控制的设计目标

无线传感器网络是与应用密切相关的，不同的应用对应有不同的拓扑控制设计目标要求

• 能量消耗

  能量优化是无线多跳网络拓扑控制研究的一个重要目标，设计能量消耗最小化的网络协议是无线传感器网络成功应用的关键

• 覆盖度

  覆盖可以看成是对传感器网络服务质量的度量

  在覆盖问题中，最重要的因素是网络对物理世界的感知能力

  生成的拓扑必须保证足够大的覆盖度，即覆盖面积足够大的监视区域

  衡量全网覆盖情况有一个量化指标——平均每个节点的覆盖率 C(%)：
  $$C=\frac{所有节点覆盖区域面积}{N\times \pi \times R^2}$$

• 连通性

  为了实现传感器节点间的相互通信，生成的拓扑必须保证连通性，即从任何一个节点都可以发送消息到另外一个节点

  连通性是任何无线传感器网络拓扑控制算法都必须保证的一个重要性质

• 算法的分布式程度

  在无线传感器网络中，一般情况下是不设置认证中心的，传感器节点只能依据自身从网络中收集的信息做出决策。任何一种涉及节点间同步的通信协议都有建立通信的开销。若节点能够了解全局拓扑和传感器网络中所有节点的能量，就能做出最优的决策；若不计同步消息的开销，得到的就是最优的性能

• 网络延迟🚩

  当网络负载较高时，低发射功率会带来较小的端到端延迟
  而在低负载情况下，低发射功率会带来较大的端到端延迟

• 干扰和竞争

  减少通信干扰、减少MAC层的竞争和延长网络的生命期基本上是一致的。功率控制可以调节发射范围，层簇式网络可以调节工作节点的数量。这些都能改变一跳邻居节点的个数，即与它竞争信道的节点数

• 对称性

  对称性是指若从节点m到n有一条边，那么一定存在从节点n到m的边。由于非对称链路在目前的MAC协议中没有得到很好的支持，而且非对称链路通信的开销很大，对于传感器网络能量小的特点而言是一个瓶颈，因此一般都要求生成的拓扑中链路是对称的

• 鲁棒性和可扩展性

  传感网中的拓扑处于变化中，因为：

  1. 节点易造成因能量耗尽而失效
  2. 新节点的加入
  3. 部分传感器节点的可移动性等

  这就要求拓扑控制具有鲁棒性和可扩展性，以适应变化，从而保证网络的连通性和覆盖度

功率控制技术

在满足网络连通的前提下，通过节点功率控制或动态调整节点的发射功率，精简节点间的无线通信链路，保留生成一个高效的数据转发拓扑结构，在保证网络拓扑连通的基础上，使得网络中节点的能量消耗最小

功率控制对网络拓扑结构的影响：

• 统一功率分配算法COMPOW

  COMPOW 协议是一种简单的将功率控制与路由协议相结合的解决方案

  基本思想：所有的传感器节点使用一致的发射功率，在保证网络连通的前提下将功率最小化

  COMPOW 建立各个功率级的路由表，在功率 $P_i$ 级时，通过使用功率 $P_i$ 交换 HELLO 消息建立路由表 $R{T}_{pi}$ ，所有可达节点都是路由表中的表项

  COMPOW 选择最小的发射功率 $P_{com}$ ，使得 $R{T}_{pcom}$ 与最大发射功率具有相同数量的表项，于是整个网络使用公共的发射功率 $P_{com}$

  但该协议只适用于节点分布均匀的情况，缺陷较为明显

• 基于节点度的功率控制LMN/LMA

  LMN/LMA是基于节点度数的算法

  一个节点的度数是指所有距离该节点一跳的邻居节点的数目

  基于节点度的算法一般动态调节节点的发射功率，使得节点的度数处于一个合理的区间

  局部平均算法LMN和本地邻居平均算法LMA是两种周期性动态调整节点发射功率的算法

  LMA算法的主要思想：给定节点度的上下限，动态调整节点的发射功率，使得节点的度落在要求区间内

  LMN与LMA相似，区别在于LMN将所有邻居的邻居数求平均值作为自己的平均数

  LMN算法和LMA算法对节点的要求不高，不需要严格的时间同步，可以保证算法的收敛性和网络的连通性

• 基于邻近图的功率控制

  RNG、DRNG和DLSS等基于邻近图的近似算法在基于邻近图的算法中，所有节点以最大功率发射时形成的拓扑图为图 G，定义为 G = (V, E) 的形式，V 代表图中顶点的集合，E 代表图中边的集合，E 中的元素可以表示为 (u，v)，其中 u, v∈V，按照一定的规则 Q，求出该图的邻近图 G’，最后 G’ 中每个节点以自己所邻接的最远通信节点来确定发射功率

  经典的邻近图模型有RNG（Relative Neighborhood Graph）、GG（Gabriel Graph）、YG（Yao Graph）以及MST（Minimum Spanning Tree）等

典型的层次型拓扑控制方法

层次型拓扑控制是将所有的传感器节点分成一定的簇结构形式

每个簇结构由簇头节点负责将簇内的数据通过其他簇头路由或直接传送到汇聚节点，在簇内部普通节点将感知到的数据传送到簇头节点。从而由簇头节点形成一个处理并转发数据的骨干网，其他节点则可可以暂时关闭通信模块，进入睡眠状态以节省能量

• LEACH

  （这个协议在无线传感网路由中介绍过）

  LEACH是第一个被提出的聚类路由协议，也是一种自适应分簇拓扑算法

  基本思想：将节点组织成簇结构形式，每个簇有一个簇头节点，其他节点作为非簇头节点。所有的非簇头节点只与本簇的簇头节点通信

  LEACH使用轮转的方式选举节点成为簇头节点，从而让所有的节点都有机会成为簇头节点而达到网络中节点能量消耗均匀的目的

• HEED

  HEED（ Hybrid Energy-Efficient Distributed clustering ）是一种混合式的分簇算法，通过定义簇内平均最小可达功率AMRP指标来衡量簇内节点通信成本
  $$AMRP=\frac{{\sum }_{i=1}^{M}MinPw{r}_i}{M}$$

  HEED算法首先根据节点的剩余能量来概率性地选择一些候选节点，以簇内通信代价的高低来竞争产生最终簇头，以簇内平均可达能量作为衡量簇内通信成本的标准

  HEED算法将操作时间分为成簇持续时间 $T_{CP}$ 和网络操作时间 $T_{NO}$

  在成簇持续时间内每个节点分布式的通过有限次的迭代选举出簇头节点，节点在网络操作时间内发送数据到本簇簇头节点，簇头节点可以选择一种路由协议将数据经过多条路径经由其他簇头节点传送到基站或者汇聚节点。

  在簇头选举阶段，每个节点以不同的初始概率发送竞争消息，每次迭代将概率加倍直至为1或有邻节点己经被选为簇头。簇头竞选成功后，其他节点在竞争阶段根据收到的簇头通告信息选择加入AMRP（最小通信代价）最低的簇头

  • 优点
    • 采用了一种对普通节点和簇头节点都统一的机制来衡量簇内通信的代价，而不是LEACH算法所使用的节点和簇头间的距离作为是否加入该簇的指标，这样可以协调簇头覆盖范围内所有节点的能量消耗，从而产生比较均匀的簇头分布
    • 在簇头选举中考虑了节点的剩余能量情况，让剩余能量占初始能量比例更大的节点有更多的机会成为簇头，使得选出的簇头更适合担任数据转发任务，形成的网络拓扑结构更为合理，全网能量消耗更加均匀

• GAF

  GAF地域自适应保真算法将监测区域划分成虚拟单元格，将节点按照位置信息划入相应的单元格，相邻单元格的任意两个节点可直接通信。

  GAF节点有3种状态：

  • 工作状态
  • 睡眠状态
  • 发现状态

  每个单元格只有一个定期选举产生的簇头节点处于工作状态，其他节点周期性地进入睡眠和发现状态。发现状态的节点可以竞争簇头

• TopDisc

  TopDisc是基于最小支配集问题的典型算法

  在TopDisc算法中，由网络中的一个初始节点开始发送用于发现邻居节点的查询消息，该消息携带有发送节点的状态信息。随着查询消息在整个传感器网络中的扩散，算法依次为每个传感器节点标记上颜色即状态

  根据算法中节点状态的个数，TopDisc包括两种具体的节点状态标记方法：三色算法和四色算法

  • 优点：TopDisc算法在密集部署的无线传感器网络中执行速度快
  • 缺点：形成的网络拓扑灵活性不强，也未考虑节点能耗的均衡问题

拓扑控制中的休眠调度技术

拓扑控制中的休眠调度技术能够使节点在没有事情发生时通信模块为睡眠状态，而在有事情发生时自动醒来并唤醒邻居节点，形成数据转发的拓扑结构

这种机制的引入，使得无线通信模块大部分时间都处于关闭状态，只有传感器模块处于工作状态，有效节省了能量开销

此机制重点在于解决节点在睡眠状态和活动状态之间的切换考虑节点能耗的均衡问题

• STEM

  STEM（稀疏拓扑、能源管理）算法包含两种不同的机制：STEM-B和 STEM-T

  在STEM-B算法中每个睡眠节点可以周期性地醒来侦听信道。如果某个节点想要建立通信，它会作为主动节点先发送一连串Beacon包。目标节点在收到Beacon包后，发送应答信号，并自动进入数据接收状态
  如果没有数据通信，节点大部分时间只保持在侦听信道上的周期性侦听

  STEM-T算法比STEM-B算法简单。其节点周期性地进入侦听阶段，探测是否有邻居节点要发送数据。当一个节点想与某个邻居节点进行通信时，它首先发送一连串的唤醒包，发送唤醒包的时间长度必须大于侦听的时间间隔，以确保邻居节点能够接收到唤醒包，然后该节点直接发送数据包。
  可见STEM-T算法与STEM-B算法相比省略了请求应答过程，但增加了节点唤醒次数

  STEM算法使节点在整个生命周期中的多数时间内处于睡眠状态，适用于类似环境监测或者突发事件检测等应用

• ASCENT

  ASCENT（自适应自配置的传感器网络拓扑）算法是另一种节点唤醒机制，其重点在于均衡网络中骨干节点的数量，并保证数据通路的畅通

  节点接收数据时若发现丢包严重就向数据源方向的邻居节点发出求助消息；当节点探测到周围的通信节点丢包率很高或者收到邻居节点发出的帮助请求时，它醒来后主动成为活动节点，帮助邻居节点转发数据包

  节点可以处于4种状态：

  1. 休眠状态
  2. 侦听状态
  3. 测试状态
  4. 活动状态

  从本质上说，ASCENT是一个从汇聚节点向数据源节点回溯建立路由的过程。通过ASCENT算法，节点能够根据网络情况动态地改变自身状态，从而动态地改变网络拓扑结构

• CCP

  CCP覆盖配置协议：网络睡眠节点最大化

  CCP有3个基本的状态：工作状态、侦听状态和睡眠状态

  为了避免由于每个节点根据局部信息独立进行调度而引起的冲突，CCP引入了加入和退出两个过渡状态

• SPAN

  基本思想：在不破坏网络原有连通性的前提下，根据节点的剩余能量、邻居节点的个数、节点的效用等多种因素，自适应地决定是成为骨干节点还是进入睡眠状态

  睡眠节点周期性地唤醒，以判断自己是否应该成为骨干节点，骨干节点周期性地判断自己是否应该退出