基于Wardrop均衡的DSR路由協議研究

郭敏 鄭明春

山東師范大學 山東 250014

0 引言

DSR路由協議最主要的特點是使用“源路由”，所發送的每個數據分組均在其分組頭中攜帶其將要通過的一個完整的、按序排列的節點序列。通過直接使用源路由，發送節點就能夠選擇和控制其發送分組的傳輸路由，支持使用多條路由到達任何同一個目的節點，容易保證所使用的路由是開環路由。

當某個源節點S產生一個新分組需要傳輸給某個目的節點D的時候，S就在該分組的分組頭中添入一條源路由，從而給出沿著該條源路由竹筏該分組到目的節點D的轉發跳序列。源節點S首先搜索其路由存儲器，看是否有合適的源路由，如果有就按照已有的源路由進行分組的傳輸。如果節點S在其路由存儲器中沒有找到任何可用路由，那么節點S初始化路由需求協議來動態的尋找一條新路由到達目的節點 D。并把源節點 S和目的節點D分別稱為該路由尋找的發起節點和目的節點。

在DSR路由協議版本中，源節點在面對多條路由選擇時沒有任何機制來確定優先選擇較新的路由。源節點在搜索其路由存儲器中的路由時，可能會選擇到局部鏈路已經很擁塞的路徑。而這樣的路徑如果被使用的話，則可能造成分組轉發的時延、數據分組丟失增大等問題。路由查找過程中，源節點選擇路徑進行傳輸分組時，接收到的第一條RREP信息后，存儲在源節點的路由存儲器，并立即使用本條路徑進行數據發送。一旦本條路徑只是跳數最小，所以回應RREP信息比較快，但是網絡中的部分節點的流量很大，源節點繼續使用本條路徑轉發數據分組，這樣就容易在流量大的節點附近造成局部擁塞，同樣可能導致時延、數據分組丟失率增大等問題。文獻[3]提出了一種以路徑能量和流量作為參考，控制鏈路上的擁塞問題，但是沒有考慮到單個節點擁塞對整個網絡造成的影響；多數情況下，路徑中的任意一條鏈路的中斷，都可能影響數據的正常的傳輸。文獻[4]在路由查找過程中，考慮了中間節點的隊列長度和隊列增量判斷節點的擁塞狀況，但是在源節點路由緩存器中并沒有考慮已有鏈路的擁塞狀況。文獻[5]是在AODV路由協議基礎上進行擁塞控制的。

本文提出了一種改進的 W-DSR(Wardrop-DSR)路由算法，通過對DSR路由協議進行改進達到Wardrop均衡理論模型的狀態，實現每次選擇路徑傳輸數據分組時是基于最小“代價”進行選擇的。經過多次調整，可以認為數據分組會根據W-DSR路由算法近似均勻的分配到不同的路徑上，使得網絡中所有可以選擇的路徑上的“代價”近似相等。W-DSR路由算法能夠調整網絡上由于 DSR路由協議的源節點在接收到第一條RREP信息后，立即使用這一條路徑發送數據而可能造成的網絡擁塞、數據分組丟失等問題，從而提高了網絡的傳輸效率。仿真結果表明，W-DSR算法在數據分組端到端時延、丟包率和鏈路吞吐量上都有很大的改善，提高了網絡傳輸效率。

1 W-DSR路由原理及算法

1.1 Wardrop均衡

Wardrop均衡理論是由著名交通問題專家 Wardrop于1952年提出來的，是研究交通規劃問題的重要方法，又稱為“用戶平衡(User Equilibrium—UE)條件”。假設每個節點都是“自私”的，當沒有一個節點可以通過改變自己的路徑能夠降低自己的阻抗(時延、鏈路利用率等等)時，就說網絡實現了Wardrop均衡。通俗來說就是保證了每個用戶所要通過的路徑是阻抗最小的，即對單個用戶來說是最優的。假設用戶都是自私的，每個用戶都會選擇對自己來說最優的路徑，經過一段時間的選擇，整個交通網絡就會達到Wardrop均衡，從而可以有效減輕交通網絡阻塞。Wardrop均衡用數學表達式表示如下：

本文借助 Wardrop均衡理論在計算機網絡上進行了嘗試，假設每個路由都是“自私”的，并且都會選擇對自己來說“代價”最小的路徑，經過一段時間的選擇，整個網絡就會達到Wardrop平衡，從而優化計算機網絡上的擁塞問題，仿真實驗證明確實起到了很大的優化效果。

1.2 W-DSR路由描述

根據Wardrop均衡理論，網絡中的所有節點路由都是“自私的”。每個源節點都希望能夠通過網絡以最快的速度、最高的性能發送數據分組到目的節點。W-DSR(Wardrop-DSR)路由算法是通過對DSR路由協議進行改進達到Wardrop均衡模型狀態，促使源節點每次選擇路徑傳輸數據分組時是基于路徑的最小“代價”進行選擇。經過多次調整，可以認為數據分組會根據W-DSR路由算法近似均勻的分配到不同的路徑上，使得網絡中所有可以選擇的路徑上的“代價”近似相等，整個網絡就會達到Wardrop均衡狀態，這樣能夠有效地緩解鏈路的局部擁塞，從而減輕因鏈路擁塞造成的時延和丟包率等問題。

在W-DSR路由算法中，本文首先假定的條件有：①無線Ad Hoc網絡移動節點不能過快；②每個移動節點采用全向天線，具有相同的傳輸距離，所有鏈是雙向鏈；③存在相鄰節點尋找協議。

源節點在等待路由應答的時間里，對收到來自同一個目的節點的路徑信息進行比較并更新。本文設定4個參數，作為最小“代價”的參考標準。以最小“代價”作為 W-DSR路由算法的最小阻抗。

(2) 路徑時延DT，在源路由S存儲器中不存在到達目的節點D的路徑時，發送RREQ消息進行路由查找，找到合適的路徑后，需要返回RREP消息，在RREP消息中添加記錄時延的信息DT，每到下一跳路由時，把從本跳路由到下一跳路由的時延加到DT中，即 DT=DT+ΔDT。選擇時延作為一個參考標準，更能清晰的表示路徑的擁塞程度，如果路徑中有鏈路是擁塞的，所返回RREP消息所用的時間一定是較長的。

(3) 數據分組轉發跳數H，在其他機制相同的情況下，跳數越小，意味著開銷、端到端延遲越小。因此，將跳數作為一個選擇機制。

(4) 源路由S的路由存儲器中路徑存在時間T，在源路由S中設置一個時間標記T，一旦源路由把路徑存儲在路由存儲器中，T開始計時。由于在 DSR路由協議版本中，源節點在面對多條路由選擇時沒有任何機制來確定優先選擇較新的路由。所以本文標記存儲到路由存儲器中的時間，并作為計算最小“代價”的一個標準，這樣無論源路由存儲器中是否存儲合適的路徑來轉發數據分組，W-DSR路由算法都能夠有效的控制最小“代價”(見表1)。

表1 i節點的路由信息表

由以上4個參數，我們得到從目的節點到達本節點的總代價的計算公式：

其中a, b, c, d為預設參數，在模擬試驗時設定合適的值；i為第i條到達同一目的節點的路徑。在節點每次收到RREP信息時首先會判斷是否是源節點，如果不是源節點則在節點的路由信息表中計算并保存總“代價”，如果是源節點收到RREP信息，同樣需要在節點的路由信息表中計算并保存總“代價”，同時源節點需要比較到達同一目的節點的所有路徑的總“代價”，選擇總“代價”最小 min{Wi}的路徑進行數據分組的轉發。

無線Ad Hoc網絡在每個周期內都會進行若干次路徑的重新選擇，各節點總是根據W-DSR路由算法將數據分組發送到路由“代價”最小的路徑上(類似于最小“代價”路由)。將這些小的片段連起來觀察就會發現，隨著鏈路上的帶寬減小、時延增大等情況的發生，鏈路上的“代價”發生變更后，后續的數據分組就可能會回避該路徑，而選擇那些整體“代價”小的路徑進行傳輸。經過多次的調整，可以認為數據流會根據W-DSR路由算法近似均勻的分配到不同的路徑上，從而網絡中所有可以選擇路徑上的總“代價”近似相等。能夠調整網絡上由于 DSR路由協議沒有流量控制造成的擁塞情況，提高網絡的整體傳輸效率。

2 仿真實驗

2.1 仿真環境及參數

在ubuntu10.0環境下，采用NS-2.35仿真平臺來進行仿真，所有試驗編碼采用C++語言TCL腳本語言實現。采用的仿真環境是由 20個無線節點組成的網絡拓撲圖(如圖 1所示)，分布在300m*400m的仿真區域內，仿真時間為100s，暫停時間設為100s。也就是在仿真這段時間里沒有移動，另外設置使用CBR流，每一條數據流每秒送出50個數據包。

在同一仿真場景中，W-DSR算法在數據分組端到端延遲時間、數據分組丟失率兩個性能上跟未修改的DSR協議進行比較。

圖1 網絡拓撲圖

2.2 數據分組端到端時延時間

數據分組端到端延遲時間(End-to-End Delay of Data Packets)：這包含所有可能的延遲時間的總和，如發現路徑的緩沖時間、MAC層的重傳時間、傳遞時間等，用來衡量路由算法時間效率。尤其對于語音通信，延遲過大會嚴重影響通信質量。

圖2 端到端時延

從圖 2中可以看出，隨著時間的推移，兩種協議下端到端延遲都會增大，但是 M-DSR算法端到端的延遲要比DSR協議小些。這是因為M-DSR算法在查找到達目的節點路徑時，選擇“代價”最小的鏈路進行傳輸，避免了由于鏈路擁塞等問題造成的時延增大，必然是要比DSR協議的時延小。

2.3 數據分組丟失率

數據分組丟失率(Data Packet Dropping)：由CBR來源端產生的數據分組不能成功傳送到目的端的數據分組數目與數據分組傳送數據分組的數目的比值，用來衡量路由算法對傳送數據分組的優劣。

圖3 數據分組丟失率

圖3顯示了隨著時間的推移兩種協議下數據分組的丟失率情況。時間越久，鏈路上的擁塞程度越大，兩種協議的數據分組的丟失率都會上升。但是由于W-DSR采用了選擇“代價”最小路由，在一定程度上減輕了鏈路擁塞，數據包送達比例會比DSR情況下有所提高，而且隨著時間增長，優勢趨于明顯。

3 結論

通過對無線Ad Hoc網絡路由協議的深入研究，針對DSR路由協議的不足，本文提出了一種新的W-DSR路由算法。當源節點要發送數據分組到達目的節點時，不論源節點的路由存儲器中是否存在到達目的節點的路徑，W-DSR算法都能夠讓源節點選擇“代價”最小的路徑傳輸，經過一段時間的不斷調整，最終會使得整個網絡能夠滿足Wardrop均衡的條件。利用這一理論，經過一段時間的調整，網絡上的“代價”會近似相等，并近似等于最小“代價”，達到了控制鏈路擁塞的目的，有效的減少了數據分組端到端延時時間以及數據分組的丟失率。仿真結果表明，W-DSR路由算法的傳輸效率得到了很大提高。

[1]陳林星,曦,曹毅.移動 Ad Hoc網絡—自組織分組無線網絡技術[M].北京:電子工業出版社.2012.

[2]于宏毅,陳萬壽.無線移動自組織網[M].北京:人民郵電出版社.2005.

[3]沈奔,秦軍,萬麗.無線Ad Hoc網絡中AODV路由算法的研究與改進[J].計算機技術與發展.2011.

[4]無線 Ad Hoc網絡 DSR路由協議的優化設計[J].計算機工程.2009.

[5]黃海軍.城市交通網絡平衡分析-理論與實踐[M].北京:人民交通出版社.1994.

[6]宋玲,劉勃蘭.NS2中添加路由協議的研究與實現[J].通信和計算機.2006.