一種基于分層聚合的分布式異常數(shù)據(jù)檢測方案

許春杰,吳 蒙,楊立君

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

0 概述

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

2 基本模型

2.1 集中式方案

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

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

2.2 分布式方案

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

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

2.2.1 數(shù)據(jù)預處理

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

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

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

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

1.m,n = Dataset的行、列維數(shù)

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,不執(zhí)行合并操作,將簇摘要信息繼續(xù)向上傳遞,得到簇中心點相互之間的距離構成的矩陣,將矩陣中元素與w比較,如果dis(c1,c2)

步驟3將得到的簇摘要信息繼續(xù)逐層上傳直至網(wǎng)關節(jié)點,中間由父節(jié)點執(zhí)行簇合并算法,網(wǎng)關節(jié)點執(zhí)行2.2.4節(jié)中的異常簇檢測算法,計算距離當前聚類中心較近的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未發(fā)生合并 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 分布式方案全局異常數(shù)據(jù)檢測示意圖

2.3 復雜度和能耗分析

2.3.1 集中式方案

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

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

2.3.2 分布式方案

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

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

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

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

3 實驗仿真

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

3.1 高斯數(shù)據(jù)集實驗

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

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

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

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

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

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

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

基于數(shù)據(jù)總量以及聚類操作得到簇的數(shù)量,可以衡量HSCBD與A_HSCBD方案相對于集中式方案所能夠?qū)崿F(xiàn)的通信復雜度節(jié)省率,結(jié)果如圖6所示。由圖6可知,在高斯數(shù)據(jù)集中,本文方案比HSCBD方案能夠?qū)崿F(xiàn)更高的通信復雜度節(jié)省率。

圖6 2種方案的能量節(jié)省率(高斯數(shù)據(jù)集)

3.2 IBRL數(shù)據(jù)集實驗

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

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

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

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

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

3.3 結(jié)果分析

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

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

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

4 結(jié)束語

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