ISSN1001⁃9081
CODENJYIIDU2020⁃03⁃10
http://www.joca.cnDOI:10.11772/j.issn.1001-9081.2019071224
基于图信号处理的无线传感器网络异常节点检测算法
2
卢光跃1,,周
2*2
亮1,,吕少卿1,,施
22
聪1,,苏可可1,
(1.西安邮电大学通信与信息工程学院,西安710121;2.陕西省信息通信网络及安全重点实验室(西安邮电大学),西安710121)
(∗通信作者电子邮箱zl2018zd@163.com)
摘要:针对无线传感器网络(WSN)中传感器自身安全性低、检测区域恶劣及资源受限造成节点采集数据异常的
问题,提出一种基于图信号处理的WSN异常节点检测算法。首先,依据传感器位置特征建立K-近邻(KNN)图信号模型;然后,基于图信号在低通滤波前后的平滑度之比构建统计检验量;最后,通过统计检验量与判决门限实现异常节点存在性的判断。通过在公开的气温数据集与PM2.5数据集上的仿真验证,实验结果表明,与基于图频域异常检测算法相比,在单个节点异常情况相同条件下,所提算法检测率提升7个百分点;在多个节点异常情况相同条件下,其检测率均达到98%,并且在网络节点异常偏离值较小时仍具有较高的检测率。
关键词:无线传感器网络;图信号处理;异常节点检测;图低通滤波器;平滑度中图分类号:TP393.02文献标志码:A
Outliernodedetectionalgorithminwirelesssensornetworksbasedon
graphsignalprocessing
(1.SchoolofCommunicationsandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’anShaanxi710121,China;
(Xi’anUniversityofPostsandTelecommunications),Xi’anShaanxi710121,China)
2.ShaanxiKeyLaboratoryofInformationCommunicationNetworkandSecurity
22*222
LUGuangyue1,,ZHOULiang1,,LYUShaoqing1,,SHICong1,,SUKeke1,
Abstract:Sincethelowsecurityofsensors,poordetectionareaandresourcelimitationinWirelessSensorNetwork
(WSN)causeoutlierdatacollectedbynodes,analgorithmoftheoutliernodedetectioninWSNbasedongraphsignalprocessingwasproposed.Firstly,accordingtothesensorpositionfeatures,aK-NearestNeighbors(KNN)graphsignalmodelwasestablished.Secondly,thestatisticaltestquantitywasbuiltbasedonthesmoothnessratioofthegraphsignalbeforeandafterlow-passfiltering.Finally,thejudgementoftheexistenceofoutliernodeswasrealizedthroughthestatisticaltestquantityanddecisionthreshold.ExperimentsonthepublictemperaturedatasetandPM2.5datasetdemonstratethatcomparedwithalgorithmofoutliernodedetectionbasedongraphfrequencydomain,theproposedalgorithmhasthedetectionrateincreasedby7%undertheconditionofsingleoutliernodeandhasthedetectionrateof98%undertheconditionofmultipleoutliernodes,andkeephighdetectionrateundertheconditionofoutliernodewithsmalldeviationvalue.
Keywords:WirelessSensorNetwork(WSN);graphsignalprocessing;outliernodedetection;graphlow-passfilter;smoothness
0
无线传感器网络是由大量静态或动态的传感器节点以自
引言
组织和多跳方式构成的一种分布式传感网络[1]。随着无线通信和微电子技术的不断创新,具有体积小、低成本和低功耗的传感器节点被广泛应用到医疗实时监测[2]、生态环境监测[3]、军事战场监视[4]等许多重要领域[5]。由于传感器节点自身安全性低、资源受限、常处于恶劣的环境中且无人看护,使得节点极易受到来自外界和自身因素的影响而导致节点出现异常。如果异常信息未被检测而加以分析,将会给决策带来严重后果。同时,由于大规模非规则网络结构的出现,使得对具有非规则网络拓扑结构的无线传感器网络异常检测成为研究
的热点。
异常值也被称为离群值,是指节点自身故障、节点之间通信受阻及外界环境攻击等原因造成采集数据显著偏离正常模式下传感器采集的值。目前,对于异常节点的检测方法有许多种类型。基于统计学的方法[6]需要相应的先验知识建立统计概率分布模型,在该模型的基础上对数据的分布进行映射,通过它们和统计模型的拟合程度进行判决。如果准确获得统计模型,该算法则可以有效检测异常值;然而,在很多应用场景中,很难获得传感器分布的先验参数。基于分类的异常检测算法[7]主要通过数据距离寻找数据之间的相似度,并根据相似度对节点数据进行分类寻找异常节点,其优势在于并不需要统计模型。此外还有基于K均值的检测算法[8]和基于局
收稿日期:2019⁃07⁃15;修回日期:2019⁃09⁃17;录用日期:2019⁃09⁃18。基金项目:陕西省教育厅科研计划项目(17JK0703)。作者简介:卢光跃(1971—),男,河南南阳人,教授,博士,主要研究方向:信号与信息处理、频谱感知、大数据分析;周亮(1994—),男,陕西西安人,硕士研究生,主要研究方向:大数据分析、图信号处理;吕少卿(1987—),男,山西五寨人,讲师,博士,主要研究方向:社交网络、大数据分析;施聪(1994—),男,陕西西安人,硕士研究生,主要研究方向:深度学习、频谱感知;苏可可(1996—),女,陕西渭南人,硕士研究生,主要研究方向:大数据分析、图信号处理。
784计算机应用
第40卷
部异常因子(LocalOutlierFactor,LOF)的检测算法[9],这些异
常检测算法在某些方面具有很高的检测率,但是其大多数只是从数据的时间相关性或空间相关性考虑。而目前随着网络技术的快速发展,人们已经步入大数据与智能物联时代,不同网络下的数据处理急剧增加,比如信息网络[10]、社交网络[11]、大脑神经网络等不同类型网络。面对这些具有非规则拓扑结构网状的高维度数据异常检测算法相对较少,因为不仅要考虑数据本身问题,还要考虑数据自身存在的拓扑结构。国外学者Shuman等[12]和Sandryhaila等[13]提出了图信号处理GraphSignalProcessing,GSP)的概念,其思想是通过数据的拓扑结构建立网络加权图,再将信号值映射到网络加权图的各个顶点上形成图信号。因此,图信号能够很好地体现网络数据与网络拓扑结构之间的关系,为解决非规则拓扑结构网络的高维度数据提供了一种天然的数学模型。目前图信号处理主要应用于网络缺失值重构[14]、网络异常检测[15]、拓扑图
学习[16]以及图小波变换[17]
等领域。
文献[18]中提出使用图频域异常检测算法对无线传感器网络异常节点进行检测,其核心思想是异常节点导致图信号在图频域的高频分量增大。因此根据图频域傅里叶系数与阈值可直接判断是否存在异常节点,该方法便于实现且异常检测率达到89%。但该方法只单一从图频域进行判断,在传感器异常节点偏离值较小时则会导致检测率降低。针对以上问题,本文提出了一种新的无线传感器网络异常节点检测算法,首先建立图信号模型,设计图低通滤波器,然后基于低通滤波前后的图信号平滑度之比构建统计检验量,从而实现对异常节点的存在性进行最终检测。该算法不仅在相同条件下具有更高的检测率,当网络中异常节点偏离值较小时,仍能达到较高的检测率。
1.11
相关理论
图信号处理是基于对图或网络上的信号进行分析所衍生图信号模型
的一种新兴的数学工具。与传统的数字信号不同,图信号是将信号值映射在图的各个节点上,每一个节点表示该信号产生的位置。
在构建图信号模型时,根据每个传感器节点的位置特征,计算相邻节点间的欧氏距离,通过K-近邻来建立图信号模型。图1所示的是一个简单的图信号拓扑。图信号中每个节点表示一个传感器,节点上的竖线表示传感器采集的信号值,图模型中节点之间有边连接表示节点之间相关联,反之则无关联。
通常,将一个无向图定义为G=(V,
E),V={v代表N个节点的集合,E是所有相连节点边的集合。而图的
1,v2,⋯,vN}网diag络{拓d扑结构则用图拉普拉斯矩阵L=D-W表示,
D=i}表示图的度矩阵,表示图的加权矩阵,di是与节点i相连的所有边的数目;W∈RN×NW={wij},wij表示节点i与节点j
之间的关联程度,可定义为:
wìïaij
Kij2, i≠jij=íï其中:i到节点j=î
a0的欧氏距离:1,表示节点i(1)i=与节点jijj相连接,反之aij=0;Kij为节点Kij1.2
(Xi-Xj)2+(Yi-Yj)2
(2)
在经典的数字信号处理图信号的傅里叶变换=
(DigitalSignalProcessing,DSP)
中,函数f(t)的傅里叶变换如式∫
(3)所示:
F(ω)=
R
f(t)e-jωtdt(3)
从经典的傅里叶分析,可以得出e-jωt实质上代表一维拉普拉斯矩阵的特征函数[12],即:
-Δ(ejωt)=-∂22ejωt=ω2ejωt(4在图信号处理中,∂t)
可以使用图拉普拉斯矩阵的特征值与特征向量定义图傅里叶变换。首先将图拉普拉斯矩阵进行特征值分解L=UΛUT,得到图拉普拉斯矩阵的特征向量矩阵U=[u1,2,⋯1,u因此图信号的傅里叶变换和逆变换定义为:
,N2),⋯,u,其中N0]=和λ特征值矩阵Λ=diag{λi}1≤λ2≤⋯≤λ(i=N。
F=UTf
(5)f=UF
(6)
图拉普拉斯矩阵的特征值λi表示图信号的频率,ui表示图频率相对应的图信号分量。从式(4)可以看出,ω越大,频率越
大;图信号的频率λi也类似,即λi越大,图信号频率也越大。
1.3
Fig.1Network图1图信号网络拓扑
topologyofgraphsignals
在图信号处理中,图信号平滑度
(∑图信号的平滑度可定义为:Sf)=
w
ij
(i,j)∈ε
[f(j)-f(i)]2
(7)
其中ε表示与节点i相连的所有边的集合。
从式(7)中可以看出,图信号平滑度表示节点图信号的相近程度。平滑度越大,说明相邻节点的图信号有较大差异;而平滑度越小,说明相邻节点的图信号越相似。
当所有节点都正常工作时,节点上的图信号不仅在时间上平稳变化,在空间上相邻节点之间的图信号也随着时间平稳变化,因此图信号的平滑度小;而当存在异常节点时,图信号的平滑度将不可避免地增大。
2.21
异常节点检测方法
在无线传感器网络正常工作时,图频域
相邻传感器节点间的相似性也是平稳变化的,该相似性是指正常工作时相邻传感器采集数据之间差值的绝对值,所以图信号在频域具有低频特征。如果采集的数据有异常值存在,则会在频域出现高频分量。如图12时图信号的频域只含有低频特征;、3、5个)异常节点时的频谱图。可以明显看出,所示,分别绘制传感器在无异常节点和有多个(如而当有异常节点存在,在无异常值可以
(第3期卢光跃等:基于图信号处理的无线传感器网络异常节点检测算法
785看出其频域不仅含有高频分量,而且随着异常节点个数的增
加高频分量也更加丰富。
Fig.图2graph2
有/无异常节点的图信号频谱对比
2.2
signalsFrequencywithandspectrumwithoutcomparisonoutliernodes
of
图低通滤波器的设计如式图低通滤波器
g(λi)=
{1其中λ0,,λ(8)所示:
λi<λcut
(8)
i≥λcut
在本文中选择图拉普拉斯矩阵特征值的中位数作为图滤cut为图滤波器截止频率。
波器截止频率。2.3首先对图信号进行低通滤波,平滑程度准则
得到低通滤波后的图信号为:
fLP=Ug(λ)UTf(9)
计算低通滤波后图信号的平滑度,即:SLP(f)=∑wij[fLP(j)-fLP(i)]
2(10)
(i,j)∈ε
图3表示低通滤波前后有、无异常节点图信号的对比。
无异常节点时,相邻节点间的信号值相近,图信号具有低频特征,频率分量都在低频部分,因此无异常节点时图信号在低通滤波前后基本一致。当存在异常节点时,图信号的平滑度变化,出现较多的高频分量,此时异常节点存在时的图信号通过低通滤波后,其异常的高频部分被抑制,因此异常节点存在时图信号低通滤波前后将有较大的变化,这意味着其平滑度会有较大的变化。
图3
withoutFig.低通滤波前后有、outlier3
Comparisonnodesbeforeof无异常节点的图信号对比
graphandaftersignalslow-withpassand
filtering
基于以上分析,设计如式(11)所示的平滑程度判决
准则η:
η=S(f)
ìHSLP其中:
H(f)=í
0,η<γ
îH1,η≥γ
(11)
0表示不存在异常节点,H1表示存在异常节点,γ表示判决门限。2.4
图确定判决门限
4表示有、无异常节点的η的样本统计直方图,从图中
箭头所指的局部放大部分可以看出η在有无异常节点时的分布情况。
Fig.图44
有、Sample无异常节点的样本统计直方图
withoutstatisticaloutlierhistogramnodes
withand
结合有、无异常节点的η的样本统计,根据样本统计变量,选取有异常节点的最小值和无异常节点的最大值作为判
决门限的取值区间,通过遍历判决门限区间上的每一个值计算相对应的准确率,将准确率最大时所对应的判决门限设为最佳判决门限。
3
本文的所有数据处理及仿真均采用实验仿真与分析
Matlab-2017b软件进
行。在美国主要城市日平均气温数据集gov/pub/data/gsod)(ftp://ftp.ncdc.noaa.
[19]和加利福尼亚日平均PM2.5数据集
https://www.epa.gov/outdoor-air-quality-data)[20]
上分别进行
仿真,并与文献[18]中基于图频域分析的方法进行受试者工作特征ROC的每一个点表示相对应的判决门限。在虚警率相同的情况下曲线中,(Receiver检测率作为OperatingYCharacteristic轴,虚警率作为,ROCX轴,)曲线对比。在ROC曲线上检测率越高,表明对应算法的性能越好,此时虚警率与检测率相交的点即为该数据集下的最佳判决门限。3.1
本文首先选取的是美国主要城市气温数据集,气温数据集
该数据集来源于美国国家气象局官方网站公开的美国主要城市2003年日平均气温数据集。在实验仿真中,150-19.9个主要城市365天日平均气温数随机选择该数据集下据。数据集范6每个竖线代表每个传感器采集的信号值。
个节点相连接建立~99.9oF。首先根据传感器位置特征将节点与最近邻的
围从6近邻图信号模型。如图5所示,图上的图5美国主要城市2003年日平均Fig.5
Network气温网络拓扑
temperatureofUSAtopologymajorofcitiesdailyinaverage
2003
(786计算机应用
第40卷
本文分别对2种不同场景下的异常情况进行实验仿真。首先考虑单个节点异常,与文献[18]中模拟故障节点类似,每
一次随机选择某一天单个传感器节点气温值偏离20∘
异常节点,为了体现所提算法在异常偏离值较小时具有更好F作为的检测性能,同时仿真了气温值偏离10∘况。第二种考虑多个节点异常,每次随机选择某一天多个
F和15∘F时的异常情(2%、3%、5%个)传感器节点作为异常节点,同时偏离10∘两种情况下均进行50000次仿真实验。
F。图6显示在单个节点异常情况下偏离值不同时本文所提算法与图频域算法的ROC曲线对比。从图中可以看出,单个节点异常偏离值越大,即数据集的方差越大时,其检测效率越高;反之,当异常偏离值较小,即数据集的方差较小时,其检测率较低。而且从图中明显看出在虚警率相同条件下,所提算法在单个节点异常偏离值为10∘法在异常偏离值为20∘F时的检测率高于图频域算同时所提算法优于图频域算法,F时的检测率。结果表明在虚警率相且当异常偏离值较小时所提算法相比图频域算法具有更高的检测性能。
图6
Fig.气温数据不同偏离值下的6
ComparisonROC曲线对比所示为多个different(2%temperatureof、3%、5%dataROC个)deviations
curveswith
图7节点异常情况下本文所提算法与图频域算法的ROC曲线对比。从图中可看出随着异常节点数增多,两种算法的检测性能同时增大;但从图中虚线所指的局部放大图中可看出,在相同仿真条件下,所提算法检测率均高于图频域算法的检测率。
Fig.7
图7
Comparison气温数据多节点异常下的ofROCcurvesoftemperatureROC曲线对比
dataunder
3.2
PM2.multipleoutliernodes
第2个仿真实验数据采用美国环境保护局官方网站公开
5数据集
的加利福尼亚州监测站点2015年日平均PM2.5数据集。在实验仿真中,随机选取了该数据集下的60个站点200天的日平均PM2.5数据,数据集范围从-2.03μg/m3到164.851μg/m3,
如图8所示。
PM2.同样对两种不同场景下的异常情况进行实验仿真,由于
实验中,5数据与气温数据的度量值不一样,将某一天的单个节点数据值偏离因此在第一种仿真15μg/m3作为异常节点,同时为了体现本文所提算法在异常偏离值较小时具有
更好的检测性能,仿真了单个节点数据值偏离10μg/m3和5μg/m3时的异常情况。第二种实验每次随机选择某一天多个(2%、3%、5%个)传感器节点作为异常节点,同时偏离10μg/m3。两种情况均进行10000次仿真实验。
图8加利福尼亚2015年日平均PM2.5dailyaverageFig.8
PM2.Network网络拓扑
5ofCaliforniatopologyof图9显示PM2.5数据集在单个节点异常情况下偏离值不in2015
同时本文所提算法与图频域算法的ROC曲线对比。与气温数据集在单个节点异常情况下的仿真结果一样,数据集的方差越大,其检测率也越大。同样,在异常偏离值为5μg/m3时
其15检μg/m测性能仍然高于频域算法在异常偏离程度为3时的检测性能。
图9
Fig.PM2.9
5数据不同偏离值下的ComparisonofROC曲线对比
图10是PM2.different5数据集在多个PM2.5dataROC(deviations
curveswith
2%、3%、5%个)节点异常情况下本文所提算法与图频域算法的ROC曲线对比图。从图中可以看出,异常节点数越多,两种算法的检测性能越好,但当虚警率相同时所提算法在相同仿真条件下仍然具有较高
的检测性能。
对以上两种具有不同特征集的数据上分别进行实验仿真,结果表明在虚警率相同的情况下所提算法具有更好的检测性能。此外,可以看出在PM2.5数据集上的检测性能略低于气温数据集,这是因为气温数据日变化幅度较大,导致数据集方差较大,使得整体的平滑度较低,而PM2.5数据集日变化PM2.幅度5数据集的检测性能较低。但相比现有的图频域算法,
较小,其方差较小,导致整体的平滑度较大,因此第3期卢光跃等:基于图信号处理的无线传感器网络异常节点检测算法
787本文所提算法仍具有较高的检测性能。
Fig.图10
10
ComparisonPM2.5数据多节点异常下的ofROCcurvesofPM2.ROC5曲线对比
4结语
multipleoutliernodes
dataunder
本文提出了一种基于图信号处理的无线传感器网络异常
节点检测算法。利用传感器节点的顶点域平滑性与图频域低频特性联合分析方法计算低通滤波前后图信号的平滑度,建立平滑程度判决准则,实现对异常节点的存在性判断。在不同的数据集上分别进行实验仿真,结果表明,在虚警率相同时所提算法在相同仿真条件下均具有较高的检测率,同时,在单个节点异常偏离值较小时仍具有较好的检测性能。参考文献(References)
[1]
surveySHUKLAontechniquesDS,PANDEYofWSNsAC,involvingKULHARIeventA.andOutliererrordetectionbasedoutli⁃:a
vativeers[C]Applications//ProceedingsofofComputationalthe2014InternationalIntelligenceConferenceonPower,onEnergy
Inno⁃andControlswithTheirImpactonHumanity.Piscataway:IEEEDMITRIEV:113-116.
,[2]
2014talultrawidebandAS,RYZHOVwirelesssensorAI,LAZAREVnetworkforVAmedical,etal.ElectronicsapplicationsExperimen⁃
[2015J].,Journal60(9):1027ofCommunications-1036.
Technologyand,[3]
LUOandnationalextremeX,CHANGJournallearningX.ofControlmachineAnovel,indataAutomationwirelessfusionsensorschemeandSystemsnetworksusinggreymodel
,[2015J].Inter⁃[4]
(3):539-546.
,13KUMARroutingKA,KRISHNAAVN,CHATRAPATIKS.Newgeneousprotocolwithellipticcurvecryptographyformilitaryhetero⁃secure
[5]OptimizationwirelessAKYILDIZSciencessensor,2017networks,38([2)J]:.341Journal-365.ofInformationand2002surveyonsensorIF,SUnetworksW,SANKARASUBRAMANIAM[J].IEEECommunicationsY,Magazineetal.A
,[6]ZHANG,40(Y8,)HAMM:102-114.
outlierdetectionforwirelessNAS,sensorMERATNIAnetworksN[,J]et.al.InternationalStatistics-based
nalJour⁃[7]
GHORBELofGeographicalO,AYADIInformationA,LOUKILScienceK,,et2012al.,Classification26(8):1373-1392.ingdataus⁃ceedingsoutlierdetectionmethodinwirelesssensornetworks[8]
ComputingofABIDConference.the13thIEEEPiscatawayWireless:IEEECommunications[C]//Pro⁃,2017:699-704.andMobilethroughA,outlierKACHOURIandneighborhoodA,MAHFOUDHIdatainwirelessA.Anomalysensordetectionnetworks[TechnologiesC]//ProceedingsSignaloftheand2ndImageInternationalProcessingConference,PiscatawayonAdvanced[9]2016SWAIN:26R-30.
for:IEEE,sensorR,KHILARPM.Compositefaultdiagnosisinwireless
[10]municationsnetworksusingneuralnetworks[J].WirelessBAIoverXwireless,WANG,2017sensorZ,,95ZOU(3):networksL,2507etforal.-2548.
PersonalCom⁃monitoringCollaborativefusionestimation[11]
greenhouseCAIZ,HE[ZJ],.GUANInformationX,etFusional.Collective,2018,data42CO:2-sanitization119concentration-126.inaventingsensitiveinformationinferenceattacksSecureinsocialComputingnetworksforpre⁃[2018J].,IEEE15(4)Transactions:577-590.
onDependableand,[12]
SHUMANingfieldofDsignalI,NARANGprocessingSKon,graphsFROSSARD:extendingP,ethighal.-Thedimension⁃
emerg⁃al[13]SignaldataSANDRYHAILAProcessinganalysistographsAMagazinenetworks,MOURA,and2013otherJM,irregulardomains[J].IEEEF.30(Discrete3):83-signal98.
processingon[14](QIU7):K1644[J],MAO-.1656.
IEEETransactionsonSignalProcessing,2013,61structionX,SHENX,etal.Time-varyinggraphsignalrecon⁃[15]
ing蒋俊正,,2017[,J]11.(IEEE6):870Journal-883.
ofSelectedTopicsinSignalProcess⁃检2364.测定(位杨杰,欧阳缮.一种新的无线传感器网络中异常节点liernodesJIANG算法[detectionJZJ],.YANG电子与andlocalizationJ,信OUYANG息学报,inwirelessS.2018Novel,40sensormethod(10):networks
for2358out⁃
-[J].JournalofElectronics&InformationTechnology,2018,40[16](LIU10)temporalY:,2358YANG-2364.smoothnessL,)
YOUforK,etal.Graphlearningbasedonspatio⁃[17]
ZHENGcess,2019X,,TANG7:62372Y,ZHOU-62386.
time-varyinggraphsignal[J].IEEEAc⁃waveletdecompositionforsignalsJ.Aframeworkonundirectedofadaptivegraphs[multiscaleTransactionsonSignalProcessing,2019,67(7):1696-1711.J].IEEE
[18]SANDRYHAILAgraphs:frequencyA,analysisMOURA]J.MIEEEF.DiscreteTransactionssignalonprocessingSignalPro⁃
oncessing,2014,62(12):3042[J-3054.
ofShaanxiThisworkProvincialispartiallyEducationsupportedDepartmentbythe(Scientific17JK0703)Research.
ProgramLUGuangyue,bornin1971,Ph.D.,professor.Hisresearch
interestsbigdataincludesignalandinformationprocessing,spectrumZHOUanalysis.
sensing,Liang,bornin1994,M.S.candidate.HisresearchinterestsLYUincludeShaoqingbigdata,bornanalysisin1987,graph,Ph.signalD.,processing.lecturer.HisresearchinterestsSHIincludeCong,socialborninnetworking1994,M.,bigS.datacandidate.analysis.HisresearchinterestsincludeSUdeepKekelearning,born,inspectrum1996,M.sensing.
S.candidate.Herresearchinterests
includebigdataanalysis,graphsignalprocessing.
因篇幅问题不能全部显示,请点此查看更多更全内容