基于改進GA和信任感知的無線傳感器網絡安全分簇路由協議

王出航, 王 雪, 胡黃水, 趙宏偉, 韓由佳

(1. 長春師范大學 計算機科學與技術學院, 長春 130032； 2. 吉林建筑科技學院 計算機科學與工程學院, 長春 130114；3. 吉林大學 計算機科學與技術學院, 長春 130012； 4. 長春工業大學 計算機科學與工程學院, 長春 130012)

無線傳感器網絡(WSNs)廣泛應用于軍事、 環境監測和太空探索等領域[1-2]. 為有效延長無線傳感器網絡的生命周期, 可利用分簇路由組織節點并傳輸數據至基站[3-5]. 由于無線傳感器網絡的大規模和動態特性, 路由易受來自網內外各種惡意節點的攻擊[6-9], 因此, 安全分簇路由協議設計成為無線傳感器網絡的研究熱點.

目前, 加密和身份認證是一種有效提高分簇路由安全性的方法. 文獻[8]采用K-means聚類和蟻群優化分簇, 基于球面網格的多橢圓曲線加密路由算法確定路由, 安全地將數據從源節點發送至基站. 但這類算法計算復雜、 能耗較高且通常只能抵御外部攻擊[10]. 而基于信任感知的安全分簇路由能識別惡意節點, 抵抗內部攻擊, 提高網絡安全性[10-12]. 不同于非分簇安全路由算法[13-15]中所有節點都參與路由計算, 分簇安全路由僅選取網絡中信任度高的節點參與最優路徑搜索, 保證網絡安全的同時提高了能量效率. 文獻[10]提出了一種考量多種信任因子結合節點度、 距離的分簇安全路由算法, 其從隨機產生的候選簇頭集中選出信任度值大的節點作為簇頭, 簇頭選擇最近簇頭轉發數據或直接發送給基站. 仿真結果表明, 其能有效評估節點信任值, 提高網絡路由的安全可靠性, 但該算法在計算信任度時忽略了歷史行為影響, 導致計算不準確, 簇頭選舉時隨機選擇候選簇頭, 并且僅基于距離選擇下一跳將導致能量和信任值都較低的節點成為簇頭或中繼簇頭, 從而降低了算法的整體性能. 基于此, 文獻[12]提出了一種基于信任與能耗均衡的安全分簇路由協議, 計算節點綜合信任值時考慮歷史信任, 并采用模糊邏輯計算直接信任值, 根據偏離度對間接信任值進行過濾和權重分配. 路由選擇時距離基站近的簇頭直接與基站通信, 其他簇頭選取剩余能量多、 綜合信任度大且相比距離基站近的簇頭作為其下一跳. 仿真結果表明, 該協議在提升網絡安全和可靠性的同時也提高了網絡數據包傳輸量及能耗均衡性, 但其與文獻[10]算法相同, 隨機選舉簇頭可能將能量和信任值都較低的節點選為簇頭或中繼簇頭, 導致某些節點因能量消耗不均而早死. 文獻[16]提出了一種基于信任云的分簇無線傳感器網絡安全路由方法, 選取網絡中節點度高、 剩余能量大、 信譽好的節點作為簇頭, 并利用粒子群進行優化, 同時為降低簇頭的負荷, 選出專門的信任云節點負責簇內節點信譽的計算, 并把結果反饋給簇頭, 路由選擇時距離自身近且信譽好的簇頭成為下一跳或直接發送至基站. 仿真結果表明, 該方法能應對無線傳感器網絡中的路由安全問題, 且能有效控制節點的能耗, 但現有路由安全算法都通過本地決策選擇簇頭并選擇簇頭下一跳, 無法找到最優簇頭和路徑. 此外, 現有算法在信任值計算、 簇頭選舉和路由選擇時通常不考慮節點負載, 導致網絡負載不均衡, 從而降低了網絡生命周期. 而遺傳算法具有良好的全局搜索能力, 常用于尋找最優簇頭或路由[17]. 但基本遺傳算法存在收斂速度較慢、 易陷入局部最優等缺點[18-20].

針對上述問題, 本文提出一種采用改進遺傳算法同時選擇最優簇頭和搜索最佳路徑的安全路由協議SCRGA(a trust-aware secure clustering routing protocol for wireless sensor networks using an enhanced genetic algorithm). 將簇頭選舉和路由搜索用同一個染色體編碼, 并基于簇頭綜合信任值最大、 全網能量消耗最小以及負載均衡為目的構建適應度函數, 遺傳操作時定義約束條件避免產生非合理個體, 并將上一輪最優染色體加入初始種群, 保持種群多樣性以避免局部最優并提高收斂速度. 仿真結果表明, SCRGA協議相比其他算法具有更好的能量效率和負載均衡性, 在保障網路安全的基礎上有效延長了其生命周期.

1 確定節點綜合信任值

與傳統安全路由算法相同, 節點的綜合信任值是參與簇頭選舉和路徑搜索的關鍵[15,17], 綜合信任值越大的節點安全性越高, 更有可能被選為簇頭和中繼節點. SCRGA組合節點的直接和間接信任值確定其綜合信任值.

1.1 節點直接信任值

節點根據鄰居節點的接收和發送數據包個數, 計算其對每個鄰居節點的直接信任值, 節點i對鄰居節點j的直接信任值可表示為

(1)

其中: 等式右側第一項表示歷史信任值, 第二項表示當前信任值；γ和1-γ(0<γ<1)分別是歷史信任值和當前信任值的權重, 其值大小根據實際的WSN確定, 本文令γ=0.5;Rt和St分別表示發送和接收的數據包數量占總數據包數量的比例, 可表示為

(2)

(3)

此外, 還定義了揮發因子, 目的是快速降低從具有高信任度值的普通節點被捕獲成為惡意節點的信任值.揮發因子計算公式為

ω1=e-c1mod(T,τ),

(4)

ω2=e-c2mod(T,τ),

(5)

其中T為網絡的當前時間,τ為時間閾值,c1和c2為用于調整信任值變化速度的常數.引入mod(T,τ)是為保證歷史信任值不會太小, 并使揮發因子在一定范圍內周期性衰減.

1.2 節點的間接信任值

節點i對節點j的間接信任值由其公共鄰居節點提供的直接信任值計算得到.公共鄰居節點集合可以用Bh={B1,B2,…,Bm}表示, 其中m是公共節點個數.節點i對節點j的間接信任值表示為

(6)

(7)

其中p為節點i的鄰居節點個數.

2 確定最優簇頭和最佳路徑

SCRGA采用改進的遺傳算法同時進行簇頭選舉和路徑搜索, 為提高收斂速度, 本文從染色體編碼、 選擇、 交叉和變異操作以及終止條件方面進行改進, 特別是構造了基于綜合信任值、 能量消耗和負載的適應度函數, 使選出的簇頭和路徑綜合信任度較高、 能量消耗較小且負載均衡, 從而有效延長網絡生命周期.

2.1 構造適應度函數

設n為網絡節點數,H={h1,h2,…,hk}為簇頭集合,M={m1,m2,…,mq}為成員集合, 則有k+q=n.為計算方便, 將基站表示為hk+1；dij為節點i和j之間的距離,dmax表示其最大值；

CHmi={hj|?hj∈H∧0

為成員mi的候選簇頭集,Hmi為mi的簇頭;

nxCHhi={hj|?hj∈(H∪hk+1)∧dhihk+1>dhjhk+1∧dhihj≤dmax}

為簇頭hi的下一跳候選簇頭集, 且nxHhi為hi的下一跳簇頭,nHhi表示簇頭hi作為中繼的次數.用Ld表示節點負載；Einitial表示節點的初始能量,Eresiduali表示節點i的剩余能量.

采用文獻[7,13]的能量消耗模型, 即節點i發送l位數據到節點j, 其消耗的能量為

(8)

ERij=l×Eelec,

(9)

融合l位數據消耗的能量為

EDA=l×EpDb,

(10)

其中EpDb是融合l位數據的能耗.

由式(8)～(10)計算得到每個簇頭節點和成員節點消耗的能量分別為

于是, 可求出整個網絡的能量消耗為

(13)

SCRGA的目標之一是最小化Etotal, 由式(13)可見, 其能均勻分布簇, 因為它既考慮了簇間也考慮了簇內能量最小. 分簇網絡中成員節點的負載均相同, 因此網絡負載均衡僅考慮簇頭, 表示為

(14)

為加速算法收斂, 考慮只有當節點自身剩余能量和綜合信任值大于網絡平均剩余能量和網絡平均綜合信任值時才參與簇頭選舉, 即對任意的hi, 滿足

(15)

此外, 為找到可信度高的路由路徑, 考慮整個簇頭的平均綜合信任值, 表示為

(16)

SCRGA的第三個目標是保障簇頭和路由的安全, 因此, 構建如下適應度函數：

(17)

通過該函數找到安全可靠、 能量效率高和負載均衡的最優簇頭和最佳路徑.

2.2 遺傳操作

SCRGA采用實數編碼表示染色體, 且簇頭選擇和路由搜索用一個染色體表示, 不增加染色體長度的同時提高算法效率, 即染色體的前部分表示路由搜索, 后部分表示簇頭選擇, 如圖1所示.

圖1 簇頭選擇和路由搜索的染色體表示Fig.1 Chromosome representation for cluster heads selection and routing search

首先, 由圖1可見, 從100個節點中根據式(15)任意選出k個(k=6)簇頭9,23,48,69,81,95, 根據變量定義可得到每個成員節點的候選簇頭集和每個簇頭的下一跳候選簇頭集. 根據

?gj|{(gi∈nxCHhi,i∈[1-k])||(gi∈CHmi-k,i∈[k+1,n])}

(18)

計算染色體中各基因, 分別得到每個成員節點的簇頭, 成員1的簇頭為9, 成員2的簇頭為48,…, 成員100的簇頭為48. 同理, 可分別得到每個簇頭到基站的路由路徑, 9→81→23→BS, 23→BS, 48→95→BS, 69→48→95→101, 81→23→BS, 95→BS. 由于對染色體的基因進行了約束, 既保證了染色體的合理性又提高了算法收斂性. 依此可得到初始種群.

其次, 對初始種群中的每個染色體根據式(17)分別計算其適應度值, 并按從小到大排列. 采用精英選擇策略選取15%的精英個體直接遺傳到下一代種群, 其他的執行交叉操作. 由于染色體由兩部分構成, 所以采用兩點交叉生成子染色體, 即在父染色體的路由搜索和簇頭選舉部分各隨機確定一個交叉點, 對交叉點之間的基因進行交換, 如圖2所示.

圖2 染色體兩點交叉Fig.2 Two-point crossover of chromosome

由圖2可見, 生成的子染色體同樣為合理染色體, 對生成的兩個子染色體根據式(17)分別計算其適應度值, 并與相應的父染色體適應度值進行比較, 適應度小的用于變異操作. 然后采用位變異對各染色體進行變異操作, 即隨機選取某個位置基因修改為新基因, 新基因利用式(18)生成, 以保證新染色體的合理性. 生成的新染色體采用式(17)計算其適應度值并與父染色體進行比較, 適應度值小的遺傳至下一代. 于是, 所有變異操作后保留的染色體結合精英染色體形成新一代種群. 如果迭代次數達到預設的值或滿足

(19)

則算法終止, 其中ω為種群大小,ε為一個任意較小的正數, 用于表明種群個體差異, 與文獻[15]相同取10-5. 一旦算法終止, 種群中適應度值最小的個體即為最優解, 并將該最優解加入下一輪初始種群中加快算法收斂. 算法流程如圖3所示.

圖3 改進的遺傳算法流程Fig.3 Flow chart of improved geneic algorithm

3 仿真分析

為驗證SCRGA的性能, 在MATLAB環境下對其進行仿真測試, 并與TC-SRA[13]及文獻[7]提出的改進遺傳算法(簡稱SRBNT)進行比較分析. 網絡中100個節點隨機分布在100 m×100 m的目標區域, 基站位于中心(50 m,50 m), 同時將10個惡意節點分布在網絡中, 仿真參數設置如下： 節點初始能量為1 J,Eelec=50 nJ/bit,εfs=10(pJ·bit-1)/m2,εmp=0.0013(pJ·bit-1)/m4,EpDb=5 nJ/bit, 數據包大小為4 000 bit, 控制包大小為200 bit, 節點的最大通信范圍dmax=50 m, 交叉率為0.85, 變異率為0.04, 種群數為200.

丟包率是評價網路安全的重要指標之一. 圖4為3種不同算法在不同惡意節點數目下的丟包率對比結果. 由圖4可見, 隨著惡意節點數的增加, 3種算法的丟包率都呈上升趨勢, 但SCRGA的丟包率低于TC-SRA, 平均減少了15.98%的丟包率. 這主要是因為SCRGA考慮了歷史信任對現在的影響, 引入了揮發因子降低歷史信任值對節點的綜合信任值作用, 提高了檢測惡意節點的速度. 與SRBNT相比, SCRGA的丟包率平均降低了19.44%. 這是因為SRBNT的時間因子是預先設定值, 隨著網絡的運行, 時間因子可能不再適用網絡的信任評價功能. 因此, SCRGA總體優于TC-SRA和SRBNT的安全性能.

當網絡存在惡意節點時, 其數量越多, 存在網絡中時間越長, 則基站收到的數據包數量就越少. 圖5為基站收到的數據量隨惡意節點數量增加而降低時3種算法的對比結果. 由圖5可見, 當網絡存在2,4,6,8,10個惡意節點時, SCRGA基站收到的數據總量分別為30 747 KB,29 565 KB,28 357 KB,27 155 KB,25 917 KB； 比TC-SRA分別提升了1.69%,2.16%,3.03%,2.95%,3.41%； 比SRBNT分別提升了3.40%,6.03%,7.32%,7.64%,8.72%.

圖4 3種算法在不同惡意節點下的網絡丟包率對比Fig.4 Comparison of packet loss rate of three algorithms in different malicioius nodes

圖5 3種算法在不同惡意節點下基站收到的數據量對比Fig.5 Comparison of data received by BS of three algorithms in different malicioius nodes

對于資源受限的無線傳感器網絡, 網絡的剩余能量是評價網絡性能的重要指標之一. 圖6為3種算法的網絡能量對比結果. 由圖6可見, 隨著網絡的運行, 網絡的剩余能量逐漸下降. SRBNT和TC-SRA的曲線斜率更大, 說明網絡的能量消耗較快. 而SCRGA網絡的剩余能量多于SRBNT和TC-SRA, 這是因為SCRGA設計遺傳算法的適應度函數時, 除考慮節點的綜合信任值外還考慮了簇頭節點承擔的負載和網絡能量消耗兩個指標, 合理地規劃了每個簇頭節點應承擔的負載大小, 從而提高了網絡的能量效率.

圖7為3種算法的網絡存活節點數對比結果. 通常網絡存活節點數越多, 基站收到的相關數據就越多, 網絡的性能也越好. 由圖7可見, SCRGA通過遺傳算法均勻選舉簇頭, 網絡的能量消耗較均衡, SCRGA比SRBNT和TC-SRA的網絡生命周期長. 而SRBNT比TC-SRA的網絡生命周期短, 是因為SRBNT需要采集和計算眾多因子, 從而增加了節點間信息的交互次數, 消耗了更多能量.

圖6 3種算法的網絡剩余能量對比Fig.6 Comparison of network residual energy of three algorithms

圖7 3種算法的網絡剩余節點數對比Fig.7 Comparison of number of surviving nodes of three algorithms

綜上所述, 為提高信任感知無線傳感器網絡分簇路由的安全可靠性以及能量效率和負載均衡, 本文提出了一種基于改進遺傳算法的新協議SCRGA. 以最大化平均綜合信任值、 最小化網絡能耗和均衡網絡負載為目標, 采用改進遺傳算法搜索全局最優解, 得到全網最優簇頭集和最佳路由路徑. 仿真結果表明, 無論是在能耗、 丟包率還是網絡延遲方面, SCRGA均優于TC-SRA和SRBNT的性能, 而且對黑洞攻擊、 選擇性轉發攻擊、 Hello洪泛攻擊、 蟲洞攻擊和槽洞攻擊有良好的防御作用.