基于子图拉普拉斯谱的异常传感器检测及识别方法∗

张文安，洪 毅，史秀纺，葛其运

(1.浙江工业大学信息工程学院，浙江 杭州 310023；2.科润智能控制股份有限公司，浙江 江山 324100)

在如今日益提倡“万物互联”的背景下，无线传感器网络已逐步影响着人们生活的方面。随着各行各业的飞速发展，对传感器系统的要求也越来越高，尤其是在军事、交通等领域中，需要传感器系统具有较高的可靠性、灵活性、精确性以及抗干扰性。然而在实际环境中，无线传感器网络容易受到外界因素或自身因素的干扰，例如在无线传感器网络中，传感器之间交互的数据容易受到黑客的篡改，从而影响系统的决策；在车联网系统中，当传感器自身能耗较大时，一旦传感器供电不足，其采集到的数据将不再具备连续性，这将对智能交通系统造成极大的影响。因此，为保障系统的正常运行，传感器一旦出现异常，需要快速检测出异常情况并识别异常传感器。

针对无线传感器网络的异常检测，现有的研究方法主要有三类:基于深度学习的方法、基于信息融合的方法和基于图模型的方法。在基于深度学习的方法中，文献[1]基于LeNet－5卷积神经网络设计了合适的卷积层特征面及全连接层的参数，构造了3种新的卷积神经网络模型，并通过模型的卷积层自主学习数据特征，从而对传感器异常数据进行检测，该方法解决了传统检测算法的性能容易受到相关阈值影响的问题。文献[2]中利用卷积神经网络(CNN)中的卷积层和池化层提取传感信号之间的相关特征，并在此基础上通过全连接层诊断传感器异常。基于信息融合的算法对无线传感器网络的异常诊断也有良好的效果，如文献[3]提出了一种基于卡尔曼滤波的传感器融合算法，结合信息熵方法对无线传感器网络进行异常检测，文献[4]中将贝叶斯推理法与多源信息融合相结合，来诊断无线传感器网络中的异常信息。基于深度学习的方法和基于信息融合的方法都只是利用传感器之间的数据时间关联性进行建模分析，对于传感器在空间上的分布情况考虑较少，这会造成模型对数据的依赖性较高从而忽视传感器之间的空间分布关联度。基于图模型的方法能弥补上述方法的不足，Sandryhaila和Moura在文献[5]中首次提出利用图高通滤波器对无线传感器网络进行异常检测，该方法通过图频谱判断无线传感器网络是否出现异常，且异常检测率较高。卢等人在文献[6]中利用传感器节点的顶点域平滑性与图频域低频特性联合分析方法计算低通滤波前后图信号的平滑度，建立平滑程度判决准则，实现对异常节点的存在性判断。然而以上方法只能判断无线传感器网络中是否存在异常情况，并不能成功识别异常传感器，如何在无线传感器网络中识别异常传感器仍具有一定挑战。

文献[7]通过传感器采集的历史数据，构造非线性多项式图滤波器即数据重构模型拟合图上传感器历史数据，将实时数据作为模型的输入，通过对比每个传感器上输出信号与输入信号的残差大小从而判断传感器的异常情况，该方法检测率高于经典的图频率检测方法，尤其是对于较小的信号扰动，其检测效果优势较为明显，然而该方法所设计的非线性模型参数较多，且算法中的阈值求取也较为复杂。文献[8]进一步改进了文献[5]的结果，将传感器网络划分为多个子网络并定义为子图，利用子图的特定频率来识别异常节点，该方法针对密集节点群有较好的识别效果，但对于稀疏节点群以及边缘节点中的异常节点识别效果较差。针对以上问题，本文提出了一种基于子图拉普拉斯谱的异常传感器检测及识别算法，从而提高稀疏节点群及边缘节点群中的异常节点检测及识别性能。本文方法有如下特点:①在保证内部密集节点群异常检测效果的基础上，通过将整体图模型进行子图划分，增强边缘节点群及稀疏节点群中异常节点的在图上的重要性，从而提高边缘节点群及稀疏节点群异常检测效果。②对于子图网络拓扑结构，本文通过只构建中心节点与邻居节点的边连接，省去邻居节点之间相互的边连接的方法，突出子图中心节点的重要性，降低计算复杂度。③本文所提方法较易实现，通过将图频域信号还原，对比还原信号与原信号的差异，能快速找出异常节点。

1 图相关理论及问题描述

图信号处理(Graph Signal Processing)是将经典的规则域数字信号处理工具，如信号采样[9]、傅里叶变换[10]、滤波[7]和频率响应[11]，延伸到图上非规则域信号处理的一种新兴的研究工具。高维数据的低维表示是图模型处理数据的优势之一，其对信号的处理提供了极大的方便。对此本文利用图模型来处理传感器所采集的数据，并分析检测异常传感器及其所在位置。

1.1 图信号模型要素

首先用图模型表示一个无线传感器网络，如图1所示，图上黑点代表传感器，黑点之间的边代表传感器之间的通信。

图1 无线传感器网络图模型

用G表示一个图模型，模型上的节点集用V表示，节点之间的连线(即边集)用E表示，则一个图可以简单的用G(V，E)表示。对于一个传感器个数为N的网络，为了反映图上节点之间的连接关系，定义了邻接矩阵A，若节点i与节点j之间有边连接，则A(i，j)＝1，反之，则A(i，j)＝0其中i，j＝1，…，N。如果考虑不同节点之间的关联程度，可根据问题的需求来定义节点与节点之间的权重关系，于是可将邻接矩阵调整为邻接权重矩阵W，即

式中:w i j表示节点i与节点j的连接权值。本文在边权重的选取上主要参考文献[11]中两方面的因素:节点间距离以及相邻节点历史信号差值。节点间的关系是正相关的，对此利用高斯核函数定义节点间的边权重:

式中:r ij为节点i与节点j的欧式距离，r i j＝‖x ix j‖，其中x i，x j分别为节点i，j的位置。e ij(T)表示T时刻节点i与节点j历史信号差值的平均值，即

式中:f i(t)，f j(t)表示为第i个节点与第j个节点在t时刻采集的信号，T表示当前时刻。σij和σg是可调参数，分别控制节点间距离及节点间信号相似度对权重选择的影响。根据邻接权重矩阵可构造度矩阵D，其内部的元素d i j的定义如下:

度矩阵是一个对角阵，其所在行或列的对角元素值越大，则所对应的节点对于整体图的关联程度越大。

在经典的离散数字信号处理方法中，通常利用傅里叶变换将不同角频率的三角函数作为正交基，求出信号在不同正交基上的分量，从而将信号进行分解。与离散傅里叶变换类似，图傅里叶变换的目的也是通过线性映射来获取图信号在不同频率上的分量。为此引进图拉普拉斯矩阵L。对于图而言，图拉普拉斯矩阵等价于图信号的梯度的散度，其数值上等于

图拉普拉斯矩阵是一个半正定对称矩阵，其特征向量相互正交，可以构成图频域的正交基，其特征值可作为图信号的频率。

1.2 图拉普拉斯谱

本文选择图拉普拉斯谱对图信号进行处理。将图拉普拉斯矩阵L进行特征值分解:

式中:Λ＝diag{λi}，i＝1，2，…，N，λi为L的特征值，正交矩阵U＝[u1，u2，…，u N]，u i∈ℝN为特征值λi对应的特征向量，u1，u2，…，u N构成了图频域中的正交基，传感器所采集到的信号可表示为:

式中:列向量f(t)＝[f1(t)，f2(t)，…，f N(t)]T∈ℝN表示t时刻所有传感器采集到的信号，系数a1，a2，…，a N表示信号在不同特征频率上的分量，向量u1，u2，…，u N对应的特征值满足:

在图信号的拉普拉斯谱中，较小的特征值对应较低的频率，将图上传感器收集到的信号投射到不同频率的正交基上，即左乘UT便可将信号从节点域转换到图频域:

图2 2013年3月某天洛杉矶温度信号频谱图

1.3 问题描述

当传感器采集的数据异常增大或减小时，类似在正常信号上加了噪声，其高频分量将会出现异常增大的情况。为便于观察异常信号对高频分量的影响，采用文献[8]中的高通滤波器对信号进行预处理

式中:H为高通滤波器(t)]T∈ℝN是经过高通滤波处理后的高频图信号。将预处理后的信号转换到图频域上，得

图3 不同区域存在异常节点的高通信号频谱对比图

2 异常节点检测及识别算法

本文设计的异常节点检测及识别算法分为三部分:子图划分，滤波设计，异常节点检测及识别。

2.1 子图划分

为了增强图上边缘、稀疏节点群中节点的重要程度，并在这些节点出现异常时，能快速检测并识别异常节点，本文首先对整体图模型进行划分，其划分情况如图4所示，将图上每一个节点和它最近的M个相邻节点共同构成子图模型G i＝(V i，E i，W i)，i＝1，2，…，N，第i幅子图的节点集合V i＝[vi，1，v i，2，…，vi，M＋1]，其中vi，1表示子图i的中心节点，其余节点为中心节点的邻居节点。在未知节点间网络连接通信的情况下，为节省通信开销，降低矩阵求逆时的计算难度，突出中心节点在子图中的重要作用，所构造的子图模型中，邻居节点间不存在边连接。

图4 子图划分示意图

2.2 滤波设计

在子图模型中，节点之间的信号差异较小，所以在频谱图上，信号的分量会主要集中在低频段，根据式(7)可知传感器上采集的信号可由不同频率分量的信号线性组合构成，而高频分量远小于低频分量，且信号间的异常波动体现在高频分量上，因此本文首先设计一个低通滤波器，对高频分量进行抑制，将图频域上的信号进行维度压缩

式中:p i，k∈ℝM＋1是子图i所设低通滤波器的第k个列向量，P i＝[p i，1，p i，2，…，p i，M＋1]为子图i的低通滤波器，u i，1，u i，2，…，u i，M＋1表示子图i的图拉普拉斯矩阵特征分解后的特征向量，其对应的特征值构成的特征值矩阵表示为Λi＝diag{λi，k}，k＝1，2，…，M＋1。通过设置的低通滤波器，可以保留图频域信号的低频分量，将信号中的噪声滤除，从而保证相邻节点之间信号的相似度。图频域信号在经过低通滤波器处理之后将还原回节点域

2.3 异常节点检测及识别

本文所提出的异常传感器检测及识别算法的流程如图5所示。

图5 异常传感器检测及识别算法流程图

经过低通滤波器处理后，节点间信号的波动将会减小，将还原后的信号与最初节点采集得到的信号进行对比，计算子图i中各节点的还原信号与采集信号的绝对差值

对于子图i，若Δf i，1(t)大于所设定的阈值θ1，则将子图G i归于集合S1，若Δf i，k(t)大于所设定的阈值θ2，则将子图G i归于疑似异常子图集合S2。对节点i的异常情况首先进行预判定

当TF(i)＝1时，则判定节点i出现异常，当TF(i)＝0时，需对节点i进行下一步检测。将包含节点i的所有子图设为集合C i，将集合S2中包含节点i的子图设为集合S2，i，则节点i的状态TN(i)可定义为:

式中:｜S2，i｜表示集合S2中包含节点i的子图个数，｜C i｜表示包含节点i的所有子图个数，ε为所设阈值，当TN(i)＝1时，节点i同样被认为存在异常情况。最终，用状态TS(i)来判断节点i是否存在异常情况:

若TS(i)＝1，则认为节点i存在异常情况，反之则为正常节点。

3 仿真结果及分析

本文所用数据集来源于美国国家气象局官方网站公开的全球温度数据集[12]。本文选取2013年，经度在东经54°～东经69°，纬度在南纬6°～北纬17°，海拔高度在50米以下的49个温度传感器节点的前5个月的数据作为实验仿真数据，验证所提算法的有效性。首先验证边缘异常节点的检测及识别性能，针对某一天的温度数据随机选择一个边缘节点进行人为攻击，其攻击方式是在原有采集数据的基础上增加15℉，采用本文所提的子图方法进行检测，经过子图处理后，其高通信号频谱图如图6所示，可以看出，即使边缘节点出现问题，也能在频谱图高频分段上表现出差异。

图6 边缘节点群单个节点受到攻击时高通信号频谱子图

对于异常节点的识别，利用本文设置的低通滤波器把图频域信号还原至节点域信号，当1号边缘节点出现问题时，其信号对比如图7所示。

图7 1号边缘节点出现异常时，还原信号与采集信号对比图

从图7(a)中可以看出，1号节点在受到攻击时，由于其是边缘节点，在图上位置与图上许多节点较为疏远，即使出现问题也不易在整体图中检测出异常现象；当采用本文所提的方法进行检测时，如图7(b)所示，经子图和低通滤波器处理之后，1号节点与原先采集的信号相比，偏差较大，即可认为1号节点出现异常。

针对所采用的数据集，选择连续65天内，49个节点的温度数据。在本文所提算法中，利用箱形统计图方法[13]，确定阈值θ1＝10，θ2＝7.5，ε＝0.9。为说明所提算法性能，本文与文献[8]中的方法、FD[14]、DFD[15]、基于双邻域算法[16]以及分簇算法[17]进行对比，从以下四个指标来说明算法的性能:检测率DR(Detection Rate)、定位率TPR(True Position Rate)、漏检率MR(Missing Rate)、误检率ER(Error Rate)。实验总次数记为Tall，将检测出存在异常节点的实验次数记为Tdet，将能检测出所有真实异常节点的试验次数记为Ttrue，未能检测出所有真实异常节点的试验次数记为Tmiss，将检测出非真实异常节点的次数记为Terror，则有

首先分析单个节点异常的检测性能。每次随机选择其中一个节点进行攻击，首先测试异常增大的情况，其结果如表1所示。

表1 单个节点信号值异常增大15℉不同检测方法的检测指标表

从表1中可看出，本文所提算法对于单个节点异常精准识别率相较于其他方法有较大的优势。[1]中所提方法也用采用了子图模型，但其模型对节点间的连通性要求较大，本文的子图模型更突出中心节点的重要性，且效果也远比文[1]中的结果好。

当传感器供电不足时，往往会出现无示数情况，于是本文检测了单个传感器信号值置0时，异常节点的检测效果，其结果如表2所示。

表2 单个节点信号值置0不同检测方法的检测指标表

由于本文所选温度的范围在20～70之间，当出现节点信号置0的情况，异常节点在不同的算法下，检测效果都增强了，但误报率也普遍升高，整体上本文所提方法的误报率优于其他方法。

由于无线传感器网络中存在多个传感器同时出现异常的情况，因此，本文对多个传感器同时出现异常的情况进行了验证，其结果如表3和表4所示。

表3 随机两个节点信号值异常增大15℉不同检测方法的检测指标表

表4 随机三个节点信号值异常增大15℉不同检测方法的检测指标表

从表3、表4可以看出随着异常节点数目的增多，算法的检测性能普遍下降，且误报率和漏检率明显升高，但本文所提方法在多个节点出现异常时，仍能保持相对较高的识别率。

4 结论

本文采用一种基于子图拉普拉斯谱的异常节点识别方法对故障传感器进行检测识别，该方法在传统频谱法分析基础上加以改进，提高了边缘稀疏节点群中异常节点的检测及识别准确率，且在一定程度上保证了俺去多节点异常时的检测性能，算法易于实现且开销较小，适合应用于无线传感器网络中。后续工作将在空间域的基础上，增加时间域的判断，以进一步提升识别精确度。