林德鈺， 王 泉

(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院，710071 西安)

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

林德鈺， 王 泉

(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院，710071 西安)

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

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

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

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

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

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

1 簇間能耗不均問(wèn)題

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

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

圖1 簇間路由能耗不均問(wèn)題

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

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

2 系統(tǒng)模型及相關(guān)假設(shè)

2.1 能耗模型

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

erx=bEelec，

(1)

etx=b(Eelec+εampdα).

(2)

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

2.2 網(wǎng)絡(luò)模型

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

2.3 相關(guān)假設(shè)

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

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

圖3 網(wǎng)絡(luò)模型

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

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

假設(shè)網(wǎng)絡(luò)報(bào)文可無(wú)限分割且可以分割成無(wú)限小，并且以網(wǎng)絡(luò)拓?fù)渲械娜我庖簧刃苇h(huán)中的所有節(jié)點(diǎn)作為研究對(duì)象.

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

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

3.1 博弈模型

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

(P,S,U).

(3)

在此單次能量?jī)?yōu)化博弈模型中，把網(wǎng)絡(luò)拓?fù)渲械娜我庖粚觡(1≤n≤k)中所有節(jié)點(diǎn)作為博弈模型的參與者，假設(shè)第n層中具有的節(jié)點(diǎn)數(shù)目為N，則參與者集合表示為

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

(4)

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

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

(5)

其中每個(gè)節(jié)點(diǎn)的策略為

si=Dij.

(6)

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

節(jié)點(diǎn)j的容量為

(7)

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

3.2效用函數(shù)

先定義平衡因子如下

(8)

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

).

(9)

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

(10)

(11)

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

(12)

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

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

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

圖4 非合作博弈模型

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

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

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

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

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

4 實(shí)驗(yàn)與分析

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

4.1 評(píng)價(jià)指標(biāo)

本算法是以提高能量效率為目標(biāo)，而對(duì)于WSNs來(lái)說(shuō)，最能反映能量效率的物理指標(biāo)為網(wǎng)絡(luò)生命期. 對(duì)于網(wǎng)絡(luò)生命期，不同的應(yīng)用場(chǎng)景有不同的定義，本文定義如下3個(gè)指標(biāo)：

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

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

最后一個(gè)節(jié)點(diǎn)能量耗盡的時(shí)間(LND)：表示網(wǎng)絡(luò)最后一個(gè)節(jié)點(diǎn)能量耗盡的時(shí)間.

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

數(shù)據(jù)總量：在仿真期間網(wǎng)絡(luò)Sink節(jié)點(diǎn)收集到的所有數(shù)據(jù). 因?yàn)閃SNs中所有節(jié)點(diǎn)的鋪設(shè)是用來(lái)收集數(shù)據(jù)的，所以衡量數(shù)據(jù)總量較具有實(shí)際意義. 此外，Sink節(jié)點(diǎn)收集的數(shù)據(jù)總量也叫Sink的吞吐量，反映的是網(wǎng)絡(luò)性能指標(biāo).

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

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

4.2 實(shí)驗(yàn)結(jié)果及分析

圖5顯示采用5種協(xié)議的存活節(jié)點(diǎn)數(shù)目隨仿真時(shí)間變化圖，從圖5可看出，在相同時(shí)間內(nèi)，本文提出的EIRNG協(xié)議的存活節(jié)點(diǎn)數(shù)量明顯高于其他4種協(xié)議. 特別值得一提的是，EIRNG針對(duì)作者之前工作的EEREG的簇間路由協(xié)議進(jìn)行了改進(jìn)，圖5可看出，EIRNG使得網(wǎng)絡(luò)生命期相應(yīng)延長(zhǎng)了. 本文的網(wǎng)絡(luò)生命期分別采用4.1節(jié)所定義的FND，HND以及LND. 圖6顯示網(wǎng)絡(luò)生命期的對(duì)比圖. 從圖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é)點(diǎn)數(shù)目變化對(duì)比

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

圖6 網(wǎng)絡(luò)生命期對(duì)比

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

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

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

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

5 結(jié) 論

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

[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

國(guó)家自然科學(xué)基金(61572385)

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

王 泉， qwang@xidian.edu.cn

(編輯苗秀芝)