一种基于分层聚合的分布式异常数据检测方案

许春杰,吴 蒙,杨立君

(南京邮电大学 a.计算机学院; b.通信与信息工程学院; c.物联网学院,南京 210023)

0 概述

无线传感器网络(Wireless Sensor Network,WSN)是一种由许多传感器设备组成的自组织网络,其中传感器节点以无线信道为媒介,通过多跳方式彼此连接。传感器收集环境信息并将感知数据传送回中央管理节点(即网关节点),以便进一步处理。目前,无线传感器网络已经在环境监测、军事、救援、医疗保健等诸多领域得到广泛的应用[1]。

传感器节点是一种微型嵌入式设备,在环境监测、智能交通等系统中起到关键性作用。但是在实际应用中,传感器节点在功率、带宽和计算能力方面存在不足[2-4],这些固有局限性可能使网络更容易发生故障或遭受恶意程序的攻击[5-6]。数据中的异常或异常值通常被定义为与数据集其余部分不一致的表现行为[7],可以通过分析网络中的传感器感知数据或与流量有关的属性来识别网络中的不正当行为。

传感器网络中绝大部分能量消耗来自于节点间彼此的通信而非计算[8],例如在Sensoria传感器中,通信和计算能耗之间的比值约为103～104。因此,异常数据检测的关键是将计算过程分布到各个子级节点,最大限度地减少网络中的通信需求。集中式异常检测方法需要将大量的原始感知数据或者预处理数据传送到指定的节点进行集中式处理,这将消耗传感器网络中的能量,从而减少网络的寿命。针对该问题,本文提出一种基于分层聚合的分布式异常数据检测方案,以期在保证检测率的同时降低通信消耗。

1 相关工作

目前国内外已有的传感器网络异常检测技术大致可分为基于密度的方法[9]、基于子空间[10]与相关性[11-13]的高维数据的孤立点检测、支持向量机[14]、复制神经网络[15]、基于聚类分析的孤立点检测[16]以及与关联规则和频繁项集的偏差。

根据可用数据背景知识的类型,异常检测机制又可分为3类方法[6]。第1类方法不需要先验知识就能发现异常值,该方法一般使用聚类或者无监督学习方法。第2类是监督式异常检测,此方法需要一个所含数据已经被明确标记为正常值或者异常值的数据集。通过监督训练,训练有素的分类器能够获得将新数据分类为正常或异常的能力。第3类方法是半监督异常检测方法。

数据聚类[17]是找到相似数据点簇的过程,聚类的结果能够使得每组数据点被较好的分离。基于数据聚类的异常检测基本是先将数据聚类,然后使用簇执行异常检测。

为了检测无线传感器网络中的路由攻击,文献[18]提出一种基于聚类的方案。在该方案中,每个传感器节点监视其接收到的路由消息,每个特征向量可由多维特征空间中的一个特征点表示,攻击流量在特征空间中会表现出异常。

文献[19]设计一种名为LogCluster的基于聚类的异常检测方案来识别在线系统问题。LogCluster方案由知识库初始化阶段和在线学习阶段2个阶段构成。知识库初始化阶段包含日志矢量化、日志聚类和代表性矢量提取3个步骤。在线学习阶段可以用来调整在知识库初始化阶段构建的簇。

文献[20]提出一种基于K-Means的无线传感器网络异常数据检测方案,以欧式距离作为衡量数据间相似度的指标对感知数据进行聚类划分,从而确定异常数据点。但是该方案将所有的计算消耗集中到网关节点中,网关节点能量消耗较大。

文献[21-23]针对传感器网络提出一种基于多层聚合的分布式异常数据检测技术,并构建一个具有分层拓扑的无线传感器网络模型。聚类算法采用最简单的基于宽度的聚类,传感器节点将簇的摘要合并信息发送到其各自的父节点,大幅缩减用于数据传递的能量消耗。但是该方案同样存在参数难以确定的问题,而且随着迭代的进行,会产生累计误差。

本文提出一种基于分层聚合无线传感器网络的分布式异常数据检测方案,基于K-Means++的数据聚类算法和K近邻异常检测方案对异常簇进行协作检验。该方案在节点级别识别异常数据向量,在网络中只传播能够代表当前节点信息的摘要信息,执行簇合并算法以减少网络通信开销,同时由网关节点执行异常簇的检测,将异常簇信息传递至各节点进行异常数据点检测。

2 基本模型

2.1 集中式方案

检测全局异常的最简单方法是使用集中式方案。在集中式方案中,在时间窗口的最后,每个传感器节点sj将其所有的感知数据发送给网关节点sg∈S。网关节点sg将其自身的数据Xg与收到的数据XR合并得到汇总数据X=XR∪Xg。集中式方案的聚类算法运行在数据集X上,得到一个簇的集合C={Cr:r=1,2,…,Nc}。基于固定宽度的聚类算法是一种较为简单且常用的算法,欧式距离作为衡量数据向量间相似性的指标。在得到簇的集合后,在这些簇的集合数据中使用异常检测算法即可识别出异常簇群。

由于集中式方案包括较高的通信费用和中心节点的处理时延等缺点,因此本文提出一种分布式异常检测算法,通过将数据摘要逐层合并进行传递,极大地减少了信息传递所消耗的通信能量。

2.2 分布式方案

由于无线数据通信会使系统产生较大的开销,对依靠电池供电的传感器生命周期产生较重负担,因此传感器节点在转发数据之前必须先对数据进行本地处理,以压缩冗余,提高系统效率。图1为分布式方案数据传输示意图。

图1 WSN中分布式异常检测示意图

2.2.1 数据预处理

2.2.2 基于K-Means++的聚类算法

算法1K-Means++聚类算法Cluster(Dataset,K)

输入标准化的感知向量Dataset,聚类数K

输出每个节点的簇的摘要Digest以及簇集C={Cr:r=1,2,…,Nc}

1.m,n = Dataset的行、列维数

2.centers[0]←Dataset中随机向量

3.for i=1 to k do

4.sum_all = 0

5.for j=1 to m do

6.d[j]← 到聚类中心的最短距离

7.sum_all+=d[j]

8.sum_all*=w,w∈[0,1]

9.for j,di in enumerate(d) do

10.sum_all-=di

11.if sum_all>0 do

12.continue

13.endif

14.centers[i]=Dataset[j]

15.break

16.endfor

17.endfor

18.endfor

19.change=True

20.while change==True do

21.change=False,minIndex=-1

22.for i = 1 to m do

23.计算到各个聚类中心的最短距离

24.if subcenter[i,0]!=minIndex

25.change=True

26.endif

27.endfor

29.输出簇的摘要Digest,簇集C={Cr:r=1,2,…,Nc}

2.2.3 簇群合并算法

步骤2若dis(c1,c2)≥w,不执行合并操作,将簇摘要信息继续向上传递,得到簇中心点相互之间的距离构成的矩阵,将矩阵中元素与w比较,如果dis(c1,c2)

步骤3将得到的簇摘要信息继续逐层上传直至网关节点,中间由父节点执行簇合并算法,网关节点执行2.2.4节中的异常簇检测算法,计算距离当前聚类中心较近的k个簇中心的加权距离平均值,与特定阈值进行比较,找到异常的簇。

算法2簇群合并算法MergeCluster(Cm)

输入簇群C={Cr:r=1,2,…,Nc},合并阈值w

输出合并后的簇集Cm

1.Cm←C

2.l=|Cm|

3.Cu←Ø(空集)

4.for r = 1 to Ncdo

5.if cr未发生合并 then

6.flag = false

7.for j=r+1 to Ncdo

8.if cjis not merged then

9.calculate Euclid(cr,cj)

10.if Dr≤w then

11.numv=numr+numj

13.calculate Dmax_v,

14.create cluster cv

15.Cu.append(cv)

16.Mark cr,cjas merged

17.flag = true

18.break

19.endif

20.endif

21.endfor

22.if flag==False then

23.Cu.append(cr)

24.endif

25.endif

26.endfor

27. if l>|Cu| then

28.MergeCluster(Cu)

29.endif

2.2.4 异常簇检测算法

定义簇ci与其他簇的亲近度为:

其中,k取0.3|C|,j为离i最近的k个簇中心标号。

将异常簇定义为:

Ca={Cβ∈C|Corrβ>AVG(Corr)+φ×SD(Corr)},φ的不同取值对应不同的置信度[22],本文取φ=1。

图2 分布式方案全局异常数据检测示意图

2.3 复杂度和能耗分析

2.3.1 集中式方案

假设每个传感器节点的感知数据个数相同,集中式方法在单个节点处需要O(np)的内存存储感知数据,网关节点处需要O(snp)的内存空间。其中,s是网络中的传感器节点数量,p是感知数据维度,n是单个节点的感知数据数量。由于在集中式方案中,底层节点不参与计算,因此只有网关节点会产生计算开销,在基于宽度的聚类算法中,算法的时间复杂度为O(snNc),异常簇检测的时间复杂度为O(Nc2),故总体时间复杂度O(snNc+Nc2),其中,Nc

由于传感器网中的能量消耗主要用于通信,因此此处只关注通信消耗,每个链路的通信复杂度是O(np)。

2.3.2 分布式方案

每个传感器节点执行聚类算法,K-Means++聚类算法的时间复杂度为O(nkt),其中,k

每个节点需要上传摘要信息,网关节点发现全局异常簇之后,将正常簇的摘要信息发送回节点。因此,每个链路的通信复杂度为O((k+1)(p+2))。

集中式与分布式异常检测算法的时空复杂度以及通信费用消耗对比如表1所示。

表1 分布式与集中式方案复杂度及能耗分析

3 实验仿真

本文实验环境为Intel(R) Core(TM) i3-2370M CPU @2.40 GHz,Windows10操作系统,整个实验基于Python2.7实现,分别在高斯数据集与IBRL数据集中进行测试。

3.1 高斯数据集实验

人工构造高斯数据集,其包括2个特征向量温度和湿度,每个特征向量均服从正态分布,该正态分布的均值随机选自{0.30,0.35,0.45},标准差为0.03,给每个特征向量引入噪声(异常),异常数据点服从[0.5,1.0]上的均匀分布。此高斯数据集由10个传感器节点的数组组成,每个节点包含100个正常数据以及5个异常数据。数据需要先标准化到[0,1]区间以供使用。

检测率(Detection Rate,DR)是指根据异常检测算法检测出的异常数据数量占实际异常数据总数的比例。误报率(False Positive Rate,FPR)是指被算法误判为异常值的正常数据数量占实际正常数据总数的比例。

HSCBD检测方案[14]的检测效果如图3所示。由图3可知,当w∈[0.005,0.018]时,该算法有较高的检测率以及较低的误报率。当w∈[0.03,0.04]时,异常数据点可能会被划分到正常数据簇内,从而影响检测效果,并且导致较高的误报率。由此可知,HSCBD方案对w参数比较敏感。

图3 HSCBD方案检测效果(高斯数据集)

基于高斯数据集,利用控制单一变量法,实验验证本文方案A_HSCBD在不同聚类数量k时的检测率,结果如图4所示。由图4可知,当k∈[13,15]时,本文方案同样能够实现较高的检测率。当k=14时,检测效果如图5所示。由图5可知,该方案的检测效果与HSCBD相当。

图4 A_HSCBD方案的检测率(高斯数据集)

图5 A_HSCBD方案检测效果(k=14,高斯数据集)

基于数据总量以及聚类操作得到簇的数量,可以衡量HSCBD与A_HSCBD方案相对于集中式方案所能够实现的通信复杂度节省率,结果如图6所示。由图6可知,在高斯数据集中,本文方案比HSCBD方案能够实现更高的通信复杂度节省率。

图6 2种方案的能量节省率(高斯数据集)

3.2 IBRL数据集实验

IBRL数据集是在美国加利福尼亚州的因特尔伯克利实验室中收集的数据集合。收集该数据的传感器节点部署于室内环境,传感器以31 s的时间间隔收集5个测量值:温度,光强,相对湿度,电压和拓扑信息。由于数据量巨大,本文只研究2004年3月1日0:00:00—03:59:59时间窗口内的数据。

图7和图8分别为HSCBD和A_HSCBD方案基于IBRL数据的仿真结果。可以看出,当k∈[0.013,0.015]时,A_HSCBD方案的检测率为98%,与HSBCS方案的检测率96%相比,提高了2个百分点,并且误报率也处于较低水平。图9为HSCBD与A_HSCBD方案相对于集中式方案的能量节省率的对比。由图9可知,在IBRL数据集中,本文方案与HSCBD方案相比,能量节省率有了进一步提高。

图7 HSCBD方案的检测效果(IBRL数据集)

图8 A_HSCBD方案的检测效果(IBRL数据集)

图9 HSCBD与A_HSCBD方案的能量节省率对比(IBRL数据集)

3.3 结果分析

为避免偶然性因素的影响,对2个数据集进行10次实验,其平均检测率如表2所示,可以看出,与集中式方案、HSCBD方案相比,本文方案检测效率较高。

表2 3种方案10次平均检测率对比

综合分析可知,与集中式方案和HSCBD方案相比,本文方案具有较高的检测效率和通信效率,但由于聚类算法k的确定需要一个学习过程,其时间复杂度较高。

4 结束语

本文提出一种针对无线传感器网络异常数据的分布式检测方案。该方案在网络中传播能够代表当前节点信息的摘要信息,执行簇合并算法以减少网络通信开销,同时由网关节点执行异常簇的检测,将异常簇信息传递至各节点进行异常数据点检测,从而区分单节点级别异常数据。仿真结果表明,与集中式方案及HSCBD方案相比,本文方案取得了更高的检测效率并大幅降低了能量消耗。下一步将引入空间维度相似性对该方案进行改进。