基于改進(jìn)GA和信任感知的無線傳感器網(wǎng)絡(luò)安全分簇路由協(xié)議

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

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

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

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

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

1 確定節(jié)點綜合信任值

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

1.1 節(jié)點直接信任值

節(jié)點根據(jù)鄰居節(jié)點的接收和發(fā)送數(shù)據(jù)包個數(shù), 計算其對每個鄰居節(jié)點的直接信任值, 節(jié)點i對鄰居節(jié)點j的直接信任值可表示為

(1)

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

(2)

(3)

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

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

(4)

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

(5)

其中T為網(wǎng)絡(luò)的當(dāng)前時間,τ為時間閾值,c1和c2為用于調(diào)整信任值變化速度的常數(shù).引入mod(T,τ)是為保證歷史信任值不會太小, 并使揮發(fā)因子在一定范圍內(nèi)周期性衰減.

1.2 節(jié)點的間接信任值

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

(6)

(7)

其中p為節(jié)點i的鄰居節(jié)點個數(shù).

2 確定最優(yōu)簇頭和最佳路徑

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

2.1 構(gòu)造適應(yīng)度函數(shù)

設(shè)n為網(wǎng)絡(luò)節(jié)點數(shù),H={h1,h2,…,hk}為簇頭集合,M={m1,m2,…,mq}為成員集合, 則有k+q=n.為計算方便, 將基站表示為hk+1；dij為節(jié)點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作為中繼的次數(shù).用Ld表示節(jié)點負(fù)載；Einitial表示節(jié)點的初始能量,Eresiduali表示節(jié)點i的剩余能量.

采用文獻(xiàn)[7,13]的能量消耗模型, 即節(jié)點i發(fā)送l位數(shù)據(jù)到節(jié)點j, 其消耗的能量為

(8)

ERij=l×Eelec,

(9)

融合l位數(shù)據(jù)消耗的能量為

EDA=l×EpDb,

(10)

其中EpDb是融合l位數(shù)據(jù)的能耗.

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

于是, 可求出整個網(wǎng)絡(luò)的能量消耗為

(13)

SCRGA的目標(biāo)之一是最小化Etotal, 由式(13)可見, 其能均勻分布簇, 因為它既考慮了簇間也考慮了簇內(nèi)能量最小. 分簇網(wǎng)絡(luò)中成員節(jié)點的負(fù)載均相同, 因此網(wǎng)絡(luò)負(fù)載均衡僅考慮簇頭, 表示為

(14)

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

(15)

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

(16)

SCRGA的第三個目標(biāo)是保障簇頭和路由的安全, 因此, 構(gòu)建如下適應(yīng)度函數(shù)：

(17)

通過該函數(shù)找到安全可靠、 能量效率高和負(fù)載均衡的最優(yōu)簇頭和最佳路徑.

2.2 遺傳操作

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

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

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

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

(18)

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

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

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

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

(19)

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

圖3 改進(jìn)的遺傳算法流程Fig.3 Flow chart of improved geneic algorithm

3 仿真分析

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

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

當(dāng)網(wǎng)絡(luò)存在惡意節(jié)點時, 其數(shù)量越多, 存在網(wǎng)絡(luò)中時間越長, 則基站收到的數(shù)據(jù)包數(shù)量就越少. 圖5為基站收到的數(shù)據(jù)量隨惡意節(jié)點數(shù)量增加而降低時3種算法的對比結(jié)果. 由圖5可見, 當(dāng)網(wǎng)絡(luò)存在2,4,6,8,10個惡意節(jié)點時, SCRGA基站收到的數(shù)據(jù)總量分別為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種算法在不同惡意節(jié)點下的網(wǎng)絡(luò)丟包率對比Fig.4 Comparison of packet loss rate of three algorithms in different malicioius nodes

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

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

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

圖6 3種算法的網(wǎng)絡(luò)剩余能量對比Fig.6 Comparison of network residual energy of three algorithms

圖7 3種算法的網(wǎng)絡(luò)剩余節(jié)點數(shù)對比Fig.7 Comparison of number of surviving nodes of three algorithms

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