基于最小连通支配集移动的WSANs连接恢复算法

周 杰，姚 雷，杜景林

近年来，无线传感器与执行器网络(wireless sensor-actor networks，简称WSANs)在应用层面引起广泛的兴趣.WSANs［1］网络由大量传感器节点(sensor)和少量执行器节点(actor)构成，分布在特定检测地理区域中，特别是一些偏远、环境恶劣、人类无法干预的地区，传感器用来环境感知、简单处理以及转发数据到基站.执行器节点根据传感器节点汇报的事件和收集的数据执行相应的分配任务［2］.执行器节点类似于移动的机器人、无人驾驶的车辆［3］等，都是自主和协作的实现应用程序中的任务.在连通的WSANs中，一个或多个执行器节点出现故障可能会导致其他节点或通信链路失效，如果受影响的节点之间的替代路径不可用，网络就形成分区，节点丧失工作能力.这种情况不仅会阻碍节点间的合作、破坏实时连接的要求，也对实际应用造成不良后果.在WSANs所提供的远程设置服务使用额外的资源部署来恢复连接是不切实际的，重新部署节点将成为最好的恢复选择［4］.因此，WSANs应该具备容错能力，能以一种分布式的、及时的、节能的方式自我恢复.首先，恢复过程采用分布式方法，因为这些网络通常是自治的;第二，为了对监测到的事件迅速反应，恢复过程需要足够快;最后，恢复过程中的能源开销应尽量减少，以延长网络寿命［5］.

在恢复WSANs网络连通性方面，很多文献已经从各个方面进行了深入的研究，主要采用通过移动执行器节点的位置来恢复连接.文献中现有的方法可以归类成节点的级联运动［6］和块体运动［7］.为了避免过度的状态更新的开销和更好地恢复连接过程，之前的工作都是依靠于保持一跳或两跳路由表并决定参与恢复节点的标准［8－10］.文献［8］要求每个执行器节点保留两跳邻居信息.挑选失效节点的一个邻居来启动恢复过程，尽可能降低移动开销和交换消息数量.在割点失效时，分布式执行器节点恢复算法(distributed actor recovery algorithm，简称DARA)指定度最小的邻居启动恢复连通性过程，而分区检测恢复算法(partition detection and recovery algorithm，简称PADRA)首先标识出支配节点以监听割点，这个支配节点不直接移动到失效节点的位置.尽管如此，他们均使用分布式算法，需要保留两跳邻居的信息，增加了通信开销.Younis等人提出了一种名为内缩移动恢复算法(recovery through inward motion，简称RIM)［9］.当一个节点发生故障时，其邻居向它的位置移动，使他们能够相互连接，这种递归重置过程适用于处理任何节点失效时其邻居的移动.但是该算法没有区分割点与叶节点的情况，带来不必要的恢复过程.

论文设计了一种基于最小连通支配集移动的连接性恢复算法(MCDSR)，由于网络分区是割点(关键节点)失效引起的，先用基于深度优先的割点搜索算法判断节点是否是割点.一旦割点确定，再指定适当的邻居作为割点的备份节点来监听失效.备份节点检测到任何故障后，在其分区中选择一个最小连通支配集级联运动替换失效节点.替代节点不是直接移动到失效节点的确切位置，它只是移动到某个最佳位置来管理多个传感器，其子节点也相应移动与先驱节点保持连接，论文将给出最佳位置的计算方法.MCDSR的目标是确保执行器节点的覆盖度减少最少，恢复过程中造成的节点移动和通信开销最小.

图1 WSANs系统模型Fig.1 The system model of the WSANs

1 WSANs系统模型

1.1 系统模型

执行器节点是随机部署在感知区域，一旦部署完成节点就试图发现其他节点，并通过现有的技术形成一个连通的网络.执行器节点为了在更大的区域执行任务或者提高网络的连通性，可以根据应用的需求移动.图1显示一个WSANS系统模型.

图1中，一个执行器节点收集来自其邻居传感器节点的数据并与其他的执行器节点协作，其中一些关键执行器节点可以通过很长的通信链路(卫星)连接远区域的命令中心，来报告它的活动状态和探测到的事件.

1.2 问题描述

执行器节点的失效对网络的连接可能是有限的也可能是剧烈的.如果失效的节点是一个叶节点，那么对网络的连通性影响就不那么大.如果失效的节点是一个割点，起着连接多个网络分隔区的作用，将会对网络连接产生严重影响.图2显示一个内执行器网络.

图2 内执行器网络Fig.2 Inter-actor network

在图2中可以看出，一个叶节点13的失效不会影响网络的连通性，同样的17、18由于是双连通的也不会产生影响.但由于执行器节点6是割点，会将网络分隔成两块以上的不连接的区域.

为了容错割点的失效导致网络的分隔，通常采取两种策略:提前预防和实时恢复.提前预防策略致力于在网络拓扑结构初始形成阶段提供容错.在网络中建立k－连通的拓扑结构，使每个节点都有至少有K条到达其他节点的独立路径，这样的设置可以使网络能够同时容忍K－1执行器节点失效.但要注意的是，这种高度连通的网络需要部署大量的执行器节点和高能耗，在实际中是不可取的.另外，也可能限制执行器节点的移动从而影响应用层面的功能，实时恢复实现从检测到执行器节点失效到恢复的过程.但由于它是异步性，本身又是被动的，很难预测移动的位置和范围，所以需要设计一种算法来根据失效节点的影响自适应计算最佳位置和范围.

2 MCDSR恢复算法

基于最小连通支配集移动的连接性恢复算法MCDSR，该算法不要求时钟同步，这样可减少大量通信产生的能量消耗，实现网络的能量有效性.同时该算法为分布式，避免了集中式算法无法针对网络改变及时调整调度的弊端.

2.1 割点识别阶段

如果删除图中某点以及它所连接的边后，该图的连通分支的数目增加，则被删除的点称为图的割点.割点是WSANs网络拓扑中非常重要的节点，它与网络连通性关系密切.割点的存在使得WSANs网络的连通存在薄弱环节.一旦割点失效，将直接影响网络的性能，因此如何在网络拓扑中检测到割点显得尤为重要.接下来研究一种基于深度优先的割点搜索算法，在连通图上寻找割点.对图G(V，E)进行深度优先遍历，选择任意节点作为开始节点，对某一邻居节点遍历，并沿着该邻居节点继续对更深层次的邻居节点遍历，如果节点v的所有邻居节点都被遍历过，则返回到v的祖先节点重新按照上述过程深度遍历，直到所有节点都被遍历，由此得到最小遍历生成树.遍历时需要记录每个节点的两个信息:visit_num［v］和 small［v］.visit_num［v］为生成树中前序遍历时的节点序号.small［v］=min(visit_num［v］，visit_num［n］，small［m］)，m是v在深度优先生成树上的子节点，n是v在深度优先生成树上由回边连接的祖先节点，(m，v)，(n，v)均是图中的边.对于点 v，如果存在子节点 m，有 small［m］≥visit_num［v］，表明 m及其子孙均没有指向v祖先的回边，则v是割点.通过上述基于深度优先的搜索算法，可以找到无向连通图中的割点.使用邻接矩阵作为图的存储形式且图中节点个数为n时，如果算法中对邻接矩阵的查找时间复杂度为O(e)，那么该割点查找算法的总的时间复杂度为O(n+e)，因此该算法具有较好的时间复杂度和空间复杂度.

2.2 备份最小连通支配集选择与失效监测阶段

2.2.1 备份最小连通支配集选择

一旦割点确定，它的失效就会造成网络分成几个分区块，下一步就要在这些分区块中选择最小的连通支配集块作为他们的备份节点.指定备份支配集的目的是为了对割点的故障做出迅速反应，避免该故障对网络造成分区.

为避免额外的通信开销，执行器节点只保留最少的邻居状态信息(一跳邻居).由于一个关键节点失效时与其邻居断开，备份执行器节点确定后提前报告关键节点发生故障.一个节点可以作为多个执行器节点的备份.一跳邻居中备份节点的选择基于以下标准［11］:

简析：观察装置左侧加入溶液中含有,流出的溶液中含有 Ce4+、,说明左侧发生了氧化反应;同样右侧变化是,发生了还原反应。这些信息可作为判断电极反应的证据,左侧是阳极,右侧是阴极,进而写出电极反应式。要特别注意该电解过程中阳离子Ce3+在阳极上被氧化,阴离子在阴极上被还原,与常见的电解反应比较有一定的特殊性,分析时不要被所谓“常识”所迷惑,这就是突破认识误区。事实上,只要抓住电极反应的本质要素,就不会被“常识”或“特殊”所迷惑。

(1)一跳邻居位置(NP):割点失效，就从它的一条邻居列表中找到离它最近的节点.

(2)一跳邻居节点的节点度(AD):移动一个有许多邻居的节点的影响是巨大的.因此，搜索到一跳邻居节点度最小的节点，这将限制级联移动的范围，从而降低恢复过程的开销.

(3)执行器节点的ID:在失效节点一跳邻居中，可能有两个或两个以上的执行器节点离失效节点最近并且有相同的节点度.这时有着ID号大的节点将被选择去恢复连接.

根据以上标准如果割点6失效，图3中圆圈圈起来的将是备份的最小连通支配集.

图3 选择最小的CDSFig.3 Select the minimal CDS

2.2.2 失效监测

执行器节点会定期发送心跳消息给它们的邻居节点来确保它的功能有效，同时报告自己的更新状态.心跳消息包的丢失可作为节点失效监测的一种手段.

节点与其邻居交换心跳消息作为网络操作的一部分，以更新自己的状态，通过这些消息通知选定的备份节点.一个执行器节点一旦收到备份通知，它开始通过心跳包监测割点.丢失一定数量的连续心跳包时，备份节点视割点失效.

2.3 恢复过程

尽管非割点的失效不会对网络连通性造成任何问题，但它却会产生其他问题，如形成覆盖漏洞、扰乱某个特定区域的数据收集等.在这种情况下，根据应用级别的要求，这些问题仍需要处理.论文在恢复的过程中首先考虑到执行器节点连接的恢复，同时也考虑到覆盖漏洞的修复.

2.3.1 最佳位置确定

定理1 若要保证移动的执行器节点距离最短且由于移动覆盖面积减少最小，则移动执行器节点应放置在AC边A的中垂线上.

图4 最佳位置计算模型Fig.4 The calculation model of best position

证明 如图4所示，记节点移动到最佳位置形成ABCD的面积为S1，为了使由于节点失效导致的覆盖率减少到最小，保证修复连接移动节点数目最少且移动的距离最小，S1的面积应达到最大.ΔABC的面积为 S2，ΔAEC的面积为 S3.由于ΔABC的面积S2是固定的，所以要使得S1最大，需要S3取最大值.过点E做边AC的垂线EF，垂足为F，则其中，||、||分别表示线段AC、EF的模值.由于AC为固定值，要使S3最大，需EF取最大值.假设 AE≤ CE，相应地，有AF≤CF.由于AC=AF+CF，所以AC≤2CF，即

作为新的边缘节点，移动节点E要保证与C的通信，故有CE≤Rc.在ΔEFC中由勾股定理可知

从而在CE取最大值Rc，CF取最小值AC/2，EF可取最大值，此时S3最大.因为CF=AC/2，故F为AC的中点，因此移动节点的位置E点位于AC的中垂线上移动距离最短，这时才可能获得最大的感知面积，覆盖减少率最小.

2.3.2 恢复过程描述

图5显示了当执行器节点6失效时最小节点块怎样移动来恢复连接.显然，节点6是一个割点并为其备份最小连通支配集来检测失效，节点5是在最小连通支配集中失效节点6的一跳邻居节点.图5(a)～(b)确定最佳位置点，使失效节点的一跳邻居节点向最佳位置点移动.在图5(c)中，节点5向最佳位置点移动，并发送恢复消息给它的子节点.在节点5移动过程中，其子节点产生级联运动始终与节点5保持连接，见图5(d).子节点的级联运动对当前的拓扑连接不产生影响.在图5(e)中子节点5，7移动前通知它们的子节点移动保持连接.重复以上步骤直至整个网络连接恢复.

图5 恢复过程图Fig.5 Restoration process diagram

3 算法仿真结果与分析

对提出的算法进行仿真，并将其性能与先前文章提到的RIM算法、DARA算法进行比较.仿真环境部署了一个由不同数量的节点组成的拓扑结构.节点随机分布在面积为1 000 m×600 m的没有障碍的区域，即节点移动到一个新位置是不存在阻碍的.节点的数量分别被设置为20，40，60，80和100.节点的通信范围也分别设置成50，75，100和125 m.当改变节点的数量时，“r”是固定值100 m;当改变通信范围时，“N”是固定值100.所得结果是将算法取50次平均值得到的.通过以下指标评估MCDSR算法的性能:

(1)恢复过程节点移动数目:这个指标反映了由于节点失效导致的对网络拓扑的影响，移动的节点数越少说明网络拓扑改变越小，越利于网络整体的稳定.由图6中移动节点数量的图线可见，DARA算法比RIM算法有相当大的改进，论文提出的算法得到的移动节点数较DARA算法又有一定的减少，且随着节点密度的增加缓慢增加.DARA算法优于RIM算法的原因在于节点的移动集中在损坏节点的附近.论文算法移动节点数会进一步减少的原因在于每次在网络分隔区中总是寻找最小的连通支配集，而且如果子节点在先驱节点的连接范围内就不需要移动，这就减少了节点移动数量.移动数量会随着节点密度增加的原因是，密度越大，损坏节点周围的一跳节点就越多，牵涉到修复的节点就越多.

图6 不同网络规模下节点移动数量与不同通信半径下节点移动数量Fig.6 Mobile nodes in different network scale and mobile nodes in different communication radius

(2)节点总的移动距离:连通性恢复过程中涉及的所有节点移动的总距离，这个指标度量了整个网络由于节点的移动而消耗能源的多少.

图7显示了连接恢复完成后节点总移动距离.

图7 节点总的移动距离Fig.7 The total moving distance of the node

MCDSR算法明显优于现有的算法DARA、RIM.如图所示，即使节点数目、通信范围扩大，MCDSR算法总移动距离也没有突然的变化.这是因为MCDSR每次移动的都是分区中的最小连通支配集，产生的级联运动也是在超出通信范围内才移动.而RIM算法是所有的一跳均向失效节点移动，直到连接恢复.因此不管节点数目还是通信半径的增加，RIM的性能也远不及MCDSR.

(3)覆盖度减少的百分比:虽然保证连通性是恢复算法的主要目标，但节点的覆盖度对许多应用来说也是非常重要的.一个节点的故障通常会对覆盖造成负面影响.覆盖度减少的百分比的性能捕获了节点移动导致的覆盖损失.

图8显示了节点故障对覆盖度产生的影响.改变N和r时，用覆盖度减少的百分比来衡量.图8(a)表明3种方法的曲线走势大致相同.虽然增加节点密度有利于RIM和DARA的表现，但这两者的性能仍然比不上MCDSR.

图8 恢复后覆盖面积的减少Fig.8 Reduction of the coverage area after recovery

MCDSR在覆盖度方面的优势是由于其对节点移动范围的限制，当然这会导致在网络边缘的覆盖损失.在图8(b)中，随着r的增加，网络连接变得更加紧密，虽然失效节点的邻居数也在增长.DARA、MCDSR却表现了良好的覆盖性能.而RIM算法节点的定向移动使得失效节点的周围更加拥挤，而网络边缘却无法覆盖，这样就造成了巨大的边缘覆盖损失.

4 结束语

论文提出了一种基于最小连通支配集移动的节点失效恢复算法，主要关注内执行器网络关键节点失效时的连接恢复.MCDSR算法利用基于深度优先遍历割点搜索算法确定关键节点，并根据节点位置和节点度为它们指定备份节点.一旦备份节点检测到关键节点失效就启动恢复过程.在恢复过程中，该算法为备份节点找到一个最佳位置来恢复连接.仿真结果证明，和现有的一些方法相比，MCDSR在满足应用需求、减少恢复开销和限制关键节点故障对覆盖及连通的影响等方面具有优势.

［1］ Akyildiz I F，Kasimoglu I H.Wireless sensor and actor networks:research challenges［J］.Ad Hoc Networks，2004，2(4):351－367.

［2］ Akkaya K，Janapala S.Maximizing connected coverage via controlled actor relocation in wireless sensor and actor networks［J］.Computer Networks，2008，52(14):2779 －2796.

［3］ Chang CY，Xiang Y，Shi M L.Development and status of vehicular ad hoc networks［J］.Journal on Communications，2007，28(11):116 －126.

［4］ Younis M，Akkaya K.Strategies and techniques for node placement in wireless sensor networks:a survey［J］.Ad Hoc Networks，2008，6(4):621 －655

［5］ Akkaya K，Senel F，Thimmapuram A.Distributed recovery from network partitioning in movable sensor/actor networks via controlled mobility［J］.IEEE Transactions on Computers，2010，59(2):258 －71.

［6］ Tamboli N，Younis M.Coverage － aware connectivity restoration in mobile sensor networks［J］.Journal of Network and Computer Applications，2010，33(4):363 －374.

［7］ Basu P，Redi J.Movement control algorithms for realization of fault-tolerant and hoc robot networks［J］.IEEE Networks，2004，18(4):36 －44.

［8］ Abbasi A，Younis M，Akkaya K.Movement－assisted connectivity restoration in wireless sensor and actor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20(9):1366 － 1379.

［9］ Younis M，Lee S，Gupta S，et al.A localized self－ healing algorithm for networks of moveable sensor nodes［C］∥Global Telecommunications Conference，IEEE Globecom，2008:1 －5.

［10］ Yang Y Y.Adaptive energy efficient sensor scheduling for wireless sensor networks［J］.Optimization Letters，2010，4(3):359－369

［11］ Du J，Xie L，Sun X，et al.Application－oriented fault detection and recovery algorithm for wireless sensor and actor networks［J/OL］.International Journal of DistributedSensorNetworks，2012:273792.［2012 － 09 － 17］.http://www.hindawi.com/journals/ijdsn/2012/273792/.