无线传感器网络拓扑修复算法综述

2018-08-17晓璇

计算机工程 2018年8期

晓璇, ,,

(南京邮电大学 a.宽带无线通信与传感网技术教育部重点实验室; b.江苏省无线通信重点实验室,南京 210003)

0 概述

无线传感器网络(Wireless Sensor Network,WSN)[1]是由大量密集部署在目标区域的节点构成的一种自组织网络应用系统[2]。该系统由大量小规模、低成本的传感器构成,将在目标区域采集到的数据汇集到基站[3]。WSN起源于军事领域的应用,近年来,其在环境监测、医疗护理、火灾监测、交通监控等领域也得到广泛的应用[4]。

由于传感器自身资源及能量的限制,传感器节点易受到损坏,关键节点的损坏将导致网络被分割成不连通的分区,给实际应用带来不便。无线传感器网络的故障一般分为小规模故障和大规模故障,小规模故障往往源于个别传感器能量耗尽,导致邻居节点之间无法连通;大规模故障往往源于恶劣环境下,如森林中,由于失火导致大量节点失效,造成网络被分割成不连通的分区。重新将网络连通对于延长网络生存周期尤为重要。对于网络修复问题的研究业界已经取得了一定的进展,拓扑图论中有许多算法,如最短路径算法、搜索算法、生成树算法等在网络修复中也得以应用[5]。本文分析各类无线传感器网络修复算法,并针对不同的网络故障规模,对以往的研究进行分类和总结。

1 网络修复算法分类分析

在研究无线传感器网络修复算法时,需要根据不同的应用需求采用不同的系统模型。图1对现有的网络修复算法进行分类与总结。根据网络破坏规模的不同,可将已有的算法分为小规模故障修复算法和大规模故障修复算法两大类。

图1 网络修复算法的分类

在小规模故障中,根据修复算法的触发条件,可以将网络修复算法分为不区分节点重要度的算法和区分节点重要度的算法两类。如RIM[6]、MCDS[7]算法,只要节点发生故障就立即触发修复程序,这容易造成不必要的修复,增大开销。DCR[8]、DCRS[9]等算法先对节点进行重要度判断,只有当失效节点为关键节点时才启动修复算法,即为区分节点重要度的算法。该类算法可以从4个方面进行分类:1)根据关键节点的判断时间分类;2)根据关键节点的判断方法分类;3)根据重定位节点移动方式分类;4)根据算法实现角度分类。在大规模故障中,可以根据算法的实现角度分为2类:1)集中式算法,网络中的节点可以提前知道每个分区的信息,有利于修复算法的执行;2)分布式算法,节点对分区的数目以及位置等信息未知,可以有效降低消息成本。下面对具体算法的适用环境及优缺点进行分析与比较。

2 小规模故障的拓扑修复算法

该类算法主要考虑单个节点故障的情况,网络通过故障节点的邻居节点的自身移动完成网络修复,而源宿节点的寻路过程需要消耗能量[10],因此,必须尽可能减少移动距离来延长网络的生存时间。

根据算法触发条件的不同,小规模故障修复算法可分为2类:1)不区分故障节点重要度的算法;2)区分故障节点重要度的算法。前者适用于对网络覆盖率要求较高的网络,为了降低网络覆盖率的损失,只要有节点故障,就启动修复算法。后者适用于将网络连通性作为修复目标的网络,该类算法先对故障节点的重要度进行判断,仅当故障节点为关键节点时,才启动修复算法,如此可以有效减少节点重定位过程中的能量消耗,避免不必要的修复。下面针对这2类算法给出详细的分类。

2.1 不区分故障节点的重要度

冗余节点移动算法[11]、MCDS[6]算法、RIM[7]算法等修复算法不对节点的重要度进行评估,这样虽然可以在一定程度上降低消息传输的成本,但是会造成不必要的修复,增大网络中重定位节点的数目,导致节点总移动距离以及网络修复时间的增加。

当有节点失效时,冗余节点移动算法调用网络中的冗余节点移动到失效节点位置。该修复方法复杂度低,但只适用于节点密度较高的情况。RIM算法中失效节点的一跳邻居节点向失效节点移动,直到这些邻居节点可以互连。如图2所示,当B、A、G、H节点检测到节点F故障后,开始向F移动,同时需考虑自身与邻居节点的距离、度等因素。该算法在网络规模增加的情况下,节点的总移动距离会大幅增加。

图2 RIM算法拓扑结构

2.2 区分故障节点的重要度

提前对节点进行重要度判断,针对关键节点和非关键节点的故障采取不同的修复措施可以减少不必要的修复,缩短移动距离,但是会增大消息传输的成本。下面根据关键节点判断时机、判断方法、候选节点选取规则和移动方式的不同对此类算法进行分类。

2.2.1 根据关键节点判断时机的分类

1)主动修复

主动修复方法[8-9,12-14]是指在节点未失效之前先进行重要度判断,并将该信息传递给邻居节点,当节点失效时立即修复,可以有效提高修复效率。

DARA[12]算法根据节点的度和与故障节点的距离给每个故障节点选择候选节点,并级联地用候选节点来取代故障节点。该算法容易出现过度替代,且由于不提供关键节点的判断机制,每个节点需要知道整个拓扑的信息。PADRA[13]算法中每个节点存储自身两跳范围内的节点信息,采用最小连通支配集(Connected Dominating Set,CDS)将节点区分为支配节点和被支配节点2类,并以此给出割点的确定方案。如果割点的邻居节点中存在被支配节点,则当割点失效时该节点邻居节点中的被支配节点取代割点的位置;否则,每个割点找到最近的邻居节点来取代自己,直到这个邻居节点是被支配节点为止。相对于DARA算法来说,PADRA算法总移动距离较少,降低了能耗,延长了网络的生命周期,但是该算法引入的深度优先搜索(Depth First Search,DFS)算法复杂度较高,增大了消息传输成本。

2)被动修复

被动修复方法[15-17]是指在节点失效后才采取相应的措施进行网络修复。CCRA[15]、LeDiR[16]算法为被动修复算法,只需要判断失效节点的重要性,这可以有效降低消息传输成本,但会增大网络修复时间。LeDiR[16]重定位尽可能少的节点,通过块移动来完成网络修复,确保任何一对受影响的节点相对故障前的状态路径是没有扩展的。被动修复方法分为4个步骤:(1)故障检测;(2)最小块确认;(3)取代故障节点;(4)子节点移动。该算法降低了参与移动节点各自的移动距离,但是增大了总移动距离。此外,该算法采用的块移动方法增大了平均移动节点数目以及能量消耗。

2.2.2 根据关键节点判断方法的分类

通过一跳邻居节点来判断网络中的节点是否为关键节点,可以降低算法的复杂度,有效减少消息传输的成本,在一定程度上降低能量消耗。DCR[8]算法根据一跳邻居节点的位置信息提前确定关键节点,并在邻居节点中选择候选节点,当节点失效时,候选节点就会启动网络修复程序。该算法采用提前预测与及时响应相结合的方式,适用于对时延有限制的应用。如图3所示,A为非关键节点,即使节点A故障,它的一跳邻居节点相互之间仍然为连通;节点F的故障会导致它的邻居节点被分割成2个不连通的分区,因此,节点F为关键节点。由于该算法仅依赖于一跳的邻居节点信息来确定关键节点,可能出现所选择的关键节点并非为割点的情况,造成不必要的修复。

图3 关键节点确定

在确定关键节点时,既需要依赖尽可能少的局部信息来减少能耗,又需要保证消息的价值。仅根据一跳邻居节点判定关键节点易造成误判,采用DFS算法复杂度较高,因此,C2AM[9]、CCRA[15]以及DCRS[9]提出根据两跳邻居节点的信息来判断节点是否为关键节点。DCRS[9]算法根据一跳邻居节点的位置信息和部分两跳邻居节点来判定关键节点,在消息传输的成本和消息的价值之间寻求平衡。此外,DCRS通过设定阈值改善了级联算法,限制了节点重定位的范围,降低了重定位中长路由的风险,有效减少了总移动距离以及移动节点数目。

PADRA算法通过确定网络的CDS来判断节点是否为关键节点,也存在算法假设每个节点对该信息已知,如DARA算法和CVTR[14]算法。在此类算法中,每个节点需要提前知晓整个网络的拓扑信息,具有一定的局限性。与其他算法不同的是,CVTR算法针对割点和非割点采取不同的修复措施,而并非忽略非割点的故障,这样可以有效降低覆盖损失率,使得修复后的网络覆盖率达到90%,且总移动节点数目较少,但是修复过程中总移动距离较大,能耗过大。

2.2.3 根据重定位节点移动方式的分类

块移动[16]是指根据节点原先的位置,分区中的领导节点向着失效节点的位置移动,分区中的其他节点保持原先的链路拓扑跟随着领导节点的方向移动,该类算法移动节点数目过多,总移动距离较大。

级联移动[17]相对块移动来说,只需要移动相对较少数量的节点,此外块移动需要分区中的每个节点知道各自需要移动的位置,增大了消息传输的成本,而级联移动中节点只需知道局部范围内邻居节点的信息。根据研究目标的不同,不同算法的级联移动策略也不同,如DARA需要根据邻居节点的度和距离选择候选节点,PADRA根据动态规划选择需要重定位的节点,DCRS根据CDS确定关键节点和候选节点,并给定阈值来确定如何实现级联移动。

2.2.4 根据算法实现方式的分类

集中式算法[6,11]是指在算法执行时,节点相互之间存在联系,以快速地完成网络修复,算法实现比较简单。缺点是每个节点都需要知道整个网络的拓扑信息,会造成消息传输成本过大,算法效率随着问题规模的增大而增大,仅适用于小规模的网络。

局部分布式算法[17]是指局部地以一部分为单位分别执行算法,每个节点仅需要保存局部节点的信息,减少了消息传递,可以有效延长网络的生存时间,而且算法的效率随着网络规模的增大变化不大,因此,该算法适用于大规模的网络,缺点是算法实现相对复杂。

2.3 算法分类与归纳比较

大多文献都是在某些限制条件下提出了网络修复算法,只能针对某些性能进行改善。表1对已有的不同算法实现方法和性能进行了比较。除了上文提到的参数之外,总移动距离是指从网络修复开始至整个网络连通参与移动的所有节点的总移动距离。总移动节点数目是指参与到网络修复过程中的总节点数目,当大量的节点移动时所需要消耗的能量较多,但是当较少的移动节点完成网络修复时,又会造成大量的通信开销,使得移动节点的能量消耗过大,造成节点之间负载的不平衡,如CCRA[15]算法。因此,针对单个节点故障的网络修复算法,研究的重点是找到总移动节点数目和总移动距离之间的平衡,在完成网络修复的同时延长网络的生存时间。

表1 单个节点失效算法的性能比较

3 大规模故障的拓扑修复算法

由于传感器节点的资源和能量的限制使得传感器节点不适合长距离移动,因此通过邻居节点重定位完成网络修复只适合处理单个节点故障的情况,当网络出现大规模故障产生分区时,需要往分区之间填充中继节点(Relay Node,RN)来完成网络修复。该类算法的主要目标是减少所需RN的数目,一般假设RN相对普通的传感器节点来说具有更高的能量以及更大的通信范围。根据对网络整体拓扑信息的已知情况,从算法实现角度,将此类算法分为集中式算法和分布式算法。

3.1 集中式算法

在网络出现大规模故障的情况中,已有的多数算法均为集中式算法,此类算法的优点在于网络中的节点可以提前知道每个分区的信息,包括分区的数目和位置,有利于修复算法的执行,但是集中式算法的消息成本较大。下面针对此类文献中的代表性算法进行介绍。

3.1.1 蜘蛛网算法和ORC算法

大部分算法只关注减少RN的数目,导致新放置的RN大多为割点,网络容易再次出现分区。为了减少割点所占的比例,蜘蛛网算法[18]与ORC算法[19]提出通过Graham Scan算法求得凸多边形,然后以轮的方式迭代确定RN的放置位置。

蜘蛛网算法建立了一个蜘蛛网的拓扑图,从每个分区到重心部署节点,直到所有的分区连通。如图4所示。其中,实线代表中继节点之间的连线,虚线代表分区代表节点之间或者分区代表节点和中继节点之间的连线。从分区Pi往重心依次放置中继节点Ri。在朝着重心部署RN的过程中,为了增加连通的强度,一个分区至少应该和它的左右2个邻居分区相连接。该算法以增加RN的数目为代价获得了多个可取的功能,不仅增加了网络的总覆盖率,而且减少了割点所占的百分比,增加了平均节点的度,可以更好地平衡RN的流量负载分布。ORC算法通过每一轮寻找网络分区的凸多边形和Steiner点(Steiner Point,SP)的方式确定RN的位置。第1轮求得的SP为第2轮求凸多边形的初始节点,以此类推,直到整个网络连通。相对蜘蛛网算法,ORC算法降低了RN的数目,但是网络对故障的容忍性较低。

图4 蜘蛛网部署中继节点的算法

3.1.2 CIST算法

由于分区的大小以及分区间的距离具有随机性,因此每个分区选取一个代表节点会造成RN的不合理使用。CIST[20]算法提出需要针对连接的不同分区选择不同的代表节点。CIST算法首先求得各个分区建立的最小生成树,然后确定所有可能的三角形集合,选定权重最小的三角形,形成Steiner最小树,最后将得到的树和未连接的分区通过最小生成树连接起来。CIST算法采用迭代寻找连接3个分区的最佳三角集合的方法,相对于沿着最小生成树的边放置RN的方式,该算法所需的RN的数目较少,但是复杂度较高。

3.1.3 特殊应用场景下的修复算法

有些文献针对特定的应用场景提出了网络修复算法,如虚拟骨干网修复算法[21]和移动与固定RN混合部署算法[22]。虚拟骨干网修复算法针对支配节点出现大规模故障的情况,通过给每个分区重建支配集CDS来完成网络修复。

当缺少足够多的RN来连接所有的分区时,一些RN可以用作移动数据采集器(Mobile Data Collector,MDC)来访问多个分区。文献[22]提出了固定和移动的RN数目动态变化的策略,先假定所有的RN均为MDC,并通过迭代来降低MDC的数目。该算法首先找到成本消耗最小的分区安置固定的RN,然后根据阈值来检测是否满足覆盖限制条件,若满足,则对网络分簇,使得每个MDC访问一个簇中的每个分区。该算法在满足覆盖限制条件的同时可以使最大移动距离最小化。但是,MDC实现的是间断性的网络连接,不可避免地在数据采集和传输的过程中会出现时延,在实时的应用中这些数据是无效的。

3.2 分布式算法

集中式算法要求网络中的节点需提前掌握整个网络的拓扑信息,但在恶劣环境中有时难以获得该信息,此时需要采用分布式算法进行网络修复。在分布式算法中,通过RN的安置来了解整个网络拓扑,节点不需要知道全部拓扑信息,使得修复更加迅速,消息成本较低。但是由于分布式算法自身条件的限制,该类算法复杂度较高,且对RN配置有较高的要求,如需要携带摄像机来观察周围节点的分布情况。

3.2.1 CORP算法

文献[23]提出的CORP算法将网络划分为等大小的网格,通过每一圈向中间靠拢来实现网络修复。具体实现步骤如下:

1)计算每个边界节点的邻居节点与其他分区上一圈的边界节点的距离,取最小的小区作为最佳小区,然后确定新一圈的边界节点,以此循环下去直到所有分区布置的最佳邻居节点都连通。

2)通过优化布局节点,使用尽可能少的RN实现连通。

该算法经过RN的安置和裁剪2个步骤有效地减少RN的数目,降低了通信能耗。但是该算法并未明确给出代表节点的选择方案。

3.2.2 DORMS算法

DORMS[24]算法从每个分区向网络中心放置RN,只要RN到达彼此的通信范围内,则认为分区连通。算法分为2步:

1)初始化RN安置过程:每个分区朝着网络重心的位置放置RN,根据每个分区的标号以及距离中心点的位置给每个RN标号,距离分区最近的节点可以确定分区的位置,并在任意2个分区和重心之间确定MST。

2)重定位RN的位置:该部分通过重定位RN的位置来减少RN。

该算法不仅连通了网络,而且生成了更多有效的拓扑,增加了连通的平均度,平衡了通信负载,但是需要的RN数目较多。

3.2.3 博弈论和RPFP算法

以往大规模故障修复的算法均先确定RN的位置然后直接放置RN,修复的主要目的是减少RN的数目。但是考虑到实际应用,在确定的位置投放RN并不实际,因此,文献[25-26]提出通过无人机在大致的故障区域投放RN,然后将RN移动到需要放置RN的位置来完成网络修复。该类算法除了需要确定RN的放置位置,也应考虑RN的移动问题,这将增大算法的复杂度。

博弈论[25]算法提出每个RN需要包含摄像头来确定自己的移动方向,根据分区的概率密度函数(Probability Density Function,PDF)来决定需要连接的目标分区,具有高PDF的分区可以尽早修复使之成为已连通分区中的一员,如果和RN连通则具有和已连通分区相同的纳什均衡值,直到整个网络具有相同的均衡值时证明整个网络已连通,修复过程停止。RPFP[26]算法提出每个分区采用凸多边形算法来确定代表节点,通过寻找三角形中的0斜率点确定RN的放置位置。算法使用贪心方式来放置RN,因此,修复时间短,但是可能出现多个RN同时向一个目标位置移动的情况,直到RN感知到彼此存在时才计算各自针对目标位置的优先级,在一定程度上造成了RN资源的浪费。

3.3 算法性能比较

大规模网络破坏的修复算法一般以所需RN的数目、平均节点的度以及平均路径长度等性能参数作为修复目标。所需RN的数目表示修复分区过程中的总成本,一般希望可以最小化RN的数目;平均节点的度指网络的鲁棒性,度越高可以更好地平衡负载,降低出现再次故障的概率;平均路径长度(Average Path Length,APL)指代修复后分区之间的路径长度,较小的APL值可以有效地降低数据延迟,适用于对实时性要求较高的网络。

图5以RN的通信半径为横坐标,对不同的算法针对以上3个性能进行了比较,由于不同算法性能修复目标的侧重点不同,因此每种性能参数只对部分算法进行对比。蜘蛛网算法虽然所需RN的数目较多,但是修复后网络节点平均度较高,适用于对网络稳定性要求较高的场景;RFPF算法和ORC算法平均路径长度较短,适用于对实时性要求较高的网络;CORP算法和DORMS算法为分布式算法,较好地达到了RN数目和平均节点的度2个性能之间的平衡。此外,固定和移动节点混合部署算法中假设RN数目固定,博弈论算法适用于传感器节点数目较少的小规模网络。