翟小超

(西安电子科技大学数学与应用数学，陕西西安 710071)

无线传感网络WSNs由大量微小、低消耗的传感器节点通过无线通信连接构成。许多网络被部署在无人监督的恶劣环境中。出于费用考虑，传感器节点通常是低成本、低质量的。传感器的低质量和恶劣的部署环境导致传感器采集到的数据中存在大量的误差、错误、丢失值、重复值和不一致数据。传感网络中数据本身的不可靠性使得难以将这些数据用于有意义的科学研究。异常值是导致网络数据不可靠的主要原因之一，所以无线传感网络中数据的异常值检测受到越来越广泛的重视。

异常值检测的研究源于数据挖掘领域。现存文献中存在大量的异常值检测方法，例如支持向量机，聚类方法，统计学方法，基于临近点的方法等［1］。在文献［2］中，作者给出了一种支持向量机的异常值检测方法。但这种方法需要每隔一段时间传感器采集到足够多的数据后才能对收集的数据进行检测，不是一种实时的线上检测方法。文献［3～4］构建了一个朴素贝叶斯分类器用于异常值检测。这种方法实现了线上实时的异常检测，且还可近似地预测网络中的丢失数据。然而，这种方法仅适用于一维数据;再次，这种方法事先需要一个训练集来学习分类器参数，大多数情况下一个好的训练集难以获得。文献［5］利用PCA技术识别出局部异常值。然而，PCA方法事先需要一个训练集来计算主元，且在选取合适主元时计算复杂度较高。文献［6］给出了一种新的椭圆异常定义。当数据集的形状是超椭球时，这种方法检测的准确率比较高，然而，当数据集是不规则的几何形状时，检测结果是不可信的。

在无线传感网络中，传感器节点按照固定的时间间隔不断地捕获数据，传感器捕获的每一个数据都带有一个唯一的时间戳。上述文献中除了文献［3～4］，均未考虑到传感器采集到的数据本身在时间上的连续性。鉴于此，本文从传感网络数据在时间上的相关性角度出发，提出了一种针对无线传感网络的可变阈值异常值检测方法，在无需事先获取训练集的前提下，实现了对传感器采集数据的线上实时的异常检测。

针对本文模型作如下假设:(1)网络中传感器采集数据的时间间隔不可过长，不超过5分钟。(2)网络中的数据符合马尔科夫假设不会发生突变。

1 数据异常因子

在众多异常值检测方法中存在着一种既直观又简单的方法——利用相邻点之间的距离来判断异常值。如果当前数据点距离上一时刻数据点的距离超过某一范围，就认为该点是一个异常点。

如图1所示，数据点1，2，3，4，5 均是正常数据点，显然数据点6是一个异常数据点。然而6，7之间的距离与6，5之间的距离基本一样，若依照相邻点间的距离来判断异常点，7也将被检测为异常，但观察图1会发现数据点7应该是正常的，这样数据点7则被误报。为避免上述误报，做如下定义。

图1 异常值示意图

定义1 (Normal Hop Distance)数据点obj(k)为传感器在t时刻捕获的数据，设t时刻之前捕获的数据之中已被检测为正常的，且在时间上距离obj(k)最近的数据点记为obj(i)，则当前数据点obj(k)的正常跳距离为

其中，式(1)中的距离dist(obj(k)，obj(i))表示数据点obj(k)到数据点obj(i)的马氏距离。

其中，∑ =cov(D)为数据集D的协方差矩阵。

在计算两个数据之间的距离时，通常采用的是欧氏距离，但欧氏距离在计算时，是将数据中的所有属性都等同对待的，而马氏距离在计算时，则会根据数据集自身的特点，调节各属性对最终结果的贡献率。对于一个二维数据，在欧氏距离下，数据点的δ邻域是一个圆，而在马氏距离下，数据点的δ邻域是一个椭圆。如图2所示，分别为数据集中同一个数据点，在马氏距离与欧氏距离下的δ邻域。可看出，在马氏距离下的δ邻域所画出的椭圆，其长轴方向正是数据集变化的主要方向，而短轴方向恰是数据集变化幅度最小的方向。即马氏距离能提取数据集的特征，并将其体现在数据的δ邻域上。因此，本文计算距离时均采用马氏距离。

图2 同一点在马氏距离下的δ邻域和在欧氏距离下的δ邻域

定义2 (Outlier Factor)设传感器在t时刻捕获的数据点为obj(k)，则当前数据点obj(k)的异常因子为

其中，δ(k)为当前数据obj(k)对应的动态阈值。

根据每个数据点异常因子的大小可将数据集D中的数据分为3种状态:

正常态:若数据点obj(k)的异常因子 OF(k)∈［0，1］;

临界态:若数据点obj(k)的异常因子 OF(k)∈(1，trustvalue］;

异常态:若数据点obj(k)的异常因子 OF(k)∈(trustvalue，+∞］。

其中，trustvalue是一个＞的参数。

在实际部署的网络中，传感器可能受到各种未知的影响，从自然界中捕获的实时数据常常会呈锯齿状上升或下降，即数据处于不确定的波动中。在这些波动中，有些数据的波动处于合理的范围;而有些波动则较严重，是由异常值导致的。有鉴于此，本文在正常态与异常态之间引入临界态，并通过参数trustvalue来控制临界态的大小。参数trustvalue的值越小检测越严格，参数trustvalue的值越大检测越宽松。在现实使用中，可根据网络部署环境和实际检测的需要来调节参数trustvalue。

本文借用无罪推定的法律原则，即任何人在被宣判有罪之前都推定为无罪，只有那些处于异常态的数据才被认为是异常值。

2 检测方法

在定义1和2的基础上，给出本文的检测策略和动态阈值δ(k)的更新方法。

对于t时刻采集到的数据obj(k)，在已知对应的阈值δ(k)的情况下可得到异常因子OF(k)，并通过异常因子来判断当前数据所处的状态。若obj(k)处于异常态则认为其是一个异常值，否则认为其是一个正常值。然后，利用前一时刻数据obj(k－1)所处的状态和当前数据所处的状态，以及当前的阈值δ(k－1)，确定下一时刻的阈值。依照上述策略，即可实现对传感器采集数据的线上实时的检测。其具体实现包括如下步骤:

步骤1 部署传感网络，开始采集数据;

步骤2 传感器采集到初始m个数据后，计算δ(m);

步骤3 根据设定的动态阈值更新更新机制得到δ(m+1);

步骤4 传感器捕获到第i个数据obj(i)，计算OF(i)，然后判断第i个数据所处的状态，如果第i个数据处于异常态，判定obj(i)是一个异常值;

步骤5 根据设定的更新机制，利用obj(i－1)的状态，obj(i)的状态以及当前的δ(i)，得到下一时刻的阈值δ(i+1);

步骤6 重复步骤4和步骤5直到传感器停止采集数据。

其中，步骤2中假设传感器节点采集到的前m个数据都是正常的，δ(m)可取为

经典马尔科夫假设认为，下一时刻的状态仅与当前时刻状态有关，而与以前状态无关。但将其应用于本模型时仿真效果并不好。这里假设下一时刻的状态仅与当前时刻的状态和前一时刻的状态有关，而与前一时刻之前的状态无关。分析传感网络中数据集的特征，同时进行大量的仿真实验，制定了如图3所示的阈值更新机制。

图3 动态阈值更新机制

假设当前数据为obj(i)，已知前一个数据的状态，当前数据状态和当前阈值，按照图3所示的更新规律，给出如下的更新方法:(1)数据obj(i－1)处于正常态，数据obj(i)处于临界态，新阈值δ(i+1)在阈值δ(i)的基础上适度增大。(2)数据obj(i－1)处于正常态，数据obj(i)处于异常态，新阈值保持不变。(3)数据obj(i－1)处于临界态，数据obj(i)处于异常态，新阈值δ(i+1)在阈值δ(i)的基础上适度增大。(4)数据obj(i－1)处于临界态，数据obj(i)处于正常态，新阈值维持不变。(5)数据obj(i－1)处于异常态，数据obj(i)处于临界态，新阈值维持不变。(6)数据obj(i－1)处于异常态，数据obj(i)处于正常态，新阈值δ(i+1)在阈值δ(i)的基础上减小。(7)数据obj(i－1)处于正常态，数据obj(i)处于正常态，新阈值δ(i+1)在阈值δ(i)的基础上适度减小。(8)数据obj(i－1)处于异常态，数据obj(i)处于异常态，新阈值 δ(i+1)在阈值δ(i)的基础上增大。(9)数据obj(i－1)处于临界态，数据obj(i)处于临界态，新阈值δ(i+1)应等于当前NHD(i)。

相比现有技术，本文模型具有如下优点:(1)在无需训练集的条件下，实现了对传感器数据的线上实时的检测。(2)可通过调节参数trustvalue来调节检测的松紧度，以适应各种不同环境下的检测要求。(3)在检测数据过程中，无需额外的数据通信，故适用于多种拓扑的无线传感器网络，包括在动态的网络。

3 仿真实验

仿真实验是在一台4 GB内存，赛扬双核2.6 GHz，32位Win7操作系统下，使用Matlab 2010b进行的。在仿真实验中，取m=5，即假设传感器初始采集到的前5个数据均是正常的。采用人工生成的数据集D来检测本文算法。数据集D如图4所示，共包含400条数据。首先，对数据集添加一定数目的随机噪声点后得到带有噪声的数据集，然后对新数据集使用本文的算法进行检测，以此来检验算法的性能。

图4 生成数据D集示意图

图5 阈值动态变化示意图

生成的数据集D由中心相同短轴相同长轴不同的2个椭圆构成，数据从文中图4红星处开始也在此处结束，正好形成2个完整的椭圆。生成数据集中相邻点之间的距离变化趋势分8个阶段:(1)始逐渐减小。(2)逐渐增大。(3)逐渐减小。(4)逐渐增大。(5)逐渐减小。(6)逐渐增大。(7)逐渐减小。(8)逐渐增大。这一趋势恰与上图中阈值动态变化总体趋势吻合。而图5中跃出点恰好是仿真时加入的随机噪声点。

图6 数据集D添加100个噪声后检测结果

为数据集D加入100个随机噪声后，新数据集包含300个正常数据点和100个噪声点，噪声在数据集中所占比例为25%。图6为参数trustvalue=3.0时的检测结果，其中圆圈表示加入的噪声点，星形表示数据集中被检测为异常的数据点，蓝点表示数据集中被检测为正常的数据点。因此，外红圈内红星表示该点是噪声点且被检测为异常点，即该噪声点被正确检出，外红圈内蓝点表示该点是正常点但被检测为异常点，即该点被误报，只有红星的点表示噪声点被检测为正常点，即该点被漏报，只有蓝点表示非噪声点被检测为正常点，即正常点被检测为正常点。观察图5可知，检测出101个异常点，噪声全被检出，有一个正常数据点被误报。

表1 仿真实验结果汇总表

将仿真实验结果汇总结果如表1所示。对于数据集D，在噪声比不超过50%的情况下，本文算法检出率均保持在95%以上，且误报率维持在2%以下，说明本文的检测方法在绝大多数情况下能快速有效地检测出网络中的异常值。

4 结束语

本文从时间上相邻数据点的间距这一直观角度出发，构建新的异常值检测模型。首先，定义了新的异常因子，并以此将数据分为正常、异常、临界3种状态。然后，利用异常因子构建了一个基于动态阈值的异常值检测模型，并给出了动态阈值的更新方法。本文的检测方法在无需训练集的条件下，实现了线上实时的异常值检测。仿真实验表明，算法在数据集中噪声比不超过50%的情况下检出率保持在95%以上，同时误报率维持在2%以下。本方法在实际应用中还存在如下问题:(1)参数trustvalue的取值问题。(2)传感网络中异常值检测大多都是针对网络的时间相关性和空间相关性建模，本文模型中并未利用到相邻传感器数据之间的相关性，若在模型中引入相邻传感器数据之间的相关性，是否能进一步提高算法的检测精度。(3)如何在现有检测的方法的基础上，实现对临界态数据的再判定，以减少临界态数据的漏检。

［1］Zhang Y，Meratnia N，Havinga P JM.Outlier detection techniques for wireless sensor network:a survey［J］.IEEE Communications Surveys＆ Tutorials，2010(12):159 －170.

［2］Rajasegarar S，Leckie C，Palaniswami M，et al.Quarter sphere based distributed anomaly detection in wireless sensor networks［C］.IEEE International Conference on Communications，2007.

［3］Elnahrawy E，Nath B.Context－ aware sensors［J］.EWSN，2004，29(20):7 －93.

［4］Janakiram D，Adi Mallikarjuna Reddy V，Phani Kumar A V U.Outlier detection in wireless sensor networks using bayesian belief networks［C］.Delhi，India:In Proceedings of the First International Conference on Communication System Software and Middleware(COMSWARE)，2006(1):1 －6.

［5］Chatzigiannakis V，Papavassiliou S，Grammatikou M，et al.Hierarchical anomaly detection in distributed large－scale sensor networks［C］.11th IEEE Symposium on Computers and Communications，2006:761 －767.

［6］Rajasegarar S，Bezdek J C，Leckie C，et al.Elliptical anomalies in wireless sensor networks［J］.ACM Transactions on Network，2010(6):1 －28.

［7］Miao X，Jiankun H，Song H，et al.Scalable hyper－ grid k －NN－based online anomaly detection in wireless sensor networks［J］.IEEE Transactions on Parallel Distribut System，2013(24):1661－1670.

［8］Moshtaghi M，Bezdek JC，Havens T C，et al.Streaming analysis in wireless sensor networks［J］.Wireless Communication Mobile Computer，2012(6):763 －771.

［9］Burbeck K，Nadjm －Tehrani S.Adaptive real－ time anomaly detection with incremental clustering［R］.Informations Secures Technology Report，2007(12):56 －67.

［10］Moshtaghi M，Leckie C，Karunasekera S，et al.Incremental elliptical boundary estimation for anomaly detection in wireless sensor networks［C］.Vancouver，BC，Canada:In Proceedings of the 11th IEEE International Conference on Data Mining(ICDM)，2011(12):467 －476.

［11］Hill D，Minsker B，Amir E.Real－time bayesian anomaly detection for environmental sensor data［C］.Venice，Italy:In Proceedings of the Congress－International Association for Hydraulic Research(IAHR)，2007.