针对历史数据与邻居协作融合的思想所引生的无线传感器网络故障检测问题, 提出了一种检测机制, 不仅适用于故障节点随机分布的场景, 也适用于故障节点集中分布的场景.仿真结果表明:当节点度数减小、节点故障率升高时, 检测精度仍可以维持在96.7%以上.本检测机制只需要交互较少的信息, 从而节省了节点的通信能耗和信道带宽.
A new fault detection mechanism based on historical data and neighbor-coordination was presented. It gives the combination of detection methods was given based on historical data with the detection ways from neighbor-coordination. Simulation shows that the fault detection mechanism based on historical data and neighbor-coordination can be not only applied to the scene where the nodes are randomly distributed, but also for scenarios in which the failed nodes are intensive. The detection accuracy can reach 96.7% or more although the average degree of the nodes reduces or the failure rate of the nodes increases. In addition, different nodes only communicate few messages with each other in this detection mechanism. And thus, the energy of the node and the bandwidth of the channel can be saved.
无线传感器网络(WSN，wireless sensor networks)[1]已经被广泛应用到国防军事、环境监测、交通管理、医疗卫生等领域[2].由于传感器节点的能量、存储容量及计算能力有限，并且应用环境恶劣，传感器节点非常容易发生故障，从而影响传感器网络的服务质量[3].因此，研究WSN中节点的故障检测技术变得尤为重要.
目前，邻居协作[4]的故障检测机制通过交换邻居测量值进行故障状态的判断，由于需要大量的消息交互，将占用过多的网络带宽.为了解决上述问题，提出将历史数据和邻居协作方法融合的故障检测机制(HDNC, history data and neighbor-coordination)，适用于节点度较小和故障率较高的场景，不仅保证了较高的故障检测精度，还降低了交互的消息数量进而节省了节点的能量与通信的带宽.
1 HDNC检测机制HDNC检测机制的过程如下.
1) 选取根节点：计算各节点的邻居数，找到邻居数最大的节点，并将其作为根节点；如有2个或者多个节点的邻居数相等，则选择能量较大的作为根节点；如果各节点的邻居数以及能量都相等，则选择历史故障次数小的节点作为根节点.
2) 第1轮检测：采用改进的残差比故障检测机制(MRRFD, modified residual ratio fault detection)判断根节点的状态，如果根节点为正常节点则作为网络节点状态判断的起始参照节点；如果根节点为故障节点，则从剩余节点中按照1) 重新选取根节点并判断其状态，直到找到参照节点.
3) 第2轮检测：结合邻居节点之间的状态关系，用参照节点判定出邻节点的状态.如果邻节点为正常节点，可以作为参照节点对它的邻节点进行判定；如果邻节点为故障节点，则不能作为参照节点.
4) 第3轮检测：如果依然存在未知状态的节点，则重新执行检测，直到所有节点状态都为已知.
2 改进的残差比故障检测机制MRRFD残差比故障检测机制(RRFD，residual ratio fault detection)常用来检测网络流量的异常，并将此引进到传感器故障检测中[5]. RRFD的决策函数是关于一个点和滑动窗的似然比，它检验一个点与滑动窗之间的异常变化，检测个别和局部之间的变化关系，能突出显示短时间内的异常变化情况[6].
改进的残差比故障检测机制(MRRFD)：加强了数据的选取条件，排除了故障测量值的干扰；对决策函数做了改进，使之更合理；再通过决策函数判断yt+N+1是否在故障时采用了自适应阈值，可以更好地决策不同时刻不同测量值是否出现故障.
MRRFD的检测步骤如下.
步骤1 筛选滑动窗数据
对测量序列…yt+1, yt+2, yt+3, …, yt+N…进行筛选，剔除序列中故障的数据，用正常的N个数据建立滑动窗.
步骤2 零均值化
将测量序列…yt+1, yt+2, yt+3, …, yt+N…进行均值化，得到序列…xt+1, xt+2, xt+3，…，xt+N+1….
步骤3 建立AR模型
对零均值化后的序列…xt+1, xt+2, …，xt+N+1…采用AR(2) 模型得到残差{…et+1, et+2, …，et+N+1…}.
|
(1) |
其中，i=1, 2, …, N+1. φ1、φ2为模型系数.系数φ1、φ2有以下估计式：
|
(2) |
步骤4 确定决策函数DFt(N+1)
决策函数定义如下：
|
(3) |
|
(4) |
其中et+N是对应检测点的残差.
DFt(N+1) 的确定不同于RRFD，在计算δe选取滑动窗数据，待判定的
(t+N+1) 时刻的数据并不参与计算，这样就避免了决策函数受到(t+N+1) 时刻数据的影响，进而使得决策函数更加合理.
步骤5 确定自适应阈值U (N+1)，L (N+1)
采用刷新机制把当天和前一天的数据行为综合起来，使得历史数据的影响起主导作用.综合方法如下.
1) 对阈值预测值进行建模
|
(5) |
其中: p (N+1) 是时刻(t+N+1) 的阈值预测值，也就是时刻(t+N+1) 正常模型；et+N是t时刻的残差；et+N+1是t+1时刻的残差；γ是加权常数，它控制新数据在模型中所占的比重.
2) 设定一个容许范围[L (N+1), U (N+1)]
如果测量值完全符合上述正常模型，那么一定为正常.这种判定太过苛刻，所以需要设定一定的允许范围，只要在这个范围内就可以判定为正常.允许范围的上下界如下：
|
(6) |
|
(7) |
|
(8) |
|
(9) |
步骤6 通过决策函数判断yt+N+1是否故障：
当L (N+1) ≤DFt(N+1) ≤U (N+1) 时，yt+N+1是正常的；反之，yt+N+1是故障的.
3 邻居协作思想要判定某一个节点Si的测量值yi是否正常，只需要将yi与邻节点中的正常节点S正的测量值进行比较，如果测量值之差小于阈值θ，则认为节点Si为正常节点；如果测量值之差大于阈值θ，则认为节点Si为故障.
邻居协作思想的判断依据：对于相邻节点，依据局部性原理，如果节点都无故障，相邻节点的测量值应该非常相近，其差值dijt(dijt=|yi-yj|)应该小于某一阈值θ(θ为节点测量值的正常值范围).当其中1个节点故障或2个节点都故障时，其测量值之差dijt可能会超过θ，定义节点间的状态关系如下.
1) 当dijt＜θ时，即相邻两节点测量值之差dijt小于阈值θ，则两者状态关系为相似.此时，两者状态相同，可能同为正常或同为故障.
2) 当dijt≥θ时，即相邻两节点测量值之差dijt大于或等于阈值θ，则两者状态关系为不确定.此时，两者可能同为故障或1个正常1个故障.
因此，通过比较正常的节点S正与待判定节点Si的测量值，进而判定该节点的状态是否合理.当测量值之差小于阈值θ，两节点的状态相同，又因为参与比较的节点为正常节点，所以待判定节点为正常节点；当测量值之差大于或等于阈值θ，那么两节点的状态为不确定，又因为参与比较的节点为正常节点，所以待判定节点为故障节点.
4 仿真结果采用Matlab 7.0进行仿真.假定200个节点随机分布，分别从故障检测精度、平均消息交互数方面对分布式故障检测(DFD, distributed fault detection)、改进的分布式故障检测(NDFD, new distributed fault detection)及基于历史数据及邻居协作的故障检测(HDNC, history data and neighbor-coordination)等方法进行仿真与比较.
故障检测精度R和平均消息交互数M可作为评估算法性能的2个指标.故障检测精度指的是判断正确的节点数与节点总数的比值.平均消息交互数指的是不同节点之间消息交互的总数与节点总数的比值.
仿真中，节点的故障率P分别为0.1、0.2、0.3、0.4、0.5、0.7，它们表示在不同场景中，每个节点发生故障的概率；平均节点的度d分别为3和5，它们是指每个节点平均的邻居数.
根据图 1，DFD、NDFD的检测精度对平均节点度有一定的依赖，在相同故障率条件下平均节点度越小，检测精度越低.随着节点故障率P的增大，DFD和NDFD的检测精度都大幅下降，当P≥0.4时，这2个机制的检测精度降到了70%以下.提出的机制表现出良好的性能，不仅消除了对平均节点度的依赖，还在节点故障率P增大的情况下，依然可以保证很高的检测精度.甚至在P=0.7时，检测精度仍然高达96.7%.由此可见，HDNC可以良好地被应用于大规模故障的场景中.
|
图 1 DFD、NDFD、HDNC的检测精度 |
在图 2中，HDNC的平均消息数远远小于DFD和NDFD的平均消息数，也就是说，相对于DFD和NDFD，HDNC大大节省了信道的带宽，并在一定程度上节省了节点的能量.这对于带宽、能量和计算能力都有限的无线传感器网络来说，无疑具有重大意义.具体来说，随着故障率P的增大HDNC的平均消息数反而减小，这是因为P增大时，作为参照节点的正常节点减少，进而邻居协作机制的应用次数就会减少，此时主要依靠改进的残差比故障检测机制(MRRFD)对自身节点的状态进行判定，进而节点间交互的消息数会减小.然而，不论DFD还是NDFD，其平均消息数都呈现先下降后上升的趋势.故障率P增大，趋势状态为可能正常(LG, likely good)的节点就会减小，进而交互的消息数就会下降；当故障节点数大于1/2时，会误将可能故障(LF, likely faulty)的节点错判成LG节点，这样判定出的LG节点增多，自然会导致交互的消息数增大.
|
图 2 DFD、NDFD、HDNC的平均消息数 |
图 1、图 2说明了故障节点随机分布的情况，为了表明3种不同检测机制对于集中故障的处理能力，专门对其进行了仿真.假设d表示平均节点度. 图 3表明，即使在d=5且P=3时，DFD和NDFD的检测精度为80%左右.随着P的增大，这2种机制的检测精度大大下降，根本无法处理大规模的集中故障.相反，提出的HDNC无论在d=3或d=5时，随着P的增大，依然能够保持非常高的检测精度，即HDNC可以良好地检测大规模集中式故障.
|
图 3 大规模集中故障时3种检测机制的检测精度 |
由图 4可以看出，无论在d=3或d=5时，HDNC的平均消息数都远远小于DFD和NDFD.也就是说，在处理大规模集中故障时，HDNC依然可以节省带宽、节省能量.
|
图 4 大规模集中故障时3种检测机制的平均消息数 |
综上所述，提出的HDNC不仅适用于故障节点随机分布的场景，还适用于故障节点集中分布的场景.它解决了传统邻居协作检测机制(如DFD、NDFD)对于节点度的依赖问题，使得HDNC不仅可以应用于节点度较高的情况，也可以应用于节点度较低的情况.此外，HDNC解决了随着故障率增大，传统邻居协作方法失效的问题.即使故障率较高，HDNC依然能够维持很高的检测精度.除了检测精度这个常用指标，HDNC还考虑了信道带宽有限、节点能量及计算能力有限的因素，通过大大降低不同节点之间消息的交互数，实现了节省带宽、降低能量消耗及减小计算量的目的.
5 结束语传统的邻居协作检测机制(如DFD、NDFD)有如下缺点：平均节点度减小时，检测精度下降；节点故障率升高时，检测精度急剧下降；只关注检测精度，并未考虑节点的能量、信道的带宽等信息.针对以上不足，提出了HDNC故障检测机制，有效地将历史数据检测方法与邻居协作检测方法结合在一起，不仅提高了故障检测精度，还降低了消息的交互数.仿真结果表明，HDNC不仅可以处理随机分布的故障，还可以处理大规模集中故障.在平均邻居数较小、故障率较高的情况下，HDNC依然可以保持在96.7%以上的检测精度.
| [1] | Mini R A F, Loureiro A A F, Nath B. The distinctive design characteristic of a wireless sensor network: the energy map[J].Computer Communications, 2004, 27(10): 935–945. doi: 10.1016/j.comcom.2004.01.004 |
| [2] | Hsin C, Liu M. Self-monitoring of wireless sensor networks[J].Computer Communications, 2006, 29(4): 462–476. doi: 10.1016/j.comcom.2004.12.031 |
| [3] | Barborak M, Dahbura A, Malek M. The consensus problem in fault-tolerant computing[J].ACM Computing Survey, 1993, 25: 171–220. doi: 10.1145/152610.152612 |
| [4] | Jiang P. A new method for node fault detection in wireless sensor networks[J].Sensors, 2009, 9(2): 1282–1294. doi: 10.3390/s90201282 |
| [5] |
董言治, 刘松涛. 基于matlab的时间序列分析和动态数据建模[J]. 计算机工程, 2003, 29(12): 170–172.
Dong Yanzhi, Liu Songtao. Time series analysis and dynamic data modeling based on matlab[J].Computer Engineering, 2003, 29(12): 170–172. doi: 10.3321/j.issn:1002-8331.2003.12.054 |
| [6] |
杨雅辉. 网络流量异常检测及分析的研究[J]. 计算机科学, 2008, 35(5): 108–113.
Yang Yahui. Network traffic anomaly detection and analysis research[J].Computer Science, 2008, 35(5): 108–113. |