無線傳感網(wǎng)中基于DPAM-MD算法的惡意節(jié)點識別研究

張琳，尹娜，王汝傳,2,4

（1. 南京郵電大學 計算機學院，江蘇 南京 210003；2. 江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室，江蘇 南京 210003；3. 南京郵電大學 計算機技術(shù)研究所，江蘇 南京 210003；4. 南京郵電大學 寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點實驗室，江蘇 南京 210003）

1 引言

作為一種分布式傳感網(wǎng)絡，無線傳感網(wǎng)中的傳感器不僅可以感知和檢查外部世界，而且可以通過無線的方式進行通信。因此在無線網(wǎng)中，可以隨時更改設備的位置，還可以通過有線或無線方式跟互聯(lián)網(wǎng)進行連接。隨著網(wǎng)絡的不斷發(fā)展，很多領域都與無線傳感器網(wǎng)絡息息相關，例如家庭、健康、環(huán)境以及軍事等[1]。按照這種趨勢，在不久的將來，我們的生活將離不開這種由低成本、小型和低功耗的傳感器節(jié)點組成的無線傳感器網(wǎng)絡。因此對無線傳感器網(wǎng)絡的安全進行有效的保障顯得尤為重要。在無線傳感器網(wǎng)絡中有很多以損害無線傳感網(wǎng)為目的的惡意性傳感器節(jié)點，這些節(jié)點干擾無線傳感器網(wǎng)絡的正常運行，浪費正常節(jié)點的資源，使得無線傳感器網(wǎng)絡的安全受到了嚴重的破壞。為了能夠識別這些惡意節(jié)點，排除他們所造成的干擾，很多國內(nèi)外專家學者對這一問題進行了深入的探討。

在國內(nèi)，蔡紹賓等[2]還進行了基于模型的無線傳感器網(wǎng)絡惡意節(jié)點識別技術(shù)的研究。MA&TP-BRSN模型被楊光等[3]提出，該模型可以將信譽值非常高的節(jié)點識別出來，但是具有相對較低的惡意節(jié)點的識別度。而對于Li等[4]提出的融合模型，主要是通過識別惡意節(jié)點的具體位置從而將其排除無線傳感器網(wǎng)絡中。除此之外，國外還有很多學者在這方面有很多研究。例如，一種基于統(tǒng)計方法的 WSN惡意節(jié)點檢測方案被Sliva等[5]設計出來。該模型首先將無線傳感網(wǎng)中的正常節(jié)點的通信行為用一套規(guī)則表示出來，當新的節(jié)點開始通信之前用已定義的規(guī)則來判斷該節(jié)點是否為惡意節(jié)點。但是該方案也存在一定的弊端，它沒有將節(jié)點之間的交互關系所造成的影響考慮進來，這樣很容易將正常節(jié)點錯判成惡意節(jié)點。而在 SUN[6]和 TIAN[7]研究的惡意節(jié)點識別方法中存在著需要特殊節(jié)點開銷大，能耗低等不足。SaurabhGaneriwal等[8]提出了 BRSN模型來判斷節(jié)點的性質(zhì)。該模型只是簡單的通過設定一個閾值來區(qū)分正常與惡意節(jié)點，只能夠識別一些比較明顯的節(jié)點，但是對于一些信譽值和正常節(jié)點很相似的節(jié)點，該模型就無法發(fā)揮很高的價值。

在上面介紹的識別惡意節(jié)點的模型以及方法中，通過計算信譽閾值的模型來識別的方法是相對比較全面的，然而這種方面還是有很多需要改進的地方，在原有的基礎上無線網(wǎng)已經(jīng)有突破性發(fā)展，隨之而來的惡意節(jié)點也變得越來越強大。惡意節(jié)點不在像以前那么明顯，而是變得越發(fā)的隱蔽[9]，從表面看幾乎和正常節(jié)點沒有什么差別，具有這種特性最常見的惡意節(jié)點就是亞攻擊性節(jié)點[10]。針對此，本文提出了基于DPAM-MD(density-based partitioning around medoids-malicious node detection)算法的新型惡意節(jié)點識別方法，將時序和相似度這 2個概念引入到模型中，通過結(jié)合曼哈頓度量和DPAM算法識別出亞攻擊性節(jié)點。經(jīng)仿真實驗結(jié)果驗證，改進后的算法對識別特征不明顯的惡意節(jié)點效果非常顯著。

2 相關定義

定義1惡意節(jié)點。在WSN中主要包含2大節(jié)點，正常節(jié)點與異常節(jié)點，通常將以損害無線傳感網(wǎng)為目的的惡意性傳感器節(jié)點被稱為惡意節(jié)點，該節(jié)點屬于異常節(jié)點這個大類中[11]。

定義 2亞攻擊性節(jié)點。隨著互聯(lián)網(wǎng)的不斷發(fā)展，一些惡意節(jié)點變得更加的隱蔽，幾乎與正常節(jié)點沒什么區(qū)別，這種節(jié)點的特性處于正常和異常節(jié)點之間，傳統(tǒng)的模型很難將這種節(jié)點有效的識別出來，將這類節(jié)點稱為亞攻擊性節(jié)點。如圖1所示亞攻擊性節(jié)點屬于內(nèi)部攻擊節(jié)點[12]。

圖1 節(jié)點類型

定義 3節(jié)點信譽值序列。設在無線傳感器網(wǎng)絡中任意節(jié)點a，經(jīng)過若干個相同的時間間隔t,節(jié)點a的信譽值序列就是在每個時間間隔點處的信譽值所組成的序列，即

定義 4序列相似度。任意節(jié)點a的信譽值序列A和基準信譽值序列B之間的相似度即為序列相似度，測量相似度的方法有很多例如曼哈頓度量，歐幾里得度量，高斯徑向基函數(shù)，擴展的Frobenius范數(shù)等。

定義 5曼哈頓度量設是2個被p個數(shù)值屬性描述的對象。對象i和j之間的曼哈頓度量的定義為

曼哈頓度量具有非負性，同一性，對稱性，三角不等式等數(shù)學特性。

定義6k-中心點算法。該算法是一種基于中心點或中心對象進行劃分的k-中心點算法[13]。

典型的k-中心點算法描述如下[14]。

輸入：

k//最終簇的個數(shù)；

D//包含n個對象的數(shù)據(jù)集合。

輸出：k個簇的集合。

方法：

1) 從D中隨機選擇k個對象作為初始的代表對象或種子；

2) repeat

3) 將每個剩余的對象分配到最近的代表對象所代表的簇；

4) 隨機地選擇一個非代表對象orandom；

5) 計算用orandom代替代表對象oj的總代價S；

6) ifS＜0，thenorandom替換oj，形成新的k個代表對象的集合；

7) until不發(fā)生變化

絕對誤差標準函數(shù)定義如下[15]

其中，E是數(shù)據(jù)集中所有對象P與Ci的代表對象oi的平方差之和。

3 基于DPAM-MD算法的惡意節(jié)點識別

以上介紹了惡意節(jié)點的基本概念，并且介紹了原有基于信譽閾值模型的不足。本節(jié)將詳細闡述如何改進方案，提高惡意節(jié)點的識別率。

3.1 節(jié)點信譽值的計算

本文中節(jié)點信譽值的計算，引用了 Saurabh Ganeriwal等提出的針對資源受限的無線傳感器網(wǎng)絡設計的一種信譽評測模型BRSN模型，節(jié)點的綜合信譽值如下所示

3.2 節(jié)點相似度與相似度序列的計算

無線傳感器網(wǎng)絡對所有的節(jié)點數(shù)據(jù)進行匯聚，計算生成信譽值序列A，設網(wǎng)絡中共有m個節(jié)點，這些節(jié)點的信譽時間序列為需要注意的是，網(wǎng)絡中可以通過原有信任閾值判斷機制識別出來的惡意節(jié)點不需要提供信譽時間序列，本算法只用于識別亞攻擊性節(jié)點。將任意節(jié)點的相似度序列A和基準信譽值序列(b為網(wǎng)絡判斷惡意節(jié)點的信譽閾值，B是長度m的等值序列)代入到式(1)可得到相似度序列C。

若通過式(4)算出的結(jié)果越小即越接近0，則表明節(jié)點信譽序列和基準信譽序列相似度越大；相反若算出的結(jié)果越大即越接近 1，則表明節(jié)點信譽序列和基準信譽序列相似度越小。

3.3 使用DPAM算法對相似度序列C進行聚類

1)k值的確定

相似度反映的是節(jié)點信譽時間序列與基準序列的相似程度，為了將相似度序列C劃分成若干類，同k-中心點算法，DPAM算法首先也要通過k值來確定節(jié)點劃分的種類數(shù)量。

2) 中心點的確定

本文的 DPAM 算法是在k-中心點算法上的一種改進，在k-中心點算法中，中心點的替代策略使得時間復雜度很高，效率很低，無法滿足當前大數(shù)據(jù)的需求，因此在DPAM算法中提出了基于密度的中心點替換策略。

通過式(5)計算每個樣本的密度

其中，dist是某種距離度量，r為半徑，C為相似度序列數(shù)據(jù)集，式(5)表明以x為中心點，r為半徑組成的球體所包含的樣本數(shù)；r規(guī)定為r=p×q,q為給定常數(shù)，而P則為兩兩數(shù)據(jù)對象距離的均值為

樣本的平均密度為

將樣本密度大于平均密度AD(x)的樣本全部放在集合L中，L可以表示為

在L中取最大密度點作為第一個聚類中心Y1，并從L中刪除；取距離Y1最遠的高密度點作為第2個中心點Y2；重復以上2步直至找到k個中心點。最終k個中心點就是相隔距離較遠的k個處于高密度區(qū)域的點，這些中心點基本上是確定的, 從而避免了初始中心選擇的隨機性, 保證了聚類結(jié)果較好的穩(wěn)定性。

初始中心點確定后，計算出與每個初始中心點密度相近的k個點集，分別為Z1,Z2,L ,Zk

式(9)表示以Yi為中心，AD為半徑的點的集合。每次的替代過程都在Z1,Z2,L ,Zk這些點集中進行，直到滿足條件為止。若這些點集都不滿足，則考慮其他的節(jié)點。

3) 目標函數(shù)

一個目標函數(shù)用來評估劃分的質(zhì)量，使得簇內(nèi)對象相互相似，而與其他簇中的對象相異。也就是說該目標函數(shù)以簇內(nèi)高相似和簇間低相似性為目標。傳統(tǒng)的聚類方法都是以簇內(nèi)節(jié)點到中心點距離和最小作為目標函數(shù)，沒有考慮到簇間的影響。基于此本文提出了新的目標函數(shù)，在該目標函數(shù)中均衡了簇內(nèi)與簇間距離，當E值越小則表明分類效果越好，如下所示

其中，θ簇間距離的權(quán)重是簇內(nèi)距離的θ倍，一般取值為1，in(d)為簇內(nèi)距離和，即簇內(nèi)每一點到它所屬類中心的距離的平方和，見式(2)，out(d)為簇間距離和，即不同聚類中心間的距離

3.4 惡意節(jié)點的識別

亞攻擊性節(jié)點的信譽值與系統(tǒng)設定的閾值非常的接近，換句話說亞攻擊性節(jié)點的信譽時間序列與基準信譽值序列的相似度接近 1，利用這一特征通過上述的DPAM算法對相似度數(shù)據(jù)集C進行聚類從而識別出惡意節(jié)點。

DPAM-MD算法具體的實現(xiàn)過程如圖2所示。

4 仿真實驗

為了驗證本文算法的有效性，通過Matlab軟件用M語言進行編程仿真，將原有的信譽閾值識別惡意節(jié)點的模型與本文改進后的模型進行比較。

圖2 DPAM-MD算法流程

仿真環(huán)境：操作系統(tǒng) Windows 7，編譯軟件Matlab7.0.1；處理器為AMD A4-3300M APU with Radeon（tm）HD Graphics 1.90 GHz，內(nèi)存為 2 GB。

在實驗中規(guī)定，50～300個無線傳感器節(jié)點在100 m×100 m的正方形區(qū)域內(nèi)進行部署，這些節(jié)點的位置是固定不變的。除此之外節(jié)點的外在特性都是相同的，例如物理結(jié)構(gòu)單元和能量，節(jié)點都有數(shù)據(jù)融合的功能。假定在這些節(jié)點中有惡意節(jié)點以0.5～0.6的概率對網(wǎng)絡正常通信進行破壞；實驗中選取時間間隔區(qū)間為在50～300。

4.1 評價指標的設定

為了比較直觀的驗證算法對惡意節(jié)點的識別性能，本文引用2個評價指標對算法的性能進行分析，分別為召回率R和誤判率W。

召回率R指的是惡意節(jié)點識別的情況，也稱為惡意節(jié)點識別度，它是指被識別出來的惡意節(jié)點的個數(shù)RM與實際無線傳感器網(wǎng)絡中設定的惡意節(jié)點總數(shù)AM的比值。即

誤判率W即正常節(jié)點錯判情況，也稱正常節(jié)點的錯判率，指的是正常節(jié)點被識別為惡意節(jié)點的個數(shù)WR與無線傳感器網(wǎng)絡中實際設定的正常節(jié)點的總數(shù)AN的比值。即

4.2 參數(shù)的設定

在DPAM-MD算法的實現(xiàn)過程中有2個非常重要的參數(shù)分別是k值和時間序列的長度，本文將節(jié)點的信譽時間序列作為輸入數(shù)據(jù)進行聚類分析，因此時間序列的長度T的不同可能會對惡意節(jié)點識別的效果造成影響，除此之外本文采用了基于k-中心點算法改進的DPAM聚類算法，因此k值在實驗中也起到了關鍵性作用。為了能夠選擇出最佳的參數(shù)，分別設定k值取2, 3, 4這幾個值，而時間序列長度取50、100、150、200、250、300個時間間隔。在實驗中以信譽評價系統(tǒng)的判斷閾值為0.5為例進行分析判斷。

由圖 3和圖 4可以很清楚的看出使用DPAM-MD算法對惡意節(jié)點進行識別的過程中，隨著輸入的時間序列長度的增加，算法對惡意節(jié)點的識別度越高，也就是召回率越高，并且時間序列長度越長，正常節(jié)點的誤判率也越低。由此可以看出時間序列長度越長越好。而對于k值，當k=2時算法對惡意節(jié)點的識別率處在 3種情況適中的水平,但是在正常節(jié)點的誤判率方面表現(xiàn)的最差;對于k=4時,節(jié)點的誤判率處于3種情況適中的水平,但其惡意節(jié)點的識別率很低;只有當k=3時對惡意節(jié)點的識別度最高，正確節(jié)點的誤判率最低，因此當k為3時算法對惡意節(jié)點的識別能力最強。

圖3 不同參數(shù)對惡意節(jié)點識別率的影響

4.3 與傳統(tǒng)信譽閾值模型（BRSN）對比

傳統(tǒng)的信譽閾值模型主要原理是首先設置節(jié)點的閾值λ，算出所有節(jié)點的閾值當某個節(jié)點的信譽值低于閾值時，則判定該節(jié)點是惡意節(jié)點。為了比較本文模型與該模型的優(yōu)劣，分別選取閾值為0.45、0.5、0.55這3種情況進行比較，基準序列值取0.5。

圖4 不同參數(shù)對正常節(jié)點誤判率的影響

從圖5和圖6看出，在信譽閾值模型中，隨著閾值的提高能識別出更多的惡意節(jié)點，但與此同時越來越多的正常節(jié)點被錯判為惡意節(jié)點。在算法BRSN[8]中若想控制正常節(jié)點的誤判率，就必須將閾值λ控制在較低值，這樣的結(jié)果就會造成惡意節(jié)點識別率的降低。傳統(tǒng)的模型很難將誤判率和識別率協(xié)調(diào)，造成這一結(jié)果的主要原因就是,亞攻擊性節(jié)點的攻擊行為比一般的惡意節(jié)點更加隱蔽具有節(jié)制性,傳統(tǒng)模型通過簡單的閾值判斷很難將亞攻擊性節(jié)點與正常節(jié)點區(qū)分開。而DPAM-MD能夠有效的將亞攻擊性節(jié)點識別出來，并且降低了正常節(jié)點的誤判率。由此可以看出本文算法的可行性。在圖5中很明顯可以看出在惡意節(jié)點相對較少時，惡意節(jié)點的識別率不論是哪種算法，識別率都相對較高，而隨著惡意節(jié)點的個數(shù)的增加傳統(tǒng)的算法識別出的惡意節(jié)點個數(shù)較少，識別率降低。同樣的在圖 6中隨著正常節(jié)點個數(shù)的增加，正常節(jié)點的誤判率都有下降的趨勢。分析其原因是因為算法在判斷過程中采用了新型的聚類算法，當樣本的特征差異不夠或者數(shù)據(jù)不是很充分時，不足以拉開特征距離，很容易造成誤判。

4.4 與MA&TP-BRSN模型對比

MA&TP-BRSN 模型[3]是在 BRSN 模型[8]的基礎上進行改進，綜合考慮了多種內(nèi)部攻擊行為，該模型將節(jié)點的評價行為和通信行為區(qū)分開來，建立了對第三方節(jié)點惡意評價行為的具體測評方法,并在此基礎上給出了節(jié)點間接信譽參數(shù)的更新計算方法。該模型包括多重攻擊節(jié)點信任值的計算與評判方法MA-BRSN以及第三方節(jié)點的間接信譽參數(shù)更新計算方法TP-BRSN。為了進一步的檢測本文算法的可行性，在相同場景下將 DPAM-MD算法與BRSN[8]、TP-BRSN[3]進行比較。

圖5 不同取值BRSN與DPAM-MD對惡意節(jié)點識別的比較

圖6 不同取值BRSN與DPAM-MD對正常節(jié)點誤判的比較

參照文獻[3]，將信任閾值規(guī)定為0.4，對3種模型進行比較。由圖7和圖8可以看出，在相同網(wǎng)絡設置下，BRSN算法很難識別攻擊頻率相對節(jié)制性，攻擊行為更加隱蔽的惡意節(jié)點，而TP-BRSN模型，盡管有較高的識別率，但與此同時它的正常節(jié)點的誤判率相對較高。究其原因是因為上述的模型缺乏對新形勢下亞攻擊性節(jié)點攻擊手段的考慮，很難有效地識別攻擊頻率相對更有節(jié)制，攻擊行為更加隱蔽的亞攻擊性節(jié)點。只有DPAM-MD算法可以在保證低誤判率的同時提高惡意節(jié)點的識別能力。

5 結(jié)束語

本文是對傳統(tǒng)信譽閾值模型加以改進，提出了一種新的識別惡意節(jié)點的DPAM-MD算法，該算法通過獲取所有節(jié)點的信譽時間序列，通過改進后的聚類方法將節(jié)點進行分類，從而更為準確地判斷出惡意節(jié)點。在利用本算法識別惡意節(jié)點過程中，不僅能夠保證較高的惡意節(jié)點識別率，同時正確節(jié)點的誤判率也得到了改善。仿真實驗結(jié)果表明，該方法能夠有效的識別網(wǎng)絡內(nèi)部的惡意節(jié)點，能夠?qū)鹘y(tǒng)的信譽閾值模型進行較好的補充。

圖7 不同模型對惡意節(jié)點識別的比較

圖8 不同模型對正確節(jié)點誤判的比較

當然，在本算法中時間序列的長度越長，實驗仿真的效果越好，但與此同時會讓整個算法的開銷變得很大，在本文中并沒有將其加以討論，還需繼續(xù)研究。隨著無線傳感器網(wǎng)絡的不斷發(fā)展，惡意節(jié)點會愈發(fā)隱蔽，無線傳感器網(wǎng)絡領域的安全方面還有更多問題和工作有待解決。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y,et al. Wireless sensor networks a survey[J].Computer Networks, 2002,38(4):393-422.

[2] 蔡紹濱,韓啟龍,高振國,等.基于云模型的無線傳感器網(wǎng)絡惡意節(jié)點識別技術(shù)的研究[J]. 電子學報, 2012, 40(11):2232-2238.CAI S B, HAN Q L, GAO Z G ,et al. Research on cloud trust model for malicious node detection in wireless sensor network[J]. Acta Electronica Sinica, 2011, 40(11):2232-2238.

[3] 楊光,印桂生,楊武,等. 無線傳感器網(wǎng)絡基于節(jié)點行為的信譽評測模型[J]. 通信學報,2009,12:18-26.YANG G, YIN G S, YANG W,et al. Reputation model based on behaviors of sensor nodes in WSN[J]. Journal on Communications, 2009,12:18-26.

[4] LI H J, LI K Q, QU W Y. Secure and energy-efficient data aggregation with malicious aggregator identification in wireless sensor networks[J]. Future Genration Computer Systems,2014,37(7): 108-116.

[5] DA S A P R, MARTINS M H T, ROCHA B P S,et al. Decentralized intrusion detection in wireless sensor networks[A]. Proceedings of the 1st ACM International Workshop on Quality of Service & Security in Wireless and Mobile Networks[C]. ACM ,2005. 16-23.

[6] SUN B,WU K, POOCH U W. Zone-based intrusion detection for mobile ad hoc networks[J]. International Journal of Ad Hoc and Sensor Wireless Networks,2003,2(3):1-28.

[7] TIAN D, GEORGANAS N D. Energy efficient routing with guaranteed delivery in wireless sensor networks[A]. The IEEE International conference on Wireless Communications and Networking(WCNC 2003)[C]. 2003 ,3:1923-1929.

[8] SAURABH G M B S. Repution-based framework for high integrity sensor networks[A]. Proceedings of the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks(SASN’04)[C]. New York ,NY,2004.66-77.

[9] SHIGEN S B, LIA Y J, XUA H Y,et al. Signaling game based strategy of intrusion detection in wireless sensor networks[J]. Computers and Mathematics with Applications, 2011,62 (6):2404-2416.

[10] TUBAISHAT M, MADRIA S. Sensor networks: an overview[J]. Potentials, IEEE, 2003, 22(2): 20-23.

[11] WANG W J, CHATTERJEE M, KWIAT K,et al. A game theoretic approach to detect and co-exist with malicious nodes in wireless networks[J] .Computer Networks, 2014. 63-83.

[12] AHMED A, ABU B K, CHANNA M I,et al. A survey on trust based detection and isolation of malicious nodes in ad-hoc and sensor networks[J].Frontiers of Computer Science,2015.280-296.

[13] PARDESHI B, TOSHNIWAL D. Improvedk-medoids clustering basedon cluster validity index and object density[A]. Proc of the 2nd IEEE International Advance Computing Conference[C]. 2010.379-384.

[14] GAO D Y, YANG B R. An impronvedk-medoids clustering algo rithm[A].Proc of the 2nd International Conference on Computer and Autonmation Engineering(ICCAE)[C]. 2010.132-135.

[15] CHEN X Q, PENG H, HU J S.K-medoids subatitution clustering method and a new clustering validity index method[A].Proc of 6th World Congress on Intelligent Control and Automation[C]. 2006.5896-5900.