顧曉勇,李光輝,3*

(1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122;2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室,南京 210003;3.物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程技術(shù)研究中心,江蘇 無錫 214122)

無線傳感器網(wǎng)絡(luò)是由大量微型、低成本的傳感器節(jié)點組成。無線傳感器節(jié)點通常被直接暴露在外界環(huán)境中進行環(huán)境信息的采集,如測量溫度、濕度、降水量、光照強度等。正常情況下測量的數(shù)據(jù)在一定范圍內(nèi)緩慢波動,但當(dāng)無線傳感網(wǎng)絡(luò)遭受外部事件(如火災(zāi)、降雨、空氣污染等)的影響,或節(jié)點自身的軟硬件故障(如電池能量不足、節(jié)點故障、軟件缺陷等)時,節(jié)點觀測值顯著偏離于正常模型,通常被稱為離群值[1]。因此,針對傳感器數(shù)據(jù)流進行離群檢測,對于保證傳感器網(wǎng)絡(luò)的數(shù)據(jù)質(zhì)量具有重要意義。

關(guān)于無線傳感網(wǎng)絡(luò)異常數(shù)據(jù)檢測方法,國內(nèi)外學(xué)術(shù)界已有很多研究成果[2-5]。潘軼彪等[6]提出了一種采用歷史數(shù)據(jù)集建立模型,估計當(dāng)前讀數(shù),并按照真實值與估計值間的差異檢測異常的方法。Yao等[7]提出了一種高效的在線異常檢測算法,該算法利用時間序列的分段線性模型,分別構(gòu)造參考時間序列和新的時間序列模型,通過求它們之間的相似度量值來捕捉時間序列中的差異,尋找該序列中的異常,該方法可以查找長時間的異常。Zhang等[8]提出了基于SVM模型的自適應(yīng)離群檢測算法,首先利用數(shù)據(jù)流的時間相關(guān)性在本地節(jié)點建立模型,判斷數(shù)據(jù)是否為局部離群點,再接收來自鄰居節(jié)點的相關(guān)系數(shù),利用空間相關(guān)性整合得全局檢測模型,可以找出全局離群點。近年來,許多學(xué)者用BPNN檢測異常數(shù)據(jù),但BPNN存在局部最優(yōu)解,訓(xùn)練時間長,效率低等問題。屈洪春等[9]提出了利用遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的算法,并應(yīng)用于異常檢測,相比BPNN該算法改善了優(yōu)化的精度和異常檢測率。但是遺傳算法的缺點也日益明顯,隨機搜索會導(dǎo)致過早收斂,思維進化算法[10]就可以很好的解決這個問題,但是它也存在局部搜索隨機性等問題。

針對上述問題,本文提出了一種基于小生境的思維進化算法,用來優(yōu)化BPNN參數(shù),由此獲得了一種新的傳感器網(wǎng)絡(luò)異常數(shù)據(jù)檢測算法。

1 算法原理

BP神經(jīng)網(wǎng)絡(luò)[11]是一種按誤差逆向傳播訓(xùn)練的多層前饋網(wǎng)絡(luò)。結(jié)構(gòu)如圖1所示,X1,X2,…,Xn是BP神經(jīng)網(wǎng)絡(luò)的輸入值,Y1,Y2,…,Ym是BP神經(jīng)網(wǎng)絡(luò)的預(yù)測值。網(wǎng)絡(luò)輸入層為n,隱含層為l,輸出層為m。

圖1 BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

思維進化算法[12]的基本思想是把群體劃分為若干個子群體,個體在子群體內(nèi)通過向優(yōu)勝者學(xué)習(xí),為成為優(yōu)勝子群體而展開全局競爭。思維進化算法過程中添加了記憶與定向?qū)W習(xí)機制,改善了搜索效率。

小生境技術(shù)的基本思想是將每一代個體劃分為若干類,每個類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代表組成一個群體,再在不同群體之間進行雜交、變異產(chǎn)生新一代群體,并且采用預(yù)選擇機制、排擠機制或分享機制以及聚類機制等完成選擇任務(wù)。在遺傳算法中,小生境技術(shù)主要采用排擠法和共享法,這兩種方法均需較多的個體參與競爭和共享資源,造成了時間的浪費。本文用文獻[13]中的RCS(Restricted Competition Selection)方法生成小生境,該方法只需幾個簡單的個體就可以完成。通過控制子群體之間的排斥和競爭,使各個子群體在進化過程中動態(tài)形成各自獨立的搜索空間,從而保持群體的多樣性。該算法如下所示,NMEA算法中有m個子群體,子群體的優(yōu)勝者為Umbest。

設(shè)兩子群體優(yōu)勝者間的距離為dij,s為個體編碼長度:

(1)

小生境算法如表1所示。

表1 小生境算法

2 基于NMEA的BPNN異常檢測算法

本文考慮將NMEA與BPNN結(jié)合起來,尋求新的傳感器網(wǎng)絡(luò)異常數(shù)據(jù)檢測算法。將BPNN與NMEA相結(jié)合,以避免網(wǎng)絡(luò)陷入局部極小值。在思維進化算法中,采用實數(shù)編碼法,根據(jù)BPNN結(jié)構(gòu)將解空間映射到編碼空間,每個編碼空間對應(yīng)一個個體。定義NMEA中的個體為BPNN中的一組待優(yōu)化的權(quán)閾值,尋找最優(yōu)個體得到最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu),建立檢測模型并進行異常檢測。神經(jīng)網(wǎng)絡(luò)的訓(xùn)練終止條件是樣本與網(wǎng)絡(luò)實際輸出值的均方誤差達到最小(對應(yīng)NMEA中的得分函數(shù)最大),公式為:

(2)

(3)

NMEA優(yōu)化的權(quán)閾值總數(shù)為s=nl+ml+l+m。用NMEA優(yōu)化的權(quán)閾值作為BPNN的初始值,然后構(gòu)建模型進行訓(xùn)練。本文提出的異常檢測算法包括基于NMEA的BPNN參數(shù)優(yōu)化和傳感器數(shù)據(jù)流異常檢測兩個階段。

2.1 基于NMEA的BPNN參數(shù)優(yōu)化

傳統(tǒng)的MEA對局部的搜索具有隨機性,受文獻[13]的啟發(fā),本文提出了一種新的思維進化算法。具體步驟如下:

Step 1 隨機生成N個個體形成初始群體,按照式(2)、式(3)計算各個個體的得分。

Step 2 按照個體得分從大到小進行排序,選取前q個個體為優(yōu)勝者,分別以優(yōu)勝者為中心形成子群體。

Step 3 生成小生境。對q個子群體的優(yōu)勝者分別按照式(1)計算優(yōu)勝者間的得分,得分低的個體將被丟棄,生成新的個體,直到產(chǎn)生各自的搜索空間。

Step 4 分別以優(yōu)勝者為中心生成新的子群體。

Step 5 在小生境中執(zhí)行趨同操作,查找局部最優(yōu)解。

Step 6 比較成熟群體的得分,分?jǐn)?shù)最少的子群體被丟棄,生成新的個體。

Step 7 將生成的新的個體與整個群體的優(yōu)勝者按照式(1)進行相比,直到新生成的個體在不同的小生境中。

Step 8 當(dāng)最優(yōu)勝者的得分不再變化時則停止迭代,得到最優(yōu)解;否則轉(zhuǎn)Step4。

2.2 基于最優(yōu)BPNN的傳感器網(wǎng)絡(luò)異常數(shù)據(jù)檢測

2.2.1 滑動窗口模型

本文使用滑動窗口模型處理傳感器數(shù)據(jù)流,該模型是用來查看傳感器節(jié)點最近一個采樣時間段的數(shù)據(jù),即對傳感器數(shù)據(jù)流選取一個固定長度的窗口。

如圖2所示,滑動窗口大小為n。若在t時刻窗口中存儲數(shù)據(jù)為{Xt-n+1,…,Xt-1,Xt},則在t+1時刻

圖2 滑動窗口模型

2.2.2 異常檢測過程

首先利用歷史數(shù)據(jù)訓(xùn)練神經(jīng)網(wǎng)絡(luò),獲得下一時刻的采樣預(yù)測值。然后選取訓(xùn)練數(shù)據(jù)的后v個樣本數(shù)計算神經(jīng)網(wǎng)絡(luò)的模型殘差,并確定置信區(qū)間范圍。當(dāng)下一時刻的數(shù)據(jù)在區(qū)間范圍內(nèi),則該數(shù)據(jù)為正常值;反之,則為異常值。公式如下:

(4)

式中:S為神經(jīng)網(wǎng)絡(luò)模型殘差,v代表選取的樣本數(shù),Ei(i=1,2,…,v)為選取的樣本值,F代表所選取樣本的平均值。

置信區(qū)間的上、下界分別用如下公式給出:

(5)

(6)

Step 1 輸入數(shù)據(jù)到滑動窗口{Xt-n+1,…,Xt-1,Xt}中。

Step 2 讀取下一時刻的數(shù)據(jù)Xt+1,利用訓(xùn)練好的模型獲得該時刻的預(yù)測值t+1,按照式(4)～式(6)計算置信區(qū)間范圍。

Step 4 判斷數(shù)據(jù)讀取情況。若下一時刻數(shù)據(jù)能夠讀取,轉(zhuǎn)Step 2,否則結(jié)束。

綜上所述,本文提出的NMEA-BP異常檢測算法如表2所示。

表2 NMEA-BP異常檢測算法

3 實驗結(jié)果及分析

為了評估NMEA-BP異常檢測算法的性能,本文使用因特爾伯克利實驗室的無線傳感網(wǎng)絡(luò)數(shù)據(jù)集(IBRL)以及文獻[15]提供的帶標(biāo)記傳感網(wǎng)絡(luò)數(shù)據(jù)集(LWSNDR)完成了仿真實驗。實驗是在Intel(R)Core(TM)i5-2450MCPU,主頻2.5GHz,內(nèi)存8G,操作系統(tǒng)Window8環(huán)境下進行的,編程語言采用MATLAB2014a。分別實現(xiàn)了BP、NMEA-BP、SVM以及ELM算法,并進行了實驗結(jié)果的比較。

3.1 數(shù)據(jù)集

IBRL數(shù)據(jù)集來自于部署在IntelBerkeley實驗室中的無線傳感器網(wǎng)絡(luò),該網(wǎng)絡(luò)有54個MICA2傳感器節(jié)點,采樣周期為30s,運行周期為2004年2月28日到2004年4月5日,每個節(jié)點的數(shù)據(jù)包括溫度、濕度、光照及電壓4個屬性。本文分別選取7號傳感器節(jié)點2004年2月28日1點到16點的溫度、濕度采樣數(shù)據(jù),選取9號傳感器節(jié)點2004年2月28日8點到2004年2月29日22點的溫度、濕度采樣數(shù)據(jù),選取29號傳感器節(jié)點2004年3月5日17點到2004年3月8日4點的溫度、濕度采樣數(shù)據(jù),選取7號傳感器節(jié)點2004年3月5日17點到2004年3月8日5點的溫度、濕度采樣數(shù)據(jù)作為本實驗數(shù)據(jù)集。LWSNDR數(shù)據(jù)集采集的是室內(nèi)和室外的溫度、濕度數(shù)據(jù),選取兩組室外的數(shù)據(jù)LWSNDR-1和LWSNDR-2。由于樣本數(shù)據(jù)集中異常值較少,實驗過程中我們?nèi)斯るS機地添加異常值。實驗數(shù)據(jù)集如表3所示。

表3 實驗所用數(shù)據(jù)集

3.2 性能評價指標(biāo)

對于二分類問題,可將樣本根據(jù)其真實類別和決策模型檢測類別的組合劃分成真正例TP(True Positive)、假正例FP(False Positive)、真反例TN(True Negative)、假反例FN(False Negative)4種情形。

為了評價算法的性能,本文使用檢測率TPR(True Positive Rate)和誤報率FPR(False Positive Rate)兩個指標(biāo)。公式如下:

(7)

(8)

3.3 參數(shù)設(shè)定

BPNN的訓(xùn)練參數(shù)如表4所示。Show為訓(xùn)練過程中的顯示步數(shù);Lr為神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)速率;Epochs為神經(jīng)網(wǎng)絡(luò)允許的最大訓(xùn)練步數(shù);Goal為神經(jīng)網(wǎng)絡(luò)的目標(biāo)精度。

表4 BP神經(jīng)網(wǎng)絡(luò)的訓(xùn)練參數(shù)

3.4 BP神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化的對比實驗

為驗證本文提出的小生境思維進化優(yōu)化算法的效率,在IBRL_7的訓(xùn)練數(shù)據(jù)中選取4組不同規(guī)模的數(shù)據(jù),為500、1 000、1 500、2 000個數(shù)據(jù),同時在LWSNDR-2訓(xùn)練數(shù)據(jù)集上選取4組不同規(guī)模的數(shù)據(jù),為300、600、900、1 200個數(shù)據(jù)。分別使用BP算法和NMEA-BP算法在不同規(guī)模數(shù)據(jù)集上做訓(xùn)練,并用訓(xùn)練時間作為衡量指標(biāo),實驗結(jié)果如圖3所示,橫坐標(biāo)代表選取的數(shù)據(jù)樣本序號,縱坐標(biāo)代表訓(xùn)練時間。由圖3(a)可知,在IBRL數(shù)據(jù)集上,BP算法平均訓(xùn)練時間為32 s,NMEA-BP算法在訓(xùn)練時間方面優(yōu)勢較明顯,平均訓(xùn)練時間為24 s,相對BP算法訓(xùn)練時間減少25%;由圖3(b)可知,在LWSNDR數(shù)據(jù)集上,BP算法平均訓(xùn)練時間為17 s,NMEA-BP算法平均訓(xùn)練時間為11 s,相對BP算法訓(xùn)練時間減少33%。這是由于NMEA算法使用更短的速度達到了誤差要求縮短了訓(xùn)練時間。

圖4 BP算法和NMEA-BP算法的誤差平方和曲線

圖3 BP算法和NMEA-BP算法在不同規(guī)模數(shù)據(jù)集上的訓(xùn)練時間

選取數(shù)據(jù)集IBRL_7和LWSNDR-2的神經(jīng)網(wǎng)絡(luò)誤差平方和曲線,橫坐標(biāo)代表訓(xùn)練步數(shù),縱坐標(biāo)代表均方誤差。由圖4(a)可得,在同樣目標(biāo)誤差下,NMEA-BP算法達到訓(xùn)練誤差時需要172步,而BP算法需要214步達到訓(xùn)練誤差;由圖4(b)可得,在同樣目標(biāo)誤差下,NMEA-BP算法達到訓(xùn)練誤差時需要91步,而BP算法需要126步達到訓(xùn)練誤差。證明經(jīng)NMEA算法優(yōu)化后的BPNN的權(quán)閾值得到了全局尋優(yōu),有更好的收斂效果。

3.5 異常檢測算法的對比實驗

為了評估NMEA-BP算法性能,分別在上述6個數(shù)據(jù)集上進行對比實驗,結(jié)果如表5和表6所示。從表5可以看出,在不同的數(shù)據(jù)集下,NMEA-BP算法TPR比BP、ELM、SVM算法平均提高了0.8%、1.92%、3.2%;NMEA-BP算法FPR比BP、ELM、SVM算法平均降低了1.65%、2.13%、2.15%。從表5還可以發(fā)現(xiàn),SVM算法在數(shù)據(jù)集Ⅱ,Ⅲ,Ⅳ上TPR和FPR較好,但SVM算法在數(shù)據(jù)集Ⅰ上FPR偏高是由于訓(xùn)練樣本較少,數(shù)據(jù)分布不均勻?qū)е碌?與NMEA-BP算法對比,FPR相對偏高,TPR稍低。ELM算法在4個數(shù)據(jù)集上都表現(xiàn)出了較高的TPR,而在數(shù)據(jù)Ⅰ中FPR相對偏高是由于ELM隱層神經(jīng)元數(shù)目是隨機的,建立的檢測模型不夠穩(wěn)定,就決定了TPR和FPR的高低。BP算法雖然對于訓(xùn)練集的數(shù)據(jù)能很好地擬合,但由于數(shù)據(jù)集Ⅰ的測試數(shù)據(jù)和異常數(shù)據(jù)的差距較小,算法求得的置信區(qū)間范圍較小,導(dǎo)致該數(shù)據(jù)集的誤報率偏高。NMEA-BP算法在數(shù)據(jù)集Ⅰ上的誤報率比BP算法降低了5.8%,這是由于優(yōu)化后的模型預(yù)測更精確,置信區(qū)間的范圍相對準(zhǔn)確。在其他3個數(shù)據(jù)集上大部分異常樣本與正常樣本區(qū)分度較高,可以很容易檢測出來。從表6可以看出,在不同的數(shù)據(jù)集下,NMEA-BP算法和BP算法均表現(xiàn)出較好的檢測結(jié)果,而SVM算法和ELM算法的檢測率相對偏低,這是數(shù)據(jù)分布不均勻?qū)е碌?。因?NMEA-BP算法具有更好的檢測性能。

表5 關(guān)于IBRL數(shù)據(jù)集的算法性能對比

表6 關(guān)于LWSNDR數(shù)據(jù)集的算法性能對比

圖5 NMEA-BP算法的異常檢測結(jié)果

為了更直觀地闡明NMEA-BP算法的異常檢測過程,現(xiàn)以數(shù)據(jù)集Ⅲ為例說明。圖5給出了NMEA-BP的異常檢測結(jié)果。其中,橫坐標(biāo)為樣本數(shù),縱坐標(biāo)為溫度,根據(jù)置信區(qū)間判斷異常,兩條線段代表區(qū)間的上下界,用圓圈圈出的則為異常值。選取第1 000個樣本的數(shù)據(jù),其值為30.11,而NMEA-BP算法的預(yù)測值為30.21,通過區(qū)間公式計算置信區(qū)間,為[29.91,30.51],故算法判定該樣本為正常值;若樣本值不在置信區(qū)間范圍內(nèi),則算法判定該樣本為異常值。

圖6 BP算法和NMEA-BP算法的ROC曲線

在對不同算法進行比較時,較為合理的判斷依據(jù)是比較ROC(Receiver Operating Characteristic)曲線下的面積[16],即AUC(Area Under ROC Curve),該方法簡單,直觀,通過圖示就可以觀察分析方法的準(zhǔn)確性。圖6給出了NMEA-BP和BP兩種算法的ROC曲線。其中,橫坐標(biāo)代表FPR,縱坐標(biāo)代表TPR。

由圖6可以發(fā)現(xiàn)BP算法ROC曲線被NMEA-BP算法ROC曲線完全包住,ROC曲線越靠近左上角表明其TPR更好,因此,NMEA-BP算法的ROC曲線有更大的AUC。NMEA-BP算法在TPR接近100%時FPR僅為1.5%,而BP算法此時的TPR為92%左右,故NMEA-BP算法具有更好的檢測性能。

4 結(jié)論

本文提出了一種基于NMEA-BP的傳感器網(wǎng)絡(luò)數(shù)據(jù)流異常檢測算法。該算法將小生境技術(shù)與思維進化相結(jié)合,對BPNN的權(quán)閾值進行尋優(yōu),克服了傳統(tǒng)BPNN收斂速度慢和易陷入局部極小的缺陷等問題,加快了BPNN學(xué)習(xí)速率。NMEA-BP算法在異常檢測率較高的同時減少了訓(xùn)練時間。實驗結(jié)果表明,與其他同類算法相比,NMEA-BP算法對傳感器數(shù)據(jù)流的異常檢測有更高的檢測率和更低的誤報率。本文算法是利用時間相關(guān)性檢測的,今后的研究將考慮利用節(jié)點間的空間相關(guān)性,以便進一步提高檢測率,降低誤報率。

參考文獻:

[1] 李建中,高宏. 無線傳感器網(wǎng)絡(luò)的研究進展[J]. 計算機研究與發(fā)展,2008,45(1):1-15.

[2] 李娟娟,孟國營,謝廣明,等. 基于小波包與SOM神經(jīng)網(wǎng)絡(luò)的傳感器故障診斷[J]. 傳感技術(shù)學(xué)報,2017,30(7):1035-1039.

[3] Mainwaring A,Polastre J,Szewczyk R,et al. Wireless Sensor Networks for Habitat Monitoring[C]//Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. IEEE,2002:88-97.

[4] 孫利民,李建中,陳渝,等. 無線傳感器網(wǎng)絡(luò)[M]. 北京:清華大學(xué)出版社,2005:407-417.

[5] McDonald D,Sanchez S,Madria S,et a1. A Survey of Methods for Finding Outliers in Wireless Sensor Networks[J]. Journal of Network and Systems Management,2015,23(1):1-20.

[6] 潘軼彪,袁景淇,朱凱,等. 基于多層感知器的異常數(shù)據(jù)實時檢測方法[J]. 上海交通大學(xué)學(xué)報,2011,45(8):1226-1229.

[7] Yao Y,Sharma A,Golubchik L,et a1. Online Anomaly Detection for Sensor Systems:A simple and efficient approach[J]. Performance Evaluation,2010,67(11):1059-1075.

[8] Zhang Y,Meratnia N,Havinga P J M. Distributed Online Outlier Detection in Wireless Sensor Networks Using Ellipsoidal Support Vector Machine[J]. Ad Hoc Networks,2013,11(3):1062-1074.

[9] 屈洪春,王帥. 一種基于進化神經(jīng)網(wǎng)絡(luò)的混合入侵檢測模型[J]. 計算機科學(xué),2016,43(S1):335-338.

[10] Gao J L. Modeling of Photovoltaic Cell Based on BP Neural Networks Improved by MEA[J]. Applied Mechanics and Materials,2012,217-219:809-814.

[11] 孫艷梅,苗鳳娟,陶佰睿. 基于PSO的BP神經(jīng)網(wǎng)絡(luò)在壓力傳感器溫度補償中的應(yīng)用[J]. 傳感技術(shù)學(xué)報,2014,27(3):342-346.

[12] Sun C Y. Mind-Evolution-Based Machine Learning:Framework and the Implementation of Optimization[C]//Proceeding of International Conference on Intelligent Engineering Systems. IEEE,1998:355-359.

[13] Lee CG,Cho D H,Jung H K. Niche Genetic Algorithm with Restricted Competition Selection for Multimodal Function Optimization[J]. IEEE Transaction on Magnetics,1999,35(1):1722-1725.

[14] Hill D J,Minsker B S. Anomaly Detection in Streaming Environmental Sensor Data:A Data-Driven Modeling Approach[J]. Environmental Modeling and Software,2010,25(9):1014-1022.

[15] Shan S,Alzahrani M,Rajasegarar S,et al. Labeled Data Collection for Anomaly Detection in Wireless Sensor Networks[C]//Proceeding of International Conference on Intelligent Sensors. IEEE,2010:269-274.

[16] 周志華. 機器學(xué)習(xí)[M]. 北京:清華大學(xué)出版社,2016:33-35.