无线传感器网络中基于模式频繁度的异常检测方法*

施晓斌，吴丹萍，程红举

(福州大学 数学与计算机科学学院，福建 福州 350108)

0 引言

在WSN中，由于环境噪声和感知器件误差的影响，感知数据带有一定的不确定性。软件与硬件故障将导致不准确和不可靠读数的出现。而事件的发生也将导致与正态分布明显不同的观测值的出现。那些特征与正态分布特征明显不同的观测值被称为异常值[1]。异常值检测，是基于某种措施来识别偏离其余数据模式的数据实例的过程，用于过滤噪声数据，查找故障节点和发现用户感兴趣的事件。

区分异常值的来源是一个重要的问题。一般来说，如果检测到的异常值是错误或噪声数据，则应将其从传感数据中去除，以确保数据质量和准确性，并避免通信负载造成的能耗。但是，若是事件造成的异常值，消除异常值将导致关于事件的重要隐藏信息的丢失[2]。

传统的集中式异常检测技术将会产生巨大的能量和带宽的消耗，这对资源受限的WSN网络来说并不友好[3]。此外事件在网络中发生的概率通常不高，在没有发生事件的情况下收集到的数据价值是十分有限的。考虑到节点有限的资源，因此需要限制异常检测算法的复杂度，尽可能设计轻量级的分布式在线算法[4]。

本文考虑以下问题：如何以在线和分布式的方式快速准确地检测WSN中的异常数据，并区分异常值的来源。本文研究了流数据的数据变化模式和数据的空间相关性在异常检测问题上的运用，提出了一种基于数据变化模式频繁度和空间相关性的PFSC(Pattern Frequency and Spatial Correlation)异常检测方法。PFSC异常检测方法分两个阶段进行。第一阶段，为数据创建一个分布模型，根据数据变化模式的频繁程度筛选出潜在的异常数据；第二阶段，利用相邻节点数据间的空间相关性来区分异常值的来源，此处本文通过拉依达准则完成异常值来源的判定。

1 相关工作

针对WSN中集中式与分布式异常检测方法的研究，Lau等人[5]提出了一种基于名为CNBD的朴素贝叶斯框架的集中算法，其中端到端传输时间在sink处收集，并使用朴素贝叶斯框架进行分析。Subramaniam等[6]提出了一种用于传感器网络的分布式在线异常值检测技术，以分布式方式计算多维数据分布近似的框架，以便在资源有限的传感器网络中实现复杂的应用。Xu等人[7]通过比较连续时间实例的数据，得出是否存在瞬时故障的结论。如果存在瞬态故障，则使用其标记为正常的实例数据来校正数据。文献[8]提出了一种基于信誉的投票和决策树的分布式事件检测方法，并评估了用于早期发现灾害特别是住宅火灾的性能和适用性。

针对在线数据连续积累、实时更新的特点，文献[9]提出了一种环境数据流偏离历史模式的识别方法。该方法是基于数据流及其预测区间的自回归数据驱动模型。文献[10]将基于聚类的算法和最近邻异常值检测方法相结合，用于实现高效聚类和对异常值检测，训练阶段需要对一段时间内的观测值进行聚类。文献[11]提出了一种基于距离相似性的技术来识别传感器网络中的全局异常值。该技术尝试通过相邻节点之间的一组代表性数据交换来减少通信开销。每个节点使用距离相似度来本地识别异常值，然后将离群值广播到相邻节点进行验证。相邻节点重复该过程，直到网络中的整个传感器节点最终同意全局异常值。然而广播带来的通信开销使其无法应用到大型网络。

2 网络模型与相关知识

2.1 网络模型

WSN由随机部署在一个平面区域上的一组传感器节点S={s1,s2, …,sn}组成。节点i通信范围内的邻居节点用Si={s1,s2, …,sk}表示。节点i在时刻t的观测值表示为xi(t)，xmax表示有效的节点观测值最大值，xmin为有效的节点观测值最小值，节点i到n时刻为止的观测值集合以Xi(n)表示，即Xi(n)={xi(1),xi(2), …,xi(n)}。

本文假设指定区域内节点密度较高(如小型家居系统)，当一个事件发生时，多个临近事件发生地的节点都将及时地捕获到该事件。

定义1数据变化模式：节点i在t时刻的数据变化模式Δxi(t)与上一时刻的观测值相关，Δxi(t)=│xi(t)-xi(t-1)│，Δxi(t)∈D，其中D为区间[0,xmax-xmin]。不失一般性，本文将数据变化模式简称为模式。

ΔXi(n)表示节点i从2时刻到n时刻为止所有数据变化模式的集合，即:

ΔXi(n)={Δxi(2),Δxi(3), …, Δxi(n)}

其中│ΔXi(n)│=n-1。

定义2模式区间：D为区间[0,xmax-xmin]，将D均匀地划分为若干区间{d1,d2, …,dk}，称为模式区间，ΔXi(n)中任意的一个数据变化模式在D的某一个模式区间内。

定义3区间频繁度：在节点的数据变化模式集合ΔXi(n)= {Δxi(2),Δxi(3), …, Δxi(n)}中，属于模式区间dj的模式的个数记为V(j)，则称P(j)=V(j)/(n-1)为模式区间dj的频繁度。

2.2 相关知识

2.2.1数据异常

根据本地节点异常的原因对异常进行分类，有点异常、上下文异常与集体异常三类[12]。

(1)点异常：相对于数据集被认为是异常的单个数据实例。

(2)上下文异常：在当前上下文中被认为是异常的数据实例。在不同的上下文中，相同的数据实例可能被认为是正常的。

(3)集合异常：连续多个测量值为常数，即在一段时间内测量值几乎没有什么波动。

图1 异常类型

图1显示了Chandola等人定义的异常[12]。在时段24发生点异常，即数据实例对于整个数据集是异常的。在时段43出现上下文异常，但是如果该观测值出现在时刻t1，t2，t3或t4，则不会被认为是异常的。最后，集合异常发生在时间段54～71，节点由于故障在该时段内连续出现多个几乎没有什么波动的观测值。本文将上下文异常视为点异常的一种特例。

2.2.2WSN中数据空间相关性

在WSN中，数据实例之间经常存在相对位置关系，这样的数据称为空时数据(spatio temporal dam)。在进行异常检测时，常常利用数据的空间相关特性区分节点故障和事件。由于组成事件的感知数据之间具有较强的时空关联性，当事件发生时，临近节点将拥有相似的观测值，这是因为基于噪声测量与传感器故障可能随机无关，而事件测量可能在空间上相关的事实。这一观察使我们能够区分事件和错误。例如，对Intel室内项目[13]的数据进行空间相关性的分析。图2给出了两个邻近的节点(节点4，6)和一个非临近节点(节点24)的温度随时间变化的趋势图。可以明显地看出4,6节点彼此邻近，其同一时刻的观测值更加接近。在空间上彼此邻近的邻居节点的数据具有一定程度的相似性。

图2 节点温度变化趋势图

3 异常检测算法

数据的变化模式由节点上连续观测值的差值构成。本文异常检测方法的思想是将数据流的数据变化模式映射到某个特征空间的分区中，将非频繁出现的分区认为是异常分区，频繁出现的分区认为是正常分区。若某时刻数据的变化模式映射到特征空间的异常分区，则将该时刻的数据当做潜在异常值，并利用相邻节点数据的空间相关性对其进行验证。

该算法的目标是识别出潜在的异常观测值并将其分类。在判断异常观测值产生的原因时，目标节点收集其邻居节点集Si的当前时刻观测值，并利用数据的空间相关性进行判断，避免了将节点数据传输至Sink节点产生的大量能量消耗。PFSC方法是一个自学习-检测的过程，可分为两个阶段，即第一阶段为训练阶段，第二阶段为异常检测阶段。

3.1 数据变化模式

节点的数据流是按时间顺序排列的一系列数据的集合，也称为时间序列。在时间序列数据挖掘的研究中，通常用时间序列模式表示来描述原始的时间序列，即将原始时间序列映射到某个特征空间中，并用它在这个特征空间中的映像来描述原始序列。时间序列模式一定程度上保留了时间序列的主要特征，更能反应时间序列的变化情况。分段线性表示(PLR)是将时间序列表示成多段相邻的直线，用多段直线段拟合原时间序列，时间序列Xi(n)的PLR模型表示为：

Xi(n)={xi(1),xi(2),…,xi(n)}

L(Xi(n))={L(y1,y2),L(y2,y3),…,L(yk-1,yk)}

(1)

式中，yj∈Xi(n)，L(yj,y(j+1))表示连接两点的直线段。

在此基础上，本文将PLR中的线段长度压缩为1，分段数量设置为n-1，同时用│y(j+1)-yj│来描述分段L(yj,y(j+1))的特征，得到Xi(n)的数据变化模式：

H(Xi(n))={Δxi(2),Δxi(3),…,Δxi(n)}

(2)

数据变化模式一定程度上保留了时间序列在各个时刻的数据变化情况。通常在正常的工作环境下，节点的读数在连续的时间内是渐变的过程，而异常观测值与正常值存在明显的差异，并且在节点的工作过程中异常值出现的频率通常远低于正常数据。因此，若将数据变化模式映射到某个特征空间的分区中，数据流中正常数据的变化模式落在特征空间的高频率分区，而异常值的变化模式相对处于低频率分区。

3.2 训练阶段

训练阶段的思想是：在数据流中为数据变化模式集ΔXi(n)创建一个分布模型，即将数据变化模式映射到某个特征空间的分区中，确定非频繁出现的分区。

数据变化模式Δxi(t)=│xi(t)-xi(t-1)│，其取值范围为[0,xmax-xmin]，记为D。为了对数据流的模式创建一个分布模型，将每个采样周期产生的模式映射到特征空间中，模式的取值范围D= [0,xmax-xmin]被均匀地划分为若干个模式区间{d1,d2, …,dk}。模式区间数量根据领域知识进行估计。每一个模式区间对应D的一个小的取值范围。

训练阶段开始时，对每个采样周期的模式判断其在哪一个模式区间内，该模式区间dj出现的次数V(j)加1。图3给出了节点i在训练阶段的操作过程。

图3 节点i训练阶段图

图3中，节点i的训练阶段，在时刻4数据变化模式为Δxi(4)，判断其属于d2分区，V(2)加1。同理，节点进行下一个时刻数据变化模式Δxi(5)的映射，此时V(1)为2，该过程直至训练阶段结束。

在训练阶段结束时，对D中的模式区间统计其模式出现的次数，计算各个模式区间的频繁度。

(3)

频繁模式区间阈值为P，若P(j)

3.3 检测阶段

3.3.1异常识别

异常识别的任务是筛选出数据流中的潜在异常值。学习阶段结束后可以获取特种空间中非频繁模式区间。在异常识别过程中，将目标数据映射到特种空间的分区中，如果该时刻数据的模式落在非频繁模式区间，则将其当做潜在的异常值进行处理。映射过程与学习阶段相似。

3.3.2异常分类

为了确认是否真的出现了异常并对异常进行分类，本文利用WSN数据的空间相关性进行验证。当节点i产生一个潜在异常观测值xi(t)时，该节点利用无线信道向其邻节点Si= {s1,s2, …,sk}请求其t时刻的数据xj(t)，其中j∈Si。计算其邻居节点xj(t)的平均值μ和标准差σ。根据拉依达准则，若

|xi(t)-μ|<δσ

(4)

则认为该节点观测值与其邻居节点观测值状态相一致，该异常观测值是由事件引起的；若不满足式(4)，则认为该节点观测值与其邻居节点观测值状态不一致，该异常观测值是由节点软、硬件故障或者环境等其他因素引起的错误数据。

δ的取值根据实际应用确定。假设事件是一个Bernoulli过程，并且事件过程中，数据符合正态分布，将事件过程的数据化简为符合正态分布的随机变量：

=1-(Φ(δ)-Φ(-δ))

=2-2Φ(δ)

(5)

其中Φ(δ)为标准正态分布，当Φ(δ)>0.9时，p<0.1，查表可得当δ取大于1.29时，Φ(δ)>0.9。本文将在实验中对拉依达系数δ的取值进行讨论。

4 实验

本文在MATLAB环境下采用Inter室内实验室项目[13]数据集来分析算法的性能。所采用的数据集的数据格式如表1所示。

表1 Inter室内实验室项目数据格式

4.1 评估指标

异常值检测算法通常使用检测率(召回率)、查准率和误报率(虚警率)进行评估。为了定义这些度量，此处采用混淆矩阵，如表2所示。

表2 混淆矩阵

因此，检测率(Detection rate)、查准率(Precision rate)和误报率(False alarm rate)定义如下：

检测率：Dr=TP/(TP+FN)

(6)

查准率：Pr=TP/(TP+FP)

(7)

误报率：Fr=FP/(FP+TN)

(8)

4.2 算法性能

本文所提出的算法有两个参数对算法的性能具有影响，分别为D的分区频繁度阈值p和拉依达准则的系数δ。实验分两组进行，分别分析在设置不同的分区频繁度阈值p和设置不同拉依达法则系数δ的情况下，PFSC算法的性能。

图4展示了PFSC算法性能随分区频繁度阈值p变化趋势图。其中p增大时，PFSC算法的检测率增大，而查准率减小，误判率因查准率的减小而增大。这是因为当p取较大值时，算法在判断潜在异常数据时不仅识别出实际异常值，同时将部分变化模式较大的正常数据也识别为潜在异常数据，导致算法在检测率增大的同时查准率下降。当p取0.05时，PFSC算法检测率为83.903%，准确率为73.589%，误判率为1.581%，此时PFSC性能较好。

图4 频繁模式区间阈值实验图

图5展示了不同拉依达准则系数δ对PFSC算法性能的影响。δ在1.5前后PFSC的检测率呈现不同状态，当δ大于1.5时，检测率逐渐减小。图中可以明显看出，PFSC的准确率随δ增大而增大，同时误判率持续减小，这是因为拉依达准则系数δ控制错误数据的判定，δ越大说明异常数据越偏离其邻居节点数据，它为错误数据的可能性越大。其中δ取1.5时，PFSC的检测率为83.835%，准确率为74.093%，误判率为1.54%。

图5 拉依达准则系数δ实验图

从实验结果可以看出，PFSC算法在p取0.05，δ取1.5时性能最好。

为判定数据不同程度的异常率对算法性能的影响，本文将比较PFSC算法与文献[14]提出的基于小波的异常检测算法(Wavelet Based Outlier Detection,WBOC)和文献[15]提出的基于K最近邻的KNN异常检测算法在数据不同异常率下的性能。其中PFSC算法p取0.05，δ取1.5，WBOC误差阈值取2，KNN误差阈值取2。

实验效果如图6～图7所示。可以看出，当节点采集的数据异常率从5%增大到20%时，三种算法的检测率都呈下降趋势。当异常率较大时，在PFSC与KNN算法中，目标节点因邻居节点潜在的异常数据而影响本地异常值的判定，邻居节点集Si中的异常数据越多，算法检测率越低。其中PFSC算法的异常鉴定与KNN相似，其检测率接近于KNN算法。在数据异常率为12.5%时，PFSC的检测率为80.27%。

图6 数据异常率对检测率影响

图7 数据异常率对误报率影响

图7展示，当节点产生5%到20%不同程度异常率的数据时，PFSC算法的误判率维持在2.41%左右，相比于WBOC与KNN有更低的误判率。

5 结论

本文研究了无线传感器网络中的异常值检测问题。由于网络的特殊特性和资源限制，本文提出了一种基于数据变化模式频繁度与数据空间相关性的PFSC算法，并以在线和分布式的方式检测异常。实验表明，PFSC算法在检测不同异常率的数据流时有较高的检测率和较小的误判率。

[1] MA L,GU X D, WANG B W. Correction of outliers in temperature time series based on sliding window prediction in meteorological sensor network[J]. Information, 2017, 8(2):60.

[2] GANGULY A R, GAMA J, OMITAOMU O A, et al. Knowledge discovery from sensor data[M]. Springer Berlin Heidelberg, 2010.

[3] RASSAM M A, ZAINAL A, MAAROF M A. Advancements of data anomaly detection research in wireless sensor networks: a survey and open issues[J]. Sensors, 2013, 13(8): 10087-10122.

[4] ZHANG Y. Observing the unobservable: distributed online outlier detection in wireless sensor networks[D]. Enschede: University of Twente, 2010.

[5] LAU B C P, MA E W M, CHOW T W S. Probabilistic fault detector for wireless sensornetwork[J]. Expert Systems with Applications, 2014, 41(8): 3703-3711.

[6] SUBRAMANIAM S, PALPANAS T, PAPADOPOULOS D, et al. Online outlier detection in sensor data using non-parametric models[C]//Proceedings of the 32nd International Conference on Very Large Data Bases, 2006: 187-198.

[7] XU X, GENG W, YANG G, et al. LEDFD: A low energy consumption distributed fault detection algorithm for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2014, 10(2): 714530.

[8] BAHREPOUR M, MERATNIA N, POEL M, et al. Distributed event detection in wireless sensor networks for disaster management[C]//Intelligent Networking and Collaborative Systems (INCOS), 2010 2nd International Conference on. IEEE, 2010: 507-512.

[9] HILL D J, MINSKER B S. Anomaly detection in streaming environmental sensor data: A data-driven modeling approach[J]. Environmental Modelling & Software, 2010, 25(9): 1014-1022.

[10] FAWZY A, MIKHTAR H M O, HEGAZY O. Outliers detection and classification in wireless sensor networks[J]. Egyptian Informatics Journal, 2013, 14(2): 157-164.

[11] BRANCH J W,GIANNELLA C, SZYMANSKI B, et al. In-network outlier detection in wireless sensor networks[J]. Knowledge and Information Systems, 2013, 34(1): 23-54.

[12] O′REILLY C, GLUHAK A, IMRAN M A, et al. Anomaly detection in wireless sensor networks in a non-stationary environment[J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 1413-1432.

[13] Intel. IntelLab data[EB/OL].(2004-××-××).http://www.select.cs. cmu.edu/data/labapp3/index.html.

[14] ZHUANG Y Z, CHEN L. In-network outlier cleaning for data collection in sensor networks[C]// Int′l VLDB Workshop on Clean Databases, Cleandb 2006.

[15] XIE M, HU J K, HAN S, et al. Scalable hypergrid k-NN-based online anomaly detection in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(8): 1661-1670.