基于图信号处理的无线传感器网络异常节点检测算法

卢光跃，周 亮*，吕少卿，施 聪，苏可可

（1. 西安邮电大学通信与信息工程学院，西安710121； 2. 陕西省信息通信网络及安全重点实验室（西安邮电大学），西安710121）

（*通信作者电子邮箱zl2018zd@163.com）

0 引言

无线传感器网络是由大量静态或动态的传感器节点以自组织和多跳方式构成的一种分布式传感网络［1］。随着无线通信和微电子技术的不断创新，具有体积小、低成本和低功耗的传感器节点被广泛应用到医疗实时监测［2］、生态环境监测［3］、军事战场监视［4］等许多重要领域［5］。由于传感器节点自身安全性低、资源受限、常处于恶劣的环境中且无人看护，使得节点极易受到来自外界和自身因素的影响而导致节点出现异常。如果异常信息未被检测而加以分析，将会给决策带来严重后果。同时，由于大规模非规则网络结构的出现，使得对具有非规则网络拓扑结构的无线传感器网络异常检测成为研究的热点。

异常值也被称为离群值，是指节点自身故障、节点之间通信受阻及外界环境攻击等原因造成采集数据显著偏离正常模式下传感器采集的值。目前，对于异常节点的检测方法有许多种类型。基于统计学的方法［6］需要相应的先验知识建立统计概率分布模型，在该模型的基础上对数据的分布进行映射，通过它们和统计模型的拟合程度进行判决。如果准确获得统计模型，该算法则可以有效检测异常值；然而，在很多应用场景中，很难获得传感器分布的先验参数。基于分类的异常检测算法［7］主要通过数据距离寻找数据之间的相似度，并根据相似度对节点数据进行分类寻找异常节点，其优势在于并不需要统计模型。此外还有基于K均值的检测算法［8］和基于局部异常因子（Local Outlier Factor，LOF）的检测算法［9］，这些异常检测算法在某些方面具有很高的检测率，但是其大多数只是从数据的时间相关性或空间相关性考虑。而目前随着网络技术的快速发展，人们已经步入大数据与智能物联时代，不同网络下的数据处理急剧增加，比如信息网络［10］、社交网络［11］、大脑神经网络等不同类型网络。面对这些具有非规则拓扑结构网状的高维度数据异常检测算法相对较少，因为不仅要考虑数据本身问题，还要考虑数据自身存在的拓扑结构。国外学 者Shuman 等［12］和Sandryhaila 等［13］提 出 了 图 信 号 处 理（Graph Signal Processing，GSP）的概念，其思想是通过数据的拓扑结构建立网络加权图，再将信号值映射到网络加权图的各个顶点上形成图信号。因此，图信号能够很好地体现网络数据与网络拓扑结构之间的关系，为解决非规则拓扑结构网络的高维度数据提供了一种天然的数学模型。目前图信号处理主要应用于网络缺失值重构［14］、网络异常检测［15］、拓扑图学习［16］以及图小波变换［17］等领域。

文献［18］中提出使用图频域异常检测算法对无线传感器网络异常节点进行检测，其核心思想是异常节点导致图信号在图频域的高频分量增大。因此根据图频域傅里叶系数与阈值可直接判断是否存在异常节点，该方法便于实现且异常检测率达到89%。但该方法只单一从图频域进行判断，在传感器异常节点偏离值较小时则会导致检测率降低。针对以上问题，本文提出了一种新的无线传感器网络异常节点检测算法，首先建立图信号模型，设计图低通滤波器，然后基于低通滤波前后的图信号平滑度之比构建统计检验量，从而实现对异常节点的存在性进行最终检测。该算法不仅在相同条件下具有更高的检测率，当网络中异常节点偏离值较小时，仍能达到较高的检测率。

1 相关理论

1.1 图信号模型

图信号处理是基于对图或网络上的信号进行分析所衍生的一种新兴的数学工具。与传统的数字信号不同，图信号是将信号值映射在图的各个节点上，每一个节点表示该信号产生的位置。

在构建图信号模型时，根据每个传感器节点的位置特征，计算相邻节点间的欧氏距离，通过K-近邻来建立图信号模型。图1 所示的是一个简单的图信号拓扑。图信号中每个节点表示一个传感器，节点上的竖线表示传感器采集的信号值，图模型中节点之间有边连接表示节点之间相关联，反之则无关联。

通常，将一个无向图定义为G=(V，E)，V={v1，v2，…，vN}代表N个节点的集合，E是所有相连节点边的集合。而图的网络拓扑结构则用图拉普拉斯矩阵L=D-W表示，D=diag{di}表示图的度矩阵，di是与节点i相连的所有边的数目；W∈RN×N表示图的加权矩阵，W={wij}，wij表示节点i与节点j之间的关联程度，可定义为:

其中:aij= 1表示节点i与节点j相连接，反之aij= 0；Kij为节点i到节点j的欧氏距离:

1.2 图信号的傅里叶变换

在经典的数字信号处理（Digital Signal Processing，DSP）中，函数f(t)的傅里叶变换如式（3）所示:

从经典的傅里叶分析，可以得出e-jωt实质上代表一维拉普拉斯矩阵的特征函数［12］，即:

在图信号处理中，可以使用图拉普拉斯矩阵的特征值与特征向量定义图傅里叶变换。首先将图拉普拉斯矩阵进行特征值分解L=UΛUT，得到图拉普拉斯矩阵的特征向量矩阵U=[u1，u2，…，uN] 和 特 征 值 矩 阵Λ= diag{λi} (i=1，2，…，N)，其中0=λ1≤λ2≤…≤λN。

因此图信号的傅里叶变换和逆变换定义为:

图拉普拉斯矩阵的特征值λi表示图信号的频率，ui表示图频率相对应的图信号分量。从式（4）可以看出，ω越大，频率越大；图信号的频率λi也类似，即λi越大，图信号频率也越大。

图1 图信号网络拓扑Fig. 1 Network topology of graph signals

1.3 图信号平滑度

在图信号处理中，图信号的平滑度可定义为:

其中ε表示与节点i相连的所有边的集合。

从式（7）中可以看出，图信号平滑度表示节点图信号的相近程度。平滑度越大，说明相邻节点的图信号有较大差异；而平滑度越小，说明相邻节点的图信号越相似。

当所有节点都正常工作时，节点上的图信号不仅在时间上平稳变化，在空间上相邻节点之间的图信号也随着时间平稳变化，因此图信号的平滑度小；而当存在异常节点时，图信号的平滑度将不可避免地增大。

2 异常节点检测方法

2.1 图频域

在无线传感器网络正常工作时，相邻传感器节点间的相似性也是平稳变化的，该相似性是指正常工作时相邻传感器采集数据之间差值的绝对值，所以图信号在频域具有低频特征。如果采集的数据有异常值存在，则会在频域出现高频分量。如图2 所示，分别绘制传感器在无异常节点和有多个（如1、3、5 个）异常节点时的频谱图。可以明显看出，在无异常值时图信号的频域只含有低频特征；而当有异常节点存在，可以看出其频域不仅含有高频分量，而且随着异常节点个数的增加高频分量也更加丰富。

图2 有/无异常节点的图信号频谱对比Fig. 2 Frequency spectrum comparison of graph signals with and without outlier nodes

2.2 图低通滤波器

图低通滤波器的设计如式（8）所示:

其中λcut为图滤波器截止频率。

在本文中选择图拉普拉斯矩阵特征值的中位数作为图滤波器截止频率。

2.3 平滑程度准则

首先对图信号进行低通滤波，得到低通滤波后的图信号为:

计算低通滤波后图信号的平滑度，即:

图3 表示低通滤波前后有、无异常节点图信号的对比。无异常节点时，相邻节点间的信号值相近，图信号具有低频特征，频率分量都在低频部分，因此无异常节点时图信号在低通滤波前后基本一致。当存在异常节点时，图信号的平滑度变化，出现较多的高频分量，此时异常节点存在时的图信号通过低通滤波后，其异常的高频部分被抑制，因此异常节点存在时图信号低通滤波前后将有较大的变化，这意味着其平滑度会有较大的变化。

图3 低通滤波前后有、无异常节点的图信号对比Fig. 3 Comparison of graph signals with and without outlier nodes before and after low-pass filtering

基于以上分析，设计如式（11）所示的平滑程度判决准则η:

其中:H0表示不存在异常节点，H1表示存在异常节点，γ表示判决门限。

2.4 确定判决门限

图4 表示有、无异常节点的η的样本统计直方图，从图中箭头所指的局部放大部分可以看出η在有无异常节点时的分布情况。

图4 有、无异常节点的样本统计直方图Fig. 4 Sample statistical histogram with and without outlier nodes

结合有、无异常节点的η的样本统计，根据样本统计变量，选取有异常节点的最小值和无异常节点的最大值作为判决门限的取值区间，通过遍历判决门限区间上的每一个值计算相对应的准确率，将准确率最大时所对应的判决门限设为最佳判决门限。

3 实验仿真与分析

本文的所有数据处理及仿真均采用Matlab-2017b 软件进行。在美国主要城市日平均气温数据集（ftp://ftp.ncdc.noaa.gov/pub/data/gsod）［19］和 加 利 福 尼 亚 日 平 均PM2.5 数 据 集（https://www. epa. gov/outdoor-air-quality-data）［20］上分别进行仿真，并与文献［18］中基于图频域分析的方法进行受试者工作特征（Receiver Operating Characteristic，ROC）曲线对比。在ROC 曲线中，检测率作为Y轴，虚警率作为X轴，ROC 曲线上的每一个点表示相对应的判决门限。在虚警率相同的情况下检测率越高，表明对应算法的性能越好，此时虚警率与检测率相交的点即为该数据集下的最佳判决门限。

3.1 气温数据集

本文首先选取的是美国主要城市气温数据集，该数据集来源于美国国家气象局官方网站公开的美国主要城市2003年日平均气温数据集。在实验仿真中，随机选择该数据集下150 个主要城市365 天日平均气温数据。数据集范围从-19.9～99.9oF。首先根据传感器位置特征将节点与最近邻的6 个节点相连接建立6 近邻图信号模型。如图5 所示，图上的每个竖线代表每个传感器采集的信号值。

图5 美国主要城市2003年日平均气温网络拓扑Fig. 5 Network topology of daily average temperature of USA major cities in 2003

本文分别对2 种不同场景下的异常情况进行实验仿真。首先考虑单个节点异常，与文献［18］中模拟故障节点类似，每一次随机选择某一天单个传感器节点气温值偏离20°F 作为异常节点，为了体现所提算法在异常偏离值较小时具有更好的检测性能，同时仿真了气温值偏离10°F和15°F时的异常情况。第二种考虑多个节点异常，每次随机选择某一天多个（2%、3%、5%个）传感器节点作为异常节点，同时偏离10°F。两种情况下均进行50 000次仿真实验。

图6 显示在单个节点异常情况下偏离值不同时本文所提算法与图频域算法的ROC 曲线对比。从图中可以看出，单个节点异常偏离值越大，即数据集的方差越大时，其检测效率越高；反之，当异常偏离值较小，即数据集的方差较小时，其检测率较低。而且从图中明显看出在虚警率相同条件下，所提算法在单个节点异常偏离值为10°F 时的检测率高于图频域算法在异常偏离值为20°F 时的检测率。结果表明在虚警率相同时所提算法优于图频域算法，且当异常偏离值较小时所提算法相比图频域算法具有更高的检测性能。

图6 气温数据不同偏离值下的ROC曲线对比Fig. 6 Comparison of ROC curves with different temperature data deviations

图7所示为多个（2%、3%、5%个）节点异常情况下本文所提算法与图频域算法的ROC 曲线对比。从图中可看出随着异常节点数增多，两种算法的检测性能同时增大；但从图中虚线所指的局部放大图中可看出，在相同仿真条件下，所提算法检测率均高于图频域算法的检测率。

图7 气温数据多节点异常下的ROC曲线对比Fig. 7 Comparison of ROC curves of temperature data under multiple outlier nodes

3.2 PM2.5数据集

第2 个仿真实验数据采用美国环境保护局官方网站公开的加利福尼亚州监测站点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。两种情况均进行10 000次仿真实验。

图8 加利福尼亚2015年日平均PM2.5网络拓扑Fig. 8 Network topology of daily average PM2.5 of California in 2015

图9显示PM2.5数据集在单个节点异常情况下偏离值不同时本文所提算法与图频域算法的ROC 曲线对比。与气温数据集在单个节点异常情况下的仿真结果一样，数据集的方差越大，其检测率也越大。同样，在异常偏离值为5 μg/m3时其检测性能仍然高于频域算法在异常偏离程度为15 μg/m3时的检测性能。

图9 PM2.5数据不同偏离值下的ROC曲线对比Fig. 9 Comparison of ROC curves with different PM2.5 data deviations

图10 是PM2.5 数据集在多个（2%、3%、5%个）节点异常情况下本文所提算法与图频域算法的ROC 曲线对比图。从图中可以看出，异常节点数越多，两种算法的检测性能越好，但当虚警率相同时所提算法在相同仿真条件下仍然具有较高的检测性能。

对以上两种具有不同特征集的数据上分别进行实验仿真，结果表明在虚警率相同的情况下所提算法具有更好的检测性能。此外，可以看出在PM2.5 数据集上的检测性能略低于气温数据集，这是因为气温数据日变化幅度较大，导致数据集方差较大，使得整体的平滑度较低，而PM2.5 数据集日变化幅度较小，其方差较小，导致整体的平滑度较大，因此PM2.5 数据集的检测性能较低。但相比现有的图频域算法，本文所提算法仍具有较高的检测性能。

图10 PM2.5数据多节点异常下的ROC曲线对比Fig. 10 Comparison of ROC curves of PM2.5 data under multiple outlier nodes

4 结语

本文提出了一种基于图信号处理的无线传感器网络异常节点检测算法。利用传感器节点的顶点域平滑性与图频域低频特性联合分析方法计算低通滤波前后图信号的平滑度，建立平滑程度判决准则，实现对异常节点的存在性判断。在不同的数据集上分别进行实验仿真，结果表明，在虚警率相同时所提算法在相同仿真条件下均具有较高的检测率，同时，在单个节点异常偏离值较小时仍具有较好的检测性能。