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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

1.1WSN定位攻擊特點分析

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

(5)

(6)

2分布式p范數(shù)支持向量機分類算法

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

(7)

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

(8)

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

(9)

(10)

(11)

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

(12)

(13)

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

根據(jù)KKT條件,得到

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

(14)

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

(15)

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

(16)

其對偶問題可以表示為:

(17)

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

圖1　節(jié)點迭代計算示意圖

3實驗仿真與結果分析

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

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

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

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

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

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

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

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

3.2實驗結果與分析

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

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

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

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

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

4結論

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

參考文獻：

[1]劉華博, 崔建明, 戴鴻君. 基于多元分類的無線傳感器網絡惡意節(jié)點檢測算法[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]汪淑麗. 基于支持向量機的無線傳感器網絡的入侵檢測系統(tǒng)[J]. 傳感器與微系統(tǒng), 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]. 傳感器與微系統(tǒng)，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—)，西北工業(yè)大學博士研究生，主要從事無線傳感器網絡研究。

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