一種基于時序信譽的WSNs 惡意節(jié)點檢測算法*

邢哲源，馮秀芳

(太原理工大學 計算機科學與技術學院，山西 太原030024)

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)將不同類型傳感器置于節(jié)點內部，感知周圍溫度、濕度、壓力、光強等并對數據進行收集，具有廣泛的應用價值［1］。由于WSNs 的自身特點，導致了其容易受到各種各樣的攻擊。傳統(tǒng)的網絡安全策略大多基于密碼學，對WSNs 完全防御效果不夠理想［8］。

近年來，一種基于信任機制的信譽模型在計算機領域內得到大量的應用。國內學者于2007 年通過貝葉斯公式計算節(jié)點信譽值，并以閾值作為判斷條件，對惡意節(jié)點加以識別［2］;王鵬江等人于2010 年又通過引入“間接信譽”對該模型加以改進［3］;2013 年，由曾梅梅等人提出的灰色馬爾科夫信譽評價模型在綜合信譽的基礎上添加了能量信譽概念［4］;吳正一、李健等人于2014 年又在信譽模型的基礎上引入能量因素和環(huán)境誤差的概念［5］。WSNs 發(fā)展，催生出更加隱蔽的新型攻擊方式，惡意節(jié)點持續(xù)不斷的攻擊行為大大減少，在多數情況下保持與正常節(jié)點相同或相似［6］。單純通過閾值進行判斷，可能出現低識別率的問題，而提高閾值容易導致較高的誤判率。同時，在WSNs 中正常節(jié)點由于通信故障往往會導致出現異常行為記錄，從而導致誤判。

本文提出一種基于時序的WSNs 信任模型，在原有信譽閾值模型的基礎上，引入時序和相似度的概念，通過聚類分析出攻擊行為不明顯的惡意節(jié)點。實驗表明:本方案有較好的惡意節(jié)點識別率，同時避免了原信譽閾值模型由于提高閾值所導致的正常節(jié)點誤判率上升的問題。

1 相關定義

1.1 時序信譽和樣本信譽值序列與節(jié)點信譽值序列

本文所采用的方法是將被視為整體的節(jié)點通信行為歷史進行等長時間間隔的拆分，在每一個時間間隔處對節(jié)點的信譽進行評價，并最終形成時序信譽序列。這一方式在本文中被稱之為時序信譽。

對于任意節(jié)點x，經過n 個相同的時間間隔Δt 后其所有時間間隔點處的信譽值組成其信譽值序列X={Xt1，Xt2，Xt3，…，Xtn}，n ＞1，稱為節(jié)點x 的信譽序列X。

樣本信譽值序列中每個元素表示正常節(jié)點的標準信譽值。樣本序列可以記為O={Ot1，Ot2，Ot3，…，Otn}，n ＞1。

1.2 亞攻擊節(jié)點

多個惡意節(jié)點相互協(xié)作地針對WSNs 進行具有明確分工的攻擊時，通過哨崗節(jié)點等方式將具有更高的隱蔽性。攻擊節(jié)點并不以激增方式盲目地發(fā)起攻擊，其行為在信譽值上更趨近于正常節(jié)點的信譽值，不易被系統(tǒng)發(fā)覺。上述節(jié)點稱為“亞攻擊節(jié)點”，如圖1。

圖1 亞攻擊節(jié)點Fig 1 Sub-attack node

1.3 序列相似度和相似度序列

序列相似度是任意節(jié)點x 的信譽值序列X 與樣本信譽值序列O 之間的相似度，取值范圍在［0，1］之間。使用歐幾里得度量(Euclidean metric)對節(jié)點信譽序列和樣本信譽序列的相似度進行計算。

N 維歐氏空間是一個點集，其每個點x 或者向量X，可以表示為(x［1］，x［2］，x［3］，…，x［n］)，其中，xi(i=1，2，3，…，n)是實數，表示x 的第i 維坐標。兩個點A=(a［1］，a［2］，a［3］，…，a［n］)和B=(b［1］，b［2］，b［3］，…，b［n］)之間的距離定義為

對于具有n 個節(jié)點的WSNs，其相似度序列為S={s1，s2，s3，…sn］，n 為節(jié)點數量。

1.4 K-mediods 聚類算法

本實驗采用K-mediods 聚類算法［6］對相似度數據集M進行分析。

1.4.1 K 值的確定

K-medoids 聚類算法的基本思想為:設K 是給定的聚類數目，首先需要確定初始聚類中心，即隨機選擇K 個代表對象;第二劃分聚類，分別計算非代表對象與代表對象的距離并將其分配給距離最近的一個簇，確定初始的聚類劃分;最后迭代獲得最終聚類結果，通過不斷迭代尋找最優(yōu)的中心點。

1.4.2 中心點的確定

原始中心點隨機選擇一個非中心點，重新獲得聚類結果。如果優(yōu)化聚類效果，則保存此次替換;反之，恢復原中心點，具體定義為

其中，p 為空間中的點，oi為簇Ci的中心點，E 為所有對象的平方誤差和。

在進行新一輪中心的替換后，以新的中心集聚類得到的簇用new Ci=1，2，3，…，k 表示，原來的簇以old Ci=1，2，3，…，k 表示，新舊聚類的評價函數可以分別表示

可以求得代價函數為式(5)

最后根據代價來決定中心點。

1.5 信息的匯聚和處理

WSNs 對所有節(jié)點的數據進行匯聚，計算生成信譽值序列X，即網絡包含m 個節(jié)點，節(jié)點信譽值序列由m 個數值組成:為節(jié)點x的綜合信譽值。

1.6 計算相似度和生成相似度序列

將任意節(jié)點的信譽相似度序列和樣本序列視為n 維歐氏空間中的兩個點，當其歐式距離越大時，表示節(jié)點的信譽序列與樣本序列之間的相似度越小;反之，其相似度越大。最終即可產生相似度序列S。

1.7 聚類和惡意節(jié)點識別

節(jié)點的信譽時間序列與基準序列的相似度越高，說明節(jié)點行為離惡意節(jié)點與正常節(jié)點區(qū)分的臨界點越近;反之，相似度向0 收斂。

通過使用K-mediods 算法找最優(yōu)聚類，實現對具有亞攻擊性節(jié)點的識別。這種節(jié)點的信譽往往貼近系統(tǒng)閾值，將此屬性體現在信譽時間序列與基準序列的相似程度上，從數值上則為相似度接近1。

使用K-mediods 聚類算法對相似度數據集S 進行聚類，識別惡意節(jié)點的處理過程。

輸入:相似度數據對象的數據集。經過聚類預計得到K 個聚類，每個包含n 個對象。

輸出:K 個由像素度極高的對象組成的數據集，使得每個對象與其最近中心點的差異度總和最小，該數據集中心對象的值越接近1，則越接近系統(tǒng)閾值，視為亞攻擊節(jié)點。

1)初選數據中心:從輸入的數據對象中隨機選擇K 個點，作為初始中心點。

3)迭代優(yōu)化:對每個非中心點依次執(zhí)行:用當前點替換其中一個中心點，并依據代價函數計算出由此所產生的總代價，若為負，則保留此次替換;反之，還原中心點。

4)終止迭代:當替換不能再產生更好的聚類劃分時，終止迭代。本算法的具體實現過程如圖2 所示。

圖2 算法流程圖Fig 2 Algorithmic flow chart

2 實驗分析

在Matlab 中，依照上文的設計，建立了基于時序信譽機制的WSNs 信譽模型，并且驗證了算法的有效性。

在WSNs 中隨機的設置50 ～300 個節(jié)點，其中有1/10節(jié)點以0.4 ～0.6 的概率對網絡進行攻擊;在50 ～300 個時間間隔內，為網絡中所有節(jié)點生成其信譽序列;通過改變節(jié)點數量n、信譽序列長度m，K-mediods 中的參數K，對不同條件下的識別效果進行分析。

2.1 參數對算法性能的影響

不同時序長度m 會對結果產生不同的識別精確度，分別將時序長度m 設置為10，50，100，150，200，250，300，結果如圖3 所示。時序長度的增長可以有效地提高識別率，但會導致算法在時間和空間上開銷增大。

圖3 不同序列長度對識別率的影響Fig 3 Influence of different sequences length on recognition rate

在K-medoids 聚類算法中，K 值的選擇對結果有非常明顯的影響。K 值的選擇一般都由經驗確定，再根據實際結果調整，最終選出最優(yōu)值。

分別將K 取值為2，3，4 對算法進行檢驗，以識別率和誤判率為選擇條件，最終確認K 值。綜合分析發(fā)現:當K=3 時，算法在識別率和誤判率兩方面都有較好的效果，如圖4、圖5 所示。

圖4 不同K 值對惡意節(jié)點識別率的影響Fig 4 Influence of different K value on recognition rate of malicious node

圖5 不同K 值對正常節(jié)點誤判率的影響Fig 5 Influence of different K value on misjudgment rate of normal node

2.2 與信譽閾值模型的性能對比

本算法的設計初衷是對原有的信譽閾值模型的不足加以補充，通過改進來保證信譽閾值模型對更加隱蔽的亞攻擊節(jié)點進行有效的識別。在信譽閾值機制下，閾值的設定多依賴經驗。為對比本算法對原有識別方法的改進，選擇多個不同閾值進行仿真，比較識別效果。

在本算法中，需要一個類似判斷閾值的信譽參考值，在此折中地將閾值設置為0.5。使用本算法識別出來的惡意節(jié)點:一部分是信譽值低于0.5 的節(jié)點;另一部分是本算法識別出的亞攻擊節(jié)點。同時分別使用λ=0.4，0.5，0.6 作為閾值，對惡意節(jié)點的識別率進行比較。通過實驗可以發(fā)現，提高閾值可以提高識別率，但誤判率也會提高。而本文算法可以在提高識別率的同時(圖6)，保證誤判率穩(wěn)定(圖7)。

3 結束語

本文對WSNs 信譽閾值模型加以改進，提出了一種基于時序信譽的WSNs 惡意節(jié)點檢測模型。在檢測過程中，通過聚類可以有效地判斷惡意節(jié)點，同時減少了誤判率的提高。但本算法需要較長的時序長度，會導致整個算法開銷增大。

圖6 本文算法與不同閾值的信譽閾值模型的識別率比較Fig 6 Recognition rate comparison between credit threshold model of different threshold and the proposed algorithm

圖7 本文算法與不同閾值的信譽閾值模型的誤判率比較Fig 7 Misjudgment rate comparison between this algorithm and credit threshold model of different threshold

隨著WSNs 領域的不斷發(fā)展，攻擊行為變得愈發(fā)隱秘，而無線傳感器節(jié)點依然會受到自身特性的制約。因此，在WSNs 安全領域依然存在著諸多的理論問題和實際工作急需解決。

［1］ 張旭彬，劉志宏.無線傳感器網絡及移動Sink 安全［J］，計算機科學，2013，40(11A):4－7.

［2］ 肖德琴，馮健昭，楊 波，等.基于無線傳感器網絡的信譽形式化模型［J］.計算機科學，2007，34(6):84－87.

［3］ 王江鵬，余 琴，成鴻飛.基于信譽模型的無線傳感器網絡惡意節(jié)點識別方法［J］.現代商貿工業(yè)，2010，15(9):338－339.

［4］ 曾梅梅，蔣 華，王 鑫，等.一種基于灰色馬爾可夫模型的信譽評測模型及其安全路由協(xié)議［J］.計算機應用研究，2013，30(12):3756－3761.

［5］ 吳正一，李 健.無線傳感器網絡信譽管理機制［J］.網絡安全技術與應用，2014(2):120－123.

［6］ 姚麗娟，羅 可，孟 穎.一種新的K-medoids 聚類算法［J］.計算機工程與應用，2013，49(19):153－157.

［7］ Malik Tubaishat，Sanjay Madria.Sensor networks:An overview potentials［J］.Digital Object Identifier，IEEE，2003，22(2):20－23.