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

3 拓扑维护研究现状

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

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

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

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

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

　　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采用角色轮换的方法对局部拓扑进行维护，而采用拓扑重构的方法来对整个网络拓扑进行维护。

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

　　3.4 拓扑维护算法分类

　　拓扑维护算法分类可以从许多方面来进行，如可以根据设计目标将拓扑维护分为确保覆盖、连通的拓扑维护，故障容忍和安全的拓扑维护，能量消耗均衡的拓扑维护等。此外，很难将目前研究的设计目标和设计要素分开，导致分类可能并没有精确地反映设计者的最初意图。为了尽量避免该问题，本文根据第2 节设计的拓扑维护模型对现有的拓扑维护算法进行分类，如表1 所示。

　　4 存在的问题和发展趋势

　　从以上可见，无线传感器网路拓扑维护研究取得了一些成果，但其仍然存在一些问题。此外，随着无线传感器网络的实际应用，如何确保拓扑维护的安全性以及如何有机地与其它层互相融合将是拓扑维护算法的主要发展方向。

　　（1）缺乏实际的拓扑维护实施

　　尽管许多研究机构致力于本文提到的拓扑维护技术研究，且许多的理论和基于仿真的证据表明拓扑维护算法或协议能有效减小网络的能量消耗从而延长网络的生命周期，但是迄今为止，很少有实际的网络实施来证明拓扑维护事实上能被用于实现这些目标。

　　（2）未能量化拓扑维护频率

　　拓扑维护算法要考虑拓扑重构产生的报文开销和优化拓扑的质量之间的权衡，一般情况下，产生一个高质量的优化拓扑，就需要频繁执行拓扑维护协议。另一方面，每一次执行拓扑维护协议将导致相当数量的报文开销。目前，很少有研究仔细考虑两者之间的权衡关系。

　　（3）安全的拓扑维护

　　目前的大部分拓扑维护协议通常假设传感器部署在一个可信的、非敌对的环境中，并没有考虑到节点内部或外部攻击的影响。而无线传感器的实际应用尤其是商业和军事应用，存在各种类型的恶意行为和攻击，对手可以利用使用的拓扑维护算法来对网络发起攻击。因此，必须采取相应的安全策略，提高拓扑维护算法的鲁棒性，使其能防御各类攻击。

　　（4）跨层的拓扑维护

　　无线传感器网络的生命期优化目标涉及从底层硬件到上层应用的所有环节， 因此仅通过拓扑构建甚至拓扑维护往往难以达到最理想效果，需要拓扑控制（构建与维护）与其它上下层协议紧密耦合协同。因此，拓扑维护的设计也必须兼顾各层协议的特点，以便在无线传感器网络体系结构中扮演好承上启下的重要角色。

　　5 结论

　　本文对无线传感器网络拓扑维护研究现状进行了综述，并对当前研究中存在的普遍问题进行了分析和概括。从目前的研究现状来看，拓扑维护研究主要以基于角色轮换和拓扑重构为主，已经提出了CCP、EETMS等算法。但目前的研究还存在模型理想化、缺乏实际的拓扑维护实施以及未能量化拓扑维护运行频率和缺乏算法性能有效度量等问题。

　　总之，拓扑维护算法已经取得了初步的研究成果，但专门面向拓扑维护的研究还太少。而且，目前的研究未能考虑实际应用所面对的如环境地形、噪音干扰、恶意攻击等诸多因素。可见，拓扑维护还有许多问题需要进一步研究，特别是需要探索面向实际应用的安全和跨层的拓扑维护技术。