0 引言

    提高節(jié)點能量利用率,、擴延網(wǎng)絡(luò)壽命成為無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks,，WSNs)的研究熱點^[1]。通過協(xié)調(diào)節(jié)點間通信來平衡網(wǎng)絡(luò)能量消耗,，是提高網(wǎng)絡(luò)壽命最為有效的技術(shù)之一^[2-3],。在這些技術(shù)中，路由決策起著重要作用,，因為路徑的選擇直接影響到節(jié)點能量消耗^[4-5],。

    由于地理路由協(xié)議(Geographical Routing Protocols，GRPs)無需建立路由表,，也無需進(jìn)行路由發(fā)現(xiàn)和路由維護,，使得GRPs非常適用于無線傳感網(wǎng)絡(luò)。典型的地理路由協(xié)議有GPSR(Greedy Perimeter Stateless Routing)^[6],、GOAFR^[7],、GRR^[8]、GAR^[9],、BVGF^[10],、GEAR(Geographical and Energy Aware Routing)^[11]、OVCR^[12],、VAA^[13]。地理路由協(xié)議GRPs的不足之處在于它沒有從全局考慮網(wǎng)絡(luò)信息,，對于無線傳感網(wǎng)絡(luò)而言,，能量利用率是非常重要的性能指標(biāo)^[14]。

    為此,，本文針對地理路由協(xié)議GRPs的特性及其不足,，利用進(jìn)化博弈理論(Evolutionary Game Theory,，EGT)，平衡了網(wǎng)絡(luò)能量消耗,。通過EGT建立平衡能量消耗的方案,，進(jìn)而擴延網(wǎng)絡(luò)壽命。此外,，EGT能夠在全局信息未知的環(huán)境下進(jìn)行正確的決策,。

1 EGT-EBGR算法

    EGT-EBGR算法目的是平衡網(wǎng)絡(luò)能量消耗，使得節(jié)點的能量消耗速度相近,。依據(jù)節(jié)點密度,，源節(jié)點S將其傳輸范圍劃分為K個子區(qū)域。首先利用基于EGT的區(qū)域選擇算法(EGT-based Regions Selection,，EGT-RS)選擇下一個轉(zhuǎn)發(fā)子區(qū)域,，然后再利用貪婪地理算法選擇轉(zhuǎn)發(fā)節(jié)點。

    如圖1所示,，源節(jié)點S將它向目的節(jié)點D的傳輸方向的鄰居節(jié)點劃分了4個區(qū)域,，分別為R1、R2,、R3,、R4。然后,，利用EGT-RS算法,，為當(dāng)前數(shù)據(jù)包選擇了一個轉(zhuǎn)發(fā)區(qū)域。假定選擇了R2作為當(dāng)前數(shù)據(jù)包的轉(zhuǎn)發(fā)區(qū)域,，最后,，再在R2區(qū)域，利用貪婪轉(zhuǎn)發(fā)算法選擇離目的節(jié)點D最近的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點,。

1.1 基于EGT的區(qū)域選擇算法EGT-RS

    復(fù)制動態(tài)在每個博弈理論間隔進(jìn)化一個新的數(shù)據(jù)包分布矢量^[16],，不斷進(jìn)化，直到得到最優(yōu)的分布矢量X^*,。實際上,，計算分布矢量X^*的關(guān)鍵在于設(shè)計適度函數(shù)FF(Fitness Function)，適度函數(shù)F_k(X)的定義如下：

其中E_tr,、E_tx分別節(jié)點接收,、發(fā)送一個數(shù)據(jù)包所需的能量。

1.2 復(fù)制動態(tài)

    從子區(qū)域l到子區(qū)域k的切換概率P_k,，l(X),，其與兩個子區(qū)域l、k的適度函數(shù)相關(guān)，如式(2)所示,。

    從子區(qū)域k到其他所有子區(qū)域的轉(zhuǎn)換概率之和應(yīng)等于1：

    因此,，復(fù)制動態(tài)的差異值反映了子區(qū)域k的流入和流出的數(shù)據(jù)包凈差：

    因此，對于僅有兩個子區(qū)域的場景,，利用式(2),，可計算過渡概率矩陣P：

    當(dāng)所有子區(qū)域的流入和流出數(shù)據(jù)包相等時，系統(tǒng)就到達(dá)穩(wěn)定狀態(tài),。

1.3 進(jìn)化均衡

2 性能分析

    利用OMNeT++4.22網(wǎng)絡(luò)仿真器建立仿真平臺,，仿真參數(shù)如表1所示。傳感節(jié)點隨機分布于二維的100×100 m²區(qū)域,。

    提出的EGT-EBGR協(xié)議與3種隨機選擇方案進(jìn)行比較,。這3種隨機選擇方案分別為：(1)隨機+隨機（Random+Random）：表示隨機選擇轉(zhuǎn)發(fā)區(qū)域，并且也隨機地選擇轉(zhuǎn)發(fā)節(jié)點,；(2)（EGT-RS+Random）：利用EGT-RS算法選擇轉(zhuǎn)發(fā)區(qū)域,，然后再從轉(zhuǎn)發(fā)區(qū)域內(nèi)隨機地選擇轉(zhuǎn)發(fā)節(jié)點；(3)隨機+GA（Random+GA）：隨機地選擇轉(zhuǎn)發(fā)區(qū)域,，然后再利用貪婪算法從區(qū)域內(nèi)選擇轉(zhuǎn)發(fā)節(jié)點,。

2.1 網(wǎng)絡(luò)壽命

    本次實驗中，數(shù)據(jù)包產(chǎn)生率為2 packets/s,，節(jié)點數(shù)從120～520變化,，仿真結(jié)果如圖2所示。

    從圖2可知,，網(wǎng)絡(luò)壽命隨節(jié)點數(shù)的增加呈上升趨勢,。正如預(yù)期的，Random+Random方案的壽命最短,，依次為Random+GA,、EGT-RS+Random，而提出的EGT-EBGR協(xié)議最高,。原因在于EGT-RS+Random方案利用EGT-RS算法選擇轉(zhuǎn)發(fā)區(qū)域,，平衡網(wǎng)絡(luò)能量消耗速度。此外,，從圖1可知,，提出的EGT-EBGR協(xié)議的網(wǎng)絡(luò)壽命比Random+Random、EGT-RS+Random分別提高了近38%,、9%,。

2.2 平均每個數(shù)據(jù)包的能量消耗

    本次實驗分析向目的節(jié)點傳輸一個數(shù)據(jù)包所消耗的平均能量，實驗數(shù)據(jù)如圖3所示,。從圖3可知,，提出的EGT-EBGR的能量消耗比Random+Random下降了約64%,。原因在于：EGT-EBGR協(xié)議中的每個節(jié)點利用納什均衡做出最優(yōu)的轉(zhuǎn)發(fā)決策，從能量均衡角度選擇轉(zhuǎn)發(fā)區(qū)域,，而隨機選擇增加了能量消耗。

3 結(jié)論

    針對無線網(wǎng)絡(luò)路由問題,，本文提出了基于博弈論能耗均衡的無線傳感網(wǎng)絡(luò)路由算法EGT-EBGR,。EGT-EBGR算法通過平衡網(wǎng)絡(luò)能量消耗，提高網(wǎng)絡(luò)壽命,。EGT-EBGR首先將數(shù)據(jù)包攜帶節(jié)點的傳輸范圍劃分幾個轉(zhuǎn)發(fā)子區(qū)域,，然后再利用進(jìn)化博弈算法，從中選擇一個子區(qū)域作為轉(zhuǎn)發(fā)區(qū)域,，再從選擇的子區(qū)域內(nèi),，利用貪婪算法選出下一跳轉(zhuǎn)發(fā)節(jié)點。仿真結(jié)果表明,，提出的EGT-EBGR協(xié)議的網(wǎng)絡(luò)壽命比隨機選擇下一跳轉(zhuǎn)發(fā)節(jié)點(Random+Random)高了近38%,，能量消耗下降了64%。

參考文獻(xiàn)

[1] ZHANG H,，SHEN H.Balancing energy consumption to maximize network lifetime in data-gathering sensor networks[J].IEEE Trans.Parallel Distrib.Syst.,，2009，20(10)：1526-1539.

[2] 羅四維,，侯孟書,，周益民.一種新的基于能量消耗速率模型的分簇路由協(xié)議[J].計算機科學(xué)，2012,，39(6)：46-50.

[3] IYER G,，AGRAWAL P，MONNERIE E,，et al.Performance analysis of wireless mesh routing protocols for smart utility networks[C].In Proc.IEEE Int.Conf.Smart Grid Commun.,，Oct.2011：114-119.

[4] PANTAZIS N A，NIKOLIDAKIS S A,，VERGADOS D D.Energy-efficient routing protocols in wireless sensor networks：A survey[J].IEEE Commun.Surv.Tuts.,，2013，15(2)：551-591.

[5] ZHANG D,，LI G,，ZHENG K，et al.An energy balanced routing method based on forward-aware factor for wireless sensor networks[J].IEEE Trans.Ind.Informat.,，2014,，10(1)：766-773.

[6] SEADA K，HELMY A,，GOVINDAN R.On the effect of localization errors on geographic face routing in sensor networks[C].In：Proc.of the 3rd International Symposium on Information Processing in Sensor Networks,，IPSN’04,，2004：71-80.

[7] KUHN F，WATTENHOFER R,，ZHANG Y,，et al.Geometric ad-hoc routing：of theory and practice[C].Proc.of the Twenty-Second Annual Symposiumon Principles of Distributed Computing，PODC’03,，2003：63-72.

[8] KERMARREC A M,，TAN G.Greedy geographic routing in large-scale sensor networks：a minimum network decomposition approach[C].Proc.of the Eleventh ACM International Symposium on Mobile Ad Hoc Networking and Computing，MobiHoc’10,，2010：161-170.

[9] LIU W J,，F(xiàn)ENG K T.Greedy routing with anti-void traversal for wireless sensor networks[J].IEEE Trans.Mob.Comput.，2009,，8(7)：910-922.

[10] Xing Guoliang,，Lu Chenyang，PLESS R,，et al.Impact of sensing coverage on Greedy geographic routing algorithms[J].IEEE Trans.Parallel Distrib.Syst.2006,，17(4)：348-360.

[11] YU Y，GOVINDAN R,，ESTRIN D.Geographical and energy aware routing: a recursive data dissemination protocol for wireless sensor networks[J].Technical Report CSD-TR-01-0023,，UCLA Computer Science Department，2011,，3(6)：36-42.

[12] HSU M T,，LIN F Y S，CHANG Y S,，et al.Reliable Greedy forwarding in obstacle-aware wireless sensor networks[J].Proc.of the 9th International Conference on Algorithms and Architectures for Parallel Processing,，ICA3PP’09，2009：797-808.

[13] JOSHI G P,，KIM S W.A distributed geo-routing algorithm for wireless sensor networks[J].Sensors,，2009，9(6)：4083-4103.

[14] TEMBINE H,，ALTMAN E,，EL-AZOUZI R，et al.Evolutionary games in wireless networks[J].IEEE Trans.Syst.,，Man,，Cybern.B，Cybern.,，2010,，40(3)：634-646.

[15] ABD M A，SINGH B K,，AL RUBEAAI S F,，et al.Game theoretic energy balanced(GTEB) routing protocol for wireless sensor networks[C].In Proc.IEEE Wireless Commun.Netw.Conf.(WCNC),，2014：2564-2569.

[16] MEHMMOD A，SARAB F.Extending wireless sensor network lifetime with global energy balance[J].IEEE Sensors Journal,，2015,，15(9)：5053-5064.

[17] BROUWER L E J.Uber abbildung von mannigfaltigkeiten[J].Math.Ann.，2012,，71(4)：32-43.

作者信息：

朱亞東1,，高翠芳2

（1.江蘇聯(lián)合職業(yè)技術(shù)學(xué)院 信息中心，江蘇 南京211135,；2.江南大學(xué) 理學(xué)院，江蘇 無錫214112）