基于備份路由的ＤＳＲ協議改進
2008-12-31 00:00:00楊琳蘋徐家良唐紅
計算機應用研究 2008年12期
(1重慶郵電大學移動通信技術重點實驗室，重慶 400065； 2.重慶三峽學院a.網絡信息中心; b.數學與計算機科學學院，重慶404000)
摘 要：
在按需路由協議DSR基礎上，選擇最少相交點路由，綜合考慮帶寬、延遲因素提出了DSRBACKUP路由協議。通過選取一條符合最低要求的較優路由作為備份，以此來減輕振蕩對QoS保障造成的影響。經仿真分析，DSRBACKUP路由協議在合適的路由開銷下，提高了QoS數據流性能的穩定性，達到預期效果。
關鍵詞：移動自組織網絡； 備份路由； 動態源路由； 仿真； 服務質量
中圖分類號：TP393.03 文獻標志碼：A
文章編號：10013695(2008)12375302
Improvement of DSR based on backup routing
YANG Linping1， 2a， XU Jialiang2b， TANG Hong1
(1. Key Laboratory of Mobile Communications Technology， Chongqing University of Posts Telecommunications， Chongqing 400065， China; 2. a.Network Information Center， b. College of Mathematics Computer Science， Chongqing Three Gorges University， Chongqing 404000， China)
Abstract:This paper proposed animprovement versionof routingbased on DSR——DSRBACKUP， which considered the least disjoint noderouting withbandwidth and delay as metric. By selectingof optimum backup routing， DSRBACKUP could alleviatethe faultfrom performance vibration. Simulations demonstratethat DSRBACKUP can improve performance stability and achieve prospective effect with appropriate overhead.
Key words：MANET; backup routing; DSR; simulation; QoS
在移動自組織網絡（MANET）[1]中提供QoS保障是為不同種類的業務（如語音、視頻、郵件等）提供適合的資源，即所謂的區分服務。通常根據數據流的不同種類，在帶寬、延遲等方面的不同要求，結合控制協議和資源管理機制共同完成QoS的保證，即QoS模型。INSIGNIA[2]是一種分布式、基于流的QoS模型，包含數據調度、包轉發、路由、準入控制等模塊。對于MANET網絡，節點位置動態變化的特性使得如何提高對網絡拓撲變化的適應性，提供有保證的QoS具有很重要的意義。在仿真實驗中發現，INSIGNIA模型中超過一半的數據分組由于中間節點的網絡資源缺乏，數據流鏈路中斷，無法快速地恢復鏈路，造成不穩定的QoS服務，其主要原因是路由協議的影響。如果考慮帶QoS約束的有備份路由協議或多路徑的路由協議協助INSIGNIA QoS模型進行快速恢復，那么QoS的穩定性會得到提高。
1 相關研究
動態源路由（DSR）協議[3]是一個專門為多跳無線Ad hoc網絡設計的簡單且高效的路由協議，提供快速的按需路由服務，適合節點移動或網絡拓撲動態變化的環境。DSR中一般采用雙層路由緩存器的方式提供更高的選路由命中率：主路由緩存器中存儲由路由應答返回的路由；第二路由緩存器保存的是通過學習的方式（如轉發數據、網絡偵聽）獲取的。當尋找路由時首先到主路由緩存器中，然后去第二路由緩存器。但是兩個路由緩存器不存在相互備份的關系，所以無法提供備份路由。
文獻[4]提出了對DSR改進的一種備份源路由協議（BSR）。BSR的特點是減少路由發現洪泛的頻率，而洪泛是按需路由所占的主要花費。備份路由是在主要路由中斷后即時啟用的。其選擇備份路由的方式是考慮路由穩定性。BSR備份路由的選擇是基于實驗性質的估計。
文獻[5]提出了基于DSR協議的多路徑改進方案：分離多徑路由（SMR）。SMR主要是建立最大不相交路徑的多條路由。其中，主路由是最短時延路徑，而其他路由是選取與主路由有最大不相交路徑的路由。數據傳輸被分散在各條路由上進行，以避免節點擁塞，高效地利用網絡資源。但是多徑的路由協議被證明[6]，當路徑達到兩條以上時，控制開銷會降低性能甚至超過所獲取的性能優勢，而且在多條路由上進行負載均衡管理復雜，得不償失。所以選擇一條帶QoS約束的備份路由協議是能夠在性能和開銷方面取得最佳平衡的一種方式。路由的QoS約束條件主要是延遲和帶寬。在INSIGNIA QoS模型中，通過建立帶備份的QoS路由機制，完成合適的帶寬預留，提供QoS數據流的快速自適應，當網絡關鍵節點發生服務質量下降甚至故障時，能夠快速地調整到備份路由并重新建立新的最合適的QoS路由。
2 DSRBACKUP的設計
本文提出一種基于DSR的改進，即DSRBACKUP。考慮路由的帶寬和時延選取與主路由具有最少相交節點的一條端到端的備份路由，利用備份路由應對網絡節點移動產生的性能波動，提供QoS保證。最少相交節點備份路由給DSRBACKUP中主要路由提供最大可能的備份。
具體改動如下：
a)保持DSR中路由請求（RReq）中各個選項值不變。增加MinBCur選項，表示此路由中所有節點中的最小帶寬值；增加MinBReq選項，表示路由中所需要的最小帶寬資源。
b)保持DSR中路由應答（RRep）中各個選項值不變。增加BackupFlag選項，表示是否包括備份路由標記。如果BackupFlag=1表示此路由應答包含備份路由；BackupFlag=0為普通路由應答。
c)增加路由丟失（RLost）協議數據類型，選項包括源地址、目的地址、源路由、用于發送給路由丟失的起始節點，通知其重新建立備份路由。
d)設立備份路由緩存器，用于保存接收到的備份路由。增加MaxDuplicateRReq標記來代表路由請求（RReq）的最大可接受重復次數；增加MaxWaitTime表示路由請求目的節點等待重復路由請求的最大時間。
DSRBACKUP協議處理主要包括三個部分：
a)路由發現。傳統的多路徑選擇是考慮打開DSR中路由請求的洪泛機制，即當中間節點接收到路由請求后對鄰居節點廣播，以此來尋找多條可用路徑，但路由請求廣播風暴會造成巨大的資源開銷。此處利用設置帶寬限制來降低廣播成本，根據帶寬和時延，選取與主要路由相交節點最少的一條備份路由。
（a)起始節點發送數據前，檢查路由緩存器中是否已有到目的節點路由，同時包括主要路由和備份路由緩存器。如果兩者都有或有一個命中則按照DSR源路由方式發送數據包。如果都沒有則按需要建立RReq路由請求，設立源地址、目的地址、請求標志號、地址列表、最小可使用帶寬MinBCur、最小需求帶寬值MinBReqTTL等選項，并廣播發送給鄰居節點。
（b)中間節點在路由請求最大可接受重復次數的限制內檢查其剩余帶寬BRemain，如果BRemain （c)路由請求的目的節點在收到一個新的路由請求時，設置在MaxWaitTime時間限制內接收重復路由請求并根據最小帶寬MinBReq和時延Delay，選取合適的主要路由和一條備份路由，發送路由應答給起始節點。 b)路由維護。當主要路由和一條備份路由建立之后，如果主要路由上出現斷鏈路，備份路由若存在，則會通過路由切換自動啟動。 對于路由維護中的路由重建機制，可以采用兩種方式：當主要路由和備份路由同時失效時，發起重新建立新路由的過程；在兩路由其中之一失效就開始路由重建。當要發起路由重建時，通過產生路由丟失（RLost）通知，設立其中的源地址、目的地址，根據相關信息獲取路由發起節點的返回源路由，填入其中并發送給源節點。當路由發起節點接收到RLost時，重新發起路由發現過程，重新建立路由。根據文獻[5]的仿真實驗結果，考慮到提供更好的QoS穩定性，本文采用后一種方式，即任一路由失效就開始重新建立路由。 c)備份路由選擇。目的節點在最長等待時間（MaxWaitTime）限制之內，記錄下最小可使用帶寬（MinBCur）大于最小需求帶寬值MinBReq的所有路由，選擇最先到達的路由為主要路由；然后在所有接收到的除主要路由以外的可用路由中再選擇一條備份路由。筆者考慮最大程度地備份主要路由中的節點，所以優先使用最少相交節點路由作為備份路由；然后根據最小可使用帶寬MinBCur和時延Delay，設定不同的比重（這里分別都設為0.5），選擇最合適的備份路由。 測量標準中路由最小可使用帶寬MinBCur和時延Delay的公式為 metric =（a/MinBCur+b×Delay)/ (1/MinBCur+ Delay)。 用偽代碼語言描述備份路由選擇過程如下： Begin If MaxWaitTime not timeout If MinBCur> MinBReq If SelectedPriRoute is empty SelectedPrimeRoute= CurRevRoute Else If sharednode(CurRevRoute， selectedPrimeRoute) <=LastSharedNodeNum If Metric<=CurrentMetric CurrentMetric = Metric SelectedBackupRoute = CurRevRoute End if End if End If Else Ignore CurRevRoute End if End if End 3 仿真分析 本文采用NS2進行性能仿真，目的是分析DSRBACKUP協議對節點移動的性能變化。采用802.11 DCF控制方式，節點移動速度分為慢速0~20 km/h和中速20~50 km/h。仿真具體參數如下所示： 場景范圍通信距離鏈路帶寬 1 500 m×1 500 m250 m2 m/s 數據包大小數據流類型移動方式 512 Byte恒定數據流隨機 在不同節點個數的場景下仿真，設置每節點都是數據源，隨機發起數據流，要求最小帶寬為75~500 kbps，移動速度為慢速，節點個數分別設置為10~50，最大可接受RReq重復次數MaxDuplicateRReq分別設置為5、6、7。結果如圖1所示。其中，（a）表明DSRBACKUP的路由請求次數隨著可接受RReq重復次數的增加更接近于線性增加。在設定MaxDuplicateRReq，考慮到獲取更多的可選路由，同時要適當控制路由控制開銷，選擇在達到線性增加之前是比較好的做法。（b）中當節點數低于30個，DSRBACKUP協議的分組交付率較DSR有一定的優勢，但在超過這30個節點后優勢不是很明顯，甚至呈現劣勢，分析原因是隨著節點的增多，備份路由可以彌補分組交付時的發送錯誤，但同時路由的路徑長度也隨之變長，路由切換的機會增加，也增加了備份路由的開銷，造成性能沒有提升。 在不同移動速度的場景中，設定節點個數為20，同樣設定每節點都是數據源，要求最小帶寬為75~500 kbps，節點平均移動速度分別為0~50 km/h，其中最大可接受RReq重復次數MaxDuplicateRReq設置為5。結果如圖2所示。其中，（a）移動速度在慢速到中速過程，DSRBACKUP有明顯的優勢，但隨著速度的增大，這一優勢不明顯；在（b）中，速度的增加使得時延的性能改進效果不大，分析主要原因在于開銷的增大。 路由開銷采用計算在仿真期間發送的路由分組總個數的方式，對于在多跳路徑上發送的分組，每發送一跳計算為一次發送。圖3（a）中顯示了隨著節點速度的增加，路由開銷DSRBACKUP較DSR有一定的增加，主要是路由發現過程的RReq復制包和路由維護中的路由重建請求。DSRBACKUP的路由失效次數是計算主要和備份路由均無法找到的次數。圖3（b）中可以看出，備份路由的存在使得路由失效次數減少接近一倍多，從路由開銷增加的比例和路由失效次數降低的幅度來看，當在節點移動速度不快的情況下，DSRBACKUP較DSR具有較好的性能開銷比。 4 結束語 本文介紹的DSRBACKUP協議是一種對按需路由協議DSR設計添加的備份路由機制，為在移動節點中QoS數據通信流的性能穩定提供保證機制，減輕了路由協議振蕩對QoS保證造成的影響。通過仿真結果發現，DSRBACKUP在中等節點數量、非高速移動環境下能夠提供較好的性能穩定性。 參考文獻： [1]KIMD. A new mobile environment: mobile Ad hoc networks (MANET)[J]. IEEE Vehic Tech Soc News，2003(8):2935. [2]LEE S B， AHN G S. INSIGNIA: an IPbased quality of service framework for mobile Ad hoc networks[J]. Journal of Parallel and Distributed Computing， 2000，60(4):374406. [3]JOHNSON D. RFC 4728， Thedynamic source routing protocol (DSR) for mobile Ad hoc networks for IPv4[S]. 2007. [4]GUO Song， YANG O， SHU Yantai. Improving source routing reliability in mobile Ad hoc networks[J]. Parallel and Distributed Systems， 2005，16(4):362373. [5]LEE S J， GERLA M. Split multipath routing with maximally disjoint paths in Ad hoc networks[C]//Proc of IEEE ICC’01. 2001:32013205. [6]ADIBI S， ERFANI S. A multipath routing survey for mobile Ad hoc networks[C]//Proc of Consumer Communications and Networking Conference. 2006:984988. [7]李君，舒炎泰，竇志斌，等.基于DSR協議的備用路由機制設計和性能評價[J].計算機工程與應用， 2006，42(36):100103. [8]周敬祥，李臘元. Ad hoc網絡DSR路由協議的優化[J]. 計算機應用研究， 2006，23(12):292293，322.
