無線傳感器網(wǎng)絡(luò)中基于模式頻繁度的異常檢測方法*

施曉斌，吳丹萍，程紅舉

(福州大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，福建 福州 350108)

0 引言

在WSN中，由于環(huán)境噪聲和感知器件誤差的影響，感知數(shù)據(jù)帶有一定的不確定性。軟件與硬件故障將導(dǎo)致不準確和不可靠讀數(shù)的出現(xiàn)。而事件的發(fā)生也將導(dǎo)致與正態(tài)分布明顯不同的觀測值的出現(xiàn)。那些特征與正態(tài)分布特征明顯不同的觀測值被稱為異常值[1]。異常值檢測，是基于某種措施來識別偏離其余數(shù)據(jù)模式的數(shù)據(jù)實例的過程，用于過濾噪聲數(shù)據(jù)，查找故障節(jié)點和發(fā)現(xiàn)用戶感興趣的事件。

區(qū)分異常值的來源是一個重要的問題。一般來說，如果檢測到的異常值是錯誤或噪聲數(shù)據(jù)，則應(yīng)將其從傳感數(shù)據(jù)中去除，以確保數(shù)據(jù)質(zhì)量和準確性，并避免通信負載造成的能耗。但是，若是事件造成的異常值，消除異常值將導(dǎo)致關(guān)于事件的重要隱藏信息的丟失[2]。

傳統(tǒng)的集中式異常檢測技術(shù)將會產(chǎn)生巨大的能量和帶寬的消耗，這對資源受限的WSN網(wǎng)絡(luò)來說并不友好[3]。此外事件在網(wǎng)絡(luò)中發(fā)生的概率通常不高，在沒有發(fā)生事件的情況下收集到的數(shù)據(jù)價值是十分有限的?？紤]到節(jié)點有限的資源，因此需要限制異常檢測算法的復(fù)雜度，盡可能設(shè)計輕量級的分布式在線算法[4]。

本文考慮以下問題：如何以在線和分布式的方式快速準確地檢測WSN中的異常數(shù)據(jù)，并區(qū)分異常值的來源。本文研究了流數(shù)據(jù)的數(shù)據(jù)變化模式和數(shù)據(jù)的空間相關(guān)性在異常檢測問題上的運用，提出了一種基于數(shù)據(jù)變化模式頻繁度和空間相關(guān)性的PFSC(Pattern Frequency and Spatial Correlation)異常檢測方法。PFSC異常檢測方法分兩個階段進行。第一階段，為數(shù)據(jù)創(chuàng)建一個分布模型，根據(jù)數(shù)據(jù)變化模式的頻繁程度篩選出潛在的異常數(shù)據(jù)；第二階段，利用相鄰節(jié)點數(shù)據(jù)間的空間相關(guān)性來區(qū)分異常值的來源，此處本文通過拉依達準則完成異常值來源的判定。

1 相關(guān)工作

針對WSN中集中式與分布式異常檢測方法的研究，Lau等人[5]提出了一種基于名為CNBD的樸素貝葉斯框架的集中算法，其中端到端傳輸時間在sink處收集，并使用樸素貝葉斯框架進行分析。Subramaniam等[6]提出了一種用于傳感器網(wǎng)絡(luò)的分布式在線異常值檢測技術(shù)，以分布式方式計算多維數(shù)據(jù)分布近似的框架，以便在資源有限的傳感器網(wǎng)絡(luò)中實現(xiàn)復(fù)雜的應(yīng)用。Xu等人[7]通過比較連續(xù)時間實例的數(shù)據(jù)，得出是否存在瞬時故障的結(jié)論。如果存在瞬態(tài)故障，則使用其標記為正常的實例數(shù)據(jù)來校正數(shù)據(jù)。文獻[8]提出了一種基于信譽的投票和決策樹的分布式事件檢測方法，并評估了用于早期發(fā)現(xiàn)災(zāi)害特別是住宅火災(zāi)的性能和適用性。

針對在線數(shù)據(jù)連續(xù)積累、實時更新的特點，文獻[9]提出了一種環(huán)境數(shù)據(jù)流偏離歷史模式的識別方法。該方法是基于數(shù)據(jù)流及其預(yù)測區(qū)間的自回歸數(shù)據(jù)驅(qū)動模型。文獻[10]將基于聚類的算法和最近鄰異常值檢測方法相結(jié)合，用于實現(xiàn)高效聚類和對異常值檢測，訓(xùn)練階段需要對一段時間內(nèi)的觀測值進行聚類。文獻[11]提出了一種基于距離相似性的技術(shù)來識別傳感器網(wǎng)絡(luò)中的全局異常值。該技術(shù)嘗試通過相鄰節(jié)點之間的一組代表性數(shù)據(jù)交換來減少通信開銷。每個節(jié)點使用距離相似度來本地識別異常值，然后將離群值廣播到相鄰節(jié)點進行驗證。相鄰節(jié)點重復(fù)該過程，直到網(wǎng)絡(luò)中的整個傳感器節(jié)點最終同意全局異常值。然而廣播帶來的通信開銷使其無法應(yīng)用到大型網(wǎng)絡(luò)。

2 網(wǎng)絡(luò)模型與相關(guān)知識

2.1 網(wǎng)絡(luò)模型

WSN由隨機部署在一個平面區(qū)域上的一組傳感器節(jié)點S={s1,s2, …,sn}組成。節(jié)點i通信范圍內(nèi)的鄰居節(jié)點用Si={s1,s2, …,sk}表示。節(jié)點i在時刻t的觀測值表示為xi(t)，xmax表示有效的節(jié)點觀測值最大值，xmin為有效的節(jié)點觀測值最小值，節(jié)點i到n時刻為止的觀測值集合以Xi(n)表示，即Xi(n)={xi(1),xi(2), …,xi(n)}。

本文假設(shè)指定區(qū)域內(nèi)節(jié)點密度較高(如小型家居系統(tǒng))，當一個事件發(fā)生時，多個臨近事件發(fā)生地的節(jié)點都將及時地捕獲到該事件。

定義1數(shù)據(jù)變化模式：節(jié)點i在t時刻的數(shù)據(jù)變化模式Δxi(t)與上一時刻的觀測值相關(guān)，Δxi(t)=│xi(t)-xi(t-1)│，Δxi(t)∈D，其中D為區(qū)間[0,xmax-xmin]。不失一般性，本文將數(shù)據(jù)變化模式簡稱為模式。

ΔXi(n)表示節(jié)點i從2時刻到n時刻為止所有數(shù)據(jù)變化模式的集合，即:

ΔXi(n)={Δxi(2),Δxi(3), …, Δxi(n)}

其中│ΔXi(n)│=n-1。

定義2模式區(qū)間：D為區(qū)間[0,xmax-xmin]，將D均勻地劃分為若干區(qū)間{d1,d2, …,dk}，稱為模式區(qū)間，ΔXi(n)中任意的一個數(shù)據(jù)變化模式在D的某一個模式區(qū)間內(nèi)。

定義3區(qū)間頻繁度：在節(jié)點的數(shù)據(jù)變化模式集合ΔXi(n)= {Δxi(2),Δxi(3), …, Δxi(n)}中，屬于模式區(qū)間dj的模式的個數(shù)記為V(j)，則稱P(j)=V(j)/(n-1)為模式區(qū)間dj的頻繁度。

2.2 相關(guān)知識

2.2.1數(shù)據(jù)異常

根據(jù)本地節(jié)點異常的原因?qū)Ξ惓＿M行分類，有點異常、上下文異常與集體異常三類[12]。

(1)點異常：相對于數(shù)據(jù)集被認為是異常的單個數(shù)據(jù)實例。

(2)上下文異常：在當前上下文中被認為是異常的數(shù)據(jù)實例。在不同的上下文中，相同的數(shù)據(jù)實例可能被認為是正常的。

(3)集合異常：連續(xù)多個測量值為常數(shù)，即在一段時間內(nèi)測量值幾乎沒有什么波動。

圖1 異常類型

圖1顯示了Chandola等人定義的異常[12]。在時段24發(fā)生點異常，即數(shù)據(jù)實例對于整個數(shù)據(jù)集是異常的。在時段43出現(xiàn)上下文異常，但是如果該觀測值出現(xiàn)在時刻t1，t2，t3或t4，則不會被認為是異常的。最后，集合異常發(fā)生在時間段54～71，節(jié)點由于故障在該時段內(nèi)連續(xù)出現(xiàn)多個幾乎沒有什么波動的觀測值。本文將上下文異常視為點異常的一種特例。

2.2.2WSN中數(shù)據(jù)空間相關(guān)性

在WSN中，數(shù)據(jù)實例之間經(jīng)常存在相對位置關(guān)系，這樣的數(shù)據(jù)稱為空時數(shù)據(jù)(spatio temporal dam)。在進行異常檢測時，常常利用數(shù)據(jù)的空間相關(guān)特性區(qū)分節(jié)點故障和事件。由于組成事件的感知數(shù)據(jù)之間具有較強的時空關(guān)聯(lián)性，當事件發(fā)生時，臨近節(jié)點將擁有相似的觀測值，這是因為基于噪聲測量與傳感器故障可能隨機無關(guān)，而事件測量可能在空間上相關(guān)的事實。這一觀察使我們能夠區(qū)分事件和錯誤。例如，對Intel室內(nèi)項目[13]的數(shù)據(jù)進行空間相關(guān)性的分析。圖2給出了兩個鄰近的節(jié)點(節(jié)點4，6)和一個非臨近節(jié)點(節(jié)點24)的溫度隨時間變化的趨勢圖?？梢悦黠@地看出4,6節(jié)點彼此鄰近，其同一時刻的觀測值更加接近。在空間上彼此鄰近的鄰居節(jié)點的數(shù)據(jù)具有一定程度的相似性。

圖2 節(jié)點溫度變化趨勢圖

3 異常檢測算法

數(shù)據(jù)的變化模式由節(jié)點上連續(xù)觀測值的差值構(gòu)成。本文異常檢測方法的思想是將數(shù)據(jù)流的數(shù)據(jù)變化模式映射到某個特征空間的分區(qū)中，將非頻繁出現(xiàn)的分區(qū)認為是異常分區(qū)，頻繁出現(xiàn)的分區(qū)認為是正常分區(qū)。若某時刻數(shù)據(jù)的變化模式映射到特征空間的異常分區(qū)，則將該時刻的數(shù)據(jù)當做潛在異常值，并利用相鄰節(jié)點數(shù)據(jù)的空間相關(guān)性對其進行驗證。

該算法的目標是識別出潛在的異常觀測值并將其分類。在判斷異常觀測值產(chǎn)生的原因時，目標節(jié)點收集其鄰居節(jié)點集Si的當前時刻觀測值，并利用數(shù)據(jù)的空間相關(guān)性進行判斷，避免了將節(jié)點數(shù)據(jù)傳輸至Sink節(jié)點產(chǎn)生的大量能量消耗。PFSC方法是一個自學(xué)習(xí)-檢測的過程，可分為兩個階段，即第一階段為訓(xùn)練階段，第二階段為異常檢測階段。

3.1 數(shù)據(jù)變化模式

節(jié)點的數(shù)據(jù)流是按時間順序排列的一系列數(shù)據(jù)的集合，也稱為時間序列。在時間序列數(shù)據(jù)挖掘的研究中，通常用時間序列模式表示來描述原始的時間序列，即將原始時間序列映射到某個特征空間中，并用它在這個特征空間中的映像來描述原始序列。時間序列模式一定程度上保留了時間序列的主要特征，更能反應(yīng)時間序列的變化情況。分段線性表示(PLR)是將時間序列表示成多段相鄰的直線，用多段直線段擬合原時間序列，時間序列Xi(n)的PLR模型表示為：

Xi(n)={xi(1),xi(2),…,xi(n)}

L(Xi(n))={L(y1,y2),L(y2,y3),…,L(yk-1,yk)}

(1)

式中，yj∈Xi(n)，L(yj,y(j+1))表示連接兩點的直線段。

在此基礎(chǔ)上，本文將PLR中的線段長度壓縮為1，分段數(shù)量設(shè)置為n-1，同時用│y(j+1)-yj│來描述分段L(yj,y(j+1))的特征，得到Xi(n)的數(shù)據(jù)變化模式：

H(Xi(n))={Δxi(2),Δxi(3),…,Δxi(n)}

(2)

數(shù)據(jù)變化模式一定程度上保留了時間序列在各個時刻的數(shù)據(jù)變化情況。通常在正常的工作環(huán)境下，節(jié)點的讀數(shù)在連續(xù)的時間內(nèi)是漸變的過程，而異常觀測值與正常值存在明顯的差異，并且在節(jié)點的工作過程中異常值出現(xiàn)的頻率通常遠低于正常數(shù)據(jù)。因此，若將數(shù)據(jù)變化模式映射到某個特征空間的分區(qū)中，數(shù)據(jù)流中正常數(shù)據(jù)的變化模式落在特征空間的高頻率分區(qū)，而異常值的變化模式相對處于低頻率分區(qū)。

3.2 訓(xùn)練階段

訓(xùn)練階段的思想是：在數(shù)據(jù)流中為數(shù)據(jù)變化模式集ΔXi(n)創(chuàng)建一個分布模型，即將數(shù)據(jù)變化模式映射到某個特征空間的分區(qū)中，確定非頻繁出現(xiàn)的分區(qū)。

數(shù)據(jù)變化模式Δxi(t)=│xi(t)-xi(t-1)│，其取值范圍為[0,xmax-xmin]，記為D。為了對數(shù)據(jù)流的模式創(chuàng)建一個分布模型，將每個采樣周期產(chǎn)生的模式映射到特征空間中，模式的取值范圍D= [0,xmax-xmin]被均勻地劃分為若干個模式區(qū)間{d1,d2, …,dk}。模式區(qū)間數(shù)量根據(jù)領(lǐng)域知識進行估計。每一個模式區(qū)間對應(yīng)D的一個小的取值范圍。

訓(xùn)練階段開始時，對每個采樣周期的模式判斷其在哪一個模式區(qū)間內(nèi)，該模式區(qū)間dj出現(xiàn)的次數(shù)V(j)加1。圖3給出了節(jié)點i在訓(xùn)練階段的操作過程。

圖3 節(jié)點i訓(xùn)練階段圖

圖3中，節(jié)點i的訓(xùn)練階段，在時刻4數(shù)據(jù)變化模式為Δxi(4)，判斷其屬于d2分區(qū)，V(2)加1。同理，節(jié)點進行下一個時刻數(shù)據(jù)變化模式Δxi(5)的映射，此時V(1)為2，該過程直至訓(xùn)練階段結(jié)束。

在訓(xùn)練階段結(jié)束時，對D中的模式區(qū)間統(tǒng)計其模式出現(xiàn)的次數(shù)，計算各個模式區(qū)間的頻繁度。

(3)

頻繁模式區(qū)間閾值為P，若P(j)

3.3 檢測階段

3.3.1異常識別

異常識別的任務(wù)是篩選出數(shù)據(jù)流中的潛在異常值。學(xué)習(xí)階段結(jié)束后可以獲取特種空間中非頻繁模式區(qū)間。在異常識別過程中，將目標數(shù)據(jù)映射到特種空間的分區(qū)中，如果該時刻數(shù)據(jù)的模式落在非頻繁模式區(qū)間，則將其當做潛在的異常值進行處理。映射過程與學(xué)習(xí)階段相似。

3.3.2異常分類

為了確認是否真的出現(xiàn)了異常并對異常進行分類，本文利用WSN數(shù)據(jù)的空間相關(guān)性進行驗證。當節(jié)點i產(chǎn)生一個潛在異常觀測值xi(t)時，該節(jié)點利用無線信道向其鄰節(jié)點Si= {s1,s2, …,sk}請求其t時刻的數(shù)據(jù)xj(t)，其中j∈Si。計算其鄰居節(jié)點xj(t)的平均值μ和標準差σ。根據(jù)拉依達準則，若

|xi(t)-μ|<δσ

(4)

則認為該節(jié)點觀測值與其鄰居節(jié)點觀測值狀態(tài)相一致，該異常觀測值是由事件引起的；若不滿足式(4)，則認為該節(jié)點觀測值與其鄰居節(jié)點觀測值狀態(tài)不一致，該異常觀測值是由節(jié)點軟、硬件故障或者環(huán)境等其他因素引起的錯誤數(shù)據(jù)。

δ的取值根據(jù)實際應(yīng)用確定。假設(shè)事件是一個Bernoulli過程，并且事件過程中，數(shù)據(jù)符合正態(tài)分布，將事件過程的數(shù)據(jù)化簡為符合正態(tài)分布的隨機變量：

=1-(Φ(δ)-Φ(-δ))

=2-2Φ(δ)

(5)

其中Φ(δ)為標準正態(tài)分布，當Φ(δ)>0.9時，p<0.1，查表可得當δ取大于1.29時，Φ(δ)>0.9。本文將在實驗中對拉依達系數(shù)δ的取值進行討論。

4 實驗

本文在MATLAB環(huán)境下采用Inter室內(nèi)實驗室項目[13]數(shù)據(jù)集來分析算法的性能。所采用的數(shù)據(jù)集的數(shù)據(jù)格式如表1所示。

表1 Inter室內(nèi)實驗室項目數(shù)據(jù)格式

4.1 評估指標

異常值檢測算法通常使用檢測率(召回率)、查準率和誤報率(虛警率)進行評估。為了定義這些度量，此處采用混淆矩陣，如表2所示。

表2 混淆矩陣

因此，檢測率(Detection rate)、查準率(Precision rate)和誤報率(False alarm rate)定義如下：

檢測率：Dr=TP/(TP+FN)

(6)

查準率：Pr=TP/(TP+FP)

(7)

誤報率：Fr=FP/(FP+TN)

(8)

4.2 算法性能

本文所提出的算法有兩個參數(shù)對算法的性能具有影響，分別為D的分區(qū)頻繁度閾值p和拉依達準則的系數(shù)δ。實驗分兩組進行，分別分析在設(shè)置不同的分區(qū)頻繁度閾值p和設(shè)置不同拉依達法則系數(shù)δ的情況下，PFSC算法的性能。

圖4展示了PFSC算法性能隨分區(qū)頻繁度閾值p變化趨勢圖。其中p增大時，PFSC算法的檢測率增大，而查準率減小，誤判率因查準率的減小而增大。這是因為當p取較大值時，算法在判斷潛在異常數(shù)據(jù)時不僅識別出實際異常值，同時將部分變化模式較大的正常數(shù)據(jù)也識別為潛在異常數(shù)據(jù)，導(dǎo)致算法在檢測率增大的同時查準率下降。當p取0.05時，PFSC算法檢測率為83.903%，準確率為73.589%，誤判率為1.581%，此時PFSC性能較好。

圖4 頻繁模式區(qū)間閾值實驗圖

圖5展示了不同拉依達準則系數(shù)δ對PFSC算法性能的影響。δ在1.5前后PFSC的檢測率呈現(xiàn)不同狀態(tài)，當δ大于1.5時，檢測率逐漸減小。圖中可以明顯看出，PFSC的準確率隨δ增大而增大，同時誤判率持續(xù)減小，這是因為拉依達準則系數(shù)δ控制錯誤數(shù)據(jù)的判定，δ越大說明異常數(shù)據(jù)越偏離其鄰居節(jié)點數(shù)據(jù)，它為錯誤數(shù)據(jù)的可能性越大。其中δ取1.5時，PFSC的檢測率為83.835%，準確率為74.093%，誤判率為1.54%。

圖5 拉依達準則系數(shù)δ實驗圖

從實驗結(jié)果可以看出，PFSC算法在p取0.05，δ取1.5時性能最好。

為判定數(shù)據(jù)不同程度的異常率對算法性能的影響，本文將比較PFSC算法與文獻[14]提出的基于小波的異常檢測算法(Wavelet Based Outlier Detection,WBOC)和文獻[15]提出的基于K最近鄰的KNN異常檢測算法在數(shù)據(jù)不同異常率下的性能。其中PFSC算法p取0.05，δ取1.5，WBOC誤差閾值取2，KNN誤差閾值取2。

實驗效果如圖6～圖7所示?？梢钥闯?，當節(jié)點采集的數(shù)據(jù)異常率從5%增大到20%時，三種算法的檢測率都呈下降趨勢。當異常率較大時，在PFSC與KNN算法中，目標節(jié)點因鄰居節(jié)點潛在的異常數(shù)據(jù)而影響本地異常值的判定，鄰居節(jié)點集Si中的異常數(shù)據(jù)越多，算法檢測率越低。其中PFSC算法的異常鑒定與KNN相似，其檢測率接近于KNN算法。在數(shù)據(jù)異常率為12.5%時，PFSC的檢測率為80.27%。

圖6 數(shù)據(jù)異常率對檢測率影響

圖7 數(shù)據(jù)異常率對誤報率影響

圖7展示，當節(jié)點產(chǎn)生5%到20%不同程度異常率的數(shù)據(jù)時，PFSC算法的誤判率維持在2.41%左右，相比于WBOC與KNN有更低的誤判率。

5 結(jié)論

本文研究了無線傳感器網(wǎng)絡(luò)中的異常值檢測問題。由于網(wǎng)絡(luò)的特殊特性和資源限制，本文提出了一種基于數(shù)據(jù)變化模式頻繁度與數(shù)據(jù)空間相關(guān)性的PFSC算法，并以在線和分布式的方式檢測異常。實驗表明，PFSC算法在檢測不同異常率的數(shù)據(jù)流時有較高的檢測率和較小的誤判率。

[1] MA L,GU X D, WANG B W. Correction of outliers in temperature time series based on sliding window prediction in meteorological sensor network[J]. Information, 2017, 8(2):60.

[2] GANGULY A R, GAMA J, OMITAOMU O A, et al. Knowledge discovery from sensor data[M]. Springer Berlin Heidelberg, 2010.

[3] RASSAM M A, ZAINAL A, MAAROF M A. Advancements of data anomaly detection research in wireless sensor networks: a survey and open issues[J]. Sensors, 2013, 13(8): 10087-10122.

[4] ZHANG Y. Observing the unobservable: distributed online outlier detection in wireless sensor networks[D]. Enschede: University of Twente, 2010.

[5] LAU B C P, MA E W M, CHOW T W S. Probabilistic fault detector for wireless sensornetwork[J]. Expert Systems with Applications, 2014, 41(8): 3703-3711.

[6] SUBRAMANIAM S, PALPANAS T, PAPADOPOULOS D, et al. Online outlier detection in sensor data using non-parametric models[C]//Proceedings of the 32nd International Conference on Very Large Data Bases, 2006: 187-198.

[7] XU X, GENG W, YANG G, et al. LEDFD: A low energy consumption distributed fault detection algorithm for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2014, 10(2): 714530.

[8] BAHREPOUR M, MERATNIA N, POEL M, et al. Distributed event detection in wireless sensor networks for disaster management[C]//Intelligent Networking and Collaborative Systems (INCOS), 2010 2nd International Conference on. IEEE, 2010: 507-512.

[9] HILL D J, MINSKER B S. Anomaly detection in streaming environmental sensor data: A data-driven modeling approach[J]. Environmental Modelling & Software, 2010, 25(9): 1014-1022.

[10] FAWZY A, MIKHTAR H M O, HEGAZY O. Outliers detection and classification in wireless sensor networks[J]. Egyptian Informatics Journal, 2013, 14(2): 157-164.

[11] BRANCH J W,GIANNELLA C, SZYMANSKI B, et al. In-network outlier detection in wireless sensor networks[J]. Knowledge and Information Systems, 2013, 34(1): 23-54.

[12] O′REILLY C, GLUHAK A, IMRAN M A, et al. Anomaly detection in wireless sensor networks in a non-stationary environment[J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 1413-1432.

[13] Intel. IntelLab data[EB/OL].(2004-××-××).http://www.select.cs. cmu.edu/data/labapp3/index.html.

[14] ZHUANG Y Z, CHEN L. In-network outlier cleaning for data collection in sensor networks[C]// Int′l VLDB Workshop on Clean Databases, Cleandb 2006.

[15] XIE M, HU J K, HAN S, et al. Scalable hypergrid k-NN-based online anomaly detection in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(8): 1661-1670.