WSN中基于超橢圓判決邊界的異常檢測的動態建模

方小明，劉艷梨

(江蘇安全技術職業學院 電氣工程學院，江蘇 徐州 232001)

0 引言

在有線感知基礎設施部署過于昂貴或不能實現的環境中，無線傳感器網絡(WSN，wireless sensor network)為監測和數據收集提供了一個成本高效的平臺[1-2]。WSN由一組節點構成，每個節點都配備一組感知設備。在每個節點上安裝不同的感知元件(如溫度和濕度傳感器)，使得WSN能夠收集大量多維的和相關的樣本。WSN的一個重要挑戰是檢測由周圍環境中感興趣的事件或節點故障引起的異常測量值。在節點上發現異常測量值，使得我們可以通過減少網絡上原始數據的通信，節省無線節點的有限資源。為了檢測異常，需要對節點的行為進行建模。

人們提出了各種數據挖掘方法來建立節點的行為模型。在分散式方法中，WSN中的每個節點都建立一個自身正常行為的局部模型，將局部模型的參數轉發到基站或簇頭，然后根據局部模型計算全局模型。近年來，人們提出了許多采用這種方法的不同數據建模方法。然而，這些模型大多為靜態模型，不能適應環境中的變化。此外，這些模型的準確性依賴于初始訓練周期的正確選擇。如果初始訓練周期不能很好地代表將來的測量值，模型就是失敗的。因此，重要的問題是如何持續學習非平穩環境中的行為模型，即如何檢測非平穩環境中的異常事件。

異常檢測是WSN中一個活躍的研究課題。在WSN中，異常檢測技術已應用于許多方面，包括入侵檢測、事件檢測和質量保證[3-5]。在這些應用中，有許多因素會影響異常檢測的使用，如傳感器的移動、環境條件(有利的或不利的)、環境的動態性和能量約束。因此，異常檢測技術在實際應用中的一個關鍵問題是如何將其推廣到具有動態變化的在線數據流中。

文獻[6]提出了一類支持向量機(SVM，support vector machine)模型來發現WSN數據中的異常現象。這種方法主要假設所有的訓練數據都可以在傳感器上獲得，并且訓練以批處理的方式進行。盡管這些方法可以為正常數據提供良好的決策邊界，但它們對于每個傳感器有很高的計算開銷；文獻[7]提出了一種基于長短期記憶網絡自編碼(LSTM-Autoencoder)的網絡流量異常檢測方法，將真實網絡流量從數據包和會話流級別兩方面提取數據特征，采用離散小波變換(DWT，discrete wavelet transform)分解原始特征向量得到更高維特征，用已訓練的LSTM-Autoencoder模型對訓練數據進行重構，通過分析重構誤差分布確定檢測閾值。該方法的主要缺點首先是訓練對數據中的噪聲敏感，其次很難理解是什么觸發了報告的異常；文獻[8-9]把超橢圓邊界用來建模系統的正常行為與批處理訓練。這種方法允許訓練數據中存在噪聲，并向用戶報告個別異常。然而，其超橢圓邊界是在一個訓練周期上計算的，而且要求節點在訓練期間將測量值保存在存儲器中，在訓練結束時所有的測量值以批處理方式處理。盡管這些方法在計算上是高效的，但它們不能適應環境中的變化，是一種靜態模型。作為比較，本文將這種方法稱為靜態數據捕獲異常檢測(SDCAD，static data capture anomaly detection)；文獻[10]提出了一種基于四分之一超球SVM算法的異常數據檢測方法，利用從傳感器節點中收集到的原始數據建立支持向量機預測模型，并結合粒子群算法找出最佳參數，然后利用最佳參數對原本的模型進行優化；文獻[11]提出了一種新的時間-空間-屬性單類超球面支持向量機來建模WSN中的異常事件檢測問題，并提出了在線和部分在線離群點檢測算法。但部分在線離群點算法在訓練和更新時需要大量的計算；文獻[12]提出了一種累積和(CS，cumulative sum)算法來檢測網絡異常。盡管基于CS的異常檢測算法計算效率高，但基于其閾值的檢測機制通常不能準確地建模正常行為；文獻[13]提出了數據流自回歸模型的迭代估計，并采用CS作為在線異常檢測；對于多維數據中的異常檢測是著名的批(子群)處理技術，它采用馬氏距離[9，14-15]進行異常檢測；文獻[16]提出了一種基于改進壓縮感知(CS，compressed sensing)重構算法和智能優化GM(1，1)的WSN異常檢測方法。首先通過建立雙層異質WSN異常檢測模型，并采用壓縮感知技術對上層觀測節點收集到的下層檢測節點溫度測量數據進行處理，同時結合溫度數據稀疏度未知特點，構造有效的稀疏矩陣和測量矩陣，并重新定義測量矩陣正交變換預處理策略，使得CS觀測字典滿足約束等距條件；其次，重新定義離散蜘蛛編碼方式，蜘蛛種群不斷協同進化，以獲得稀疏結果中非零元素的位置信息，利用最小二乘法得到非零元素的幅度信息，實現對未知數量檢測節點數據的精確重構，在此基礎上采用蜘蛛種群迭代進化得到優化后GM(1，1)的參數序列，通過檢測參數序列的相關閾值來判定節點是否發生異常；文獻[17]提出了一種基于傳感器網絡時間序列數據的檢測方法，方法利用傳感器采集的K個正常數據的中位數建立樞軸量，構造置信區間，并提出了一種計算數據區間差異度的方法來判斷發生異常的來源。實驗結果表明，該方法對傳感器網絡的異常數據檢測率保持在98%以上，誤報率保持在0.5%以下，具有一定的實用性；文獻[18]提出一種基于平衡迭代規約層次聚類(BIRCH，balanced iterative reducing and clustering using hierarchies)的WSN流量異常檢測方案。該方案在擴充流量特征維度的基礎上，利用BIRCH算法對流量特征進行聚類，并通過設計動態簇閾值和鄰居簇序號優化BIRCH聚類過程來提高算法的聚類質量和性能魯棒性。進一步設計了基于拐點的綜合判決機制，結合預測，聚類結果對流量進行異常檢測，以保證方案的檢測準確性；為了提高無線傳感網絡的魯棒性，針對目前的網絡漏洞檢測方法無法計算出相鄰節點的相對位置信息，存在無線傳感器網絡漏洞檢測誤差大的問題，文獻[19]提出了先利用覆蓋漏洞發現算法組建傳感器極點坐標，獲取最相近節點間位置信息，計算出任意節點被其最相近節點覆蓋的邊緣弧信息序列，然后得到對應傳感器節點間需要增加的新傳感器數量，從而實現無位置信息的無線傳感器網絡漏洞檢測方法；文獻[20]針對WSN中傳感器自身安全性低、檢測區域惡劣及資源受限造成節點采集數據異常的問題，提出了一種基于圖信號處理的WSN異常節點檢測算法。算法首先依據傳感器位置特征建立-近鄰圖信號模型，然后基于圖信號在低通濾波前后的平滑度之比構建統計檢驗量，最后通過統計檢驗量與判決門限實現異常節點存在性的判斷。通過在公開的氣溫數據集與PM2.5數據集上的仿真驗證結果表明，與基于圖頻域異常檢測算法相比，在單個節點異常情況相同條件下，所提出的算法檢測率提升了7個百分點。在多個節點異常情況相同條件下，其檢測率均達到98%，并且在網絡節點異常偏離值較小時仍具有較高的檢測率。

為了實現WSN中動態數據流環境的異常檢測，本文提出了一種迭代方法來建立超橢圓判決邊界，其中每個節點基于到當前時間為止的測量值來調整其超橢圓模型，本文將提出的這種方法稱為動態數據捕獲異常檢測(DDCAD，dynamic data capture anomaly detection)。當邊界參數變化較小時，DDCAD算法終止；同時，還提出了一種遺忘因子方法來提高模型在非平穩環境中的跟蹤能力；仿真實驗結果表明，提出的方法通過適應環境中的變化，在非平穩環境中比現有的批處理方法能夠獲得更高的準確性，更適合于實際應用。

1 動態數據流環境下的迭代超橢圓邊界算法

首先給出描述異常檢測超橢圓模型所需的定義。令Xk={x1，x2，…，xk}為一個WSN中的一個節點在時刻{t1，t2，…，tk}的前k個樣本，其中每個樣本是Rd中的一個d×1向量。向量中的每個元素表示由節點測量的感興趣的屬性，如溫度和相對濕度。Xk的樣本均值mk和樣本協方差Sk計算如下：

(1)

(2)

以具有協方差矩陣Sk的、以mk為中心的有效半徑t的超橢圓定義為：

(3)

超橢圓ek的邊界定義為：

(4)

定義1：將關于ek的單點一階異常定義為在其外面的任意數據向量x∈Rd，即對于ek來說：

(5)

已知節點在tk的樣本，要處理節點上的下一個樣本。在tk+1，我們記錄測量向量xk+1∈Rd。首先，用式(5)來測試xk+1，然后用它來增大ek。如果xk+1?ek，就聲明它是一個異常，并將它發送給基站進行進一步處理。特征矩陣迭代更新公式為：

(6)

(7)

我們采用S-1=I(其中I是單位陣)，而不采用從前幾個樣本獲得的估計值來初始化迭代方法，因為前幾個樣本通常會產生一個奇異的樣本協方差矩陣。

我們用正常和異常測量值來增大ek。假設大部分數據都是正常的，因此可以抵消用異常測量值進行更新的任何不希望的影響。然而，也可以設計更復雜的方法，以不同的方式處理異常。這時應考慮異常是否是環境中的正常變化(漂移)。這類分析需要額外的輸入來確定異常的類型。

圖1 DDCAD序列ek收斂到其最終狀態e818=es

2 采用遺忘因子的跟蹤能力

為了使DDCAD算法能夠跟蹤監測環境中的數據變化，我們為舊的測量值引入遺忘因子。通過引入遺忘因子0<λ2的樣本均值：

mk+1，λ=λmkλ+(1-λ)xk+1

(8)

對于k個樣本，采用指數遺忘因子λ的加權樣本協方差為：

(9)

首先要找到考慮遺忘因子的迭代協方差矩陣更新公式，然后得出特征矩陣的迭代更新公式。通過整理式(9)，可以基于上一步的協方差矩陣加上一個更新值，寫出k+1時刻的協方差矩陣的更新公式。式(10)為協方差矩陣的一步更新：

(10)

將式(10)中的mk+1替換為式(8)中mk+1可得：

(11)

為了計算特征矩陣的更新公式，我們用矩陣逆引理式(12)來求兩個矩陣的和的逆。假設E是可逆的且B是一個方陣。注意，在本文中，E是一個數，C和D是向量。將這個引理應用到式(11)中，經過重新整理，得到式(13)：

(B+CED)-1=B-1-B-1C(E-1+DB-1C)-1DB-1

(12)

(13)

把用式(8)和式(13)對ek的更新序列稱為遺忘因子DDCAD(FFDDCAD，forgetting factor DDCAD)。

圖2 采用FFDDCAD在每次更新后特征矩陣的特征值

2.1 采用滑動窗口的基準估計

為了限制FFDDCAD更新公式中k的增長，可以在大小為w的滑動窗口上采用FFDDCAD。為了提供比較基準，從窗口開始重新計算總體估計，以便在每次輸入后得到準確的FFDDCAD橢圓。對于在線算法來說，盡管這種方法的計算效率不高，但它提供了采用主動測量值的超橢圓邊界的精確值(即在滑動窗口中的測量值)，并用作基準，作為比較在計算中限制大k效應所提出的方法。

2.2 有效N跟蹤方法

在這種方法中，為了解決跟蹤k較大的問題，當k≥neff時，我們簡單地用不變的neff來代替式(13)中的k。其思想是在k≥neff后，分配給數據樣本的權重趨于0，即λk≌0，因此相應的樣本幾乎被完全遺忘。在本文中，取neff=3τ，其中τ=1/(1-λ)為具有指數遺忘因子λ的迭代算法的記憶范圍。基準方法和有效N跟蹤方法的示意如圖3所示。方框所示為在橢圓邊界計算中所考慮的樣本。在有效N跟蹤方法中，舊樣本的權重按指數下降。

1.英語中有些以a-為詞首的表語形容詞如asleep，awake，alive修飾名詞時須放在其所修飾的名詞后做后置定語。例如：

圖3 在樣本k和k+1的基準方法和有效N方法的示意圖

2.3 計算復雜度討論

在計算復雜度方面，SDCAD、DDCAD和FFDDCAD都需要對數據進行一次遍歷，所以它們的計算復雜度都隨n線性增長，有漸近復雜度O(nd2)；迭代方法(DDCAD和FFDDCAD)以在線處方式處理數據，具有恒定的存儲復雜度，而SDCAD方法的存儲需求隨n線性增長；采用有效N跟蹤的FFDDCAD準確性和效率使得其適合于在線流數據分析，特別是在WSN中。

3 仿真實驗

本節首先給出在評價不同方法時采用的數據集，然后比較提出的采用有效N方法和基準方法的FFDDCAD，并比較了兩種FFDDCAD方法在合成數據集上的檢測率和誤報率。在合成數據集中，將[-10 10]上的均勻噪聲隨機加入到1%的樣本中，并將這些樣本標記為異常，而其他剩余的樣本視為正常。另一種比較方法是基于與提出的基準方法的偏差而引入的，這種方法不需要標記數據集，因此允許采用實際的數據集進行比較。接下來，我們比較了FFDDCAD相比于SDCAD在異常檢測上的效果。最后，我們比較了本文提出的采用有效N方法的FFDDCAD與和文獻[13]中提出的變化檢測技術。

3.1 數據集

采用3個數據集來評價本文提出的異常檢測迭代模型，并將其與現有的靜態方法進行比較。第一個數據集(稱為DS1)由某院校物聯網研究實驗室的54個傳感器收集的測量數據構成；第二個數據集(稱為DS2)是從部署在某市城市道路之間的23個交通傳感器收集的數據；第三個數據集(稱為DS3)是由部署在某市小鎮的森林中的16個傳感站收集的數據。圖4為3個數據集的散點圖。

圖4 用于評價的數據集的散點圖

通過考慮具有不同正態分布N(∑1，μ1)和N(∑2，μ2)的M1和M2兩種模式的兩個合成數據集SDS1和SDS2如圖5所示。模式M1和M2的參數值如表1所示。M1為初始模式，M2為最終模式。M1的變換如下。

表1 用于生成合成數據集的兩個正態分布的參數

圖5 用于評價的合成數據集的散點圖

3.2 DDCAD的收斂性

運行第2節中提出的DDCAD方法，并將其與計算整個數據集的協方差矩陣和均值的批處理SDCAD方法[9]進行比較。采用焦距(兩個橢圓之間的距離的量度)來檢查DDCAD的最終橢圓邊界與SDCAD的距離有多近。焦距考慮了兩個橢圓的形狀和位置，結果如圖6所示。圖6中點構成的虛線橢圓為DDCAD得到的最終橢圓，實線構成的橢圓為采用SDCAD方法得到的最終橢圓；可以看到，DDCAD算法和SDCAD算法的最終結果非常相似，兩個最終橢圓之間的焦距即FD(en，ens)非常小，對于DS1為0.001 6，DS2為0.001 4，DS3為0.002 4。這些小的距離并沒有對最終的邊界產生視覺上的明顯影響。

圖6 采用DDCAD和SDCAD得到的最終橢圓邊界與相應的焦距

3.3 跟蹤能力的比較

為了比較提出的跟蹤方法，我們首先用合成數據集來比較所提出的異常檢測模型的準確性。對于基準方法，考慮300個樣本的窗口大小。同樣，neff設置為300個樣本。表2所示為兩種跟蹤方法的檢測率和誤報率，其中DR表示檢測率，FA表示誤報率。可見，有效N跟蹤方法具有與基準方法相當的準確性。這說明有效N跟蹤方法是基準方法的良好近似，neff可以代替跟蹤迭代公式中的k來當解決k變大時的不穩定性問題。

表2 不同跟蹤方法在合成數據集上的比較

3.4 異常檢測能力的比較

我們對兩個合成數據集SDS1和SDS2比較采用有效N跟蹤方法的FFDDCAD和文獻[9]提出的SDCAD方法，得到的檢測率和誤報率如表3所示。可見，在代表非平穩環境的這兩個數據集中，采用有效N跟蹤方法的FFDDCAD比批處理的SDCAD方法有更高的準確性。這是因為用于批處理學習的數據不是來自單個分布，所以正態性假設很弱，從而導致模型無法檢測異常。

表3 異常檢測能力的比較 %

3.5 數據流中的變化檢測

本節比較了本文提出的FFDDCAD方法與文獻[13]的方法用于數據流的在線異常檢測。在數據流分析中，通常采用動態預測模型和殘差分析(如CS)來檢測數據流中的變化或異常。為便于比較，我們不直接采用文獻[13]的方法，而是采用遞歸最小二乘(RLS，recursive least squares)迭代建立以濕度作為輸入(激勵信號)的溫度預測的自回歸各態歷經(ARX，autoregressive eXogenous)模型，階數為np=4，并對其殘差應用CS來發現數據流的變化。FFDDCAD的定義是發現單點異常，并且可以很容易地修改來檢測變化點。當FFDDCAD模型在數據流中發現na個連續的單點異常時，它可以發出變化信號。

由于在實際的數據集中缺乏基本的真實性，這使得很難解釋變化的點。因此，這里我們僅采用DS1和兩個合成數據集來比較兩種方法的結果。ARX/RLS和FFDDCAD在初始狀態時都視為是不準確的，因此，延遲采用這兩個模型對初始化后的前nd=50樣本進行異常檢測。注意，在每個變化點之后，模型重置回其初始狀態。

圖7為ARX/RLS方法和FFDDCAD方法對于數據流變化檢測的結果，加號表示變化點；可見，FFDDCAD方法和ARX/RLS方法對于DS1的性能是相當的，但采用FFDDCAD方法可以檢測到更多的變化點，表明FFDDCAD方法優于ARX/RLS方法；而對于SDS1，ARX/RLS方法不能發現模式之間的變化點，而FFDDCAD方法可以檢測到5個變化點；在SDS2中，FFDDCAD方法可以檢測所有模式變化，而ARX/RLS方法僅檢測到一個模式變化；總之，FFDDCAD方法對于數據流變化的檢測始終優于ARX/RLS方法。

圖7 ARX/RLS(左)與FFDDCAD(右)對于數據流分析和變化點檢測的比較

4 結束語

本文針對WSN中的異常檢測提出了一種迭代模型，其迭代性使得它更適合于流數據分析；此外，在模型中引入遺忘因子，使其適合于非平穩環境；評價表明，提出的方法可以密切跟蹤環境中的變化，在非平穩環境中能獲得比批處理方法更好的準確性。同時在數據流的異常檢測中，本文提出的采用遺忘因子的FFDDCAD可以更好地檢測環境中的變化，計算復雜度也比目前先進的方法更低。