基于NMEA-BP的WSN數據流異常檢測算法*

顧曉勇,李光輝,3*

(1.江南大學物聯網工程學院,江蘇 無錫 214122;2.江蘇省無線傳感網高技術研究重點實驗室,南京 210003;3.物聯網技術應用教育部工程技術研究中心,江蘇 無錫 214122)

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

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

針對上述問題,本文提出了一種基于小生境的思維進化算法,用來優化BPNN參數,由此獲得了一種新的傳感器網絡異常數據檢測算法。

1 算法原理

BP神經網絡[11]是一種按誤差逆向傳播訓練的多層前饋網絡。結構如圖1所示,X1,X2,…,Xn是BP神經網絡的輸入值,Y1,Y2,…,Ym是BP神經網絡的預測值。網絡輸入層為n,隱含層為l,輸出層為m。

圖1 BP神經網絡結構

思維進化算法[12]的基本思想是把群體劃分為若干個子群體,個體在子群體內通過向優勝者學習,為成為優勝子群體而展開全局競爭。思維進化算法過程中添加了記憶與定向學習機制,改善了搜索效率。

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

設兩子群體優勝者間的距離為dij,s為個體編碼長度:

(1)

小生境算法如表1所示。

表1 小生境算法

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

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

(2)

(3)

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

2.1 基于NMEA的BPNN參數優化

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

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

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

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

Step 4 分別以優勝者為中心生成新的子群體。

Step 5 在小生境中執行趨同操作,查找局部最優解。

Step 6 比較成熟群體的得分,分數最少的子群體被丟棄,生成新的個體。

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

Step 8 當最優勝者的得分不再變化時則停止迭代,得到最優解;否則轉Step4。

2.2 基于最優BPNN的傳感器網絡異常數據檢測

2.2.1 滑動窗口模型

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

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

圖2 滑動窗口模型

2.2.2 異常檢測過程

首先利用歷史數據訓練神經網絡,獲得下一時刻的采樣預測值。然后選取訓練數據的后v個樣本數計算神經網絡的模型殘差,并確定置信區間范圍。當下一時刻的數據在區間范圍內,則該數據為正常值;反之,則為異常值。公式如下:

(4)

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

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

(5)

(6)

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

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

Step 4 判斷數據讀取情況。若下一時刻數據能夠讀取,轉Step 2,否則結束。

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

表2 NMEA-BP異常檢測算法

3 實驗結果及分析

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

3.1 數據集

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

表3 實驗所用數據集

3.2 性能評價指標

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

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

(7)

(8)

3.3 參數設定

BPNN的訓練參數如表4所示。Show為訓練過程中的顯示步數;Lr為神經網絡的學習速率;Epochs為神經網絡允許的最大訓練步數;Goal為神經網絡的目標精度。

表4 BP神經網絡的訓練參數

3.4 BP神經網絡參數優化的對比實驗

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

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

圖3 BP算法和NMEA-BP算法在不同規模數據集上的訓練時間

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

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

為了評估NMEA-BP算法性能,分別在上述6個數據集上進行對比實驗,結果如表5和表6所示。從表5可以看出,在不同的數據集下,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還可以發現,SVM算法在數據集Ⅱ,Ⅲ,Ⅳ上TPR和FPR較好,但SVM算法在數據集Ⅰ上FPR偏高是由于訓練樣本較少,數據分布不均勻導致的,與NMEA-BP算法對比,FPR相對偏高,TPR稍低。ELM算法在4個數據集上都表現出了較高的TPR,而在數據Ⅰ中FPR相對偏高是由于ELM隱層神經元數目是隨機的,建立的檢測模型不夠穩定,就決定了TPR和FPR的高低。BP算法雖然對于訓練集的數據能很好地擬合,但由于數據集Ⅰ的測試數據和異常數據的差距較小,算法求得的置信區間范圍較小,導致該數據集的誤報率偏高。NMEA-BP算法在數據集Ⅰ上的誤報率比BP算法降低了5.8%,這是由于優化后的模型預測更精確,置信區間的范圍相對準確。在其他3個數據集上大部分異常樣本與正常樣本區分度較高,可以很容易檢測出來。從表6可以看出,在不同的數據集下,NMEA-BP算法和BP算法均表現出較好的檢測結果,而SVM算法和ELM算法的檢測率相對偏低,這是數據分布不均勻導致的。因此,NMEA-BP算法具有更好的檢測性能。

表5 關于IBRL數據集的算法性能對比

表6 關于LWSNDR數據集的算法性能對比

圖5 NMEA-BP算法的異常檢測結果

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

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

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

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

4 結論

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

參考文獻:

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

[2] 李娟娟,孟國營,謝廣明,等. 基于小波包與SOM神經網絡的傳感器故障診斷[J]. 傳感技術學報,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] 孫利民,李建中,陳渝,等. 無線傳感器網絡[M]. 北京:清華大學出版社,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] 潘軼彪,袁景淇,朱凱,等. 基于多層感知器的異常數據實時檢測方法[J]. 上海交通大學學報,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]. 計算機科學,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]. 傳感技術學報,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] 周志華. 機器學習[M]. 北京:清華大學出版社,2016:33-35.