一种在线容错和邻居协作的传感器节点故障诊断算法

魏甜甜,曾雅丽,马梦莹,陈志德,2,3

1(福建师范大学 数学与信息学院,福州 350108)2(网络安全与密码技术福建省高校重点实验室,福州 350108)3(中国科学院 信息工程研究所 中国科学院网络测评技术重点实验室,北京 100093)

1 引 言

无线传感器网络(Wireless Sensor Networks,WSNs)常被部署在恶劣的环境中,导致网络中的传感器节点相对于其它网络更易发生故障从而影响整个无线传感器服务性能.WSNs节点故障[1]分为硬故障和软故障两类,硬故障是指传感器节点不能和其它节点通信,软故障是指传感器节点硬件部分正常,但感知或传送的数据不正确.

在WSNs故障诊断方面,研究人员已经做了很多相关的研究,并取得了很多成就.故障诊断主要有集中式和分布式两种主要方法.集中式主要是节点将数据信息传输到sink节点进行相关判断,因此导致靠近sink节点的传感器能量消耗巨大,缩短传感器节点生命周期[2].传感器具有数据存储、简单计算和节点通信的功能[3],并且与计算相比,节点通信耗能更大.分布式节点故障诊断算法是基于节点自身及其邻居节点数据信息进行故障诊断,有效地避免了集中式诊断的不足.一些经典的分布式故障检测算法,如基于k-means聚类的WSNs分布式故障检测算法[4],基于加权距离的容错(DFWD)的故障检测算法[5],分布式贝叶斯(Distributed Bayesian)故障检测算法[6],基于隐马尔可夫模型(HMM)的WSNs分布式故障检测算法[7],分布式故障诊断算(Distributed Fault Detection,DFD)[8]都是利用邻居节点数据的相似性对节点进行故障检测与诊断,存在邻居节点过少,故障发生率高时故障诊断正确率不高的问题.Muhamm-ed T等人[9]对节点数据进行建模分析,对节点数据预测分析,进而对节点状态进行判断.Panda M等人[10]提出基于概率知识的故障检测算法,该算法仅和邻居节点交换一次数据,判断正确率高.Ould-Ahmed-Vall 等人[11]提出了一个通用容错事件检测方案,仅适用于考虑事件高度本地化的检测.Ding M等人[12]提出并分析了两种用于故障传感器识别和容错事件边界检测的新算法,但对检测效率存在延迟.季赛等人[13]采用时间冗余的方法结合节点历史数据对节点进行状态判定.Lo C等人[14]则设计一种基于模型的分布式在线故障诊断,但仅对特定的故障类型做出诊断.Mahapatro A等人[15]提出一种在线分布式算法,通过比较相邻节点产生的数据和传播每个节点的决策来实现故障诊断.以上方法都受到邻居节点个数和故障发生率的影响,并且需要邻居节点不断交换数据,造成传感器节点的能量耗损严重.现有的关于故障诊断方面的研究工作中还存在以下两个问题尚未得到很好的解决:

1) 如何在邻居节点较少,故障发生率较高的情况下仍有较高的故障诊断正确率;

2) 如何有效地降低传感器节点由于故障检测而造成的能量消耗.本文针对这两个问题提出基于在线容错和邻居协作的故障诊断算法(A Sensor Fault Diagnosis Algorit-hm Using Online Fault-tolerant and Neighbor- cooperation,FDOFN),与分布式诊断算法DSFD[10]和经典算法DFD[8]的对比结果表明本文所提出的FDOFN在故障诊断正确率和通信代价上都有明显的优势.

2 系统模型

2.1 模型假设

1)假设所有传感器节点都只发生软故障,即均可接收和发送数据.

2)假设传感器节点可以确定自己的地理位置.

3)传感器节点具有相同的结构,感知相似的数据.

4)正常传感器节点数据在短时间内稳定变化,且不同节点同一时刻的测量数据服从正态分布.

2.2 网络模型及定义

设无线传感器网络可表示为G(V,E),其中V为传感器节点的集合,E为链路集合.设任意节点vi和vj的位置分别为(xi,yi),(xj,yj),则节点vi和vj之间的欧氏距离可以表示为:

(1)

当相邻的节点vi和vj之间的欧氏距离dist(vi,vj)小于通信半径R时,称这两节点在G(V,E)存在链路.对任意节点vi∈V的邻居节点集合可以表示为:

NEI(vi)={vj|vj∈V(vi,vj)∈E}

(2)

3 无线传感器节点故障检测算法

3.1 在线容错故障检测算法

由于在一个WSNs的检测环境中,传感器节点是连续采集数据的,传感器节点的数据是带有时间的数据,因此可以表示为时间序列.同一节点所收集到的数据在较短时间内应该是稳定变化的,也即相邻时刻之间的时间序列应是相似的.对于时间序列的相似性我们采用欧氏距离进行计算.

记节点vi在t-1时刻及其之前的m个数据的时间序列为Xt-1=(x1,x2,…,xm),t时刻及其之前的m个数据的时间序列为Xt=(x2,x3,…,xm+1),Xt-1与Xt的时间序列的欧氏距离为:

(3)

Xt与Xt+1的时间序列的欧氏距离为:

(4)

由于节点时间序列应是相似的,为此两者之间的欧氏距离之差应在一定的范围内,即|DXt-1,t-DXt,t+1|

为便于表示我们用dt+1=|DXt-1,t-DXt,t+1|表示在时刻t+1时的两时间序列之差.则在时刻t时的时间序列欧式距离之差为dt=|DXt-2,t-1-DXt-1,t|.

考虑到复杂多变的无线传感器网络环境影响以及数据的正常波动,只要不满足条件就向邻居节点发出反馈是不现实的,同时会加大节点能量的耗损,为此引入节点可容忍度值rmax.定义节点初始值r=1,若dt+1

算法1.在线容错故障检测算法

输入:传感器节点vi在某段时间的时间序列数据Xit及其邻居节点数据NEIXit;r0,rmax;阈值d0;

输出:节点诊断状态(Fvi=0正常 orFvi=2可疑)

1) fori←1NEIXit//遍历所有邻居节点

2) 计算Xit的自身欧氏距离DXt-1,t和DXt,t+1

3)d=|DXt-1,t-DXt,t+1|

4) ifd

5)r=r0;Fvi=0;

6) else ifd≥d0&r0

7)r=r+1;Fvi=0

8) else ifd

9)r=r-1;Fvi=0

10) else ifd≥d0&r≥rmax

11)Fvi=2,启动基于邻居协作故障诊断机制

12) end

3.2 邻居协作故障诊断机制

当节点被标记为可疑节点之后,需要通过基于邻居节点的数据的空间相关性进一步确定该节点的真实状态.为此本文利用节点数据空间相似性,建立邻居协作故障诊断机制.当节点vi为可疑节点时,根据邻居协作故障诊断机制,诊断向其邻居节点NEI(vi)发送请求,邻居节点收到故障请求之后,邻居节点根据自身状态做出回复:

a.如果vj∈NEI(vi)为正常节点,则发送该时刻感知数据给节点vi;

b.如果vj∈NEI(vi)为可疑节点,则发送该时刻感知数据给节点vi,并在下一时刻发送故障请求给节点vj的邻居节点NEI(vj);

c.如果vj∈NEI(vi)为故障节点,则不发送感知数据给节点vi,仅发送一个表示节点发生故障的消息′f′给节点vi.

(5)

记Ni为节点vi非故障节点的邻居节点的个数,节点vi邻居节点的感知数据为NEIvxi(k),其中:

NEIvxi(k)={xvj(k)|vj∈NEI(vi),j=1,2,…,Ni}

(6)

(7)

(8)

N(k)={xv1(k),xv2(k),…,xvNi+1(k)}

(9)

(10)

(11)

其中med{|N(k)-medi|}表示N(k)中各个元素xvi(k),i=1,2,…,Ni+1与中值medi的差的绝对值的中位数.

则节点状态判定准则为:

具体实现如算法2所示.

算法2.邻居协作故障诊断机制算法

输入:vi在Fvi=2状态k时刻的数据vxi(k),NEIvxi在k时刻数据NEIvxi(k)及对应的节点状态.

输出:节点诊断状态Fvi=0正常 orFvi=1故障.

1) fori←1toNEIXit//遍历所有的邻居节点k时刻数据

2) ifFvi=0 orFvi=2

3)N(k)=NEIvxi(k)∪vxi(k)//构造非故障节点数据集

4) else

5) break

6) end

7) end

8) sortN(k)//升序排列集合N(k)

9) 计算集合N(k)中位数medi

10)mad=med{|N(k)-medi|}//计算中值绝对偏差的中位数

13) iftvi>3

14)Fvi=1//节点故障

15) else

16)Fvi=0//节点正常

17) end

综合在线容错检测阶段和邻居协作故障诊断从而完成对节点的最终状态的判定.节点状态判断整个流程如图1所示.

图1 故障诊断流程图Fig.1 Flow chart of fault diagnosis algorithms

4 实验结果及分析

本实验利用python3.0模拟在100*100m2的矩形区域内,通过随机函数部署一定数量的传感器节点.假设节点的测量数据为某个时刻的温度测量值,设传感器每隔时间T采集一次数据,其中正常节点的数据为[15.0-19.0]之间,发生故障的数据为[0-100]随机变化,同时考虑传感器节点所处环境复杂多变,在同一时刻数据加入5%的噪声数据.设置在线容错故障检测阶段参数d0=1.从故障诊断正确率和能量消耗(通信次数)两个因素衡量算法的性能.

首先,考虑参数rmax对实验结果的影响,分别模拟在100个节点,150个节点,200个节点时,通过改变通信半径分别实现平均邻居节点数目为k=5,k=10,k=15,k=20时在节点故障率为0.30时 FDOFN算法rmax对故障检测正确率的影响,经过多次实验,实验结果如图2(a)所示.图2(a)中x轴表示rmax的取值,y轴表示故障诊断正确率.

由图2(a)可知,当rmax<5时,节点故障诊断正确率变化不大.而在rmax=1,rmax=2时相对rmax=3,rmax=4时故障诊断正确率略低.原因是当rmax=1时,相当于节点基本没有执行在线故障检测机制,一旦节点数据发生异常就将节点标记为可疑节点,若此时可疑节点为故障节点,在邻居协作节点故障诊断阶段是初步诊断为可疑节点或者正常节点的集合,因此经过邻居节点故障诊断机制诊断,最终可能会将可疑节点诊断为正常节点或者故障节点.若此时可疑节点为正常节点,同样节点最终可能会被诊断为故障节点或者正常节点.特别是在邻居节点为5时,节点被标记为可疑节点之后,最终结果得到正确判定的可能性就更低.rmax=2时,节点故障诊断率略有提高,这是由于排除了当节点为正常节点时,由于噪声数据的影响,将节点误判为故障节点的情况.当rmax=3,rmax=4时,故障诊断正确率都相对达到最高,这是因为此时经过在线阶段的初步检测,可以将连续多次发生数据异常数据被标记为可疑节点的节点状态本身为故障节点的可能性更高,而此时又可以将故障节点有效标记为可疑节点,不至于由于rmax的影响,导致某些故障节点不能转化为可疑节点而造成将故障节点诊断为正常节点,造成故障诊断正确率的下降.当5≤rmax<8时,故障诊断正确率随着rmax值的增加而减小,这是因为由于节点在连续出现数据异常时,此时rmax值会增大,随着rmax值的增加,在线故障检测阶段需要连续数据异常的次数m就随之增加,也就是节点必须要连续m次发生数据异常,节点才有可能标记为异常节点.rmax值越大,节点标记为可疑节点的条件就越高,导致发生故障的节点不能转化为可疑节点,从而无法执行邻居节点故障检测机制,此时会导致故障节点的最终诊断状态为正常节点.rmax值越大,故障节点不能转化为可疑节点的可能性就越大,此时故障诊断正确率就越低.当rmax≥8时,部分故障节点基本不能转化为可疑节点,此时节点状态将错误判定为正常节点,而一些永久故障节点则随着时间的延续,最终转化为可疑节点,经过邻居协作阶段得以正确判定其状态.而正常的节点由于可容忍度值的增大,不会转化为可疑节点,即正常节点状态仍为正常节点,因此故障诊断正确率基本保持不变.而rmax=3和rmax=4节点故障诊断正确率基本一样,为减少节点能量通信次数,为此在本文中采用rmax=4为在线容错检测阶段的可容忍故障能力参数.

图2 Fig.2

然后考虑在节点个数相对更少的情况下,rmax对故障诊断正确率的影响.模拟仅有50个节点的情况下,通过改变通信半径,多次试验使得平均邻居节点位于2到5之间,分别考虑在故障率分别为0.05,0.10,0.15,0.20,0.25,0.30情况下,故障诊断正确率结果如图2(b)所示.当故障发生率为0.05时,节点故障诊断正确率尚能保持较高的故障诊断正确率,但当节点故障率升高时,特别是在节点故障率为0.25,0.3时节点诊断正确率无论在rmax取何值都有相对较低的故障诊断正确率.为此该算法在节点特别稀疏的场景下,和其他算法一样相比并不具备良好的优势,仍不能很好的适应节点邻居节点个数小于5的情况.这是因为本文算法FDOFN在邻居协作诊断机制方面,对邻居节点数据依赖较大,特别是当邻居节点个数小于5时,故障率发生较高时,由于可参照的正常节点个数较少,节点状态容易发生状态的误判.

为此综合以上实验,本文将考虑平均邻居节点个数为5以上的情形下,多次实验考虑本文算法性能.固定参数d0=1,rmax=4,在100*100m2范围内均匀分布200个节点,改变节点故障率和平均邻居节点数目,多次实验得到FDOFN故障诊断正确率如图3所示.从图中可知,该算法在邻居节较少、故障率较高时仍能达到较高的故障诊断正确率.这是由于本文算法FDOFN则通过在线容错检测的检测,降低了将正常节点误判为故障节点的概率.同时提高了将故障节点诊断为故障节点的可能性.若节点vi为故障节点,则节点vi必然会连续出现数据异常,从而此时节点为可疑节点,进入邻居协作故障诊断,而邻居协作故障检测阶段,数据均为初步诊断为非故障节点的数据(正常节点或者可疑节点),并且经过t值的判断,又很好的排除了极值的影响,从而节点vi被判定为故障节点,节点状态得以正确判定.若节点vi为正常节点,则只有当节点vi连续多次出现数据异常时才会将该节点判定为可疑节点,而由于在线容错节点可容忍度rmax的引入,将这种情况出现的概率大大降低.为此本文算法这种双重诊断的方法,极大的提高了故障诊断正确率.

图3 FDOFN算法故障诊断正确率Fig.3 Effects of fault probablity on the fault diagnosis accuracy of FDOFN

其次,考虑本文算法FDOFN和DSFD算法[10]、DFD算法[8]在不同节点故障率和不同平均节点个数的情况下的故障诊断正确率.实验结果图4、图5、图6、图7分别表示在平均邻居节点个数为5、10、15、20的四种情况下,不同节点故障率对故障诊断正确率的影响.由图4可知,在平均邻居节点个数k=5时,FDOFN算法比其他两种算法表现出更好的故障诊断正确率.而在邻居节点分别为为10,15,20时,FDOFN算法也仍保持了较高的故障诊断正确率.DSFD算法是基于统计学的3σ准则的原理,仅仅依靠某一时刻邻居节点的数据进行判断,当部分邻居节点在某时刻受到异常数据的影响时,故障检测的正确率也在一定程度上受到异常数据的影响.同时当故障率升高时,故障检测正确率也有所下降.DFD算法则是采用相邻节点在两个临近时刻感知的数据的差值做出判断,对于一个正常的节点vi,若其邻居节点中初步诊断状态为正常的节点个数小于其邻居节点的个数的一半时,会将该正常节点的状态误判为故障节点.特别是在邻居节点个数较少时,或在故障率发生较高的情况下,更容易出现初步诊断状态为正常的节点个数小于其邻居节点个数的一半的情况,此时节点状态会得到错误的判断.而本文算法FDOFN则克服了以上算法的不足,通过在线容错检测的检测,降低了将正常节点误判为故障节点的概率,同时提高了将故障节点诊断为故障节点的可能性,从而比其他算法更具有优势.

图4 k=5时故障率对正确率的影响Fig.4 Effcets of fault probability on the fault diagnosis accuracy when k=5

图5 k=10时故障率对正确率的影响Fig.5 Effcets of fault probability on the fault diagnosis accuracy when k=10

图6 k=15时故障率对正确率的影响Fig.6 Effcets of fault probability on the fault diagnosis accuracy when k=15

最后进行通信代价的对比.由于传感器节点消耗能量模块主要包括传感器模块、处理器模块和无线通信模块[17],传输1bit的信息100m的距离所需要的能量大约相当于执行3000条计算指令所消耗的能量.因此传感器节点的耗能主要在于节点与节点之间的互相通信.本文通过通信次数来衡量故障诊断造成的能量消耗.固定200个传感器节点,平均邻居节数k=5考虑在一定时间段内,节点采集数据10次.假设节点在第4次数据采集时发生故障,考虑三种算法在10次数据采集时间段内在k=5而节点故障率不同时,通信次数的变化.如图8所示,DSFD算法和DFD算法为对节点进行故障诊断,需一直同其邻居节点进行数据通信,而本文算法FDOFN仅在节点标记为可疑节点时才和其邻居节点进行通信,大大降低了节点之间的互相通信,因此其通信次数远远低于其他两种算法.

图7 k=20时故障率对正确率的影响Fig.7 Effcets of fault probability on the fault diagnosis accuracy when k=20

图8 k=5时故障率对通信次数的影响Fig.8 Effect of fault probability on the number of communications when k=5

综上可知,本文算法FDOFN在保持较高的故障检测正确率的同时,还能够极大地减少传感器节点的能耗,延长网络的生存周期.

5 结 论

通过分布式在线故障检测进行节点的状态判定是无线传感器故障检测的有效方法之一,本文方法的关键在于在线容错故障检测阶段具有一定的容错能力,降低了将正常节点诊断为故障节点的可能性,并且只在节点数据连续发生异常时才和邻居进行通信,使节点之间的通信大大减少,从而有效地减少节点的能量耗损,从而提高了传感器节点的使用寿命.同时基于邻居协作故障诊断机制利用改进的3σ准则有效地避免了异常数据造成的故障诊断干扰,进一步提高故障诊断正确率.仿真实验表明,该算法在有效地减少能量消耗的情况下,克服了传统算法对邻居节点较少、故障率高、故障诊断正确率低的缺点,对复杂的传感器网络环境也表现出良好的优势,并且适用于大规模无线传感器网络.