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

标

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

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

　　（1）网络生命周期

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

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

　　（2）覆盖和连通

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

　　（3）安全和故障容忍

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

　　（4）能量效率和收敛时间

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

　　（5）能量均衡和可扩展性

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

　　2 拓扑维护模型

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

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

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

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

　　（1）触发器

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

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

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

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

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

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

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

　　（2）决策器

决策器主要确定采用何种策略来维护当前的网络拓扑结构，它是拓扑维护的核心。拓扑维护策略可以分为两种，一种是基于角色轮换的拓扑维护策略，也就是说通过对网络中节点的角色-如睡眠/工作、