劉 宏，夏未君，王其濤

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

?

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

劉 宏，夏未君，王其濤

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

傳統(tǒng)的ADHoc路由協(xié)議由于節(jié)點(diǎn)的能量不均衡，導(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é)點(diǎn)通信繁忙程度、節(jié)點(diǎn)剩余能量等因素建立代價(jià)函數(shù)PEQ，選擇剩余能量相對較高，通信繁忙程度較輕的路由鏈路，從而達(dá)到均衡網(wǎng)絡(luò)的目的；仿真結(jié)果表明，EOARP協(xié)議在數(shù)據(jù)傳輸性能、能量均衡、以及網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量等方面指標(biāo)均有較大改善，有效地延長了網(wǎng)絡(luò)生命周期。

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

0 引言

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

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

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

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

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

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

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

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

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

(1)

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

1.2 能量均衡路由

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

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

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

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

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

(2)

(3)

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

(4)

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

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

1.3 路由代價(jià)函數(shù)

由上所述可得到基于能量有效的路由代價(jià)函數(shù)，當(dāng)網(wǎng)絡(luò)基尼系數(shù)在0.5以內(nèi)，說明在當(dāng)前的網(wǎng)絡(luò)內(nèi)，各節(jié)點(diǎn)剩余貯能比較平均。而且基尼系數(shù)越小，各節(jié)點(diǎn)剩余貯能越平均，當(dāng)基尼系數(shù)為0時(shí)，表明網(wǎng)絡(luò)各節(jié)點(diǎn)剩余貯能都一樣，且在路由選擇時(shí)更偏重選擇節(jié)點(diǎn)通信繁忙程度較輕的鏈路；而當(dāng)網(wǎng)絡(luò)基尼系數(shù)大于0.5，說明當(dāng)前網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)剩余貯能相差校大，基尼系數(shù)越大，各節(jié)點(diǎn)剩余貯能就相差越大，此時(shí)，路由選擇則以偏重選擇鏈路剩余貯能較的鏈路。綜合考慮網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)繁忙程度以及能量均衡機(jī)制，定義代價(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é)點(diǎn)S需要與目標(biāo)節(jié)點(diǎn)D通信時(shí)，由于其路由表中沒有相關(guān)路由條目信息，于是源節(jié)點(diǎn)就按如下步驟發(fā)起路由發(fā)現(xiàn)過程：

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

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

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

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

3 路由維護(hù)

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

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é)點(diǎn)剩余能量[17]等方面指標(biāo)進(jìn)行比較。

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

假定網(wǎng)絡(luò)傳感器節(jié)點(diǎn)隨機(jī)分布在正方形區(qū)域范圍，且在此區(qū)域內(nèi)各節(jié)點(diǎn)隨機(jī)分布，實(shí)驗(yàn)主要參數(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í)間的延長，數(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é)議由于路由代價(jià)函數(shù)占用了一定的資源，導(dǎo)致路由開銷稍微變大相比I-LEACH協(xié)議稍弱。

圖3 路由開銷比較

2)能耗均衡比較：

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

圖4 能耗均衡比較

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

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

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

5 結(jié)論

從能量均衡角度出了提出了EOARP路由協(xié)議，該協(xié)議通過引入公共經(jīng)濟(jì)學(xué)中洛倫茨指數(shù)法來衡量網(wǎng)絡(luò)的能耗均衡，建立代價(jià)函數(shù)PEQ，根據(jù)代價(jià)函數(shù)選擇剩余能量相對高，通信繁忙程度相對輕的路由鏈路，從而達(dá)到均衡網(wǎng)絡(luò)的目的，提高了網(wǎng)絡(luò)的能量利用率，節(jié)約能源。仿真結(jié)果表明：文中提出的EOARP路由協(xié)議在數(shù)據(jù)傳輸性能、能量均衡、節(jié)點(diǎn)剩余能量等方面指標(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] 麻晉文. 移動(dòng)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é)報(bào)，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] 張足生，袁華強(qiáng)，于峰崎．無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)重傳算法[J]．傳感技術(shù)學(xué)報(bào)，2013，10(7)：1019-1024．

[7] 朱全政，楊 樂．能量角度聯(lián)合自適應(yīng)路由修復(fù)新算法[J]．計(jì)算機(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)計(jì)與信息論壇,2003,18(5)：28-32.

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

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

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

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

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

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

[17]林 愷,趙 海,尹震宇，等.無線傳感器網(wǎng)絡(luò)路由中的能量預(yù)測及算法實(shí)現(xiàn)[J].通信學(xué)報(bào),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é)基金資助項(xiàng)目(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