有损网络中基于计时器的节点故障检测模型研究

赵英姿

有损网络中基于计时器的节点故障检测模型研究

赵英姿

当前大多数不可靠故障检测器利用可靠的通信链路来通知完全连通网络中的故障，且在部署时没有考虑能量、存储和带宽方面的资源约束，不适用于有损网络。基于此，提出一种低功耗有损网络故障检测模型ALLONE。该模型在考虑无线链路间歇性故障的条件下，利用自适应计时器实现节点故障检测。此外，提出两种计时器调整技术，实现多应用场景下ALLONE的运行性能调整。在Omnet++/Mixim框架下对模型和方法进行评估。仿真结果表明，与其他方法相比，其方法提高了故障检测和恢复率，降低了报文丢失率和故障阳性检测率，没有增加能耗开销。

故障检测；有损网络；资源约束；计时器

0 引言

不可靠故障检测器是分布式系统的一个重要服务。Chandra和Toueg等人[1]阐述了故障检测的重要意义，将故障检测器定义为每个进程的启示程序（Oracle），可定期提供一个可能已经发生故障的进程列表。王明等[2]提出一种自适应心跳检测器（SA-HD，Self-Adaptive Heartbeat Detector）。SA-HD采用了基于拉式（pull）的自适应心跳算法，在考虑故障检测性能的同时也考虑了心跳检测所占用的网络资源对网络性能的影响。饶翔等[3]提出一种基于故障注入测试的故障特征提取方法，该方法主要由3步组成：（1）过滤噪声日志；（2）构造1个故障识别器识别不同故障的早期特征；（3）为每类故障构造限状态追踪器追踪该故障的后期传播状态，从而在故障被识别出来后持续跟踪故障传播状态。文献[4]针对现有方法在满足网格特定需求方面的缺陷，提出设计动态自适应故障检测服务的手段，通过对分布式系统中已有动态自适应故障服务的分析，设计了解决的办法。然而，上述检测方案大多假设通过一种机制，利用可靠的通信链路来通知完全连通网络中的故障。另外，检测器在部署时也没有考虑能量、存储和带宽方面的资源约束。因此，不适用于有损网络。为此，本文重点研究MANET、MESH和WSN等低功耗有损网络（LLN）的故障检测问题。旨在改进LLN的故障检测模式，并提出一种新的故障检测器ALLONE（低功耗有损网络的自适应故障检测器）。在考虑无线链路间歇性故障的情况下，利用自适应计时器实现节点故障检测。进程故障的检测只基于节点对网络的本地感知，与全局信息交换无关。被交换的疑似故障列表捎带到LLN应用的周期性数据报文中。基于Omnet++/Mixim展开仿真实验，评估本文方法的检测和精度性能。结果表明，与其他方法相比，本文方法提高了故障检测和恢复率，降低了报文丢失率和故障阳性检测率，而且并没有增加能耗开销。

1 问题分析

设一个系统包括两个进程：进程Pj必须周期性地向Pi发送数据报文。首先假设链路可靠性较高，这意味着在正常进程间传播的报文总是能被正确传输。故障检测时间（Tj）定义为：如果Tj在接收到期望报文前到期，则Pi怀疑Pj故障。根据应用参数（比如周期性发送间隔，传输延时等），可对Tj数值初始化。

然而，如果除了进程故障外还有可能发生报文丢弃和链路故障，则上述情况将会不同。实际上，就上述Tj而言，当Pj仍在正常运行但由于间歇性故障（有损链路、拥塞等）导致报文丢失时，Pi便有可能出错。此外，在整个网络寿命期间，报文丢失模式也不稳定。随着障碍物、地理特征、抑制、部署和机动性不同，上述情况也会发生变化。为此，本文根据Pj的动态有损模式来更新Tj。此外，如果网络包括2个以上进程，则每个节点的故障检测器必须在本地检测出故障，然后将故障情况通知给其他相邻节点。所支持的机制必须考虑能耗、带宽和存储空间等资源约束。实际上，通知故障情况会导致额外能耗和网络流量。

本文研究基于直接相邻节点间本地交互的自适应性计时器使用问题。利用一种随机策略，在考虑丢失率、链路状态和传输时延等因素的情况下确定计时器T 。该计时器是在两个连续相邻节点间而不是任意一对节点间定义，这样可以提高T 数值计算的准确性。此时T数值取决于本地可预测的传输延时，且不需要知道整个系统和网络结构的相关信息。本地故障怀疑信息将在网络中传输。每个进程可以查询一个故障检测模块，且该模块可以提供信息明确其相邻节点中哪些进程发生故障。这一信息的格式往往是疑似故障的列表形式。利用相邻区域交互，将该列表捎带进周期性数据报文中，可避免使用专门信令报文导致的额外开销。

2 系统模型

2.1 故障模型

假设进程有可能发生故障。此外，相邻节点间的链路为有损链路：在传输过程中报文可能会丢失。这往往是由传输链路故障导致，这些传输链路故障往往是间歇性故障。因此，如果进程没有成功发送部分报文，则这一报文丢失现象定义为间歇性故障。然而，如果进程故障，则进程永远不再属于网络，并且要把这一情况告知所有相邻节点。于是，即使故障检测器在链路故障时怀疑进程故障，则当链路恢复时也有能力检测出错误的故障判断。为了容忍LLN中的间歇性故障，本文使用文献[5，6]提出的突发报文丢失模型。连续报文丢失数量可表示为BL（突发长度）变量的几何分布，该分布明确了处于Bad状态（即连续报文丢失）的时间长度。定义故障检测器必须能够容忍的突发丢失上限（BLL）为：

2.2 数据采集模型

考虑基于周期性报文传输的两种通信模型：检索驱动和时间驱动。其中，检索驱动模型又称为检索响应路由模型，以网络侦询为基础，进程依次向所有网络节点（相邻节点）发起查询。目的进程在协议参数事先定义好的时间间隔内做出响应。例如，DSR[7]和AODV[8]均为基于查询的协议。另一方面，时间驱动模型使用周期性数据传输方法。路由协议为每轮数据传输定义了一个时间隙或一个时间间隔。许多主动式协议（例如DSDV[9]、OSR[10])使用时间驱动模型来构建和维护路由。

3 ALLONE：故障检测算法

算法根据通信模型的周期性模式按轮运行。在每一轮中，节点向其相邻节点发送报文，直到有可能故障为止。本文模型的基本原则是：将疑似故障捎带进当前数据/路由报文，并?逐Su条s传p播e信c息t。e因d此i， 将表S示u进s程pPeic t包e含其d疑i似 故列障表相加邻到节每点个的报列文表中。。进程Pi的ALLONE模块如图1所示：

图1 ALLONE模型

它由两个主要组件（发送和接收）和一个任务构成：对每个消息MSG，ALLONE检查MSG是否属于发送组件（即Pi 生成的将要发送到网络中的数据报文）。如果属于，则Pi中MSG包含Suspectedi 集合（第4行）。在将信息捎带处理后，Pi向neighborsi 中的相应节点发送新的报文?MSGs（第5行）。然后，Pi 为每个正常已知相邻节点初始化一个新的计时器，即节点Pj等待下一报文，计时器为Tj。如果有Tj到期，则Pi怀疑Pj在任务T1中故障。然后，疑似信息插入Suspected（i第20行）。如果有另一个MSG需要发送，则该疑似信息包含在下一数据报文中。计时器调度具有动态特性，取决于网络的随机变化。下一节将阐述如何调节计时器。另一方面，如果Pi接收到来自相邻节点Pj 的MSG（第8行），则ALLONE运行第2个组件（即接收组件），根据接收到的报文中捎带的的疑似故障集合来更新疑似故障集合。它还努力寻找先前被错判的疑似故障，以便能从疑似列表中将相应节点去除。首先，Pi将数据报文发送给其应用层。然后，检索相关信息，即源节点Pj的集合Suspected（j第11和12行）。因为Pi已经成功地从Pj处接收到报文，所以中止计时器? Tj（第13行）。Pi 检查Pj 在最近是否被怀疑，以便将其从Suspectedj集合中删除（第14和15行）。此后，Pi 利用接收到的Pj 报文中关于疑似故障和错判故障的相关信息来更新自己的列表。因此，Pi包括Pj通知的每一个疑似故障进程。此外，如果Pj通知Pm先前被错判为疑似故障进程，则Pi将Pm 从其Suspectedi 中删除（第16-18行）。如果Suspectedi 不包括Pm 但后者仍在Suspectedi 列表中，则检测出错判。

4 计时器调整技术

本节阐述如何调度ALLONE中的故障检测计时器（图1第7行）。本文提出的计时器T 应该在考虑传输故障、通信协议内容和网络动态特征的条件下进行动态更新。为此，本文提出基于这一机制的两种计时器调整方法。第1种方法通知所有故障且虚警率较低，因此，称为精度感知随机自适应计时器A-SAT。第2种方法以最短时间通知各种进程故障以进行实时监控。很显然，这可能增加虚警率。然而，该机制的目的是实现实时检测。于是，本文将其称为完整性感知随机自适应计时器C-SAT。两种方法的计时器设置和更新算法如图2所示：

图2 计时器自适应算法

在开始时，由于没有之前的通信过程供我们获取统计数据，所以根据传输间隔和延时的假设值来设置首个T值（第1行）。然后，应用运行期间利用关于被接收数据报文的有效丢失率来更新T。也就是说，如果错误检测率WDR超过能够容忍的错误检测率TWR（第2和3行），则T将会增加，其中TWR是用于控制故障检测器精度的阈值。如果到达该阈值，则ALLONE必须在通知故障前增加等待时间。然而，如果T允许满足预期TWR值，那么若它还没有达到预先定义的可靠性阈值（第4到5行），我们通过降低其数值来增加故障通知性能。在应用中引入是为了明确允许快速检测时故障检测器的预期可靠性。很显然，算法希望提高检测速度的同时降低差错率，如图3所示。算法性能取决于预定义参数及Decrease(T)和 Increase(T)函数。下面将阐述如何根据应用要求采用不同方式实现时间增加/下降功能。

4.1 精度感知方法(A-SAT)

本文希望通过A-SAT方法，提高故障通知的精确性。这种方法的目的是降低错判率。为此，使用文献[11]中的乘性相加加性相减算法（MIAD）。MIAD将计时器数值的指数增加特点与线性下降特点融合起来，以满足故障检测最低可靠性要求：

假设故障检测器已经发生了多起错误，于是虚警率超过能够容忍的阈值（WDR>TWR）。根据算法如图3所示：

图3计时器更新进程

我们增加计时器数值。因为A-SAT希望降低错误数量，所以将计时器乘以以放大其数值。此外，参数a取决于程序运行期间观察到的本地随机信息，即WDR和TWR。因此，计时器的指数上升取决于导致其增加的有效虚警率。然而，在decrease(T)函数中，使用参数β降低计时器数值。根据故障检测期间的本地通知延时来推导β数值（通知延时是指故障出现至故障被检测出来之间的时间）。请注意，如果故障检测器的可靠性低于可靠性阈值要求，则触发decrease(T)函数。出于简便考虑，将可靠性定义为正确故障判断的比例，即1-WDR。通过在控制虚警率时猛烈增加计时器数值，A-SAT增加其等待时间，以容忍更多的间歇性故障，避免错误判断。每当故障检测率下降时，根据通知延时的均值来降低计时器数值，以迅速克服可靠性较低的问题。

4.2 完整性感知(C-SAT)

本文提出完整性感知随机自适应技术（C-SAT）以实现故障的迅速检测。目的是迅速通知任何故障。为此，我们使用文献[11]中的加性增加乘性相减方法（AIMD）。与MIAD方法不同，AIMD融合了计时器的线性上升和指数性下降特点，如下式所示：

对于AIMD和A-SAT，计时器的增加和下降函数分别取决于故障通知的可靠性和虚警率。C-SAT猛烈降低计时器数值来迅速检测出任何故障。为此，将T与根据有效虚警率而确定的参数相乘。做出这种选择，是因为C-SAT通过降低计时器数值来迅速检测出故障。同时，为了避免误判，当到达可靠性要求时，C-SAT增加T值。为此，将T与参数相加，参数取决于应用运行期间的随机信息（比如导致先前部分误判的传输延时平均周期数值）。

5 性能评估

本节评估了动态故障检测器ALLONE和计时器调整方法的性能。首先，比较本文基于计时器的广义模型与无计时器的故障检测器。然后，衡量计时器更新的重要性，以及两种动态调整方法（即C-SAT和A-SAT）的影响。为此，选择文献[12]中的HeartBeat（HB）作为无计时器故障检测器。基于Omnet++/Mixim展开仿真实验，仿真模型总结如表1所示：

表1 仿真模型

为了阐述使用自适应故障检测器的结果，本文主要利用两种场景考察多次仿真的结果。在场景1改变随机部署的节点数量（20-200个节点）；在场景2改变相同网络条件下的故障数量（所有节点的10%-50%）。为了获得周期性数据通信模型，采用文献[8]中的有向扩散路由协议DD。在本文仿真测试中，比较DD-HB（利用无计时器故障检测器进行增强的DD协议），FaT2D[2]（利用静态计时器故障检测器进行增强的DD协议），以及ALLONE的两个版本：ALLONE-ASAT和ALLONE-CSAT。这两个版本的主要区别就是使用的计时器调整技术不同。

5.1 性能指标：

本文实验主要考察3种类型6大指标：

（1）故障检测器的属性：在该类型下，主要测试精度和完整性属性。于是，可以根据虚警率（精度）和故障检测率（完整性）方面的性能表现对本文方法进行分类。

（2）检测和恢复性能：每种检测机制的目的均是发现网络中的故障，恢复路由路径，避免故障的影响。为此，使用检测和恢复周期及报文丢失率两个指标。这些测量值可以衡量检测技术的速度及其对数据报文丢失的影响。

（3）资源管理：因为LLN是资源受限型网络，所以有必要评估并比较每种技术的能耗和开销（网络中的报文量）。

5.2 结果分析

完整性性能如图4所示：

图4 故障检测计时器对完整性的影响

两种ALLONE方法的结果要优于基于计时器的静态FaT2D算法。此外，C-SAT的完整率最高（70%-95%）。很显然，这是因为C-SAT中的计时器进行了调整，以实现所有故障的迅速检测。然而，无计时器HB算法只能检测出网络中所有故障的50%。因为，采集的来自所有节点的信息在送给应用前HB无法做出决策，所以检测方法的速度非常慢。检测时间如图5所示：

图5 故障检测计时器对检测和恢复时间的影响

从图5中可以显著看出这点。如上文所述，HB需要等待较长时间才能决策是否出现节点故障。为此，它的检测时间要长于基于计时器的FaT2D、C-SAT和A-SAT。然而，如果考察这3种算法的检测和恢复时间，会发现C-SAT的性能最优。请注意，检测和恢复时间相加便确定了故障处理的整个时间（先是检测和通知，然后是抑制和路径恢复）。HB没有定义任何恢复机制。

另一方面，3种算法中A-SAT的精度最高如图6所示：

图6 故障检测计时器对精度的影响

很明显，这是因为A-SAT中利用公式进行了计时器更新，以实现差错率最小化。尤其地，HB在这方面的性能也较优，因为它宣布进程为故障进程所需时间较长。因此，它可避免出现差错。

对LLN来说，能耗、内存空间和带宽是重要约束，因此需要评估故障检测机制对电池使用量和开销的影响。

即使C-SAT和A-SAT部署了专门的计时器更新机制，但是与静态计时器相比，电池能耗的差异很小，如图7所示：

图7 故障检测计时器对能耗的影响

这一结果非常有前景，因为部署专门的故障检测机制导致的额外开销可以弥补节点故障后无用传输导致的开销，如图8所示。

图8 故障检测计时器对开销的影响

此外，使用本地交互和在数据报文中捎带确认故障通知，显著降低了网络开销。与无计时器HB相比，这些特征显著提升了故障检测性能。实际上，HB方法将额外的报文转发给网络中的所有节点，以便传输故障检测信息（即每个节点的计数器），而部署的所有基于计时器的方法使用数据报文来传输这些信息。此外，报文只传输给直接相邻节点。它在数据传输过程中将会到达其他节点。与静态计时器FaT2D相比，C-SAT和A-SAT两种计时器调整方法不会导致额外的能耗。

6 总结

本文提出一种新的故障检测机制ALLONE。ALLONE的特征如下：（1）它考虑了能源约束（能量，内存，带宽），是一种低功耗有损网络的广义故障检测模型；（2）报文交换模式基于相邻节点间的本地信息交换，而不是基于系统中的全局节点信息交换；（3）可以容忍间歇性故障，通过一种交互式动态计时器对故障检测步骤进行调整。

此外，引入A-SAT和C-SAT两种计时器调整策略，使得本文可以根据应用要求来调整ALLONE的运行性能。如果降低虚警率更为重要，则应使用A-SAT，对密集型网络来说尤其如此。相反，如果检测所有故障比避免差错更为重要，则最优选择是C-SAT。两种方法均可提升检测时间和数据传输方面的性能。此外，仿真结果还表明，将故障检测信息捎带进数据报文及利用自适应计时器，可以节约能耗和带宽。

[1] Chandra T.D.and Toueg S. Unreliable failure detectors for reliable distributed systems [J]. Journal of the ACM, 2006,11(4):631-643.

[2] 王明,张春熹,伊小素.基于自适应心跳算法的分布式系统故障检测器[J].北京航空航天大学学报,2013,39(7):1601-1609.

[3] 饶翔,王怀民,陈振邦.云计算系统中基于伴随状态追踪的故障检测机制[J].计算机学报,2012,35(5):856-870.

[4] 李景林.网格环境下的故障检测服务研究[J].计算机应用与软件,2010,27(6):120-123.

[5] Quevedo D E, Nešić D. Robust stability of packetized predictive control of nonlinear systems with disturbances and Markovian packet losses [J]. Automatica, 2012,48(8): 1803-1811.

[6] Mahmood K, Rizk A, Jiang Y. On the flow-level delay of a spatial multiplexing MIMO wireless channel[C]. Communications (ICC), 2011 IEEE International Conference on. IEEE, 2011:1-6.

[7] Taneja S, Kush A. A Survey of routing protocols in mobile ad hoc networks [J]. International Journal of Innovation, Management and Technology, 2010, 1(3): 2010-0248.

[8] Alotaibi E, Mukherjee B. A survey on routing algorithms for wireless Ad-Hoc and mesh networks [J]. Computer Networks, 2012, 56(2): 940-965.

[9] Narra H, Cheng Y, Cetinkaya E K, et al. Destination-sequenced distance vector (DSDV) routing protocol implementation in ns-3[C]. Proceedings of the 4th International ICST Conference on Simulation Tools and Techniques. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2011: 439-446.

[10] Yi J, Adnane A, David S, et al. Multipath optimized link state routing for mobile ad hoc networks [J]. Ad Hoc Networks, 2011, 9(1): 28-47.

[11] Yang P, Luo W, Xu L, et al. TCP congestion avoidance algorithm identification[C].Distributed Computing Systems (ICDCS), 2011 31st International Conference on. IEEE, 2011: 310-321.

[12] Zhangjie Wang, Xiao Li. A new real-time Heartbeat Failure Detection[C]. 4th International Conference on Wireless Communications, Networking and Mobile Computing, 2008:1-3.

TP393

A

2015.03.28）

1007-757X(2015)07-0034-04

赵英姿（1971-），女，陕西洛川人，东莞理工学校，高级讲师，研究方向：移动互联网、大数据、软件工程，东莞，523000