基于Wardrop均衡的DSR路由協(xié)議研究

郭敏 鄭明春

山東師范大學(xué) 山東 250014

0 引言

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

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

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

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

1 W-DSR路由原理及算法

1.1 Wardrop均衡

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

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

1.2 W-DSR路由描述

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

在W-DSR路由算法中，本文首先假定的條件有：①無線Ad Hoc網(wǎng)絡(luò)移動節(jié)點不能過快；②每個移動節(jié)點采用全向天線，具有相同的傳輸距離，所有鏈?zhǔn)请p向鏈；③存在相鄰節(jié)點尋找協(xié)議。

源節(jié)點在等待路由應(yīng)答的時間里，對收到來自同一個目的節(jié)點的路徑信息進行比較并更新。本文設(shè)定4個參數(shù)，作為最小“代價”的參考標(biāo)準(zhǔn)。以最小“代價”作為 W-DSR路由算法的最小阻抗。

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

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

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

表1 i節(jié)點的路由信息表

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

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

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

2 仿真實驗

2.1 仿真環(huán)境及參數(shù)

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

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

圖1 網(wǎng)絡(luò)拓?fù)鋱D

2.2 數(shù)據(jù)分組端到端時延時間

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

圖2 端到端時延

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

2.3 數(shù)據(jù)分組丟失率

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

圖3 數(shù)據(jù)分組丟失率

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

3 結(jié)論

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

[1]陳林星,曦,曹毅.移動 Ad Hoc網(wǎng)絡(luò)—自組織分組無線網(wǎng)絡(luò)技術(shù)[M].北京:電子工業(yè)出版社.2012.

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

[3]沈奔,秦軍,萬麗.無線Ad Hoc網(wǎng)絡(luò)中AODV路由算法的研究與改進[J].計算機技術(shù)與發(fā)展.2011.

[4]無線 Ad Hoc網(wǎng)絡(luò) DSR路由協(xié)議的優(yōu)化設(shè)計[J].計算機工程.2009.

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

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