基于隨機矩陣理論的WSN異常節點定位算法

林 超,鄭 霖,張文輝,鄧小芳

(桂林電子科技大學 a.廣西無線寬帶通信與信號處理重點實驗室; b.廣西云計算與大數據協同創新中心;c.廣西高校云計算與復雜系統重點實驗室,廣西 桂林 541004)

0 概述

物聯網(Internet of Things,IoT)被廣泛應用于環境監測、智能交通、工業控制、醫療系統、海洋農業等領域[1],作為其核心技術之一的無線傳感器網絡(Wireless Sensor Network,WSN),是由大量具備感知、數據處理、數據存儲和通信等功能的微型節點組成的自組織網絡[2],通過分析其采集的區域數據信息可以達到實時監控該區域的目的。然而,在采集的海量數據中存在顯著偏離于正常感測數據的異常值,這些異常值產生的原因有很多,如某些節點發生故障(能量耗盡、受到外界攻擊等),或是發生了異常事件(如森林火災、交通擁塞等),同時,正常數據也會在一定范圍內發生合理的波動。因此,異常事件檢測是WSN中關鍵技術之一,可及時發現隱藏在海量數據中的異常數據或異常狀態,幫助決策者直觀迅速地了解網絡當前運行情況,做出正確的判斷和決策,從而及時解決異常問題[3]。

通過對網絡波動數據進行異常檢測,可以有效地發現異常情況并定位異常節點,在WSN實際應用中具有重要意義[4]。目前對實時高效、準確的WSN異常事件檢測算法的研究逐漸深入,在所有異常檢測的算法中,基于經典統計學的方法需要假設采集的數據符合一個統計模型[5],然后通過評估數據和模型的匹配度來確定未知數據是正常數據還是異常數據。該方法在異常檢測中有著較高的準確率,但也存在明顯的缺點,即必須已知數據所滿足的特定統計模型,而在實際的應用當中,網絡數據統計模型往往很難事先獲得或精確描述。

異常檢測還會采用基于臨近點的檢測方法[4-5],該方法通過計算數據集中每個數據之間的相似度(距離)對異常點進行識別,一種典型的基于臨近點方法的異常檢測算法是LOF(Local Outlier Factor),該算法可以有效識別異常,但存在2個不足:首先是其計算復雜度高,海量數據下的計算開銷不可忽視;其次是雖然LOF算法可以有效地發現孤立異常對象,但如果出現異常對象聚集在一起的情況,LOF算法的異常檢測準確率將大幅下降。此外,常用的異常檢測方法還有分類方法[6]和聚類分析法[7]等。

近年來,已有學者開始將數理統計學中的隨機矩陣理論(Random Matrix Theory,RMT)應用到通信領域。文獻[8]針對經典特征值類頻譜感知算法在低采樣、低信噪比下檢測效果不佳的問題,提出一種基于隨機矩陣特征值差的頻譜感知改進算法。文獻[9-10]闡述了隨機矩陣理論與無線通信緊密的聯系和數學背景,展示了隨機矩陣理論處理無線通信領域問題的優勢。文獻[11]將隨機矩陣理論中的單環定律應用于頻譜感知的研究中,設計了基于單環定律的頻譜感知算法。文獻[12]使用隨機矩陣理論作為大數據分析的框架并將其應用于移動蜂窩網絡中的數據分析。相比傳統的數據分析方法,隨機矩陣理論能夠在一定程度上擺脫傳統的物理模型,充分利用數據資源,從數據驅動角度分析挖掘網絡的關聯性和運行特征。研究者通過利用隨機矩陣理論中一些優良、成熟的定理和特性,從高維的視角分析并解決通信系統中存在的問題,取得了一定的效果。

為對WSN高維數據進行實時有效的分析，檢測網絡中是否出現異常并定位異常節點的位置，本文基于隨機矩陣理論設計一種WSN異常節點定位算法。

1 隨機矩陣理論

隨機矩陣是一個以隨機變量為元素的矩陣,其概念由WIGNER等人提出并吸引了許多數學家和統計學家對其進行深入研究,逐漸形成了隨機矩陣理論。經驗譜分布是隨機矩陣理論中的一個重要概念,對于一個特征值均為實數的n×n維隨機矩陣A,稱以下分布函數為該矩陣的經驗譜分布(Empirical Spectrun Distribution,ESD):

(1)

其中,λi(i=1,2,…,N)為特征值,I{·}表示指示函數。當隨機矩陣A的行數和列數趨于無窮大且行列比保持恒定時,其經驗譜分布函數將收斂到一個非隨機的函數,稱為極限譜分布(Limit Spectral Distribution,LSD)函數。此時,許多優良的性質將會表現出來,如Marchenko-Pastur律(M-P律)、平均譜半徑(Mean Spectral Radius,MSR)、單環定理、半圓律[13]。本文研究主要采用單環定理和平均譜半徑。

1.1 單環定理

(2)

其中,c∈(0,1],c為常數。在復平面上,矩陣Z的特征值大致分布在一個內徑為(1-c)L/2、外徑為1的圓環內。

1.2 平均譜半徑

利用平均譜半徑可以從高維視角描述系統的統計特征[15]。由隨機矩陣理論可知,當系統中有異常事件(異常的信號源)發生時,其統計隨機特性將會被破壞,隨機矩陣的特征值分布會發生變化,rMSR可反映隨機矩陣的統計特性故將其作為評價指標。平均譜半徑計算公式如下:

(3)

其中,λi(i=1,2,…,N)為協方差矩陣的特征值。

2 網絡異常情況分析與異常節點定位

在進行網絡異常分析和異常節點的定位之前,首先要明確異常值的定義,本文采用文獻[16]中的異常值定義:異常值是指在數據集中偏離正常數據模型的數據,其是由完全不同的機制產生而不是由隨機誤差導致。根據此定義,本文將與正常數據模型不一致的數據判定為異常數據。

在WSN中,正常情況下采集到的數據符合獨立同分布,而一旦出現異常情況,數據將不再滿足獨立同分布。隨機矩陣理論作為對高維數據進行統計分析的方法之一,可從高維的視角判斷WSN采集的數據中是否有異常數據出現。因此,本文基于隨機矩陣理論,從整體上分析網絡是否出現異常,并在此基礎上利用最大特征值對應特征向量的最大元素定位法對出現異常的節點進行定位。

2.1 基于隨機矩陣理論的網絡異常態勢分析

由于WSN采集的數據具有獨立的時空特性,因此本文首先利用數據的時空特性對原始數據進行組織以及數據的歸一化和標準化預處理。

假設節點數為N個,每個節點的采樣總時間為T(T>>N),則N個節點的數據可用矩陣XN×T表示：

(4)

(5)

(6)

由單環定理計算每個采樣時刻滑動窗內數據的特征值以及采用式(3)計算對應的平均譜半徑,當窗口滑動結束后,可根據各個時刻平均譜半徑的值繪制出趨勢圖并對其進行分析。當感測的數據處于正常模式時,其平均譜半徑不會突變；當發生異常擾動時,在該異常發生的一段時間內,平均譜半徑會發生顯著的變化。因此,本文使用平均譜半徑作為評價指標來判斷網絡整體態勢。算法描述如下:

算法網絡異常態勢判斷算法

輸入數據矩陣X,窗口寬度Tw,總時間T

輸出每個采樣時刻平均譜半徑值r(i)

for i=Tw:T

2.2 異常節點定位

(7)

然后對協方差矩陣P進行特征值分解,可得:

(8)

Pvk=λkvk

(9)

根據上述定理并結合式(9)可做如下推導:

(10)

(11)

由此可知,在第k個特征值λk對應的特征向量vk中,特征向量vk的第i個元素vki的變化只與矩陣P的第i行有關聯,因此,當矩陣P的第i行出現異常波動時,將導致特征向量vk上第i個元素的值出現顯著變化且與其他元素有明顯的區別,即當第i個節點的感知數據出現較為明顯的變化時,會在數據的處理中同時反映在其特征向量的第i個元素,相反地，vkj(j≠i)的其他元素則與P的第i行數據無關。利用這一關系,可以通過觀察特征向量的元素進行異常位置的定位。由特征值分解的含義可知,特征值和特征向量可以清晰地反映出矩陣在哪些方面產生的效果最大,矩陣的特征值越大,反映出矩陣在該特征值對應的特征向量上產生的效果或者能量越大,因此，在仿真實驗中依據特征值的大小,通常對前4個較大特征值對應的特征向量元素進行分析并判斷出現異常情況概率最大的節點。

3 仿真結果與分析

本文異常節點分析仿真分為2個部分進行,仿真1針對網絡的整體運行情況是否出現異常進行分析,仿真2則在仿真1的基礎上進行網絡中異常節點的定位。

3.1 實驗數據來源

本文通過英特爾伯克利實驗室(Intel Berkeley Research Lab,IBRL)實地部署的無線傳感器網絡采集到的數據進行實驗[17-18]。IBRL網絡由55個節點構成,整個網絡在2004年2月28日—2004年5月5日之間,每隔30 s采集一次數據,每條數據包含溫度、濕度、電壓、光照強度以及時間標記5個屬性。在實驗中,本文選取50個傳感器采集的電壓數據,將3月6日00:00開始的共1 000個采樣時刻的數據構成大小為50×1 000的原始數據矩陣,通過人工注入多種類型異常來驗證該算法的有效性[20]。本文的異常數據集由4種異常類型組成,其分別模擬了異常情況下4種數據變化的趨勢,如表1所示,其中,n為異常持續的時長。異常類型1模擬了節點感測到環境中發生緩慢但又有區別于正常情況下的變化(如煤氣泄漏導致空氣中有毒氣體含量的緩慢上升),其將導致節點在短時間內所采集的數據在數值上緩慢上升。異常類型2模擬了環境中出現較為劇烈的變化(發生火災而導致溫度在短時間內快速上升),這將導致節點在短時間內所采集的數據在數值上迅速上升。異常類型3模擬了傳感器節點感測到外界環境極端的變化(如人為異物的遮擋或異物入侵等)而導致其采集的數據在數值上發生一定程度的驟變。異常類型4表示數據為0,模擬了節點受到外界異常的干擾導致故障,無法正常工作。

表1 異常類型及參數

3.2 性能評價指標

實驗從異常節點定位準確率和誤警率來衡量本文算法。其中，異常節點定位準確率Pd的定義為:存在異常節點時,成功定位異常節點的次數與實驗測試次數比值的百分數。異常節點定位誤警率Pfa的定義為:不存在異常節點時,誤判為有異常節點的次數與實驗測試次數比值的百分數。

3.3 實驗結果與分析

仿真1對原始數據中的第5個節點,在350～449的采樣時間段內根據表1的異常類型分別注入異常,取時間窗口Tw=90,按2.1節的方法對該含有異常的數據集進行分析,可得到如圖1所示的仿真結果。

圖1 4類異常情況和無異常情況下的平均譜半徑Fig.1 MSR in normal condition and 4 abnormal conditions

由于時間窗口為90,因此從第90個采樣點開始分析平均譜半徑數值,通過與無異常情況下平均譜半徑的曲線相比,注入的異常會造成平均譜的值顯著增大,且不同的異常類型所導致的異常數據使得在異常發生時平均譜半徑的趨勢不同,由此可以分析出網絡運行的整體態勢,并檢測出網絡運行是否出現異常。

仿真2進一步分析定位數據異常的節點。首先對單個節點出現異常情況進行檢測。針對第5個節點，在250～350時間段內人工注入類型1的異常數據(其他異常類型也可得到相同結論)。根據2.2節協方差矩陣特征值及對應特征向量(按特征值升序排列),檢測矩陣中出現異常的行,以此對應到異常狀態量。仿真結果如圖2所示。

圖2 單個異常節點情況下的特征向量元素分布

Fig.2 Distribution of eigenvector elements in presence of one single abnormal node

圖2顯示了前4個較大特征值對應特征向量元素的分布,通過比較可以看出,圖2(c)具有較大的峰均比,而圖2(a)、圖2(b)和圖2(d)均無此現象,與圖2(c)形成明顯的差異,圖2(c)中在第5個特征向量元素處有明顯的峰值,因此,判斷第5個節點出現故障的概率最大。

為進一步驗證本文算法的異常檢測效果,本文選取了在WSN中典型的分布式故障檢測(Distributed Fault Detection,DFD)算法[21]與本文算法在異常節點檢測準確率上進行對比。對比實驗中采用IBRL網絡中1號～50號傳感器節點在1 000個采樣時刻內收集的溫度數據,隨機設置異常時刻和異常節點,使用2種算法分別對文中設計的4種異常類型各進行5 000次測試,所得異常節點定位準確率如圖3所示。可以看出,DFD算法的異常節點定位準確率低于本文算法。

圖3 單個異常節點定位準確率對比Fig.3 Location accuracy comparison of one abnormal node

此外,對多個節點出現異常情況進行定位。檢測前對原始數據在550～650和250～350時間段內向第5個和第15個節點分別人工注入類型1和類型4這兩種異常,根據2.2節方法進行檢測,仿真結果如圖4所示。可以看出,圖4(b)和圖4(c)在第5個元素和第15個元素分別出現了峰值點,且有較大的峰均比,而圖4(a)和圖4(d)中的峰均比都較小,由2.2節中的分析可知,第5個節點和第15個節點極有可能是異常節點。仿真結果與實驗前人工注入的異常條件相符。

在多個異常節點的定位對比實驗中,本文使用與之前對比實驗同樣的溫度數據集,在所有節點中隨機選取2個節點和2個時刻作為異常節點和發生異常的時間,依次選取異常類型表中類型1～類型4進行任意組合,共6種組合,使用本文的算法和分簇式DFD算法均進行5 000次的測試,并對比2個算法對多個異常節點定位的準確率,結果如圖5所示。可以看出在本文所設計的算法在多個異常節點且存在多種異常類型的情況下,檢測效果優于DFD算法。

圖4 多個異常節點情況下的特征向量元素分布

Fig.4 Distribution of eigenvector elements with multiple abnormal nodes

對本文算法和DFD算法的誤警率進行對比,實驗中不注入任何異常類型而只是存在普通噪聲,結果如表2所示。仿真結果表明,本文設計的異常節點定位算法在異常節點的定位上性能優于經典的DFD算法,證明了本文算法的有效性與優越性。

圖5 2個異常節點定位準確率對比Fig.5 Location accuracy comparison of 2 abnormal nodes

表2 異常節點定位誤警率對比

Table 2Experimental result comparison of abnormal node location%

算法誤警率本文算法1.13DFD算法2.04

4 結束語

為從海量數據中快速有效地檢測出異常情況并定位異常節點,本文設計一種基于隨機矩陣理論的無線傳感器異常節點定位算法。實驗結果表明,在不同異常情況下，該算法均可以實時有效地檢測出異常事件并定位異常節點，其檢測性能優于DFD算法,在高維數據中具有較好的適用性。下一步將針對存在多類型節點和異構數據的復雜情況對本文算法進行優化。