无线传感器网络的拓扑维护

摘要：  拓扑维护对无线传感器网络的运行至关重要，它旨在通过轮换节点角色、调用拓扑构建或维护算法来修复、重构当前的拓扑结构以提高网络的生命周期。首先对拓扑维护进行了定义，描述了拓扑维护的设计目标，并设计了一个拓扑维护通用模型。然后阐述了拓扑维护技术的研究进展，并对其中有代表性的算法进行了比较分析。最后指出了目前拓扑维护研究中存在的问题及其发展趋势。

关键字：  拓扑维护，  无线传感器网络

拓扑维护对无线传感器网络的运行至关重要，它旨在通过轮换节点角色、调用拓扑构建或维护算法来修复、重构当前的拓扑结构以提高网络的生命周期。首先对拓扑维护进行了定义，描述了拓扑维护的设计目标，并设计了一个拓扑维护通用模型。然后阐述了拓扑维护技术的研究进展，并对其中有代表性的算法进行了比较分析。最后指出了目前拓扑维护研究中存在的问题及其发展趋势。

无线传感器网络由于具有低功耗、低成本以及分布式和自组织等特点已被广泛应用于军事国防、工农业控制、环境监测、生物医疗和抢险救灾等领域。通常，一个无线传感器网络由成百上千传感器节点组成，每个节点具有感知当前环境、通过广播与邻近节点进行通信以及对收集的信息执行本地计算的能力。但是，这些能力对每个节点来说都很有限，尤其是节点的能量受限严重限制了网络的生命周期，从而影响了网络的服务质量和进一步应用。因此，近几年来，许多研究人员对无线传感器网络的节能方面进行了大量的研究，从拥塞控制[2]到数据压缩，从睡眠调度到拓扑控制。目的是尽可能多的节省能量，最大化网络生命周期。

拓扑控制作为无线传感器网络的一种关键节能技术，通常在保持网络重要特性如连通和覆盖的前提下改变、简化或优化网络的拓扑来节省能量。而且，拓扑控制形成的良好网络拓扑能够提高路由协议和MAC 协议的效率[5].然而，拓扑控制通常被视为一个单一过程，它并未包括对网络拓扑的维护，这影响拓扑控制算法的分类。目前的分类都局限于如何构建网络的拓扑结构，而忽略拓扑控制中的拓扑维护。如文献[6]提出的分类只注重拓扑构建算法，这些算法通过改变节点的传输范围来构建和优化网络的拓扑结构。文献[5][7]中提出一个更广泛的拓扑构建算法分类，主要考虑分层和混合算法。文献[8]提出了拓扑控制由拓扑构建和拓扑维护两个阶段组成，并对拓扑维护进行了简单定义和分类。

虽然文献[8]中对拓扑维护进行了简单定义，并根据目标优化拓扑构建的时间将拓扑维护技术分为静态、动态和混合拓扑维护。但文中并未对拓扑维护进行系统阐述，而对拓扑维护的定义又不严谨，对拓扑维护技术的分类也与当前研究现状不符，因为现有研究中基本上没有文中所提到的静态和混合拓扑维护算法或协议。因此，为了更深入的对无线传感器网络中的拓扑维护技术进行研究，本文从拓扑维护定义及模型，拓扑维护设计目标，以及当前的研究现状和存在的问题与发展方向等方面对拓扑维护进行了阐述。第1 节描述了无线传感器网络拓扑维护基础，主要给出了拓扑维护全新的定义，并指出拓扑维护设计目标。第2 节设计了一个拓扑维护通用模型，并对模型中的触发标准和维护策略进行了详细描述。第3 节总结了目前有关拓扑维护研究工作，并进行了比较分析。第4 节分析了当前研究中的不足，并指出拓扑维护技术的发展方向。最后对全文进行了总结。

1 拓扑维护基础

无线传感器网络拓扑控制由两部分组成，即拓扑构建和拓扑维护。一旦建立起最初的网络优化拓扑，网络开始执行它所指定的任务。由于网络任务所包含的每一个行为如感测、数据处理和传输等都需要消耗能量，因此随着时间的推移，当前的网络拓扑不再处于最优运行状态，因此需要对其进行维护使其重新保持最优或接近最优状态。

1.1 拓扑维护定义

无线传感器网络的拓扑控制可以看作一个重复的过程，如图1 所示。首先，对所有无线传感器网络都有一个拓扑初始化阶段。在该阶段，每个节点用其最大发射功率发射来建立初始拓扑。在初始化阶段后，通过运行不同的算法或协议来对初始拓扑进行优化，并最终构建一个优化拓扑，该阶段称之为拓扑构建。一旦拓扑构建阶段建立起优化网络拓扑，拓扑维护阶段必须开始工作。

[#page#]

在拓扑维护阶段，实时监测当前拓扑状态，并在适当的时候触发拓扑恢复或重构过程。从图1 中可见，在网络的生命周期内，拓扑维护周期运行，直到网络死亡。目前，对拓扑维护进行定义的文献很少，文献[8]对拓扑维护进行了简单定义，指出“拓扑维护是指当网络当前工作的拓扑结构不是最优化的拓扑结构时，及时通过修复、切换或重构新的网络拓扑，使网络达到预先设定的性质，延长网络的生命期”.

该定义没有指出拓扑维护运行的时间、所采取的维护方式，特别是定义中提到使拓扑达到或接近最优以及达到预先设定的性质，却没有指出是哪个具体阶段的最优或性质，因为随着网络的运行，网络的最优状态和性质也在发生变化。所以，本文对拓扑维护进行了比较严谨的定义，即拓扑维护是一个周期性的过程，在每个周期中它由不同的触发标准(如时间，能量，节点故障等)触发，通过尽可能多地轮换节点角色或重新运行拓扑构建过程或调用专用维护算法来修复或重构网络拓扑，均衡网络能量消耗，使新的拓扑成为当前最优或接近当前最优状态，并最终延长网络的生命周期。

1.2 设计目标

拓扑维护和其它传感器网络技术一样，其主要目的是延长网络的生命周期。此外，传感器网络被构建用来实现某些任务，如执行传感和传输传感数据，因此一个或多个服务质量目标如保持传感覆盖以及保持网络连通等也通常被考虑。

而且，无线传感器网络的应用不同则导致其底层网络的拓扑维护设计目标不同或目标优先次序不同。因此，本文接下来只介绍拓扑维护主要考虑的设计目标。

(1)网络生命周期

网络生命周期已经以不同方式被定义，如基于节点数、基于传感覆盖以及网络连通以及可扩展的网络生命周期。

拓扑维护是延长网络生命周期十分有效的技术，如拓扑维护协议SPAN和CCP 通过关闭冗余节点并维持一个节点子集处于工作状态来提高无线传感器网络的生命周期。然而，最大化网络生命周期是一个十分复杂的问题，它一直是拓扑维护研究的主要目标。

(2)覆盖和连通

覆盖和连通是无线传感器网络拓扑维护的基本问题，拓扑维护在对原有的优化拓扑进行恢复、切换或重构的过程中，必须保持原有拓扑的覆盖或连通。

(3)安全和故障容忍

拓扑维护过程中，一些传感器节点由于能量耗尽、物理损坏或环境干扰可能会失灵或发生故障，而这些传感器节点的失效并不影响拓扑维护的整体任务。如文献[12]中提出一个故障容忍的自组织方法来维护一个覆盖和连通的骨干网络。此外，无线传感器的实际应用中存在各种类型的恶意行为和攻击[13]，因此，安全也是拓扑维护的一个重要目标。

(4)能量效率和收敛时间

与无线传感器网络其它功能一样，拓扑维护算法必须是能量有效的。也就是说拓扑维护算法应该具有低的计算复杂度和低的报文开销。此外，在拓扑维护过程中，当前的拓扑将被一个新的拓扑取代，因此在新拓扑被激活之间有一个转换时间，该时间应该尽可能小。

(5)能量均衡和可扩展性

拓扑维护技术应该尽量在网络的所有节点间均衡地分布能量消耗。另外，部署在兴趣或目标区域的传感器节点可能成百上千甚至上万。拓扑维护协议或算法应该能在不同数量级节点的网络中运行。

[#page#]

2 拓扑维护模型

目前，并没有文献对拓扑维护模型进行描述。为了更好的理解拓扑维护的运行过程及其特点，本文设计了一个通用的拓扑维护模型，如图2 所示。从图中可见，拓扑维护是一个周期的过程，每个周期中从网络的当前拓扑开始，经过拓扑维护过程生成一个优化的拓扑，周期运行，直到网络死亡。

从上图可见，每个拓扑维护周期，经由触发器和决策器。

其中触发器主要根据设计的触发标准如时间、能量或节点故障等来触发拓扑维护过程。决策器用来选择拓扑维护策略。

接下来对该模型进行详细描述。

(1)触发器

触发器负责周期地触发当前网络拓扑的维护过程，其对拓扑维护的性能具有重要的影响。因为如果提前触发，则由于频繁运行拓扑维护协议或算法而消耗不必要的能量，而滞后触发，则将导致网络可能以次优甚至不连通状态运行，降低甚至无法实现网络的服务质量。常见的触发标准有：

时间：网络运行一段时间后触发拓扑维护，该时间的大小通常是固定且预先定义，通常由一个定时器来完成。

SPAN基于时间来触发网络中协调器节点的更新过程，从而实现骨干网络的拓扑维护。

能量：鉴于无线传感器设备的能量限制，当节点的能量级别低于某个阈值时触发拓扑维护是很有必要的。LPH算法中，当节点的剩余能量E(i)低于平均剩余能量Eavr 时，触发簇内拓扑维护过程。CLTC算法中，当簇头节点的能量降到门限值M 时，触发簇内拓扑维护过程。而Poly算法中，当网络的整体能量降低10%时触发拓扑维护过程。

节点故障：当网络中一个或一些节点故障时，触发拓扑维护。如SMSS算法中，当节点u 发现某个节点m 故障时，它将检查m 是否为其确定的邻节点，如果是则重新运行拓扑构建算法来维护网络拓扑结构。EETMS算法中，一旦网络发现故障节点，触发局部拓扑维护过程。

[#page#]

网络密度：采用网络的节点度或者一些重要节点的节点度来触发拓扑维护过程。AFECA提出的自适应精度节能算法使用邻居密度来触发拓扑维护过程。

此外，这些触发条件也可任意组合用来触发拓扑维护过程，如基于能量和节点故障，或者时间和能量等。此外，其它的网络参数也可作为触发标准，如链路失效、频繁丢包以及拥塞和长路由路径等。

(2)决策器

决策器主要确定采用何种策略来维护当前的网络拓扑结构，它是拓扑维护的核心。拓扑维护策略可以分为两种，一种是基于角色轮换的拓扑维护策略，也就是说通过对网络中节点的角色-如睡眠/工作、簇头/非簇头等进行切换来节约能量，实现延长网络生命周期的目的。另一种是基于拓扑重构的拓扑维护策略，其实质是运行拓扑构建阶段的算法或专门的拓扑维护算法与协议来维护网络拓扑结构。

在基于角色轮换的拓扑维护策略中，首先要明确网络中每个节点所能扮演的角色。每个节点的角色迁移与拓扑维护协议或算法特点和设计密切相关，确定节点所处角色的因素包括节点密度、位置、通信流量、丢包率、时间以及外部环境条件等。如节点当前为角色1，当某个事件发生，则节点进行相应测试以决定是否进入角色2还是继续处于角色1.

而基于拓扑重构的拓扑维护策略中，主要是重新调用拓扑构建阶段的算法或专门的拓扑维护算法。因此，调用算法的频率是关键。一旦触发器触发拓扑维护过程，拓扑维护策略则应该综合考虑网络的相关性能，决定是否调用相关算法或协议，以均衡网络能量消耗并最终延长网络生命周期。

此外，决策器还可根据网络运行情况在不同的阶段采用不同的维护策略来维护当前的网络拓扑结构。无论是基于角色转换还是基于拓扑重构的拓扑维护技术，决策器还负责对生命周期的监测。也就是说，在网络的生命周期内，决策器根据维护策略周期性地对网络拓扑结构进行维护，而一旦网络的生命周期结束，决策器停止维护过程，并宣告网络死亡。

3 拓扑维护研究现状

目前专门的拓扑维护技术研究还比较少，但相关研究结果表明优化的拓扑维护能有效地节省能量并延长网络生命周期，同时保持网络的基本属性覆盖或连通。本节中，根据拓扑维护决策器所选维护策略将现有的拓扑维护技术分为基于角色轮换、基于拓扑重构和混合的拓扑维护。

3.1 基于角色轮换的拓扑维护

基于角色转换的拓扑维护技术，通过轮换节点的角色来对拓扑进行维护。节点的角色可以从多方面描述，如睡眠/工作、簇头/非簇头、协调器/非协调器等，且节点的角色可以相互转换。目前研究中，轮换的节点角色主要有两种，一种是簇头/非簇头。它通过轮换簇内簇头节点来均衡簇内能量消耗，优化局部网络拓扑结构。LEACH是一种典型的角色轮换拓扑维护算法，通过概率随机轮换簇头，使网络中节点等概率担任簇头，有效地节省节点能量。

另一种节点角色轮换为睡眠/工作，它通过调度那些未参与通信的网络节点进入睡眠状态来节约能量，实现延长网络生命周期的目的。如SPAN通过维护组成骨干基础架构的节点来保持网络的连通和转发能力。MESH-CDS中，最大独立集中节点故障时，通过转换节点角色来修复最大独立集并维护一个连通的骨干网络。此外，CCP通过对节点角色的轮换维护网络拓扑的覆盖和连通，它是一种典型和有重要影响的基于角色转换的拓扑维护协议。其基本思想主要是通过保持一个足够大的工作节点子集来维护网络k-覆盖。

在该算法中，每个节点扮演两个角色，即睡眠节点或工作节点。每个节点利用ks-覆盖规则和接收其邻居节点的HELLO报文信息来进行本地决策以确定是否需要进行角色轮换。

[#page#]

CCP能够将网络配置到指定的覆盖度与连通度，并通过角色轮换来维护网络的覆盖和连通，其可灵活地应用于不同的网络环境。但是，CCP 需要较为精确的位置信息，并且当发射半径小于感知半径的2倍时，不能保证网络的连通性。

由上可见，基于角色轮换的技术通过调度那些未参与通信的网络节点进入睡眠状态或选择剩余能量多的节点担任簇头来维护网络连通和覆盖。睡眠节点或非簇头节点消耗的能量很小，且它们比工作节点或簇头节点的数量大得多，所以网络的能量消耗性能十分优越。而且，通常算法仅需要局部信息，通过本地进行决策，计算复杂度低。然而，基于角色轮换的拓扑维护技术仅从局部对网络进行维护，不能从网络的整体出发，导致整个网络拓扑非最优甚至不连通。

3.2 基于拓扑重构的拓扑维护

基于拓扑构建的拓扑维护技术通常周期性调用拓扑构建过程或专用的维护算法来重构网络的拓扑。如DKM协议，当节点密度| SNS | k 时运行拓扑维护过程，有效地恢复和维护网络的k -连通。SMSS算法中，当节点u 发现某个节点m 失效时，它将检查m 是否为它确定的邻节点，如果是，重新运行拓扑控制算法来维护网络拓扑结构。

EETMS算法中，一旦网络发现故障节点，触发拓扑维护过程，并最终构建一个能量有效的局部拓扑，且其链路长度之和最小。EETMS 是一种典型的专门用于拓扑维护的基于拓扑重构的技术。其思想是仅利用直接的邻居节点来响应拓扑维护过程，且节点将大部分能量花在用来估量网络连通和寻找最小能量拓扑，而不是用于转发数据。

EETMS 算法首先提出了一个判断网络连通的标准。在一个二维的欧几里得空间里，网络拓扑用一个图G(V， E) 表示，其中V 为节点集，节点个数为n .E 为所有边e(i， j)的集合，其中e(i， j) 表示节点i 和j 彼此互为邻居。则网络拓扑可用图G 的邻接矩阵A 表示，且矩阵的每个元素ai， j可表示为：

接下来，令

，如果对于任意的i， j s 有， 0 i j s ，则图G(V， E) 连通。因此，维护算法通过计算si， j 来构建一个连通的拓扑。当网络运行中发现故障节点u ，触发拓扑维护过程。此时故障节点u 的邻居集为u ，节点数u m .EETMS能够维护网络的连通，并确保链路长度之和最小。但算法中需要构建故障节点的邻接矩阵，并根据该矩阵来计算网络的连通。在高密度网络中，需要大量的存储空间和高的计算复杂度。此外，算法中并没有描述故障节点检测机制，无法知道拓扑维护算法的触发频率。

总之，基于拓扑重构的拓扑维护技术可能需要多次动态运行拓扑构建或维护算法，通常需要更多的时间和能量消耗。然而，拓扑构建过程在它每次运行时通常选择最优或接近最优拓扑，从而导致生成比基于角色转换拓扑维护技术更好的网络拓扑结构。

3.3 混合的拓扑维护

混合的拓扑维护技术结合了基于角色轮换和拓扑重构的拓扑维护。该类拓扑维护技术周期性地采用节点角色转换和拓扑重构策略。首先，混合的方法采用角色转换的维护方法对网络的局部拓扑进行维护，实现网络一部分(如一个簇)的优化。随着网络的运行，作为数据转发的骨干网络能量消耗较快，造成网络内的能量消耗不均衡，于是混合技术采用拓扑重构的维护技术来重构整个网络的拓扑，两种方法周期性地交替运行，有效地均衡网络能量消耗。DFTM采用角色轮换的方法对局部拓扑进行维护，而采用拓扑重构的方法来对整个网络拓扑进行维护。

可见，混合的拓扑维护技术可以使用基于节点角色轮换无法使用的资源，而且网络持续的时间比基于拓扑重构方法要长，因为轮转过程比一个完整的新构建过程消耗的能量少。但是，混合技术由于触发条件的选择，一个性能严重下降的拓扑可能持续很长一段时间，在它到达拓扑重构恢复点前，这将影响连通和覆盖的服务水平。