許春杰,吳 蒙,楊立君
(南京郵電大學(xué) a.計(jì)算機(jī)學(xué)院; b.通信與信息工程學(xué)院; c.物聯(lián)網(wǎng)學(xué)院,南京 210023)
無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是一種由許多傳感器設(shè)備組成的自組織網(wǎng)絡(luò),其中傳感器節(jié)點(diǎn)以無(wú)線(xiàn)信道為媒介,通過(guò)多跳方式彼此連接。傳感器收集環(huán)境信息并將感知數(shù)據(jù)傳送回中央管理節(jié)點(diǎn)(即網(wǎng)關(guān)節(jié)點(diǎn)),以便進(jìn)一步處理。目前,無(wú)線(xiàn)傳感器網(wǎng)絡(luò)已經(jīng)在環(huán)境監(jiān)測(cè)、軍事、救援、醫(yī)療保健等諸多領(lǐng)域得到廣泛的應(yīng)用[1]。
傳感器節(jié)點(diǎn)是一種微型嵌入式設(shè)備,在環(huán)境監(jiān)測(cè)、智能交通等系統(tǒng)中起到關(guān)鍵性作用。但是在實(shí)際應(yīng)用中,傳感器節(jié)點(diǎn)在功率、帶寬和計(jì)算能力方面存在不足[2-4],這些固有局限性可能使網(wǎng)絡(luò)更容易發(fā)生故障或遭受惡意程序的攻擊[5-6]。數(shù)據(jù)中的異?;虍惓V低ǔ1欢x為與數(shù)據(jù)集其余部分不一致的表現(xiàn)行為[7],可以通過(guò)分析網(wǎng)絡(luò)中的傳感器感知數(shù)據(jù)或與流量有關(guān)的屬性來(lái)識(shí)別網(wǎng)絡(luò)中的不正當(dāng)行為。
傳感器網(wǎng)絡(luò)中絕大部分能量消耗來(lái)自于節(jié)點(diǎn)間彼此的通信而非計(jì)算[8],例如在Sensoria傳感器中,通信和計(jì)算能耗之間的比值約為103~104。因此,異常數(shù)據(jù)檢測(cè)的關(guān)鍵是將計(jì)算過(guò)程分布到各個(gè)子級(jí)節(jié)點(diǎn),最大限度地減少網(wǎng)絡(luò)中的通信需求。集中式異常檢測(cè)方法需要將大量的原始感知數(shù)據(jù)或者預(yù)處理數(shù)據(jù)傳送到指定的節(jié)點(diǎn)進(jìn)行集中式處理,這將消耗傳感器網(wǎng)絡(luò)中的能量,從而減少網(wǎng)絡(luò)的壽命。針對(duì)該問(wèn)題,本文提出一種基于分層聚合的分布式異常數(shù)據(jù)檢測(cè)方案,以期在保證檢測(cè)率的同時(shí)降低通信消耗。
目前國(guó)內(nèi)外已有的傳感器網(wǎng)絡(luò)異常檢測(cè)技術(shù)大致可分為基于密度的方法[9]、基于子空間[10]與相關(guān)性[11-13]的高維數(shù)據(jù)的孤立點(diǎn)檢測(cè)、支持向量機(jī)[14]、復(fù)制神經(jīng)網(wǎng)絡(luò)[15]、基于聚類(lèi)分析的孤立點(diǎn)檢測(cè)[16]以及與關(guān)聯(lián)規(guī)則和頻繁項(xiàng)集的偏差。
根據(jù)可用數(shù)據(jù)背景知識(shí)的類(lèi)型,異常檢測(cè)機(jī)制又可分為3類(lèi)方法[6]。第1類(lèi)方法不需要先驗(yàn)知識(shí)就能發(fā)現(xiàn)異常值,該方法一般使用聚類(lèi)或者無(wú)監(jiān)督學(xué)習(xí)方法。第2類(lèi)是監(jiān)督式異常檢測(cè),此方法需要一個(gè)所含數(shù)據(jù)已經(jīng)被明確標(biāo)記為正常值或者異常值的數(shù)據(jù)集。通過(guò)監(jiān)督訓(xùn)練,訓(xùn)練有素的分類(lèi)器能夠獲得將新數(shù)據(jù)分類(lèi)為正?;虍惓5哪芰Α5?類(lèi)方法是半監(jiān)督異常檢測(cè)方法。
數(shù)據(jù)聚類(lèi)[17]是找到相似數(shù)據(jù)點(diǎn)簇的過(guò)程,聚類(lèi)的結(jié)果能夠使得每組數(shù)據(jù)點(diǎn)被較好的分離。基于數(shù)據(jù)聚類(lèi)的異常檢測(cè)基本是先將數(shù)據(jù)聚類(lèi),然后使用簇執(zhí)行異常檢測(cè)。
為了檢測(cè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的路由攻擊,文獻(xiàn)[18]提出一種基于聚類(lèi)的方案。在該方案中,每個(gè)傳感器節(jié)點(diǎn)監(jiān)視其接收到的路由消息,每個(gè)特征向量可由多維特征空間中的一個(gè)特征點(diǎn)表示,攻擊流量在特征空間中會(huì)表現(xiàn)出異常。
文獻(xiàn)[19]設(shè)計(jì)一種名為L(zhǎng)ogCluster的基于聚類(lèi)的異常檢測(cè)方案來(lái)識(shí)別在線(xiàn)系統(tǒng)問(wèn)題。LogCluster方案由知識(shí)庫(kù)初始化階段和在線(xiàn)學(xué)習(xí)階段2個(gè)階段構(gòu)成。知識(shí)庫(kù)初始化階段包含日志矢量化、日志聚類(lèi)和代表性矢量提取3個(gè)步驟。在線(xiàn)學(xué)習(xí)階段可以用來(lái)調(diào)整在知識(shí)庫(kù)初始化階段構(gòu)建的簇。
文獻(xiàn)[20]提出一種基于K-Means的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)異常數(shù)據(jù)檢測(cè)方案,以歐式距離作為衡量數(shù)據(jù)間相似度的指標(biāo)對(duì)感知數(shù)據(jù)進(jìn)行聚類(lèi)劃分,從而確定異常數(shù)據(jù)點(diǎn)。但是該方案將所有的計(jì)算消耗集中到網(wǎng)關(guān)節(jié)點(diǎn)中,網(wǎng)關(guān)節(jié)點(diǎn)能量消耗較大。
文獻(xiàn)[21-23]針對(duì)傳感器網(wǎng)絡(luò)提出一種基于多層聚合的分布式異常數(shù)據(jù)檢測(cè)技術(shù),并構(gòu)建一個(gè)具有分層拓?fù)涞臒o(wú)線(xiàn)傳感器網(wǎng)絡(luò)模型。聚類(lèi)算法采用最簡(jiǎn)單的基于寬度的聚類(lèi),傳感器節(jié)點(diǎn)將簇的摘要合并信息發(fā)送到其各自的父節(jié)點(diǎn),大幅縮減用于數(shù)據(jù)傳遞的能量消耗。但是該方案同樣存在參數(shù)難以確定的問(wèn)題,而且隨著迭代的進(jìn)行,會(huì)產(chǎn)生累計(jì)誤差。
本文提出一種基于分層聚合無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的分布式異常數(shù)據(jù)檢測(cè)方案,基于K-Means++的數(shù)據(jù)聚類(lèi)算法和K近鄰異常檢測(cè)方案對(duì)異常簇進(jìn)行協(xié)作檢驗(yàn)。該方案在節(jié)點(diǎn)級(jí)別識(shí)別異常數(shù)據(jù)向量,在網(wǎng)絡(luò)中只傳播能夠代表當(dāng)前節(jié)點(diǎn)信息的摘要信息,執(zhí)行簇合并算法以減少網(wǎng)絡(luò)通信開(kāi)銷(xiāo),同時(shí)由網(wǎng)關(guān)節(jié)點(diǎn)執(zhí)行異常簇的檢測(cè),將異常簇信息傳遞至各節(jié)點(diǎn)進(jìn)行異常數(shù)據(jù)點(diǎn)檢測(cè)。
檢測(cè)全局異常的最簡(jiǎn)單方法是使用集中式方案。在集中式方案中,在時(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。集中式方案的聚類(lèi)算法運(yùn)行在數(shù)據(jù)集X上,得到一個(gè)簇的集合C={Cr:r=1,2,…,Nc}?;诠潭▽挾鹊木垲?lèi)算法是一種較為簡(jiǎn)單且常用的算法,歐式距離作為衡量數(shù)據(jù)向量間相似性的指標(biāo)。在得到簇的集合后,在這些簇的集合數(shù)據(jù)中使用異常檢測(cè)算法即可識(shí)別出異常簇群。
由于集中式方案包括較高的通信費(fèi)用和中心節(jié)點(diǎn)的處理時(shí)延等缺點(diǎn),因此本文提出一種分布式異常檢測(cè)算法,通過(guò)將數(shù)據(jù)摘要逐層合并進(jìn)行傳遞,極大地減少了信息傳遞所消耗的通信能量。
由于無(wú)線(xiàn)數(shù)據(jù)通信會(huì)使系統(tǒng)產(chǎn)生較大的開(kāi)銷(xiāo),對(duì)依靠電池供電的傳感器生命周期產(chǎn)生較重負(fù)擔(dān),因此傳感器節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)之前必須先對(duì)數(shù)據(jù)進(jìn)行本地處理,以壓縮冗余,提高系統(tǒng)效率。圖1為分布式方案數(shù)據(jù)傳輸示意圖。
圖1 WSN中分布式異常檢測(cè)示意圖
2.2.1 數(shù)據(jù)預(yù)處理
2.2.2 基于K-Means++的聚類(lèi)算法
算法1K-Means++聚類(lèi)算法Cluster(Dataset,K)
輸入標(biāo)準(zhǔn)化的感知向量Dataset,聚類(lèi)數(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]← 到聚類(lèi)中心的最短距離
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è)聚類(lèi)中心的最短距離
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é)中的異常簇檢測(cè)算法,計(jì)算距離當(dāng)前聚類(lèi)中心較近的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 異常簇檢測(cè)算法 定義簇ci與其他簇的親近度為: 其中,k取0.3|C|,j為離i最近的k個(gè)簇中心標(biāo)號(hào)。 將異常簇定義為: Ca={Cβ∈C|Corrβ>AVG(Corr)+φ×SD(Corr)},φ的不同取值對(duì)應(yīng)不同的置信度[22],本文取φ=1。 圖2 分布式方案全局異常數(shù)據(jù)檢測(cè)示意圖 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ì)算開(kāi)銷(xiāo),在基于寬度的聚類(lèi)算法中,算法的時(shí)間復(fù)雜度為O(snNc),異常簇檢測(cè)的時(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í)行聚類(lèi)算法,K-Means++聚類(lèi)算法的時(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))。 集中式與分布式異常檢測(cè)算法的時(shí)空復(fù)雜度以及通信費(fèi)用消耗對(duì)比如表1所示。 表1 分布式與集中式方案復(fù)雜度及能耗分析 本文實(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)行測(cè)試。 人工構(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ū)間以供使用。 檢測(cè)率(Detection Rate,DR)是指根據(jù)異常檢測(cè)算法檢測(cè)出的異常數(shù)據(jù)數(shù)量占實(shí)際異常數(shù)據(jù)總數(shù)的比例。誤報(bào)率(False Positive Rate,FPR)是指被算法誤判為異常值的正常數(shù)據(jù)數(shù)量占實(shí)際正常數(shù)據(jù)總數(shù)的比例。 HSCBD檢測(cè)方案[14]的檢測(cè)效果如圖3所示。由圖3可知,當(dāng)w∈[0.005,0.018]時(shí),該算法有較高的檢測(cè)率以及較低的誤報(bào)率。當(dāng)w∈[0.03,0.04]時(shí),異常數(shù)據(jù)點(diǎn)可能會(huì)被劃分到正常數(shù)據(jù)簇內(nèi),從而影響檢測(cè)效果,并且導(dǎo)致較高的誤報(bào)率。由此可知,HSCBD方案對(duì)w參數(shù)比較敏感。 圖3 HSCBD方案檢測(cè)效果(高斯數(shù)據(jù)集) 基于高斯數(shù)據(jù)集,利用控制單一變量法,實(shí)驗(yàn)驗(yàn)證本文方案A_HSCBD在不同聚類(lèi)數(shù)量k時(shí)的檢測(cè)率,結(jié)果如圖4所示。由圖4可知,當(dāng)k∈[13,15]時(shí),本文方案同樣能夠?qū)崿F(xiàn)較高的檢測(cè)率。當(dāng)k=14時(shí),檢測(cè)效果如圖5所示。由圖5可知,該方案的檢測(cè)效果與HSCBD相當(dāng)。 圖4 A_HSCBD方案的檢測(cè)率(高斯數(shù)據(jù)集) 圖5 A_HSCBD方案檢測(cè)效果(k=14,高斯數(shù)據(jù)集) 基于數(shù)據(jù)總量以及聚類(lèi)操作得到簇的數(shù)量,可以衡量HSCBD與A_HSCBD方案相對(duì)于集中式方案所能夠?qū)崿F(xiàn)的通信復(fù)雜度節(jié)省率,結(jié)果如圖6所示。由圖6可知,在高斯數(shù)據(jù)集中,本文方案比HSCBD方案能夠?qū)崿F(xiàn)更高的通信復(fù)雜度節(jié)省率。 圖6 2種方案的能量節(jié)省率(高斯數(shù)據(jù)集) IBRL數(shù)據(jù)集是在美國(guó)加利福尼亞州的因特爾伯克利實(shí)驗(yàn)室中收集的數(shù)據(jù)集合。收集該數(shù)據(jù)的傳感器節(jié)點(diǎn)部署于室內(nèi)環(huán)境,傳感器以31 s的時(shí)間間隔收集5個(gè)測(cè)量值:溫度,光強(qiáng),相對(duì)濕度,電壓和拓?fù)湫畔ⅰS捎跀?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方案的檢測(cè)率為98%,與HSBCS方案的檢測(cè)率96%相比,提高了2個(gè)百分點(diǎn),并且誤報(bào)率也處于較低水平。圖9為HSCBD與A_HSCBD方案相對(duì)于集中式方案的能量節(jié)省率的對(duì)比。由圖9可知,在IBRL數(shù)據(jù)集中,本文方案與HSCBD方案相比,能量節(jié)省率有了進(jìn)一步提高。 圖7 HSCBD方案的檢測(cè)效果(IBRL數(shù)據(jù)集) 圖8 A_HSCBD方案的檢測(cè)效果(IBRL數(shù)據(jù)集) 圖9 HSCBD與A_HSCBD方案的能量節(jié)省率對(duì)比(IBRL數(shù)據(jù)集) 為避免偶然性因素的影響,對(duì)2個(gè)數(shù)據(jù)集進(jìn)行10次實(shí)驗(yàn),其平均檢測(cè)率如表2所示,可以看出,與集中式方案、HSCBD方案相比,本文方案檢測(cè)效率較高。 表2 3種方案10次平均檢測(cè)率對(duì)比 綜合分析可知,與集中式方案和HSCBD方案相比,本文方案具有較高的檢測(cè)效率和通信效率,但由于聚類(lèi)算法k的確定需要一個(gè)學(xué)習(xí)過(guò)程,其時(shí)間復(fù)雜度較高。 本文提出一種針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)異常數(shù)據(jù)的分布式檢測(cè)方案。該方案在網(wǎng)絡(luò)中傳播能夠代表當(dāng)前節(jié)點(diǎn)信息的摘要信息,執(zhí)行簇合并算法以減少網(wǎng)絡(luò)通信開(kāi)銷(xiāo),同時(shí)由網(wǎng)關(guān)節(jié)點(diǎn)執(zhí)行異常簇的檢測(cè),將異常簇信息傳遞至各節(jié)點(diǎn)進(jìn)行異常數(shù)據(jù)點(diǎn)檢測(cè),從而區(qū)分單節(jié)點(diǎn)級(jí)別異常數(shù)據(jù)。仿真結(jié)果表明,與集中式方案及HSCBD方案相比,本文方案取得了更高的檢測(cè)效率并大幅降低了能量消耗。下一步將引入空間維度相似性對(duì)該方案進(jìn)行改進(jìn)。2.3 復(fù)雜度和能耗分析
3 實(shí)驗(yàn)仿真
3.1 高斯數(shù)據(jù)集實(shí)驗(yàn)
3.2 IBRL數(shù)據(jù)集實(shí)驗(yàn)
3.3 結(jié)果分析
4 結(jié)束語(yǔ)