基于WSN的分布式容错算法研究

刘 洋，王 军，2*，吴云鹏

(1. 苏州科技大学，江苏苏州 215009； 2. 中国科学院长春光学精密机械与物理研究所，吉林 长春 130033)

1 引言

WSN是由大量具有感知和通信能力的低功耗节点组成的多跳自组织网络，其通常部署在一些人迹罕至的恶劣环境中，这就要求WSN具备一定的容错能力以应对极端环境所导致的各类故障。一般影响WSN性能的故障分为硬故障和软故障，硬故障主要是节点自身组件损坏或电源能量不足等因素造成的，而软故障主要是节点采集传输数据的误差率太大，不能得到准确的观测值。而如何设计可靠的容错机制，实现WSN数据传输的高效准确，是目前研究的热点。

当前，国内外大多数解决方案都是从实践上研究容错机制，在文献[3]中，Somaye等人设计了一种基于WSN的容错和节能聚类算法(fault tolerance and energy clustering，FTEC)，FTEC算法折中考虑了能耗和容错这两个矛盾因素，在具体容错过程中，该算法依据一定规则划分有效簇，并对CH节点导致的故障提出了相应的自愈恢复策略，一定程度上提高了WSN的容错性能，不过该算法没有考虑实际算法开销以及数据传输时延，只能在特定环境下应用；文献[4]中，Chalhoub等人提出了一种以机器学习技术为核心的容错框架，对不同故障类型的传感器进行检测与跟踪，以便能够快速进行自愈操作，但是该系统没有考虑机器学习模型需要遍历所有节点，此方案会产生大量额外的通信开销，不适用于大规模网络；文献[5]中，Menaria等人提出了一种基于Petri网的分布式模型进行WSN容错，该方案通过邻居节点感知信息的时空相关性来检测节点故障，能在物理层上极大的容忍硬件故障，然而该算法没有考虑负载平衡的解决方案，随着网络节点数的增加，算法效率会逐渐降低，不能满足多节点网络需求；文献[6]里，蒋和徐等人基于不相交路径设计了一种路由容错系统，通过色彩空间分离技术搭建节点间的数据路由路径，避免了节点路由路径的缠绕问题，大大增强了数据传输稳定性，但是其不能完全克服随机路径选择过程中的网络故障，实用性稍差，难以大规模推广。

针对上述问题，本文提出了一种基于分簇的分布式容错算法(distributed fault-tolerant algorithm，DFTA)，通过故障检测、故障分类和故障恢复进行容错机制设计，首先监视系统是否存在任何不当行为(故障检测)，之后分析收集的数据并对网络进行故障分类，最后使用建议的恢复算法在CH级别上进行恢复操作，并且利用该算法克服能量损失和硬件故障，延长了WSN内节点的生命周期。

2 网络与节点模型

2.1 网络模型与假设

如图1所示，假设有N个初始能量相同的静态传感器节点随机分布在一个二维区域内，它们分组成簇并自己选定CH，簇内的传感器节点根据自己的传输半径以多跳的方式相互连接，各个簇内的节点通过各自CH能够互相通信，最终将来自所有簇的聚合消息都传输至基站，用以进一步处理信息。设所有节点初始状态正常，都有属于自己的独立ID号，结构、功能和传输半径均一致，并以固定的速率感知来自环境的数据，健康的节点可以将自己感测到的数据交换到邻居节点上，且周期性地将自己处理过的数据和广播信息传输给CH节点，通过同步通信，CH在一个固定的时间间隔内接收所有节点的数据和广播消息用以保持网络状态，并且CH具有数据检查和汇聚节点的属性功能。

图1 WSN分簇网络模型

2.2 节点能耗模型

DFTA算法设计的最终目标是为了延长整个WSN的工作寿命，所以需要以节点能量耗尽所经历时间为最大时间建模，所以本算法在Heinzelman等人提出的能耗模型上做了一些改进，在WSN数据传输能量消耗上仅针对数据传输和数据接收，令电池能量损耗为0，其能耗方程式如式(1)所示。

(1)

式(1)中，为传输1比特数据后的剩余能量，单位为焦耳()，为每个节点的初始能量，代表一定时间内传输1比特数据所消耗的能量，为传输时间，单位为微秒()，为接收到1比特数据后的剩余能量，是接收1比特数据所消耗的能量，代表接收时间，为电池的能量所示，本模型中假设电池为理想状态，不考虑其损耗，并设定所有传输路径具有相同的负载。

2.3 路径损耗模型

为了进一步降低网络内能量损耗，本文算法基于自由空间路径损耗模型做了一些改进，DFTA中，路径损耗(path loss，P)与距离成正比，其路径损耗模型如式(2)所示。

=

(2)

2.4 CH竞选模型

在实现算法之前，需要对WSN内节点进行分簇和竞选CH的处理，首先任意传感器节点i在其通信范围内广播一条包含其能量、位置和编号的消息，为了减少网络内节点的整体能量消耗，控制参加竞选的节点数量，在该模型内设置一个竞选能量阈值T，如果节点能量大于该阈值则可以参加CH竞选，反之则不行。每一轮中，符合条件的节点计算其CH竞争半径(radius of competition，R)的大小，并综合考虑节点剩余能量和与基站(base station，BS)的距离等因素，其计算公式如式(3)所示

(3)

式(3)中，表示第个节点到的距离；是任意节点到的最大距离；代表自定义的最大竞争半径，其单位都是米；为当前竞选节点的剩余能量；为竞争系数，取值为0到1之间的常数。针对本文大规模网络的应用背景，考虑节点能量与距离因素对的影响，将的取值定为80-100，取值为065，当≅，≅时，节点的竞争半径最大，其竞选成功率也达最高。

3 分布式容错算法

提出的算法是通过故障检测、故障分类和故障恢复来实现WSN节点的物理层故障，属于自愈技术的范畴，在DFTA算法中，网络内的每个节点通过周期性的广播消息向CH节点表示其运行状态，CH再根据簇内节点状态进行下一步动作，该算法共分为部署、故障检测和故障恢复这三个阶段。

3.1 部署阶段

在部署阶段中，主要包含两个状态，分别为设置状态和稳态状态，DFTA算法路由协议是基于LEACH的概念，其路由协议的时间栈如图2所示。

图2 部署阶段路由协议时间栈

在设置状态时，应用CH竞选模型选择合适的节点成为CH，每一轮中，选定的CH节点向簇内所有节点广播一条广告消息，通知所有节点更新状态消息，在接受到该消息之后，所有非CH节点确定自己所在簇，并开始进入工作状态。

在稳态状态时，各个簇中的节点开始感知消息，并将感知到的数据与自身邻居节点进行聚合比较，然后在规定的时间间隔内将感测到的信息传输给各自CH，最后经由CH汇总数据信息传输至BS。由于CH过多通信需要消耗大量能量，所以每一轮都必须重新竞选CH节点，延长网络内节点的生存寿命。

3.2 故障检测阶段

本阶段主要是在CH级别和节点级别上进行故障诊断与检测。在节点级，传感器节点定时发送和接收来自邻居节点的所有数据，时间设置为300μs，之后节点使用处理器将自身的采集数据与邻居数据进行对比，以此来诊断各个传感器节点；当关闭收发机电路时，传感器节点进入睡眠状态，时间设定为299μs。在CH级，CH节点接收簇内各节点收集的聚合数据，并使用式(4)对簇内节点进行综合评估。

()=()-()(0≤≤)

(4)

式(4)中，()为信息差分向量，()为邻居节点在一个周期内感知到的数据信息值，为差分因子，()表示传感器节点在周期内感知到的信息值，通过计算()与()之间的向量差来对节点进行评估。CH从接收到的数据筛选发送方标识符，以识别哪些传感器节点能够成功发送数据，在周期t内无法向CH发送广播消息的节点则被标识为故障节点，成功的对节点状态进行检测。

3.3 故障恢复阶段

本阶段为DFTA算法最重要的一环，主要是在节点级别和CH级别上联合处理传感器节点的硬件故障。当传感器节点没有在周期t内感知到环境信息，则会被检测为“感知错误”，CH将其声明为业务节点；若传感器节点在一个周期时间t内都没有从其邻居们接收到任何数据，其会被检测为“接收故障”，CH会将其声明为仅感测节点，它只感知环境信息发送给CH，而不从其邻居接收任何数据。

当节点电池能量大于预设置的休眠阈值时，CH会将其标识为活动节点，随着节点能量达到一个阈值极限时，该节点会保留接收到的信息并向CH发送一条休眠通知消息，宣告自己为休眠节点，CH反馈消息并移除该节点，使用其它节点来替代其工作，至此网络重新进入活动模式，新的节点开始向CH广播消息，CH节点反过来将该节点添加到网络中用以更新拓扑；若故障节点未得到CH反馈，它将一直保持睡眠状态，CH重新选择路由路径并将该节点移出拓扑。而针对业务节点与仅感测节点，CH也会将其标识为故障节点，并使用其它节点来更新拓扑。其具体的容错算法流程图如图3所示。

图3中，N表示网络中的活动节点数量，N为故障节点数量，N代表故障存疑节点，需要进一步确认其状态；该容错步骤主要是从广播消息与数据包(data packet，DP)这两方面来进行CH判断，以此来检测节点组件故障和电源模块状态，若节点发生故障，CH则开始进入恢复阶段，其具体恢复流程如图4所示。

4 实验结果及分析

4.1 实验设置

在本节实验中，使用MATLAB仿真软件对提出的DFTA算法进行验证，令所有传感器节点以分布式方式随机分布在一个300m×300m正方形区域内，每个节点的最大传输距离设定为75m，其初始能量都为10J，节点休眠阈值设置为初始能量的3%，CH竞选阈值设为初始能量的70%，所有节点的数据传输时间都规定为300μs，网络内节点故障概率随机设置，对节点数量N={50，100，…，300}进行重复比较，并根据CH竞选模型将网络分成不同的簇，对实验方案独立执行50次取其平均值作为最终结果，其仿真伪代码和参数表如下。

图3 一轮容错流程图

图4 CH级故障恢复

仿真伪代码:1) For random(k) do {随机使用不同的节点故障概率}2) For N=50 to 300 step 50 do {从50到300个节点,每次递增50}3)H←randamnetwork(N);{构建随机网络} 4) For A in DFTA do {运行DFTA算法} 5)S←A.InitPhaseTopo(K,H);{初始化网络拓扑}6)TN←CalculateNodeAverageLifeTime(S);{计算节点的平均生存时间}

表1 仿真参数表

4.2 仿真结果及性能分析

4.2.1 检测精度分析

为了验证DFTA算法在故障检测上的性能优势，使用故障检出率和故障误检率作为故障检测精度的分析指标，其中故障检出率=已检出的故障节点个数/网络故障节点总数，故障误检率=检测为故障的正常节点数/网络正常节点总数。对WSN内节点分别在传感器故障、接收器故障和电池故障情形下进行检测精度比较，并针对这三种故障设置不同的节点故障率，按照实验设置每种实验方案独立执行50次，取平均值为最终结果，其实验结果如图5(a)和(b)所示。

图5 三种故障下的检测精度

由图5(a)和(b)可知，DFTA算法针对不同故障情形都具有较高的故障检测精度。当节点发生传感器故障，且网络故障率低于30%时，算法的故障检出率在80%以上，误检率在3%以下，这是由于节点发生感知或发射器故障(统称传感器故障)时，它不会传输任何感知信息给CH，且无法与正常邻居节点进行信息交互，故CH节点对此类故障有较高的检测精度；当节点发生接收器故障，且网络故障率在40%以上时，故障检出率在70%左右，误检率在6%以下，检测精度良好；当节点出现电池故障时，由于网络内节点初始能量是随机设置的，仅通过节点本身发送休眠信息，CH很难分辨出节点是否已经达到休眠阈值进入休眠，所以在网络故障率同为30%左右时，电池故障的检测率相比于传感器故障降低了8%，又因为CH通过接收电池故障节点的邻居节点消息，可判断出该节点的故障类型，故相同的网络故障率条件下，其故障检出率还高于节点接收故障。从整体的实验结果来看，DFTA算法对各种故障类型都具有很好的适应性，这对于本文容错算法的实际应用提供了重要支撑。

4.2.2 网络容错率分析

为验证故障节点数量对DFTA算法容错性能的影响程度，将其与网络级联故障自愈算法(network cascade fault self-healing，NCFSH)、故障冗余路由算法(failure redundant routing algorithm，FRRA)和分布式异构聚类算法(distributed heterogeneous clustering algorithm，DHCA)进行比较，并且在每次实验中，增加网络节点个数，其失效节点容错率比较图如图6所示。

图6 不同节点数量下的容错率

图6清楚的展示出了不论节点数量多少，DFTA算法都具有较其它三种算法更高的故障节点容忍率。对于拥有200个节点的WSN而言，当网络中超过37%、24%和20%的部署节点出现故障时，FRRA、NCFSH和DHCA算法均不能维持WSN基本功能，而本文算法仍可进行正常感测工作，这是由于所提算法是在CH级进行故障恢复，并在完成一轮恢复工作后重新进行CH竞选，极大程度上保证了CH能够正常进行恢复工作，使网络拥有高容错率。而随着节点数量的增加，DFTA算法的容错率提升幅度最大，其性能方面远超其它同类算法。

4.2.3 能量消耗分析

图7展示了DFTA、FRRA、NCFSH和DHCA这四种算法在节点数量一定时WSN内能量消耗情况，其中横轴代表传输数据包次数，纵轴为网络内平均能量消耗。从图中可以看出这四种算法的变化趋势大致相同，DFTA算法的能量消耗率比NCFSH算法节省了16%，比DHCA算法节省了22%，也比FRRA算法节省了28%，这是因为本文的节点能耗仅针对数据传输和数据接收，通信路径损耗也只是与距离的发射和接收功率成正比的，再加上CH节点会移除网络中发生故障的节点，减少了故障节点的能量消耗，并且增加节点休眠唤醒机制，大大减小了WSN整体能量消耗，达到了预期结果。

图7 能量消耗比较图

4.2.4 节点生存率分析

节点生存率是衡量容错算法适用性的一个重要指标，由已部署节点总数减去被移除网络拓扑的节点个数比上节点总数来表示。本小节在节点数为300的网络规模下对每一轮的存活节点数量进行仿真分析，并将其与DHCA、FRRA和NCFSH这三种算法进行比较，其实验结果如图8所示。

图8 节点生存率比较图

如图8所示，本文算法在平均节点生存率方面有较高优势，其相较于NCFSH算法节点生存率提高了13.6%，比DHCA算法提高了19.5%，比FRRA算法提高了20.7%，这主要是由于DFTA算法在每一轮都会重新竞选CH，大大减小了CH节点的能量消耗，并且将这种高能耗平均到了多个节点上，再加上算法采用的节点能耗模型和路径损耗模型，进一步降低了网络内能量消耗，从而延长了部署节点的生存时间，表现出了良好的性能。

5 结论

WSN作为现代通信系统的重要组成部分，高容错能力是提高其网络性能的有效方法，本文以网络故障管理中故障容错能力为研究目标，提出了一种基于WSN的分布式容错算法(DFTA)来检测和恢复节点硬件故障，并分别在节点级和CH级执行检测和恢复。DFTA算法与FRRA、NCFSH、DHCA算法相比，在节点故障检测上平均能够达到80%左右的精度，在网络容错率和能量消耗方面性能也均高于其它三种算法，最后在节点生存率方面相较于其它三种算法分别提高了13.6%、19.5%、20.7%，显示出了理想的故障容错能力。

在未来研究中，会侧重构造更多的传感器网络用以模拟真实环境样本，评估软件故障对WSN的实际影响，在增加大量数据包的基础上，构建一种合适的路由算法，降低通信开销，并在CH节点上应用自配置机制来管理各个簇内网络，最后能够延长WSN网络寿命和算法稳定性。