基于能量均衡和擁塞程度的改進(jìn)AODV路由協(xié)議

陳書旺,宋樹麗,宋彤彤,王真真,尹曉偉,黃 濤

(1.河北科技大學(xué)信息科學(xué)與工程學(xué)院，石家莊 050000；2.河北科技大學(xué)教務(wù)處，石家莊 050000)

無線自組網(wǎng)(wireless Ad Hoc network)是由一組移動節(jié)點(diǎn)動態(tài)形成的網(wǎng)絡(luò)，以無線鏈路的方式進(jìn)行數(shù)據(jù)傳輸，且不需基礎(chǔ)設(shè)施的臨時性網(wǎng)絡(luò)[1]。并且具有無中心性、拓?fù)鋭討B(tài)性、抗毀性等特點(diǎn)。主要應(yīng)用在軍事和民用方面，尤其是應(yīng)用在通信設(shè)施資源匱乏的場合中。而自組網(wǎng)節(jié)點(diǎn)進(jìn)行通信的前提是路由協(xié)議，因此路由協(xié)議成為目前自組網(wǎng)體系結(jié)構(gòu)中的熱門研究對象。中外的一些學(xué)者提出了許多路由協(xié)議標(biāo)準(zhǔn)，路由協(xié)議的性能不同導(dǎo)致所適用的環(huán)境不同。根據(jù)路由發(fā)現(xiàn)策略的不同分為兩類：①反應(yīng)式表驅(qū)動路由協(xié)議，如DSDV(destination sequenced distance vector routing)、WRP(wireless routing protocol)等；②反應(yīng)式按需基于源端路由協(xié)議，如DSR(dynamic source routing)[2]、AODV等[3]；其中表驅(qū)動路由協(xié)議需要周期性地廣播路由更新消息，這類路由協(xié)議需要較高的資源代價(jià)，路由成本大、能量利用率較低。而按需路由協(xié)議非常適用于自組網(wǎng)，不需要實(shí)時維護(hù)路由消息?？梢怨?jié)省網(wǎng)絡(luò)資源，提高能量利用率，減少擁塞，適應(yīng)網(wǎng)絡(luò)的拓?fù)渥兓?，延長網(wǎng)絡(luò)的生存時間。

AODV[4-5](Ad Hoc on demand distance vector routing)是一種典型的按需路由協(xié)議，包括路由發(fā)現(xiàn)和路由維護(hù)兩個階段。當(dāng)源節(jié)點(diǎn)需要與目的節(jié)點(diǎn)建立通信鏈路時，首先要在通信范圍內(nèi)廣播RREQ(routing request)，中間節(jié)點(diǎn)會根據(jù)是否是首次收到RREQ來決定是否轉(zhuǎn)發(fā)，目的節(jié)點(diǎn)收到RREQ后需要向源節(jié)點(diǎn)回復(fù)RREP(routing reply)。報(bào)文RREP會經(jīng)過中間節(jié)點(diǎn)回到源節(jié)點(diǎn)，此時就建立了路由路徑。通信過程中在遇到鏈路中斷時AODV會發(fā)起本地路由修復(fù)進(jìn)行維護(hù)。

相比于其他路由協(xié)議，AODV路由協(xié)議的只有在需要時才會發(fā)起路由尋找，這樣提高了網(wǎng)絡(luò)資源利用率，減少延遲。AODV路由協(xié)議能快速響應(yīng)網(wǎng)路的拓?fù)渥兓?，并且不會形成環(huán)路。由于人們對網(wǎng)絡(luò)性能的要求不斷提高，近年來許多學(xué)者對AODV路由協(xié)議在不同方面進(jìn)行了優(yōu)化。Ranjan等[6]提出了IOAS-AODV(improved optimum angle selection-AODV)一種新的路由算法，通過基于象限位置，電池狀態(tài)，隊(duì)列長度，選擇一組交替路徑的有限節(jié)點(diǎn)來避免擁塞和修復(fù)斷鏈。陸偉等[7]對于能量損耗提出了一種新的改進(jìn)機(jī)制，構(gòu)造了一種數(shù)學(xué)模型，其中包含節(jié)點(diǎn)的信號屬性。根據(jù)鏈路質(zhì)量和能量的消耗情況來選擇路徑。此協(xié)議在通信中不僅能保證能量消耗最小還能選擇最優(yōu)的路徑。何王吉等[8]提出了一種電量估算策略，將復(fù)合期望傳輸次數(shù)和節(jié)點(diǎn)的剩余能量作為路由度量。改進(jìn)后的算法有效減少能量損耗,延長網(wǎng)絡(luò)生存時間。文獻(xiàn)[9]針對擁塞問題提出了一種新的機(jī)制，根據(jù)路由度量得到函數(shù)擬合曲線，根據(jù)擬合曲線來設(shè)定不同的閾值。由平均隊(duì)列與閾值的關(guān)系決定是否丟棄報(bào)文。這種新的機(jī)制在路由性能方面都優(yōu)于傳統(tǒng)的AODV。李愛武等[10]對路由協(xié)議在擁塞方面進(jìn)行了優(yōu)化，在平均隊(duì)列的基礎(chǔ)上提出了動態(tài)檢測的方式，根據(jù)擁塞程度向相鄰節(jié)點(diǎn)發(fā)出信號，鄰居節(jié)點(diǎn)嘗試找出一條可替代的路徑來進(jìn)行通信。這種改進(jìn)的算法提高了路由協(xié)議的性能。文獻(xiàn)[11]針對擁塞提出了兩種優(yōu)化協(xié)議：EDAODV(early detection congestion and control routing protocol)和AODV-I(improved Ad-Hoc on-demand distance vector routing protocol)，其中EDAODV采用雙向路徑發(fā)現(xiàn)，預(yù)先檢測擁塞，而AODV-I協(xié)議在RREQ中添加了擁塞處理，可以避免選擇忙路由，同時RREQ還添加了路由修復(fù)機(jī)制，這種改進(jìn)使資源能充分利用。

自組網(wǎng)中由于每個無線節(jié)點(diǎn)的能量可用性有限，在通信過程中節(jié)點(diǎn)的能量會不斷減少直至耗盡，所以在數(shù)據(jù)轉(zhuǎn)發(fā)過程中考慮能量是非常必要的。而保證鏈路穩(wěn)定傳輸就必須要考慮擁塞問題，擁塞的后果會導(dǎo)致數(shù)據(jù)丟失甚至網(wǎng)絡(luò)發(fā)生崩潰。因此路由度量的選擇對于通信質(zhì)量至關(guān)重要。AODV路由協(xié)議只將跳數(shù)作為選擇路徑的標(biāo)準(zhǔn)，學(xué)者們在選擇路徑時只加入了能量或擁塞因素，這使得路徑的選擇變得局限。

基于以上的背景和分析，以AODV協(xié)議為基礎(chǔ)，將路徑擁塞和能量損耗同時考慮在內(nèi)，并且將能量狀態(tài)和擁塞狀態(tài)分成不同的等級并用不同的跳數(shù)來表示。引入了跳數(shù)代價(jià)和路徑判斷因子，根據(jù)跳數(shù)代價(jià)和實(shí)際跳數(shù)得出每段路徑的總跳數(shù)，最后利用路徑判斷的公式將每段路徑的跳數(shù)累加得到最終的跳數(shù)，選擇跳數(shù)最少的路徑進(jìn)行數(shù)據(jù)的傳輸。改進(jìn)后的路由協(xié)議有效地減少網(wǎng)絡(luò)擁塞，減少延遲，提高節(jié)點(diǎn)的存活率。

1 改進(jìn)的路由選擇算法的度量指標(biāo)

1.1 擁塞度量——跳數(shù)

當(dāng)鏈路發(fā)生擁塞時會造成丟包率增加、端到端時延增加、吞吐量下降等問題。用緩沖區(qū)占有率(buffer occupation rate,BOR)來衡量擁塞程度，緩存占用率表示：某一時間段此鏈路的隊(duì)列長度與鏈路最大可承載長度的比值。擁塞度(congestion degree,CD)的表示方法：

(1)

式(1)中：Lt為某一時間內(nèi)鏈路的隊(duì)列長度；Lm表示鏈路最大可承載的長度。其中，Lt為一個不斷變化的值，Lm為一個定值。AODV協(xié)議中，路徑的選擇是以跳數(shù)的大小為標(biāo)準(zhǔn)。所以提出將擁塞以跳數(shù)的形式表示，引入一個擁塞因子C(hhops)。將擁塞度轉(zhuǎn)化為跳數(shù)分為以下三種情形。

(1)CD≤20%時，表示鏈路處于穩(wěn)定的狀態(tài)，基本上不會發(fā)生擁塞，數(shù)據(jù)可以正常通信，此時跳數(shù)代價(jià)為0，即：

C(hhops)=0

(2)

(2)20%

C(hhops)=3

(3)

(3)CD≥60%時，數(shù)據(jù)緩沖區(qū)已經(jīng)要達(dá)到飽和狀態(tài)，開始處于丟包階段，丟棄數(shù)據(jù)包，增加端到端的時間。此時的跳數(shù)代價(jià)為6，即：

C(hhops)=6

(4)

1.2 剩余能量——跳數(shù)

在復(fù)雜的網(wǎng)絡(luò)環(huán)境中，考慮能量因素是至關(guān)重要的，由于AODV的重傳次數(shù)增加，會引起網(wǎng)絡(luò)風(fēng)暴，造成不必要的能量消耗。選擇剩余能量大的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的接收和發(fā)送，可以延長網(wǎng)絡(luò)的生存時間。剩余能量等級表示為

(5)

式(5)中：Ei為節(jié)點(diǎn)i的剩余能量；Es為節(jié)點(diǎn)的初始能量。為了將能量以跳數(shù)的形式表示出來，引入一個能量因子E(hhops)。分以下四種情況討論。

(1)當(dāng)Er≥0.5時，表明節(jié)點(diǎn)剩余大量能量，可以正常通信，接收和轉(zhuǎn)發(fā)數(shù)據(jù)。此時的跳數(shù)代價(jià)為0，即：

E(hhops)=0

(6)

(2)當(dāng)0.2

E(hhops)=3

(7)

(3)當(dāng)0.1≤Er≤0.2時，表明節(jié)點(diǎn)能量損耗大部分，所剩無幾了，為了在數(shù)據(jù)傳輸?shù)臅r候盡量地減少時延，防止此類節(jié)點(diǎn)參與通信傳輸。跳數(shù)代價(jià)設(shè)為6，即：

E(hhops)=6

(8)

(4)當(dāng)Er<0.1時，表明節(jié)點(diǎn)已經(jīng)接近枯竭，只能作為目的節(jié)點(diǎn)來接收數(shù)據(jù)。

1.3 路徑判斷因子ω

在CE-AODV-H協(xié)議中，定義了判斷因子ω作為路由選擇的判定依據(jù)：

ω=ω0+ω1+…+ωi

(9)

式(9)中：ω0～ωi分別表示每段路徑的穩(wěn)定判斷因子，ωi表示AODV路由在選擇路徑時的綜合考量，其表達(dá)式為

ωi=αC(hhops)+βE(hhops)+μhhops

(10)

式(10)中：α、β、μ為權(quán)重因子，均為小于1的正整數(shù)，且α+β+μ=1，可以根據(jù)自組網(wǎng)的具體應(yīng)用場景來設(shè)定。根據(jù)式(9)計(jì)算最后的ω。選擇ω最小且目的節(jié)點(diǎn)序列號最新的鏈路進(jìn)行通信。如果ω相同，選擇最先到達(dá)目的節(jié)點(diǎn)的鏈路。

2 最優(yōu)路徑的發(fā)現(xiàn)和建立

(1)改進(jìn)后的路由協(xié)議在路由表中增加了三個字段，CD、Er和ω。

(2)在路由請求RREQ中增加ω0字段。作為選擇路徑的依據(jù)。

(3)運(yùn)行路由協(xié)議前對α、β、μ進(jìn)行賦值。

2.1 路由發(fā)現(xiàn)

源節(jié)點(diǎn)需要向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時，首先要檢查路由表中是否有到達(dá)目的節(jié)點(diǎn)的的有效路由，如果沒有就執(zhí)行路由發(fā)現(xiàn)過程，在發(fā)送數(shù)據(jù)前，計(jì)算的節(jié)點(diǎn)CD和Er算出ω0，填入RREQ報(bào)文中的ω0字段處。

2.2 中間節(jié)點(diǎn)對RREQ的處理

中間節(jié)點(diǎn)在接收到RREQ包時，首先建立一個用于記錄反向路徑的表項(xiàng)，先不分配有效序列號，如果是第一次收到RREQ首先要判斷節(jié)點(diǎn)剩余能量的等級Er。

(1)如果Er<0.1時，則直接丟棄該節(jié)點(diǎn)。

(2)如果能量-跳數(shù)代價(jià)為式(6)～式(8)情況下記錄此時的跳數(shù)，其次判斷擁塞度，并記錄此時的總跳數(shù)ωi。然后繼續(xù)RREQ的數(shù)據(jù)轉(zhuǎn)發(fā)。中間節(jié)點(diǎn)轉(zhuǎn)發(fā)流程圖如圖1所示。

圖1 中間節(jié)點(diǎn)轉(zhuǎn)發(fā)流程Fig.1 Intermediate node forwarding process

2.3 目的節(jié)點(diǎn)對RREQ的處理

為了選擇最優(yōu)的路徑，目的節(jié)點(diǎn)同樣需要對路徑進(jìn)行能量和擁塞的判斷，當(dāng)RREQ到達(dá)目的節(jié)點(diǎn)后，設(shè)定等待時間的上限，超過等待時間，此時要更新該節(jié)點(diǎn)的路由表信息，根據(jù)路由表攜帶的跳數(shù)、擁塞、能量計(jì)算路徑的ωi，最后選擇ω最小的路徑進(jìn)行RREP的轉(zhuǎn)發(fā)。

2.4 改進(jìn)算法路徑選擇實(shí)現(xiàn)

圖2為改進(jìn)算法的路徑選擇過程，將擁塞和能量考慮在內(nèi)。從圖2中可以看出，從源節(jié)點(diǎn)S到目的節(jié)點(diǎn)D共有三條路徑，L1：S→A→B→D；L2：S→A→C→E→D；L3：S→F→G→D。由于此網(wǎng)絡(luò)對能量比較敏感，所以將β賦值為0.5，α設(shè)為0.2，μ為0.3。設(shè)定節(jié)點(diǎn)初始能量為100 J,鏈路最大可承受長度為50。某一時刻節(jié)點(diǎn)狀態(tài)：L1路徑：實(shí)際跳數(shù)為2，節(jié)點(diǎn)A的剩余能量為60 J，擁塞度為2/5，節(jié)點(diǎn)B的剩余能量為20 J，擁塞度為3/5。L2路徑：實(shí)際跳數(shù)為3，節(jié)點(diǎn)A的剩余能量為60 J，擁塞度為2/5，節(jié)點(diǎn)C的剩余能量為50 J，擁塞度為1/5，節(jié)點(diǎn)E的剩余能量為40 J，擁塞度為1/5。L3路徑：實(shí)際跳數(shù)為2，節(jié)點(diǎn)F的剩余能量為30 J，擁塞為2/5，節(jié)點(diǎn)G的剩余能量為9 J，擁塞為3/5。

圖2 路由建立過程Fig.2 Route establishment process

傳統(tǒng)的AODV會選擇L1I路徑或L3路徑，但將能量和擁塞考慮在內(nèi)，在選擇路徑時，由于節(jié)點(diǎn)G的剩余能量等級Er<0.1,所以丟棄該節(jié)點(diǎn)，排除路徑L3。根據(jù)式(9)、式(10)計(jì)算鏈路的ω的值，得出路徑L2的ω大于路徑L3的ω。最終選擇L2路徑為最優(yōu)路徑進(jìn)行傳輸數(shù)據(jù)。

3 仿真與結(jié)果分析

使用仿真平臺為網(wǎng)絡(luò)仿真器NS2(network simulator-2,NS2.35)。仿真參數(shù)設(shè)置：①區(qū)域面積： 1 000 m×500 m；②節(jié)點(diǎn)移動速度：0～10 m/s；③模擬時間：100 s；④移動模型：隨機(jī)路點(diǎn)模型；⑤無線模型mac：802.11；⑥連接數(shù)：10；⑦數(shù)據(jù)包尺寸：512 B；⑧字節(jié)初始能量：100 J；⑨暫停時間：0、25、50、75、100 s。

衡量路由協(xié)議的標(biāo)準(zhǔn)為路由開銷、數(shù)據(jù)包投遞率、節(jié)點(diǎn)存活率和端到端時延。路由開銷指路由消息數(shù)與節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的比值。反映了網(wǎng)絡(luò)的路由效率。數(shù)據(jù)包投遞率表示目的節(jié)點(diǎn)所接收的數(shù)據(jù)包與源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包之比，反映了網(wǎng)絡(luò)傳輸?shù)目煽啃?。端到端時延即包的延時就是指包的接收時間與包的發(fā)送時間差。節(jié)點(diǎn)存活率指模擬時間結(jié)束所存活的節(jié)點(diǎn)與總節(jié)點(diǎn)數(shù)的比值。通過改變暫停時間來仿真AODV、CE-AODV-H和AODV-I路由協(xié)議。

圖3 端到端的時延Fig.3 End-to-end delay

圖3表明CE-AODV-H、AODV和AODV-I三種路由協(xié)議的端到端時延整體上隨著暫停時間的增大而減少，在暫停時間較小時，節(jié)點(diǎn)移動速度快，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化迅速，節(jié)點(diǎn)的能量消耗快，鏈路隊(duì)列易發(fā)生擁塞。AODV-I路由協(xié)議只將擁塞考慮在內(nèi)，在端到端時延方面由于AODV協(xié)議，而提出的路由協(xié)議中，選取剩余能量大的節(jié)點(diǎn)傳輸，控制隊(duì)列長度能有效地緩解擁塞，比AODV-I和AODV路由協(xié)議的時延都小。

圖4、圖5表明改進(jìn)后的路由協(xié)議CE-AODV-H在數(shù)據(jù)包投遞率和路由開銷方面方面優(yōu)于AODV和AODV-I路由協(xié)議，暫停時間增加，節(jié)點(diǎn)移動變慢，路由轉(zhuǎn)發(fā)次數(shù)減少，路由開銷也就減少，數(shù)據(jù)不易發(fā)生丟包，數(shù)據(jù)包投遞率增加，改進(jìn)的協(xié)議引入了能量和擁塞的等級來選擇最短路徑，有效地提高了數(shù)據(jù)包投遞率。

圖4 數(shù)據(jù)包投遞率Fig.4 Packet delivery rate

圖5 路由開銷Fig.5 Routing overhead

圖6 節(jié)點(diǎn)存活率Fig.6 Node survival rate

圖6為在整個仿真時間內(nèi)節(jié)點(diǎn)的存活情況，隨著暫停時間的不斷增加，節(jié)點(diǎn)的存活率也不斷增加。在仿真的過程中用跳數(shù)來表示能量的等級，剩余能量大，跳數(shù)代價(jià)小，參與通信時可以更好地避免節(jié)點(diǎn)死亡，因此相比于AODV和AODV-I路由協(xié)議，CE-SODV-H可以更好地提高節(jié)點(diǎn)的存活率。

4 結(jié)論

針對數(shù)據(jù)傳輸過程中能量消耗過大導(dǎo)致節(jié)點(diǎn)死亡、隊(duì)列長度過長導(dǎo)致?lián)砣?，提出了CE-AODV-H改進(jìn)路由協(xié)議，通過緩沖區(qū)占有率將擁塞分成不同的等級，同時將剩余能量也劃分等級，丟棄能量小的節(jié)點(diǎn)，不同的等級用不同的跳數(shù)代價(jià)表示?；谀芰亢蛽砣鴶?shù)最小建立路由，同時還考慮了權(quán)重因子α、β、μ的配置問題，可以根據(jù)不同的場景靈活的配置，更好地滿足路由需求。仿真結(jié)果表明，CE-AODV-H路由協(xié)議相比于普通的AODV路由協(xié)議減少了路由開銷和端到端的時延，提高了數(shù)據(jù)包投遞率和節(jié)點(diǎn)的存活率。路由性能進(jìn)一步得到了改善。