一種基于分層聚合的分布式異常數據檢測方案

許春杰,吳 蒙,楊立君

(南京郵電大學 a.計算機學院; b.通信與信息工程學院; c.物聯網學院,南京 210023)

0 概述

無線傳感器網絡(Wireless Sensor Network,WSN)是一種由許多傳感器設備組成的自組織網絡,其中傳感器節點以無線信道為媒介,通過多跳方式彼此連接。傳感器收集環境信息并將感知數據傳送回中央管理節點(即網關節點),以便進一步處理。目前,無線傳感器網絡已經在環境監測、軍事、救援、醫療保健等諸多領域得到廣泛的應用[1]。

傳感器節點是一種微型嵌入式設備,在環境監測、智能交通等系統中起到關鍵性作用。但是在實際應用中,傳感器節點在功率、帶寬和計算能力方面存在不足[2-4],這些固有局限性可能使網絡更容易發生故障或遭受惡意程序的攻擊[5-6]。數據中的異常或異常值通常被定義為與數據集其余部分不一致的表現行為[7],可以通過分析網絡中的傳感器感知數據或與流量有關的屬性來識別網絡中的不正當行為。

傳感器網絡中絕大部分能量消耗來自于節點間彼此的通信而非計算[8],例如在Sensoria傳感器中,通信和計算能耗之間的比值約為103～104。因此,異常數據檢測的關鍵是將計算過程分布到各個子級節點,最大限度地減少網絡中的通信需求。集中式異常檢測方法需要將大量的原始感知數據或者預處理數據傳送到指定的節點進行集中式處理,這將消耗傳感器網絡中的能量,從而減少網絡的壽命。針對該問題,本文提出一種基于分層聚合的分布式異常數據檢測方案,以期在保證檢測率的同時降低通信消耗。

1 相關工作

目前國內外已有的傳感器網絡異常檢測技術大致可分為基于密度的方法[9]、基于子空間[10]與相關性[11-13]的高維數據的孤立點檢測、支持向量機[14]、復制神經網絡[15]、基于聚類分析的孤立點檢測[16]以及與關聯規則和頻繁項集的偏差。

根據可用數據背景知識的類型,異常檢測機制又可分為3類方法[6]。第1類方法不需要先驗知識就能發現異常值,該方法一般使用聚類或者無監督學習方法。第2類是監督式異常檢測,此方法需要一個所含數據已經被明確標記為正常值或者異常值的數據集。通過監督訓練,訓練有素的分類器能夠獲得將新數據分類為正常或異常的能力。第3類方法是半監督異常檢測方法。

數據聚類[17]是找到相似數據點簇的過程,聚類的結果能夠使得每組數據點被較好的分離。基于數據聚類的異常檢測基本是先將數據聚類,然后使用簇執行異常檢測。

為了檢測無線傳感器網絡中的路由攻擊,文獻[18]提出一種基于聚類的方案。在該方案中,每個傳感器節點監視其接收到的路由消息,每個特征向量可由多維特征空間中的一個特征點表示,攻擊流量在特征空間中會表現出異常。

文獻[19]設計一種名為LogCluster的基于聚類的異常檢測方案來識別在線系統問題。LogCluster方案由知識庫初始化階段和在線學習階段2個階段構成。知識庫初始化階段包含日志矢量化、日志聚類和代表性矢量提取3個步驟。在線學習階段可以用來調整在知識庫初始化階段構建的簇。

文獻[20]提出一種基于K-Means的無線傳感器網絡異常數據檢測方案,以歐式距離作為衡量數據間相似度的指標對感知數據進行聚類劃分,從而確定異常數據點。但是該方案將所有的計算消耗集中到網關節點中,網關節點能量消耗較大。

文獻[21-23]針對傳感器網絡提出一種基于多層聚合的分布式異常數據檢測技術,并構建一個具有分層拓撲的無線傳感器網絡模型。聚類算法采用最簡單的基于寬度的聚類,傳感器節點將簇的摘要合并信息發送到其各自的父節點,大幅縮減用于數據傳遞的能量消耗。但是該方案同樣存在參數難以確定的問題,而且隨著迭代的進行,會產生累計誤差。

本文提出一種基于分層聚合無線傳感器網絡的分布式異常數據檢測方案,基于K-Means++的數據聚類算法和K近鄰異常檢測方案對異常簇進行協作檢驗。該方案在節點級別識別異常數據向量,在網絡中只傳播能夠代表當前節點信息的摘要信息,執行簇合并算法以減少網絡通信開銷,同時由網關節點執行異常簇的檢測,將異常簇信息傳遞至各節點進行異常數據點檢測。

2 基本模型

2.1 集中式方案

檢測全局異常的最簡單方法是使用集中式方案。在集中式方案中,在時間窗口的最后,每個傳感器節點sj將其所有的感知數據發送給網關節點sg∈S。網關節點sg將其自身的數據Xg與收到的數據XR合并得到匯總數據X=XR∪Xg。集中式方案的聚類算法運行在數據集X上,得到一個簇的集合C={Cr:r=1,2,…,Nc}。基于固定寬度的聚類算法是一種較為簡單且常用的算法,歐式距離作為衡量數據向量間相似性的指標。在得到簇的集合后,在這些簇的集合數據中使用異常檢測算法即可識別出異常簇群。

由于集中式方案包括較高的通信費用和中心節點的處理時延等缺點,因此本文提出一種分布式異常檢測算法,通過將數據摘要逐層合并進行傳遞,極大地減少了信息傳遞所消耗的通信能量。

2.2 分布式方案

由于無線數據通信會使系統產生較大的開銷,對依靠電池供電的傳感器生命周期產生較重負擔,因此傳感器節點在轉發數據之前必須先對數據進行本地處理,以壓縮冗余,提高系統效率。圖1為分布式方案數據傳輸示意圖。

圖1 WSN中分布式異常檢測示意圖

2.2.1 數據預處理

2.2.2 基于K-Means++的聚類算法

算法1K-Means++聚類算法Cluster(Dataset,K)

輸入標準化的感知向量Dataset,聚類數K

輸出每個節點的簇的摘要Digest以及簇集C={Cr:r=1,2,…,Nc}

1.m,n = Dataset的行、列維數

2.centers[0]←Dataset中隨機向量

3.for i=1 to k do

4.sum_all = 0

5.for j=1 to m do

6.d[j]← 到聚類中心的最短距離

7.sum_all+=d[j]

8.sum_all*=w,w∈[0,1]

9.for j,di in enumerate(d) do

10.sum_all-=di

11.if sum_all>0 do

12.continue

13.endif

14.centers[i]=Dataset[j]

15.break

16.endfor

17.endfor

18.endfor

19.change=True

20.while change==True do

21.change=False,minIndex=-1

22.for i = 1 to m do

23.計算到各個聚類中心的最短距離

24.if subcenter[i,0]!=minIndex

25.change=True

26.endif

27.endfor

29.輸出簇的摘要Digest,簇集C={Cr:r=1,2,…,Nc}

2.2.3 簇群合并算法

步驟2若dis(c1,c2)≥w,不執行合并操作,將簇摘要信息繼續向上傳遞,得到簇中心點相互之間的距離構成的矩陣,將矩陣中元素與w比較,如果dis(c1,c2)

步驟3將得到的簇摘要信息繼續逐層上傳直至網關節點,中間由父節點執行簇合并算法,網關節點執行2.2.4節中的異常簇檢測算法,計算距離當前聚類中心較近的k個簇中心的加權距離平均值,與特定閾值進行比較,找到異常的簇。

算法2簇群合并算法MergeCluster(Cm)

輸入簇群C={Cr:r=1,2,…,Nc},合并閾值w

輸出合并后的簇集Cm

1.Cm←C

2.l=|Cm|

3.Cu←?(空集)

4.for r = 1 to Ncdo

5.if cr未發生合并 then

6.flag = false

7.for j=r+1 to Ncdo

8.if cjis not merged then

9.calculate Euclid(cr,cj)

10.if Dr≤w then

11.numv=numr+numj

13.calculate Dmax_v,

14.create cluster cv

15.Cu.append(cv)

16.Mark cr,cjas merged

17.flag = true

18.break

19.endif

20.endif

21.endfor

22.if flag==False then

23.Cu.append(cr)

24.endif

25.endif

26.endfor

27. if l>|Cu| then

28.MergeCluster(Cu)

29.endif

2.2.4 異常簇檢測算法

定義簇ci與其他簇的親近度為:

其中,k取0.3|C|,j為離i最近的k個簇中心標號。

將異常簇定義為:

Ca={Cβ∈C|Corrβ>AVG(Corr)+φ×SD(Corr)},φ的不同取值對應不同的置信度[22],本文取φ=1。

圖2 分布式方案全局異常數據檢測示意圖

2.3 復雜度和能耗分析

2.3.1 集中式方案

假設每個傳感器節點的感知數據個數相同,集中式方法在單個節點處需要O(np)的內存存儲感知數據,網關節點處需要O(snp)的內存空間。其中,s是網絡中的傳感器節點數量,p是感知數據維度,n是單個節點的感知數據數量。由于在集中式方案中,底層節點不參與計算,因此只有網關節點會產生計算開銷,在基于寬度的聚類算法中,算法的時間復雜度為O(snNc),異常簇檢測的時間復雜度為O(Nc2),故總體時間復雜度O(snNc+Nc2),其中,Nc

由于傳感器網中的能量消耗主要用于通信,因此此處只關注通信消耗,每個鏈路的通信復雜度是O(np)。

2.3.2 分布式方案

每個傳感器節點執行聚類算法,K-Means++聚類算法的時間復雜度為O(nkt),其中,k

每個節點需要上傳摘要信息,網關節點發現全局異常簇之后,將正常簇的摘要信息發送回節點。因此,每個鏈路的通信復雜度為O((k+1)(p+2))。

集中式與分布式異常檢測算法的時空復雜度以及通信費用消耗對比如表1所示。

表1 分布式與集中式方案復雜度及能耗分析

3 實驗仿真

本文實驗環境為Intel(R) Core(TM) i3-2370M CPU @2.40 GHz,Windows10操作系統,整個實驗基于Python2.7實現,分別在高斯數據集與IBRL數據集中進行測試。

3.1 高斯數據集實驗

人工構造高斯數據集,其包括2個特征向量溫度和濕度,每個特征向量均服從正態分布,該正態分布的均值隨機選自{0.30,0.35,0.45},標準差為0.03,給每個特征向量引入噪聲(異常),異常數據點服從[0.5,1.0]上的均勻分布。此高斯數據集由10個傳感器節點的數組組成,每個節點包含100個正常數據以及5個異常數據。數據需要先標準化到[0,1]區間以供使用。

檢測率(Detection Rate,DR)是指根據異常檢測算法檢測出的異常數據數量占實際異常數據總數的比例。誤報率(False Positive Rate,FPR)是指被算法誤判為異常值的正常數據數量占實際正常數據總數的比例。

HSCBD檢測方案[14]的檢測效果如圖3所示。由圖3可知,當w∈[0.005,0.018]時,該算法有較高的檢測率以及較低的誤報率。當w∈[0.03,0.04]時,異常數據點可能會被劃分到正常數據簇內,從而影響檢測效果,并且導致較高的誤報率。由此可知,HSCBD方案對w參數比較敏感。

圖3 HSCBD方案檢測效果(高斯數據集)

基于高斯數據集,利用控制單一變量法,實驗驗證本文方案A_HSCBD在不同聚類數量k時的檢測率,結果如圖4所示。由圖4可知,當k∈[13,15]時,本文方案同樣能夠實現較高的檢測率。當k=14時,檢測效果如圖5所示。由圖5可知,該方案的檢測效果與HSCBD相當。

圖4 A_HSCBD方案的檢測率(高斯數據集)

圖5 A_HSCBD方案檢測效果(k=14,高斯數據集)

基于數據總量以及聚類操作得到簇的數量,可以衡量HSCBD與A_HSCBD方案相對于集中式方案所能夠實現的通信復雜度節省率,結果如圖6所示。由圖6可知,在高斯數據集中,本文方案比HSCBD方案能夠實現更高的通信復雜度節省率。

圖6 2種方案的能量節省率(高斯數據集)

3.2 IBRL數據集實驗

IBRL數據集是在美國加利福尼亞州的因特爾伯克利實驗室中收集的數據集合。收集該數據的傳感器節點部署于室內環境,傳感器以31 s的時間間隔收集5個測量值:溫度,光強,相對濕度,電壓和拓撲信息。由于數據量巨大,本文只研究2004年3月1日0:00:00—03:59:59時間窗口內的數據。

圖7和圖8分別為HSCBD和A_HSCBD方案基于IBRL數據的仿真結果。可以看出,當k∈[0.013,0.015]時,A_HSCBD方案的檢測率為98%,與HSBCS方案的檢測率96%相比,提高了2個百分點,并且誤報率也處于較低水平。圖9為HSCBD與A_HSCBD方案相對于集中式方案的能量節省率的對比。由圖9可知,在IBRL數據集中,本文方案與HSCBD方案相比,能量節省率有了進一步提高。

圖7 HSCBD方案的檢測效果(IBRL數據集)

圖8 A_HSCBD方案的檢測效果(IBRL數據集)

圖9 HSCBD與A_HSCBD方案的能量節省率對比(IBRL數據集)

3.3 結果分析

為避免偶然性因素的影響,對2個數據集進行10次實驗,其平均檢測率如表2所示,可以看出,與集中式方案、HSCBD方案相比,本文方案檢測效率較高。

表2 3種方案10次平均檢測率對比

綜合分析可知,與集中式方案和HSCBD方案相比,本文方案具有較高的檢測效率和通信效率,但由于聚類算法k的確定需要一個學習過程,其時間復雜度較高。

4 結束語

本文提出一種針對無線傳感器網絡異常數據的分布式檢測方案。該方案在網絡中傳播能夠代表當前節點信息的摘要信息,執行簇合并算法以減少網絡通信開銷,同時由網關節點執行異常簇的檢測,將異常簇信息傳遞至各節點進行異常數據點檢測,從而區分單節點級別異常數據。仿真結果表明,與集中式方案及HSCBD方案相比,本文方案取得了更高的檢測效率并大幅降低了能量消耗。下一步將引入空間維度相似性對該方案進行改進。