基于負(fù)載均衡的路由協(xié)議的設(shè)計

基于負(fù)載均衡的路由協(xié)議的設(shè)計

摘要在移動自組網(wǎng)中，減少移動節(jié)點電池能量消耗，延長網(wǎng)絡(luò)總的壽命時間，已經(jīng)成為路由協(xié)議性能評價的重要方面。本文提出了一種新的路由選擇度量，它綜合考慮了節(jié)點的剩余能量，路徑的延時和跳數(shù)，試圖通過一種最優(yōu)路徑選擇算法來保護(hù)網(wǎng)絡(luò)中的低能量節(jié)點。結(jié)合該度量方式還提出一種路由選擇協(xié)議LBAODV(LoadBalancingbasedAd-HocOn-DemandDistanceVectorRouting)，仿真結(jié)果表明，該協(xié)議能夠使節(jié)點能耗與負(fù)載的分布更為均勻，相比以前相關(guān)的路由算法有效提高了吞吐量。

關(guān)鍵詞Adhoc網(wǎng)絡(luò)；路由協(xié)議；負(fù)載均衡；AODV；能量1引言

移動AdHoc網(wǎng)絡(luò)(MANET)[1]是由一組移動節(jié)點通過自組連接形成的多跳無線網(wǎng)絡(luò)。不同于有線網(wǎng)絡(luò)，它不需要固定的基礎(chǔ)設(shè)施。由于其自組織性、快速部署和無須任何固定設(shè)施的特點，MANET有廣泛的應(yīng)用，如戰(zhàn)地指揮控制、緊急災(zāi)難恢復(fù)、礦場操作和研討會信息共享。MANET正作為重要的、有前途的研究領(lǐng)域受到極大關(guān)注。

如今按需路由協(xié)議是移動adhoc網(wǎng)絡(luò)中應(yīng)用最廣泛的一種路由協(xié)議。作為按需路由協(xié)議代表的AODV[2]和DSR[3]都是以最短路徑作為路由選擇的標(biāo)準(zhǔn)，它們在網(wǎng)絡(luò)輕負(fù)載情況下表現(xiàn)良好。然而，在高業(yè)務(wù)量的情況下，AODV和DSR的性能都急劇惡化[4]，部分原因是由于其在路徑選擇時傾向于使用相同的節(jié)點作為中間節(jié)點，大量的數(shù)據(jù)通過少量節(jié)點傳輸，引起網(wǎng)絡(luò)的阻塞，從而導(dǎo)致較高的分組時延，部分節(jié)點也會過早地電池耗盡。許多研究者認(rèn)識到，當(dāng)網(wǎng)絡(luò)負(fù)載較重時，最短路徑并非是MANET中用于路徑選擇的最佳度量[5，6]。

與此同時，網(wǎng)絡(luò)負(fù)載平衡正受到越來越多的關(guān)注。MANE網(wǎng)絡(luò)的各個節(jié)點在充當(dāng)終端角色發(fā)送和接收信息的同時，還作為路由中繼節(jié)點轉(zhuǎn)發(fā)信息。由于MNANET網(wǎng)絡(luò)特點，路由的選擇會直接影響網(wǎng)絡(luò)吞吐量，端到端時延，終端節(jié)點的能量消耗等參數(shù)。多數(shù)終端節(jié)點都采用有限電源模式，因此剩余能量就作為節(jié)點最寶貴的資源，一旦資源耗盡，終端節(jié)點就無法工作，也無法作為中繼節(jié)點繼續(xù)工作，進(jìn)而導(dǎo)致整個網(wǎng)絡(luò)無法正常運行。然而，在一些節(jié)點能量耗盡的時候，其它節(jié)點還有過多剩余能量，這就造成了MANET網(wǎng)絡(luò)的能耗不公平性，還有些節(jié)點擔(dān)負(fù)著比其它節(jié)點更為重要的作用，一旦能量耗盡會對整個網(wǎng)絡(luò)造成巨大損失。因此，就需要在基于最短路徑路由的常規(guī)路由協(xié)議基礎(chǔ)上，更多的考慮網(wǎng)絡(luò)的能量損耗公平性，即負(fù)載均衡性能。

本文第2節(jié)介紹MANET中負(fù)載平衡路由的相關(guān)工作;第3節(jié)描述路由協(xié)議LBAODV，提出一種新的路由選擇度量，它綜合考慮了節(jié)點的剩余能量，路徑的延時和跳數(shù)，試圖通過一種最優(yōu)路徑選擇算法來保護(hù)網(wǎng)絡(luò)中的低能量節(jié)點7第4節(jié)給出仿真環(huán)境、性能參數(shù)和仿真結(jié)果；最后提出結(jié)論和進(jìn)一步的研究工作。2負(fù)載均衡路由協(xié)議的研究

目前提出的負(fù)載均衡路由算法主要有：MRP–LB(Multi-PathRoutingwithLoadBalancing)[7]、MSR(Multi-PathSourceRouting)[8]、DLAR(DynamicLoad-AwareRouting)[9]、LWR(LoadAwareRouting)[10]、LSR(Load-SensitiveonDemandRouting)[11]和LBAR(Load-BalancedAdHocRouting)[12]。這些算法的選路準(zhǔn)則不再象普通的MANET中的路由算法(如：AODV、DSR等)那樣，以“路由最短”作為選路準(zhǔn)則，而是通過一些能夠反映網(wǎng)絡(luò)負(fù)載狀態(tài)的信息來作為選擇準(zhǔn)則。表1從選路準(zhǔn)則、性能評價、是否需要周期性發(fā)送信息三個方面列出了目前已提出的主要的負(fù)載均衡路由算法的特點。

由于現(xiàn)有的adhoc路由協(xié)議缺乏網(wǎng)絡(luò)負(fù)載平衡能力，而且沒有考慮網(wǎng)絡(luò)中的每個節(jié)點的壽命，面對大量數(shù)據(jù)業(yè)務(wù)，協(xié)議不能提供令人滿意的性能。針對上述的不足之處，本文提出了LBAODV協(xié)議是綜合路由的負(fù)載均衡，延時和跳數(shù)來選擇最優(yōu)路徑的。改進(jìn)主要基于以下幾個方面：

1）當(dāng)中間節(jié)點收到RREQ消息后，首先判斷自己的剩余能量所處的狀態(tài)，進(jìn)而來判斷是否進(jìn)行轉(zhuǎn)發(fā)，從而防止了RREQ分組在全網(wǎng)范圍內(nèi)的不必要轉(zhuǎn)發(fā)和某些節(jié)點的失效，減少了網(wǎng)絡(luò)擁塞，提高了系統(tǒng)吞吐量，并且平衡網(wǎng)絡(luò)負(fù)載，延長了重負(fù)荷節(jié)點的生存時間。

2）當(dāng)中間節(jié)點（或者目的節(jié)點）收到來自不同路徑的同一個路由請求識別碼的路由請求時，對收到的各請求分組中包含的路徑信息進(jìn)行緩存，然后本節(jié)點將從收到的多個來自不同路徑的路由應(yīng)答分組中按照一定的算法綜合考慮路由的負(fù)載均衡，延時和跳數(shù)來選擇最優(yōu)路徑進(jìn)行記錄，以便數(shù)據(jù)分組可以選擇到目的節(jié)點代價最優(yōu)的路徑進(jìn)行傳輸。3LBAODV協(xié)議描述3.1三級電池能量閾值保護(hù)狀態(tài)

考慮到AdHoc網(wǎng)絡(luò)的節(jié)點能量受限，一旦能量耗盡就不能繼續(xù)工作。而骨干節(jié)點停止工作后將很容易導(dǎo)致整個網(wǎng)絡(luò)的失效。所以路由選擇應(yīng)該盡量避免使用那些剩余能量少的那些節(jié)點。LBAODV協(xié)議按式（3-1）定義電池剩余能量率RER（ResidualEnergyRatio）：此外根據(jù)節(jié)點的剩余能量，每個節(jié)點根據(jù)自身的能量等級對路由請求做出相應(yīng)的響應(yīng)。本協(xié)議采用了3個能量級別，分別為：Danger，Warning，Normal，分別對應(yīng)于rer1，rer2，rer3三級閾值。其中三者順序為：rer1<rer2<rer3。當(dāng)中間節(jié)點收到RREQ消息后，首先判斷自己的剩余能量所處的狀態(tài)，進(jìn)而來判斷是否進(jìn)行轉(zhuǎn)發(fā)該消息。

1）若當(dāng)前節(jié)點的處于Danger狀態(tài)時，該節(jié)點將丟棄所有路由請求信息，不再進(jìn)行任何的消息轉(zhuǎn)發(fā)，從而保護(hù)了該節(jié)點。它只為自己作為源節(jié)點或者目的節(jié)點的路徑服務(wù)；

2）若當(dāng)前節(jié)點處于Warning狀態(tài)時，該節(jié)點將在它的路由表中查找符合條件的替換節(jié)點，并且通知它的上下游節(jié)點實現(xiàn)本地路徑的更新；

3）若當(dāng)前節(jié)點處于Normal狀態(tài)時，在路由請求RREQ中添加一個字段來記錄所經(jīng)過節(jié)點的最小剩余能量率，以及來記錄RREQ從源節(jié)點發(fā)出到目的節(jié)點的延遲。然后繼續(xù)廣播RREQ。3.2LBAODV協(xié)議描述3.2.1路由發(fā)現(xiàn)操作

當(dāng)源節(jié)點需要和另一節(jié)點進(jìn)行通信但沒有到目的節(jié)點的有效路由可使用時，協(xié)議通過對RREQ進(jìn)行廣播的方式發(fā)起路由發(fā)現(xiàn)過程。RREQ消息攜帶有源節(jié)點和目的節(jié)點地址、初始化值為0且每次遞加1的序列號、和源節(jié)點的剩余能量率RER添加到相應(yīng)的域。收到RREQ消息的各中間節(jié)點將對本節(jié)點的剩余能量狀態(tài)進(jìn)行判斷。剩余能量不足而導(dǎo)致功能受限節(jié)點通過丟棄RREQ而防止本節(jié)點成為新路徑的中間節(jié)點，以避免RREQ風(fēng)暴。使產(chǎn)生的路由在避開受限節(jié)點的同時減少了受限節(jié)點轉(zhuǎn)發(fā)RREQ帶來的附加控制開銷。非功能受限狀態(tài)的中間節(jié)點在收到第一個RREQ時，對RREQ中攜帶的節(jié)點序列號和相應(yīng)路徑的信息進(jìn)行記錄之后，然后對域進(jìn)行設(shè)置為原始值和該節(jié)點延遲轉(zhuǎn)發(fā)的時間之和，再將本節(jié)點的剩余能量率RER和該請求消息中的域中的值進(jìn)行比較，如果小于該值，則把當(dāng)前節(jié)點的剩余能量RER添加到該域中。以實現(xiàn)對RREQ的更新，并將更新后的RREQ再次向目的節(jié)點廣播。源節(jié)點和目的節(jié)點地址、序列號相同的兩個RREQ應(yīng)被認(rèn)為是同一個RREQ分組。當(dāng)一個中間節(jié)點收到RREP分組時，直接按照RREP中包含的路徑對RREP繼續(xù)進(jìn)行轉(zhuǎn)發(fā)。另外，當(dāng)中間節(jié)點收到RREP分組時，還會更新本節(jié)點到目的節(jié)點的路由。3.2.2源節(jié)點的操作

在AODV協(xié)議中，源節(jié)點只接收第一個到達(dá)的RREP報文。在改進(jìn)的LBAODV協(xié)議中，主要做了兩方面的改進(jìn)。第一：節(jié)點收到數(shù)據(jù)包后不是一律立即轉(zhuǎn)發(fā)，而是按照剩余能量的多少，延遲一個與剩余能量成反比