基于图信号处理的无线网络异常节点检测方法

A Method for Detecting Abnormal Nodes in Wireless Networks Based on Graph Signal Processing

摘要: 无线网络中的异常节点会降低群里的通信性能，在传输数据时造成丢包或者错传等情况发生，大规模节点异常甚至会导致网络瘫痪。为此，提出基于图信号处理的无线网络异常节点检测方法。首先，根据网络各节点空间位置特征，计算邻近节点间的距离，再结合K–近邻原理搭建无线网络图信号模型，通过高通图滤波装置划分图信号高频区域；然后，采用拉普拉斯矩阵、傅里叶变换获取各子图频谱特征，通过傅里叶逆变换得出图频率各分量信号，使用箱型图统计算法求出子图正常节点信号两个极值，在这两个值范围内即为正常节点，超出此范围即为异常节点，经过判定、筛选确定异常节点位置，最终完成异常节点检测的任务。实验结果表明，该方法对无线网络异常节点的检测精度高，且检测运行时间开销较少。

Abstract: Abnormal nodes in wireless networks reduce communication performance within the group, causing packet loss or error transmission during data transmission, and large-scale node anomalies can even lead to network paralysis. Therefore, a wireless network anomaly node detection method based on graph signal processing is proposed. Firstly, based on the spatial location characteristics of each node in the network, the distance between adjacent nodes is calculated. Then, a wireless network graph signal model is constructed using the K-nearest neighbor principle, and the high-frequency region of the graph signal is divided through a high pass graph filtering device. Then, Laplacian matrix and Fourier transform are used to obtain the spectrum characteristics of each sub graph, and the component signals of the graph frequency are obtained through the inverse Fourier transform. The box chart statistical algorithm is used to calculate the two extreme values of the normal node signals of the sub graph. Within these two value ranges, it is considered a normal node, and beyond this range, it is considered an abnormal node. After judgment and filtering, the position of the abnormal node is determined, and the task of detecting abnormal nodes is ultimately completed. The experimental results show that this method has high detection accuracy for abnormal nodes in wireless networks, and the detection runtime is relatively low.

1. 引言

无线网络是处于不同位置下用于沟通主观感知与客观物理世界的桥梁，也是互联网信息提取与处理的关键支持技术，由若干个网络节点组成 [1] [2] 。在通信技术与电子技术发展的背景下，无线网络被推广使用到目标定位、核生化监测与工业生产等方面。但由于网络节点受造价成本及其存储容量、能量、运算能力、通信带宽的限制，且无线网络一般部署在恶劣、无人看守的环境下，当网络受到外界攻击或网络节点出现异常时，导致数据传输过程中出现丢包、错传等现象，进而降低网络通信性能，严重时还可能导致网络瘫痪。

随着无线网络规模越来越大、各类攻击行为越来越隐蔽，检测异常节点变得难上加难，为此，大量学者开始关注对异常节点检测方法的研究。李忠等人 [3] 采用图卷积神经网络建立异常节点检测模型，通过变分自编码装置得出正常节点特征，利用损失函数、邻接矩阵算出各节点特征值，将正常节点特征值作为判断依据，经过图卷积神经网络训练得出异常节点位置，完成检测任务；王兆堃等人 [4] 采用支持向量机搭建网络异常节点检测模型，通过随机近似函数与梯度下降算法完成模型求解，确定异常节点位置，检测出异常节点。

图卷积神经网络、支持向量机在无线网络异常节点检测取得一定成果，但这两个文献方法选用检测方法较为繁琐，增加检测环节难度，时效性较差，降低整个检测系统性能，为此，提出一种基于图信号处理的无线网络异常节点检测方法。采用加权矩阵、拉普拉斯矩阵等方法提取节点图信号特征，避免节点图信号提取时出现频谱包络，进而大大提升异常节点检测结果；使用箱型图统计算法确定异常节点检测阈值，此算法简单，检测分析用时极短，节省大量检测时间。经过实验证实了图信号处理方法优于图卷积神经网络、支持向量机文献方法。

2. 图信号处理下无线网络异常节点检测方法

2.1. 异常节点检测程序

图信号处理是一种借助图或者信号特征的数学分析方法，与典型数据信号相比，图信号处理能够将信号特征值投影在无线网络每个节点中，各节点代表此信号生成的空间位置，这大大降低异常节点检测难度。由此，采用图信号处理设计无线异常节点检测程序 [5] [6] ，整个流程如图1所示。

Figure 1. Abnormal node detection procedure

图1. 异常节点检测程序

图1中，无线网络异常节点检测主要分为两个部分，即节点处理与检测。其中，处理阶段主要由预处理与局部处理构成。预处理：运用高通图滤波装置对各节点图信号进行初步处理，得到网络图高频区域；局部处理：利用拉普拉斯矩阵、加权矩阵等算法进行深度处理，得出每个节点图频信号特征；检测环节：借助箱型图统计算法得出判定阈值，经过分析、筛选确定异常节点位置，进而发现异常节点。

2.2. 无线传感器图信号模型建立

在建立无线网络图信号模型时，按照各节点空间位置特征算出邻近节点之间的距离，借助K-近邻算法搭建无线网络图信号模型。一般将无线网络无向图用 $G=\left(V,E\right)$ 表示，这里的 $V=\left\{v_1,v_2,\cdots ,v_m\right\}$ 表示m个网络节点集，E表示连接节点边的集。无线网络图的结构借助拉普拉斯矩阵进行描述 [7] [8] ，即 $L=D-W$ ，其中 $D=diag\left\{d_q\right\}$ 表示图的度矩阵， $d_q$ 表示与q节点相连边的个数， $W=\left\{w_{qp}\right\}$ 表示图的加权矩阵， $w_{qp}$ 表示任意两个节点p、q相关程度，则有：

$w_{qp}=\frac{a_{qp}}{{\left(K_{qp}\right)}^2}$ (1)

其中， $a_{qp}$ 表示q与p相连接线， $K_{qp}$ 表示q与p之间的欧式距离，其计算方式如下：

$K_{qp}=\sqrt{{\left(x_q-x_p\right)}^2+{\left(y_q-y_p\right)}^2}$ (2)

其中， $\left(x_q,y_q\right)$ 表示q空间坐标； $\left(x_p,y_p\right)$ 表示p空间坐标。

通过公式(1)~公式(2)得出无线网络各节点相关性与距离，进而建立无线网络图信号模型。

2.3. 图信号的傅里叶变换

数字信号处理后进行函数 $f\left(t\right)$ 的傅里叶变换，过程如公式(3)所示。

$F\left(\omega \right)={\displaystyle {\int }_{R}f\left(t\right){\text{e}}^{-j\omega t}\text{d}t}$ (3)

其中，j表示虚数单位；t表示时间量； $\omega$ 表示频率；R表示一个常数矩阵；e表示频谱； ${\text{e}}^{-j\omega t}$ 表示拉普拉斯矩阵一维的特征函数，则有：

$-\Delta \left({\text{e}}^{-j\omega t}\right)=-\frac{\partial }{{\partial }^{2}t}{\text{e}}^{-j\omega t}={\left(\omega {\text{e}}^{-j\omega t}\right)}^2$ (4)

其中， $\partial$ 导数偏置项。

基于傅里叶变换原理，采用图拉普拉斯矩阵特征值和特征矢量描述无线网络图的傅里叶变换。已知图拉普拉斯矩阵L，将 $L=D-W$ 进行分解处理，即 $L=UB{U}^T$ ，得到其特征矢量矩阵 $\left[U\right]=\left[u_1,u_2,\cdots ,u_q,\cdots ,u_m\right]$ 及其特征值矩阵 $B=diag\left\{{\gamma }_q\right\}$ 。其中， ${\gamma }_q$ 表示图信号的频率， $u_q$ 表示 ${\gamma }_q$ 对应的图信号分量， $q=1,2,\cdots ,m$ ， $0\le {\gamma }_1\le {\gamma }_2\le \cdots \le {\gamma }_q\le \cdots \le {\gamma }_m$ ，T表示矩阵转换因子。则图信号F的傅里叶变换与逆变换过程为：

$F=U^{T}f$ (5)

$f=UF$ (6)

其中，f表示图频率。结合公式(4)可知， $\omega$ 的数值越大，图信号频率越大； ${\gamma }_q$ 同理，其特征值越大，所对应的频率也就越大。根据此原理判断无线传感器图信号模型中各节点情况。

2.4. 异常节点检测

2.4.1. 预处理

在检测无线传感器图信号模型中各节点异常时，应首先对图信号进行预处理，通常借助高通滤波方式完成预处理。由于无线网络邻近两个节点的信号值相差较小，为此，F只能展现出图低频部分的特征。但当无线网络中可能存在两个以上异常节点时，可能会影响F的平滑性，进而增大F的图高频分量，此区域就会出现频谱包络的情况，影响异常节点检测结果 [9] 。为此，先获取F的高频分量，即 $F_G=\left[f_1^G,f_2^G,\cdots ,f_M^G\right]$ 。该过程就是将F输入高通图滤波装置H中，经过处理得到高频图信号 $F_G$ ，如公式(7)所示。

$\begin{array}{l}H=\frac{D-W}{2}\\ F_G=H{U}^{T}f\end{array}$ (7)

经过高通图滤波装置处理后，发现有异常节点与没有异常节点的F频谱相比，其图高频分量部分存在较大差异。换句话说，当无线网络有异常节点的F通过H处理后，图信号的高频部分出现异常波峰，当未有异常节点F通过H后，则不会出现异常波峰。但如果无线网络节点个数较多时，分解图的拉普拉斯矩阵谱运算量较大且占用较多存储，影响无线网络F的傅里叶变换效率，由此在完成预处理后 $F_G$ 需要进行局部子图处理。

2.4.2. 高频图信号局域处理

高频图信号局域处理分为两个子部分。第一部分负责提取子图频谱特征，第二部分为了求解子图频率各分量信号。

第一部分：设定 $F_q^Z$ 表示 $G_q=\left\{V_q,E_q,W_q\right\}$ 的子图信号，将无线网络各节点也是子图中心节点和其邻近节点集组成 $G_q$ 的节点集，即 $V_q$ 。基于无线网络结构可知， $V_q\not\subset V$ ； $E_q$ 表示任意子图图信号模型中所有边，也就是子图中节点之间连接集，且符合 $E_q\not\subset E$ 。 $v_q^C$ 表示任意子图q的中心节点； $W_q=\left\{w_{qp}\right\}$ 表示 $G_q$ 与 $F_q^Z$ 对应的加权矩阵。按照 $W_q$ 结果即可获得子图的度矩阵 $D_q$ 及其拉普拉斯矩阵 $L_q$ ，求解过程如公式(8)、公式(9)所示。

$D_q=diag\left({\displaystyle {\sum }_{q=1}^{{}_m}{w}_q\left(m,q\right)}\right)$ (8)

$L_q=D_q-W_q$ (9)

每个子图的 $F_q^Z=\left[f_{q,1}^Z,f_{q,2}^Z,\cdots ,f_{q,O}^Z\right]$ 表示维度是 $m_q\times O$ 数据矩阵，当中 $m_q$ 用来描述中 $v_q^C$ 的 $G_q$ 中无线网络节点总数量，也即是 $\left|m_q\right|=\left|V_q\right|$ 。 $f_{q,o}^Z\left(o=1,2,\cdots ,O\right)$ 表示第o个采样时间点 $G_q$ 的子图数据矩阵。

通过以上环节，即可建立 $G_q$ 与 $F_q^Z$ ，将 $L_q$ 的特征值新型分解处理，获得一个关于 $L_q$ 的特征矩阵 $B_q=diag\left(\gamma \left(q,m_q\right)\right)$ 及其特征向量矩阵 $U_q=\left[u_{q,1},u_{q,2},\cdots ,u_{q,m_{q_s}},\cdots ,u_{q,m_q}\right]$ 。再根据公式(5)得出 $G_q$ 的图频谱矩阵 ${\hat{F}}_q^Z=\left[{\hat{f}}_{q,1}^Z,{\hat{f}}_{q,2}^Z,\cdots ,{\hat{f}}_{q,o}^Z,\cdots ,{\hat{f}}_{q,O}^Z\right]$ ，求解详细构成如公式(10)所示：

$\{\begin{array}{l}{L}_q=U_q{B}_q{U}_q^{-1}\\ {\hat{F}}_q^Z=U_q^{-1}{F}_q^Z\end{array}$ (10)

第二部分：求解每个子图频谱各分量的信号 ${\hat{F}}_q$ 。先求解 $G_q$ 的频率分量值 $m_{q,\max }$ ， $m_{q,\max }$ 即 $G_q$ 第O个时间点和历史时间点的频率分量差值最大图频率分量值，求解过程为：

$m_{q,\max }=\underset{m_{q_s}}{\arg \min }{\displaystyle \underset{o=1}{\overset{O-1}{\sum }}\left|{\hat{f}}_{q,O}^Z\left(m_{q_s}\right)-{\hat{f}}_{q,o}^Z\left(m_{q_s}\right)\right|}$ (11)

其中， ${\hat{f}}_{q,o}^Z={\left[{\hat{f}}_{q,o}^Z\left(1\right),{\hat{f}}_{q,o}^Z\left(2\right),\cdots ,{\hat{f}}_{q,o}^Z\left(m_{q_s}\right),\cdots ,{\hat{f}}_{q,o}^Z\left(m_q\right)\right]}^T$ 。求解 ${\hat{F}}_q^Z$ 在 $m_{q,\max }$ 的图频分量，即：

${\hat{u}}_{q,m_{q_s}}=\{\begin{array}{l}{u}_{q,m_{q_s}},m_{q_s}=m_{q,\max }\\ 0,m_{q_s}\ne m_{q,\max }\end{array}$ (12)

基于公式(6)获取 $F_q^Z$ 对应的 ${\hat{F}}_q^Z$ 在 $m_{q,\max }$ 上的 ${\hat{F}}_q$ ，运算过程为：

${\hat{F}}_q={\hat{U}}_q{\hat{F}}_q^Z$ (13)

其中， ${\hat{U}}_q=\left[{\hat{u}}_{q,1},{\hat{u}}_{q,2},\cdots ,{\hat{u}}_{q,m_{q_s}},{\hat{u}}_{q,m_q}\right]$ 。通过公式(13)确定各子图的图频谱各分量信号 ${\hat{F}}_q$ 。

2.5. 无线网络异常节点检测实现

(A) 阈值判定

对比每个自图信号分量 ${\hat{F}}_q=\left[{\hat{f}}_q\left(m_q,O\right)\right]$ 中各节点目前信号值和其历史时间点信号值差，将这些节点信号差值和作为阈值，也就是异常节点判据，从而确定疑似异常子图，同时将此图中心节点看作疑似异常网络节点 [10] 。

采用箱型图统计算法得出q子图 $m_q$ 节点的两个阈值极值，即 ${\delta }_{\min ,q}\left(m_q\right)$ 、 ${\delta }_{\max ,q}\left(m_q\right)$ 。

$\begin{array}{l}{\delta }_{\min ,q}\left(m_q\right)=Q_{1,q}\left(m_q\right)-\tau Q_{2,q}\left(m_q\right)+\tau Q_{1,q}\left(m_q\right)\\ {\delta }_{\max ,q}\left(m_q\right)=Q_{2,q}\left(m_q\right)+\tau Q_{2,q}\left(m_q\right)-\tau Q_{1,q}\left(m_q\right)\end{array}$ (14)

其中， $Q_{1,q}\left(m_q\right)$ 与 $Q_{2,q}\left(m_q\right)$ 分别描述q子图信号 $m_q$ 节点的信号集 ${\hat{f}}_q\left(m_q,O\right)$ 的下与上四分位数；超出 $\left[{\delta }_{\min ,q}\left(m_q\right),{\delta }_{\max ,q}\left(m_q\right)\right]$ 范围即为疑似异常节点。

判定筛选，若q子图有任意节点信号未在 $\left[{\delta }_{\min ,q}\left(m_q\right),{\delta }_{\max ,q}\left(m_q\right)\right]$ 范围内，表明此子图 $G_q$ 是疑似异常子图，提取其中心节点 $v_q$ ，将符合判定筛选条件的中心节点组成在一起，记作疑似异常节点集，用 $V_A$ 表示。

(B) 筛选分析

筛选 $V_A$ 与 $V_q$ 时，假设 $V_q\not\subset V_A$ ，代表 $V_q$ 中心节点为无线网络正常节点；假设 $V_q\subset V_A$ ，代表 $V_q$ 中心节点为无线网络异常节点。

通过阈值判定与筛选发现每个子图 $G_q$ 中异常节点位置，完成无线网络异常节点检测任务。

3. 实验过程与结果分析

为验证上述设计的基于图信号处理的无线网络异常节点检测方法的实际应用效果，设计如下实验。

3.1. 实验参数设定

实验设定采样间距2 s，实验时长为550 s，选用通信路由协议为DSR，无线网络范围为8 km × 10 km，节点移动模式为Random Way point Model，节点移动速率为Normal (8, 4)，节点总数量为220个，正常节点与异常节点数量分别为200个与20个，各节点分布情况如图2所示。

Figure 2. Schematic diagram of wireless network distribution

图2. 无线网络分布示意图

图2中，黑点表示无线网络正常节点，黑色五角星表示异常节点。

3.2. 异常检测性能分析

检出率是衡量异常节点检测性能关键指标之一，值越高表明此方法性能越好。以数据传输率角度，分析图信号处理方法与图卷积神经网络、支持向量机方法异常节点检测检出率变化情况，结果如图3所示。

Figure 3. Variation of anomalous node detection rate for the three methods

图3. 三种方法的异常节点检出率变化情况

通过图3可以明显看出，在数据传输速率为0~100 kbit/s时，三种方法的异常节点检出率随数据传输增加而增加，当数据传输率100 kbit/s之后，三种方法趋于平缓，这是因为提取异常节点特征集已趋于稳定，为此异常节点检出率处于稳定状态。从异常节点检出率变化曲线变化情况可知，图信号处理方法检测出及其接近理想检出率，由于所提方法采用高通滤波避免节点处理过程出现频谱包络，获取节点数据特征更加多且精准，基本上能将所有异常节点检测出现，进而得出检出率越高；图卷积神经网络的全连接模式过于冗余，异常节点检测过程可能遗漏一部分，得出检出率远小于所提方法；支持向量机方法对于小规模无线网络节点异常检测效率较好，对于大规模异常节点检测运算时，易出现维数灾难，进而降低检出率。由此，证实了所提方法异常检测性能良好。

为了进一步验证图信号处理方法性能，实验从网络作业时间角度进行验证，依旧选用图卷积神经网络、支持向量机方法作为对比方法，采用这三种方法进行异常节点检出率分析，结果如图4所示。

Figure 4. Transformation of detection rate under different operation time of wireless network

图4. 无线网络不同运行时间下检出率变换情况

图4中，随着无线网络运行时间增加，图信号处理方法异常节点检出率幅度变化极小，检测系统较为稳定，这是因为其能够根据K-近邻算法得出邻近两个网络节点相关性与距离，精准判断出异常节点在无线网络结构位置，进而保证异常节点检测出率的精度；图卷积神经网络、支持向量机方法由于异常与正常节点分类性能较差，易将正确节点当作异常节点，使得检测结果与实际情况存在一定偏差，进而得出异常检出率曲线波动较大。

3.3. 检测运行时间开销

运行时间是验证异常节点检测速度的关键指标。实验无线网络环境不变，从无线网络节点中随机选取10个异常节点，分别选用所提方法与图卷积神经网络、支持向量机方法进行检测运行时间开销对比，结果见表1所示。

Table 1. Comparison of detection runtime overhead by methods

表1. 各方法检测运行时间开销对比

通过表1可知，所提方法每次异常节点检测运行时间开销均小于图卷积神经网络、支持向量机方法检测运行时间开销，由于所提方法选用箱型图统计阈值判定方法简单，可大幅度降低异常节点判定难度，为此14 ms内即可完成10个异常节点检测任务。而图卷积神经网络、支持向量机方法分别至少需要62 ms、69 ms才能检测出10个异常节点，检测运行开销远大于所提方法。

4. 结论

为了解决无线网络异常检测精度低与运行时间开销大问题，研究一种基于图信号处理的无线网络异常节点检测方法。根据无线网络节点特征设计异常节点检测程序，采用K-近邻算法建立无线网络图信号模型，使用高通图滤波装置、加权矩阵等方法对图信号进行处理，得出子图频谱特征，使用拉普拉斯矩阵算出子图图频率各分量信号，利用箱型图统计算法确定异常节点判定阈值，经过分析、筛选确定异常节点位置，进而完成异常节点检测任务。实验从数据传输率、网络作业时间角度均证实了图信号处理方法检出率高，并能保证检测速度，可推广使用。