無線傳感網(wǎng)絡惡意節(jié)點識別算法①

周文雄, 林 穗

(廣東工業(yè)大學 計算機學院, 廣州 510006)

引言

無線傳感器網(wǎng)絡現(xiàn)有大部分路由協(xié)議都是以假設網(wǎng)絡中的所有節(jié)點安全可信為基礎的.而在現(xiàn)實情況下, 因傳感器節(jié)點直接暴露在惡劣或開放的環(huán)境中而受到限制, 導致節(jié)點易被攻擊者俘獲, 最后改造成了惡意節(jié)點, 從而對路由層產(chǎn)生侵入攻擊.現(xiàn)有的對稱密鑰安全機制在一定程度上只能夠?qū)ν獠康墓暨M行抵抗,而對于節(jié)點被俘獲過程中所帶來的內(nèi)部攻擊卻無能為力[1].信任的基本評估機制可以對故障節(jié)點、惡意節(jié)點以及不協(xié)作節(jié)點進行完整的識別, 從而達到抵抗網(wǎng)絡相關(guān)攻擊的目的, 而且這一評估機制可以在一定程度上提升無線傳感器網(wǎng)絡的完整性、機密性以及安全性[2].如果將節(jié)點信任機制引入到路由協(xié)議之中, 那么它就能以一種分配策略的身份將惡意節(jié)點從網(wǎng)絡中排除出去, 還可以解決內(nèi)部攻擊問題, 保證了重要的數(shù)據(jù)僅能從可信節(jié)點之間傳輸, 繼而建立起安全高效的路由協(xié)議[3].

現(xiàn)實社會中, 無線傳感器網(wǎng)絡面臨著多種多樣的安全威脅, 例如: 蟲洞、女巫攻擊、選擇性轉(zhuǎn)發(fā)、污水池攻擊以及虛假路由信息等.針對上述無線網(wǎng)絡安全威脅, 近年來已經(jīng)提出多種算法用以檢測識別惡意節(jié)點, 達到了抵御外部偽造的路由訊息、Sybil 攻擊和Hello flood 攻擊的目的.如劉志鋒等人建立了一種多層攻擊下的、以簇為基礎的傳感網(wǎng)評估模型, 增強了網(wǎng)絡恢復的能力從而達到提升生存力的目的, 而且此模型還能用于區(qū)分網(wǎng)絡受到何種攻擊方式[4]; Awad A 等利用虛擬坐標提高傳感器網(wǎng)絡的路由性能, 從而隱藏惡意節(jié)點的攻擊目標[5]; Naser A 等在研究過程中以兩跳鄰居信息為基礎提出了一種新的算法來對選擇性的轉(zhuǎn)發(fā)攻擊來進行檢測[6].段正飛等針對蟲洞攻擊對節(jié)點定位過程的影響, 提出了一種距離矢量跳安全定位算法.通過改進沖突集建立方法,選出最合適的信標節(jié)點廣播睡眠信息, 提高了蟲洞檢測成功率和定位精度[7].付翔燕等建立了以最優(yōu)轉(zhuǎn)發(fā)為基礎的隨機路由算法, 利用可信任的鄰居節(jié)點進行監(jiān)聽, 可對惡意節(jié)點做到有效的防御和處理[8].齊全等提出一種基于信譽機制的認知ad hoc 網(wǎng)絡分簇協(xié)作感知方法, 將權(quán)值應用為節(jié)點信譽值的基礎上實現(xiàn)了數(shù)據(jù)之間的融合, 然后對融合值和實際值進行了比較分析, 判斷數(shù)據(jù)節(jié)點的可疑性, 并利用懲罰系數(shù)來降低數(shù)據(jù)信譽值, 篩選惡意節(jié)點[9].與有線網(wǎng)絡相比較, 無線傳感器網(wǎng)絡在開放環(huán)境下, 能量、帶寬、計算能力、存儲空間受到一定限制,這就決定了傳統(tǒng)的入侵檢測技術(shù)難以直接應用到無線傳感器網(wǎng)絡中.因此, 針對無線傳感器網(wǎng)絡的特點, 金鑫等提出了針對無線傳感器網(wǎng)絡的入侵檢測模型, 它由鄰居節(jié)點監(jiān)聽、歷史行為記錄、數(shù)據(jù)釆集融合、拓撲和路由追蹤等搭建[10].為提升無線網(wǎng)絡傳感器的安全性和使用時間, 本文在對前人相關(guān)研究進行分析和借鑒的基礎上, 引入信任以及信譽系統(tǒng), 針對的節(jié)點類型主要有兩種, 分別是轉(zhuǎn)發(fā)節(jié)點和傳感節(jié)點, 提出了一種以隨機并行為基礎的簇頭選舉算法, 該算法以安全數(shù)據(jù)的融合為基礎, 可以均勻地選舉節(jié)點, 對惡意節(jié)點進行識別清除, 加密通信數(shù)據(jù), 從而有效地實現(xiàn)無線網(wǎng)絡通信的安全.

1 算法設計

1.1 簇頭節(jié)點的可信選舉

假定全網(wǎng)時間同步并且各節(jié)點有獨一無二的身份標志.網(wǎng)絡的簇結(jié)構(gòu)如圖1 所示不考慮具體的密鑰分布策略, 但假設各節(jié)點擁有3 種密鑰: 公鑰、密鑰以及私鑰.公鑰被網(wǎng)絡中的全部節(jié)點擁有, 主要作用為收獲基站廣播.密鑰主要作用為簇結(jié)構(gòu)內(nèi)部的組播或廣播,每一個簇結(jié)構(gòu)擁有其內(nèi)部特有的密鑰.因此, 可以通過簇內(nèi)密鑰實現(xiàn)基站和其它簇之間的通訊, 還可以使得鄰居節(jié)點的簇頭內(nèi)部信息交換相互不影響.私鑰一般是被某一個節(jié)點存放, 以便于節(jié)點間的數(shù)據(jù)通訊.

圖1 無線傳感網(wǎng)層次路由的拓撲結(jié)構(gòu)

在路由層級中, 簇頭節(jié)點扮演著核心的角色, 如數(shù)據(jù)采集融合、信息轉(zhuǎn)送、密鑰轉(zhuǎn)存等.在相對繁雜的網(wǎng)絡背景下, 層級路由急需改善的核心問題是如何采取適當?shù)姆绞絹肀ＷC簇頭的可信任度.在對簇頭節(jié)點進行可信選舉的過程中不應該對太多的因素進行考量,而是應該把其當作一個最優(yōu)化的選舉方式, 僅須對可信度、距離和密度之間的最優(yōu)化進行考量分析.節(jié)點密集度是指在某節(jié)點附近的鄰居節(jié)點密集程度, 可以直接表示為鄰居節(jié)點的數(shù)量; 距離D 指的是簇頭節(jié)點和成員節(jié)點間相隔的距離.對距離和密集程度進行設置的主要目的是為了能夠以節(jié)點的信任評估為基礎來實現(xiàn)路由主干節(jié)點選擇的均勻性.如果密集度越高, 那么簇頭間數(shù)據(jù)信息的融合率就會越大, 如果距離越近,那么節(jié)點間的通訊代價就會越小[11].

若節(jié)點p 在等候選擇的信任簇節(jié)點集s 之中, 那么THSp 命令為表示節(jié)點p 的簇頭選舉函數(shù).如果對概率形式的信任值進行利用, 那么對簇頭選舉進行無約束優(yōu)化的問題表達式就如式(1)所示:

式中, OT 表示的是普通成員節(jié)點對候選的可信簇頭節(jié)點p 表現(xiàn)出的總體信任值, α、β、γ 分別代表的是節(jié)點處的信任值、密集度以及距離的權(quán)重, 且存在α+β+γ=1 的現(xiàn)象, 表示信任值的調(diào)整系數(shù).如果使用理論基礎上的信任值, 那么基本表達式如式(2)所示:

其中, m(T)指普通成員對可信節(jié)點p 總體信任值的信任分量, M(T,-T)指不確定分量.

由式(2)可得出簇頭選舉函數(shù)具有這種特性: 隨著可信值和密集度的提高, 函數(shù)值增大; 隨著距離的增加,函數(shù)值減小.此可以表為一個組合優(yōu)化問題, 若p 要成為可信簇頭, 則p*必須為簇頭選舉函數(shù)的一個解, 即:

可得出式(3)的解并不是唯一存在, 是3 個參數(shù)α、β、γ 的不同函數(shù); 因此, 須依據(jù)實際情境, 擬定3 個參數(shù)的值, 最后對其進行迭代優(yōu)化.通過分析節(jié)點發(fā)送和接受的消息使每個節(jié)點的行為得到監(jiān)督, 從而自動檢測識別惡意節(jié)點并清除, 實現(xiàn)對無線網(wǎng)絡的保護.

1.2 算法優(yōu)化

在傳統(tǒng)的層次路由之中, 一般會對全網(wǎng)節(jié)點的安全可信性進行肯定假設.但是在實際操作和工作環(huán)境之中, 層次路由經(jīng)常會受到威脅.威脅的來源和種類主要分為以下兩個方面: (1) 惡意節(jié)點有時會充當簇頭節(jié)點對網(wǎng)絡流量產(chǎn)生一定的誤導影響, 從而對網(wǎng)絡的安全產(chǎn)生一定的威脅; (2) 惡意節(jié)點有時會加入到正常的簇結(jié)構(gòu)中, 通過發(fā)送某些錯誤信息而對監(jiān)測結(jié)果產(chǎn)生相應的影響.傳統(tǒng)HRBNT 算法主要解決單一網(wǎng)絡威脅, 忽略了信任路由自身功能漏洞, 并沒有對信任整體進行充分考慮, 如簇結(jié)構(gòu)不穩(wěn)定導致惡意節(jié)點不能及時排除、關(guān)鍵節(jié)點防御能力不足等問題[12], 為了實現(xiàn)上述問題的有效解決, 確保簇結(jié)構(gòu)工作過程中的安全可靠, 本文以簇頭可信選舉和節(jié)點信任值為基礎, 對無線傳感器網(wǎng)絡層次路由協(xié)議HRBNT 進行優(yōu)化.改進算法基于節(jié)點行為分析, 綜合信任度、密集度等參數(shù)選舉簇頭, 根據(jù)鄰居節(jié)點建立高效穩(wěn)定的簇結(jié)構(gòu), 與原算法在預防惡意節(jié)點方面更加優(yōu)秀, 保證網(wǎng)絡高安全性.算法優(yōu)化和建立過程主要為:

① HRBNT 之運行過程呈周期性, 其可分為數(shù)次循環(huán).如簇頭的能量小于一定閾值或該輪運行操作即將結(jié)束時, 當前簇頭發(fā)布重新選擇信息, 進入后面的循環(huán)運行操作, 并選舉新的簇頭.

② 每一次運行過程中, 各個節(jié)點會依據(jù)本身的運行狀態(tài)考慮是否成為候選簇頭: 每一個節(jié)點會生成一個[0, 1]間的隨機數(shù), 假設閾值T(n)大于隨機數(shù), 那么此節(jié)點可選作候選簇頭, 然后鄰居節(jié)點會收到它選作候選節(jié)點的廣播.在每一次循環(huán)過程中, 若節(jié)點曾經(jīng)被選取為簇頭, 則需要設置T(n)為0, 如此當選過簇頭的節(jié)點就不會再一次成為簇頭, 從而實現(xiàn)提高其他節(jié)點當選概率的目標; 在當選過簇頭的節(jié)點個數(shù)逐漸增多時, 其他節(jié)點當選為簇頭的閾值T(n)也會增長, 節(jié)點生成比T(n)小的隨機數(shù)的概率隨之提高, 因此其他節(jié)點當選的概率就會增大.T(n)的基本計算式(4)如下:

其中, P 指簇頭在全部節(jié)點中所占的比值, r 指循環(huán)次數(shù), G 指還沒當選過簇頭的節(jié)點的集合, er 代表節(jié)點當前能量, ei 代表節(jié)點初始化能量.

③ 若節(jié)點生成的隨機數(shù)大于T(n)或者其已被選作簇頭, 那么可作為成員節(jié)點, 等候接收候選簇頭的廣播訊息.如果此節(jié)點接收到了若干候選簇頭節(jié)點的廣播訊息, 那么就查找本地相關(guān)的紀錄, 對擁有較低信任值的節(jié)點進行排除, 收集信任值較高的節(jié)點.成員節(jié)點在選擇加入某簇結(jié)構(gòu)之后會發(fā)送相應的請求包, 告知該候選簇頭.候選簇頭的選舉過程如圖2 所示, 其中的1、2 和3 號節(jié)點為候選簇頭節(jié)點, 4 號節(jié)點為成員節(jié)點, 虛線表示成員節(jié)點的通信半徑.4 號節(jié)點排除信任值較低的2 號節(jié)點, 計算1 號節(jié)點和3 號節(jié)點的簇頭選舉函數(shù), 并向選舉值最大的1 號節(jié)點發(fā)送請求包, 請求加入該簇.

圖2 實際網(wǎng)絡聯(lián)機情形

④ 候選簇頭發(fā)送廣播消息后, 等候接收其他節(jié)點的請求包.在簇頭接收到來源于全部節(jié)點發(fā)出的加入申請之后, 它就會對本地的信任紀錄加以運用, 對具有惡意節(jié)點的請求進行排除, 從而確保簇的全部成員是安全可信的.同時, 經(jīng)過等待接收簇頭的考察, 僅行為良好的節(jié)點才能和簇頭節(jié)點連接, 預防惡意節(jié)點頻繁的加入簇導致過多消耗簇頭能量.簇結(jié)構(gòu)的形成過程如圖3 所示, 其中4、5 和6 號節(jié)點為成員節(jié)點, 都向1 號候選簇頭發(fā)送請求包, 虛線圓表示簇頭節(jié)點的通信半徑.由于6 號節(jié)點信任值較低, 所以只接受4 和5 號節(jié)點的請求, 且信任值最大的5 號為影子簇頭節(jié)點[13].

圖3 簇結(jié)構(gòu)的形成過程

⑤ 簇頭首先利用TDMA 時分復用給其余節(jié)點提供方案, 通過廣播把方案信息轉(zhuǎn)發(fā)給簇結(jié)構(gòu)中的全部節(jié)點, 以告訴節(jié)點什么時隙可以發(fā)送數(shù)據(jù), 杜絕節(jié)點間互相共謀或者互相影響.簇組員收到TDMA 信息時,立刻為對應的時隙轉(zhuǎn)發(fā)消息.全部簇節(jié)點的信息傳送完成之后, 數(shù)據(jù)信息會被融合轉(zhuǎn)化為其它信號, 再次發(fā)給其它簇頭和基站.節(jié)點間的數(shù)據(jù)通信可選用最短路徑、泛洪廣播和列分層級等不同協(xié)議, 實現(xiàn)形式須依據(jù)現(xiàn)實情況、網(wǎng)絡功能和規(guī)格等確定, 在此不做深入討論[14,15].

1.3 閾值的確定

假設網(wǎng)絡中簇頭節(jié)點的數(shù)目是特定的, 所有節(jié)點的初始能量相同.由于簇頭節(jié)點比成員節(jié)點耗費的能量更多, 為了避免某些簇頭節(jié)點比其它成員節(jié)點先耗盡能量, 造成網(wǎng)絡生命周期的縮短, 需要每個節(jié)點輪流充當簇頭節(jié)點以平均分配能量負載.

假設某個節(jié)點i 在第r+1 輪循環(huán)中自主決定它以T(n)的概率當選為簇頭節(jié)點.閾值T(n)的確定應該使得當前輪數(shù)期望的簇頭節(jié)點數(shù)目為k.因此, 如果整個網(wǎng)絡中共有N 個節(jié)點, 則有:

為確保全部節(jié)點在相同的時間段內(nèi)成為簇頭的幾率同等, 則需要每一個節(jié)點平均在 N/k輪中作為簇頭節(jié)點一次.用指示函數(shù) Ci(t)表示節(jié)點i 在最近的r*mod(N/k)輪是否成為簇頭節(jié)點, 如果節(jié)點i 已經(jīng)當選過一次簇頭節(jié)點或者一次以上, 則 Ci( t)=0, 否則Ci(t)=1.于是每個節(jié)點在r+1 輪應當以T(n)的概率當選為簇頭節(jié)點, 則:

由此可保證通過每個 N/k環(huán)循環(huán)后, 全部節(jié)點的能量近似相等.得出每一輪循環(huán)期望的簇頭數(shù)目是:

式中, 全部節(jié)點都自主決定其以T(n)的概率當選為簇頭節(jié)點, 但是某些節(jié)點由于本身能量較低, 作為簇頭節(jié)點或會造成其過早的死亡.為延長網(wǎng)絡生命周期, 可根據(jù)節(jié)點能量情況, 對T(n)的算法進行調(diào)整:

其中, er 為節(jié)點當前能量, ei 為節(jié)點初始化能量.

但是, 對于經(jīng)過長時間運行的網(wǎng)絡來說, 其全部節(jié)點的現(xiàn)有能量較之前都會有所降低, 閾值T(n)也自然會變小, 而這些節(jié)點成為簇頭的基本概率也會有所降低, 從而使每一輪循環(huán)被選為簇頭的節(jié)點個數(shù)有所減少, 最終甚至會影響網(wǎng)絡能量消耗的均衡性, 縮短網(wǎng)絡的生命周期.因此, 進一步改進后的T(n)的計算方法如下:

其中, rs 指節(jié)點連續(xù)沒有被選為簇頭的選舉次數(shù).如果節(jié)點被選為簇頭, 則將rs 重置為0.上式對節(jié)點能量、閾值在選擇簇頭時的影響方面進行了綜合考量, 改進算法更具公平性.

2 算法實驗與結(jié)果分析

使用Matlab 進行仿真實驗, 我們把節(jié)點信任值的計算參數(shù)設為α=β=γ=1/3.實驗范圍是參照節(jié)點i 和i 通訊區(qū)間的全部節(jié)點, i 的坐標定為(50, 50).試驗范圍內(nèi)全部簇頭節(jié)點會將選舉信息進行廣播, 節(jié)點i 在收到相應的廣播之后會對兩者之間的相互距離進行計算,并且對歷史記錄信任過的節(jié)點以及候選簇頭節(jié)點的密集程度進行查找, 最后以最優(yōu)原則為依據(jù)對可信簇頭進行選擇.

具體結(jié)果如表1 所示, 依據(jù)可信任簇頭選取方法,對等候選舉的節(jié)點可信數(shù)值、數(shù)據(jù)采集融合率、信息傳輸耗損和簇結(jié)構(gòu)的負載均衡進行綜合考量.由于18 號節(jié)點選舉值最大, 則讓參照節(jié)點選取其為簇頭節(jié)點, 然后朝簇頭節(jié)點發(fā)出入列申請.

表1 參照點i 的信任節(jié)點選舉數(shù)據(jù)

實驗對HRBNT 算法和改進算法路由層級的建立采取了仿真模擬, 模擬結(jié)果如圖4 和圖5 所示.在原算法中, 無線網(wǎng)的全部節(jié)點會以收到廣播的次數(shù)和頻率為標準來對較近的簇進行選擇; 但在改進算法中, 成員節(jié)點通常會選擇選舉函數(shù)值最大的簇, 并且會向簇頭發(fā)出加入請求, 候選的簇頭在收到請求之后會對本地的信任記錄進行查詢, 然后根據(jù)成員節(jié)點信任值的高低來決定允許或拒絕其加入.

據(jù)仿真結(jié)果數(shù)據(jù)得到, 原算法不能對惡意節(jié)點進行及時地識別和排除, 有時還會將一部分惡意節(jié)點誤認為是網(wǎng)絡流量, 從而導致破壞網(wǎng)絡正常結(jié)構(gòu)的后果;而改進算法則可對惡意簇頭與節(jié)點進行有效的清除,并且還可在最大程度上對簇結(jié)構(gòu)的布局進行優(yōu)化整合.這其中的原因主要在于, 建立路由層級時, 原算法在一定程度上缺乏恰當?shù)男湃螜C制, 但改進算法對可信度、密集度進行了充分考量并利用節(jié)點之間的協(xié)同合作檢測惡意節(jié)點, 使網(wǎng)絡更加安全可信.

圖4 HRBNT 算法在網(wǎng)絡攻擊下的簇結(jié)構(gòu)

圖5 改進算法在網(wǎng)絡攻擊下的簇結(jié)構(gòu)

3 結(jié)語

本研究提出了一種基于節(jié)點信任值的無線傳感網(wǎng)路由算法, 其以節(jié)點信任評估為基礎, 對節(jié)點距離與密集度進行分析考量, 并使用局部最優(yōu)化和分布式策略,經(jīng)過對路由節(jié)點的可信選舉, 預防惡意節(jié)點參與數(shù)據(jù)通信, 保證了層次路由的安全性和可信性, 可對無線傳感網(wǎng)節(jié)點失效和被俘獲所導致的路由安全問題進行有效的解決.