一种用于Ad Hoc网络的自适应故障检测算法

李 香，门朝光，何忠政

(哈尔滨工程大学 计算机科学与技术学院，哈尔滨 150001)

故障检测器是构建可靠分布式应用系统的基础组件之一［1］。对于具有分布式特性的Ad Hoc网络，其网络拓扑结构易变，带宽、能源有限，网络中结点发生故障的概率较高，故障检测服务是提高系统可靠性和安全性的有效手段之一。Ad Hoc网络中需要着重考虑故障检测机制的自适应性和可扩展性，以适应网络拓扑变化。此外，故障检测器的服务质量(QoS)需要依靠超时值的正确设定，一个过小的超时值能快速检测到节点是否出现故障，但同时也会增加判断错误的次数，减少故障检测器的准确率，而过大的超时值虽然能减少判断错误的次数，提高准确率，但又会增加检测时间，使SAN的收敛时间延长，因此故障检测器应达到快速性和准确性的平衡［2］。在分布式系统故障检测算法的基础上，专家和学者针对Ad Hoc网络高度动态变化的拓扑结构、分布式等特性提出了一些Ad Hoc网络故障检测算法［3-5］。此外，故障检测器可用来解决分布式系统中的一些基本问题，如一致性和原子提交问题［6，7］。本文基于Xiong的故障检测算法TAM FD［8］，提出了适应于Ad Hoc网络的故障检测算法，通过对心跳消息到达时间进行动态预测并实时更新调整，以减少网络状态变化对预测时间的影响，从而尽量避免故障检测器发生错误的判断。

1 系统模型

系统由n个结点组成，∏为结点集合。假设故障类型为Fail-Stop，结点之间通过可靠的通信信道连接，如果结点q向p发送一条心跳消息，除非p本身发生故障，否则它最终会收到该消息。每一个故障检测器输出一个当前被怀疑为故障的结点集合Suspectsi。故障检测器的历史H被定义为:H:∏×T→2∏。H(p，t)是t时刻故障检测器对结点p的判断。如果q∈H(p，t)，则认为在t时刻p怀疑q［9］。

系统存在一个全局时钟，系统中消息的发送、传输及处理时间，即消息传输延迟有上限，设全局稳定时间GST之后结点间一跳消息传输延迟的最大值为Δmessage。

根据以上系统模型和假设，定义故障检测级别如下:

(1)强完整性:每一个故障的结点最终都会被所有正确的结点永远判定为故障。

(2)最终强准确性:存在某个时间t，在此之后，每个正确的结点都不会被任意一个正确结点判定为故障。

2 自适应故障检测算法

2.1 基本思想

被检测结点q周期性地向检测结点p发送心跳消息，每个发送消息的序号顺序递增。p根据最近i次接收到的心跳消息到达时间和预测策略，预测第i+1次心跳消息到达时间。如果在预测的时间内检测结点p没有收到被检测结点q发来的心跳消息，则怀疑q故障;如果p之后收到q发来的心跳消息，则取消对该结点q的怀疑。

2.2 超时值预测模型

基于心跳策略的故障检测算法的核心是对心跳到达超时值的预测，自适应故障检测算法大多是根据系统状态对心跳消息到达时间的预测超时值进行调整。

其中:为最近i个心跳消息到达时间延迟的平均值。

采用Chen［10］类似方法，引入固定修正值αi+1对EAi+1进行调整，以反映系统的动态变化，并减少网络状况对预测时间的影响。修正值αi+1计算公式如下:

对EAi+1进行调整，得到心跳消息到达时间的预测超时值τi+1为:

其中γ为调节系数。

2 .3 故障检测算法

采用基于PUSH类型的心跳策略，根据网络状态预测并自适应调节超时值，以确保故障检测的实时动态性，从而满足上层应用的需求。提出的Ad Hoc网络环境下的故障检测算法如下:

故障检测算法.

算法的主要工作机理如下:

Task 1.被检测结点q以间隔Δ周期性地向检测结点p发送心跳消息。

Task 3.如果在预测的时间内，p未收到q发送的心跳消息，则p怀疑q故障。

2.4 算法证明

引理1

如果在tcrash时刻被检测结点发生故障，则存在一个时刻tmute，在此之后检测结点p不会接收到被检测结点q发送的消息。

网络中结点个数为N，有:

证明:最坏情况下，网络为线性结构，且p和q相距N-1跳，则q的心跳消息经过(N-1)个心跳间隔和传输延迟到达p。全局稳定时间GST后，一跳结点间消息传输延迟上界为Δmessage。因此，最坏情况下，若q在tcrash时刻故障，停止发送心跳消息，则存在时刻tcrash+(N-1)(Δ+Δmessage)，在此之后p不会接收到q发送的消息。故引理1成立。

引理2

假设检测结点p从被检测结点q接收了i个心跳消息序列，当p不再从q接收任何的直接或间接心跳消息时，存在一个时刻后p开始怀疑q。

证明:当p从q接收到i个心跳消息，它会预测下一个心跳消息到达时间之后p开始怀疑q。那么，当收敛时，肯定存在p开始怀疑q的时刻。因此，只需证明有界。

根据文献［8］中证明，以下式子(7)、(8)成立:

若只接收到一条最新心跳消息，无重复最新心跳消息存在，由算法1有由(7)、(8)得 τi+1有界，即有界。

若接收到重复最新心跳消息，则由算法1有。结合式(7)、(8)，只需证明更新有界。如引理1所述，在最坏情况下，除q之外p的所有邻居结点都在转发该重复最新心跳消息的路径中，则p至多在(N-2)(Δ+Δmessage)时长之后接收到来自q的重复最新心跳消息。因此，有，可计算出有界，即预测时间的更新值有界。

故有界，即引理2成立。

定理1

(强完整性)本文设计的故障检测算法满足强完整性要求，即

证明:如果引理1，2被证明，则定理1成立。即存在一个时刻tmute，在此之后没有一个正确的检测结点收到发生故障的被检测结点发送的心跳消息;存在一个时刻ttimeout，在此之后所有正确的检测结点会永久性地判定被检测结点发生故障。

由引理1和引理2可得定理1成立。证毕。

定理2

(最终强准确性)本文设计的故障检测算法满足最终强准确性要求，即

证明:由引理1可知，除非结点发生故障，否则心跳消息一定会在(N-1)(Δ+Δmessage)之前到达p。设tk+1为k+1次心跳消息实际到达时间，有tk+1＜(N-1)(Δ+Δmessage)。

因此，存在时间t为(N-1)(Δ+Δmessage)，在此之后，每个正确的结点都不会被任意一个正确结点判定为故障。证毕。

3 实验结果

仿真实验在Windows XP SP3环境下使用GloMoSim进行模拟仿真。50个结点在1000×1000m2范围内采取随机移动模型以2m/s-20m/s速度匀速移动，MAC层采用IEEE 802.11协议，网络层采用IP协议，应用层采用CBR协议，采用DSR路由协议源结点周期性地向目的结点发送固定尺寸的报文。

心跳消息发送间隔为5000ms，初始超时值为5500ms，对预测和实际超时值进行比较。如图1所示:实际超时值近似于固定值;随着心跳消息的增多，预测超时值逐渐趋近于实际超时值。因此，本文故障检测算法可以准确地对超时值做出预测。

图1 超时值比较

平均错误率λM和查询准确率PA经常被用来评价故障检测算法的准确性，且需要两者结合来检验［10］。心跳消息发送间隔为1000ms，接收窗口大小为500，实验统计接收消息达到500以后λM、PA随检测时间变化的曲线，对故障检测算法的准确性进行检验。

图2对比了NFD-E［10］、TAM FD［8］、本文故障检测算法的平均错误率。从图中可以看出:随着检测时间的增长，算法的平均错误率逐渐降低;当检测时间达到500ms时，平均错误率达到10-2级别，具有较低的平均错误率，这表明故障检测器在单位时间内发生误判的概率较小，有效地避免了状态切换带来的系统开销，从而提高故障检测的性能。其中，本文算法的平均错误率最低，这是由于本文算法充分考虑Ad Hoc网络特点，根据接收到的心跳消息实时动态更新预测超时值，从而能更好地适应Ad Hoc网络环境。

NFD-E、TAM FD、本文故障检测算法查询准确率随检测时间变化的情况如图3所示。随着检测时间的增长，查询准确率不断提高，在600ms后查询准确率超过97%，表明故障检测器输出正确的概率较高。其中，NFD-E查询准确率相对较差，随着检测时间的增长，查询准确率停留在90%左右，且波动较大，可见固定的修正值不适合动态的Ad Hoc网络环境。TAM FD随着检测时间的增长，查询准确率平稳上升，一定时间后趋于平衡。本文故障检测算法在检测时间较小时与TAM FD性能基本一致;随着检测时间的增长，达到500ms以后，本文算法的查询准确率高于TAM FD。

图2 不同算法平均错误率比较

图3 不同算法查询准确率比较

4 结语

该文提出了一个Ad Hoc网络环境下的故障检测算法，算法根据网络状况动态的调节预测超时时间;针对Ad Hoc网络多跳通信和结点混杂工作模式等特点，对预测时间进行更新。理论证明，算法满足强完整性和最终强准确性，是一个♢P类故障检测器。仿真实验表明:算法可以准确地对超时值做出预测;算法的平均错误率低、查询准确率高，具有较好的检测准确性指标。

［1］Pasin M，Fontaine S，Bouchenak S.Failure Detection in Large Scale Systems:a Survey［C］//IEEE Network Operations and Management Symposium Workshops.Salvador，2008:165-168.

［2］杨光.存储区域网中基于神经网络故障检测器的研究［J］.计算机工程与应用，2011，47(33):10-12.

［3］Friedman R，Tcharny G.Evaluating failure detection in mobile ad-hoc networks［J］.International Journal of Wireless and Mobile Computing，2005，1(8):1-3.

［4］Elhadef M，Boukerche A.A Gossip-Style Crash Faults Detection Protocol for Wireless Ad-Hoc and Mesh Networks［C］//Proceedings of IPCCC.New Orleans，2007:600-605.

［5］Elhadef M，Abdun-Nur F.Adaptable Crash Faults Detector for Mobile Ad-Hoc Networks［C］//Proceedings of AINAW’07.Niagara Falls，2007:207-212.

［6］Chockler G，Demirbas M，Gilbert S.Consensus and collision detectors in wireless ad hoc networks［C］//24th Annual Symposium on the Principles of Distributed Computing(PODC).Las Vegas，2005:197-206.

［7］Wu W，Cao J，Yang J.A hierarchical consensus protocol for mobile ad hoc networks［C］//Proceedings of the 14th Euromicro International Conference on Parallel，Distributed，and Network-Based Processing(PDP’06).Washington，DC，2006:64-72.

［8］Xiong N，Vasilakos A.Comparative analysis of quality of service and memory usage for adaptive failure detectors in healthcare systems［J］.IEEE Journal on Selected Areas in Communications，2009，27(4):495-509.

［9］Chandra T D，Toueg S.Unreliable failure detectors for reliable distributed systems［J］.Journal of ACM，1996，43(2):225-267.

［10］Chen W，Toueg S，Aguilera M K.On the quality of service of failure detectors［J］.IEEE Transactions on Computers，2002，51(5):561-580.