无线传感器网络分布式离群数据检测研究*

唐 琪，刘学军

(南京工业大学电子与信息工程学院，南京211816)

在无线传感器网络中，偏离正常模式的感知数据被认为是离群数据。离群数据［1］的可能来源包括网络中的噪声、异常事件、恶意攻击等等。在某些重要的传感器网络应用中，如火灾监测、环境和栖息地检测［2］、欺诈和入侵检测［3］、目标追踪、战场观测等，这些离群数据通常起着十分重要的作用。基于无线传感器网络的离群数据检测技术也越来越受到人们的关注。离群数据检测的算法有基于统计的、基于偏差的、基于聚类的、基于距离［4］的、基于密度［5－6］的等等。基于密度的离群数据检测算法可以发现任意形状的数据布局中的离群数据，它是根据读数的所有维度计算读数之间的距离，再通过局部离群因子来判定离群数据的存在与否，离群因子愈大，数据就更可能离群，反之则可能性愈小。无线传感器网络的离群点检测分为集中式方法和分布式方法。集中式方法是将每个传感器感知的数据直接传送给Sink节点，Sink节点采用一定的算法对全部数据进行离群点检测，该方法由于需要传输大量的数据，加快了能量的消耗。分布式方法是每个传感器节点对感知数据进行本地检测，做出本地判决，只把这种本地结论及其相关信息向Sink节点传送，然后由Sink节点在更高层次上综合多方面的数据进一步完成处理，获得最终的判决结论，这种方法相对集中式方法节省了能量的消耗，提高了网络的生存周期，从而延长了网络的寿命。

本文提出了一种基于密度的分布式离群数据检测算法，并通过引入时空关联性有效提高了检测精度。为了更精确地检测到离群数据，在传感器节点采集到的数据中，不同的属性赋予了不同的权重。本文后续内容如下:第2节介绍了相关的研究工作;第3节提出了一种无线传感器网络分布式的离群数据检测算法;第4节通过实验分析了分布式离群数据检测算法的性能;第5节总结了全文。

1 相关研究

离群点又名孤立点，偏差点，异常点等，是数据集中偏离大部分数据的数据，并怀疑这些数据的异常产生于不同的机制而不是产生于随机因素。研究人员最开始提出了基于统计的离群点检测算法，后来陆陆续续地提出了各种各样的离群点检测方法。Zhang Yang等人对传感器网络的离群点检测技术进行了综述，详细地分析了传感器网络中离群点检测的意义、应用领域以及相关算法等。SHENG Bo［7］利用直方图提取分布特征，不需要传输网络中的全部数据，降低了通信开销，但该算法仅对一维数据适合，不适合多维数据。姜旭宝［8］等人提出了基于变宽的直方图的异常数据检测算法，通过数据聚合的方式将网络中的动态感知数据聚合成变宽的直方图来检测出异常数据，避免不必要的数据传输，也有效降低了通信开销。V.S.Kumar Samparthi［9］等人提出了基于核密度估计的分布式多维数据离群点检测算法。张天佑等人提出的SLDF算法，适用于高维大数据集［10－11］的空间离群点检测，但是，它只考虑了空间数据集的问题。

以上这些方法都只是从时间或空间的单一角度进行离群点检测的研究，而本文在基于分簇的无线传感器网络环境中，综合考虑了时间和空间的相关性以及属性权重等方面，提出了基于密度的时空关联的分布式离群数据检测算法TSLOF(Time and Space Local Outlier Factors)。

2 时空关联分布式离群数据检测算法

2.1 网络结构

2.1.1 簇的划分

为实现无线传感器网络分布式离群数据检测，本文采用的是LEACH协议［12］，它是一种典型的分簇路由协议，定义了“轮”的概念，每一轮有簇头的形成和数据传输两个阶段。簇头的形成阶段:每一个传感器节点从0到1随机选取一个数，若小于这轮设定的门限值T(m)，则选为簇头。T(m)的计算公式如下:

其中，p是节点成为簇头的百分比，r是当前的轮数，G是在最后的rmod(1/p)轮中还没有担当簇头的节点集合。

数据传输阶段，传感器节点连续采集数据，传给簇头，然后簇头在进行必要的数据聚集和融合之后，发送到Sink节点。此阶段持续一段时间后，进入下一轮，不断地循环。分簇的无线传感器网络结构如图1所示。

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

2.1.2 网络模型

2.2 数据预处理

本文主要对传感器节点采集的数据进行两个方面的数据预处理。一方面是基准化。由于环境影响着传感器节点采集的数据，有时，不同的节点采集的正常数据可能有较大的差异，在计算空间局部离群因子时，容易把某些差异较大的正常数据误判为异常数据。为避免这种情况的发生，可以给每个传感器的读数指定一个基准值，传感器节点采集的数据除以该基准值，就得到了它的计算值，这一过程被称为基准化。离群点的计算是采用计算值进行的。每个传感器节点都有独立的基准值，通常取该节点正常读数的平均值。通过基准化，可以降低将差异较大的正常数据误判为异常数据的可能性，从而提高离群数据检测的准确度。计算值的公式为:

另一方面是归一化，即将有量纲的数据化为无量纲的数据，数值归一到0和1之间。在某些传感器网络的应用中，节点接收到的数据是多维的，不同的属性之间取值差异可能较大，在计算距离时，对各维的读数进行归一化，可以消除取值范围不同、计量单位不同对结果带来的不利影响。

2.3 基于时空关联的分布式离群数据检测算法

算法分为三个阶段:第一阶段为簇成员节点利用滑动窗口机制检测时间离群数据并发给簇头节点;第二阶段为簇头节点检测簇成员节点之间的时空离群数据并发给Sink节点;第三阶段为Sink节点检测各个簇头节点传送来的离群数据并得到所期望的离群数据。

2.3.1 算法基本概念

采用滑动窗口机制［14］，假设一个窗口宽度为B，每隔Δ时间传感器接收一个读数，且是在正常情况下，一个窗口B的读数数量为a个，即B=Δa。

定义1 数据对象Xi相对于数据对象Xp的加权距离:

其中ωl表示数据对象属性l的权重，xil表示数据对象Xi在属性l上的值，xpl表示数据对象Xp在属性l上的值。

定义2 数据对象Xi的第k距离:

该定义通过研究每一个对象与被研究对象之间的距离并找出其数值上为第k大的距离，来确定一个针对被研究对象的个性化的局部空间区域的范围，对于被研究对象密度较大的区域，该数值一般情况下较小;对于被研究对象密度较小的区域，该数值一般情况下则较大。对象Xi满足:至少有与k个对象 Xq的加权距离满足 dist(Xi，Xq，ω)≤dist(Xi，Xj，ω);最多有k－1个对象Xq的加权距离满足dist(Xi，Xq，ω)＜dist(Xi，Xj，ω)。

定义3 数据对象Xi的第k距离邻域:所有到数据对象Xi的加权距离小于或等于数据对象Xi的第k距离的数据对象的集合。记作:Nb(Xi)。该定义是以被研究对象为圆心，该数据对象的第k距离为半径的区域内的所有数据对象的集合。

定义4 k是一个给定的自然数，对象Xi对于对象Xj的可达距离:

当对象Xi远离对象Xj时，对象Xi关于对象Xj的可达距离就是它们之间的距离 dist(Xi，Xj，ω)，即dist(Xi，Xj，ω)＞k－distance(Xj)。当对象 Xi靠近对象Xj时，对象Xi关于对象Xj的可达距离就是对象Xj的k距离。

定义5 对象Xi的可达密度:

其中，Nb(Xi)为对象Xi的第k距离邻域。该定义首先计算数据对象Xi的第k邻域内的所有数据对象到数据对象Xi的所有距离之和，再计算其所有距离之和的平均值。可达密度使用了对象Xi的k近邻的平均可达距离的倒数来度量密度对象Xi，反映了Xi附近的数据分布情况。显然，当对象Xi的周围分布稀疏时，其局部可达密度会相应比较小。

定义6 局部离群因子:

2.3.2 算法描述

(1)算法步骤详述

第1阶段，簇成员节点检测时间离群数据:每个簇内的簇成员节点之间不进行互相通信，每个簇成员节点在一个窗口B中计算得到n'个时间局部离群因子TLOF(Xi)值最大的读数，值TLOF(Xi)根据定义6求得。簇成员节点将检测到的时间离群数据传送给簇头节点。

第2阶段:簇头节点接收簇成员节点的时间离群数据，并计算这些数据的空间局部离群因子SLOF(Xi)，值SLOF(Xi)也是根据定义6求得。将时间局部离群因子和空间局部离群因子结合起来称为时空局部离群因子TSLOF，如式(8)所示。通过降序排序，将每个簇的n个TSLOF值最大的候选离群数据传送给Sink节点。

其中ρ∈［0，1］，决定了时间局部离群因子和空间局部离群因子的比例，ρ越大，时间局部离群因子所占的比例越大，ρ越小，空间局部离群因子所占比例越大。

第3阶段:Sink节点接收到的n×M个离群数据，通过空间局部离群因子SLOF求得top－n个离群数据。

上述描述中的n'和n由用户指定。

(2)算法伪代码

3 算法实验分析

在200 m×200 m的区域内随机部署200个传感器节点和一个基站Sink。分为两种情况，一种是不分簇的网络，另一种是5%的传感器成为簇头的网络，都是单跳通信。设节点初始能量为0.5 J，发送和接收能耗均为0.395 nJ/bit，空闲能耗为0.039 nJ/bit，放大电路功耗 100 pJ/(bit·m2)，通信距离为50 m，仿真时间为1 000 s，数据分组大小为512 byte，MAC 层协议为 IEEE 802.11，ρ＜0.5，传感器节点采集的数据维度d=2，以温度、湿度为属性数据。温度的权值高于湿度的权值。

3.1.1 网络能量消耗

以30 s为一个时间窗口，设节点采集异常读数的速度为4个/s，在一个时间窗口内，传感器节点采集的异常读数总数为120个。图2给出了无线传感器网络时空关联的集中式和分布式离群数据检测的能耗比较。时空关联的集中式离群数据检测是指在没有分簇的无线传感器网络中时空关联的离群数据检测。从图中可以看出，集中式离群数据检测的无线传感器网络比时空关联的分布式离群检测无线传感器网络的能量消耗要快些，这是因为集中式离群数据检测将大量数据的直接传输给Sink节点，而分布式离群数据检测会将一部分数据传输给簇头节点，再由簇头将一小部分数据传输给Sink节点，因此，集中式离群数据检测能量消耗过快。

图2 分布式与集中式能耗对比

3.1.2 精确度比较

以30 s为一个时间窗口，传感器节点采集到的异常读数的速度分别为 1个/s，2个/s，4个/s，6个/s，8个/s，即在一个窗口内，传感器节点采集的异常读数总数分别为30个、60个、120个、180个、240个，对这5组数据集进行离群数据检测，离群数据检测的精确度采用式(9)的方法:

(1)时空关联的分布式检测算法与集中式检测算法检测精度对比

从图3可知，当传感器节点采集数据较少时，集中式离群数据检测精度与分布式离群数据检测精度相同;当传感器节点采集数据较多时，集中式离群数据检测精确度也只略好于分布式离群数据检测精确度，分布式离群数据检测保持了较高的检测精度。主要原因是集中式离群数据检测是在传感器节点检测离群数据之后，将所有时间离群数据直接传送给Sink节点，而分布式离群数据检测是经过簇头的筛选之后再传送给Sink节点，有可能会漏掉某些离群数据。

图3 分布式算法与集中式算法精确度比较

(2)时空关联的分布式检测算法与只考虑空间的分布式检测算法检测精度对比

图4显示了时空关联的分布式离群数据检测算法(也称为TSLOF算法)与只考虑空间的分布式离群数据检测算法(也称为SLOF算法)的检测精度比较。由于TSLOF算法既考虑了传感器节点的时间因素也考虑了空间因素，而SLOF算法只考虑了空间因素，忽略了传感器节点的时间因素，因此前者检测精确度高于后者检测精确度。

图4 TSLOF算法与SLOF算法精确度对比

3.1.3 TSLOF算法与OTOD算法性能比较

由于本文所提出的TSLOF算法与薛安荣等人提出的OTOD算法［15］都是无线传感器网络中考虑时空关联性的异常数据检测算法，两者比较类似。因此实验将两种算法进行性能比较。

图5显示了TSLOF算法和OTOD算法的能量消耗比较。从图5可以看出，TSLOF能耗明显低于OTOD算法。主要原因是:OTOD算法中，各节点需要将其潜在的离群数据通过多跳传送到Sink节点，因此，需要传输大量的数据，而TSLOF算法中，各簇成员节点将其时间离群数据传送给它的簇头，簇头对数据进行处理、融合，再将少量时空离群数据传给Sink节点。显然，TSLOF算法的能耗明显低于OTOD算法。

图5 TSLOF算法与OTOD算法能耗对比

我们也对TSLOF算法和OTOD算法的检测精度进行了比较。从图6可以看出，两种算法的检测精度比较接近。但是，OTOD算法是通过与相邻节点的比较来判定一个节点的数据是否为异常数据，当该节点的相邻节点都为全局离群数据时，可能会将该节点的离群数据误判为正常数据，在这种情况下，OTOD算法的检测精度会大大下降。本文提出的TSLOF算法由于时空离群点的判定是在簇头节点实现的，可以避免上述问题。

图6 TSLOF算法与OTOD算法精确度对比

4 总结与展望

本文提出的无线传感器网络时空关联的分布式离群数据检测算法，与集中式离群数据检测算法相比节省了能量消耗，同时也保持了较高的检测精度，时空关联的分布式离群数据检测精确度高于只考虑空间因素的分布式离群数据检测精确度，并且通过实验验证了这几点。在实际应用中，可以通过调整ρ的大小来确定时间和空间因素所占比重的大小。接下来的工作是将我们提出的算法与实际应用相结合，并考虑簇之间的权重问题，使离群数据检测算法的准确率得到更有效的提高。

［1］ Zhang Yang，Nirvana Meratnia，Paul Havinga.Outlier Detection Techniques for Wireless Sensor Networks:A Survey［J］.IEEE Communications Surveys ＆ Tutorials，2010，12(2):1－12.

［2］ Annie H Liu，Julian J Bunn，K Mani Chandy.Sensor Networks for the Detection and Tracking of Radiation and Other Threats in Cities［C］//The 10th International Conference on Information Processing in Sensor Networks.Chicago:IPSN，2011:1－12.

［3］ 周贤伟，王培，覃伯平，等.一种无线传感器网络异常检测技术研究［J］.传感技术学报，2007，20(8):1870－1874.

［4］ Vu N H，Gopalkrishnan V.Efficient Pruning Schemes for Distance-Based Outlier Detection［C］//Proc.of the European Conference on Machine Learning and Knowledge Discovery in Databases.2009:160－175.

［5］ 薛安荣，鞠时光，何伟华，等.局部离群点挖掘算法研究［J］.计算机学报，2007，30(8):1455－1463.

［6］ 张卫旭，尉宇.基于密度的局部离群点检测算法［J］.计算机与数字工程，2010，38(10):11－14.

［7］ Sheng Bo，Li Qun，Mao Wei-zhen.Outlier Detection in Sensor Networks［C］//Proc of the 8th ACM International Symposium on Mobile Ad hoc Networking and Computing.New York:ACM Press，2007:219－228.

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

［9］ Kumar Samparthi V S，Harsh K Verma.Outlier Detection of Data in Wireless Sensor Networks Using Kernel Density Estimation［J］.International Journal of Computer Applications，2010，5(7):26－32.

［10］ Subramaniam S，Palpanas T，Papadopoulos D.Online Outlier Detection in Sensor Data Using Non-Paramemer Model［C］//Prnc of the 32th International Conference on Very Large Data Bases，2006:187－198.

［11］ Angiulli F，Pizzuti C.Outlier Mining in Large Highdimensional Data Sets［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17(2):203－215.

［12］陈雪娇，李向阳.WSN中LEACH协议的研究与改进［J］.计算机应用，2009，29(12):3241－3243.

［13］孙雨耕，周寅，边桂年，等.无线传感器网络中一种能量有效的分簇组网算法［J］.传感技术学报，2007，20(2):377－381.

［14］杜威，邹先霞.基于数据流的滑动窗口机制的研究［J］.计算机工程与设计，2005，26(11):2922－2924.

［15］薛安荣，李明.无线传感器网络中异常读数检测算法研究［J］.计算机应用研究，2010，27(9):3452－3455.