WSN中基于子博弈的節(jié)點能量優(yōu)化算法研究*

張科峰，王改云

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 博弈樹求解圖

該博弈樹求解的過程如下：

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

（2）若 2 在左，2 將選擇退（3，0），因為（3，0）＞（-1，-1）。

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

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

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

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

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

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

圖3 子博弈機制安全度模型

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

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

2.2 安全度描述算法

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

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

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

其中，0.5為修正因子。

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

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

針對不同的應(yīng)用需求，對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é)點全部發(fā)送報文進(jìn)行咨詢，顯然不能消除一些惡意節(jié)點和不可置信節(jié)點帶來的威脅，因此需要剔除不可置信節(jié)點。本文采用深安全度節(jié)點簇來描述一個高安全度節(jié)點的集合，它集合了一個WSN網(wǎng)絡(luò)節(jié)點中的前n位安全度高的節(jié)點。每次依據(jù)節(jié)點安全度進(jìn)行路由的流程如圖5所示。

圖5 節(jié)點安全度計算流程圖

3 實驗方案及仿真

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

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

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

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

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

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

本文引入子博弈機制來實現(xiàn)節(jié)點能量優(yōu)化算法，首先引入節(jié)點安全度評價概念，在此基礎(chǔ)上判斷某個具體節(jié)點是否可以參與本次路由，有效降低了路由過程中選擇低能量節(jié)點的現(xiàn)象，從圖6中關(guān)于死亡節(jié)點出現(xiàn)的情況可以得知，路由網(wǎng)絡(luò)的魯棒性有一個明顯的改善。同時，從圖7可以得出該算法優(yōu)化了網(wǎng)絡(luò)的能量管理。每次路由過程中重新選擇不同的節(jié)點安全度進(jìn)行安全度判斷，有效防止了節(jié)點共謀，解決了對某一個節(jié)點過度依賴的問題。本方案也有待解決的問題和不足之處。本文主要通過計算節(jié)點安全度來判斷某節(jié)點是否可以參與路由的過程，這會使得路由節(jié)點過多從而導(dǎo)致計算復(fù)雜。如何選擇一個參數(shù)來適配計算復(fù)雜度、網(wǎng)絡(luò)魯棒性以及高能量節(jié)點，同時對本文給出的其他兩種環(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]陳作漢，任旭鵬，盧鵬麗.對抗共謀及節(jié)點行為動態(tài)性的 P2P 信任模型[J].計算機應(yīng)用，2011，31（2）：308-312.

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

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

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

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