0 引言

    提高節(jié)點能量利用率、擴(kuò)延網(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)和路由維護(hù)，使得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)而擴(kuò)延網(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é)點隨機(jī)分布于二維的100×100 m²區(qū)域。

    提出的EGT-EBGR協(xié)議與3種隨機(jī)選擇方案進(jìn)行比較。這3種隨機(jī)選擇方案分別為：(1)隨機(jī)+隨機(jī)（Random+Random）：表示隨機(jī)選擇轉(zhuǎn)發(fā)區(qū)域，并且也隨機(jī)地選擇轉(zhuǎn)發(fā)節(jié)點；(2)（EGT-RS+Random）：利用EGT-RS算法選擇轉(zhuǎn)發(fā)區(qū)域，然后再從轉(zhuǎn)發(fā)區(qū)域內(nèi)隨機(jī)地選擇轉(zhuǎn)發(fā)節(jié)點；(3)隨機(jī)+GA（Random+GA）：隨機(jī)地選擇轉(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ū)域，而隨機(jī)選擇增加了能量消耗。

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ò)壽命比隨機(jī)選擇下一跳轉(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].計算機(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）