謝麗霞，田宇祺

(中國民航大學 計算機科學與技術(shù)學院，天津 300300)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)中每個節(jié)點可以用于監(jiān)視封閉環(huán)境中的物理數(shù)據(jù)，并將數(shù)據(jù)存儲起來，通過自組織網(wǎng)絡(luò)發(fā)送到基站[1]。

傳感器節(jié)點的功率和計算能力等因素的固有限制使傳感器節(jié)點易產(chǎn)生故障，或受到攻擊[2]。因此必須識別WSN中的異常節(jié)點，及時進行網(wǎng)絡(luò)維護以提供可靠和安全的網(wǎng)絡(luò)功能。WSN中的異?？赡苁怯删W(wǎng)絡(luò)中的傳感器發(fā)生故障、攻擊者的攻擊/入侵引起，通過分析網(wǎng)絡(luò)中與流量相關(guān)的屬性值來識別[3]。

在數(shù)據(jù)挖掘和機器學習領(lǐng)域中異常識別被廣泛研究。異常識別一般可分為3種方法，第一種方法是使用無監(jiān)督學習發(fā)現(xiàn)異常。Liu等[4]提出一種基于k-均值分類算法的節(jié)點識別方法，該方法通過梯度下降和支持向量機兩種算法計算節(jié)點信譽值以識別異常節(jié)點，該方法缺點是識別時間過長。第二種方法是使用監(jiān)督分類，如常琳等[5]提出一種基于數(shù)據(jù)驅(qū)動的異常識別算法，該算法利用交叉窗口的故障權(quán)重識別異常，但該方法僅針對故障異常。Nesrine Berjab等[6]設(shè)計一種基于事件-條件-動作規(guī)則和模糊邏輯理論的無線傳感器網(wǎng)絡(luò)異常節(jié)點識別算法，但當數(shù)據(jù)量過大時，該方法的異常節(jié)點識別率可能會降低。第三種方法是新穎性識別。Kanev等[7]搭建一種基于人工神經(jīng)網(wǎng)絡(luò)的異常識別方法，該方法的缺點是需要大量計算。Lopez valcarce等[8]通過最大似然方法來解決噪聲數(shù)據(jù)和矩陣補全問題以識別異常節(jié)點，但其攻擊的識別精度不高。

上述類型的算法計算量太復雜，無法在內(nèi)存和功率受限的傳感器節(jié)點中執(zhí)行。因此，需要考慮到傳感器網(wǎng)絡(luò)對異常識別的局限性，研究新的算法。

本文提出一種基于重要性分數(shù)的CUR低秩矩陣分解WSN異常節(jié)點識別方法。該方法可更好擬合網(wǎng)絡(luò)數(shù)據(jù)固有的低秩屬性，且對于網(wǎng)絡(luò)數(shù)據(jù)的缺失和噪聲具有較強的魯棒性。本文的創(chuàng)新點主要為以下兩點：①使用一種改進的CUR矩陣分解方法，具體操作是在初始化矩陣時根據(jù)重要性分數(shù)構(gòu)造矩陣C、矩陣U、矩陣R。②增加參數(shù)ρ，通過計算候選列與選擇列的相關(guān)性，選擇相關(guān)性小的候選列構(gòu)造矩陣。

1 異常節(jié)點識別模型設(shè)計

具體處理流程如圖1所示。

圖1 異常節(jié)點識別模型

(1)數(shù)據(jù)獲取與處理

獲取無線傳感器網(wǎng)絡(luò)的節(jié)點流量數(shù)據(jù)，去除數(shù)據(jù)中明顯異常值并進行歸一化處理，然后將處理后的數(shù)據(jù)輸入到下一模塊進行屬性矩陣重構(gòu)。

(2)CUR矩陣分解

首先將輸入的數(shù)據(jù)構(gòu)建為屬性矩陣X。然后基于改進的CUR矩陣分解模型，利用重要性分數(shù)將屬性矩陣X分解為矩陣C、矩陣U、矩陣R這3個矩陣，將3個矩陣相乘得到重構(gòu)的正常矩陣Y，其中矩陣C、矩陣R是從X的行和列中根據(jù)相關(guān)性選擇的元素組成。最后使用殘差算法對屬性矩陣和重構(gòu)矩陣進行殘差計算，求出異常矩陣A。

(3)異常節(jié)點識別

根據(jù)異常矩陣A中節(jié)點向量的期望和標準差構(gòu)建休哈特控制圖。圖中中線的中心值為列向量的期望，上下控制限為中心值加減標準偏差，以此根據(jù)異常矩陣A來捕獲屬性矩陣與重構(gòu)矩陣之間的差異，利用上下控制限之間的閾值為標準來判斷節(jié)點是否發(fā)生異常[9]。

2 CUR矩陣分解模型構(gòu)建

UTXV=∑=diag(σ1，σ2，…σρ)

(1)

此處∑∈Rd×p，ρ=min{d，p}， 同時，diag(·)表示一個對角線上帶有指定元素的對角線矩陣。等效于X=U∑VT， 3個矩陣U、V以及X構(gòu)成∑。σi是X的奇異值，向量ui和vi分別是第i個左和第i個右奇異向量。

2.1 屬性矩陣構(gòu)建

無線傳感器網(wǎng)絡(luò)數(shù)據(jù)流在被監(jiān)測的過程中，若某節(jié)點的流量數(shù)據(jù)出現(xiàn)偏差，則該節(jié)點可被認為狀態(tài)異常。在無線傳感器網(wǎng)絡(luò)中通常監(jiān)測轉(zhuǎn)發(fā)率、接受率以及流量數(shù)來識別節(jié)點的異常表現(xiàn)。3個特征屬性具體含義和選擇原因如下。

特征屬性1 轉(zhuǎn)發(fā)數(shù)：轉(zhuǎn)發(fā)數(shù)是在固定時間內(nèi)某節(jié)點將所獲得的數(shù)據(jù)成功轉(zhuǎn)發(fā)時所通過的流量數(shù)。在WSN中，傳感器會相互發(fā)送數(shù)據(jù)信號，節(jié)點異常時會發(fā)生數(shù)據(jù)轉(zhuǎn)發(fā)異常，因此該屬性是判斷節(jié)點異常的重要依據(jù)。

特征屬性2 接收數(shù)：接收數(shù)為在固定時間內(nèi)某節(jié)點完整接收到其它節(jié)點數(shù)據(jù)時通過的流量數(shù)，與丟包率類似，但在網(wǎng)絡(luò)環(huán)境沒有受到攻擊和損壞的情況下，節(jié)點的丟包率會接近0。

特征屬性3 流量數(shù)：流量數(shù)為某固定時間間隔內(nèi)節(jié)點通過的流量。該指標反映節(jié)點總體流量走向，同樣可作為判斷節(jié)點是否異常的依據(jù)。

本文所提出的異常節(jié)點識別算法，將從收集的網(wǎng)絡(luò)節(jié)點流量數(shù)據(jù)中提取出3個特征屬性值構(gòu)建屬性矩陣Xd×p。p是網(wǎng)絡(luò)傳感器節(jié)點的數(shù)量，并且因為節(jié)點的異?？赡軙诙鄠€時間周期中有所表現(xiàn)，所以算法在識別某一周期的異常節(jié)點時，會將該周期的前一個周期和后一個周期節(jié)點的特征屬性值與該周期的屬性值同時作為矩陣的列向量，以保證精確識別異常。Xij表示第j個節(jié)點中的第i個屬性值。

2.2 CUR矩陣分解

構(gòu)建屬性矩陣X后，對X進行矩陣分解以提取矩陣中的正常成分，并將分解后提取的正常成分重構(gòu)為一個與屬性矩陣X盡可能相近的正常矩陣Y，其中重構(gòu)的矩陣Y代表矩陣X的主模式。然后將矩陣X與矩陣Y做殘差運算，可以得到異常矩陣A，A能夠反映X的異常成分，進而反映無線傳感器網(wǎng)絡(luò)節(jié)點的異常變化，該部分實現(xiàn)過程如式(2)所示

(2)

在矩陣分解時使用CUR分解方法，提取的正常成分將由矩陣C、矩陣U、矩陣R構(gòu)成，三者計算得到矩陣Y，代入式(2)中，結(jié)果如式(3)所示

(3)

矩陣在分解過程中，往往會存在訓練過擬化的問題。為解決此問題，在公式中引入L2-1范數(shù)和F范數(shù)，將其代入式(3)，基于相關(guān)性的CUR低秩矩陣分解模型如式(4)所示

(4)

式(4)中，CUR組成的矩陣Y代表無異常情況下的節(jié)點數(shù)據(jù)，矩陣A為異常矩陣。其中L2-1范數(shù)和F范數(shù)的公式如式(5)、式(6)所示

(5)

(6)

因此，對于屬性矩陣X=[X1，X2，…，Xp]， CUR的目標就是將X矩陣分解為3個矩陣C、U、R后得出異常矩陣A，并滿足式(4)。

2.3 基于SVD改進的CUR矩陣分解

為構(gòu)造C(R類似)，本文將為X的每一列計算一個“重要性分數(shù)”，并將該分數(shù)作為重要性抽樣概率分布從X中隨機抽樣少量列。在CUR矩陣分解中利用診斷回歸分析作為探索性數(shù)據(jù)分析的工具。

為激勵選擇的重要性抽樣分數(shù)，矩陣X的第j列可以表示為下式

(7)

其中，r=rank(X)，vξj是第ξ個右奇異向量的第j個坐標的元素值。即X的第j列是所有左奇異向量和奇異值的線性組合，V的第j行的元素是系數(shù)。因此，可以將Xj近似為左上k個奇異向量和相應的奇異值的線性組合

(8)

因為尋找的X列同時與所有右上k個奇異向量的跨度相關(guān)聯(lián)，所以計算歸一化的統(tǒng)計分數(shù)為

(9)

(1)計算v1，…，vk和等式的標準化統(tǒng)計杠桿得分；

(2)保持X第j列的概率為pj=min{1，cπj}；

(3)根據(jù)概率Pj返回由X的選定列組成的矩陣C。

在這個過程中，矩陣C包含c′列，其中c′≤c在期望中，c′緊密集中在期望周圍。列分數(shù)使用X的右上k個奇異向量進行計算，這種計算容易成為列選擇運行時間的瓶頸。在秩參數(shù)k(1)中，矩陣X的非零元素乘以低次多項式的時間可以呈線性關(guān)系。已經(jīng)驗證在列的選擇中至少99%的概率可以滿足式(10)

(10)

計算CUR矩陣分解的主要算法以任意d×p矩陣、秩參數(shù)和誤差參數(shù)作為輸入?yún)?shù)，然后執(zhí)行以下步驟：

(1)在X上運行列選擇算法構(gòu)造矩陣C；

(2)在XT上運行列選擇算法構(gòu)造矩陣R；

(3)將矩陣U定義為U=C+XR+， 其中C+表示矩陣C的廣義逆。

與列選擇算法一樣，上述算法的運行時間主要由列和行的分數(shù)的計算決定。對于C，U和R的構(gòu)建，可以通過下式驗證

(11)

2.4 相關(guān)性程度判斷

矩陣C的列和矩陣R的行是用于生成數(shù)據(jù)矩陣的基本向量，這些基本向量之間的相關(guān)性越低，向量的表示性越好，因為選擇具有高相關(guān)性的兩列意味著選擇相同的基礎(chǔ)向量，所以在根據(jù)重要性分數(shù)選擇X的列向量構(gòu)造矩陣C、R時，需要計算每個候選列與先前選擇的列的相關(guān)性，只有相關(guān)性程度小于參數(shù)δ時，才選定該候選列組成矩陣C或矩陣R。Pearson系數(shù)是衡量向量相似度的一種方法，輸出范圍為[-1，1]，0表示不相關(guān)，負值表示負相關(guān)，正值表示正相關(guān)。由于分解過程只需要判斷向量的相關(guān)性程度，因此對該系數(shù)取絕對值，那么對于矩陣中候選列向量S=[S1，S2，…，Sn] 與已被選定組成分解矩陣的向量L=[L1，L2，…，Ln]， 本文中選擇Pearson相關(guān)性系數(shù)計算向量的相關(guān)性程度，公式如下

(12)

其中，μ表示均值，σ表示方差，E()表示期望。

2.5 算 法

在本文中使用基于重要性分數(shù)改進的CUR方法進行矩陣分解，其具體算法見表1。

表1 構(gòu)建改進過的CUR方法進行矩陣分解

上述算法主要解決C、U、R矩陣初始化構(gòu)造問題。在算法中，初始的矩陣R是從矩陣X的多個實際行中選擇重構(gòu)而成，初始的矩陣C列是從屬性矩陣X的實際列中選擇重構(gòu)而成，并且U是一個低秩的矩陣。該方法步驟如下：

(1)計算矩陣列向量的重要性分數(shù)，并根據(jù)重要性分數(shù)從屬性矩陣X中選定組成矩陣C、R的候選列。

(2)在根據(jù)重要性分數(shù)選定某候選列后，計算候選列和已被選定組成矩陣的列項的相關(guān)性程度，若相關(guān)性程度低于閾值參數(shù)ρ，才可將該候選列選為新矩陣的列向量。選定指定數(shù)量的列后輸出矩陣C、矩陣R。

(3)根據(jù)矩陣C、R利用矩陣分解模型中的公式計算矩陣U和矩陣A。

2.6 優(yōu)化訓練

初始化矩陣后，采用交替更新的方法，對矩陣U和異常矩陣A進行進一步訓練優(yōu)化。方法為固定其中一個矩陣，代入式(4)進行求導，并使求導結(jié)果為0，求得更新后的矩陣后交替優(yōu)化另一個矩陣。具體方法描述如下：

(1)固定U矩陣更新A矩陣。當U矩陣固定時，式(4)對于A矩陣來說為凸函數(shù)，可以表示為式(13)

(13)

對式(13)的A進行求導，并令結(jié)果等于零得式(14)，可求得矩陣A

X-A-CUR-αDRA=0

(14)

(2)固定A矩陣更新U矩陣。當A矩陣固定時，式(4)對于U矩陣來說為凸函數(shù)，可以表示為式(15)

(15)

對式(15)的U求導并令結(jié)果等于零得式(16)

CTCURRT-CTART-CTXRT+λD′UU=0

(16)

3 異常節(jié)點識別

將矩陣X分解之后，得到的異常矩陣A為稀疏矩陣，矩陣A為屬性矩陣X的異常部分。當各個測量周期，采取均值、標準差或者極差作為統(tǒng)計信息時，節(jié)點存在異常的測量周期與正常的測量周期在對應矩陣列向量之間的差別就表現(xiàn)為二者統(tǒng)計信息之間的差別[10-12]。該差別可用休哈特控制圖捕捉到。

根據(jù)中心極限定理的理論，假設(shè)正常節(jié)點的屬性向量服從正態(tài)分布，那么可以通過矩陣A中列向量的均值和方差設(shè)置休哈特控制圖里的上中下3條控制限，其中中線的中心值取值為列向量的期望，上下控制限的取值為中心值加減標準偏差，以控制限為標準判斷節(jié)點是否發(fā)生異常。如果某個節(jié)點的統(tǒng)計數(shù)據(jù)超過上控制限或低于下控制限，則認為該節(jié)點發(fā)生異常。

(17)

(18)

(19)

(20)

其中，d3/d2是極差標準差的無偏估計，E(R)表示期望，D(R)表示方差，CL為中心線，UCL和LCL為上下控制限。計算得到UCL以及LCL后，如果某個節(jié)點向量的均值超過UCL或者低于LCL，那么這個節(jié)點就被判斷為異常節(jié)點。

4 實驗結(jié)果分析

基于MATLAB 2018a平臺模擬還原無線傳感器網(wǎng)絡(luò)模型，并收集仿真的節(jié)點流量屬性數(shù)據(jù)，以識別率和誤測率為指標，分析檢驗本文算法的性能并與其它算法進行對比。

4.1 實驗結(jié)果對比

仿真過程中運用PEGASIS路由算法來降低能量消耗，減少能量不足對算法的影響。為節(jié)省能源，在一個區(qū)域中不均勻的部署一些節(jié)點，最好的方法是讓很少的節(jié)點識別周圍的環(huán)境而不失去精度。無法決定網(wǎng)絡(luò)在睡眠狀態(tài)中優(yōu)先從哪個節(jié)點喚醒時，優(yōu)先選擇喚醒來自網(wǎng)格單元的頭部節(jié)點，其中網(wǎng)格單元由ID表示。網(wǎng)絡(luò)部署和識別的主要過程如下：①頭節(jié)點循環(huán)識別活動鄰居節(jié)點的濃度；②如果濃度值超過閾值，這些節(jié)點需要激活它們的鄰居(如果它們的鄰居被激活，則無需再激活它們)，鄰居繼續(xù)識別并重復相同的工作；③如果一個節(jié)點及其所有活動鄰居的濃度正常，節(jié)點應進入睡眠模式；④讀數(shù)異常的節(jié)點向接收節(jié)點發(fā)送信息。圖2為仿真的部分節(jié)點的分布圖。

圖2 仿真節(jié)點分布

其中總體節(jié)點分布為：x坐標水平方向為-50 m～350 m，y坐標垂直方向為-50 m～350 m，它們的時間間隔均是30 min。

采集數(shù)據(jù)時，以30 min為一個周期，并對接收和發(fā)送的數(shù)據(jù)以及流量數(shù)據(jù)進行數(shù)值歸一化處理。預處理后模擬的無線傳感器網(wǎng)絡(luò)流量近似正常情況下的流量，分布呈周期性分布，如圖3所示。從網(wǎng)絡(luò)流量的角度出發(fā)，向個別節(jié)點(即矩陣列向量)人工注入一定規(guī)則的異常，添加的異常主要分為外部攻擊、內(nèi)部攻擊和能耗異常，注入異常后的流量分布如圖4所示。對添加異常后的節(jié)點數(shù)據(jù)提取特征屬性值，最終生成原始節(jié)點屬性矩陣X。

圖3 原始流量

圖4 加入異常后的流量

根據(jù)本文所提出的算法，在對矩陣X進行矩陣分解后將使用休哈特控制圖確定網(wǎng)絡(luò)異常節(jié)點，如果某個測量點的統(tǒng)計值超過UCL或者低于LCL，那么這個節(jié)點就被判斷為異常節(jié)點，休哈特圖識別結(jié)果如圖5所示。

圖5 異常節(jié)點識別結(jié)果

為驗證本算法的有效性，分別采用4種算法進行實驗，然后與本文模型的識別結(jié)果作對比。4種算法分別是傳統(tǒng)的主成分分析法PCA[13]、非負矩陣分析方法NMF[14]、改進的PGNMF方法[15]和最新的基于閾值測量算法[16]。具體結(jié)果如圖6、圖7所示。

圖6 5種算法的識別準確率對比

圖7 5種算法的誤報率對比

本文的算法與其它4種算法的檢測準確率比較結(jié)果如圖6所示。從圖6可以看出，當節(jié)點故障率在0.05～0.3之間時，5種算法的檢測準確率相差不大，都能達到0.96以上，這是由于大部分噪聲都在時間關(guān)聯(lián)性識別階段被過濾掉了；當節(jié)點故障率大于0.3時，5種算法的檢測準確率都明顯下降，但本文所采用的算法(圖中為上三角)要明顯優(yōu)于其它4種算法。這主要是因為5種算法都有空間關(guān)聯(lián)性識別階段，隨著故障率的增加，異常節(jié)點容易受到未識別到異常事件的鄰居節(jié)點的影響，轉(zhuǎn)換為正常狀態(tài)，從而被誤認為沒有異常事件發(fā)生的正常節(jié)點。因為本文算法受鄰居節(jié)點影響小，所以檢測準確率比其它方法高。

在誤報率方面，本章算法與其它4種算法的比較結(jié)果如圖7所示。從圖7中可以看出，隨著節(jié)點異常率的升高，本文所采用的算法的誤報率明顯低于其它4種算法，這是因為該算法充分考慮非時空屬性關(guān)聯(lián)對異常事件識別的影響。通過屬性關(guān)聯(lián)置信度的計算可以判定待識別點與樣本數(shù)據(jù)屬性關(guān)聯(lián)模型的相似程度，從而有效地區(qū)分異常事件和干擾因素。

4.2 算法復雜度對比

本文算法主要包括兩個步驟：CUR低秩矩陣分解和休哈特控制圖識別異常節(jié)點。CUR低秩矩陣分解，①矩陣構(gòu)建的復雜度為O(dp)；②CUR矩陣分解，進行次數(shù)為k2的模型訓練迭代，所以該步驟復雜度為O(k2vdp)， 其中：d為特征屬性的數(shù)量，p為傳感器節(jié)點的數(shù)量，v為分解子矩陣的空間維數(shù)；因此CUR低秩矩陣分解的時間復雜度為O(dp)+O(k2vdp)=O(k2vdp)。 休哈特控制圖識別異常節(jié)點，①統(tǒng)計信息計算的時間復雜度為O(dp)； ②控制限設(shè)置，只進行數(shù)據(jù)賦值為O(1)；③異常節(jié)點判斷，時間復雜度為O(p)； 因此休哈特控制圖識別異常節(jié)點的時間復雜度為O(dp)+O(1)+O(p)=O(dp)。

因此本文方法總時間復雜度=O(k2vdp)+O(dp)=O(k2vdp)， 對比實驗中其它幾種方法的時間復雜度如下：PCA方法的處理復雜度為O(dp2)，NMF方法的復雜性為O(k1vdp)，k1為該方法模型訓練時的迭代次數(shù)，PGNMF方法的復雜性為O(k1dv2)。因為本文引入范數(shù)，對模型訓練次數(shù)進行控制，防止過擬化，所以模型訓練的迭代次數(shù)k2

5 結(jié)束語

本文提出了一種基于改進CUR低秩矩陣分解的無線傳感器網(wǎng)絡(luò)異常節(jié)點識別方法，該方法利用網(wǎng)絡(luò)屬性特征、重要性分數(shù)和相關(guān)度參數(shù)改進CUR矩陣分解，使分解后的異常矩陣能更加精準地用來識別節(jié)點異常，為WSN中異常節(jié)點的識別提供了一種新的思路。仿真實驗數(shù)據(jù)驗證了該方法的可行性，與其它傳統(tǒng)和新穎的異常識別方法相比，本文算法具有更高的異常識別率，并且穩(wěn)定性更佳。由于目前提出的基于改進CUR低秩矩陣分解異常節(jié)點識別方法不具備實時性，下一步要改進數(shù)據(jù)輸入形式，達到實時識別的目的。