基于时间序列数据的无线传感器网络的异常检测方法*

彭能松,张维纬*,张育钊,黄 焯,郑力新

(1.华侨大学工学院,福建 泉州 362000;2.工业智能化技术与系统福建省高校工程研究中心,福建 泉州 362000)

无线传感器网络WSN(Wireless Sensor Networks)作为沟通主观感知世界和客观物理世界的桥梁,是一种全新的信息获取和处理技术,是物联网的重要支撑技术之一,已经得到了迅速的发展和广泛的应用[1],包括国防、军事、医疗保健、环境监测、制造业和其他许多领域[2-3]。

随着无线传感器网络规模的增加,传感器网络的异常检测越发的关键。尤其是对于一些紧急事件,例如化学物质泄漏、火灾等,往往需要及时预警并采取紧急处理措施。但是,恶劣的部署环境和传感器本身的不可靠性导致传感器产生错误的读数,从而影响传感器网络的异常检测。

现有的空间离群检测算法通常分为三步[4-5]:首先,通过最小邻数来确定基于空间属性的邻域关系。其次,使用空间属性来计算离群的程度,捕获对象与其空间邻域之间的差异。最后,将具有最大空间离群度的n个对象输出为异常点。在进行空间离群检测时需要与邻居节点交换信息,额外的通信会加快传感器节点能量的消耗。外部的因素或传感器节点自身的问题(如能量耗尽等),导致无线传感器网络错误节点增加,利用WSN的空间属性将降低事件的检测率。

WSN的时间属性记录着周围环境随时间的变化规律,当事件发生时,例如火灾发生时温度会在短时间内急剧上升。也就是说,事件发生后会持续一段时间,并且事件的特征随着时间具有某些变化规律。利用WSN的时间属性进行异常检测具有很高的研究价值。对无线传感器网络中的异常数据进行检测通常要考虑两个问题[6]:①错误传感器会影响整个网络对事件的检测;②传感器能量有限,应尽量减少网络中消息通信,降低传感器能源的消耗。

基于此,本文从传感器网络的时间属性入手,采用分布式检测方法对传感器网络进行异常检测。实验结果和分析表明了本文方法减少了错误传感器对事件检测的影响,提高了事件的检测率并降低了传感器节点能量的消耗。

本文第1节介绍已有的相关工作及研究成果;第2节将介绍传感器网络异常检测的方法及相关定义,并给出本文使用的符号定义;第3节介绍基于时间序列的无线传感器网络异常检测方法;第4节是实验结果及分析;最后是本文的小结。

1 相关工作

Krishnamachari B等[7]最早提出一种分布式的局部算法,通过空间(邻居节点)交换感知信息(0表示正常数据,1为非正常数据),统计邻居检测到事件的概率,结合节点故障概率,最后利用Bayesian分析的方法,决定是否发生了错误或事件。李桂丹等[8]提出一种分布式的容错事件边界检测算法,节点通过和邻居节点交换一次信息,通过简单地计算识别故障;并利用统计比较的方法判断其是否处于事件边界。这种方法算法复杂度低,容错性高。但比较依赖传感器网络的密度,密度越大检测率越高。魏畅[9]等提出一种基于约简策略与自适应SVDD(Support Vector Data Description)的离群检测方法,利用基于数据分布密度准则和数据流时间相关性自适应更新决策模型,取得了很好的检测效果。高建良等[10]提出了基于加权中值的故障诊断策略,对邻居节点测量数据进行进行加权处理,测量数据之间差距的方法来检测故障节点,但文中没有涉及事件的检测。费欢[11]等改进k-means 算法,根据无线传感器数据特点,采用欧氏距离为指标,根据数据到聚类中心的距离判断数据的异常。姜旭宝等[12]提出一种基于变宽直方图的异常数据检测算法,将相同特性的高频区域合并,减少不必要的数据传输,降低网络开销。曹冬磊等[13]从事件的时空相关性入手,提出了一种分布式的无线传感器网络事件区域检测的容错算法,通过检验事件随机过程的统计特征和传感器本地采样值构成的时间序列的符合程度来实现容错,但随着网络错误节点的增加,事件检测率也随之降低。赵志刚[14]将传统的置信区间用于异常数据的检测,在实际应用中取得很好的检测效果。李云飞[15]提出一种中位数的置信区间讨论了Ⅰ型极小值分布总体位置参数和尺度参数的区间估计问题。

受文献[14-15]的启发,本文将改进的置信区间用来检测数据是否存在异常。借鉴文献[11,16]采用距离检测离群点的思想,结合文献[13]的事件阈值函数,提出区间差异度的概念,作为异常来源的判断。并针对以往成果的不足:采用空间属性的异常检测方法对传感器网络密度要求高以及当错误节点增加事件检测率降低,误报率增加。本文从时间序列数据入手提出了以时间序列为基础的无线传感器网络异常检测方法,实现采样集中异常值的检测,识别故障节点和事件节点。

2 WSN异常检测基本原理

一般当传感器在连续的一段时间内,检测的数据偏离正常的数据,就可以认为有异常发生。而导致异常的原因有很多,特定区域发生事件称为事件异常;由自身故障或外部引起的称为发生故障或发生错误。

由于采用传感器网络空间属性将加快节点能量消耗,随着无线传感器网络故障节点的增加,事件检出率降低的问题。因此本文的检测方法采用传感器网络时间序列数据。改进置信区间,估计小范围的总体样本波动区间,用于异常值的检测,再利用区间差异度判断异常的来源。

2.1 时间序列数据模型

本文从WSN的时间相关性角度分析,在进行数据分析前需先建立一个时间序列数据模型。假设在监测区域随机的部署有n个传感器进行数据的采集。传感器节点通过底层时间同步机制保证采集和传输的数据同步性。

由于传感器节点的存储能力有限,不能满足时间序列数据的无限增长性,本文采用滑动窗口处理数据,节点只保存最新的k个数据。滑动窗口具体定义为:

定义1滑动窗口模型(Sliding Window Model)[17]为数据流最新的k个数据元素维护一个窗口,假设新数据元素从右边进来,当新数据元素到达,最左边的元素将过期,窗口向右滑动一个数据元素。

假设在某一个采样周期内,任一传感器采集的数据集为R(ti)={r(t1),r(t2),…,r(tn)}其中t1,t2,…,tn为采样时刻。设节点当前的窗口数据为{r(t1),r(t2),…,r(tp)},当新数据r(tp+1)到达且为正常数据时,窗口向前滑动,同时将窗口中的数据更新为{r(t2),r(t3),…,r(tp+1)},后续的数据以此类推。

当建立滑动窗口模型之后,要对时间序列数据计算置信区间和区间差异度。

2.2 置信区间和区间差异度

2.2.1 置信区间

如何确定传感器t时刻的读数r(t)是否异常,传统的阈值方法存在阈值范围难以确定的问题,太小或太大会产生误报或者漏报。而传感器网络采集的数据在不同的部署环境具有不同的特点,例如在某些温度变化很大的环境中,即使数据变动较大,数据也是正常的;而在有些稳定的环境下,有可能小的波动就是异常。根据数据特点采用置信区间判断异常值。

在自然条件下假设正常数据在范围[a,b]内波动,而异常数据往往与正常数据有较大的差异,一般反映为样本的极值,它们会对统计推断带来不良的影响[15],而样本的中位数能很好的抵抗异常值的干扰,越靠近中位数的样本其抵抗能力越强[18],因此本文采用中位数构造枢轴量。

设X1,X2,…,Xn是来自均匀分布的总体X～U(a,b)的独立同分布样本,设med为样本X1,X2,…,Xn的中位数[15]。

(1)

在方差δ2未知的情况下采用样本方差S2来计算中位数的置信区间[14]。

(2)

(3)

易验证T为关于μ的枢轴量,对于给定的α,令

(4)

即

(5)

得到置信度为1-α的置信区间

(6)

由式(6)知该区间为总体样本中位数的一个估计区间,将式(6)做相应的变形得到总体样本的估计区间。

(7)

式(7)即为总体样本区间估计,但区间估计的精度受样本数k和置信度α的影响较大,样本数k和置信度α的选择将在实验结果及分析中说明。

2.2.2 区间差异度

为了定性的描述传感器t时刻的读数r(t)与总体样本{r(t1),r(t2),…,r(tp)}的关系,即r(t)与置信区间[LCL,UCL]的差异。而衡量个体差异的方法有很多,主要分为两大类:距离度量和相似度度量,其中距离度量主要有欧几里得距离和明可夫斯基距离等;相似度度量包含向量空间余弦相似度和皮尔森相关系数等。本文根据距离度量的思想提出区间差异度的概念,定义如下:

定义2区间差异度:对于样本空间点rt(i),其区间差异度γ表示rt(i)与置信区间的差异程度,公式如下:

(8)

式中:rt(i)为传感器t(i)时刻的读数,UCL(Upper Confidence Limit)为置信区间上限,LCL(Lower Confidence Limit)为置信区间下限。γ表示t(i)时刻的读数与置信区间的差异程度,γ越大说明传感器读数距离总体样本越远,为异常值的可能性越大。

在本文中只考虑异常值大于正常值的情况,若检测异常值小于正常值的情况只需将式(8)换为式(9)即可。

(9)

当检测到异常值后需要验证异常值的来源,判断是节点异常还是突发事件,首先对判断条件进行分析。

(10)

(11)

式中:Rth(t)为判断事件的阈值函数[13],En(t)是正确的传感器在正常区域中的读数的期望函数;Ee(t)是正确的传感器在事件区域中读数的期望函数。ξ是判断是否发生事件的重要指标,如果区间差异度大于ξ,则认为发生事件。

综上,置信区间对样本总体参数估计及差异度采用距离衡量类间相似程度的思想为进行异常值检测提供了理论基础,在此基础上,本文提出了一种利用WSN时间序列数据进行异常检测的方法。本文的方法不仅适用于高密度的传感器网络,对于低密度非均匀分布的传感器网络同样适用。

本文中使用的符号和术语定义如表1所示。

表1 符号定义

3 异常检测

本节将给出一种以WSN时间序列为基础,分为异常数据识别,异常来源验证两个步骤,利用置信区间识别传感器数据集中可能存在的异常数据点,在检测到异常数据点后,需计算γ和ξ从而区分其异常来源。下文将分别进行详细说明。

3.1 异常数据识别

在自然环境下,传感器的采样值rt(i)表现为在小范围内小幅度的波动,但出现异常时则会在短时间内出现明显的偏差[18],且事件特征至少可以持续Tth时间[13]。

传感器节点里保存k个正常数据,数据可在部署前保存在传感器节点里或部署后节点保存采集的正常数据。利用k个正常值和给定的置信度α计算得到总体样本的区间估计[LCL,UCL]。如果r(t)不满足式(12),那么该测量值可能为异常数据。

LCL≤r(t)≤UCL

(12)

式中:UCL,LCL分别为置信区间的上下限,r(t)为t时刻采样值,当r(t)满足(12)时更新滑动窗口的数据元素。

此外,当传感器节点发生故障时,可能在连续的采样时刻内产生同样的读数[19],即

r(t)=r(t-1)

(13)

将式(12)和式(13)称为判断传感器读数是否异常的判断条件。

3.2 异常来源验证

当某个传感器t时刻的读数r(t)的值不在区间[LCL,UCL]内或r(t)=r(t-1)时就认为发生了异常;为确定异常来源需要计算数据与置信区间的区间差异度γ和ξ,在Tth时间内,计算m次区间差异度的值,并计算平均值μ(γ)如果μ(γ)<1可以认为是由测量误差或置信区间预估偏差引起的。

如果μ(γ)>ξ且r(t)≠r(t-1),认为该节点检测到事件。

如果μ(γ)<ξ或r(t)=r(t-1),认为该节点发生错误。当节点发生故障时,传感器采集的前一刻数据可能丢失,为了避免数据的丢失,在传感器节点发生故障前将数据备份到邻居节点。当m/2次满足条件(μ(γ)<ξ或r(t)=r(t-1))时,认为该节点即将发生故障,这时将该传感器节点的数据向所有邻居节点传播。

本文的伪代码描述如下:

Input:r(t),En(t),Ee(t),Tth,ΔT,k,α,Rth(t);

Calculating confidence intervals

if(LCL<=r(t)<=UCL andr(t)!=r(t-1)){

Update sliding window

status=Normal;

}

else{

while(every ΔTtime andt′

Calculatingμ(γ)andξ

if(μ(γ)<1 andr(t)!=r(t-1)){

ErrorCount+=1;

}

if(μ(γ)<ξorr(t)=r(t-1)){

FaultCount+=1;

if(FaultCount>m/2){

broadcasting data to all neighbors

}

}

if(μ(γ)>ξandr(t)!=r(t-1)){

EventCount+=1;

}

t′+=ΔT;

}

if(ErrorCount>2m/3);

status=Error;

if(FaultCount>2m/3);

status=Fault;

if(EventCount>2m/3);

status=Event;

3.3 性能分析

从时间复杂度和空间复杂度考虑,假设滑动窗口中的数据流规模为w,滑动窗口的大小为k,w>k。进行一次数据更新,滑动窗口有w-k次的数据输入。每更新一次窗口就要重新计算置信区间,所以时间复杂度O(w-k),空间复杂度为O(k)。所以本文的算法即使在大规模的数据中也不会出现数据灾难。

与采用WSN空间属性的方法相比,本文只从WSN时间数据入手,没有和邻居节点交换信息,不产生额外的通信消耗。只有当节点即将发生故障的时候向邻居传播数据,以消耗少量的能量,提高算法的安全性。

4 实验结果及分析

为了对本文的算法进行定性的分析,引入节点的检测率(True Positive Rate)和误报率(False Positive Rate)[20]用来衡量算法的可靠性。

定义3事件节点检测率(Event True Positive Rate ETPR)ETPR(C):

(14)

定义4事件节点误报率(Event False Positive Rate EFPR)EFPR(C):

(15)

定义5错误节点检测率(Fault True Positive Rate FTPR)FTPR(C):

(16)

定义6错误节点误报率(Fault False Positive Rate FFPR)FFPR(C):

(17)

式中:Ev为实际事件节点集合,S为事件区域所有节点,Er为实际错误节点集合。

由于估计的置信区间存在精度偏差,有可能将正常节点识别为误差节点,所以引入误差节点误识率。

定义7误差节点误识率(Error False Recogni-tion Rate EFRR)EFRR(C):

(18)

式中:N为正常节点集合。

如前文所述样本数k(滑动窗口大小)和置信度α的选择会影响置信区间的估计值。样本数太少会造成较大的偏差,影响算法的性能。由于传感器节点空间资源有限,样本不能太大否则会导致传感器节点能源过快消耗。为了确定样本数和置信度大小,本文通过实验来进行选择。

本文的实验是在python2.7平台上,n个传感器均匀的部署在32a×32a的区域中。假设事件过程{r(t)}和错误随机过程{r′(t)}分别满足r(t)～N(μ,σ2)和r′(t)～U(En(t),Ee(t)),对∀t,模拟实验中取μ=100,σ=10。假设传感器的采样频率为10 Hz,即ΔT=0.1s,Tth=1s,m=10。

实验1 本实验n=1024,错误节点占传感器节点总数的10%。假设事件发生在(17,5)到(27,15)的11a×11a区域。α取值为95%或99%。实验结果均取100次实验结果的平均值,仿真结果如表2所示。

表2 不同样本数和置信度下的实验结果

随着样本数增加,同一个置信度下,检出率总体先增加后减小,误报率总体先减小后增加。在样本数为30时有较好的检测结果,为减小因置信区间估计导致的误差节点误识率EFRR(C),选择样本数为30,置信度为99%作为后续实验的参数。

为验证本文方法的效果并评估其性能与文献[13]的方法进行对比实验。

实验2 比较本文的方法在不同规模,相同的错误节点(0.5%)下的性能。文献[13]使用其论文描述的实验参数δ=1.96,C=8。图1为一次实验的快照,圆点为错误节点。实验结果如图2～图5所示。图2和图3为事件区域事件的检测率和误报率,图4和图5为错误节点检测率和误报率。本文采用WSN的时间属性,所以在不同规模传感器网络下具有较高的事件检出率和较低的事件误报率,且错误节点同样保持较高的检测率和低的误报率。实验结果表明本文的方法在不同规模的传感器网络下算法稳定性高,受传感器网络规模影响小。

图5 错误节点误报率

图1 一次模拟实验快照

图2 事件节点检测率

图3 事件节点误报率

图4 错误节点检测率

实验3 为了验证不同错误节点下算法的稳定性,采用传感器节点数量n=1 024,并和文献[13]做比较。实验结果如图6～图9所示。

图6 事件节点检测率

图7 事件节点误报率

图8 错误节点检测率

图9 错误节点误报率

图6和图7为事件区域事件检测率和事件误报率,实验表明,即使随着错误节点的增加,采用本文的算法还能保持较高的检出率,而误报率也不会随着错误节点的增加而增加,这是因为本文采用WSN时间序列的数据,这样可以减少因WSN空间错误节点影响而产生误判的情况。

图8和图9为错误节点检测率和误报率,当错误节点增加时,传感器节点的错误检测率保持98%以上,误报率保持0.5%以下。

5 结语

本文从数据的时间相关性入手,只需少量的数据通过简单的计算就能估计出较好的总体样本区间,计算区间与数据的区间差异度实现异常来源的判断,算法复杂度低,计算量小而且不产生额外的传感器网络通信,有效的延长了传感器网络的寿命。受传感器网络规模的影响小,在传感器网络错误节点增加的情况下仍保持较高的检测率和较低的误报率。

参考文献:

[1] Zhou Zhangbing,Xu Jiabei,Zhang Zhenjiang. Energy-Efficient Optimization for Concurrent Compositions of WSN Services[J]. IEEE Access,15 Sep 2017,PP(99):1-1,ISSN:2169-3536.

[2] Bai X,Liu L,Cao M,et al. Collaborative Actuation of Wireless Sensor and Actuator Networks for the Agriculture Industry[J]. IEEE Access,2017,5(99):13286-13296.

[3] Qiu T,Zhao A,Xia F,et al. ROSE:Robustness Strategy for Scale-Free Wireless Sensor Networks[J]. IEEE/ACM Transactions on Networking,2017,PP(99):1-16.

[4] Ayadi H,Zouinkhi A,Boussaid B,et al. A Machine Learning Methods:Outlier Detection in WSN[C]//International Conference on Sciences and Techniques of Automatic Control and Computer Engineering. IEEE,2016:722-727.

[5] Xu W,Gao H,Liu Y,et al. An Adaptive Spatial Outlier Detection Algorithm with no Parameter for WSN[C]//International Conference on Information Fusion. 2017:1-8.

[6] Luo X,Dong M,Huang Y. On Distributed Fault-Tolerant Detection in Wireless Sensor Networks[J]. IEEE Transactions on Computers,2006,55(1):58-70.

[7] Krishnamachari B,Iyengar S. Distributed Bayesian Algorithms for Fault-Tolerant Event Region Detection in Wireless Sensor Networks[J]. Computers IEEE Transactions on,2004,53(3):241-250.

[8] 李桂丹,孙雨耕,刘丽萍,等. 分布式无线传感器网络容错事件边界检测[J]. 计算机工程与应用,2009,45(17):28-32.

[9] 魏畅,李光辉. 基于约简策略与自适应SVDD的无线传感网络 离群检测方法[J]. 传感技术学报,2017,30(9):1388-1395.

[10] 高建良,徐勇军,李晓维. 基于加权中值的分布式传感器网络故障检测[J]. 软件学报,2007,18(5):1208-1217.

[11] 费欢,李光辉. 基于K-means聚类的WSN异常数据检测算法[J]. 计算机工程,2015,41(7):124-128.

[12] 姜旭宝,李光耀,连朔. 基于变宽直方图的无线传感器网络异常数据检测算法[J]. 计算机应用,2011,31(3):694-697.

[13] 曹冬磊,曹建农,金蓓弘. 一种无线传感器网络中事件区域检测的容错算法[J]. 计算机学报,2007,30(10):1770-1776.

[14] 赵志刚,屈剑锋. 基于WSN和置信区间计算的转播机房温控系统[J]. 计算机工程与应用,2011,47(30):219-223.

[15] 李云飞. 极值分布参数基于不完全数据的区间估计[J]. 统计与决策,2015(13):81-83.

[16] 陈圣兵,王晓峰. 基于样本差异度的SVM训练样本缩减算法[J]. 计算机工程与应用,2012,48(7):20-22.

[17] Datar M,Gionis A,Indyk P,et al. Maintaining Stream Statistics over Sliding Windows[J]. Siam Journal on Computing,2002,31(6):1794-1813.

[18] Huber P J. Robust Statistics[J]. Journal of the American Statistical Association,1981,78(381):1248-1251.

[19] Lee D W,Kim J H. High Reliable In-Network Data Verification in Wireless Sensor Networks[J]. Wireless Personal Communications,2010,54(3):501-519.

[20] Fei H,Xiao F,Guang-Hui L I,et al. An Anomaly Detection Method of Wireless Sensor Network Based on Multi-Modals Data Stream[J]. Chinese Journal of Computers,2017,40(8):1829-1842.