《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 基于博弈論能耗均衡的無(wú)線傳感網(wǎng)絡(luò)路由算法
基于博弈論能耗均衡的無(wú)線傳感網(wǎng)絡(luò)路由算法
2017年電子技術(shù)應(yīng)用第7期
朱亞?wèn)|1，高翠芳2
1.江蘇聯(lián)合職業(yè)技術(shù)學(xué)院 信息中心，江蘇 南京211135；2.江南大學(xué) 理學(xué)院，江蘇 無(wú)錫214112
摘要： 為了平衡能量消耗，延長(zhǎng)網(wǎng)絡(luò)壽命，提出基于博弈論能耗均衡的無(wú)線傳感網(wǎng)絡(luò)路由算法——EGT-EBGR。EGT-EBGR路由的目的是使節(jié)點(diǎn)能耗均衡，進(jìn)而延長(zhǎng)網(wǎng)絡(luò)壽命。首先，將發(fā)送節(jié)點(diǎn)的傳輸范圍劃分幾個(gè)轉(zhuǎn)發(fā)子區(qū)域，然后再結(jié)合進(jìn)化博弈論EGT(Evolutionary Game Theory)，從平衡負(fù)載角度，從轉(zhuǎn)發(fā)子區(qū)域內(nèi)選擇一個(gè)轉(zhuǎn)發(fā)子區(qū)域，再利用貪婪算法從此轉(zhuǎn)發(fā)子區(qū)域內(nèi)選擇一個(gè)節(jié)點(diǎn)作為下一跳的轉(zhuǎn)發(fā)節(jié)點(diǎn)。通過(guò)進(jìn)化博弈論和貪婪算法GA(Greedy Algorithm)平衡負(fù)載，縮短傳輸距離，有效地降低地能量消耗速度，進(jìn)而延長(zhǎng)網(wǎng)絡(luò)壽命。仿真數(shù)據(jù)表明，提出的EGT-EBGR協(xié)議能夠有效地平衡能量消耗，擴(kuò)延了網(wǎng)絡(luò)壽命。
中圖分類號(hào)： TN925
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2017.07.029
中文引用格式： 朱亞?wèn)|，高翠芳. 基于博弈論能耗均衡的無(wú)線傳感網(wǎng)絡(luò)路由算法[J].電子技術(shù)應(yīng)用，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.
Energy-balanced routing algorithm based on Game-Theory for WSNs
Zhu Yadong1，Gao Cuifang2
1．Information Center，Jiangsu Union Technical Institute，Nanjing 211135，China； 2．School of Science，Jiangnan University，Wuxi 214112，China
Abstract： To extend the network lifetime by balancing energy consumption, evolutionary game theory-based energy balance geographical routing(EGT-EBGR) protocol is proposed in this paper. The objective of the proposed protocol is to make sensor nodes deplete their energy at approximately the same time. The transmission range of a sender is divided into serval forwarding sub-regions, evolutionary game theory(EGT) is used to balance the traffic load to available sub-regions. Greedy algorithm(GA) is used to select the best node to balance the load in the selected sub-region. This EGT and GA is shown to be an effective solution for load balancing and extending network lifetime. Simulation results show that EGT-EBGR protocol offers significant improvement over existing protocols in extending network lifetime.
Key words : WSNs；routing；energy balance；evolutionary game theory；Greedy

0 引言

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

    由于地理路由協(xié)議(Geographical Routing Protocols，GRPs)無(wú)需建立路由表，也無(wú)需進(jìn)行路由發(fā)現(xiàn)和路由維護(hù)，使得GRPs非常適用于無(wú)線傳感網(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的不足之處在于它沒(méi)有從全局考慮網(wǎng)絡(luò)信息，對(duì)于無(wú)線傳感網(wǎng)絡(luò)而言，能量利用率是非常重要的性能指標(biāo)[14]。

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

1 EGT-EBGR算法

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

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

tx5-t1.gif

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

tx5-1.1-x1.gif

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

    tx5-gs1.gif

其中Etr、Etx分別節(jié)點(diǎn)接收、發(fā)送一個(gè)數(shù)據(jù)包所需的能量。

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

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

tx5-gs2-3.gif

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

    tx5-gs4.gif

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

     tx5-gs5-6.gif

    因此，對(duì)于僅有兩個(gè)子區(qū)域的場(chǎng)景，利用式(2)，可計(jì)算過(guò)渡概率矩陣P：

 tx5-gs7-8.gif

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

1.3 進(jìn)化均衡

tx5-gs9-13.gif

2 性能分析

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

tx5-b1.gif

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

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

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

tx5-t2.gif

    從圖2可知，網(wǎng)絡(luò)壽命隨節(jié)點(diǎn)數(shù)的增加呈上升趨勢(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 平均每個(gè)數(shù)據(jù)包的能量消耗

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

tx5-t3.gif

3 結(jié)論

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



作者信息：

朱亞?wèn)|1，高翠芳2

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

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。