無線傳感網絡惡意節點識別算法①

周文雄, 林 穗

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

引言

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

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

1 算法設計

1.1 簇頭節點的可信選舉

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

圖1 無線傳感網層次路由的拓撲結構

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

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

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

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

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

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

1.2 算法優化

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

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

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

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

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

圖2 實際網絡聯機情形

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

圖3 簇結構的形成過程

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

1.3 閾值的確定

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

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

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

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

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

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

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

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

2 算法實驗與結果分析

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

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

表1 參照點i 的信任節點選舉數據

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

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

圖4 HRBNT 算法在網絡攻擊下的簇結構

圖5 改進算法在網絡攻擊下的簇結構

3 結語

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