張科峰，王改云

（桂林電子科技大學(xué) 電子工程與自動(dòng)化學(xué)院，廣西 桂林 541004）

在無(wú)線傳感器網(wǎng)絡(luò) WSN（Wireless Sensor Network）中，節(jié)點(diǎn)的能量非常有限，并且不能持續(xù)供電，節(jié)省能量就顯得異常重要。由于傳感器節(jié)點(diǎn)體積小，不可能帶有很大的電池以供節(jié)點(diǎn)消耗，因此節(jié)點(diǎn)的電量是非常有限的。盡管節(jié)點(diǎn)結(jié)構(gòu)簡(jiǎn)單、耗電量不大，但是目前的很多應(yīng)用要求傳感器網(wǎng)絡(luò)可以長(zhǎng)時(shí)間工作，更換電池或給電池充電是不可行的，因此，無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)的一個(gè)目標(biāo)就是有效利用僅有的能量以延長(zhǎng)網(wǎng)絡(luò)壽命[1]。

WSN中傳統(tǒng)的最優(yōu)可信路徑算法（MTP），節(jié)點(diǎn)能量選擇的主要依據(jù)是從鄰居節(jié)點(diǎn)發(fā)送詢問(wèn)報(bào)文來(lái)獲取該節(jié)點(diǎn)的安全度。例如參考文獻(xiàn)[2]采用的就是當(dāng)節(jié)點(diǎn)x請(qǐng)求y節(jié)點(diǎn)路由時(shí)，y節(jié)點(diǎn)發(fā)現(xiàn)x節(jié)點(diǎn)的路由請(qǐng)求中的能量存儲(chǔ)值和本地存儲(chǔ)的值不一致，就向鄰居節(jié)點(diǎn)發(fā)送請(qǐng)求報(bào)文，從返回的請(qǐng)求報(bào)文中綜合判斷后，返回安全度的差異作為判斷，從而作出接收請(qǐng)求與否的決策。參考文獻(xiàn)[2]的算法沒(méi)有考慮P2P技術(shù)中節(jié)點(diǎn)共謀存在的問(wèn)題，并忽略了WSN中網(wǎng)絡(luò)部署結(jié)構(gòu)給其節(jié)點(diǎn)安全度判斷帶來(lái)的影響。而參考文獻(xiàn)[3]通過(guò)對(duì)交互節(jié)點(diǎn)間的局部評(píng)價(jià)進(jìn)行加權(quán)后得出評(píng)價(jià)可信度計(jì)算節(jié)點(diǎn)的全局信譽(yù)值，再采用基于局部評(píng)價(jià)標(biāo)準(zhǔn)差、局部評(píng)價(jià)集中度的方法識(shí)別和抑制共謀攻擊，然后根據(jù)節(jié)點(diǎn)行為的變化更新其信譽(yù)值和評(píng)價(jià)可信度來(lái)抑制節(jié)點(diǎn)共謀行為的發(fā)生。參考文獻(xiàn)[2]中忽略了節(jié)點(diǎn)安全度誤判給整個(gè)路由路徑帶來(lái)的影響，最終導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)能量選擇效率降低。

本文將子博弈精煉模型引入到能量節(jié)點(diǎn)選擇模型中，并就此提出一種最高安全度的能量節(jié)點(diǎn)選擇算法EOP（Energy Optimal Path）。本文設(shè)計(jì)了一個(gè)安全度評(píng)價(jià)函數(shù)，用來(lái)監(jiān)測(cè)整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的安全度，并就節(jié)點(diǎn)安全度的返回值進(jìn)行相似性分析，如果相似性超過(guò)一定的閾值就判斷其存在節(jié)點(diǎn)共謀，并采用繼任節(jié)點(diǎn)簇再次判斷以確定節(jié)點(diǎn)的安全度。

1 傳統(tǒng)基于節(jié)點(diǎn)安全度的能量選擇模型

在傳統(tǒng)基于節(jié)點(diǎn)安全度的能量選擇模型[2]中，節(jié)點(diǎn)安全度的評(píng)價(jià)信息需要從其他節(jié)點(diǎn)收集，因此節(jié)點(diǎn)安全度的確認(rèn)就需要一個(gè)參數(shù)模型進(jìn)行評(píng)價(jià)。節(jié)點(diǎn)安全度判斷是整個(gè)WSN網(wǎng)絡(luò)可信判斷的核心，本文也以節(jié)點(diǎn)安全度來(lái)判斷節(jié)點(diǎn)能量值的有效性。

節(jié)點(diǎn)安全度的內(nèi)容如下：節(jié)點(diǎn)能量和合作度等參數(shù)存儲(chǔ)在本地節(jié)點(diǎn)上，節(jié)點(diǎn)安全度的評(píng)價(jià)信息卻需從鄰居節(jié)點(diǎn)的回復(fù)結(jié)果來(lái)計(jì)算自身的安全度。然而這種安全度收集方式存在數(shù)據(jù)作假問(wèn)題，如節(jié)點(diǎn)被俘且進(jìn)一步對(duì)數(shù)據(jù)造假或者惡意節(jié)點(diǎn)偽造自身安全度。這些問(wèn)題可以通過(guò)圖1提出的安全度檢查來(lái)進(jìn)行驗(yàn)證。傳統(tǒng)的節(jié)點(diǎn)安全度模型如圖1所示。

圖1 傳統(tǒng)的節(jié)點(diǎn)安全度模型

假設(shè)節(jié)點(diǎn)1發(fā)送路由請(qǐng)求節(jié)點(diǎn)5，那么在傳統(tǒng)的節(jié)點(diǎn)安全度模型中，節(jié)點(diǎn)5會(huì)將節(jié)點(diǎn)1的安全度與本地保存的安全度進(jìn)行比較，如果有誤差，節(jié)點(diǎn)5就會(huì)向其所有的鄰居節(jié)點(diǎn)（即節(jié)點(diǎn) 2、3、4、6、7、8、9）發(fā)送一個(gè)驗(yàn)證報(bào)文，這樣節(jié)點(diǎn)5所能依賴的驗(yàn)證節(jié)點(diǎn)有7個(gè)；再假設(shè)節(jié)點(diǎn)5向節(jié)點(diǎn)8發(fā)送請(qǐng)求，那么按照節(jié)點(diǎn)安全度模型，節(jié)點(diǎn)8也會(huì)向其所有的鄰居節(jié)點(diǎn)發(fā)送驗(yàn)證報(bào)文，然而節(jié)點(diǎn) 8就只能依賴 5、7、9這 3個(gè)節(jié)點(diǎn)來(lái)判斷。

該節(jié)點(diǎn)安全度模型的缺點(diǎn)如下：

（1）每個(gè)節(jié)點(diǎn)所能依賴的驗(yàn)證節(jié)點(diǎn)固定，完全存在節(jié)點(diǎn)共謀作假的可能，從而導(dǎo)致網(wǎng)絡(luò)能量過(guò)度消耗的現(xiàn)象。

（2）每個(gè)節(jié)點(diǎn)所依賴的驗(yàn)證節(jié)點(diǎn)個(gè)數(shù)和安全度對(duì)應(yīng)的加權(quán)不一致。路由節(jié)點(diǎn)對(duì)其依賴節(jié)點(diǎn)返回安全度的值是完全不一致的，因此存在誤判斷的情況。

（3）在此路由中可能存在對(duì)某幾個(gè)節(jié)點(diǎn)的過(guò)度信任與依賴，從而導(dǎo)致某些節(jié)點(diǎn)能量過(guò)度消耗，過(guò)早出現(xiàn)死亡節(jié)點(diǎn)的情況。

2 子博弈納什均衡機(jī)制的節(jié)點(diǎn)能量選擇判定

在傳統(tǒng)的節(jié)點(diǎn)安全度模型中，節(jié)點(diǎn)的安全度的評(píng)價(jià)方案還不夠完善。特別是節(jié)點(diǎn)的安全度由節(jié)點(diǎn)所有的鄰居節(jié)點(diǎn)來(lái)評(píng)價(jià)，由此帶來(lái)了節(jié)點(diǎn)共謀的問(wèn)題，并使得安全度值的數(shù)據(jù)不完全可信，最終導(dǎo)致節(jié)點(diǎn)能量消耗增加。本文提出了一種新方案，將子博弈納什均衡理論引入到節(jié)點(diǎn)安全度最優(yōu)路徑的判斷策略中來(lái)。對(duì)每個(gè)節(jié)點(diǎn)返回的安全度值進(jìn)行分塊處理，并剔除節(jié)點(diǎn)安全度值較低的節(jié)點(diǎn)，最終得出一個(gè)可信的安全度值。如果節(jié)點(diǎn)安全度高的一簇節(jié)點(diǎn)返回的評(píng)價(jià)值誤差在￡范圍之內(nèi)，就接受該節(jié)點(diǎn)作為路由節(jié)點(diǎn)。

子博弈納什均衡是將納什均衡中包含的不可置信的威脅策略剔除出去，它要求參與者的決策在任何時(shí)間點(diǎn)上都是最優(yōu)的。子博弈納什均衡的定義如下：

定義1 子博弈納什均衡 （SubgamePerfectNash Equilibrium）中的動(dòng)態(tài)博弈是指各參與者行動(dòng)有先后，后行動(dòng)者根據(jù)先行者所作的選擇來(lái)決定自己的選擇。其中，完全信息博弈表示每個(gè)參與者對(duì)其他參與者的特征、戰(zhàn)略空間和評(píng)價(jià)函數(shù)都了解，子博弈是指整個(gè)博弈過(guò)程中某一階段以后的博弈。它具有初始信息和進(jìn)行博弈分析所需的全部信息[4]。

定義2對(duì)于擴(kuò)展式博弈的策略組合S*=（S1*，…，Si*，…，Sn*），其中，每個(gè)參與者所選擇的戰(zhàn)略都是最優(yōu)的，并且如果它是原博弈的納什均衡，則它在每一個(gè)子博弈上也都構(gòu)成納什均衡，即它是一個(gè)子博弈精煉納什均衡。

子博弈精煉納什均衡是基于每個(gè)參與者自身角度來(lái)考慮所選擇策略的不同收益程度，在此收益程度的基礎(chǔ)上建立一個(gè)策略選擇的過(guò)程，這種過(guò)程用圖來(lái)表示就是一棵“與或樹(shù)”。對(duì)于不同的參與者，這種“與或樹(shù)”是不一樣的，這樣的一棵“與或樹(shù)”就是博弈樹(shù)（Game Rree）。建立起博弈樹(shù)之后求解的一個(gè)解集合就是子博弈精煉納什均衡的解集合?，F(xiàn)在假設(shè)一棵博弈樹(shù)[5]結(jié)構(gòu)如圖2所示，其中，坐標(biāo)分別代表的是根節(jié)點(diǎn)的進(jìn)退策略收益值。

圖2 博弈樹(shù)求解圖

該博弈樹(shù)求解的過(guò)程如下：

（1）若 2 在右，2 將選擇進(jìn)（0，3），因?yàn)椋?，3）＞（3，0）。

（2）若 2 在左，2 將選擇退（3，0），因?yàn)椋?，0）＞（-1，-1）。

（3）在2的選擇中，1的最大收益是選擇進(jìn)，因?yàn)椋?，0）＞（0，3），所以納什均衡為（進(jìn)（進(jìn)，退）），均衡解為（進(jìn)，退），均衡收益為（3，0）。

2.1 節(jié)點(diǎn)安全度選擇模型的建立

基于子博弈精練納什均衡理論，引入子博弈精煉納什均衡的節(jié)點(diǎn)安全度模型建立在如下兩個(gè)定義的基礎(chǔ)上。

定義3 深安全度節(jié)點(diǎn)：它的影響因素包括能量因素和合作度因素。兩組因素加權(quán)處理后共同描述一個(gè)節(jié)點(diǎn)的信任度，深信任度是信任度的前n位值。

定義4 深安全度節(jié)點(diǎn)簇：M個(gè)深信任度節(jié)點(diǎn)組成一個(gè)深信任節(jié)點(diǎn)簇。

基于以上兩個(gè)定義建立的安全度模型如圖3所示。

圖3 子博弈機(jī)制安全度模型

集合S用來(lái)描述一個(gè)深安全度節(jié)點(diǎn)簇，它取自所有網(wǎng)絡(luò)節(jié)點(diǎn)中的前n個(gè)節(jié)點(diǎn)，而在每一次的路由過(guò)程中，全網(wǎng)絡(luò)都需要刷新每個(gè)節(jié)點(diǎn)的安全度值，并對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)依據(jù)安全度值進(jìn)行分簇，對(duì)所有的分簇進(jìn)行遞歸求解子博弈納什均衡，并從納什均衡集中選取最優(yōu)結(jié)果集作為路由請(qǐng)求節(jié)點(diǎn)的仲裁節(jié)點(diǎn)集，此集作為上任節(jié)點(diǎn)選擇該節(jié)點(diǎn)安全度的值是否成為路由節(jié)點(diǎn)的依據(jù)。使用該集合中的元素返回的報(bào)文信息作為判斷依據(jù)。假設(shè)節(jié)點(diǎn)x向節(jié)點(diǎn)y發(fā)送路由請(qǐng)求，當(dāng)y收到x的節(jié)點(diǎn)請(qǐng)求之后判斷本地的存儲(chǔ)的x安全度值，如果誤差范圍存在且超過(guò)閾值￡，就向本次路由中深安全度節(jié)點(diǎn)簇發(fā)送詢問(wèn)報(bào)文。當(dāng)所有深安全度節(jié)點(diǎn)返回的關(guān)于此節(jié)點(diǎn)的安全度值后，對(duì)這些安全度值進(jìn)行分簇，并建立博弈樹(shù)。對(duì)此博弈樹(shù)進(jìn)行遞歸求解，得出一個(gè)最優(yōu)解集。對(duì)解集中的值進(jìn)行相似度判斷，如果相似度高于某閾值a，就認(rèn)為該數(shù)據(jù)不合理，并繼續(xù)之前闡述的子博弈選擇過(guò)程。節(jié)點(diǎn)安全度最優(yōu)解集處理步驟如圖4所示。

圖4 節(jié)點(diǎn)安全度最優(yōu)解集流程圖

2.2 安全度描述算法

每個(gè)節(jié)點(diǎn)的安全度值在每次路由過(guò)程完成之后刷新，本文每個(gè)節(jié)點(diǎn)的安全度值用一個(gè)變量t來(lái)描述，每個(gè)節(jié)點(diǎn)的安全度值與其節(jié)點(diǎn)自身存儲(chǔ)的能量值以及其合作度相關(guān)聯(lián)。t表示節(jié)點(diǎn)當(dāng)前的安全度，e表示節(jié)點(diǎn)自身存儲(chǔ)的能量值，c表示節(jié)點(diǎn)的合作度 （節(jié)點(diǎn)通過(guò)一次路由，合作度值加1）。每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)集合 S（e，c），即當(dāng)前節(jié)點(diǎn)的（能量，合作度），對(duì)相應(yīng)的節(jié)點(diǎn)還存在一個(gè)集合 W（W1，W2），即相應(yīng)的權(quán)值，它們的關(guān)系式為：

其中，W1+W2=1（2）。

假設(shè)m為每個(gè)節(jié)點(diǎn)參與總路由過(guò)程中的成功百分比，那么有如下2個(gè)變量定義：

其中，0.5為修正因子。

其中，0.8為修正參數(shù)。

則有：W1=α/（α+β）；W2=β/（α+β）

針對(duì)不同的應(yīng)用需求，對(duì)W1和W2進(jìn)行不同的權(quán)重選擇，相應(yīng)得出不同安全度。參數(shù)范圍與適用的網(wǎng)絡(luò)環(huán)境關(guān)聯(lián)表如表1所示。

表1 參數(shù)范圍與適用的網(wǎng)絡(luò)環(huán)境關(guān)聯(lián)表

如果是普通節(jié)點(diǎn)全部發(fā)送報(bào)文進(jìn)行咨詢，顯然不能消除一些惡意節(jié)點(diǎn)和不可置信節(jié)點(diǎn)帶來(lái)的威脅，因此需要剔除不可置信節(jié)點(diǎn)。本文采用深安全度節(jié)點(diǎn)簇來(lái)描述一個(gè)高安全度節(jié)點(diǎn)的集合，它集合了一個(gè)WSN網(wǎng)絡(luò)節(jié)點(diǎn)中的前n位安全度高的節(jié)點(diǎn)。每次依據(jù)節(jié)點(diǎn)安全度進(jìn)行路由的流程如圖5所示。

圖5 節(jié)點(diǎn)安全度計(jì)算流程圖

3 實(shí)驗(yàn)方案及仿真

本實(shí)驗(yàn)的目的是將傳統(tǒng)最優(yōu)路徑選擇算法（MTP）[2]與本文提出的EOP算法在網(wǎng)絡(luò)能量空洞以及節(jié)點(diǎn)能量消耗兩個(gè)方面進(jìn)行對(duì)比。

實(shí)驗(yàn)中，設(shè)定傳感器節(jié)點(diǎn)區(qū)域大小為[10，10]，隨機(jī)生成網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為100。子博弈選擇出的安全度優(yōu)化集的相似度閾值為0.7，每個(gè)節(jié)點(diǎn)的合作度初始值在30～100之間隨機(jī)取，網(wǎng)絡(luò)中的節(jié)點(diǎn)能量在20～100之間隨機(jī)取。為了驗(yàn)證本文算法在網(wǎng)絡(luò)節(jié)點(diǎn)能量?jī)?yōu)化上的優(yōu)越性，在隨機(jī)生成的100個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)中進(jìn)行了2 000次的路由過(guò)程記錄，并提取路由過(guò)程中出現(xiàn)的死亡節(jié)點(diǎn)個(gè)數(shù)以及每次路由的節(jié)點(diǎn)能量數(shù)據(jù)，基于提取出的數(shù)據(jù)來(lái)分析網(wǎng)絡(luò)中出現(xiàn)能量空洞以及網(wǎng)絡(luò)節(jié)點(diǎn)能量?jī)?yōu)化效率的問(wèn)題，通過(guò)系統(tǒng)仿真實(shí)驗(yàn)數(shù)據(jù)進(jìn)行如下分析。

兩種方法分別在路由過(guò)程中出現(xiàn)首節(jié)點(diǎn)死亡情況對(duì)比如圖6所示。

圖6 兩種算法出現(xiàn)首節(jié)點(diǎn)死亡路由次數(shù)對(duì)比

由圖6可知，基于安全度算法的無(wú)線傳感器網(wǎng)絡(luò)在第 443、964和 1 750次時(shí)出現(xiàn)首節(jié)點(diǎn)死亡，SOP算法出現(xiàn)首節(jié)點(diǎn)死亡的路由次數(shù)比MTP算法的路由次數(shù)要多，從而可以看出基于子博弈安全度算法在路由安全魯棒性上要優(yōu)于傳統(tǒng)算法。

實(shí)驗(yàn)結(jié)果取的是單組實(shí)驗(yàn)中的50輪實(shí)驗(yàn)結(jié)果，以輪為單位取單輪實(shí)驗(yàn)中所有路徑的路徑安全度平均值，從圖7中可以看出，與傳統(tǒng)算法相比，節(jié)點(diǎn)安全度算法在平均路徑能量值上性能明顯較優(yōu)。在實(shí)際的傳輸過(guò)程中，假定節(jié)點(diǎn)的安全度以100為單位計(jì)算，當(dāng)節(jié)點(diǎn)的安全度少于100×￡（￡<1）時(shí)，路由節(jié)點(diǎn)傳輸被判斷為路由失敗，那么從圖7可以看出，基于子博弈的安全度算法節(jié)點(diǎn)路由成功的概率明顯大于傳統(tǒng)算法。這是由于傳統(tǒng)算法沒(méi)有考慮路徑中安全度的信任問(wèn)題，因此安全性能較差。而更新后的算法中的可信度融入了安全的因素，因此更新后的算法的安全性較優(yōu)。

本文引入子博弈機(jī)制來(lái)實(shí)現(xiàn)節(jié)點(diǎn)能量?jī)?yōu)化算法，首先引入節(jié)點(diǎn)安全度評(píng)價(jià)概念，在此基礎(chǔ)上判斷某個(gè)具體節(jié)點(diǎn)是否可以參與本次路由，有效降低了路由過(guò)程中選擇低能量節(jié)點(diǎn)的現(xiàn)象，從圖6中關(guān)于死亡節(jié)點(diǎn)出現(xiàn)的情況可以得知，路由網(wǎng)絡(luò)的魯棒性有一個(gè)明顯的改善。同時(shí)，從圖7可以得出該算法優(yōu)化了網(wǎng)絡(luò)的能量管理。每次路由過(guò)程中重新選擇不同的節(jié)點(diǎn)安全度進(jìn)行安全度判斷，有效防止了節(jié)點(diǎn)共謀，解決了對(duì)某一個(gè)節(jié)點(diǎn)過(guò)度依賴的問(wèn)題。本方案也有待解決的問(wèn)題和不足之處。本文主要通過(guò)計(jì)算節(jié)點(diǎn)安全度來(lái)判斷某節(jié)點(diǎn)是否可以參與路由的過(guò)程，這會(huì)使得路由節(jié)點(diǎn)過(guò)多從而導(dǎo)致計(jì)算復(fù)雜。如何選擇一個(gè)參數(shù)來(lái)適配計(jì)算復(fù)雜度、網(wǎng)絡(luò)魯棒性以及高能量節(jié)點(diǎn)，同時(shí)對(duì)本文給出的其他兩種環(huán)境的研究，都是后續(xù)研究的方向。

[1]KANNAN R， SARANGI S， IYENGAR S S.Sensor-centric energy-constrained reliable query routing for wireless sensor networks[J].Journal of Parallel and Distributed Computing，2004，64（7）：839-852.

[2]陳作漢，任旭鵬，盧鵬麗.對(duì)抗共謀及節(jié)點(diǎn)行為動(dòng)態(tài)性的 P2P 信任模型[J].計(jì)算機(jī)應(yīng)用，2011，31（2）：308-312.

[3]王江濤，陳志剛，鄧曉衡.WSN中基于完全信息動(dòng)態(tài)博弈的可信路由研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31（8）：1478-1483.

[4]吳廣謀，王文平，尤海燕，等.數(shù)據(jù)，模型與決策[M]北京：石油工業(yè)出版社，2003.

[5]王騏，孫建伶.基于優(yōu)化迭代的博弈樹(shù)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2008，25（2）：228-230.

[6]孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.