1. 引言

近年来，无线传感器/移动自组织网络及容迟/扰网络等无线网络的应用越来越广泛，其中拓扑控制是无线网络中研究的主要问题之一，它不仅可以延长网络的生命周期还可以减少信号干扰，因此拓扑控制的研究具有重要意义。本文针对无线传感器/移动自组织和容迟/扰网络中的拓扑控制问题，分析和总结了近年来相关的主要方向和研究成果，同时对无线传感器/移动自组织和容迟/扰网络中的拓扑控制解决方法进行了分类和总结，并指出了其中的不足与未来的研究方向。

随着电子技术的飞速发展，无线传感器/移动自组织网络(wireless sensor and ad hoc network)和容迟/扰网络(delay-tolerant network)的应用越来越普遍，各种行业都在使用，不管是在民用、军用还是一些特殊行业，特别是在一些极端环境下如矿井监测、军事侦查、水下监测、海岸线监测、目标跟踪等方面得到广泛引用。由于网络设备自身资源的限制，其能量有限,并且在恶劣环境下很容易被损坏，而在无线网络中节省能量，延迟网络的寿命显得尤为重要，特别是在如军事、海岸线监测等行业中，有可能由于网络的损坏导致不可估量的损失，因此如何节省能量，在保证网络连通情况下延长网络生命周期非常重要。

拓扑控制的目标就是在保证网络连通性、吞吐量及覆盖度下以最少的能耗维持网络的拓扑结构，从而延长网络的生命周期和减少信号干扰。在传感器网络中由于其自身的特点，可以通过调节其发射功率来控制能耗，还可以通过调整传感器的状态如休眠或活动等来节能，也可以通过分簇的方法将网络中的节点进行分簇，簇头节点以轮换方式选取，通过簇头节点之间的数据传输实现整个网络的连通。然而，在拓扑控制中有几个性能指标和因素是必须要考虑的：性能指标包括连通性、覆盖度等，考虑因素包括能量有限、带宽有限、拓扑结构的动态变化和非结构化(无线移动自组织和容迟/扰网络中)、断续连接(容迟/扰网络中)和可扩展性等。

下面对几个性能指标和考虑因素概念的详细阐述：

连通性：连通是指网络中的节点可以自由通信，各节点都可以与其它节点通信，整个网络畅通。其中包括单连通、双连通和多连通，其连通度越大，网络就越健壮。

覆盖度：是指网络所覆盖的范围，特别是在传感器网络中是指所监控或检测的范围，这对后面的决策起着重要作用，覆盖度越高，则决策效果会越好。

能量有限：相对于其它的电子设备来说，传感器非常小，成本低，容易部署，但是由于其自身的原因导致其能量有限，只能通过有限的电池等供电设备提供能量，当然现在也有太阳能等自动储存能量的传感器，但是会受到环境和技术等方面的制约，因此目前大部分传感器还是通过电池供电。一旦能量耗尽，传感器将会失效，因此，在网络拓扑控制时，如何节省能量非常重要。

带宽有限：无线网络的带宽由于其自身原因是有限的，比如现在常用的IEEE 802.11和ZigBee，它们的上限分别只能达到54 Mb/s和250 Kb/s。并且，在实际应用中，由于同时通信所引起的信号干扰，使得带宽所能达到的最大值比理论值小很多，因此，在网络拓扑控制中保持合适的传输负载很重要。

拓扑结构动态变化和非结构化：一般来说，无线网络中的通信设备，如WSN中传感器等都是随机部署在一定区域，因此它们之间的通信链路可能是不稳定的，并且在恶劣环境下，传感器还有可能被损坏，从而使得通信中断等情况。而对于无线自组织和容迟/扰网络来说，许多设备本身就是移动的，整个网络的拓扑结构都在实时动态变化。因此，如何通过设置相关参数进行网络的拓扑控制非常重要。

断续连接：相对于有线信道来说，无线信道本身的通信可靠性就差，并且通信质量还受外界环境因素的影响。因此在无线自组织网络和容迟/扰网络中，由于通信设备的实时动态移动，使得设备之间的通信会断断续续，因此，在通信断续情况下，如何以最少能耗下，维护一种拓扑结构保证数据传送到目的节点是拓扑控制中的挑战性问题。

可扩展性：由于在不同环境下，各种网络的规模和应用不同，如WSN中部署的节点个数可能是10个，100个或者更多，这就要求拓扑控制要适用于大规模传感器网络。

2. 拓扑控制分类

纵观当前国内外关于无线网络拓扑控制的研究拓扑控制的方法大概可以分为以下几类：基于功率调整(Power Adjustment)、基于睡眠调度(Power Mode)、基于连通支配集(Connected Dominating Set)和混合结构(包括基于功率调整与基于连通支配集混合和基于睡眠调度与基于连通支配集混合)的拓扑控制，其中基于连通支配集的拓扑控制又可细分为基于几何结构(Based on Geometry)和基于簇结构(Based on Clustering)的拓扑控制。具体分类图如图1所示。

2.1. 基于功率调整

功率调整的方法是指通过调整节点的功率而减少传送数据的能耗，而不是以最大功率传输数据，节点之间通过功率相互协作找到合适的传输功率形成一个连通的网络。在实际中，节点只有几个功率值可以调整，如，Mica 2有30个不同的功率值而Telos节点仅支持8个不同的功率值。但是，在这些有限的功率值中同样可以通过设计算法调整节点的功率，以在保证网络连通的情况下使得总能耗最小。

1) 最小能量通信网络(MECN)

Rodoplu [1] 等提出了一种无线传感器网络下基于位置的本地化算法，并且使得传输数据包所需的能量最小。此算法的主要思想是以多跳的方式找到网络中任意节点到汇聚节点的路径，且能耗最小，从而构造出最小能耗且连通的网络。

2) 小的最小能量通信网络(SMECN)

SMECN [2] 算法是MECN算法的扩展版，此算法所构建的网络比MECN更简单、更快、更节能，SMECN的目的是构建比MECN更小的子图，SMECN算法还证明了SMECN所构建的子图比MECN的小。之后在文献 [3] 中又提出了一种基于SMECN的更有效的算法，此算法可以适用于动态变化的拓扑结构。

3) COMPOW

COMPOW [4] 算法是通过调整各节点的功率，使各节点在尽量小的相同功率情况下保证整个网络连通，从而使得整个网络能耗最小。

2.2. 基于睡眠调度

睡眠调度方法是通过调整节点的不同电源模式来减小能耗。每个节点有四种电源模式：睡眠，监听，发送和接收。发送和接收模式比睡眠模式消耗的能量高得多，连续监听也消耗大量能量。因此，冗余监控节点的状态可以切换到睡眠状态以节省能源。此功能已用于拓扑控制，在保证不降低网络容量和保持连通的情况下减小功耗从而延长网络寿命。

GAF [5] 通过从路由角度识别关闭不必要的节点来节约能量，从而保持恒定的路由。STEM [6] 算法用于管理分布式系统级别的功耗，而不仅仅是在单个节点级别。这种分布式算法确定哪一组传感器节点将负责给定的用户查询，哪些传感器节点将保持闲置状态以节省能耗。ASCENT [7] 建立在这样的概念上：随着密度的增加，只有一部分节点才是建立路由转发骨干网所必需的。在ASCEN中，每个节点基于测量操作区域评估其连通性并调整其功率是否参与多跳网络拓扑结构。汤荣 [8] 等提出了一种基于(ε, ζ)-近似融合的无线传感网拓扑控制算法，此算法从网络中选择部分节点，通过一定的运算对对这些节点进行处理,然后通过控制每个传感器节点的休眠与工作状态构而构建合适的拓扑结构。

以上方法都是通过调度电源模式来降低能耗。

2.3. 基于最小连通支配集

支配集是指满足以下条件的图的子集：该子集外的每个节点都至少有一个直接邻居属于该子集。由支配节点组成的连通图被称为连接支配集(CDS)，它减少了通信负载和能量。一般情况下，无线网络可以建成图模型，从而将拓扑控制问题转换为寻找最小连通支配集问题，但是此问题是NP-Hard问题，因此，许多研究都集中通过启发式算法来解决这个问题。连通支配集还可以细分为基于几何结构的和基于簇结构的。

1) 基于簇结构

基于簇结构的拓扑控制的核心思想是通过在网络中挑选节点集来构建高效的分层拓扑结构。其中许多簇方法都是使用连通支配集的方法来构建虚拟骨干网。

PACDS [9] 是一种计算功率感知连通支配集的拓扑控制方法。ECDC [10] 是一种基于协调重构机制的新型节能分布式连通支配集算法，以进一步延长网络寿命和减小平衡能量消耗。TMPO [11] 是一种分布式拓扑控制算法，它基于网络的最小支配集构造来维护骨干拓扑。根据这种算法，每个节点根据邻居节点之间传播的两跳邻居信息确定最小支配集中自身及其一跳邻居。卫岚宁 [12] 等提出了一种基于改进近邻传播算法的无线传感网分簇与节能，此算法在在近邻传播聚类算法的基础上提出EAPCP算法，对分簇方法进行优化，提高能量利用率，较好的实现了网络的拓扑控制。

2) 基于几何结构

基于几何的拓扑控制已被广泛用于无线网络，特别是在无线传感器网络和无线自组织网络中。

文献 [13] [14] 提出了一种拓扑控制算法，每个节点根据能量消耗权重图建立自己的局部最小生成树，然后调整网络拓扑，使得整个网络以较小能耗维护一种保持数据有效传输的拓扑结构。Angand C W和Tham C K [15] 提出了iMST算法，试图通过减少干扰来最大化平均信道利用率。文献 [16] 提出了一系列结构，即用于无线自组织网络中拓扑控制和广播的k局部最小生成树(LMSTk)。Y Wu [17] 等提出了一种自组织网络下一定延迟约束下最小化干扰的拓扑控制算法，此算法通过建立时延约束下信号干扰最小生成树的方法实现网络的拓扑控制。Min-Te Sun [18] 等提出了自组织网络下用于节能和可靠的无线通信的分布式拓扑控制方法，此方法是一种局部拓扑控制算法，即基于关节点的拓扑控制，它可以有效地节省网络的功耗，与现有的拓扑控制协议不同，此方法将关节点指定为发起者，并构建最小生成树树，以在节省网络连接的同时实现节能。Zebbane, B [19] 等提出了一种无线传感器网络下分布式轻量级冗余感知的拓扑控制方法，它通过将网络划分成组来使用同一区域中的传感器冗余，从而通过保持最少的工作节点并关闭冗余节点来维护连接的骨干网。Zhen Hong [20] 等提出一种异构无线传感器网络下基于能量预测的簇树拓扑控制方法，此方法在考虑链路质量，丢包率等因素的情况下，节省能量，保证网络负载均衡，同时利用中心极限定理和正态分布机制，根据理想和实际平均剩余能量之间的差异，准确预测每轮网络(网络生命周期由轮次表示)，在此基础上，通过成本函数(包括能量，链路质量和丢包率)及其距离来选择簇头。通过能量，距离和链路质量确定非簇头被加入簇。此外，选择每个簇中的几个非簇头作为通过多跳通信传输数据的中继节点，以减少每个簇头的负载并延长网络的生命周期。

以上研究都是无线自组织网络或无线传感器网络下的拓扑控制研究，而关于容迟/扰网络下的拓扑控制研究较少，这是由于容迟/扰网络下的拓扑结构随时间的推进而实时动态变化。Huang M等人 [21] [22] [23] 研究了可预测的容迟/扰网络下中的拓扑控制问题，其中时间演进的网络拓扑结构是可以预测的。他们首先将这种时间演化网络建模为包含空间和时间信息的时空带权有向图。拓扑控制的目标是从原始时空图形建立一个稀疏结构，此拓扑结构要满足以下条件：1) 网络是连通的，并且支持任何两个节点之间都有路由；2) 拓扑结构的总成本最小。Chen等人 [24] [25] [26] 也提出了基于概率和生成树的可预测容迟/扰网络下拓扑控制，他们也证明了这个问题是NP-Complete问题，并且提出了启发式算法，它们都能有效地减小能量消耗和保证网络连通。

2.4. 基于混合

混合方法是指使用以上两种或两种以上相互协作完成网络的拓扑控制，如将基于簇结构和基于功率调整结合会使得整个网络的总能耗更小。

SPAN [27] 是一种多跳ad hoc无线网络的节能技术，能够在不明显降低网络容量或连通性的情况下降低能耗。CLUSTERPOW [28] 旨在通过增加空间复用来增加网络容量。他们提供了一个简单的模块化体系结构在网络层实现CLUSTERPOW。LEACH [29] 是一种基于簇的协议，利用本地基于簇的站(簇头)的随机旋转来平均分配网络中节点之间的能量负载。石美红 [30] 等提出了一种基于优化成簇多跳的LEACH协议改进算法，此算法依据通信射频能耗模型，实现网络的拓扑控制。M.Khalily-Dermanya [31] 等提出了一种基于网络编码的无线传感器网络中的拓扑控制的凸优化模型，次方法结合了拓扑控制和基于网络编码的多播，提高了整体性能，节省了能耗。将优化问题被转化为凸问题，从而有许多理论和概念优势，通过Karush-Kuhn-Tucker (KKT)最优性条件来导出全局最优解的解析表达式。JinsongGui [32] 等提出了一种异构无线网络中基于博弈的局部多目标拓扑控制方法，在此方法中提出了链路生存时间的概念，并将任何链路的多目标加权和作为关于传输功率，链路延迟和链路生存期的函数进行建模。然后提出的基于游戏的局部多目标拓扑控制可以确保在所得到的拓扑结构中存在期望的拓扑特性，其中所提出的改进的局部δ-改进算法算法不仅刺激节点在拓扑控制操作上的合作并确保网络收敛到稳定状态，而且在执行时间和通信开销方面比传统算法具有更好的性能。A. Xenakis [33] 等提出了一种具有不均衡能量分布的无线传感器网络覆盖和寿命优化的拓扑控制，此方法使用不相等的能量分配算法，成功地延长了网络的生命周期；通过使用拓扑控制原理来安排节点，从而提供最佳的覆盖范围，针对此问题抽象出了相应的优化问题模型，定义了一个包含网络覆盖率和生命周期的目标函数，该函数被最大化。此问题通过模拟退火在多项式时间内解决。在每个收敛点评估更新的拓扑，并且实现接近最佳的节点放置以及近乎最优的不相等的能量分配收费方案。

表1是从时间复杂度、信息复杂度、分布式、连通性和移动性等方面对以上拓扑控制算法的比较：

3. 不足与未来的方向

针对目前的研究来看，在无线网络中拓扑控制上存在很多具有挑战性的问题，特别是容迟/扰网络：

1) 如何构建更高效的随机容迟/扰网络模型；

2) 如何设计一种高效的分布式算法来寻找每一对节点之间的通信链路来实现拓扑控制；

3) 如何准确获取网络拓扑信息。

4. 结语

本文对当前与无线网络中拓扑控制相关的主要研究成果进行了综述，并指出了未来的研究方向。当前大部分研究都处在摸索实验研究阶段，特别是容迟/扰网络正处于理论研究阶段，投入实际应用的还比较少，但是对容迟/扰网络的研究一直也是一个热点，因为在当前移动互联网高度发展的时代，此类机会性网络下数据的有效传输和网络的拓扑控制显得尤为重要，因此对无线网络中拓扑控制的研究具有重大意义。

基金项目

本课题得到湖北省教育厅青年人才基金项目(No. Q20162801)资助。