蘇嬌嬈

(北京軍區(qū)總醫(yī)院 信息科,北京 100700)

DSR路由協(xié)議的改進

蘇嬌嬈

(北京軍區(qū)總醫(yī)院 信息科,北京 100700)

DSR路由協(xié)議是移動Ad Hoc網(wǎng)絡常用的按需路由協(xié)議之一。由于采用洪泛機制尋找和維護路由表,DSR路由協(xié)議能量開銷高、分組交付率低。針對此問題,提出局部化路由查詢方法,限制路由請求跳數(shù),改進DSR路由協(xié)議的路由發(fā)現(xiàn)過程,有效地平衡了路由信息存儲量、網(wǎng)絡擁塞和能量消耗。分析表明,改進的DSR路由協(xié)議將路由請求分組控制在一定的網(wǎng)絡范圍內(nèi),減少數(shù)據(jù)傳輸時延、降低網(wǎng)絡能量開銷。仿真結(jié)果顯示,在選擇適當?shù)淖畲筇鴶?shù)時,改進的DSR路由協(xié)議在分組交付率、路由載荷方面均優(yōu)于傳統(tǒng)的DSR路由協(xié)議。

Ad Hoc;DSR路由協(xié)議;分組交付率;路由載荷

移動Ad Hoc網(wǎng)絡是無線自組織網(wǎng)絡,無需依賴于網(wǎng)絡基礎設施,能夠迅速展開。各個網(wǎng)絡節(jié)點相互協(xié)作、通過無線鏈路進行通信、交換信息,實現(xiàn)信息和服務的共享[1]。不同于普通的Mobile IP移動網(wǎng)絡,在Mobile IP中移動節(jié)點通過基站等有線基礎設施的支持來實現(xiàn)移動通信,而移動Ad Hoc網(wǎng)絡完全由移動節(jié)點構(gòu)成[2]。這種網(wǎng)絡的建立快捷、靈活,不受有線網(wǎng)絡的約束,可廣泛的應用于災難救助、偏遠地區(qū)等無法得到有線網(wǎng)絡支持,或某些只是臨時需要通信但建立有線通信網(wǎng)絡代價過大的環(huán)境,具有廣闊的發(fā)展前景[3]。

由于移動節(jié)點的通信范圍有限,相距較遠的節(jié)點需要通過其他節(jié)點轉(zhuǎn)發(fā)才能通信,因此網(wǎng)絡中節(jié)點同時也是路由器,負責為其他節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包。由于節(jié)點移動,Ad Hoc網(wǎng)絡網(wǎng)絡拓撲結(jié)構(gòu)動態(tài)變化。移動網(wǎng)絡本身具有的通信帶寬有限、電池能源有限等特性,使得設計合適的移動Ad Hoc路由協(xié)議具有一定的挑戰(zhàn)性[4-6]。

移動Ad Hoc網(wǎng)絡路由協(xié)議按照發(fā)現(xiàn)路由的策略可分為表驅(qū)動路由和按需路由協(xié)議[1]。在表驅(qū)動路由協(xié)議中,每個節(jié)點都有一張完整的路由表,該路由表需要頻繁地更新以適應網(wǎng)絡動態(tài)拓撲結(jié)構(gòu)的變化。其優(yōu)點在于節(jié)點發(fā)送數(shù)據(jù)時時延小,但由于頻繁交換的路由信息中有大部分不為當前發(fā)送數(shù)據(jù)所需,因此將浪費大量寶貴的無線帶寬。而按需路由協(xié)議則是當節(jié)點需要發(fā)送數(shù)據(jù)時,根據(jù)需要建立相應的路由,因此節(jié)點中的路由表并不是反映了整個網(wǎng)絡的拓撲,而僅是當前所需的路由。按需路由雖會增加數(shù)據(jù)分組因等待路由建立產(chǎn)生的時延,但由于協(xié)議無需節(jié)點周期地交換路由信息,因而節(jié)省了有限的無線資源?，F(xiàn)在的移動Ad Hoc路由協(xié)議大多采用按需路由方式,主要有DSR[7-8],ABR[9-10],AODV[11],LAR[12],CBRP[13],RDMAR[14]和ZRP[15]等。這些按需路由協(xié)議分別針對不同的網(wǎng)絡應用場景設計,各自具有不同的優(yōu)缺點,其中最典型的是DSR路由協(xié)議[16-17]。

本文分析DSR路由協(xié)議在路由尋找和維護過程中使用廣播方式存在的資源消耗較大和分組交付率低的缺點,提出局部化路由查詢方法,限制路由請求跳數(shù),改進DSR路由協(xié)議的路由發(fā)現(xiàn)過程,降低網(wǎng)絡傳輸時延、提高分組交付率和降低網(wǎng)絡路由載荷。

1 DSR路由協(xié)議及其缺陷

1.1 DSR路由協(xié)議

DSR路由協(xié)議的特點在于使用了源路由的路由機制,在報文的頭部攜帶要經(jīng)過的路由,路由器按照該路由序列來轉(zhuǎn)發(fā)報文。協(xié)議包括兩部分:路由發(fā)現(xiàn)和路由維護。

(1)路由發(fā)現(xiàn)。當節(jié)點S需要到D的路由時,S廣播“路由請求”報文,每個請求報文通過序列號和S標識唯一確定。收到“路由請求”報文的節(jié)點,若滿足:1)該節(jié)點不是目的節(jié)點D。2)請求報文頭部的源路由序列中不包含該節(jié)點。3)該節(jié)點沒有接收過同樣的路由請求報文。4)節(jié)點的路由表中沒有到目的節(jié)點D的路由信息。節(jié)點將自己的地址附加到“路由請求”報文頭部的路由序列中,并將報文通過洪泛方式轉(zhuǎn)發(fā)給所有相鄰節(jié)點。

若2),3)不滿足,節(jié)點將刪除報文,防止循環(huán)處理。若1),2)不滿足,節(jié)點將發(fā)送“路由應答”給S,應答中包含了從S到D的路由,該路由從請求報文中攜帶的路由序列或節(jié)點自身路由表中記錄的路由信息中得到。S獲得路由后,使用源路由進行數(shù)據(jù)通信。

(2)路由維護。DSR路由協(xié)議支持主動應答和被動應答兩種鏈路狀態(tài)監(jiān)測方法,一旦節(jié)點在發(fā)送數(shù)據(jù)時發(fā)現(xiàn)需要使用的鄰接鏈路斷開,其發(fā)送“路由出錯”報文給這些斷開路由的源節(jié)點,源節(jié)點收到報文后將失效路由從路由表中刪除。沿途轉(zhuǎn)發(fā)“路由出錯”的節(jié)點也從自身的路由表中刪除包含該斷開鏈路的所有路由。

(3)DSR路由協(xié)議評價。1)節(jié)點無需周期性的發(fā)送報文,節(jié)省了電池能源和網(wǎng)絡帶寬,尤其是當無節(jié)點要發(fā)送數(shù)據(jù)時,網(wǎng)絡中沒有通信開銷。2)支持中間節(jié)點應答,能使源節(jié)點快速獲得路由,但會引起過時路由問題。3)每個報文都需要攜帶完整的路由信息,降低了網(wǎng)絡帶寬的利用率。

1.2 DSR路由協(xié)議存在的不足

DSR路由協(xié)議是一個簡單高效的移動Ad Hoc網(wǎng)絡按需路由協(xié)議,但在特定的應用場景下,DSR路由協(xié)議存在一些不足,主要體現(xiàn)在:

(1)DSR路由協(xié)議使用簡單的洪泛方式查找路由,即網(wǎng)絡中每個節(jié)點在收到路由請求報文后,只要報文不重復且本身不是目的節(jié)點或沒有到達目的節(jié)點的路由信息,該節(jié)點就會向相鄰節(jié)點廣播該報文。洪泛路由請求分組使得網(wǎng)絡中存在大量的冗余請求數(shù)據(jù)包,一方面占用了有限的帶寬資源,造成節(jié)點能量消耗;另一方面洪泛產(chǎn)生大量的信息干擾和碰撞。在目的節(jié)點就是源節(jié)點的鄰居節(jié)點或是離源節(jié)點較近的節(jié)點時,雖只需一步或較少幾步就可找到所需路由,但洪泛式的廣播會使網(wǎng)絡中很多節(jié)點甚至全部都參與路由查找,浪費了有限的網(wǎng)絡資源,降低了路由查找的效率。

(2)當移動節(jié)點在發(fā)送數(shù)據(jù)時發(fā)現(xiàn)所使用的鄰接鏈路斷開時,發(fā)送“路由出錯”報文給這些斷開路由的源節(jié)點。源節(jié)點還要重新進行路由發(fā)現(xiàn)過程,找到目的節(jié)點的新路由后再重發(fā)所有或部分數(shù)據(jù)。

(3)由于鏈路是單向的,當源節(jié)點收到路由出錯報文后,轉(zhuǎn)發(fā)“路由出錯”報文的節(jié)點不能通知上游節(jié)點路由信息出錯,需要重新進行路由發(fā)現(xiàn)過程。

(4)DSR的路由維護只是簡單的將出錯的鏈路信息發(fā)給有關的節(jié)點。當數(shù)據(jù)傳送了一部分,并且這一部分數(shù)據(jù)緩存在這個中間節(jié)點中,鏈路出錯的處理方法就造成了很多的浪費。

為克服DSR路由協(xié)議的不足,提出局部化路由查詢方法,限制路由請求跳數(shù),改進DSR路由協(xié)議的路由發(fā)現(xiàn)過程,降低網(wǎng)絡傳輸時延、提高分組交付率和降低網(wǎng)絡路由載荷。

2 DSR路由協(xié)議改進

2.1 平衡關系

DSR路由協(xié)議在執(zhí)行完路由尋找完成后,將發(fā)現(xiàn)的路由存儲到路由緩存器中。緩沖存儲的路徑越多,便可盡量避免路由尋找的過程,減少因為路由尋找所帶來的網(wǎng)絡擁塞問題和節(jié)點功耗。但節(jié)點路由緩存器中所存儲的路徑,必然要經(jīng)過路由尋找過程。在網(wǎng)絡節(jié)點密集的情況下路由尋找會加重網(wǎng)絡的擁塞狀況。針對Ad Hoc網(wǎng)絡,本文對DSR路由協(xié)議進行改進,降低網(wǎng)絡中路由請求分組數(shù)量,減少網(wǎng)絡的能量消耗。

傳統(tǒng)DSR路由協(xié)議中默認的是對路由請求分組的跳數(shù)不加限制,以獲得盡可能多的路由存儲在路由緩沖器中。但這同時也是對網(wǎng)絡資源和能量的浪費,一方面增加節(jié)點的功耗,另一方面網(wǎng)絡中存在大量路由請求和應答數(shù)據(jù)包,增加網(wǎng)絡負載,引起網(wǎng)絡擁塞,最終可能會使大量的數(shù)據(jù)包丟棄,降低網(wǎng)絡中數(shù)據(jù)分組的交付率,增加分組的傳輸時延。

在DSR路由協(xié)議的實際應用中,對路由尋找過程中的路由請求分組的跳數(shù)加以限制可克服上述的缺點。Ad Hoc網(wǎng)絡的每一條路由的中間節(jié)點數(shù)目并不是很多,實驗統(tǒng)計表明DSR路由協(xié)議中大多數(shù)路由的中間節(jié)點的數(shù)目較小。對路由的跳數(shù)設定一個上限閥值,以有效地減少網(wǎng)絡中路由請求分組冗余的數(shù)量,減輕節(jié)點負擔和功耗。但這是以減少節(jié)點路由緩存器所存儲的路徑條數(shù)為代價的,若將跳數(shù)的閥值設置較小,雖可減少路由請求的發(fā)送數(shù)量和降低節(jié)點的功耗,同時也可能使得許多路由請求過程找不到有效的路徑。一方面由于緩存的路徑比較少,節(jié)點會頻繁的發(fā)起路由請求過程;另一方面由于節(jié)點路由尋找的失敗,節(jié)點會繼續(xù)發(fā)起路由請求過程尋找可用的路由。

對節(jié)點路由緩存器中緩沖的路徑和網(wǎng)絡的擁塞狀況、節(jié)點的功耗之間做出一個合理的權衡,即這兩方面要做一個折中以取得最佳的結(jié)果。本文基于以上考慮,提出局部化路由查詢方法,限制路由請求跳數(shù),改進DSR路由協(xié)議的路由發(fā)現(xiàn)過程,有效的平衡了路由信息存儲量、網(wǎng)絡擁塞和能量消耗。

2.2 DSR路由協(xié)議改進

為了平衡節(jié)點緩存的路經(jīng)數(shù)、網(wǎng)絡擁塞和功耗,對路由尋找進程所發(fā)出的路由請求分組的跳數(shù)加以限制,使得路由尋找的過程在一個合理的范圍內(nèi)進行。通過路由尋找所獲得的路由的長度均不會超過給定的最大跳數(shù)閥值max_hop。

改進后的DSR路由協(xié)議通過限制路由請求跳數(shù)將路由尋找限定在網(wǎng)絡局部范圍內(nèi),減少路由請求消息的發(fā)送,減少產(chǎn)生的重復的廣播,降低路由請求分組碰撞的發(fā)生概率,減少路由的平均跳數(shù),適當提高數(shù)據(jù)分組的交付率。通過設置不同的max_hop,有效的平衡路由信息存儲量、網(wǎng)絡擁塞和能量消耗。

3 分析與仿真

3.1 性能分析

相比與傳統(tǒng)DSR路由協(xié)議,改進后的DSR路由協(xié)議在減少數(shù)據(jù)傳輸時延、網(wǎng)絡開銷、路由載荷,提高分組交付率等方面具有明顯的優(yōu)勢,更加適合于能量相對受限的AdHoc網(wǎng)絡。

(1)數(shù)據(jù)傳輸時延。移動AdHoc網(wǎng)絡路由協(xié)議使用按需操作準備發(fā)送數(shù)據(jù)時,若該數(shù)據(jù)需一條未知的傳輸路徑,需要調(diào)用路由尋找進程尋找到達目的節(jié)點的路由,因此必須延遲該分組發(fā)送,從而導致分組交付時延的增大。考慮兩個方面的時延:1)節(jié)點獲取到達目的節(jié)點的路由所消耗的時間。2)當正在使用的路由中斷后發(fā)送節(jié)點“恢復”路由所消耗的時間。改進后的DSR路由協(xié)議對路由尋找的跳數(shù)進行了限制,一方面、消除了網(wǎng)絡大量的冗余路由請求信息,減少網(wǎng)絡通信碰撞,減少時延;另一方面、使得尋找路由更加簡潔高效,速度更快,減少路由發(fā)現(xiàn)時延。路由中斷后的路由恢復同樣采用限制跳數(shù)的方法,減少路由恢復時延。

(2)節(jié)點能量開銷。盡管按需路由協(xié)議無需周期性地將路由信息傳播到整個網(wǎng)絡中從而能夠降低路由開銷,但執(zhí)行按需路由尋找進程路由時的代價可能較高。當數(shù)據(jù)發(fā)送者發(fā)送路由請求分組時,此路由請求分組洪泛到整個網(wǎng)絡中,這就有可能干擾網(wǎng)絡中的每個節(jié)點消耗寶貴的帶寬和能量。接收到路由請求分組的每個節(jié)點根據(jù)其路由存儲器中的路由信息給源節(jié)點回送一個路由應答分組,進一步轉(zhuǎn)發(fā)路由請求分組。改進后的DSR路由協(xié)議限制了洪泛的范圍,減少大量不必要的冗余數(shù)據(jù),有效降低了節(jié)點的開銷。

3.2 性能仿真

使用網(wǎng)絡模擬工具NS2,從分組交付率和路由載荷兩個方面對改進的DSR路由協(xié)議進行仿真。分組交付率定義為交付到目的節(jié)點的數(shù)據(jù)分組數(shù)量與連續(xù)比特速率數(shù)據(jù)源(CBR)源節(jié)點產(chǎn)生的數(shù)據(jù)分組數(shù)量之比。路由載荷定義為建立一條傳輸路徑所需要發(fā)送的路由分組數(shù)量。

(2)仿真結(jié)果。1)分組交付率。在max_hop取不同值時的網(wǎng)絡中數(shù)據(jù)分組的交付率如圖1所示。從圖中可看出,使用10個最大連接時,max_hop取值不同時的DSR協(xié)議的分組交付率類似。但增加網(wǎng)絡的連接數(shù)時,max_hop取值越小,數(shù)據(jù)分組的交付率越高。因此,在實際應用中,可對路由請求分組的跳數(shù)加以適當?shù)南拗?以提高分組交付率。

圖1 分組交付率比較

2)路由載荷。網(wǎng)絡路由載荷如圖2所示。無論連接數(shù)是多少,在max_hop取最小值5時的路由載荷均為最高。驗證了max_hop取值小時可提高數(shù)據(jù)分組的交付率,但同時也會增加一定的路由開銷。

圖2 路由載荷比較

仿真結(jié)果顯示了對DSR協(xié)議改進前后的兩個重要的特征差異。改進后的DSR協(xié)議提高了分組交付率。在網(wǎng)絡相對寬松的情況下,如最大連接數(shù)為10時,是否對跳數(shù)進行限制對DSR協(xié)議在分組交付率幾乎沒有影響?？傮w上當連接數(shù)增大時,對跳數(shù)進行限制時的交付率都呈遞減趨勢。但只要將跳數(shù)限制為一個合理的數(shù)值,便可適當?shù)脑黾訑?shù)據(jù)的交付率,同時不至于增加路由開銷。

時延和路由開銷方面,隨著網(wǎng)絡連接數(shù)的增加,無論是否對路由分組的跳數(shù)進行限制,網(wǎng)絡的時延和路由開銷都呈現(xiàn)遞增趨勢。但max_hop在取7和10時,路由載荷的增加并不快。因此,max_hop可在7～10之間取值。

4 結(jié)束語

由于采用洪泛的方式尋找和維護路由表,DSR路由協(xié)議開銷較大、易形成網(wǎng)絡擁塞、分組交付率低。針對DSR路由協(xié)議的缺陷,提出局部化路由查詢方法,限制路由請求跳數(shù),改進DSR路由協(xié)議的路由發(fā)現(xiàn)過程,有效地平衡了路由信息存儲量、網(wǎng)絡擁塞和能量消耗。分析和仿真結(jié)果表明改進的DSR路由協(xié)議將路由請求分組控制在一定的網(wǎng)絡范圍內(nèi),具有數(shù)據(jù)傳輸時延低、網(wǎng)絡能量開銷低,分組交付率高、路由載荷低等特點。

[1] Vassileva N,Barcelo-Arroyo F.A survey of routing protocols for energy constrained ad hoc wireless networks[C].Jeju-Island,Korea:Future Generation Communication and Networking(FGCN 2007),2007:522-527.

[2] Do-Hyun Nam,Hong-Ki Min.An efficient Ad-Hoc routing using a hybrid clustering method in a wireless sensor network[C].White Plains,NY:Proceedings of the Third IEEE International Conference on Wireless and Mobile Computing,Networking and Communications,2007:60-65.

[3] Ma Y,Kibria M R,Jamalipour A.Optimized routing framework for intermittently connected mobile Ad Hoc hetworks[C].Beijing:ICC ’08.IEEE International Conference on Communications,2008:3171-3175.

[4] Chiu Chunyuan,Kou Yuliang Kuo,Wu E H K,et al.Bandwidth-constrained routing problem in wireless Ad Hoc networks[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(1):4-14.

[5] Kadri Benamar,Feham Mohammed,M Hamed Abdallah.Weight based DSR for mobile Ad Hoc networks[C].Damascus,Syria:ICTTA 2008.3rd International Conference on Information and Communication Technologies:From Theory to Applications,2008:1-6.

[6] Mohamed Aissani,Messaoud Fenouche,Hadi Sadour,et al.Ant-DSR:cache maintenance based routing protocol for mobile Ad-Hoc networks[C].Mauritius:the Third Advanced International Conference on Telecommunications,2007:35-41.

[7] Broch J,Johnson D B,Maltz D A.The dynamic source routing protocol for mobile ad hoc networks [S].Switzerland:Internet Draft,1998.

[8] Johnson D B,Maltz D A.Mobile computing[M].Boston USA:Kluwer Academic Publishers,1996.

[9] Toh C-K.A ssiciatibity-based routing for ad hoc mobile networks[J].Wireless Personal Communications,1997,4(2):103-109.

[10]Toh C-K.Long-lived Ad Hoc routing based on the concept of associatively[S].Switzerland:Internet Draft,1999.

[11]Perkins C E,Royer E M,Das S R.Ad Hoc on-demand distance vector routing[S].Switzerland:Internet Draft,1999.

[12]Ko Y-B,vaidya N H.Location-aided routing in mobile ad hoc network[C].Dallas,TX:ACM/IEEE International Conference on Mobile Computing and Network,1998:537-545.

[13]Jiang M L,Li J Y,Tay Y C.Cluster based routing protocol (cbrp)[S].Switzerland:Internet Draft,1999.

[14]George A.Relative distance m icro-discovery ad hoc routing protocol[S].Switzerland:Internet Draft,1999.

[15]Hass Z J.The zone routing protocol for ad hoc network[S].Switzerland:Internet Draft,1997.

[16]Tao Yang,Makoto Ikeda,Giuseppe De Marco,et al.Performance behavior of AODV,DSR and DSDV protocols for different radio models in Ad-Hoc sensor networks[C].Xi’an:the 2007 International Conference on Parallel Processing Workshops,2007:51-56.

[17]Ha Duyen Trung,Watit Benjapolakul,Phan Minh Duc.Performance evaluation and comparison of different Ad Hoc routing protocols[J].Computer Communications,2007, 30(11):2478-2496.

An Improvement to DSR Routing Protocol

SU Jiaorao

(Department of Information,Beijing Military General Hospital,Beijing 100700,China)

DSR is one of the most frequently-used on-demand routing protocols in the mobile Ad Hoc networks.DSR protocol is high in energy costs and low in packet delivery fraction because DSR finds and maintains routing table by the flooding mechanism.To this problem,a localized routing discovery method is proposed to control the routing request hops.Also,the routing discovery process is improved so that the storage of the routing information,network jam and energy costs are effectively balanced.The analysis shows that the improved DSR protocol controls the routing request packets to a certain network area.In this way,the data transmission delay and the networks energy costs are reduced.The simulation results show that the improved DSR protocol has the advantages of packet delivery fraction and routing load over the traditional one on choosing the proper maximum hops.

Ad Hoc;dynamic source routing;packet delivery fraction;routing load

2014- 03- 11

蘇嬌嬈(1976—),女,碩士,工程師。研究方向:計算機通信與網(wǎng)絡。E-mail:Sjrr881@sohu.com

10.16180/j.cnki.issn1007-7820.2015.04.011

TN915.05

A

1007-7820(2015)04-038-05