基于圖信號處理的無線傳感器網絡異常節點檢測算法

盧光躍，周 亮*，呂少卿，施 聰，蘇可可

（1. 西安郵電大學通信與信息工程學院，西安710121； 2. 陜西省信息通信網絡及安全重點實驗室（西安郵電大學），西安710121）

（*通信作者電子郵箱zl2018zd@163.com）

0 引言

無線傳感器網絡是由大量靜態或動態的傳感器節點以自組織和多跳方式構成的一種分布式傳感網絡［1］。隨著無線通信和微電子技術的不斷創新，具有體積小、低成本和低功耗的傳感器節點被廣泛應用到醫療實時監測［2］、生態環境監測［3］、軍事戰場監視［4］等許多重要領域［5］。由于傳感器節點自身安全性低、資源受限、常處于惡劣的環境中且無人看護，使得節點極易受到來自外界和自身因素的影響而導致節點出現異常。如果異常信息未被檢測而加以分析，將會給決策帶來嚴重后果。同時，由于大規模非規則網絡結構的出現，使得對具有非規則網絡拓撲結構的無線傳感器網絡異常檢測成為研究的熱點。

異常值也被稱為離群值，是指節點自身故障、節點之間通信受阻及外界環境攻擊等原因造成采集數據顯著偏離正常模式下傳感器采集的值。目前，對于異常節點的檢測方法有許多種類型。基于統計學的方法［6］需要相應的先驗知識建立統計概率分布模型，在該模型的基礎上對數據的分布進行映射，通過它們和統計模型的擬合程度進行判決。如果準確獲得統計模型，該算法則可以有效檢測異常值；然而，在很多應用場景中，很難獲得傳感器分布的先驗參數?；诜诸惖漠惓z測算法［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 結語

本文提出了一種基于圖信號處理的無線傳感器網絡異常節點檢測算法。利用傳感器節點的頂點域平滑性與圖頻域低頻特性聯合分析方法計算低通濾波前后圖信號的平滑度，建立平滑程度判決準則，實現對異常節點的存在性判斷。在不同的數據集上分別進行實驗仿真，結果表明，在虛警率相同時所提算法在相同仿真條件下均具有較高的檢測率，同時，在單個節點異常偏離值較小時仍具有較好的檢測性能。