文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2017.07.029
中文引用格式： 朱亞東，高翠芳. 基于博弈論能耗均衡的無線傳感網絡路由算法[J].電子技術應用，2017，43(7)：114-116，126.
英文引用格式： Zhu Yadong，Gao Cuifang. Energy-balanced routing algorithm based on Game-Theory for WSNs[J].Application of Electronic Technique，2017，43(7)：114-116，126.
0 引言
提高節點能量利用率、擴延網絡壽命成為無線傳感網絡(Wireless Sensor Networks，WSNs)的研究熱點[1]。通過協調節點間通信來平衡網絡能量消耗，是提高網絡壽命最為有效的技術之一[2-3]。在這些技術中，路由決策起著重要作用，因為路徑的選擇直接影響到節點能量消耗[4-5]。
由于地理路由協議(Geographical Routing Protocols，GRPs)無需建立路由表，也無需進行路由發現和路由維護，使得GRPs非常適用于無線傳感網絡。典型的地理路由協議有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]。地理路由協議GRPs的不足之處在于它沒有從全局考慮網絡信息，對于無線傳感網絡而言，能量利用率是非常重要的性能指標[14]。
為此，本文針對地理路由協議GRPs的特性及其不足，利用進化博弈理論(Evolutionary Game Theory，EGT)，平衡了網絡能量消耗。通過EGT建立平衡能量消耗的方案，進而擴延網絡壽命。此外，EGT能夠在全局信息未知的環境下進行正確的決策。
1 EGT-EBGR算法
EGT-EBGR算法目的是平衡網絡能量消耗，使得節點的能量消耗速度相近。依據節點密度，源節點S將其傳輸范圍劃分為K個子區域。首先利用基于EGT的區域選擇算法(EGT-based Regions Selection，EGT-RS)選擇下一個轉發子區域，然后再利用貪婪地理算法選擇轉發節點。
如圖1所示，源節點S將它向目的節點D的傳輸方向的鄰居節點劃分了4個區域，分別為R1、R2、R3、R4。然后，利用EGT-RS算法，為當前數據包選擇了一個轉發區域。假定選擇了R2作為當前數據包的轉發區域，最后，再在R2區域，利用貪婪轉發算法選擇離目的節點D最近的節點作為轉發節點。
1.1 基于EGT的區域選擇算法EGT-RS
復制動態在每個博弈理論間隔進化一個新的數據包分布矢量[16]，不斷進化，直到得到最優的分布矢量X*。實際上，計算分布矢量X*的關鍵在于設計適度函數FF(Fitness Function)，適度函數Fk(X)的定義如下：
其中Etr、Etx分別節點接收、發送一個數據包所需的能量。
1.2 復制動態
從子區域l到子區域k的切換概率Pk，l(X)，其與兩個子區域l、k的適度函數相關，如式(2)所示。
從子區域k到其他所有子區域的轉換概率之和應等于1：
因此，復制動態的差異值反映了子區域k的流入和流出的數據包凈差：
因此，對于僅有兩個子區域的場景，利用式(2)，可計算過渡概率矩陣P：
當所有子區域的流入和流出數據包相等時，系統就到達穩定狀態。
1.3 進化均衡
2 性能分析
利用OMNeT++4.22網絡仿真器建立仿真平臺，仿真參數如表1所示。傳感節點隨機分布于二維的100×100 m2區域。
提出的EGT-EBGR協議與3種隨機選擇方案進行比較。這3種隨機選擇方案分別為：(1)隨機+隨機（Random+Random）：表示隨機選擇轉發區域，并且也隨機地選擇轉發節點；(2)（EGT-RS+Random）：利用EGT-RS算法選擇轉發區域，然后再從轉發區域內隨機地選擇轉發節點；(3)隨機+GA（Random+GA）：隨機地選擇轉發區域，然后再利用貪婪算法從區域內選擇轉發節點。
2.1 網絡壽命
本次實驗中，數據包產生率為2 packets/s，節點數從120～520變化，仿真結果如圖2所示。
從圖2可知，網絡壽命隨節點數的增加呈上升趨勢。正如預期的，Random+Random方案的壽命最短，依次為Random+GA、EGT-RS+Random，而提出的EGT-EBGR協議最高。原因在于EGT-RS+Random方案利用EGT-RS算法選擇轉發區域，平衡網絡能量消耗速度。此外，從圖1可知，提出的EGT-EBGR協議的網絡壽命比Random+Random、EGT-RS+Random分別提高了近38%、9%。
2.2 平均每個數據包的能量消耗
本次實驗分析向目的節點傳輸一個數據包所消耗的平均能量，實驗數據如圖3所示。從圖3可知，提出的EGT-EBGR的能量消耗比Random+Random下降了約64%。原因在于：EGT-EBGR協議中的每個節點利用納什均衡做出最優的轉發決策，從能量均衡角度選擇轉發區域，而隨機選擇增加了能量消耗。
3 結論
針對無線網絡路由問題，本文提出了基于博弈論能耗均衡的無線傳感網絡路由算法EGT-EBGR。EGT-EBGR算法通過平衡網絡能量消耗，提高網絡壽命。EGT-EBGR首先將數據包攜帶節點的傳輸范圍劃分幾個轉發子區域，然后再利用進化博弈算法，從中選擇一個子區域作為轉發區域，再從選擇的子區域內，利用貪婪算法選出下一跳轉發節點。仿真結果表明，提出的EGT-EBGR協議的網絡壽命比隨機選擇下一跳轉發節點(Random+Random)高了近38%，能量消耗下降了64%。
參考文獻
[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] 羅四維，侯孟書，周益民.一種新的基于能量消耗速率模型的分簇路由協議[J].計算機科學，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，FENG 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.江蘇聯合職業技術學院 信息中心，江蘇 南京211135；2.江南大學 理學院，江蘇 無錫214112）