一种无线自组网故障检测算法

徐振朋,沈 浩,曾玮妮

(1.杰瑞深软科技有限公司,江苏连云港222061;2.江苏自动化研究所,江苏连云港222061)

一种无线自组网故障检测算法

徐振朋1,沈 浩2,曾玮妮2

(1.杰瑞深软科技有限公司,江苏连云港222061;2.江苏自动化研究所,江苏连云港222061)

针对无线自组网的拓扑结构,设计一种基于分簇的无线自组网节点故障检测架构和对应的故障检测算法。分簇时分别确定主用簇和备用簇管理节点,冗余簇管理节点负责对内部成员实施异常检测,给出故障检测模块的心跳发送、心跳监控、心跳预判与实时调整机制,通过增加心跳预判实时调整机制,确保算法能够动态适应自组网易变的拓扑结构,并通过备用簇管理节点和簇间共享异常信息机制,提高系统故障检测的可靠性。利用仿真实验对故障检测机制的性能进行评估,结果表明,提出的故障检测算法具备较好的检测准确率,能够有效满足上层应用在系统可靠性设计方面的需求。

无线自组网;容错;节点故障;故障检测;心跳预判

1 概述

无线自组网(Ad Hoc Network)作为一种无中心、动态网络拓扑的分布式计算系统,依靠自身的便捷、自组以及易接入等优势已广泛用于各行业领域[1]。随着无线自组网的不断发展,其系统规模及复杂性不断提高,系统相关的信息丢失、链路故障、节点失效对顶层应用的影响越来越大[2-3]。作为基础组件,故障与失效检测是构建可靠的分布式应用的关键之一,其拓扑结构动态性对其故障检测机制的设计提出了很大的挑战,具有非常重要的理论与现实意义[4]。

故障检测机制作为可靠分布式系统的基础组件已取得了阶段性的成果[5]。基于分布式系统故障检测的基础理论,文献[6]分析了不可靠故障检测相关概念,并结合故障检测相关属性划分了故障检测机制的基本类型。作为障检测机制的核心,故障检测算法均以心跳机制为基础[7]。文献[8]提出了一个能够根据网络状况动态自适应的故障检测算法。基于自适应的故障检测算法,文献[9]提出了动态的预测修正值的计算方法,以尽量降低检测延迟。文献[10]提出的φ-检测器增强了检测灵活性。文献[11]基于灰色预测理论提出了一种基于QoS的故障检测算法。为了应对自组网系统故障检测的扩展性难题,文献[12]构建了层次式故障检测机制。然而,上述故障检测机制尚存在诸多缺点。为此,本文进一步分析无线自组网对应的故障检测模型,并在此基础上设计准确高效的故障检测算法。

2 系统模型

如图1所示,所述无线自组网由无向图G=(V,E)表示,其中V表示分布在设定地理区域的无线节点,能够在一定范围内活动[1]。E为无线节点V之间通信链路的集合,若无线节点X和Y之间存在连接e,则意味着节点Y在节点X的传输范围之内且X也在Y的传输范围之内[2]。用NX(t)表示t时刻节点X相邻节点,即t时刻处于节点X传输范围之内的节点都是X的相邻节点。假设系统各节点网络链路为混杂模式,即无论X的相邻节点是否为发送消息的目标节点,都可侦听到X发送的消息[3]。本文无线自组网节点采用随机移动模型,即在一段时间t内系统各节点的移动速度和方向是随机的。无线节点移动速度v(t)在[vmin,vmax]满足均匀分布,无线节点移动方向θ(t)在[0,2π]同样满足均匀分布[3-4]。

图1 无线自组网结构表示图

假定系统中每个节点的时钟基本一致,系统中节点通信以ω及处理延迟时间是有限但任意的[9]。本文算法主要针对失效即停止类故障事件,节点发生异常事件以后不能发出消息和接收消息,不会影响系统其他节点状态[12]。

3 故障检测架构

故障检测机制主要完成簇管理节点对内部成员异常状态监控的设计,具体流程如图2所示,主要过程如下:

(1)过程1:当系统节点收到其他节点的心跳信号时,需要向主用簇管理节点转发该信号,主用簇管理节点的心跳信号需要被转发至备用节点,主用和备用簇管理节点根据接收到的信号对节点状态进行判定。

(2)过程2:内部节点按照设定周期值向主用簇管理节点发送心跳信号,收到心跳主用簇管理节点需确定成员节点的状态并预测随后心跳的到达时间。与此同时,为了实现主用和备用簇管理节点之间的相互监控,主用簇管理节点需要向备用节点发送心跳信号。

(3)过程3:依照上述过程判定,主用节点或备用簇管理节点可以确定内部成员的是否出现异常。若判定出新的故障事件,则将该事件通过备用节点告知系统其他簇管理节点,使得每个簇管理节点能够了解整个系统的状况。

图2 局部成员内部检测流程

担负多重角色的簇管理节点需完成额外计算与传输工作,负载与开销均高于系统其他节点。为了尽量避免簇管理节点限制系统故障检测技术机制,本文对系统分组划分算法进行了相应调整,在确定系统簇管理节点时需要分别确定主用和备用节点,以支撑主用和备用节点间相互监控和簇间异常状态的高效传递,备用节点平时担负簇间异常状态消息传送功能以降低主用节点的负载。与此同时,一旦备用节点检测到主用节点发生异常,备用节点可快速接管主用节点的功能,可以尽量降低主用节点异常对整个系统故障检测机制的影响。

4 故障检测算法

分布式系统中各节点均具备各自的异常监控模块Exception_M,异常监控模块Exception_M使用集合ALL_LIST保存所有节点的标识,并通过下述过程对心跳信号进行计算和预判:

(1)计算预判值。由于无线自组网具备节点位置不定和限定续航时间的局限,因此需要尽量降低故障检测对系统处理和传输负载。心跳信号的预判值可通过下式计算得到:其中,用Δ(t)表示心跳信号的参数值;d—i表示心跳信号延迟期望值。

(2)计算调整量。调整心跳信号预判值用于体现系统不同网络状况对预判值的调整,以降低节点异常误判的概率。心跳信号预判值调整量αi+1可通过下式得到,其中,参数β∈(0,1);ε为设定的定值[12]。

(3)预判心跳信号。心跳信号的最终预判值可通过下式确定,参数γ是预判值变化值的调整变量。

具体的故障检测机制共包括INIT_HBS,DEAL_ TOS和DEAL_HBS 3个部分,INIT_HBS主要依照配置定期触发心跳信号的功能,DEAL_TOS主要依据预判值完成对心跳信号的检测功能,若超过预判值仍未接收到心跳信号则可推测被监控节点出现异常事件,需及时记录被监控节点的状态信息。DEAL_HBS主要通过初始预判值,以及对其的调整,完成准确预判心跳信号的功能。涉及预判的处理过程COMP_ DEST如下:

在COMP_DEST处理过程中,记Suspectp为监控节点p推测的异常节点的集合;记Informersp[q]为参与传输q的心跳信号给p的节点。记ArrivalTimesp[q]为节点p保存的节点q的心跳信号预判值;记Heartbeatsp[q]为监控节点p上保存的被监控节点q的心跳信号计数值。根据上述检测算法,心跳信号预判值的调整可通过DEST_UP实现,监控节点p根据当前已得到的被监控节点q的心跳信号对后续心跳信号预判值进行调整,具体过程如下:

被监控节点INIT_HBS的主要处理过程如下所示,即按照设定周期值产生自身的心跳信号。

DEAL_HBS模块主要完成调整心跳信号预判值的功能,通过收到的心跳信号数量得到后续的预判值,这里用tmr表示监控节点p可用的时间值。

DEAL_TOS模块主要处理过程如下所示,依据预判值完成对实际心跳信号的监控功能。

5 性能分析

通过NS仿真软件设定无线自组网设定为1000 m×1000 m的区域,系统中包含50个节点,设置节点移动模型为随机移动模型且速度处于[2 m/s,20 m/s]区间[4]。网络设置为DSR路由协议、IP协议、IEEE 802.11,应用层设置为固定频率的CBR会话,并且源节点按照周期值向目的节点发送固定大小的报文[5]。选取NFD_E和TAM_FD这2种具有代表性的算法进行对比[3]。如图3所示, 3种机制的平均错误率均随着检测时间的增加而降低,总体上本文算法最优。相同检测时间情况下本文算法比NFD_E和TAM_FD具备更低的平均错误率,而NFD_E具备最高的平均错误率,TAM_FD的平均错误率介于NFD_E和本文算法之间。经分析,这是由于本文故障检测机制采用了冗余簇管理节点的模式,并提出了更加准确的算法用于心跳信号预判。

图3 3种算法平均错误率对比

查询准确率是检测机制在一定时间段内输出正确结果的比率,是反映检测准确性的重要指标[4]。如图4所示,3种机制的查询准确率均随着检测时间的增加而增加,总体上本文算法的查询准确率高于TAM_FD和NFD_E。在相同检测时间情况下, NFD_E的查询准确率最低,但是随着系统检测时间的不断增加出现了局部震荡,最终只能稳定于90%左右,这是由于其固定调整值的方法无法完全适用于易变的无线自组网。不同于NFD_E算法,TAM_ FD算法的查询准确率随着系统检测时间的不断增加总体变化较平稳,最终能够稳定于95%左右。本文算法的查询准确率初始时与TAM_FD大体相当,但随着系统检测时间的不断增加最终高于后者,稳定于97%左右。经分析,这是由于本文算法设计了更准确的心跳信号预判调整方法。

图4 3种算法查询准确率对比

6 结束语

通过分析无线自组网分布式系统故障检测研究存在的问题,本文提出一种面向无线自组网的高效故障检测算法,分簇时分别确定主用和备用簇管理节点,冗余的簇管理节点负责对内部成员实施异常检测,心跳预判实时调整机制确保算法能够动态适应自组网易变的拓扑结构,并通过备用簇管理节点和簇间共享异常信息机制提高系统故障检测的可靠性。最后利用仿真实验对故障检测机制的性能进行评估,结果表明,设计的故障检测算法具有较好的可扩展性、较低的平均错误率和较高的查询准确率,能够较好地适应大规模的无线自组网系统。

[1] Stewart W,Gabriel A,James W.Fault Detection for Vehicular AdhocWirelessNetworks[J].IEEE IntelligentTransportationSystemsMagazine,2014, 6(2):34-44.

[2] 唐明珠,阳春华,桂卫华.基于改进的QBC和CS-SVM的故障检测[J].控制与决策,2012,27(10): 1489-1493.

[3] Ekin K O,Ridha M A,Onur O,et al.Survivability in Hierarchical Telecommunications Networks Under Dual Homing[J].INFORMS Journal on Computing,2014, 26(1):1-15.

[4] 胡景龙.基于分簇的Ad Hoc网络结点故障检测技术研究[D].哈尔滨:哈尔滨工程大学,2010.

[5] Chandra T D,Toueg S.Unreliable Failure Detectors for Reliable Distributed Systems[J].Journal of ACM, 1996,43(2):225-267.

[6] Larrea M,FernándezA,ArevaloS.Eventually Consistent Failure Detectors[J].Jounal of Parallel and Distributing Computing,2005,65(3):361-373.

[7] Zhang Jianhua,Song Bo,Zhang Zhaojun,et al.An Approach for Modeling Vulnerability of the Network of Networks[J].Physica A:Statistical Mechanics and Its Applications,2014,412:127-136.

[8] Bertier M,MarinO,SensP.Implementationand Performance Evaluation of an Adaptable Failure Detector[C]//Proceedingsofthe15thInternational Conference on Dependable SystemsandNetworks. Bethesda,USA:[s.n.],2002:354-363.

[9] Hayashibara N,DefagoX,KatayamaT.Two-ways Adaptive Failure Detectionwiththeφ-failureDetector[C]//ProceedingsofWorkshoponAdaptive Distributed Systems.Sorrento,Italy:[s.n.],2003: 22-27.

[10] 田 东,陈蜀宇,陈 锋.一种网格环境下的动态故障检测算法[J].计算机研究与发展,2006,43(11): 1870-1875.

[11] Hayashibara N,Cherif A,Katayama T.Failure Detectors for Large-scale Distributed Systems[C]//Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems.Osaka,Japan:[s.n.],2002:404-409.

[12] Camp T,Boleng J,Davies V.A Survey of Mobility Models for Ad hoc Network Research[J].Wireless Communications and Mobile Computing,2002,2(5): 483-502.

编辑 顾逸斐

A Failure Detection Algorithm for Ad Hoc Network

XU Zhenpeng1,SHEN Hao2,ZENG Weini2
(1.JARI Deepsoft Technology Co.,Ltd.,Lianyungang 222061,China;
2.Jiangsu Automation Research Institute,Lianyungang 222061,China)

A failure detection architecture and algorithm based on clustering are proposed according to the topology of Ad Hoc networks.The active and the backup cluster manager are designated respectively.The exception detection function of the members is implemented by the selected redundancy cluster managers.The sending,monitoring,prediction and updating process of the heartbeat message are designed for fault detection.The updating method of the heartbeat prediction is added to fit the variable topology of Ad Hoc networks dynamically.Through the backup cluster manager and the exception data shared mechanisms among clusters,the system fault detection reliability is improved.The proposal is evaluated by the simulation.As a result,the proposed failure detection mechanism achieves a high accuracy,and is capable of the requirement of the top application design for the system reliability.

Ad Hoc network;fault tolerance;node failure;fault detection;heartbeat anticipation

徐振朋,沈 浩,曾玮妮.一种无线自组网故障检测算法[J].计算机工程,2015,41(2):313-316.

英文引用格式:Xu Zhenpeng,Shen Hao,Zeng Weini.A Failure Detection Algorithm for Ad Hoc Network[J].Computer Engineering,2015,41(2):313-316.

1000-3428(2015)02-0313-04

:A

:TP301.6

10.3969/j.issn.1000-3428.2015.02.060

国家自然科学基金资助项目(61303045);江苏省自然科学基金资助项目(BK2012237)。

徐振朋(1983-),男,高级工程师、博士,主研方向:普适计算,分布式计算;沈 浩,工程师、硕士;曾玮妮,高级工程师、博士。

2014-08-28

:2014-10-27E-mail:xuzhenpeng@jari.cn