基于負載均衡的路由協議的設計

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

關鍵詞Adhoc網絡；路由協議；負載均衡；AODV；能量1引言

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

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

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

本文第2節介紹MANET中負載平衡路由的相關工作;第3節描述路由協議LBAODV，提出一種新的路由選擇度量，它綜合考慮了節點的剩余能量，路徑的延時和跳數，試圖通過一種最優路徑選擇算法來保護網絡中的低能量節點7第4節給出仿真環境、性能參數和仿真結果；最后提出結論和進一步的研究工作。2負載均衡路由協議的研究

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

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

1）當中間節點收到RREQ消息后，首先判斷自己的剩余能量所處的狀態，進而來判斷是否進行轉發，從而防止了RREQ分組在全網范圍內的不必要轉發和某些節點的失效，減少了網絡擁塞，提高了系統吞吐量，并且平衡網絡負載，延長了重負荷節點的生存時間。

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

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

1）若當前節點的處于Danger狀態時，該節點將丟棄所有路由請求信息，不再進行任何的消息轉發，從而保護了該節點。它只為自己作為源節點或者目的節點的路徑服務；

2）若當前節點處于Warning狀態時，該節點將在它的路由表中查找符合條件的替換節點，并且通知它的上下游節點實現本地路徑的更新；

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

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

在AODV協議中，源節點只接收第一個到達的RREP報文。在改進的LBAODV協議中，主要做了兩方面的改進。第一：節點收到數據包后不是一律立即轉發，而是按照剩余能量的多少，延遲一個與剩余能量成反比