劉 宏，夏未君，王其濤

(江西理工大學(xué) 電氣工程與自動化學(xué)院，江西 贛州 341000)

?

能量均衡的AD Hoc網(wǎng)絡(luò)路由協(xié)議研究

劉 宏，夏未君，王其濤

(江西理工大學(xué) 電氣工程與自動化學(xué)院，江西 贛州 341000)

傳統(tǒng)的ADHoc路由協(xié)議由于節(jié)點的能量不均衡，導(dǎo)致網(wǎng)絡(luò)耗能較大，減少了網(wǎng)絡(luò)生命周期；-從能量均衡角度提出了一種能量優(yōu)化的AdHoc網(wǎng)絡(luò)路由協(xié)議(EOARP協(xié)議)，通過引入公共經(jīng)濟(jì)學(xué)中洛倫茨指數(shù)法來衡量網(wǎng)絡(luò)的能耗均衡，結(jié)合節(jié)點通信繁忙程度、節(jié)點剩余能量等因素建立代價函數(shù)PEQ，選擇剩余能量相對較高，通信繁忙程度較輕的路由鏈路，從而達(dá)到均衡網(wǎng)絡(luò)的目的；仿真結(jié)果表明，EOARP協(xié)議在數(shù)據(jù)傳輸性能、能量均衡、以及網(wǎng)絡(luò)節(jié)點剩余能量等方面指標(biāo)均有較大改善，有效地延長了網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò)；路由協(xié)議；能量均衡；能量優(yōu)化

0 引言

AD Hoc網(wǎng)絡(luò)[1]是由移動終端所組成的具有自主性、臨時性、無基礎(chǔ)設(shè)施要求、多跳臨時性自治網(wǎng)絡(luò)系統(tǒng)，現(xiàn)已得到廣泛應(yīng)用。由于AD Hoc網(wǎng)絡(luò)的資源有限、拓?fù)浣Y(jié)構(gòu)動態(tài)、無全局標(biāo)識、帶寬低等特性，會導(dǎo)致出現(xiàn)以下兩個問題[2]：

1)在理想的網(wǎng)絡(luò)中，每個節(jié)點的能量消耗應(yīng)該是比較均等的，不會出現(xiàn)某個節(jié)點由于能量耗盡而過早的退出網(wǎng)絡(luò)，這樣就使得整個網(wǎng)絡(luò)的存活時間最長。然而在實際AD Hoc網(wǎng)絡(luò)中，一些處在網(wǎng)絡(luò)中心的節(jié)點由于頻繁的參與路由的建立、轉(zhuǎn)發(fā)而導(dǎo)使這些節(jié)點的能量消耗過大，導(dǎo)致路由鏈接斷裂，降低網(wǎng)絡(luò)生命周期；

2)當(dāng)網(wǎng)絡(luò)中的業(yè)務(wù)量比較大時，許多的鏈路可能會共用一個或幾個節(jié)點作為路徑的中間轉(zhuǎn)發(fā)節(jié)點，尤其是處在網(wǎng)絡(luò)中心位置的一些節(jié)點，因而導(dǎo)致網(wǎng)絡(luò)的流量傳輸不均衡，部分中心節(jié)點負(fù)載過重，就會發(fā)生數(shù)據(jù)擁塞。降低了網(wǎng)絡(luò)性能。

近年來，關(guān)于AD Hoc網(wǎng)絡(luò)協(xié)議[3]節(jié)能和延長網(wǎng)絡(luò)生命周期的研究已成為人們的研究熱點。并且提出了多種節(jié)能傳輸方案：文獻(xiàn)[4]中提出的基于跳數(shù)的無線傳感器網(wǎng)絡(luò)路由算法，這個算法的優(yōu)點是設(shè)計思路簡單有效，可靠性、負(fù)載均衡、網(wǎng)絡(luò)的生命周期都得到了提高，但是隨著發(fā)包頻率的增加，算法優(yōu)勢不在，保障機制不明顯；文獻(xiàn)[5]提出的LEACH協(xié)議，提出了數(shù)據(jù)聚合的層次路由協(xié)議，協(xié)議通過周期性的選擇簇頭來平衡網(wǎng)絡(luò)各節(jié)點的能量。該協(xié)議的優(yōu)點是選擇簇頭不固定，從而使網(wǎng)絡(luò)節(jié)約了能量，增加了生存時間。但是該協(xié)議需要節(jié)點具有較大功率，導(dǎo)致移動性變差，而且對大規(guī)模網(wǎng)絡(luò)不適合；文獻(xiàn)[6]提出了WSN動態(tài)重傳算法，減少了重傳的次數(shù)，降低了網(wǎng)絡(luò)能耗，但是可靠性沒有得到足夠的保證；文獻(xiàn)[7]提出了基于能量角度聯(lián)合自適應(yīng)路由修復(fù)算法，通過計算剩余能量的大小，選擇最佳的路由。其優(yōu)點是延長了網(wǎng)絡(luò)節(jié)點的生存時間。缺點是協(xié)議不穩(wěn)定，因為很容易受到外界因素的干擾；文獻(xiàn)[8]提出的TEEN協(xié)議，與LEACH采用相同的聚簇方式。其優(yōu)點是使數(shù)據(jù)傳輸量減少，而且其層次型簇頭結(jié)構(gòu)對節(jié)點功率沒有要求。但是因為存在門限設(shè)置，使某些數(shù)據(jù)上報受阻。

基于此，本文能平衡網(wǎng)絡(luò)各節(jié)點能量角度出發(fā)，提出了基于能量優(yōu)化的路由協(xié)議(Energy Optimization Ad Hoc Routing Protocol，EOARP)，該協(xié)議綜合考慮網(wǎng)絡(luò)各節(jié)點的通信繁忙程度，并引入公共經(jīng)濟(jì)學(xué)中洛倫茨指數(shù)法[9](Approach of Lorenz)來衡量網(wǎng)絡(luò)的能耗均衡，由此建立代價函數(shù)PEQ，根據(jù)代價函數(shù)選擇剩余能量相對高，通信繁忙程度相對輕的路由鏈路，從而達(dá)到均衡網(wǎng)絡(luò)的目的。

1 能量均衡代價函數(shù)建立

EOARP路由協(xié)議不是單純以最短路徑為路由，而是從均衡網(wǎng)絡(luò)各節(jié)點能量方面著手，選擇剩余能量相對高，通信繁忙程度相對輕的路由鏈路，均衡網(wǎng)絡(luò)能量。從而最大限度地延長網(wǎng)絡(luò)的生命。

1.1 節(jié)點通信繁忙程度

節(jié)點通信繁忙程度是衡量路由協(xié)議質(zhì)量的重要指標(biāo)，節(jié)點越繁忙，該節(jié)點就越耗能，且不能及時接收數(shù)據(jù)，影響通信質(zhì)量，故必須綜合分配各節(jié)點的通信。設(shè)節(jié)點i的通信繁忙程度[10]為Ri，如式(1)所示：

(1)

其中，Qlen表示當(dāng)前轉(zhuǎn)發(fā)緩存隊列長度，Qmax表示節(jié)點轉(zhuǎn)發(fā)緩存隊列的最大長度，Nlink表示節(jié)點當(dāng)前的連接數(shù)，Nneighbor表示節(jié)點當(dāng)前的鄰居節(jié)點個數(shù)。和是系數(shù)，滿足a1+a2=1。Ri越大，說明節(jié)點i通信越繁忙。

1.2 能量均衡路由

節(jié)點耗能管理是各路由協(xié)議均要重點考慮問題，本協(xié)議從維護(hù)各節(jié)點能耗的均衡方向入手，引入公共經(jīng)濟(jì)學(xué)中洛倫茨指數(shù)法來衡量網(wǎng)絡(luò)的能耗均衡。

根據(jù)美國著名統(tǒng)計學(xué)家M.O.洛倫茨提出的洛倫茨曲線，按照節(jié)點現(xiàn)有貯能從低到高排序得出了網(wǎng)絡(luò)內(nèi)節(jié)點數(shù)累計百分比和節(jié)點剩余貯能累計百分比的洛倫茨曲線，并在此曲線的基礎(chǔ)上得出了度量節(jié)點剩余貯能分配不公平程度測定的基尼系數(shù)[11](Gini Coefficient)。如圖1所示。

圖1 網(wǎng)絡(luò)內(nèi)節(jié)點數(shù)累計百分比(%)

基尼系數(shù)為洛倫茨曲線與45度對角線圍成的面積和45度對角線以下的三角形面積之比。其取值范圍為[0，1]，當(dāng)各節(jié)點剩余貯能完全相等時基尼系數(shù)就為0；當(dāng)僅有一個節(jié)點剩余貯能為初始貯能E0，而其余節(jié)點剩余貯能均為0，則基尼系數(shù)就為1，達(dá)到了能量分配最不公平狀況。

基尼系數(shù)可由式(2)計算得出：

(2)

(3)

進(jìn)一步定義節(jié)點i的貯能剩余率[12]ηi如式(4)所示：

(4)

式中，Ei為節(jié)點i的剩余貯能，E0為其初始貯能。

在進(jìn)行路由選擇時，將結(jié)合網(wǎng)絡(luò)基尼系數(shù)及節(jié)點剩余貯能進(jìn)行比較，選擇剩余貯能最多的路由鏈路，實現(xiàn)能量均衡的目的。

1.3 路由代價函數(shù)

由上所述可得到基于能量有效的路由代價函數(shù)，當(dāng)網(wǎng)絡(luò)基尼系數(shù)在0.5以內(nèi)，說明在當(dāng)前的網(wǎng)絡(luò)內(nèi)，各節(jié)點剩余貯能比較平均。而且基尼系數(shù)越小，各節(jié)點剩余貯能越平均，當(dāng)基尼系數(shù)為0時，表明網(wǎng)絡(luò)各節(jié)點剩余貯能都一樣，且在路由選擇時更偏重選擇節(jié)點通信繁忙程度較輕的鏈路；而當(dāng)網(wǎng)絡(luò)基尼系數(shù)大于0.5，說明當(dāng)前網(wǎng)絡(luò)內(nèi)各節(jié)點剩余貯能相差校大，基尼系數(shù)越大，各節(jié)點剩余貯能就相差越大，此時，路由選擇則以偏重選擇鏈路剩余貯能較的鏈路。綜合考慮網(wǎng)絡(luò)內(nèi)各節(jié)點繁忙程度以及能量均衡機制，定義代價函數(shù)PEQ如式(5)所示：

(5)

由此可定義網(wǎng)絡(luò)最佳路由選擇函數(shù)，如式(6)所示

PathSelect[source,dest]=min[PEQ(K)]k∈[1，M]

(6)

式中，M表示本協(xié)議所形成的多條備選路徑。

2 能量有效的路由的建立

當(dāng)源節(jié)點S需要與目標(biāo)節(jié)點D通信時，由于其路由表中沒有相關(guān)路由條目信息，于是源節(jié)點就按如下步驟發(fā)起路由發(fā)現(xiàn)過程：

1)源節(jié)點S創(chuàng)建一個RREQ消息，消息中包括源地址、目標(biāo)地址、目標(biāo)節(jié)點序列號等，并將此RREQ向周圍鄰居節(jié)點廣播；

2)鄰居節(jié)點N收到一個RREQ消息后，首先對此消息進(jìn)行判斷，如果是首次收到該RREQ且本節(jié)點不是目標(biāo)節(jié)點時，則根據(jù)自身鏈路通信狀態(tài)及能量狀態(tài)由式(5)計算此鏈路的累計鏈路代價值，然后再轉(zhuǎn)發(fā)該RREQ消息到它的鄰居節(jié)點。如果節(jié)點不是首次收到該RREQ，前面已收到相同廣播標(biāo)識的RREQ時，則節(jié)點丟棄該消息；

3)當(dāng)RREQ消息轉(zhuǎn)發(fā)到目的節(jié)點D后，沿途經(jīng)過的節(jié)點都建立起到源節(jié)點的反向路由，讓RREQ消息在網(wǎng)絡(luò)內(nèi)轉(zhuǎn)發(fā)已經(jīng)產(chǎn)生RREP消息返回源節(jié)點；

4)源節(jié)點S收到RREP消息后，由式(6)計算出最佳路由鏈路，其余則作為備份鏈路保留下來。

3 路由維護(hù)

網(wǎng)絡(luò)運行中，各節(jié)點通過周期性地向周圍鄰居節(jié)點發(fā)送TTL[13]為1的“Hello”消息，以確定該節(jié)點到達(dá)鄰居節(jié)點的可達(dá)性，如果檢測到節(jié)點檢測到它的上游節(jié)點或下游節(jié)點鏈路斷開，則該節(jié)點將通知源節(jié)點重新根據(jù)前面式(6)，從多條備選路由中選擇一條鏈路代價最小的鏈路代替斷開鏈路。

4 性能分析與仿真

本文使用NS-2(版本2.34)[14]進(jìn)行仿真，將EOARP路由協(xié)議與E-AODV(An Energy-efficient AODV)[15]協(xié)議、I-LEACH(Improved LEACH )[16]進(jìn)行比較，分別在數(shù)據(jù)傳輸性能、能量均衡、以及網(wǎng)絡(luò)節(jié)點剩余能量[17]等方面指標(biāo)進(jìn)行比較。

4.1 仿真參數(shù)設(shè)置

假定網(wǎng)絡(luò)傳感器節(jié)點隨機分布在正方形區(qū)域范圍，且在此區(qū)域內(nèi)各節(jié)點隨機分布，實驗主要參數(shù)設(shè)置如表1所示。

4.2 仿真結(jié)果

1)數(shù)據(jù)傳輸性能比較：

路由協(xié)議數(shù)據(jù)傳輸性能，可從數(shù)據(jù)包投遞率和路由開銷兩方面進(jìn)行仿真，仿真EOARP、E-AODV、I-LEACH3種路由協(xié)議的數(shù)據(jù)包投遞率，如圖2所示。仿真結(jié)果表明，EOARP、E-AODV、I-LEACH這3種協(xié)議均保持著較高的投遞率，隨著時間的延長，數(shù)據(jù)包投遞率相應(yīng)增加，E-AODV協(xié)議和EOARP協(xié)議均保持了較高的數(shù)據(jù)包投遞率，且EOARP協(xié)議最高。

表1 仿真參數(shù)

圖2 數(shù)據(jù)包投遞率比較

仿真EOARP、E-AODV、I-LEACH三種路由協(xié)議的路由開銷，如圖3所示，仿真I-LEACH協(xié)議在路由開銷最小，E-AODV協(xié)議最大，而EOARP協(xié)議由于路由代價函數(shù)占用了一定的資源，導(dǎo)致路由開銷稍微變大相比I-LEACH協(xié)議稍弱。

圖3 路由開銷比較

2)能耗均衡比較：

仿真EOARP、E-AODV、I-LEACH三種協(xié)議下節(jié)點平均消耗的能量比較網(wǎng)絡(luò)能量消耗的均衡性。結(jié)果如圖4所示。從圖中可以看出：E-AODV和I-LEACH協(xié)議能耗因為也采用了能量優(yōu)化算法，波動不是很大，但是能耗維持在0.5 J左右。而EOARP協(xié)議網(wǎng)絡(luò)的能耗一直比較的平穩(wěn)，保持在0.4 J左右，表明EOARP協(xié)議網(wǎng)絡(luò)耗能比較均衡。

圖4 能耗均衡比較

3)節(jié)點剩余能量比較：

在EOARP、E-AODV、I-LEACH三種協(xié)議下，仿真網(wǎng)絡(luò)節(jié)點的平均剩余能量隨網(wǎng)絡(luò)運行時間的變化情況，結(jié)果如圖5所示。由圖中可看出：在0～50 s范圍內(nèi)E-AODV、I-LEACH、EOARP三種協(xié)議節(jié)點耗能均不大，50～150 s范圍時E-AODV、I-LEACH協(xié)議節(jié)點耗能明顯提高，耗能達(dá)60%以上，而EOARP協(xié)議節(jié)點耗能為50%左右。至250 s時，EOARP協(xié)議節(jié)點耗能才達(dá)到80%左右，而E-AODV、I-LEACH協(xié)議節(jié)點耗能已達(dá)90%以上。在整個網(wǎng)絡(luò)運行時間，EOARP協(xié)議均比E-AODV、I-LEACH協(xié)議的節(jié)點剩余能量剩余能量要多。

圖5 節(jié)點剩余能量比較

5 結(jié)論

從能量均衡角度出了提出了EOARP路由協(xié)議，該協(xié)議通過引入公共經(jīng)濟(jì)學(xué)中洛倫茨指數(shù)法來衡量網(wǎng)絡(luò)的能耗均衡，建立代價函數(shù)PEQ，根據(jù)代價函數(shù)選擇剩余能量相對高，通信繁忙程度相對輕的路由鏈路，從而達(dá)到均衡網(wǎng)絡(luò)的目的，提高了網(wǎng)絡(luò)的能量利用率，節(jié)約能源。仿真結(jié)果表明：文中提出的EOARP路由協(xié)議在數(shù)據(jù)傳輸性能、能量均衡、節(jié)點剩余能量等方面指標(biāo)方面均比E-AODV協(xié)議、I-LEACH協(xié)議有較大的改善。

[1] 趙志峰,鄭少仁. Ad hoc網(wǎng)絡(luò)體系結(jié)構(gòu)研究[J]. 電信科學(xué),2001,12(1)：14-17.

[2] 麻晉文. 移動Ad hoc網(wǎng)絡(luò)中AODV路由協(xié)議的研究[D].蘭州：蘭州大學(xué),2014.

[3] Ad M, Perkins C E, Das S R. Ad hoc On-Demand Distance Vector (AODV) Routing[J]. Rfc, 2000, 6(7)：90.

[4] 任豐原，黃海寧，林 闖．無線傳感器網(wǎng)絡(luò)[J]．軟件學(xué)報，2013，14(7)：1282-1291．

[5] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks[A]. System Sciences Proceedings of Annual Hawaii International Conference on[C]. 2000，8(8)：8020.

[6] 張足生，袁華強，于峰崎．無線傳感器網(wǎng)絡(luò)動態(tài)重傳算法[J]．傳感技術(shù)學(xué)報，2013，10(7)：1019-1024．

[7] 朱全政，楊 樂．能量角度聯(lián)合自適應(yīng)路由修復(fù)新算法[J]．計算機應(yīng)用研究，2014，31(6)：1779-1782．

[8] Manjeshwar A, Agrawal D P. TEEN：a protocol for enhanced efficiency in wireless sensor networks[A]. Proceedings of International Workshop on Parallel & Distributed Computing Issues in Wireless Networks & Mobile Computing[C]. 2001：2009 - 2015.

[9] 劉志偉. 收入分配不公平程度測度方法綜述[J]. 統(tǒng)計與信息論壇,2003,18(5)：28-32.

[10] 王志遠(yuǎn). 基于節(jié)點穩(wěn)定性和路由失效預(yù)測的SP_AODV路由協(xié)議的研究與實現(xiàn)[D].沈陽：東北大學(xué),2010：22-23.

[11] 胡祖光. 基尼系數(shù)理論最佳值及其簡易計算公式研究[J]. 經(jīng)濟(jì)研究,2004,(9)：60-69.

[12] 劉 杰,王 玲,王 杉，等. 基于能量有效的逆向AODV路由協(xié)議研究[J]. 計算機應(yīng)用研究,2015,32(6)：1849-1851.

[13] 荀寶鋮,羅軍勇. 基于TTL值異常的源地址偽造報文檢測方法[J]. 計算機應(yīng)用研究,2006,12：127-128.

[14] 王永勝, 吳德偉, 劉 勇. 基于NS2網(wǎng)絡(luò)仿真研究[J]. 計算機仿真, 2004, 21(11)：257-259.

[15]羅玉宏,王建新,陳松喬. 一種基于鏈路穩(wěn)定的能量有效AODV路由協(xié)議[J]. 電路與系統(tǒng)學(xué)報,2008,(6):141-147.[16]呂 濤,朱清新,張路橋. 一種基于LEACH協(xié)議的改進(jìn)算法[J]. 電子學(xué)報,2011,(6):1405-1409.

[17]林 愷,趙 海,尹震宇，等.無線傳感器網(wǎng)絡(luò)路由中的能量預(yù)測及算法實現(xiàn)[J].通信學(xué)報,2006,27(5)：21-27.

Research on Energy-balanced AD Hoc Network Routing Protocols

Liu Hong,Xia Weijun,Wang Qitao

(School of Electrical Engineering and Automation,Jiangxi University of Science and Technology，Ganzhou 341000,China)

The unbalanced node energy of traditional AD Hoc routing protocol causes alarger network energy,and it reduces network lifecycle.The article presents a energy optimization of Ad Hoc Network Routing Protocol (EOARP protocol) from the point of energy balance.Through the introduction of public economics Lorenz index to the average energy consumption of each node in the network,combined with the busy degree in communication and residual energy of nodes to establish cost functionPEQ.Select residual energy of the node relatively high,communication link routes is lesser busy, so as to achieve a energy-balanced network.As the simulation results EOARP routing protocol has improvement indexs such as data transmission performance, energy balance, and network node residual energy, so effectively prolongs the network life cycle.

wireless sensor network; routing protocol;energy balance;energy optimization

2015-09-13；

2015-10-20。

國家自然科學(xué)基金資助項目(61163063)。

劉 宏(1968-)，男，江西萍鄉(xiāng)人，副教授，碩士研究生導(dǎo)師，主要從事無線傳感器網(wǎng)絡(luò)基礎(chǔ)設(shè)施的理論和技術(shù)方向的研究。

1671-4598(2016)03-0204-04DOI：10.16526/j.cnki.11-4762/tp

TP

A