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

許春杰,吳 蒙,楊立君

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

0 概述

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

2 基本模型

2.1 集中式方案

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

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

2.2 分布式方案

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

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

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

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

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

輸入標(biāo)準(zhǔn)化的感知向量Dataset,聚類數(shù)K

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

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

2.centers[0]←Dataset中隨機(jī)向量

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.計(jì)算到各個(gè)聚類中心的最短距離

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ù)向上傳遞,得到簇中心點(diǎn)相互之間的距離構(gòu)成的矩陣,將矩陣中元素與w比較,如果dis(c1,c2)

步驟3將得到的簇摘要信息繼續(xù)逐層上傳直至網(wǎng)關(guān)節(jié)點(diǎn),中間由父節(jié)點(diǎn)執(zhí)行簇合并算法,網(wǎng)關(guān)節(jié)點(diǎn)執(zhí)行2.2.4節(jié)中的異常簇檢測算法,計(jì)算距離當(dāng)前聚類中心較近的k個(gè)簇中心的加權(quán)距離平均值,與特定閾值進(jìn)行比較,找到異常的簇。

算法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個(gè)簇中心標(biāo)號。

將異常簇定義為:

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

圖2 分布式方案全局異常數(shù)據(jù)檢測示意圖

2.3 復(fù)雜度和能耗分析

2.3.1 集中式方案

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

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

2.3.2 分布式方案

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

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

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

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

3 實(shí)驗(yàn)仿真

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

3.1 高斯數(shù)據(jù)集實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

3.2 IBRL數(shù)據(jù)集實(shí)驗(yàn)

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

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

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

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

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

3.3 結(jié)果分析

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

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

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

4 結(jié)束語

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