基于多徑路由負載均衡的動態源路由協議

摘 要:提出了一種DSR的改進多徑路由協議(LBDSRM)。采用開銷小的綜合鏈路狀態路由判據算法，協議具有鏈路狀態實時監控與適時調整路由功能，在鏈路變化較大的情況下，主動通知有路由冗余的源節點改用或重點使用次選路由;而且協議提出了適時退避算法，解決了多徑任務與單徑任務爭用鏈路時網絡公平性問題。仿真結果表明新協議能有效避免節點擁塞，達到較好的動態負載均衡，實現網絡資源的充分利用。

關鍵詞:負載均衡; 鏈路狀態; 多徑路由; 無線網狀網; 路由判據

中圖法分類號:TP393文獻標志碼:A

文章編號:1001-3695(2010)06-2249-05

doi:10.3969/j.issn.1001-3695.2010.06.072

Load balancing dynamic source routing protocol based on multipath routing

DING Xiong1，2， XIE Kun2

(1.College of Electrical Information Engineering， Hunan International Ecnomics University， Changsha 410205， China;2.School of Computer Communication， Hunan University， Changsha 410006， China)

Abstract: This paper presented a multipath protocol based on the improved DSR (LBDSRM). The protocol used the economical and comprehensive linkstate routing algorithm. This protocol had a function of timely monitoring of linkstate and could adjust it necessarily. In the case of larger changes in the link， the node voluntarily notified the redundant source node to change into or use secondary links. The protocol set forth timely backoff algorithm to solve the fairness of the link competition between the multipath tasks and the singlepath tasks to avoid node congestion and then to realize better dynamic load balancing and the full utilization of network resources.

Key words: load balancing; linkstate; multipath routing; wireless mesh network(WMN); metric

0 引言

無線網狀網(WMN)是一種多跳、具有自組織和自愈合特點的寬帶無線網絡結構，將成為未來無線城域網骨干網的理想組網方式。無線網狀網核心技術是路由協議，主要包括先應式路由協議、反應式路由協議和混合式路由協議三種類型。先應式路由協議，如DSDV[1] 、WRP[2] 、CGSR[3]等，通過不斷地檢測網絡拓撲和鏈路質量的變化，根據變化來更新路由表。反應式路由又稱按需路由，如AODV[4]、DSR[5]、TORA[6]等，其節點不需要維護及時、準確的路由信息，當需要時才查找路由。混合型路由協議結合了兩者優點，如ZRP協議[7]是一個利用分級結構混合使用按需和主動路由策略的路由協議。然而，上述標準路由協議缺乏有效解決負載均衡的機制，使得某些節點承擔的任務會較多(超載)，而另一些節點卻是空閑的(輕載)，并不能充分利用WMN的資源。

多徑路由是一種解決負載平衡的方法。所謂多徑路由就是指一次路由發現的過程后可以發現多條到達目的節點的路由，然后根據需要使用這些路由來傳輸數據，以提高整個網絡資源的利用率。近年來出現的一些多徑路由協議大都是在DSR或是AODV的基礎上改進得到的，如SMR[8]、AOMDV[9]、MSR[10] 、AODVBR[11]、NDM[12]等。

本文提出了一種具有較高負載均衡能力的多徑路由協議。首先，研究了現有的無線WMN路由metric與多徑路由協議解決平衡問題的方法。其次，在DSR協議的基礎上提出基于多徑路由負載均衡的源路由協議(load balancing dynamic source routing protocol based on multipath routing， LBDSRM)。LBDSRM協議采用開銷小的綜合鏈路狀態路由判據算法，并同時使用多徑傳輸數據，有效地解決了網絡動態負載均衡問題，實現網絡資源的充分利用。最后，在網絡仿真工具NS2環境下對LBDSRM、MSR以及DSR協議進行仿真模擬，比較了在相同環境下這幾種路由協議的性能。實驗結果表明，LBDSRM協議在諸多性能上，特別是動態負載均衡問題的處理上較其他協議更具優勢。

1 相關研究現狀

現有多徑路由有兩種基本的使用模式:a)同時使用多條路徑(同時多徑);b)先使用主路徑，當主路徑失效后再使用其替換路徑(替換多徑)。在解決負載平衡問題上，同時多徑模式要優于替換多徑模式。

基于DSR協議的MSR與SMR是典型的同時多徑協議。MSR[10]是DSR的一種多徑擴展，把按需、多徑和源路由結合起來。協議的重點是降低分組發送延遲，提高整個網絡的負載均衡能力。該協議以延遲作為路徑規格的度量，并通過RTT的方式感知路徑的狀態，根據探測結果采用帶權重的循環調度算法，合理地把數據流分攤在多條互相獨立的路徑上，從而達到負載平衡、充分利用網絡資源的目的。SMR[8]也是一種按需路由協議，其采用分流的處理方法，即在兩條特殊的路徑上分配數據包，其中一條是最短路徑，另一條是與最短路徑具有最大獨立性的路徑。這種分流的辦法不但能更有效地利用網絡資源，提高整個網絡的負載均衡能力，而且還可以在傳輸負載很大的情況下，有效地防止網絡擁塞。

在AODV協議的基礎上擴展而來的有AOMDV[9] 、AODVBR[11]、NDM[12]等。AOMDV(按需多路徑距離矢量路由協議)在路由發現過程獲取多條無環且鏈路不相交路徑，它能夠充分利用AODV中已有的路由信息，所以在計算多路徑時只需要增加少量的額外開銷。AODVBR(后備路由協議)在回送路由應答消息過程中引入一些新思想，在不增加控制信息個數的條件下，維護了多條到目的節點的路由。NDM協議中增加了路由請求節點表，用于記錄從源節點s到目的節點d所經過的每個中間節點;NDM的RREP中返回獨立的路由，考慮到路由開銷及復雜度的因素，它一般都根據具體情況選擇路徑條數。

現有的多徑協議都存在一些缺陷，如MSR 的缺點是發包時的處理開銷明顯增加;SMR 存在傳輸RREQ 包過多， 給目的節點帶來額外的數據包排序等問題;AOMDV也存在數據傳輸中經常不能使用最短路徑等問題。所以，對多徑路由協議的優化還有較大的空間。

2 LBDSRM設計

DSR采用源路由方法，源主機確定地知道它有哪些可以到達目標主機的路徑，可以自由地從中選擇合適的路徑來發送數據包，因此，本文基于DSR設計多徑路由負載均衡的動態源路由協議(LBDSRM)。

2.1 負載平衡的metric

WMN路由協議中的路由判據包括跳數、RTT、每跳包對時延、ETT、ETX、 WCETT[13]等。跳數是通過統計鏈路中節點的個數來衡量鏈路質量。RTT(單跳往返時間)是通過測量單播偵測分組的往返時間來衡量鏈路質量。每跳包對時延是通過測量一個節點連續發給鄰居節點兩個數據包之間的時延來分析鏈路狀態。ETX(期望傳輸次數)是通過統計鄰居節點廣播測試分組的丟失率來估算發送單播數據分組的重傳次數。WCETT(加權累計ETT)是結合了整條通路的吞吐量會受控于瓶頸信道的影響與跳數增加對資源的消耗兩種思想來找出加權平均值。

對于以跳數作為判據標準的算法，雖然非常簡單，但是在密集網絡中可能會存在有很多相同跳數的最短路徑，如果在很多最小跳數判據中只是任意選擇路由，這就很可能沒有選到最優鏈路。而采用RTT、每跳包對時延、ETX等算法作為路由選擇標準時，雖然在許多方面比采用跳數作為路由標準有了很大的進步，但是由于它們都是以發送探測數據包的方式來收集鏈路的狀態信息，會給整個網絡系統帶來一定的額外開銷。作為在多信道系統的基礎上使用的WCETT，能夠很好地解決吞吐量、帶寬、跳數、時延等諸多因素的平衡，但仍沒有解決收集鏈路信息開銷大的問題。

在LBDSRM協議中，本文設計了一種開銷小的綜合節點狀態的路由判據(metric)，以提高協議的運行效率。Metric計算基于節點信息采集，包括帶寬、發送數據量、緩存空間等信息。

節點的實時網卡帶寬在一定程度上能夠反映節點的通信鏈路狀況。定義無線路由節點i的實時網卡帶寬為Bi。同時記錄節點i的接收(Ri)和發送(Si)數據的數量，定義無線路由節點i的吞吐性能為Ci=Ri+Si。

數據發送與接收緩沖隊列中的待處理數據包的數量能夠反映節點鏈路的狀態，如:當路由節點i的發送隊列長度與隊列最大長度之比超過60%時，擁塞指數定義為SQi=1;當路由節點i的發送隊列長度與隊列最大長度之比超過80%時，其擁塞指數定義為SQi=2;其他情況下，SQi=0。節點i的接收隊列飽和程度RQi也是如此。

因為路由的計算與最后路由的使用之間有一段時延，路由判據中最好要有對未來一段時間內擁塞趨勢的預判能力，所以在路由判據的計算中引入擁塞預判機制。具體方法是把當前的飽和度總和(包括接收隊列與發送隊列)與前一次統計的飽和度總和作一個對比，并定義一個預判因子Pi與飽和度差值閾值μ，有:

a)當前的飽和度總和>前一次統計的飽和度總和，且差值>μ，那么Pi=1;

b)當前的飽和度總和<前一次統計的飽和度總和，且差值>μ，那么Pi =-1;

c)當前的飽和度總和與前一次統計的飽和度總和差距≤μ，那么Pi=0。

根據上面收集的關于節點的數據，可以定義節點i與其鄰居節點之間的綜合鏈路權重值為Wi，其計算方法為

Wi=CiBi×10」+SQi+RQi+Pi

為了使沒有擁塞節點的鏈路相對于有擁塞節點的鏈路更具優勢，采用一種超限累加的機制來改善這一特殊情況下路由選擇的處理。具體方法是:計算單個節點的權重值時，根據網絡具體情況設置一個擁塞閾值n，當單個節點的權重值超過擁塞閾值時，認為該節點發生擁塞，并用超出部分的數值來衡量擁塞程度，在計算權重值時將超出部分累加到最終的權重值Wi中。改進后節點的權重值計算方法為

a)當Wi> n時，Wi= Wi+(Wi-n );

b)當Wi≤ n時，Wi= Wi。

綜上所述，對于有著k個節點的路徑的權重總值Wp的計算式如下:

Wp=∑ki=1(CiBi×10」+SQi+RQi+Pi)

2.2 負載均衡的多徑路由機制

LBDSRM協議中負載均衡的多徑路由算法的主要思想是:在路由發現過程后，按每條路徑的綜合鏈路總權值大小來按比例分配發送任務，同時使用多條較優路徑發送數據;在發送數據的同時，每個節點實時監控自己狀態，一旦有較大變化及時通知源節點進行必要的調整。算法還使用了適時退避機制，使多徑傳輸任務與只能單徑傳輸任務在發生網絡資源爭用的情況下具有一定的網絡公平性，同時也能有效避免這種情況下瓶頸節點的擁塞。算法較好地實現了網絡動態負載均衡，大大提高了整個網絡資源的利用率。

算法中需要設置多個參數值，經過多次仿真比較，發現在不同網絡環境下算法的最佳配置值有所不同。現以仿真的網絡環境為例進行最佳配置，并描述如下:

設源節點S在路由發現過程中共發現到達目的節點D有K條有效路徑，并按累計的權值大小排列順序，依次為P1，P2，…，PK。

a)當K=1時，只有一條路徑，該路徑P1的任務分配比例為100%。

b)當K=2時，有兩條路徑，設X=(WP2- WP1)/ WP1，有:

當X≤5%時，P1與P2的任務分配比例分別為50%;

當20%>X>5%時，P1的任務分配比例為70%， P2的為30%;

當40%>X≥20%時，P1的任務分配比例為90%， P2的為10%;

當X≥40%時，P1的任務分配比例為100%， P2的為0%。

c)當K=3時，有三條路徑，設X= (WP2- WP1)/ WP1 (先將P2、 P3看成一個整體)，有:

當X≤5%時，P1與P2、P3的任務分配比例分別為50%。

當20%>X>5%時，P1的任務分配比例為70%，P2、P3的為30%。

當40%>X≥20%時，P1的任務分配比例為90%， P2、P3的為10%。

當X≥40%時，P1的任務分配比例為100%， P2、P3的為0%。

對于P2與 P3的任務分配，參照K=2時的算法進行計算分配。

d)當K>3時，選取最佳的前三條路徑，按照K=3時的算法進行計算分配。

當能夠多徑傳輸的任務與只能單徑傳輸的任務在某個節點或某段鏈路上發生爭用的情況下，為了使只有單徑路由的節點在發送數據時具有一定的網絡公平性，節點就啟動適時退避算法，具體描述為:如果節點當前W

為了避免在路由發現過程中產生過多的路由響應，協議還規定了產生路由響應的次數。LBDSRM協議中最多只使用三條路徑，所以路由發現中不需要找到太多的路徑。對于中間節點一個RREQ只能響應一次，而對于目的節點一個RREQ可響應最先到達的三次。這樣即能使源節點獲得較好的多條路徑信息，又不至于導致路由響應泛濫而影響網絡的性能。

多徑路由負載均衡算法的流程如圖1所示。

2.3 LBDSRM協議的工作實例

如圖2所示，當節點S有數據需發送至D時，在路由發現中發現了通往節點D的三條路徑(當前無其他節點爭用)，其表明路徑狀態的綜合鏈路權值分別為路徑1=18、路徑2=24、路徑3=15。根據LBDSRM協議中多徑路由算法三條路徑被分別分配了27%、3%、70%的傳輸任務，主要任務放在了狀態最佳的路徑3上，并開始按此比例在三條路徑上同時發送數據。

如圖3所示，當運行一段時間后節點A需要發送數據至B，其只發現了一條通往目的節點的路徑(與S節點任務使用的路徑3重合)。為了使多徑傳輸任務與只能單徑傳輸任務在發生網絡資源爭用的情況下具有一定的網絡公平性，所以節點A向該路徑上的其他節點發送回避通告，使節點E、F的狀態權值從2變為擁塞極限值6，并通告給節點S，這時節點S的發送任務還未完成，所以它將使用新的鏈路狀態數據重新分配三條路徑的發送任務。新的路徑狀態的綜合鏈路權值分別為路徑1=18、路徑2=24、路徑3=23。根據LBDSRM協議中多徑路由算法三條路徑被分別分配了70%、15%、15%的傳輸任務，主要任務放在了路徑1上。這樣有效地減輕了有爭用節點的路徑3上的發送任務，預留了資源給節點A的單路徑發送任務，避免了這種情況下瓶頸節點的擁塞，更好地實現了網絡動態負載均衡。

2.4 LBDSRM協議的工作過程

2.4.1 路由發現過程

當某個移動節點有信息需要發出而該節點的路由緩存中又沒有所需路由信息時，就發起路由發現過程，使用洪泛方式發送一個RREQ。該RREQ結構包括源節點的地址、目的節點的地址、獨有的序列號、累計的鏈路權值等。每個接收到RREQ的節點首先檢查自己的路由請求表，查看是否需要處理該報文:

a)若該節點的地址已經處于RREQ報文的路由記錄中，節點將丟棄該請求報文不予處理。

b)若路由請求表中不存在RREQ報文中的源節點與請求序列號，則先將節點自己當前的實時鏈路權值累加到RREQ報文中的累計鏈路權值項，然后查看自己是否是RREQ報文中的目的節點。如果是，向源節點發送一個路由應答報文;如果不是，將自己的地址添加到路由請求報文的路徑記錄表中，然后將擴展后的路由請求報文轉發給所有前向鏈路。

c)若路由請求表中存在RREQ報文中的源節點與請求序列號，則表示該節點近期已處理過一個相同的RREQ報文了，節點將檢查自己是否為目的節點:如果是則查看處理次數，超過三次則丟棄該請求報文不予處理，否則向源節點發送一個路由應答報文;如果不是則丟棄該請求報文不予處理。

源節點的一次路由請求可能收到多個返回路由應答，而每個路由應答報文都攜帶一條通往目的節點的有效路徑信息，每條路徑信息不僅包括到達目的節點的詳細路由情況，還包括這條路徑的累計鏈路權值。與DSR不同的是，協議會記錄下所有返回的路徑信息與相對應的累計鏈路權值，以便按不同的累計鏈路權值來實現多徑路由發送數據給目的節點。

2.4.2 路由維護過程

當多條路由信息建立以后，就進入路由維護的過程。路由維護過程主要負責完成以下幾個任務:

a)實時監控與鄰居節點之間鏈路的有效性，并響應處理由拓撲變化可能帶來的路由信息的變化。LBDSRM協議是通過鏈路檢測、被動確認、發送確認分組等有效機制來發現傳輸鏈路發生錯誤的，這時相關節點發出路由錯誤分組報文。通過發送“路由錯誤分組報文和確認”來把路由故障報告給移動節點，報告后各節點應當及時進行路由更新以維護路由的有效性。在該節點恢復之前，網絡暫時將該節點從其他節點的高速緩存中刪除，并取消所有與該節點有連接關系的傳輸路徑。

b)實時監控本節點的鏈路狀態，并適時啟動節點狀態變化報告機制，以實現動態負載均衡。當節點監控到自己的實時鏈路狀態與節點權值記錄表所記錄的并正在使用的歷史記錄權值差距達到鏈路變化通報的閾值f時，表示當前的鏈路狀態與原來的狀態相比產生了較大變化，這時通過向源節點發送路由節點狀態變化通告報文，來通知源節點根據報告的內容有效調整源節點多徑路由的任務比例。多徑路由機制與節點變化報告機制的結合可以有效地降低網絡負載不均的概率。

c)節點實時監控單徑路由與多徑路由的鏈路競爭。節點在檢測到自己是單徑路由任務與多徑路由任務的競爭節點時，根據節點的實時狀態修改其W值并向多徑路由的源節點發送節點狀態變化通告報文，來通知多徑路由的源節點根據報告的內容有效調整其多條路徑的傳輸任務比例，采用這樣的適時退避機制，來使多徑路由任務預先適度地避開使用這條競爭路徑，以減少擁塞發生的可能性，提高系統整體的性能，達到負載均衡的目的。

3 協議仿真與分析

3.1 仿真環境與參數設置

在仿真參數選擇時，盡量使用系統的缺省設置，如802.11的基本數據帶寬為2 Mbit。在包大小的選擇上，使用了CBR業務發生器，該發生器所產生的包大小即為512 Byte。每個路由協議采用相同的仿真場景，在600 m×600 m網絡中隨機布置50個節點，每個節點具有相同的節點移動模型，節點移動速度設置在20 m/s內隨機均勻分布，節點停頓的時間分別取0、10、20、40、100 s進行五次仿真。在改進的路由協議參數配置時，根據多次試驗數據得到的結果選取了較好的設置參數，如擁塞閾值n取值設置為6，飽和度差值閾值μ為0.05， 鏈路變化通報的閾值f取值為0.2，其余參數都使用前文描述的值。

3.2 仿真結果與分析

在設置好的NS2環境下對LBDSRM、DSR與MSR協議進行了仿真模擬，得到了平均端到端延遲和歸一化路由開銷的數據，并對仿真結果進行了分析。平均端到端時延是衡量最優負載均衡路由算法最重要的指標。歸一化路由開銷是指目的節點每成功接收一個數據包所需要的路由管理包的數量，可用總的路由開銷/目的節點接收到的數據包×100%來表示。歸一化路由開銷是衡量路由協議效率的主要技術指標。仿真中使用的源節點個數分別是10和30。節點停頓時間為0(非常高的移動性)、10、20、40、100 s，數據包發送的速率為4 packets/s。實驗的數據結果如圖4、5所示。

從圖4的數據可以看出，不論是在10個源節點(輕載)還是30個源節點(重載)的環境下，采用多徑路由機制的LBDSRM與MSR都比DSR協議的平均端到端時延要短，這說明多徑路由機制能有效地分流網絡負載，避免節點擁塞，較好地實現了網絡負載均衡。LBDSRM協議的端到端時延更低于MSR，特別是在30個源節點環境下尤為明顯，這主要是因為LBDSRM在路由判據選擇的標準中有考慮到鏈路的狀態和節

點的隊列飽和程度，還引入了預判因子與超限累加機制，并且有解決單徑路由任務與多徑路由任務爭用鏈路的退避策略，所以使其較MSR協議更能有效地避開實際較為擁塞的路徑，避免節點擁塞，達到較高的動態負載均衡效果，從而有效避免了因節點過載而造成的丟包、隊列緩沖、重傳等導致的延遲增加。隨著停留時間的增大，這幾個協議的端到端時延都有所下降，這是因為停留時間增加后節點的移動性減弱，使得路由維護開銷降低，從而減少了因路由不可達而造成的丟包和頻繁的路由發現所導致的延遲。

從圖5中可看出，MSR的開銷要比LBDSRM與DSR協議大得多。這主要是因為MSR協議是通過測量單播偵測分組的往返時間來衡量鏈路質量，這就意味著需要發送大量的探測數據包，所以其開銷一直保持在一個較高的水平。而LBDSRM與DSR不需要額外發送探測數據包，所以開銷較小。從圖中總體來看， LBDSRM比DSR還是具有優勢，主要是因為LBDSRM采用多徑路由機制，使其因鏈路中斷而重新發起路由發現的幾率大大降低，所以開銷相對較少。但在網絡變化較快時，LBDSRM協議中的變化通告機制會引起較多的變化通告報文的發送，所以在這種特殊情況下其開銷有可能高于DSR協議，在圖中也印證了這點。

4 結束語

提出的LBDSRM協議使用了帶有預判因子、超限累加等機制的綜合鏈路狀態路由判據，采用融入了適時退避、限定徑數、按質配量的多徑路由技術，從而較好地實現了整個網絡的動態負載均衡，有效地避免了節點的擁塞，提高了整個網絡的性能，而且相對開銷小、效率高。LBDSRM比MSR與DSR更具有優勢，特別在網絡負載越重的環境下優勢越明顯。這是對未來無線網絡的發展與普及的有益探索。

參考文獻:

[1]PERKINS C E， BHAGWAT P. Highly dynamic destinationsequenced distancevector(DSDV) routing for mobile computers[C]//Proc ofACM SIGCOMM’94. New York: ACM Press，1994:234-244.

[2]MURTHY S， GARCIALUNAACEVES. An efficient routing protocol for wireless networks[J].Mobile Networks and Applications，1996，1(2): 183-197.

[3]蘇靜，郭偉. 無線移動自組織網路由協議綜述[J].中國測試技術，2005，35(2):91-93.

[4]PERKINS C， ROYER E， DAS S. Ad hoc on demand distance vector (AODV) routing[R] . Fremont， California: The Internet Engineering Task Force，2002.

[5]JOHNSON D， HU Y， MALTZ D. RFC 4728， The dynamic source routing protocol(DSR)for mobile Ad hoc networks for IPv4[S/OL]. (2007-02-02). http://tools.ietf.org/html/rfc4728.

[6]PARK V， CORSON S. Temporallyordered routing algorithm(TORA)version 1 functional specification[EB/OL]. (2001-07-20). http://tools.ietf.org/id/draftietfmanettoraspec-04.txt.

[7]HAAS Z J. A new routing protocol for the reconfigurable wireless networks[C]//Proc of IEEE ICUPC’97 .[S.l.]: IEEE，1997:562-566.

[8]LEE S J， GERLA M. Split multipath routing with maximally disjoint paths in Ad hoc network[C]//Proc of IEEE ICC.2001:3201-3205.

[9]MARINA M K， DAS S R. Ondemand multipath distance vector routing in Ad hoc networks[C]//Proc of IEEE ICNP. Washington DC: IEEE Computer Society，2001:14-23.

[10]WANG Lei， ZHANG Lianfang， SHU Yantai， et al. Multipath source routing in wireless Ad hoc networks[C]//IEEE Canadian Conference on Electrical and Computer Engineering. Halifax: IEEE，2000: 479-483.

[11]LEE S J， GERLA M. AODVBR backup routing in Ad hoc networks[C]//Proc of IEEE WCNC. Chicago: IEEE，2000:1311-1316.

[12]孫磊，葛臨東. 一種節點獨立的MANET 網絡多徑路由協議[J]. 計算機工程與應用，2005，41(3):159-161.

[13]DRAVES R， PADHYE J， ZILL B. Routing in multiradio， multihop wireless mesh networks[C]//Proc of ACM Annual Int’l Conference on Mobile Comp and Net(MOBICOM). New York: ACM Press，2004:114-128.