基于非合作博弈的簇間能量優(yōu)化路由算法研究

林德鈺， 王 泉

(西安電子科技大學 計算機學院，710071 西安)

基于非合作博弈的簇間能量優(yōu)化路由算法研究

林德鈺， 王 泉

(西安電子科技大學 計算機學院，710071 西安)

針對無線傳感器網(wǎng)絡(WSNs)的簇間路由進行詳細研究，指出目前簇間路由中存在的能量耗散不均衡問題. 通過實際例子指出簇間能耗不均的原因，即各個簇頭節(jié)點的自私性導致數(shù)據(jù)流量分布不均，進而引發(fā)能耗的分布不均. 在此基礎之上，提出規(guī)范各個簇頭節(jié)點行為的非合作簇間路由博弈模型，得出并證明該博弈的Nash均衡點(NEP). 然后基于此博弈模型提出本文的路由算法——基于非合作博弈的簇間能量優(yōu)化路由算法EIRNG. 最后，進行詳盡的仿真實驗，分別針對網(wǎng)絡的能量效率以及網(wǎng)絡性能進行橫向及縱向?qū)Ρ龋瑢嶒灲Y果表明，通過引入平衡因子θi，各層簇頭可選擇最優(yōu)數(shù)據(jù)轉(zhuǎn)發(fā)量，從而網(wǎng)絡中的簇頭之間的能量消耗趨于均衡. 與經(jīng)典分簇算法PEGASIS以及作者前期工作EEREG相比，采用EIRNG時網(wǎng)絡生命期可延長分別為74.1%及8.6%. 因此，基于非合作博弈的簇間路由能量優(yōu)化算法EIRNG可有效地提高能量效率以及提高網(wǎng)絡的性能.

無線傳感器網(wǎng)絡；簇間路由；Nash均衡點；非合作博弈；網(wǎng)絡性能

無線傳感器網(wǎng)絡(wireless sensor networks, WSNs)是由大量具有感知、處理以及路由功能的節(jié)點構成的網(wǎng)絡系統(tǒng)[1]. 盡管與傳統(tǒng)網(wǎng)絡節(jié)點相比，傳感器節(jié)點的處理能力、存儲容量受到限制，但是它所具有的小體積、低成本使其應用范圍相當廣泛[2]. 具體來說，傳感器可以密集鋪設的方式組成網(wǎng)絡系統(tǒng)應用于環(huán)境監(jiān)測、軍事監(jiān)測、醫(yī)療護理、瀕危物種的跟蹤以及災后安全救援等[1-3].

由于大多數(shù)的傳感器節(jié)點采用電池供能，并且在網(wǎng)絡部署完畢之后一般不可能或者難以給節(jié)點再充電或者補充能量[4-6]. 比如，地震或者火山監(jiān)測等危險區(qū)域、敵軍跟蹤等應用場景中，給節(jié)點補充能量往往是不切實際的. 而當網(wǎng)絡中某個或者某些節(jié)點能量耗盡時，將會造成網(wǎng)絡的分區(qū)或者隔離，監(jiān)測數(shù)據(jù)無法傳輸至Sink節(jié)點，這就意味著網(wǎng)絡生命的終結. 因此，如何減少節(jié)點的能量消耗對于以數(shù)據(jù)為中心的傳感器網(wǎng)絡而言至關重要. 一般而言，傳感器節(jié)點的能耗主要在于數(shù)據(jù)感知、數(shù)據(jù)處理以及數(shù)據(jù)通信等方面. 其中，通信模塊所消耗的能量是最主要的[4]. 為減少通信模塊所消耗的能量，近年來出現(xiàn)不少的路由算法，其中較為普遍也較為有效的是聚簇路由算法. 由于無線傳感器具有節(jié)點的密集鋪設的特點，在相同或者相近的監(jiān)測區(qū)域數(shù)據(jù)相關性較大，因此聚簇算法通過選取能量較高的節(jié)點作為簇頭節(jié)點來對數(shù)據(jù)進行壓縮來減少冗余數(shù)據(jù)的發(fā)送進而減少能量消耗[7-20]. 其中，有采用隨機方式選舉簇頭節(jié)點的方法，如LEACH協(xié)議[9],以及按照節(jié)點剩余能量進行簇頭選舉的協(xié)議[10-12]，也有采用社會經(jīng)濟學原理，比如引入社會福利函數(shù)的方法[13].

大部分聚簇路由協(xié)議都針對WSNs存在的“Hot Spot Problem”進行詳盡的分析，其中有采用均勻分簇的方法，輪轉(zhuǎn)法更換簇頭角色，如LEACH以及LEACH-C協(xié)議[9]. 然而，大多數(shù)文獻尚未考慮到簇頭在進行數(shù)據(jù)轉(zhuǎn)發(fā)時存在的能耗不均問題，包括本文作者之前的提出的EEREG[14]也僅局限于簇內(nèi)能效優(yōu)化. 因此，本文在原來的簇頭路由協(xié)議的基礎之上，對簇間路由不均問題做進一步研究，將非合作博弈論[15]用于規(guī)范簇頭數(shù)據(jù)轉(zhuǎn)發(fā)過程，實現(xiàn)簇頭間的能量均衡，從而進一步延長網(wǎng)絡生命期.

本文通過一個簡單例子指出簇間能耗不均的事實存在. 提出高能效的簇間路由算法的博弈模型，針對該博弈模型給出Nash均衡點并且給出相應的理論證明. 基于非合作博弈理論提出本文的EIRNG路由算法，該算法可以作為本文作者之前提出的協(xié)議的EEREG[14]的補充. 最后，對提出的EIRNG路由算法進行實驗仿真，首先定義網(wǎng)絡生命期以及其他的能量效率的指標. 并針對能量效率與EEREG以及其他的著名的聚簇路由協(xié)議進行對比分析. 驗證本協(xié)議在能量效率方面的優(yōu)越性，證實EIRNG能夠延長網(wǎng)絡生命期.

1 簇間能耗不均問題

如上圖1(a)所示，a，b，c和d分別表示簇頭節(jié)點，其中a，d表示數(shù)據(jù)源節(jié)點，圓圈內(nèi)部數(shù)字表示當前時刻各個幾點的剩余能量Ere，同時鏈路之間的通信能耗已經(jīng)相應的標示出來. 現(xiàn)在考慮源節(jié)點a，d的路由策略，假設節(jié)點b和節(jié)點c均在a和d的通信范圍內(nèi). 由于節(jié)點的自私性，所以節(jié)點a和d的理性偏好都是選擇節(jié)點b作為轉(zhuǎn)發(fā)的下一跳節(jié)點. 當節(jié)點a和節(jié)點d數(shù)據(jù)傳輸完畢，各個簇頭節(jié)點的剩余能量如圖1(c)所示，此時節(jié)點的能量極差為4.3.

假設現(xiàn)在采取一定策略規(guī)范節(jié)點的轉(zhuǎn)發(fā)行為，使得a和d在數(shù)據(jù)轉(zhuǎn)發(fā)時同時根據(jù)自身發(fā)送能耗以及接收節(jié)點的剩余能量來選擇轉(zhuǎn)發(fā)量. 如圖2所示，這里為簡單起見，假設a和d分別采取如下轉(zhuǎn)發(fā)策略：d將全部數(shù)據(jù)轉(zhuǎn)發(fā)至b，a將全部數(shù)據(jù)轉(zhuǎn)發(fā)至節(jié)點c，數(shù)據(jù)轉(zhuǎn)發(fā)完畢之后，各個簇頭剩余能量如圖2(c)所示. 由圖可知，此時簇頭節(jié)點的能量極差為2.7，顯然比圖1小，能耗不均問題有所改善.

圖1 簇間路由能耗不均問題

圖2 采用一定策略控制簇間路由能耗不均問題

Fig.2 A certain strategy adopted to alleviate the energy consumption imbalance

2 系統(tǒng)模型及相關假設

2.1 能耗模型

本文采用文獻[2-5]所采用的一階無線電模型來描述傳感器節(jié)點的傳輸功耗. 具體形式如下式：

erx=bEelec，

(1)

etx=b(Eelec+εampdα).

(2)

式中：erx和etx分別表示節(jié)點接收、發(fā)送bbit數(shù)據(jù)所消耗的能量；Eelec表示發(fā)送與接收電路發(fā)送或者接收單位bit數(shù)據(jù)所消耗的能量；εamp表示放大電路能耗以及d表示傳輸距離；α代表衰減系數(shù). 一般而言，α取值可在2～4之間. 為降低能耗，本文控制節(jié)點傳輸半徑不大于87米[9]，使其為2. 由此能耗模型可看出，當通信半徑固定時，節(jié)點的通信能耗取決于節(jié)點的數(shù)據(jù)量，所以可通過規(guī)范數(shù)據(jù)通信流量分布來實現(xiàn)能耗的均衡，這正是本文的出發(fā)點.

2.2 網(wǎng)絡模型

圖3所示為本文采用的網(wǎng)絡模型，整個區(qū)域為一扇形區(qū)域，Sink節(jié)點位于圓心處. 假設整個區(qū)域可分為k個扇形環(huán). 每個扇形環(huán)之間的間隔是d. 另外，整個網(wǎng)絡模型只是為本文論證方便，具體算法可適用圓形，長方形等一系列其他形狀.

2.3 相關假設

所有傳感器節(jié)點一經(jīng)鋪設之后，均保持靜止，并且具有相同的初始能量.

網(wǎng)絡拓撲見圖3，其模型可進一步擴展，整個監(jiān)控區(qū)域可以是圓形或者正方形或者其他任意形狀. 整個網(wǎng)絡采用分層次的拓撲，每層之間的距離為87 m，這可以保障節(jié)點的數(shù)據(jù)傳輸屬于自由空間傳輸模型.

圖3 網(wǎng)絡模型

每個傳感器節(jié)點可以調(diào)整自己的傳輸半徑，但傳輸半徑小于87 m.

Sink節(jié)點與普通節(jié)點相比具有無限數(shù)據(jù)處理能力、存儲容量，以及具有無限制的能量.

假設網(wǎng)絡報文可無限分割且可以分割成無限小，并且以網(wǎng)絡拓撲中的任意一扇形環(huán)中的所有節(jié)點作為研究對象.

3 基于非合作博弈的簇間路由算法

在無線傳感器網(wǎng)絡中，由于簇頭節(jié)點的理性以及自私性，所以在轉(zhuǎn)發(fā)數(shù)據(jù)時偏向于選取最不消耗能量的下一跳節(jié)點. 根據(jù)2.1節(jié)的能耗模型可知，傳輸距離越大，發(fā)送能耗越大. 因此，在簇頭節(jié)點傳輸數(shù)據(jù)時，偏向于選取離自己最近的鄰居作為下一跳節(jié)點. 然而根據(jù)第一節(jié)的例子可知，從整個網(wǎng)絡生命期來看這種選取下一跳的策略未必是最優(yōu)的. 因此，為克服個體的自私性以達到整體的最優(yōu)化，可采用博弈論[15]的方法來規(guī)范路徑的選取.

3.1 博弈模型

如圖4(a)所示，非合作博弈中，每個博弈參與者從自己利益出發(fā)，選取使得自身利益最大的策略. 在本文中，體現(xiàn)為每個節(jié)點理性偏好于發(fā)送最大數(shù)據(jù)量至離自身距離最近的節(jié)點. 這會導致很多節(jié)點向同一節(jié)點發(fā)送過多數(shù)據(jù)，從而導致該節(jié)點的能量提前耗盡. 因此必須制定相應策略來規(guī)范每個博弈方的行為. 圖4(b)所示的網(wǎng)絡模型中，整個網(wǎng)絡分為k個層次，每層中所有節(jié)點作為博弈參與者，博弈參與者采用的策略是依據(jù)一定的效用函數(shù)，確定發(fā)送至下一層節(jié)點的最優(yōu)通信量，此通信量可使其效用函數(shù)最優(yōu). 整個網(wǎng)絡中的每一層內(nèi)所有節(jié)點均進行相應的單步博弈，這樣可在優(yōu)化能量效率的同時減少網(wǎng)絡時延. 本博弈模型如下

(P,S,U).

(3)

在此單次能量優(yōu)化博弈模型中，把網(wǎng)絡拓撲中的任意一層k(1≤n≤k)中所有節(jié)點作為博弈模型的參與者，假設第n層中具有的節(jié)點數(shù)目為N，則參與者集合表示為

P={Pi|1≤i≤N}.

(4)

每個博弈方依據(jù)自己的效用函數(shù)采取行動，而無需知道其他博弈方的具體策略. 在文中博弈參與者所采取的策略為控制發(fā)往上一層(k-1)中的某個節(jié)點的數(shù)據(jù)量. 根據(jù)前面分析可知，通過合理規(guī)劃數(shù)據(jù)量的發(fā)送可有效提高能量效率. 因此，博弈參與者的策略集為

S=(s1,s2,…,sN).

(5)

其中每個節(jié)點的策略為

si=Dij.

(6)

表示節(jié)點i向節(jié)點j傳送的數(shù)據(jù)量.

節(jié)點j的容量為

(7)

其中Ej表示節(jié)點j計劃用于接收能量的能耗.

3.2效用函數(shù)

先定義平衡因子如下

(8)

對于博弈方Pi的收益函數(shù)表示如下

).

(9)

式中s-i表示除了節(jié)點i之外的所有其他節(jié)點的策略. 由式(8)可知道，該效用函數(shù)同時考慮了發(fā)送節(jié)點的發(fā)送能耗，以及接收節(jié)點j的接收能耗，因此該效用函數(shù)可以較好地平衡能量消耗.

(10)

(11)

令i取所有可能值(1,2,…,N)代入(11)中可得：

(12)

再將(12)代入(11)中，可得：

引理3.2第k層任意博弈方i向鄰居層k-1節(jié)點j所發(fā)送的數(shù)據(jù)量由兩者之間的能耗決定，并且當所有博弈方與節(jié)點j通信能耗相同時，所有節(jié)點發(fā)送等量的數(shù)據(jù)包是本博弈的Nash均衡點.

證明由式(2)可知，節(jié)點單位數(shù)據(jù)的發(fā)送能耗由傳輸距離決定，同時根據(jù)式(8)可知，平衡因子θi與傳輸距離相關，再由式(12)可知，博弈的Nash均衡點由影響因子θi決定，所以每個博弈方發(fā)送的最優(yōu)數(shù)據(jù)量由其發(fā)送能耗決定. 特別地，當所有博弈方的發(fā)送能耗相同時，即所有節(jié)點i(1<=i<=N)與節(jié)點j等距時，θ1=θ2=…=θN，此時，所有節(jié)點發(fā)送等量數(shù)據(jù)至j(1<=j<=M)節(jié)點.

圖4 非合作博弈模型

從引理3.1和3.2可知，本文的非合作博弈模型存在Nash均衡點，并且可看出節(jié)點發(fā)送的數(shù)據(jù)量既考慮到發(fā)送節(jié)點的發(fā)送能耗，同時也顧及到接收節(jié)點的接收能耗. 得出的最佳策略是由平衡因子θi以及cj的函數(shù)，其中平衡因子θi代表發(fā)送節(jié)點的發(fā)送能耗，cj反映接收節(jié)點的接收能耗. 因此，該模型能很好的解決簇頭節(jié)點的能耗不均衡問題. 特別地，當各博弈方到特定接收節(jié)點的發(fā)送能耗相同時，他們發(fā)送相同數(shù)據(jù)量，進一步證實本博弈的實際效果.

3.3基于非合作博弈的簇間路由算法EIRNG

根據(jù)第3節(jié)的模型模型以及引理3.1和3.2，可得出，基于非合作博弈的簇間路由算法EIRNG如下：

在每一輪簇頭選舉完畢之后，第n層(1≤n≤k-1)的簇頭節(jié)點j首先根據(jù)自身的剩余能量計算自己在本輪通信中所能承受的最大數(shù)據(jù)容量cj. 然后，簇頭節(jié)點j將cj以廣播的形式發(fā)送到前一層，即(n+1)層的所有簇頭節(jié)點. (n+1)層的所有簇頭節(jié)點i(1≤i≤N)接收到相應的數(shù)據(jù)容量值cj，根據(jù)收到的信號強度計算自身到達節(jié)點j的距離并計算自身的平衡因子θi. 接下來，節(jié)點i(1≤i≤N)將自身的平衡因子θi在本層(n+1)內(nèi)廣播. 待所有節(jié)點接收到相應的平衡因子之后，第n+1層內(nèi)的每個節(jié)點按照式(12)計算自己的最優(yōu)數(shù)據(jù)發(fā)送量，并按此值向節(jié)點j發(fā)送數(shù)據(jù)包.

一般而言，分簇階段產(chǎn)生的簇頭節(jié)點數(shù)量相對較少. 如LEACH協(xié)議產(chǎn)生的簇頭節(jié)點為5%，而EEREG[14]產(chǎn)生的簇頭節(jié)點也僅為6%左右. 因而，每層簇頭告知其最大容量cj的廣播報文所消耗的能量相對于每輪進行的數(shù)據(jù)傳輸量可忽略不計. 同時，由于簇頭節(jié)點數(shù)目有限也不致產(chǎn)生廣播風暴現(xiàn)象. 根據(jù)文獻[21],傳感器節(jié)點執(zhí)行1 000條指令所消耗的能量與將1 bit數(shù)據(jù)發(fā)送20米距離相當. 并且每執(zhí)行一次簇頭輪換才執(zhí)行一次最優(yōu)通信量的計算. 因此，盡管簇頭節(jié)點在根據(jù)平衡因子確定最優(yōu)通信量的過程需要消耗一定能量，但整體而言并不會影響非合作博弈簇間路由算法的能量效率. 為比較本簇間路由算法的能量效率，將與前期工作EEREG進行比較，算法除了不采用本文的簇間路由之外，工作機制與EIRNG完全一致. 因此，將兩者進行對比，可以很明顯的看出EIRNG的能量效率與優(yōu)勢.

4 實驗與分析

本文采用NS2進行仿真實驗，100個傳感器節(jié)點獨立均勻地分布在為R=100 m的圓形區(qū)域內(nèi). 節(jié)點的初始能量為2 J，接收或者發(fā)送1 bit數(shù)據(jù)節(jié)點電路所消耗的能量為50 nJ，εamp取值為13 pJ/bit/m2. 本文將整個網(wǎng)絡分成3層，即k取值為3，并且Sink節(jié)點位于圓心處. 為全面評價本文提出的基于博弈論的簇間路由算法，先給出相應的物理指標作為本算法的評價標準.

4.1 評價指標

本算法是以提高能量效率為目標，而對于WSNs來說，最能反映能量效率的物理指標為網(wǎng)絡生命期. 對于網(wǎng)絡生命期，不同的應用場景有不同的定義，本文定義如下3個指標：

首節(jié)點能量耗盡時間(FND)：表示網(wǎng)絡中第一個節(jié)點能量耗盡的時間，對于某些應用，特別是在軍事檢測以及瀕危物種跟蹤等對數(shù)據(jù)實時性要求較高的應用中[9]定義首節(jié)點能量耗盡時間很有實際意義.

半數(shù)節(jié)點能量耗盡時間(HND)：表示網(wǎng)絡中一半節(jié)點能量耗盡的時間.

最后一個節(jié)點能量耗盡的時間(LND)：表示網(wǎng)絡最后一個節(jié)點能量耗盡的時間.

網(wǎng)絡平均剩余能量：表示網(wǎng)絡存活節(jié)點的平均剩余能量. 對于能效優(yōu)化算法，網(wǎng)絡平均剩余能量可以較好的反映網(wǎng)絡能量的耗散速率.

數(shù)據(jù)總量：在仿真期間網(wǎng)絡Sink節(jié)點收集到的所有數(shù)據(jù). 因為WSNs中所有節(jié)點的鋪設是用來收集數(shù)據(jù)的，所以衡量數(shù)據(jù)總量較具有實際意義. 此外，Sink節(jié)點收集的數(shù)據(jù)總量也叫Sink的吞吐量，反映的是網(wǎng)絡性能指標.

相對于能量百分比的吞吐量：對能量耗散一定百分比時Sink收集到的數(shù)據(jù)總量. 這個指標同時考慮了數(shù)據(jù)量以及能量消耗. 因此可以較好地反應本算法的能量效率.

由于本文是針對簇類算法的簇間路由算法，因此，最后將實驗數(shù)據(jù)與經(jīng)典的簇類路由協(xié)議DHAC[9]、TEEN[11]、PEGASIS[12]以及作者之前所提出的EEREG[14]進行比較.

4.2 實驗結果及分析

圖5顯示采用5種協(xié)議的存活節(jié)點數(shù)目隨仿真時間變化圖，從圖5可看出，在相同時間內(nèi)，本文提出的EIRNG協(xié)議的存活節(jié)點數(shù)量明顯高于其他4種協(xié)議. 特別值得一提的是，EIRNG針對作者之前工作的EEREG的簇間路由協(xié)議進行了改進，圖5可看出，EIRNG使得網(wǎng)絡生命期相應延長了. 本文的網(wǎng)絡生命期分別采用4.1節(jié)所定義的FND，HND以及LND. 圖6顯示網(wǎng)絡生命期的對比圖. 從圖6可看出，EIRNG的FND值比PEGASIS提高74.1%，比EEREG提高6.8%；在HND值方面，EIRNG比TEEN提高29.4%，比EEREG提高4.5%；最后EIRNG的LND比TEEN提高了50.3%，比EEREG提高8.6%.

圖5 節(jié)點數(shù)目變化對比

圖7反映各協(xié)議的網(wǎng)絡平均剩余能量對比圖. 從圖中可看出，采用的EIRNG路由算法之后的節(jié)點平均剩余能量明顯高于其余4者. 同時也應該看出，與EEREG相比，由于EIRNG在簇間路由協(xié)議進行改善，因此，其平均剩余能量比EEREG要高，這也體現(xiàn)了EIRNG的優(yōu)越性.

圖6 網(wǎng)絡生命期對比

圖7 網(wǎng)絡平均能量變化

圖8顯示網(wǎng)絡仿真期間，各個Sink節(jié)點收集的數(shù)據(jù)隨時間的變化關系圖. 從圖中可看出，相同時間內(nèi)，EIRNG收集的數(shù)據(jù)量是最多的，這主要是由于EIRNG采用了合理的效用函數(shù)來規(guī)范節(jié)點的數(shù)據(jù)流發(fā)送行為，這不僅可以降低網(wǎng)絡能耗，而且可降低由于大量數(shù)據(jù)發(fā)往同一個下一跳節(jié)點導致的數(shù)據(jù)包丟失. 同時，由于采用EIRNG網(wǎng)絡生命期最長，所以圖8顯示EIRNG的數(shù)據(jù)量曲線持續(xù)到了最后.

圖9顯示仿真實驗中的各個協(xié)議相對能量百分比的Sink所收到的數(shù)據(jù)量. 可看出，EIRNG的曲線高于其他4者，同時，當網(wǎng)絡能量消耗百分之50之后，EIRNG的數(shù)據(jù)量明顯高于其他4種協(xié)議. 具體來說，當能量消耗到總能量70%時，EIRNG的數(shù)據(jù)量比TEEN高出13.2%，同時比EEREG高出2.85%.

圖9 相對能量百分率的數(shù)據(jù)量

5 結 論

WSNs具有一次性鋪設、長期使用的特點，加上具體應用場景、環(huán)境的限制，給傳感器節(jié)點再次充電或者補充能量不太現(xiàn)實. 這使得能量受限成為無線傳感器網(wǎng)絡的固有問題. 本文對聚簇路由協(xié)議中的簇間能耗不均問題進行了研究，指出了節(jié)點的自私性所引發(fā)的的數(shù)據(jù)流不均是導致簇頭間能耗不均勻的根本原因. 在此基礎上，提出了基于非合作博弈的簇間路由算法(EIRNG)，定義了效用函數(shù)以規(guī)范簇頭間數(shù)據(jù)轉(zhuǎn)發(fā)行為，以實現(xiàn)整個網(wǎng)絡拓撲的能量均衡. 最后，通過大量仿真實驗，對所提出的EIRNG進行了驗證，通過橫向與縱向?qū)Ρ缺砻?，本文的EIRNG可以較好地提高能量效率并且獲得更高的網(wǎng)絡性能.

[1] AKYIDLDIZ I, SU Weilian, SANKARASUBRAMANIAM Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114. DOI: 10.1109/MCOM.2002.1024422.

[2] HEINZELMAN, RABINER W, ANANTHA, et al. Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Hawaii International Conference on System Sciences. Los Alamitos: IEEE Press, :2000: 8020-8030.

[3] BASAGNI CAROSL A, MELACHRINOUDIS E, et al. Controlled sink mobility for prolonging wireless sensor networks lifetime[J]. Wireless Networks, 2007. 14(6):831-858. DOI: 10.1007/s11276-007-0017-x.

[4] VINCZE Z, VIDA R, VIDACS A. Deploying multiple sinks in multi-hop wireless sensor networks[C]//Proceedings of the 2007 IEEE International Conference on Pervasive Services. Istanbul, Turkey. 2007: 55-63.

[5] BASAGNI S, CAROSI A, MELACHIRINOUDIS E, et al. A new MILP formulation and distributed protocols for wireless sensor netorks lifetime maximization[C]//Proceedings of the 2006 IEEE International Conference on Communications, Istanbul, Turkey: IEEE Press, 2006: 3517-3524.

[6] LIANG W, LUO J, XU X. Prolonging network lifetime via a controlled mobile Sink in wireless sensor networks[C]//Proceedings of the 2010 IEEE Global Telecommunications Conference(GLOBECOM 2010). New York: IEEE Press. 2010:1-6.

[7] DU Xiaojiang, XIAO Yang, DAI Fei. Increasing network lifetime by balancing node energy consumption in heterogeneous sensor networks[J]. Wireless Communication and Mobile Computing, 2008, 8(1): 125-136. DOI: 10.1002/wcm.452.

[8] WEI Dali, JIN Yichao, VUEAL S, et al. An energy-efficient clustering solution for wireless sensor network[J]. IEEE Transations on Wireless Communication, 2011, 10(11): 3973-3983. DOI: 10.1109/GLOCOM.2010.5683095.

[9] PANTAZIS N, NIKOLIDAKIS S, VERGADOS D. Energy-efficient routing protocols in wireless sensor networks: a survey[J]. IEEE Communications survey & Tutorials. 2013, 15(2): 551-591. DOI: 10.1109/SURV.2012.062612.00084.

[10]LUNG C, ZHOU Chenjuan. Using hierarchical agglomerative clustering in wireless sensor networks: an energy-efficient and flexible approach[J]. Ad Hoc networks, 2007, 8(2): 328-344. DOI: 10.1016/j.adhoc.2009.09.004.

[11]MANJESHWAR A, AGRAWAL D. Teen: a routing protocol for enhanced efficiency in wireless sensor networks[C]//Proceedings of the 15thInternational Parallel and Distributed Proceeding Symposium. San Francisco: IEEE Press, 2001: 2009-2015.

[12]LINDSEY S, RAGHAVENDRA C. PEGASIS: power-efficient gathering in sensor information systems[C]//Proceedings of the 2002 Aerospace Conference, DC, USA, IEEE Press, 2002: 1125-1130.

[13]OK C, PRASENJIT MITRA P, LEE S, et al. Maximum energy welfare routing in wireless sensor networks[C]//Proceedings of the 6thInternational IFIP-TC6 Networking Conference. Atlanta: Springer Veriag, 2007: 203-214.

[14]LIN Deyu, WANG Quan, LIN Deqin, et al. An energy-efficient clustering routing protocol based on evolutionary game theory in wireless sensor networks[J].International Journal of Distributed Sensor Networks. 2015, 2015(2015): 1-14. DOI: 10.1155/2015/409503.

[15]XIE Shiyu. Economic game theory[M]. Shanghai: Fudan University Press. 2001. 209-246.

[16]FAROUK F, RIZK R, ZAKI F. Multi-level stable and energy-efficient clustering protocol in heterogeneous wireless sensor networks[J]. IET Wireless Sensor Networks, 2014,4(4): 159-169. DOI: 10.1049/iet-wss.2014.0051.

[17]CHAND S, KUMA R, KUMAR B, et al. NEECP: novel energy-efficient clustering protocol for prolonging lifetime of WSNs[J]. IET Wireless Sensor Networks, 2016, 6(5): 151-157. DOI: 10.1049/iet-wss.2015.0017.

[18]LIN Deyu, Wang Quan.A game theory based energy efficient clustering routing protocol for WSNs[J]. Wireless Networks, 2016,: 1-11. DOI: DOI 10.1007/s11276-016-1206-2.

[19]ZHAO Miao, YANG Yuanyuan, WANG Cong.Mobile data gathering with load balanced clustering and dual data uploading in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2015, 14(4): 770-785. DOI: 10.1109/TMC.2014.2338315.

[20]SINGH S, CHAND S, KUMAR B.Energy efficient clustering protocol using fuzzy logic for heterogeneous WSNs[J]. Wireless Personal Communications, 2016, 86(2): 1-25. DOI: 10.1007/s11277-015-2939-4.

[21]DU Xiaojiang, XIAO Yang, DAI Fei. Increasing network lifetime by balancing node energy consumption in heterogeneous sensor networks[J]. Wireless Communications & Mobile Computing, 2008, 8(1): 125-136. DOI: 10.1002/wcm.452.

Researchonenergy-efficientinter-clusterroutingalgorithmbasedonnon-cooperativegame

LIN Deyu, WANG Quan

(School of Computer Science and Technology, Xidian University, Xi’an 710071, China)

Detailed research focusing on the inter-cluster routing for wireless sensor networks (WSNs) is given first. The energy consumption imbalance problem and its cause are presented through a simple example. The paper points out the fact via an example that, the selfish of each cluster head leads to the imbalanced distribution of data flow and the data distribution imbalance then results in energy consumption imbalance. Subsequently, the non-cooperative game model aiming at regulating the behavior of the cluster heads is proposed. The Nash Equilibrium Point (NEP) of the game model is then obtained and proved. According to this game model, an energy-efficient Inter-cluster Routing algorithm based on Non-cooperative Game (EIRNG) is presented, which is the key contribution of the paper. Finally, extensive simulation experiments are conducted and the horizontal and vertical contrast in terms of energy efficiency and network performance are also made. The results show that the cluster heads tend to dissipate energy evenly via determining the optimal amount of the traffic based on a balance factorθi. Compared with the classic clustering routing PEGASIS and the authors’ former work EEREG, the network lifespan can be extended by 74.1% and 8.6% respectively. Therefore, the proposed EIRNG can improve the energy efficiency and the network performance of the network effectively.

wireless sensor networks; inter-cluster routing; Nash equilibrium point; non-cooperative game; network performance

by the Sink

10.11918/j.issn.0367-6234.201612085

TP393

A

0367-6234(2017)11-0095-06

2016-12-15

國家自然科學基金(61572385)

林德鈺(1988—),男,博士生；王 泉(1970—),男,教授

王 泉， qwang@xidian.edu.cn

(編輯苗秀芝)