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

1、基于負載平衡的路由協(xié)議的設(shè)計摘要在挪動自組網(wǎng)中，減少挪動節(jié)點電池能量消耗，延長網(wǎng)絡(luò)總的壽命時間，已經(jīng)成為路由協(xié)議性能評價的重要方面。本文提出了一種新的路由選擇度量，它綜合考慮了節(jié)點的剩余能量，途徑的延時和跳數(shù)，試圖通過一種最優(yōu)途徑選擇算法來保護網(wǎng)絡(luò)中的低能量節(jié)點。結(jié)合該度量方式還提出一種路由選擇協(xié)議LBADV(LadBalaningbasedAd-Hn-DeandDistaneVetrRuting)，仿真結(jié)果說明，該協(xié)議可以使節(jié)點能耗與負載的分布更為均勻，相比以前相關(guān)的路由算法有效進步了吞吐量。關(guān)鍵詞Adh網(wǎng)絡(luò)；路由協(xié)議；負載平衡；ADV；能量1引言挪動AdH網(wǎng)絡(luò)(ANET)1是由一組挪動節(jié)點

2、通過自組連接形成的多跳無線網(wǎng)絡(luò)。不同于有線網(wǎng)絡(luò)，它不需要固定的根底設(shè)施。由于其自組織性、快速部署和無須任何固定設(shè)施的特點，ANET有廣泛的應(yīng)用，如戰(zhàn)地指揮控制、緊急災(zāi)難恢復(fù)、礦場操作和研討會信息共享。ANET正作為重要的、有前途的研究領(lǐng)域受到極大關(guān)注。如今按需路由協(xié)議是挪動adh網(wǎng)絡(luò)中應(yīng)用最廣泛的一種路由協(xié)議。作為按需路由協(xié)議代表的ADV2和DSR3都是以最短途徑作為路由選擇的標(biāo)準(zhǔn)，它們在網(wǎng)絡(luò)輕負載情況下表現(xiàn)良好。然而，在高業(yè)務(wù)量的情況下，ADV和DSR的性能都急劇惡化4，局部原因是由于其在途徑選擇時傾向于使用一樣的節(jié)點作為中間節(jié)點，大量的數(shù)據(jù)通過少量節(jié)點傳輸，引起網(wǎng)絡(luò)的阻塞，從而導(dǎo)致較高的分

3、組時延，局部節(jié)點也會過早地電池耗荊許多研究者認識到，當(dāng)網(wǎng)絡(luò)負載較重時，最短途徑并非是ANET中用于途徑選擇的最正確度量5,6。與此同時，網(wǎng)絡(luò)負載平衡正受到越來越多的關(guān)注。ANE網(wǎng)絡(luò)的各個節(jié)點在充當(dāng)終端角色發(fā)送和接收信息的同時，還作為路由中繼節(jié)點轉(zhuǎn)發(fā)信息。由于NANET網(wǎng)絡(luò)特點，路由的選擇會直接影響網(wǎng)絡(luò)吞吐量，端到端時延，終端節(jié)點的能量消耗等參數(shù)。多數(shù)終端節(jié)點都采用有限電源形式，因此剩余能量就作為節(jié)點最珍貴的資源，一旦資源耗盡，終端節(jié)點就無法工作，也無法作為中繼節(jié)點繼續(xù)工作，進而導(dǎo)致整個網(wǎng)絡(luò)無法正常運行。然而，在一些節(jié)點能量耗盡的時候，其它節(jié)點還有過多剩余能量，這就造成了ANET網(wǎng)絡(luò)的能耗不公平

4、性，還有些節(jié)點擔(dān)負著比其它節(jié)點更為重要的作用，一旦能量耗盡會對整個網(wǎng)絡(luò)造成宏大損失。因此，就需要在基于最短途徑路由的常規(guī)路由協(xié)議根底上，更多的考慮網(wǎng)絡(luò)的能量損耗公平性，即負載平衡性能。本文第2節(jié)介紹ANET中負載平衡路由的相關(guān)工作;第3節(jié)描繪路由協(xié)議LBADV，提出一種新的路由選擇度量，它綜合考慮了節(jié)點的剩余能量，途徑的延時和跳數(shù)，試圖通過一種最優(yōu)途徑選擇算法來保護網(wǎng)絡(luò)中的低能量節(jié)點7第4節(jié)給出仿真環(huán)境、性能參數(shù)和仿真結(jié)果；最后提出結(jié)論和進一步的研究工作。2負載平衡路由協(xié)議的研究目前提出的負載平衡路由算法主要有：RPLB(ulti-PathRutingithLadBalaning)7、SR(u

5、lti-PathSureRuting)8、DLAR(DynaiLad-AareRuting)9、LR(LadAareRuting)10、LSR(Lad-SensitivenDeandRuting)11和LBAR(Lad-BalanedAdHRuting)12。這些算法的選路準(zhǔn)那么不再象普通的ANET中的路由算法(如：ADV、DSR等)那樣，以“路由最短作為選路準(zhǔn)那么，而是通過一些可以反映網(wǎng)絡(luò)負載狀態(tài)的信息來作為選擇準(zhǔn)那么。表1從選路準(zhǔn)那么、性能評價、是否需要周期性發(fā)送信息三個方面列出了目前已提出的主要的負載平衡路由算法的特點。由于現(xiàn)有的adh路由協(xié)議缺乏網(wǎng)絡(luò)負載平衡才能，而且沒有考慮網(wǎng)絡(luò)中的每

6、個節(jié)點的壽命，面對大量數(shù)據(jù)業(yè)務(wù)，協(xié)議不能提供令人滿意的性能。針對上述的缺乏之處，本文提出了LBADV協(xié)議是綜合路由的負載平衡，延時和跳數(shù)來選擇最優(yōu)途徑的。改良主要基于以下幾個方面：1當(dāng)中間節(jié)點收到RREQ消息后，首先判斷自己的剩余能量所處的狀態(tài)，進而來判斷是否進展轉(zhuǎn)發(fā)，從而防止了RREQ分組在全網(wǎng)范圍內(nèi)的不必要轉(zhuǎn)發(fā)和某些節(jié)點的失效，減少了網(wǎng)絡(luò)擁塞，進步了系統(tǒng)吞吐量，并且平衡網(wǎng)絡(luò)負載，延長了重負荷節(jié)點的生存時間。2當(dāng)中間節(jié)點或者目的節(jié)點收到來自不同途徑的同一個路由懇求識別碼的路由懇求時，對收到的各懇求分組中包含的途徑信息進展緩存，然后本節(jié)點將從收到的多個來自不同途徑的路由應(yīng)答分組中按照一定的算法

7、綜合考慮路由的負載平衡，延時和跳數(shù)來選擇最優(yōu)途徑進展記錄，以便數(shù)據(jù)分組可以選擇到目的節(jié)點代價最優(yōu)的途徑進展傳輸。表1負載平衡路由算法特點比擬3LBADV協(xié)議描繪3.1三級電池能量閾值保護狀態(tài)考慮到AdH網(wǎng)絡(luò)的節(jié)點能量受限，一旦能量耗盡就不能繼續(xù)工作。而骨干節(jié)點停頓工作后將很容易導(dǎo)致整個網(wǎng)絡(luò)的失效。所以路由選擇應(yīng)該盡量防止使用那些剩余能量少的那些節(jié)點。LBADV協(xié)議按式3-1定義電池剩余能量率RERResidualEnergyRati：3-1此外根據(jù)節(jié)點的剩余能量，每個節(jié)點根據(jù)自身的能量等級對路由懇求做出相應(yīng)的響應(yīng)。本協(xié)議采用了3個能量級別，分別為：Danger，arning，Nral，分別對應(yīng)

8、于rer1，rer2，rer3三級閾值。其中三者順序為：rer1rer2rer3。當(dāng)中間節(jié)點收到RREQ消息后，首先判斷自己的剩余能量所處的狀態(tài)，進而來判斷是否進展轉(zhuǎn)發(fā)該消息。1假設(shè)當(dāng)前節(jié)點的處于Danger狀態(tài)時，該節(jié)點將丟棄所有路由懇求信息，不再進展任何的消息轉(zhuǎn)發(fā)，從而保護了該節(jié)點。它只為自己作為源節(jié)點或者目的節(jié)點的途徑效勞；2假設(shè)當(dāng)前節(jié)點處于arning狀態(tài)時，該節(jié)點將在它的路由表中查找符合條件的交換節(jié)點，并且通知它的上下游節(jié)點實現(xiàn)本地途徑的更新；3假設(shè)當(dāng)前節(jié)點處于Nral狀態(tài)時，在路由懇求RREQ中添加一個字段來記錄所經(jīng)過節(jié)點的最小剩余能量率，以及來記錄RREQ從源節(jié)點發(fā)出到目的節(jié)點的

9、延遲。然后繼續(xù)播送RREQ。3.2LBADV協(xié)議描繪3.2.1路由發(fā)現(xiàn)操作當(dāng)源節(jié)點需要和另一節(jié)點進展通信但沒有到目的節(jié)點的有效路由可使用時，協(xié)議通過對RREQ進展播送的方式發(fā)起路由發(fā)現(xiàn)過程。RREQ消息攜帶有源節(jié)點和目的節(jié)點地址、初始化值為0且每次遞加1的序列號、和源節(jié)點的剩余能量率RER添加到相應(yīng)的域。收到RREQ消息的各中間節(jié)點將對本節(jié)點的剩余能量狀態(tài)進展判斷。剩余能量缺乏而導(dǎo)致功能受限節(jié)點通過丟棄RREQ而防止本節(jié)點成為新途徑的中間節(jié)點，以防止RREQ風(fēng)暴。使產(chǎn)生的路由在避開受限節(jié)點的同時減少了受限節(jié)點轉(zhuǎn)發(fā)RREQ帶來的附加控制開銷。非功能受限狀態(tài)的中間節(jié)點在收到第一個RREQ時，對RR

10、EQ中攜帶的節(jié)點序列號和相應(yīng)途徑的信息進展記錄之后，然后對域進展設(shè)置為原始值和該節(jié)點延遲轉(zhuǎn)發(fā)的時間之和，再將本節(jié)點的剩余能量率RER和該懇求消息中的域中的值進展比擬，假如小于該值，那么把當(dāng)前節(jié)點的剩余能量RER添加到該域中。以實現(xiàn)對RREQ的更新，并將更新后的RREQ再次向目的節(jié)點播送。源節(jié)點和目的節(jié)點地址、序列號一樣的兩個RREQ應(yīng)被認為是同一個RREQ分組。當(dāng)一個中間節(jié)點收到RREP分組時，直接按照RREP中包含的途徑對RREP繼續(xù)進展轉(zhuǎn)發(fā)。另外，當(dāng)中間節(jié)點收到RREP分組時，還會更新本節(jié)點到目的節(jié)點的路由。3.2.2源節(jié)點的操作在ADV協(xié)議中，源節(jié)點只接收第一個到達的RREP報文。在改良

11、的LBADV協(xié)議中，主要做了兩方面的改良。第一：節(jié)點收到數(shù)據(jù)包后不是一律立即轉(zhuǎn)發(fā)，而是按照剩余能量的多少，延遲一個與剩余能量成反比的時間能量越少，延遲時間越長轉(zhuǎn)發(fā)，如3-2式所示。這也是需要綜合考慮負載平衡，延時和跳數(shù)的原因不再是簡單的跳數(shù)越多，延時越長。第二：源節(jié)點收到第一個RREP報文后，啟動延遲器。當(dāng)延時器超時后，源節(jié)點根據(jù)以下策略在所有到達的可選途徑中選擇最優(yōu)途徑。如3-3式所示：3-2其中，為該節(jié)點根據(jù)剩余能量而進展的延遲，RE為剩余能量。3-3其中為最優(yōu)途徑，為該途徑中的最小剩余能量率，為該途徑的總的延遲，為該途徑的總的跳數(shù)，為各個參數(shù)的權(quán)重。在LBADV協(xié)議中采用。3.2.3中間

12、節(jié)點的操作當(dāng)源節(jié)點需要發(fā)送數(shù)據(jù)包且在它的路由表中沒有有效途徑時，就調(diào)用路由發(fā)現(xiàn)過程。源節(jié)點播送一個路由懇求RREQ消息，中間節(jié)點接收到RREQ后，將按照以下步驟執(zhí)行操作。if(路由表中有到目的節(jié)點的途徑)反向向源節(jié)點發(fā)送RREP消息；刪除該懇求包，不再往前發(fā)送；elseif本節(jié)點ID在RREQ記錄的ID序列中刪除該懇求包，不再往前發(fā)送；else計算該節(jié)點RER值if(RERrer1then)刪除該懇求包，不再往前發(fā)送；elseif(RERrer2)尋找交換途徑else進展途徑信息更新，然后繼續(xù)播送該懇求信息。3.2.4目的節(jié)點的操作目的節(jié)點收到RREQ以后，利用RREQ中的反向途徑信息以單播的

13、方式向源節(jié)點發(fā)送RREP。3.2.5路由維護階段在無線Adh網(wǎng)絡(luò)中由于節(jié)點可以自由挪動，網(wǎng)絡(luò)拓撲構(gòu)造的動態(tài)變化會導(dǎo)致路由失效，并考慮到節(jié)點剩余能量的變化，一旦源節(jié)點、活動途徑上的中間節(jié)點或目的節(jié)點剩余能量不可以滿足要求，就必須找到一條交換途徑。當(dāng)由于路由中間節(jié)點的剩余能量發(fā)生變化而不能滿足傳輸要求，那么需要當(dāng)前節(jié)點向周圍發(fā)送RERRRE分組尋找滿足要求的替代節(jié)點或替代節(jié)點群進展替代路由的建立。假設(shè)周圍節(jié)點中滿足要求的節(jié)點，此時需要看當(dāng)前節(jié)點剩余能量在和范圍內(nèi)，處于arning域內(nèi)，那么可繼續(xù)轉(zhuǎn)發(fā)信息，假設(shè)節(jié)點剩余能量是處于功能受限的danger域內(nèi)，那么此情況被視為等同于路由斷裂情況，發(fā)送RE

14、RR分組通知源節(jié)點?？梢?，LBADV協(xié)議防止了在網(wǎng)絡(luò)斷鏈情況下總是重新發(fā)起路由發(fā)現(xiàn)帶來的附加開銷和時延，將業(yè)務(wù)流負載平衡和網(wǎng)絡(luò)抗毀性進展了較好的結(jié)合。4仿真和分析4.1仿真環(huán)境本文使用的模擬工具是由Berkeley大學(xué)開發(fā)的NS2.30，并在NS2.30的根底上實現(xiàn)了LBADV協(xié)議。50個節(jié)點在一個500500的矩形區(qū)域按照randaypint模型挪動。仿真的時間為800秒。A層協(xié)議采用的是802.11，詳細參數(shù)見表2所示。表2LBADV模擬環(huán)境參數(shù)的設(shè)置區(qū)域大小500500節(jié)點數(shù)50節(jié)點挪動場景由setdest工具來生成場景文件網(wǎng)絡(luò)流量場景由brgen工具來生成場景文件傳播模型TRayGru

15、ndA協(xié)議802.11路由協(xié)議LBADV初始電量500J發(fā)射消耗功率1.33接收消耗功率0.85仿真時間800s4.2性能參數(shù)和仿真結(jié)果為了驗證LBADV協(xié)議的性能，選擇以下仿真參數(shù)：網(wǎng)絡(luò)的發(fā)包成功率(PaketDeliveryFratin:PDF)；節(jié)點的平均能耗(AverageEnergynsue)；能量不為零的節(jié)點數(shù)目NuberfNdes。1、網(wǎng)絡(luò)的發(fā)包成功率(PaketDeliveryFratin:PDF)在仿真過程中，采用了不同的停留時間為：0s，100，200s，300s，400s，500s，600s，700s，800s。仿真結(jié)果如圖1所示，LBADV協(xié)議的性能明顯的進步了發(fā)包的成

16、功率，當(dāng)節(jié)點停留時間比擬短的時候，該協(xié)議性能明顯高于原來的協(xié)議。圖1節(jié)點不同的停留時間下的發(fā)包成功率2、節(jié)點的平均能耗(AverageEnergynsue)圖2為節(jié)點在停留時間為0秒的情況下的平均耗能的情況，從圖中可以看出，仿真剛開場的100秒，兩個算法的能量消耗幾乎一樣，這是因為剛開場每個節(jié)點的能量都處于nral狀態(tài)，都進展對RREQ消息的處理，但是隨著時間的推移，兩個算法的能量消耗差距越來越明顯，到800秒的仿真完畢時，LBADV協(xié)議比ADV協(xié)議節(jié)省了將近170焦耳的能量。這是因為當(dāng)節(jié)點處于danger狀態(tài)的時候已經(jīng)不再進展處理不屬于源或目的節(jié)點的途徑懇求信息。一是節(jié)省了能量，平衡了網(wǎng)絡(luò)中

17、每個節(jié)點的耗能，延長了節(jié)點的壽命；二是減輕了網(wǎng)絡(luò)負擔(dān)，增加了網(wǎng)絡(luò)的帶寬利用率。圖2節(jié)點在停留時間為0秒的情況下的平均耗能3、能量不為零的節(jié)點數(shù)目NuberfNdes圖3整個網(wǎng)絡(luò)時間內(nèi)能量不為零的節(jié)點數(shù)目圖3是整個網(wǎng)絡(luò)時間內(nèi)能量不為零的節(jié)點數(shù)目情況。從圖中可以看出節(jié)點一直運行到400秒的時候，兩個協(xié)議下有效的節(jié)點數(shù)目都為總的節(jié)點數(shù)目，但是隨著時間的推移，ADV協(xié)議由于沒有考慮到節(jié)點剩余能量的情況，所以在高業(yè)務(wù)量的情況下，造成了某些節(jié)點耗能不平衡而過早的電池耗盡，而改良的協(xié)議LBADV協(xié)議性能有了明顯的進步。所以說LBADV協(xié)議可以延長挪動節(jié)點的壽命，平衡了網(wǎng)絡(luò)中每個節(jié)點的耗能。5總結(jié)本文在ADV

18、根底上提出了一種基于負載平衡的改良協(xié)議LBADV，該協(xié)議綜合考慮了節(jié)點的剩余能量，途徑的延時和跳數(shù)，通過一種最優(yōu)途徑選擇算法來保護網(wǎng)絡(luò)中的低能量節(jié)點。它有效地平衡網(wǎng)絡(luò)流量并保護網(wǎng)絡(luò)中的低能量節(jié)點，防止了網(wǎng)絡(luò)中的節(jié)點電池能量過早耗荊通過Ns-2仿真與原有的ADV協(xié)議相比擬，該算法可進步網(wǎng)絡(luò)的發(fā)包成功率，減少了網(wǎng)絡(luò)的平均耗能情況，并且延長網(wǎng)絡(luò)中的節(jié)點生存時間。下一步研究的主要工作是如何充分利用該協(xié)議能到的多條途徑，進展數(shù)據(jù)的分組傳送。參考文獻1IETFbileAdHrkingGrupharter2Perkins,RyerE,“AdhnDeandDistaneVetrRuting(ADV),July

19、2022,RF35613JhnsnD,altzD,“Dynaisurerutinginadhirelessnetrks,bilepute,1996,pp.153-1814Perkins,RyerE,DasS,etal,“PerfraneparisnftndeandrutingprtlsfrAdhnetrks,IEEEPersnaluniatins,2001,8(1),pp.16-285PerkinsDD,HughesHD,enB,“Fatrsaffetingtheperfranefadhnetrks,uniatins,2002.I2002,IEEEInternatinalnferene,2002,4,pp.2048-20526ZhngXiafeng,angYuzheng,iShunliang,etal,“AnExperientalPerfraneStudyfirelessadhSysteUtilizing802.11aStandardBasendifferentRutingPrtls,AsiaPaifiptialandirelessuniatins,tber20027PPha,SPerreau,“ulti-pathrutingprtlithladbalaningpliyinbileadhnetr