傳感器網絡定位中節點攻擊類型的分布式識別算法

王夙喆, 李勇, 程偉, 王道平

(西北工業大學 電子信息學院, 陜西 西安　710072)

?

傳感器網絡定位中節點攻擊類型的分布式識別算法

王夙喆, 李勇, 程偉, 王道平

(西北工業大學 電子信息學院, 陜西 西安710072)

摘要：針對無線傳感器網絡在定位過程中的外部攻擊節點的類型識別問題，提出了一種交替方向-Lp范數支持向量機(ADM-PSVM)分布式識別算法。該算法基于線性支持向量機分類模型，首先引入了Lp范數約束形式，通過選擇不同的范數值p以增強分類算法對數據集的適應能力；繼而根據交替方向乘子方法推導出了算法的分布式形式，實現了節點根據剩余能量將識別的計算任務分布于不同節點之間進行；最后將算法對各類型的惡意節點數據進行了訓練及識別仿真，并討論了范數約束值以及懲罰因子取值的不同對識別精確率的影響。仿真結果表明，該算法對于惡意外部攻擊節點數據具有較好的識別精確度及更高的計算效率。

關鍵詞：分布式；支持向量機；傳感器網絡；p范數；定位；識別

在無線傳感器網絡(wireless sensors network,WSN)中，節點的位置信息無論對于環境監測和預報、目標跟蹤等實際應用領域，還是基于地理位置的拓撲結構控制、路由算法等協議都起著重要的作用。但在實際應用中，傳感器節點通常被布置于無人維護或者維護較困難的物理環境下，節點的定位過程容易受到來自內部或是外部的攻擊，導致WSN產生錯誤或無效的定位結果[1]。

網絡節點受到攻擊的形式可以分為內部、外部攻擊2種。內部攻擊是攻擊者通過俘獲節點來獲得信息密鑰等信息，可以通過數據加密等方式進行防范；外部攻擊是指惡意節點通過在物理和鏈路層上采用阻擋、反射等手段對信號進行干擾，或者在網絡層采用重放、篡改報文的方式制造假象，典型的攻擊方式有移位、重放、阻塞、蟲洞攻擊等，而常規的基于加密或變頻等安全機制難以防御上述類型的攻擊[2]。近年來，研究者提出了許多節點安全定位及惡意節點的檢測算法，見文獻[3]。然而，這些方法只是將惡意節點造成的影響降低或是檢出后剔除，并沒有對其攻擊的類型進行后續的分析及識別，從而為以后有針對性地處理位置攻擊事件，有效保障網絡安全帶來了不利影響。

支持向量機(support vector machine, SVM)是一種基于統計學習理論的分類算法，由于在分類問題的良好表現，已被應用于無線傳感器網絡領域的識別和檢測問題。文獻[4]基于SVM提出了一種入侵檢測算法，該系統把網絡拓撲分成簇頭、簇成員和Sink 3層結構，每層均能根據SVM的訓練結果進行入侵檢測的判斷。文獻[5]利用SVM算法能夠在高維空間對非線性樣本進行分類的優點，通過各傳感器節點估測其與錨點間的距離作為特征向量，最終對未知節點所屬立方體空間進行分類來實現定位未知節點。以上算法都是集中式求解的，如果應用于能量與計算能力均受到限制的傳感器網絡，會出現大批節點的能量耗盡并失效；而且基于傳統向量機分類器，對于不同數據的適應性較差。因此，研究具有高效識別能力，并能根據數據特征靈活改變的分布式算法具有重要的現實意義。

本文設計了一種分布式的交替方向-Lp范數支持向量機(ADM-PSVM)定位攻擊類型識別算法。該算法將p范數支持向量機作為識別的核心算法，通過引入分布式計算中的交替方向乘子法，將其計

算過程分布于網絡的不同檢測節點，再利用鄰居節點的位置、能量信息將迭代過程進行傳遞。由于該算法充分利用了支持向量機分類器優良的分類特性，同時也利用了ADMM迭代快速的特性，因此能在分布式的網絡環境中對定位中的攻擊行為進行準確而快速的識別。

1WSN定位攻擊識別模型構造

1.1WSN定位攻擊特點分析

假設網絡中存在n個未知節點S1,S2,…,Sn,每個節點的實際位置表示為(xSi,ySi),i=1,2,…,n;另外有m個錨節點B1,B2,…,Bm,每個錨節點的位置表示為(xBj,yBj),j=1,2,…,m。未受到攻擊時,某一未知節點S1在通信范圍內共存在未知節點p個,錨點q個,因此計算出S1到未知節點及錨點之間的距離估計值分別為di,i=1,2,…,p,dj,j=1,2,…,q。

本文以未知節點S1定位過程中,受到4種外部攻擊而成為惡意節點A1為例,逐類分析其節點間距離以及鄰居節點信息的變化。①重放攻擊時,惡意節點A1將錨節點B1發往未知節點S2、S3的位置數據截取之后,隨后重新發給它們,誤讓S2、S3認為A1是錨節點B1,而原來節點S1的ID信息不廣播,其他鄰居節點將不再發現S1。②在蟲洞攻擊中,攻擊方在距離S1較遠的某一個位置通過一個低延遲的連接接收錨節點以及未知節點發來的位置與距離信息,并在A1處重放它們,此時A1增加的距離信息分別為di,i=p+1,p+2,…,p+u,dj,j=q+1,q+2,…q+v。③阻塞攻擊時,在節點A1周圍通過阻擋等手段削弱錨節點Bj發送至其他節點S2、S3的信號強度,使B1到錨節點之間的距離dj增加,并使A1與其相鄰所有節點的信號強度減弱或是消失。④移位攻擊即攻擊者重新放置未知節點S1,導致S1的距離信息di,i=1,2,…,p,dj,j=1,2,…,q的取值重新改變。

經上述分析可知各種攻擊類型對于未知節點S1與其他未知節點或是錨節點的距離均會產生一定程度影響。將這些含有攻擊特征的數據投射到一個二維平面后,如果能找到幾條直線可以將這幾類數據分開,那么這些直線就相當于最優分類平面,攻擊類型識別問題進而可以轉化為求解多個受約束的凸二次規劃問題。本文根據以上分析,基于支持向量機和分布式迭代算法,研究在WSN網絡環境下,根據數據類型的不同且依賴相鄰節點間相互協作的分布式識別攻擊類型的方法。

1.2基于線性支持向量機的分類模型

在一個有限空間Rn里,假定有n個已標記的訓練樣本,其樣本集表示為{xi,yi},其中xi∈RN,yi∈{1,-1},i=1,2,…,n。在線性可分情況下,SVM的目的就是找到一個最優超平面,能將數據集中的2類樣本完全分開并使2類數據點到超平面的間隔最大,尋找該最優分類面的問題可轉化為以下最優問題[6]:

(1)

式中,C是懲罰因子,ξi為松弛系數,引入Lagrange乘子αi,并將原問題(1)式轉化為如下的凸二次規劃的對偶形式:

(2)

1.3分布式交替方向乘子迭代算法

對于具有可分結構的凸規劃問題,其模型如下:

(3)

交替方向乘子法按照如下順序依次更新變量w、z以及乘子u,第k次的各個變量迭代更新步驟為[7]:

(4)

(5)

(6)

2分布式p范數支持向量機分類算法

本文在(2)式和(5)～(7)式的基礎上進行改進,首先加入Lp范式約束, 其中0

(7)

改寫之后,問題(7)將可以用2個節點求解,因為等式約束保證了任何一個節點優化得到的可行解與另外一個節點的解一致。因此,將其中的一項進行改寫后,得到

(8)

依據交替方向乘子法,第k次迭代步更替步驟可以寫為:

(9)

(10)

(11)

如同在集中式SVM的情況下,問題(8)將通過其對偶問題解決,為了達到這個目標,引進拉格朗日乘子α(k),并根據文獻[8],(9)對應的增廣拉格朗日函數為

(12)

(13)

在算法實現過程中,一旦解出w1(k-1),即將V=|w1(k-1)|p-2作為下一次迭代的目標函數中V=|w1(k)|p-2的近似值代替,這樣每一次迭代依然是標準的二范數SVM優化問題,而在初次迭代中,任意置一個初值或由二范數SVM作為w1(0)的初值;另外,由于0

根據KKT條件,得到

α(k)+ηw1(k+1)=0

(14)

把上述條件代入L′({w1(k)},{ξin(k)},{av2(k)}{α1(k)}),其對應的對偶問題可以表示為:

(15)

同理,(10)式對應的拉格朗日函數為

(16)

其對偶問題可以表示為:

(17)

{y}X-α(k)](U-η)-1[σ2diag{y}XT-α(k)],然后2個節點與輸入的樣本訓練集{xi,yi}更新其對偶問題的σi1(k)、σi2(k)值,繼續再計算w1(k)、v2(k)的值,當計算完成后,將σi1(k)、w1(k)賦值于節點2,最后更新出α(k+1)。這時根據轉發規則,如果2個節點的剩余能量都大于其初始能量比較的閾值時,其繼續進行k+1輪迭代,否則,將選擇一個距離低于能量閾值節點距離更近且具有更高能量水平的鄰居節點,向其傳遞σi2(k)、v2(k)、α(k+1)值,同時,原來的第2個節點就變成了第1個節點,負責迭代計算σi1(k+1)、w1(k+1)。

圖1　節點迭代計算示意圖

3實驗仿真與結果分析

3.1仿真設置及訓練、測試樣本獲取

為檢驗ADM-PSVM算法的有效性,在MATLAB里對了定位攻擊場景進行模擬。假設將600個未知節點以及150個信標節點隨機部署點到300m×300m的區域,每個節點的剩余能量分配為隨機值,通信半徑設置為20m,其定位機制采用文獻[9]提出的非測距MDS-MAP算法。按照以下步驟產生識別所需的訓練及測試數據集:

1)將網絡探測區域劃分成邊長為60m的網格單元,使每個網格平均覆蓋2～3跳范圍內的節點。

2)未受攻擊條件下,利用最短路徑法分別計算網格內部各未知節點間以及未知節點與信標間的相異性矩陣B1、B2,相異性矩陣定義為B=-JD2J/2,其中D為各節點間平方距離矩陣,J=E-N-1gI,E為N階單位矩陣,g=IT,I為N階全一矩陣。每個節點依序號取B1、B2中對應的一行共同構成向量Xnor。

3)從未知節點中取120個節點作為惡意節點,劃分為移位、重放、阻塞、蟲洞攻擊4種類型并實施攻擊,在干擾環境下重新計算相異性矩陣,并將節點得到的新一組向量定義為Xatt。

4)以2種環境下產生的相異性矩陣的差的絕對值Xtest=|Xnor-Xatt|形成一組訓練特征向量。

5)重復步驟1～4,將形成的向量作為測試樣本。

實驗中,將上述數據集生成步驟重復5次,總共產生6 000組樣本,其中訓練樣本和測試樣本各占50%。為了將本算法應用到多類型攻擊識別問題,本文采用目前應用比較廣泛的1-v-1-SVM多類識別結構[1]。懲罰因子C=1,η=1,而范數值p對于各類型攻擊識別時,從初值0.2,終值2,以等差增加0.2的方式,依次進行測試。

3.2實驗結果與分析

ADM-PSVM算法和C-SVM算法對訓練集測試樣本的識別結果如表1所示,其中ADM-PSVM的識別率取所有范數p值下正確識別樣本數與測試樣本數之比之中的最大值。由表1可以看出,本文提出的算法比傳統的標準C-SVM算法具有更好的識別精度。由于本文方法采用范數作為約束條件,不但控制了最優化問題解的稀疏性,也有效選擇了與相應攻擊類型標簽高度相關的特征向量,減小了識別錯誤率;同時對目標函數使用較低階次的范數約束,降低了原優化問題對異常值的敏感性,相比起傳統的SVM方法,ADM-PSVM避免了個別測距噪聲的影響,具有更優優越的性能;在算法訓練時間方面,本文提出的算法明顯少于C-SVM的訓練數據,尤其是當訓練數據量較大時,使用ADM-PSVM有明顯優勢。對于2種算法均在識別過程中出現誤差,經分析有以下影響因素:(1)網絡測距誤差。識別結果中有很多隨機產生的無規律識別錯誤,這些都是由于在估計每對節點距離時,其采用的是最短路徑算法,導致在節點分布不均勻的網絡中測量距離與實際距離的偏差較大,所引起的相異性矩陣誤差所導致。(2)特征樣本采集不全。某一種攻擊類型被識別為另一種是由于在訓練樣本獲取階段,網格的劃分隔離了某些攻擊類型的影響區域,特征向量無法完全獲取所有遭受攻擊的節點的數據。

表1　ADMM-SVM和SVM分類器準確率和訓練時間比較

圖2分別給出了惡意節點數目從120增加至180時,各范數p值對應的所有類型節點的識別準確率。從圖2a)、b)顯示的結果可以看出,從整體上,對于不同數目惡意節點的攻擊環境下,ADM-PSVM算法在p∈[0.2,1.4]或p∈[0.2,1.6]時,對于各類型節點的識別準確率隨著p值的增加而逐漸升高;而在其余的范圍內,均出現一定幅度下降,在p=2時,其下降幅度最大。以圖2a)中的重放攻擊識別為例,算法從0.2增加到0.8時,其識別率僅僅增長了2%,在p=1.4時,識別率增長到最大值91.67%,原因是較低的范數值降低了目標函數對測試集中異常值的敏感性,避免了類似測距誤差的影響。但是當范數值選取過大時,當p=2,目標函數選擇了所有特征,包含了其他無關的特征以及噪聲,導致識別的準確率下降到80%。另外從圖2b)可以看出,在節點總數不變的情況下,當惡意節點的數目增加到180時,各個類型的訓練樣本數目也相應增加,使分類器獲得了更多的判別信息,提高了分類器的整體識別準確率。

圖3分別給出2個范數值p約束下,帶有不同懲罰因子η的ADM-PSVM算法對于蟲洞攻擊訓練樣本的經驗風險誤差的影響,惡意節點數目為120。從圖3各子圖可以看出:2幅圖的誤差收斂曲線趨勢相似,并且當范數值p=1.6時,ADM-PSVM算法的分類經驗風險誤差較p=1時有所下降;其次,算法在η=2時,經過了一小段迭代后,分類器的經驗風險誤差開始逐漸趨于平穩。但是當η值過大時,不僅經驗風險誤差有所上升,且收斂迭代過程不平穩,迭代曲線出現了明顯波動,這表示分類器出現了過度擬合訓練數據的現象。雖然ADM-PSVM算法對于η的所有取值均會收斂,但是過大的η值阻礙了收斂速率,因此不同的參數值η會對分類器的訓練結果造成一定的影響。

圖2　范數約束值p對識別正確率的影響　　　　　圖3　懲罰因子η對經驗風險誤差的影響

4結論

為了快速而準確地對傳感器網絡定位過程中進行攻擊的惡意節點進行分類,本文提出了分布式ADM-PSVM節點定位攻擊類型識別方法。不同于傳統的集中式支持向量機分類器,該算法能將原有的識別問題分解為2個獨立的子問題,并能夠根據節點能量剩余情況轉移迭代運算參數,從而將整體計算任務分配到了不同的節點上;而且ADM-PSVM還引入任意p范數約束的條件,在選擇不同的范數p的,不僅在一定程度上選擇了相關性更強的特征向量,也降低了由于噪聲等干擾造成的影響,增強了分類器的識別性能及穩定性。通過在非測距定位機制下產生的攻擊數據集的實驗表明,本文提出的ADM-PSVM別算法取得了更優越的識別性能且降低了計算的時間復雜度。

參考文獻：

[1]劉華博, 崔建明, 戴鴻君. 基于多元分類的無線傳感器網絡惡意節點檢測算法[J]. 傳感技術學報, 2011, 24(5): 771-777

Liu Huabo, Cui Jianming, Dai Hongjun. Multivariate Classification-Based Malicious Node Detection for Wireless Sensor Network[J]. Chinese Journal of Sensor and Actuators, 2011, 24(5): 771-777 (in Chinese)

[2]Sun Bo, Shan Xuemei, Wu Kui, Yang Xiao. Anomaly Detection Based Secure In-Network Aggregation for Wireless Sensor Networks[J]. IEEE Systems Journal, 2013, 7(1): 13-25

[3]Zeng Yingpei, Cao Jiannong, Xie Li. Secure Localization and Location Verification in Wireless Sensor Networks: A Survey[J]. Journal of Supercomputing, 2013, 64(3)：685-701

[4]汪淑麗. 基于支持向量機的無線傳感器網絡的入侵檢測系統[J]. 傳感器與微系統, 2012, 31(7): 73-76

Wang Shuli. Intrusion Detection System for WSNS Based on SVM[J]. Transducer and Microsystem Technologies, 2012, 31(7): 73-76 (in Chinese)

[5]劉健, 沈海斌. 無線傳感器網絡的三維定位算法研究[J]. 傳感器與微系統，2013,32(9): 66-71

Liu Jian, Shen Haibin. Study on 3D Localization Algorithm for WSNS[J]. Transducer and Microsystem Technologies, 2013, 32(9): 66-71 (in Chinese)

[6]Chen Jinhu, Takiguchi Tetsuya, Ariki Yasuo. A Robust SVM Classification Framework Using PSM for Multi-Class Recognition[J]. Eurasip Journal on Image and Video Processing, 2015, 1: 1-12

[7]Boley Daniel. Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs[J]. SIAM Journal on Optimization, 2013, 23(4): 2183-2207

[8]Xu M H, Wu T. A Class of Linearized Proximal Alternating Direction Methods[J]. Optimization Theory and Applications, 2011: 321-337

[9]Lu Xiaopei. MDS-Based Wormhole Detection Using Local Topology in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks, 2012, 2012: 1-9

Distributed Localization Attack Type Recognition Algorithm for Malicious Nodes in Wireless Sensor Networks

Wang Suzhe, Li Yong, Cheng Wei, Wang Daoping

(Department of Electronics Engineering, Northwestern Polytechnical University, Xi′an 710072, China)

Abstract:The process of localization in wireless sensor networks is easily attacked by malicious nodes. In order to identify the types of those external attacks, an Alternating Direction Method of Multipliers-p-Norm Support Vector Machines(ADM-PSVM) algorithm is proposed. The proposed algorithm is based on classification model of the linear support vector machine. Firstly, by introducing a norm constraint into the classification algorithm, the adaptability of classifier for various types of dataset can be enhanced via selecting different value p. Then we derive distributed form of the algorithm according to Alternating Direction Method of Multipliers; this makes the classifier have the ability to distribute computing task among different nodes based on the residual energy of each node. Finally, the sample and testing dataset for each of four types of external malicious nodes are implemented in the training and testing processes of the proposed algorithm, and the influence on recognition accuracy performance in various p values and penalty factor η ones are discussed. The experimental results show that the proposed algorithm can achieve higher classification accuracy and better computational efficiency on the hostile external attack dataset.

Keywords:adaptive systems, classifiers, computational efficiency, eigenvalues and eigenfunctions, iterative methods, Lagrange multipliers, matrix algebra, mesh generation, sampling, support vector machines, vectors, wireless sensor networks; ADM-PSVM(Alternating Direction Method of Multipliers-p-Norm Support Vector Machines), attack type recognition, classification, distributed, localization, malicious, p-norm

中圖分類號：TP393; TP181

文獻標志碼：A

文章編號:1000-2758(2016)01-0085-07

作者簡介：王夙喆(1985—)，西北工業大學博士研究生，主要從事無線傳感器網絡研究。

收稿日期：2015-10-09基金項目：國家自然科學基金(61401360)、陜西省自然科學基礎研究計劃(2014JQ2-6033)與中央高校基本科研業務費專項資金(3102014JCQ01055)資助