基于灰色预测的分布式传感器网络故障检测方法*

张 健

(1.北京工业大学嵌入式软件与系统研究所，北京100124；2.北京建筑大学理学院，北京100044)

基于灰色预测的分布式传感器网络故障检测方法*

张 健1，2*

(1.北京工业大学嵌入式软件与系统研究所，北京100124；2.北京建筑大学理学院，北京100044)

针对无线传感器网络节点故障原因复杂，基于灰色预测理论，提出一种故障检测方法。算法通过分析在某一采样间隔内，观测节点数据变化趋势是否与邻居节点变化趋势一致，从而确定节点是否异常。仿真实验表明，算法故障检测能力较强，且避免了节点瞬间失效情况的出现。同时该算法设计简单，易于硬件实现。

无线传感器网络；故障检测；灰色预测；分布式

无线传感器网络是一种由大量分布的传感节点组成的多跳、自组织型网络，由于其体积小、灵活性强、价格低廉、无人值守等特性，被广泛应用于环境监测、医疗卫生、智能家居和军事等领域。但同时，也由于其自身资源的限制、尤其是能量、内存及计算能力等方面的限制，以及外部环境的影响，传感器节点特别容易发生故障。因此需要有效的容错设计技术来满足其可靠性要求。无线传感器网络容错设计需要考虑三个方面：故障模型、故障检测与诊断、修复机制［1］。从整体而言，故障可分为三个层次：部件级、节点级和网络级［2］。故障发生的位置不同，表现形式不同，容错设计也不尽相同。本文侧重传感器节点的故障检测问题。考虑到无线传感器网络自身的限制，检测算法必须使得节点能量消耗最小化以及整个网络寿命极大化。

邻居协作是无线传感器网络的一种有效被动式检测方法，高建良等提出一种基于加权中值的故障检测算法(WMDFS)，对于每个节点引入信任等级的概念，定义邻居节点的权重，根据节点的测量值与邻居节点的加权中值之间的差异，判断节点是否失效［3］。Yim等在文献［4］中提出DFD故障节点检测方案的改进算法(IDFD)［5］，算法中首先引入衡量某时刻相邻节点测量差异dij的阈值θ1和衡量相邻时刻相邻节点测量差分Δdij的阈值θ2，如果相邻节点不能同时满足两个阈值的条件，则至少有一个节点失效，然后通过节点与邻居节点中可能存在失效风险的个数，预判定节点是否为故障节点，最后通过与邻居节点中预判定故障节点的个数，给出最终的判定方案。文献［6，7］中，通过历史数据引入可信节点的概念，通过与可信邻居集合节点的比对，判定故障节点。文献［8］中，首次提出“伪故障节点”的概念，提出一种具有故障容忍的检测方案(CSFD)。

本文在充分分析无线传感器网络特点的基础上，结合上述算法的信任等级、伪故障节点等概念，将集中式网络检测算法推广到分布式网络检测算法，提出基于灰色预测的分布式传感器网络故障检测方法（GFD）。

1 网络及故障模型

图1 基于分簇的无线传感器网络结构

考虑如图1所示的基于分簇的无线传感器网络，假设大量的传感器节点被随机部署在同质的应用环境中，所有传感器节点时间同步，且具有相同的通信范围，可表示为无线传感器网络图G(V,E)，其中V={V1,V2,…,Vn}为无线传感器节点集合，E为通信边集合，若Distance(Vi,Vj)≤l，则Edge(Vi,Vj)∈E，这里l为传感器节点的通信半径，Vi,Vj互为邻居节点。由于传感器节点部署较为密集，相邻的节点监测数据的变化趋势近似相同，监测结果也应相近［9］。

根据文献［2］中指出故障可能发生在无线传感器网络的不同层，比如物理层、硬件层、系统软件层和中间件，本文对此并不关心，我们假设当故障发生时，传感器节点仍然能够完成指定任务，但结果却与实际产生较大偏差。

2 灰色系统基本理论简介［10］

在政治生活中，人民群众提出增加“透明度”，用以某一决策形成的过程，维护大众权益。一般习惯用“黑—灰—白”三种颜色表示信息透明状态。灰色系统理论研究的是“部分信息已知、部分信息未知”的“小样本”、“贫信息”不确定性系统，它通过对“部分”已知信息的生成、开发实现对现实世界的确切描述和认识。例如，给定原始数据序列

如图2(a)所示，X(0)的曲线是摆动的，震荡幅度较大，本身没有任何明显的规律。但如果对原始数据做一次累加生成新的序列记为X(1)，则

显然 X(1)具有了明显的递增趋势，如图2(b)所示。

图2 灰色序列生成示意图

2.1 累加生成算子

累加生成一种常用的由灰变白的方法，在灰色系统理论中占有极其重要的地位。

定义1 累加生成算子

设X(0)为原始序列Τ为序列算子，

式中：

则称Τ为 X(0)的一次累加生成算子，记为1-AGO(accumulating generation operator)。称r阶算子Τr为X(0)的r次累加生成算子，记为r-AGO。习惯上，记

一般地

其中

定理表明，当r充分大时，序列X(r)充分光滑。

2.2 GM(1,1)模型

设X(0)为非负序列

其中，x(0)(k)≥0(k=1,2,…,n)。 X(1)为 X(0)的1-AGO序列，Z(1)为X(1)的紧邻均值生成序列，

其中

称

为GM(1,1)模型的基本形式，其中参数-a称作发展系数，反映了序列的发展态势，b称作灰色作用量，反映数据变化的关系。

称

为GM(1,1)模型的白化方程，也叫影子方程。

则GM(1,1)模型的最小二乘估计参数列满足［11］

相应地，白化方程的解也称时间响应函数为

GM(1,1)模型的时间响应序列为

还原值

3 基于灰色预测的故障检测算法(GFD)

3.1 符号说明

表1 相关符号说明

3.2 问题提出

考虑节点Vi，每隔Δk时间，收集测量数据，经过M时刻观测后，收集到节点Vi的测量数据集构建节点Vi的邻居节点集合N(Vi)，根据收集到的N(Vi)的测量数据集，判定节点Vi是否为故障节点。

3.3 GFD算法

表2 GFD算法步骤

3.4 几点解释：

①选用灰色预测模型算法，原因基于无线传感器节点部署环境非常复杂，我们很难分析影响测量结果的众多因素，灰色预测是一种对含有不确定因素系统的进行预测的方法，且算法计算简单，计算量小，适用于无线传感器网络。

②算法中选择预测数据序列的平均误差作为节点信任等级变化的标准，避免的节点“瞬时故障”的问题。

③算法中对邻居节点预测值进行了加权，大大降低了信任等级低的节点的影响。

④对于无线传感器网络中的能力消耗的多少主要取决于节点间的通信，本算法中每个周期内，仅传递M+1时刻的预测值XˆM+1及节点的信任等级λ，对网络不会带来较大负担。

⑤本算法不仅仅适用于如图1的网络结构，同样对各种结构的传感器网络均适用。

4 仿真实验

4.1 算法特性验证

本文利用Matlab软件进行仿真实验设计，通过改变传感器节点的通信半径，考虑在邻居节点个数及节点故障率的不同水平下，GFD算法的故障检测精度问题以及节点观测窗口M的大小对故障检测精度的影响。实验仿真了WSN监测区域为30×30单元的区域，随机部署200个传感器节点，为保证算法的有效性，重复进行若干次［13］。下图给出当故障率p为10%，邻居节点平均个数k为10时，GFD算法检测效果，表3给出了不同p,k,M下GDF算法检测精度。

图3 p=0.1k=10，GFD算法检测前后对比

表3 不同p，k，m下GDF算法检测精度

从图4中可以看出，当每一周期样本容量固定时，GFD算法检测精度随传感器网络节点故障率p的增大而降低，随邻居节点个数k的增加而提高。图5说明，当传感器网络故障率p一定时，GFD算法精度会随着邻居节点个数的增加以及周期采样节点个数的增加而提高。图6给出了k=10，k=20时，GFD算法在不同故障率p、不同采样间隔M下的对照图，同样可以得出，GFD算法精度与故障率p成反比、与采样间隔M成正比。

图4 M=15 GFD算法检测结果对比图

图5 p不同情况下GDF算法检测结果对比图

图6 k不同情况下GDF算法检测结果对比图

4.2 算法性能验证

为了验证算法的有效性，对比文献［4］，在32×32的区域内随机部署1024个监测点，如图7所示；选取两个性能指标故障检出率和错误告警率，其中故障检出率为检出的故障数量与总体故障数量的比值，错误告警率为被误判为故障的数量与正常节点数量的比值。

图7 随机部署1 024个传感节点示意图

图8和图9选取采样周期M=15，对比文献［4］中的算法发现，在平均邻居节点为15和20时，在故障检出率和错误告警率两个方面，基于灰色预测的故障检测算法表现出优势。由此可见，GFD算法比较适用于传感器节点部署较为密集的环境中。

图8 算法的故障检出率

图9 算法的错误告警率

5 结语

本文提出基于灰色预测的分布式传感器网络故障检测方法（GFD），该算法充分利用了灰色预测对含有不确定因素系统的进行预测的特点，较传统的基于数据挖掘理论的故障检测算法［14-15］，计算量大大减小，算法设计更简单，易于硬件实现，文中进行了数值仿真，证明了算法的有效性。

［1］李晓维.无线传感器网络技术［M］.北京：北京理工大学出版社，2007.

［2］Koushanfar F，Potkonjak M，Sangiovanni-Vincentelli A.Fault-Tolerance in Sensor Networks［M］.Handbook of Sensor Networks.CRC Press，2004.

［3］Gao J L，Xu Y J，Li X W.Weighted-Median Based Distributed Fault Detection for Wirelesssensor Networks［J］.J Softw，2007 (18)：1208-1217.

［4］Chen J R，Kher S，Somani A.Distributed Fault Detection of Wireless Sensor Networks［C］//Proceedings of the International Conference on Mobile Computing and Networkings，LosAngeles，CA，USA；ACM：New York，USA，2006：65-72.

［5］Yim S J，Choi Y H.An Adaptive Fault-Tolerant Event Detection Scheme for Wireless Sensor Networks［J］.Sensors，2010，10(3)：2332-2347.

［6］黄日茂，邱雪松，高志鹏，等.无线传感器网络中邻居数据分析的故障检测方法［J］.北京邮电大学学报，2011，34(3)：31-34.

［7］黄日茂.无线传感器网络故障管理机制与算法［D］.北京：北京邮电大学，2012.

［8］Wang T Y，Chang L Y，Dun D R，et al.Distributed Fault-Tolerant Detection Via Sensor Fault Detection in Sensor Networks［C］//Proceedings of the IEEE 10th International Conference on Information Fusion，Quebec，Canada，2007：1-6.

［9］Kar S，Moura J M F，Ramanan K.Distributed Parameter Estimation in Sensor Networks：Nonlinear Observation Modelsand Imperfect Communication［J］.IEEE Trans.Information Theory，2012，58：3575-3605.

［10］刘思峰，党耀国，方志耕，等.灰色系统理论及其应用［M］.北京：科学出版社，2010.

［11］王能超.数值分析建模教程［M］.北京：高等教育出版社，2010.

［12］Rajasegarar S，Leckie C，Palaniswami M，et al.Distributed Anomaly Detectionin Wireless Sensor Networks［C］//Proceedings of the IEEE International Conference on Communications Systems，ICCS，Singapore，2006.

［13］Lee M H，Choi Y H.Fault Detection of Wireless Sensor Networks［J］.Comput Commun，2008，31：3469-3475.

［14］胡志鹏，魏立线，申军伟，等.基于核Fisher判别分析的无线传感器网络入侵检测算法［J］.传感技术学报，2012，25(2)：246-250.

［15］赵锡恒，何小敏，许摇亮，等.基于免疫危险理论的无线传感器网络节点故障诊断［J］.传感技术学报，2014，27(5)：658-663

张 健（1980-），女，山东德州人，北京工业大学博士研究生，北京建筑大学讲师，主要研究领域为无线传感器网络、数据挖掘技术。

A Gray-Forecast Algorithm of Fault Detection for Wireless Sensor Networks*

ZHANG Jian1，2*
(1.Embedded Software and Systems Institute，Beijing University of Technology，Beijing 100124，China；2.School of Science，Beijing University of Civil Engineering and Architecture，Beijing 100044，China)

Wireless Sensor Networks(WSNs)are widely used in environmental monitoring，health care，smart home，military fields，and so on，because of its small，flexibility，low cost and unattended.And faults are common due to the bad environment and unattended.In order to ensure WSNs’service is normal，it is necessary to detect the faults.According to the complex reasons of wireless sensor network nodes failure，this paper presents a new fault detection algorithm based on based on gray prediction theory.The algorithm is that within a sample interval，it is analyzed that the observed node’s data trend is consistent with the trend of changed in the neighbour nodes to determine whether the node is abnormal.The experiment shows fault detection precision is very high，and the algorithm avoid the node instant failure.Meanwhile，the algorithm is simple，easily implemented in hardware.

wireless sensor network(WSNs)；fault detection；gray-forecast；distributed

TP393

A

1004-1699(2015)08-1188-06

��7230

10.3969/j.issn.1004-1699.2015.08.015

项目来源：北京建筑大学科学研究基金项目（00331614047）

2014-09-29 修改日期：2015-05-04