負(fù)載均衡協(xié)議

基于負(fù)載均衡的路由協(xié)議的設(shè)計(jì)1引言移動AdHoc網(wǎng)絡(luò)(MANET)［1］是由一組移動節(jié)點(diǎn)通過自組連接形成的多跳無線網(wǎng)絡(luò)。不同于有線網(wǎng)絡(luò)，它不需要固定的基礎(chǔ)設(shè)施。由于其自組織性、快速部署和無須任何固定設(shè)施的特點(diǎn)，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］，部分原因是由于其在路徑選擇時(shí)傾向于使用相同的節(jié)點(diǎn)作為中間節(jié)點(diǎn)，大量的數(shù)據(jù)通過少量節(jié)點(diǎn)傳輸，引起網(wǎng)絡(luò)的阻塞，從而導(dǎo)致較高的分組時(shí)延，部分節(jié)點(diǎn)也會過早地電池耗盡。許多研究者認(rèn)識到，當(dāng)網(wǎng)絡(luò)負(fù)載較重時(shí)，最短路徑并非是MANET中用于路徑選擇的最佳度量［5,6］。與此同時(shí)，網(wǎng)絡(luò)負(fù)載平衡正受到越來越多的關(guān)注。MANE網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)在充當(dāng)終端角色發(fā)送和接收信息的同時(shí)，還作為路由中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)信息。由于MNANET網(wǎng)絡(luò)特點(diǎn)，路由的選擇會直接影響網(wǎng)絡(luò)吞吐量，端到端時(shí)延，終端節(jié)點(diǎn)的能量消耗等參數(shù)。多數(shù)終端節(jié)點(diǎn)都采用有限電源模式，因此剩余能量就作為節(jié)點(diǎn)最寶貴的資源，一旦資源耗盡，終端節(jié)點(diǎn)就無法工作，也無法作為中繼節(jié)點(diǎn)繼續(xù)工作，進(jìn)而導(dǎo)致整個(gè)網(wǎng)絡(luò)無法正常運(yùn)行。然而，在一些節(jié)點(diǎn)能量耗盡的時(shí)候，其它節(jié)點(diǎn)還有過多剩余能量，這就造成了MANET網(wǎng)絡(luò)的能耗不公平性，還有些節(jié)點(diǎn)擔(dān)負(fù)著比其它節(jié)點(diǎn)更為重要的作用，一旦能量耗盡會對整個(gè)網(wǎng)絡(luò)造成巨大損失。因此，就需要在基于最短路徑路由的常規(guī)路由協(xié)議基礎(chǔ)上，更多的考慮網(wǎng)絡(luò)的能量損耗公平性，即負(fù)載均衡性能。本文第2節(jié)介紹MANET中負(fù)載平衡路由的相關(guān)工作;第3節(jié)描述路由協(xié)議LBAODV，提出一種新的路由選擇度量，它綜合考慮了節(jié)點(diǎn)的剩余能量，路徑的延時(shí)和跳數(shù)，試圖通過一種最優(yōu)路徑選擇算法來保護(hù)網(wǎng)絡(luò)中的低能量節(jié)點(diǎn)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)則、性能評價(jià)、是否需要周期性發(fā)送信息三個(gè)方面列出了日前已提出的主要的負(fù)載均衡路由算法的特點(diǎn)。由于現(xiàn)有的adhoc路由協(xié)議缺乏網(wǎng)絡(luò)負(fù)載平衡能力，而且沒有考慮網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的壽命，面對大量數(shù)據(jù)業(yè)務(wù)，協(xié)議不能提供令人滿意的性能。針對上述的不足之處，本文提出了LBAODV協(xié)議是綜合路由的負(fù)載均衡，延時(shí)和跳數(shù)來選擇最優(yōu)路徑的。改進(jìn)主要基于以下幾個(gè)方面：1） 當(dāng)中間節(jié)點(diǎn)收到RREQ消息后，首先判斷自己的剩余能量所處的狀態(tài)，進(jìn)而來判斷是否進(jìn)行轉(zhuǎn)發(fā)，從而防止了RREQ分組在全網(wǎng)范圍內(nèi)的不必要轉(zhuǎn)發(fā)和某些節(jié)點(diǎn)的失效，減少了網(wǎng)絡(luò)擁塞，提高了系統(tǒng)吞吐量，并且平衡網(wǎng)絡(luò)負(fù)載，延長了重負(fù)荷節(jié)點(diǎn)的生存時(shí)間。2） 當(dāng)中間節(jié)點(diǎn)（或者日的節(jié)點(diǎn)）收到來自不同路徑的同一個(gè)路由請求識別碼的路由請求時(shí)，對收到的各請求分組中包含的路徑信息進(jìn)行緩存，然后本節(jié)點(diǎn)將從收到的多個(gè)來自不同路徑的路由應(yīng)答分組中按照一定的算法綜合考慮路由的負(fù)載均衡，延時(shí)和跳數(shù)來選擇最優(yōu)路徑進(jìn)行記錄，以便數(shù)據(jù)分組可以選擇到日的節(jié)點(diǎn)代價(jià)最優(yōu)的路徑進(jìn)行傳輸。表1負(fù)載均衡路由算法特點(diǎn)比較3LBAODV協(xié)議描述3.1三級電池能量閾值保護(hù)狀態(tài)考慮到AdHoc網(wǎng)絡(luò)的節(jié)點(diǎn)能量受限，一旦能量耗盡就不能繼續(xù)工作。而骨干節(jié)點(diǎn)停止工作后將很容易導(dǎo)致整個(gè)網(wǎng)絡(luò)的失效。所以路由選擇應(yīng)該盡量避免使用那些剩余能量少的那些節(jié)點(diǎn)。LBAODV協(xié)議按式（3-1）定義電池剩余能量率RER（ResidualEnergyRatio）（3-1）此外根據(jù)節(jié)點(diǎn)的剩余能量，每個(gè)節(jié)點(diǎn)根據(jù)自身的能量等級對路由請求做出相應(yīng)的響應(yīng)。本協(xié)議采用了3個(gè)能量級別，分別為：Danger，Warning，Normal，分別對應(yīng)于rer1，rer2，rer3三級閾值。其中三者順序?yàn)椋簉er1rer2rer3。當(dāng)中間節(jié)點(diǎn)收到RREQ消息后，首先判斷自己的剩余能量所處的狀態(tài)，進(jìn)而來判斷是否進(jìn)行轉(zhuǎn)發(fā)該消息。1） 若當(dāng)前節(jié)點(diǎn)的處于Danger狀態(tài)時(shí)，該節(jié)點(diǎn)將丟棄所有路由請求信息，不再進(jìn)行任何的消息轉(zhuǎn)發(fā)，從而保護(hù)了該節(jié)點(diǎn)。它只為自己作為源節(jié)點(diǎn)或者日的節(jié)點(diǎn)的路徑服務(wù)；2） 若當(dāng)前節(jié)點(diǎn)處于Warning狀態(tài)時(shí)，該節(jié)點(diǎn)將在它的路由表中查找符合條件的替換節(jié)點(diǎn)，并且通知它的上下游節(jié)點(diǎn)實(shí)現(xiàn)本地路徑的更新；3） 若當(dāng)前節(jié)點(diǎn)處于Normal狀態(tài)時(shí)，在路由請求RREQ中添加一個(gè)字段來記錄所經(jīng)過節(jié)點(diǎn)的最小剩余能量率，以及來記錄RREQ從源節(jié)點(diǎn)發(fā)出到日的節(jié)點(diǎn)的延遲。然后繼續(xù)廣播RREQ。3.2LBAODV協(xié)議描述3.2.1路由發(fā)現(xiàn)操作當(dāng)源節(jié)點(diǎn)需要和另一節(jié)點(diǎn)進(jìn)行通信但沒有到日的節(jié)點(diǎn)的有效路由可使用時(shí)，協(xié)議通過對RREQ進(jìn)行廣播的方式發(fā)起路由發(fā)現(xiàn)過程。RREQ消息攜帶有源節(jié)點(diǎn)和日的節(jié)點(diǎn)地址、初始化值為0且每次遞加1的序列號、和源節(jié)點(diǎn)的剩余能量率RER添加到相應(yīng)的域。收到RREQ消息的各中間節(jié)點(diǎn)將對本節(jié)點(diǎn)的剩余能量狀態(tài)進(jìn)行判斷。剩余能量不足而導(dǎo)致功能受限節(jié)點(diǎn)通過丟棄RREQ而防止本節(jié)點(diǎn)成為新路徑的中間節(jié)點(diǎn)，以避免RREQ風(fēng)暴。使產(chǎn)生的路由在避開受限節(jié)點(diǎn)的同時(shí)減少了受限節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQ帶來的附加控制開銷。非功能受限狀態(tài)的中間節(jié)點(diǎn)在收到第一個(gè)RREQ時(shí)，對RREQ中攜帶的節(jié)點(diǎn)序列號和相應(yīng)路徑的信息進(jìn)行記錄之后，然后對域進(jìn)行設(shè)置為原始值和該節(jié)點(diǎn)延遲轉(zhuǎn)發(fā)的時(shí)間之和，再將本節(jié)點(diǎn)的剩余能量率RER和該請求消息中的域中的值進(jìn)行比較，如果小于該值，則把當(dāng)前節(jié)點(diǎn)的剩余能量RER添加到該域中。以實(shí)現(xiàn)對RREQ的更新，并將更新后的RREQ再次向日的節(jié)點(diǎn)廣播。源節(jié)點(diǎn)和日的節(jié)點(diǎn)地址、序列號相同的兩個(gè)RREQ應(yīng)被認(rèn)為是同一個(gè)RREQ分組。當(dāng)一個(gè)中間節(jié)點(diǎn)收到RREP分組時(shí)，直接按照RREP中包含的路徑對RREP繼續(xù)進(jìn)行轉(zhuǎn)發(fā)。另外，當(dāng)中間節(jié)點(diǎn)收到RREP分組時(shí)，還會更新本節(jié)點(diǎn)到日的節(jié)點(diǎn)的路由。3.2.2源節(jié)點(diǎn)的操作在AODV協(xié)議中，源節(jié)點(diǎn)只接收第一個(gè)到達(dá)的RREP報(bào)文。在改進(jìn)的LBAODV協(xié)議中，主要做了兩方面的改進(jìn)。第一：節(jié)點(diǎn)收到數(shù)據(jù)包后不是一律立即轉(zhuǎn)發(fā)，而是按照剩余能量的多少，延遲一個(gè)與剩余能量成反比的時(shí)間（能量越少，延遲時(shí)間越長）轉(zhuǎn)發(fā)，如（3-2）式所示。這也是需要綜合考慮負(fù)載均衡，延時(shí)和跳數(shù)的原因（不再是簡單的跳數(shù)越多，延時(shí)越長）。第二：源節(jié)點(diǎn)收到第一個(gè)RREP報(bào)文后，啟動延遲器。當(dāng)延時(shí)器超時(shí)后，源節(jié)點(diǎn)根據(jù)以下策略在所有到達(dá)的可選路徑中選擇最優(yōu)路徑。如（3-3）式所示（3-2）其中，為該節(jié)點(diǎn)根據(jù)剩余能量而進(jìn)行的延遲，RE為剩余能量。（3-3）其中為最優(yōu)路徑，為該路徑中的最小剩余能量率，為該路徑的總的延遲，為該路徑的總的跳數(shù)，為各個(gè)參數(shù)的權(quán)重。在LBAODV協(xié)議中采用。3.2.3中間節(jié)點(diǎn)的操作當(dāng)源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)包且在它的路由表中沒有有效路徑時(shí)，就調(diào)用路由發(fā)現(xiàn)過程。源節(jié)點(diǎn)廣播一個(gè)路由請求（RREQ）消息，中間節(jié)點(diǎn)接收到（RREQ）后，將按照下列步驟執(zhí)行操作。if（路由表中有到日標(biāo)節(jié)點(diǎn)的路徑）{反向向源節(jié)點(diǎn)發(fā)送RREP消息；刪除該請求包，不再往前發(fā)送；}else{if（本節(jié)點(diǎn)ID在RREQ記錄的ID序列中）刪除該請求包，不再往前發(fā)送；else{計(jì)算該節(jié)點(diǎn)RER值if(RERrerlthen)(刪除該請求包，不再往前發(fā)送；}elseif(RERrer2)(尋找替換路徑}else(進(jìn)行路徑信息更新，然后繼續(xù)廣播該請求信息。}}}3.2.4日的節(jié)點(diǎn)的操作日的節(jié)點(diǎn)收到RREQ以后，利用RREQ中的反向路徑信息以單播的方式向源節(jié)點(diǎn)發(fā)送RREP。3.2.5路由維護(hù)階段在無線Adhoc網(wǎng)絡(luò)中由于節(jié)點(diǎn)可以自由移動，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化會導(dǎo)致路由失效，并考慮到節(jié)點(diǎn)剩余能量的變化，一旦源節(jié)點(diǎn)、活動路徑上的中間節(jié)點(diǎn)或日標(biāo)節(jié)點(diǎn)剩余能量不能夠滿足要求，就必須找到一條替換路徑。當(dāng)由于路由中間節(jié)點(diǎn)的剩余能量發(fā)生變化而不能滿足傳輸要求，則需要當(dāng)前節(jié)點(diǎn)向周圍發(fā)送RERRRE分組尋找滿足要求的替代節(jié)點(diǎn)或替代節(jié)點(diǎn)群進(jìn)行替代路由的建立。若周圍節(jié)點(diǎn)中滿足要求的節(jié)點(diǎn)，此時(shí)需要看當(dāng)前節(jié)點(diǎn)剩余能量在和范圍內(nèi)，處于warning域內(nèi)，則可繼續(xù)轉(zhuǎn)發(fā)信息，若節(jié)點(diǎn)剩余能量是處于功能受限的danger域內(nèi)，則此情況被視為等同于路由斷裂情況，發(fā)送RERR分組通知源節(jié)點(diǎn)。可見，LBAODV協(xié)議避免了在網(wǎng)絡(luò)斷鏈情況下總是重新發(fā)起路由發(fā)現(xiàn)帶來的附加開銷和時(shí)延，將業(yè)務(wù)流負(fù)載均衡和網(wǎng)絡(luò)抗毀性進(jìn)行了較好的結(jié)合。4仿真和分析4.1仿真環(huán)境本文使用的模擬工具是由Berkeley大學(xué)開發(fā)的NS2.30，并在NS2.30的基礎(chǔ)上實(shí)現(xiàn)了LBAODV協(xié)議。50個(gè)節(jié)點(diǎn)在一個(gè)500x500的矩形區(qū)域按照randomwaypoint模型移動。仿真的時(shí)間為800秒。MAC層協(xié)議采用的是802.11，詳細(xì)參數(shù)見表2所示。表2LBAODV模擬環(huán)境參數(shù)的設(shè)置區(qū)域大小500x500節(jié)點(diǎn)數(shù)50節(jié)點(diǎn)移動場景由setdest工具來生成場景文件網(wǎng)絡(luò)流量場景由cbrgen工具來生成場景文件傳播模型TwoRayGroundMAC協(xié)議802.11路由協(xié)議LBAODV初始電量500J發(fā)射消耗功率1.33W接收消耗功率0.85W仿真時(shí)間800s4.2性能參數(shù)和仿真結(jié)果為了驗(yàn)證LBAODV協(xié)議的性能，選擇以下仿真參數(shù)：網(wǎng)絡(luò)的發(fā)包成功率(PacketDeliveryFraction:PDF)；節(jié)點(diǎn)的平均能耗(AverageEnergyConsume)；能量不為零的節(jié)點(diǎn)數(shù)目(NumberofNodes)o1、網(wǎng)絡(luò)的發(fā)包成功率(PacketDeliveryFraction:PDF)在仿真過程中，采用了不同的停留時(shí)間為：0s,100,200s,300s,400s,500s,600s,700s,800s。仿真結(jié)果如圖1所示，LBAODV協(xié)議的性能明顯的提高了發(fā)包的成功率，當(dāng)節(jié)點(diǎn)停留時(shí)間比較短的時(shí)候，該協(xié)議性能明顯高于原來的協(xié)議。圖1節(jié)點(diǎn)不同的停留時(shí)間下的發(fā)包成功率2、 節(jié)點(diǎn)的平均能耗(AverageEnergyConsume)圖2為節(jié)點(diǎn)在停留時(shí)間為0秒的情況下的平均耗能的情況，從圖中可以看出，仿真剛開始的100秒，兩個(gè)算法的能量消耗幾乎相同，這是因?yàn)閯傞_始每個(gè)節(jié)點(diǎn)的能量都處于normal狀態(tài)，都進(jìn)行對RREQ消息的處理，但是隨著時(shí)間的推移，兩個(gè)算法的能量消耗差距越來越明顯，到800秒的仿真結(jié)束時(shí)，LBAODV協(xié)議比AODV協(xié)議節(jié)省了將近170焦耳的能量。這是因?yàn)楫?dāng)節(jié)點(diǎn)處于danger狀態(tài)的時(shí)候已經(jīng)不再進(jìn)行處理不屬于源或日的節(jié)點(diǎn)的路徑請求信息。一是節(jié)省了能量，均衡了網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的耗能，延長了節(jié)點(diǎn)的壽命；二是減輕了網(wǎng)絡(luò)負(fù)擔(dān)，增加了網(wǎng)絡(luò)的帶寬利用率。圖2節(jié)點(diǎn)在停留時(shí)間為0秒的情況下的平均耗能3、 能量不為零的節(jié)點(diǎn)數(shù)目(NumberofNodes)圖3整個(gè)網(wǎng)絡(luò)時(shí)間內(nèi)能量不為零的節(jié)點(diǎn)數(shù)日圖3是整個(gè)網(wǎng)絡(luò)時(shí)間內(nèi)能量不為零的節(jié)點(diǎn)數(shù)目情況。從圖中可以看出節(jié)點(diǎn)一直運(yùn)行到400秒的時(shí)候，兩個(gè)協(xié)議下有效的節(jié)點(diǎn)數(shù)日都為總的節(jié)點(diǎn)數(shù)日，但是隨著時(shí)間的推移，AODV協(xié)議由于沒有考慮到節(jié)點(diǎn)剩余能量的情況，所以在高業(yè)務(wù)量的情況下，造成了某些節(jié)點(diǎn)耗能不均衡而過早的電池耗盡，而改進(jìn)的協(xié)議LBAODV協(xié)議性能有了明顯的提高。所以說LBAODV協(xié)議能夠延長移動節(jié)點(diǎn)的壽命，均衡了網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的耗能。5總結(jié)本文在AODV基礎(chǔ)上提出了一種基于負(fù)載均衡的改進(jìn)協(xié)議LBAODV,該協(xié)議綜合考慮了節(jié)點(diǎn)的剩余能量，路徑的延時(shí)和跳數(shù)，通過一種最優(yōu)路徑選擇算法來保護(hù)網(wǎng)絡(luò)中的低能量節(jié)點(diǎn)。它有效地均衡網(wǎng)絡(luò)流量并保護(hù)網(wǎng)絡(luò)中的低能量節(jié)點(diǎn)，避免了網(wǎng)絡(luò)中的節(jié)點(diǎn)電池能量過早耗盡。通過Ns-2仿真與原有的AODV協(xié)議相比較，該算法可提高網(wǎng)絡(luò)的發(fā)包成功率，減少了網(wǎng)絡(luò)的平均耗能情況，并且延長網(wǎng)絡(luò)中的節(jié)點(diǎn)生存時(shí)間。下一步研究的主要工作是如何充分利用該協(xié)議能到的多條路徑，進(jìn)行數(shù)據(jù)的分組傳送。參考文獻(xiàn)[1]IETFMobileAdHocWorkingGroupCharterPerkinsC,RoyerE,“AdhocOnDemandDistanceVectorRouting(AODV),”July2003,RFC3561JohnsonD,MaltzD,“Dynamicsourceroutinginadhocwirelessnetworks,”MobileCompute,1996,pp.153-181PerkinsC,RoyerE,DasS,etal,“PerformancecomparisonoftwoondemandroutingprotocolsforAdhocnetworks,”IEEEPersonalCommunications,2001,8(1),pp.16-28PerkinsDD,HughesHD,OwenCB,“Factorsaffectingtheperformanceofadhocnetworks,”Communications,2002.ICC2002,IEEEInternationalConference,2002,4,pp.2048-2052ZhongXiaofeng,WangYouzheng,MiShunliang,etal,“AnExperimentalPerformanceStudyofWirelessadhocSystemUtilizing802.11aStandardBaseondifferentRoutingProtocols,”AsiaPacificOpticalandWirelessCommunications,October2002PPham,SPerreau,“Multi-pathroutingprotocolwithloadbalancingpolicyinmobileadhocnetwork[A],”4thInternationalWorkshoponMobileandWirelessCommunicationsNetwork[C],2002,pp.48-52LZhang,ZZhao,YShu,etal,“Loadbalancingofmultipathsourceroutinginadhocnetworks[A],”IEEEInternationalConferenceonCommunications