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

1、基于負載均衡的路由協(xié)議的設計          摘  要  在移動自組網中，減少移動節(jié)點電池能量消耗，延長網絡總的壽命時間，已經成為路由協(xié)議性能評價的重要方面。本文提出了一種新的路由選擇度量，它綜合考慮了節(jié)點的剩余能量，路徑的延時和跳數(shù)，試圖通過一種最優(yōu)路徑選擇算法來保護網絡中的低能量節(jié)點。結合該度量方式還提出一種路由選擇協(xié)議LBAODV (Load Balancing based Ad-Hoc On-Demand Distance Vector Routing) ，仿真結果表明，該協(xié)

2、議能夠使節(jié)點能耗與負載的分布更為均勻，相比以前相關的路由算法有效提高了吞吐量。   關鍵詞 Ad hoc 網絡；路由協(xié)議；負載均衡；AODV；能量 1  引言   移動Ad Hoc網絡(MANET) 1 是由一組移動節(jié)點通過自組連接形成的多跳無線網絡。不同于有線網絡，它不需要固定的基礎設施。由于其自組織性、快速部署和無須任何固定設施的特點，MANET 有廣泛的應用，如戰(zhàn)地指揮控制、緊急災難恢復、礦場操作和研討會信息共享。MANET 正作為重要的、有前途的研究領域受到極大關注。   如今按需路由協(xié)議是移動ad hoc

3、 網絡中應用最廣泛的一種路由協(xié)議。作為按需路由協(xié)議代表的AODV2 和DSR3 都是以最短路徑作為路由選擇的標準，它們在網絡輕負載情況下表現(xiàn)良好。然而，在高業(yè)務量的情況下，AODV和DSR 的性能都急劇惡化4 ，部分原因是由于其在路徑選擇時傾向于使用相同的節(jié)點作為中間節(jié)點，大量的數(shù)據(jù)通過少量節(jié)點傳輸，引起網絡的阻塞，從而導致較高的分組時延，部分節(jié)點也會過早地電池耗盡。許多研究者認識到，當網絡負載較重時，最短路徑并非是MANET 中用于路徑選擇的最佳度量5 ,6 。   與此同時，網絡負載平衡正受到越來越多的關注。MANE網絡的各個節(jié)點在充當終端角色發(fā)送和接收信息的同時，還作

4、為路由中繼節(jié)點轉發(fā)信息。由于MNANET網絡特點，路由的選擇會直接影響網絡吞吐量，端到端時延，終端節(jié)點的能量消耗等參數(shù)。多數(shù)終端節(jié)點都采用有限電源模式，因此剩余能量就作為節(jié)點最寶貴的資源，一旦資源耗盡，終端節(jié)點就無法工作，也無法作為中繼節(jié)點繼續(xù)工作，進而導致整個網絡無法正常運行。然而，在一些節(jié)點能量耗盡的時候，其它節(jié)點還有過多剩余能量，這就造成了MANET網絡的能耗不公平性，還有些節(jié)點擔負著比其它節(jié)點更為重要的作用，一旦能量耗盡會對整個網絡造成巨大損失。因此，就需要在基于最短路徑路由的常規(guī)路由協(xié)議基礎上，更多的考慮網絡的能量損耗公平性，即負載均衡性能。   本文第2節(jié)介紹M

5、ANET 中負載平衡路由的相關工作;第3節(jié)描述路由協(xié)議LBAODV，提出一種新的路由選擇度量，它綜合考慮了節(jié)點的剩余能量，路徑的延時和跳數(shù)，試圖通過一種最優(yōu)路徑選擇算法來保護網絡中的低能量節(jié)點7第4節(jié)給出仿真環(huán)境、性能參數(shù)和仿真結果；最后提出結論和進一步的研究工作。2  負載均衡路由協(xié)議的研究   目前提出的負載均衡路由算法主要有：MRP LB (Multi - Path Routing with Load Balancing) 7 、MSR(Multi - Path Source Routing) 8 、DLAR (Dynamic Load- Aware Rou

6、ting) 9 、LWR (Load Aware Routing) 10 、LSR(Load - Sensitive on Demand Routing) 11 和LBAR(Load - Balanced Ad Hoc Routing) 12 。這些算法的選路準則不再象普通的MANET 中的路由算法(如：AODV、DSR 等) 那樣，以“路由最短”作為選路準則，而是通過一些能夠反映網絡負載狀態(tài)的信息來作為選擇準則。表1 從選路準則、性能評價、是否需要周期性發(fā)送信息三個方面列出了目前已提出的主要的負載均衡路由算法的特點。   由于現(xiàn)有的ad hoc 路由協(xié)議缺乏網絡負載平衡能

7、力，而且沒有考慮網絡中的每個節(jié)點的壽命，面對大量數(shù)據(jù)業(yè)務，協(xié)議不能提供令人滿意的性能。針對上述的不足之處，本文提出了LBAODV協(xié)議是綜合路由的負載均衡，延時和跳數(shù)來選擇最優(yōu)路徑的。改進主要基于以下幾個方面：   1）當中間節(jié)點收到RREQ消息后，首先判斷自己的剩余能量所處的狀態(tài)，進而來判斷是否進行轉發(fā)，從而防止了RREQ分組在全網范圍內的不必要轉發(fā)和某些節(jié)點的失效，減少了網絡擁塞，提高了系統(tǒng)吞吐量，并且平衡網絡負載，延長了重負荷節(jié)點的生存時間。   2）當中間節(jié)點（或者目的節(jié)點）收到來自不同路徑的同一個路由請求識別碼的路由請求時，對收到的各請求分組中包

8、含的路徑信息進行緩存，然后本節(jié)點將從收到的多個來自不同路徑的路由應答分組中按照一定的算法綜合考慮路由的負載均衡，延時和跳數(shù)來選擇最優(yōu)路徑進行記錄，以便數(shù)據(jù)分組可以選擇到目的節(jié)點代價最優(yōu)的路徑進行傳輸。表1  負載均衡路由算法特點比較3  LBAODV協(xié)議描述3.1  三級電池能量閾值保護狀態(tài)   考慮到Ad Hoc 網絡的節(jié)點能量受限，一旦能量耗盡就不能繼續(xù)工作。而骨干節(jié)點停止工作后將很容易導致整個網絡的失效。所以路由選擇應該盡量避免使用那些剩余能量少的那些節(jié)點。LBAODV協(xié)議按式（3-1）定義電池剩余能量率RER（Residual Ener

9、gy Ratio）   （3-1）   此外根據(jù)節(jié)點的剩余能量，每個節(jié)點根據(jù)自身的能量等級對路由請求做出相應的響應。本協(xié)議采用了3個能量級別，分別為：Danger，Warning ，Normal，分別對應于rer1，rer2，rer3三級閾值。其中三者順序為：rer1rer2rer3。當中間節(jié)點收到RREQ消息后，首先判斷自己的剩余能量所處的狀態(tài)，進而來判斷是否進行轉發(fā)該消息。   1）若當前節(jié)點的處于Danger狀態(tài)時，該節(jié)點將丟棄所有路由請求信息，不再進行任何的消息轉發(fā)，從而保護了該節(jié)點。它只為自己作為源節(jié)點或者目的節(jié)點

10、的路徑服務；   2）若當前節(jié)點處于Warning狀態(tài)時，該節(jié)點將在它的路由表中查找符合條件的替換節(jié)點，并且通知它的上下游節(jié)點實現(xiàn)本地路徑的更新；   3）若當前節(jié)點處于Normal狀態(tài)時，在路由請求RREQ中添加一個字段 來記錄所經過節(jié)點的最小剩余能量率，以及 來記錄RREQ從源節(jié)點發(fā)出到目的節(jié)點的延遲。然后繼續(xù)廣播RREQ。3.2  LBAODV協(xié)議描述3.2.1  路由發(fā)現(xiàn)操作   當源節(jié)點需要和另一節(jié)點進行通信但沒有到目的節(jié)點的有效路由可使用時，協(xié)議通過對 RREQ 進行廣播的方式發(fā)起路由發(fā)現(xiàn)過程。RREQ

11、 消息攜帶有源節(jié)點和目的節(jié)點地址、初始化值為 0 且每次遞加 1 的序列號、和源節(jié)點的剩余能量率RER添加到相應的域。收到 RREQ 消息的各中間節(jié)點將對本節(jié)點的剩余能量狀態(tài)進行判斷。剩余能量不足而導致功能受限節(jié)點通過丟棄 RREQ 而防止本節(jié)點成為新路徑的中間節(jié)點，以避免RREQ風暴。使產生的路由在避開受限節(jié)點的同時減少了受限節(jié)點轉發(fā) RREQ 帶來的附加控制開銷。非功能受限狀態(tài)的中間節(jié)點在收到第一個 RREQ 時，對 RREQ 中攜帶的節(jié)點序列號和相應路徑的信息進行記錄之后，然后對 域進行設置為原始值和該節(jié)點延遲轉發(fā)的時間 之和，再將本節(jié)點的剩余能量率RER和該請求消息中的 域中的值進行比

12、較，如果小于該值，則把當前節(jié)點的剩余能量RER添加到該域中。以實現(xiàn)對 RREQ 的更新，并將更新后的RREQ 再次向目的節(jié)點廣播。源節(jié)點和目的節(jié)點地址、序列號相同的兩個RREQ 應被認為是同一個 RREQ 分組。當一個中間節(jié)點收到 RREP 分組時，直接按照 RREP 中包含的路徑對RREP 繼續(xù)進行轉發(fā)。另外，當中間節(jié)點收到 RREP 分組時，還會更新本節(jié)點到目的節(jié)點的路由。3.2.2  源節(jié)點的操作   在 AODV協(xié)議中，源節(jié)點只接收第一個到達的 RREP 報文。在改進的 LBAODV 協(xié)議中，主要做了兩方面的改進。第一：節(jié)點收到數(shù)據(jù)包后不是一律立即轉發(fā)，而

13、是按照剩余能量的多少，延遲一個與剩余能量成反比的時間 （能量越少，延遲時間越長）轉發(fā)，如（3-2）式所示。這也是需要綜合考慮負載均衡，延時和跳數(shù)的原因（不再是簡單的跳數(shù)越多，延時越長）。第二：源節(jié)點收到第一個 RREP 報文后，啟動延遲器。當延時器超時后，源節(jié)點根據(jù)以下策略在所有到達的可選路徑中選擇最優(yōu)路徑。如（3-3）式所示     （3-2）   其中， 為該節(jié)點根據(jù)剩余能量而進行的延遲， RE 為剩余能量。  （3-3）   其中 為最優(yōu)路徑， 為該路徑中的最小剩余能量率， 為該路徑的總的延遲， 為

14、該路徑的總的跳數(shù)， 為各個參數(shù)的權重。在LBAODV協(xié)議中采用 。3.2.3  中間節(jié)點的操作   當源節(jié)點需要發(fā)送數(shù)據(jù)包且在它的路由表中沒有有效路徑時，就調用路由發(fā)現(xiàn)過程。源節(jié)點廣播一個路由請求（RREQ）消息，中間節(jié)點接收到（RREQ）后，將按照下列步驟執(zhí)行操作。if  (路由表中有到目標節(jié)點的路徑)      反向向源節(jié)點發(fā)送RREP消息；    刪除該請求包，不再往前發(fā)送；      else    

15、0; if （本節(jié)點ID在RREQ記錄的ID序列中）        刪除該請求包，不再往前發(fā)送；     else          計算該節(jié)點RER值         if  (RERrer1 then)           &

16、#160; 刪除該請求包，不再往前發(fā)送；                  else if  (RERrer2)             尋找替換路徑               

17、   else            進行路徑信息更新，然后繼續(xù)廣播該請求信息。                           3.2.4  目的節(jié)點的操作   目的節(jié)點收到 RREQ 以后，利用 RRE

18、Q 中的反向路徑信息以單播的方式向源節(jié)點發(fā)送 RREP。3.2.5  路由維護階段   在無線Ad hoc網絡中由于節(jié)點可以自由移動，網絡拓撲結構的動態(tài)變化會導致路由失效，并考慮到節(jié)點剩余能量的變化，一旦源節(jié)點、活動路徑上的中間節(jié)點或目標節(jié)點剩余能量不能夠滿足要求，就必須找到一條替換路徑。當由于路由中間節(jié)點的剩余能量發(fā)生變化而不能滿足傳輸要求，則需要當前節(jié)點向周圍發(fā)送 RERRRE 分組尋找滿足要求的替代節(jié)點或替代節(jié)點群進行替代路由的建立。若周圍節(jié)點中滿足要求的節(jié)點，此時需要看當前節(jié)點剩余能量在和范圍內，處于 warning 域內，則可繼續(xù)轉發(fā)信息，若節(jié)點剩余能量

19、是處于功能受限的 danger 域內，則此情況被視為等同于路由斷裂情況，發(fā)送RERR分組通知源節(jié)點。            可見，LBAODV 協(xié)議避免了在網絡斷鏈情況下總是重新發(fā)起路由發(fā)現(xiàn)帶來的附加開銷和時延，將業(yè)務流負載均衡和網絡抗毀性進行了較好的結合。4 仿真和分析4.1 仿真環(huán)境   本文使用的模擬工具是由Berkeley 大學開發(fā)的NS2.30 ，并在NS2.30的基礎上實現(xiàn)了LBAODV協(xié)議。50個節(jié)點在一個500×500的矩形區(qū)域按照random wa

20、ypoint 模型移動。仿真的時間為800秒。MAC層協(xié)議采用的是802.11，詳細參數(shù)見表2所示。表2 LBAODV模擬環(huán)境參數(shù)的設置區(qū)域大小500×500節(jié)點數(shù)50節(jié)點移動場景由setdest工具來生成場景文件網絡流量場景由cbrgen工具來生成場景文件傳播模型TwoRayGroundMAC協(xié)議802.11路由協(xié)議LBAODV初始電量500J發(fā)射消耗功率1.33W接收消耗功率0.85W仿真時間800s4.2 性能參數(shù)和仿真結果   為了驗證LBAODV協(xié)議的性能，選擇以下仿真參數(shù)：網絡的發(fā)包成功率(Packet Delivery Fraction :PDF)；

21、節(jié)點的平均能耗 (Average Energy Consume)；能量不為零的節(jié)點數(shù)目（Number of Nodes）。   1、網絡的發(fā)包成功率(Packet Delivery Fraction :PDF)   在仿真過程中，采用了不同的停留時間為：0s，100，200s，300s，400s，500s，600s，700s，800s。仿真結果如圖1所示，LBAODV協(xié)議的性能明顯的提高了發(fā)包的成功率，當節(jié)點停留時間比較短的時候，該協(xié)議性能明顯高于原來的協(xié)議。 圖1 節(jié)點不同的停留時間下的發(fā)包成功率   2、節(jié)點的平均能耗(Avera

22、ge Energy Consume)   圖2為節(jié)點在停留時間為0秒的情況下的平均耗能的情況，從圖中可以看出，仿真剛開始的100秒，兩個算法的能量消耗幾乎相同，這是因為剛開始每個節(jié)點的能量都處于normal狀態(tài)，都進行對RREQ消息的處理，但是隨著時間的推移，兩個算法的能量消耗差距越來越明顯，到800秒的仿真結束時，LBAODV協(xié)議比AODV協(xié)議節(jié)省了將近170焦耳的能量。這是因為當節(jié)點處于danger狀態(tài)的時候已經不再進行處理不屬于源或目的節(jié)點的路徑請求信息。一是節(jié)省了能量，均衡了網絡中每個節(jié)點的耗能，延長了節(jié)點的壽命；二是減輕了網絡負擔，增加了網絡的帶寬利用率。 圖2

23、節(jié)點在停留時間為0秒的情況下的平均耗能   3、能量不為零的節(jié)點數(shù)目（Number of Nodes） 圖3  整個網絡時間內能量不為零的節(jié)點數(shù)目   圖3是整個網絡時間內能量不為零的節(jié)點數(shù)目情況。從圖中可以看出節(jié)點一直運行到400秒的時候，兩個協(xié)議下有效的節(jié)點數(shù)目都為總的節(jié)點數(shù)目，但是隨著時間的推移，AODV協(xié)議由于沒有考慮到節(jié)點剩余能量的情況，所以在高業(yè)務量的情況下，造成了某些節(jié)點耗能不均衡而過早的電池耗盡，而改進的協(xié)議LBAODV協(xié)議性能有了明顯的提高。所以說LBAODV協(xié)議能夠延長移動節(jié)點的壽命，均衡了網絡中每個節(jié)點的耗能。5 

24、; 總結   本文在AODV 基礎上提出了一種基于負載均衡的改進協(xié)議LBAODV，該協(xié)議綜合考慮了節(jié)點的剩余能量，路徑的延時和跳數(shù)，通過一種最優(yōu)路徑選擇算法來保護網絡中的低能量節(jié)點。它有效地均衡網絡流量并保護網絡中的低能量節(jié)點，避免了網絡中的節(jié)點電池能量過早耗盡。通過Ns-2仿真與原有的AODV協(xié)議相比較，該算法可提高網絡的發(fā)包成功率，減少了網絡的平均耗能情況，并且延長網絡中的節(jié)點生存時間。下一步研究的主要工作是如何充分利用該協(xié)議能到的多條路徑，進行數(shù)據(jù)的分組傳送。參考文獻   1 IETF Mobile Ad Hoc Working Group Cha

25、rter   Perkins C, Royer E, “Ad hoc On Demand Distance Vector Routing (AODV),” July 2003, RFC 3561   Johnson D, Maltz D, “Dynamic source routing in ad hoc wireless networks,” Mobile Compute, 1996, pp.153-181   Perkins C, Royer E, Das S ,et al , “Performance comparison of

26、 two on demand routing protocols for Ad hoc networks,” IEEE Personal Communications, 2001, 8 (1) , pp.16-28   Perkins D D, Hughes H D, Owen C B, “Factors affecting t he performance of ad hoc networks,” Communications , 2002. ICC 2002, IEEE International Conference, 2002, 4, pp.2048-2052   Zhong Xiaofeng, Wang Youzheng, Mi Shunliang, et al, “An Experimental Performance Study of Wireless ad hoc System Utilizing 8