基于小世界理論和QoS支持的DSR協議*

李向麗，李超超

（鄭州大學信息工程學院，河南鄭州 450001）

0 引言

在移動自組織（Ad Hoc）網絡中，動態源路由（dynamic source routing，DSR）協議是一種應用比較廣泛的路由協議。它的優點是簡單方便，不需要周期性廣播路由分組，路由開銷小，僅僅需要維護與通信節點之間的路由［1］。DSR是一種按需路由協議，不需要維護到每個節點的路由表，當有數據要發送時才進行路由發現過程，增大了端到端時延［2］;Ad Hoc節點能量是影響網絡性能的關鍵因素，DSR協議沒有考慮節點能量問題［3］;DSR協議僅僅選擇跳數作為路由選擇的標準，沒有考慮其它因素，沒有服務質量（QoS）保證［4］。針對DSR協議存在的問題，本文提出改進DSR（improved DSR，IDSR）協議，它可以有效地預測要發送數據的節點，提前進行路由發現過程，探測出該節點所在網絡拓撲結構。IDSR選擇時延和剩余能量作為選擇路徑的標準，提供QoS支持。

1 DSR協議概述

DSR協議是一種按需路由協議，包括路由發現和路由維護2個過程。

1.1 路由發現

當源節點有數據要發送時，首先檢查緩存中是否存儲有到達目的節點的路徑。如果有，則按緩存的路徑發送分組;否則，啟動路由發現過程。源節點廣播發送路由請求分組（RREQ）。中間節點收到的RREQ的源地址與標識號和之前收到的相同，就丟棄它;否則，就接收。假如中間節點的緩存中已經有到目的節點的路徑信息，或者自己就是目的節點，向源節點發送路由應答分組（RREP）。如果中間節點發現RREQ報文的路由記錄中已經包含了自己，就丟棄該報文［5］;否則，中間節點把自己的地址添加到RREQ中，之后把更新過的RREQ分組再廣播出去。

1.2 路由維護

源節點發送數據分組過程中，當中間節點發現路由的下一跳節點鏈路不可達，就向源節點發送一個路由錯誤報文（RRER）。源節點收到RRER之后，從路由緩存中刪除所有經過該節點的路由。同時，在RRER向源節點傳輸的過程中，收到此報文的中間節點也將路由緩存中含有該錯誤節點的路由刪除。如果源節點的緩存中含有另一條到達目的節點的路由，則用新的路由發送分組;否則，重新進行路由發現過程。

2 IDSR協議

下面描述IDSR的設計思想和實現技術。

2.1 小世界理論與應用

實驗表明，一個人要找另一個自己不認識的人，他首先找自己的朋友，朋友再找他的朋友。這樣經過5～6層關系就可以找到自己想要找的人。這樣的現象就稱為小世界現象。不僅僅在人類社會領域存在這樣的現象，在計算機網絡領域也存在小世界現象。經研究表明，無論什么樣的計算機網絡，只要是人在使用，就具有小世界特征，Ad Hoc網絡也具有小世界特征。一般情況下，任何一個節點的通信對端距離自己6跳以內［1］。

一個節點剛剛已經發送完分組到通信對端，根據局部性原理，預測該節點在不久之后還要發送數據，就把該節點定義為預測點。預測點廣播RREQ報文，根據小世界理論，把該RREQ報文的生存時間（TTL）設置為6跳。當TTL減為0，收到RREQ的節點就向源節點回復RREP報文。中間節點記錄下RREP報文中所攜帶的路由。經過上述過程，以預測點為中心的6跳范圍以內，每一個節點都記錄下了經過自己所能到達的所有節點的路由。

即使預測點在不久之后并沒有發送數據，經過該過程之后所得到的節點中緩存信息可以用到其它節點通信中，降低路由發現過程時延。節點在被定義為預測點之前通信過，它的緩存中會有到舊通信對端的路由緩存信息，但新的通信對端和舊通信對端可能不是一個節點，可能之前緩存的路由信息已經過期，所以，預測點提前探測所在網絡拓撲結構是有必要的。

2.2 支持QoS的路由

路由發現過程可能會產生多條到達目的節點的路徑，DSR只是以跳數作為選擇最佳路由的依據。對于有線網絡，最小跳數的路由有很好的性能，但是對于Ad Hoc網絡，這會使某些節點過早的消耗完能量，影響網絡生存周期［4］，跳數最小的路由時延不一定最小。網絡QoS是指網絡在傳輸數據流時要滿足的一系列服務請求［6］。傳輸流的QoS需求一般包括包丟失率、端到端時延等［4］。在Ad Hoc網絡中，因為某個節點過早消耗完能量會導致整條路徑失效而重新發起路由發現過程，增大時延，增加路由開銷，降低網絡生存周期。所以，本文提出以時延、剩余能量作為最佳路由選擇的標準。

把每個節點的剩余能量分成3個等級［4］;第一等級是指節點的剩余能量大于等于初始能量的50%，這樣的節點收到RREQ立即處理，通過相應檢查后，再轉發出去，沒有額外時延;第二等級是指節點的剩余能量大于等于初始能量的10%且小于初始能量50%，這樣的節點在處理RREQ前需要一段時延（delay），這段時延與節點剩余能量呈反比，最大值為 0.01 s［7］，delay的計算表達式如式（1）所示

其中，Energy為節點的剩余能量，iniEnergy為節點初始能量;第三等級是指節點剩余能量小于初始能量10%，這樣的節點不處理RREQ，把它丟棄，并且該節點也不參與數據傳輸，只能作為源節點和目的節點［8］。

該方案傳輸數據的路由盡量選擇第一等級的節點，當節點的剩余能量處于第二等級，推遲一個時延轉發RREQ，目的節點僅僅處理最先到達的RREQ，并返回RREP，這樣降低了使用第二等級節點的可能性，降低節點的消耗的速度。第三等級節點不進行數據傳輸，避免過度消耗該節點的能量。該方案在選擇最佳路由時，同時考慮到路由時延和節點的剩余能量，可以更好地滿足QoS的需求，降低端到端時延，延長網絡生存周期。

為了說明該方案具體的工作過程，以圖1為例進行描述［9］。假設A要向D發送數據，首先檢查緩存中是否含有到D的路由信息，假設沒有，啟動路由發現過程。A廣播發送RREQ報文，B收到A節點發來的RREQ，檢查自己的剩余能量，假設B節點為第一等級節點，通過對RREQ相應檢查后，立即把自己的地址添加到RREQ中，再把更新過的RREQ轉發出去。C節點收到該RREQ報文，假設它為第二等級節點，計算delay值，延遲delays把自己地址添加到RREQ報文中，再轉發出去。H節點收到廣播的RREQ后，發現自己為第三等級節點，立即丟棄RREQ報文。目的節點D處理最先收到的RREQ，并回復RREP報文。

A節點和D節點通信后，把A定義為預測點，猜測新的通信對端距離它6跳之內。A廣播發送RREQ報文，TTL為6。當TTL減為0時，收到該報文的節點會向源節點發送RREP，收到RREP的中間節點記錄下相應的路由信息。A節點可以得到A-B-C-D-E-F-G，A-H-I-J-K-L-M，A-B-C-I-JK-L，A-H-I-C-D-E-F四條長度為6跳的路徑。假設預測準確，不久之后，A有數據要發送到節點F，A節點在緩存中有2條路徑可以到達F，一條是A-B-C-D-E-F（記為P1），另一條是A-H-I-C-D-E-F（記為P2）。提前探測網絡拓撲結構時，每個節點會記錄下收到RREQ報文的時間，并根據自己能量計算轉發RREQ的延時。A節點比較P1和P2路徑的時延，選擇時延較小的一條路徑作為主路徑，并進行數據傳輸，剩余的路徑作為備選路徑。

在此之后，假設P節點有數據要發送到K，P廣播發送RREQ報文，M節點已經知道到K節點的路徑（M-L-K），收到RREQ后，M發送RREP到P節點。

圖1 預測點發現路徑Fig 1 Prediction node discovers path

3 仿真實驗與性能分析

3.1 仿真模型

以NS2作為仿真平臺，對DSR和IDSR協議進行仿真實驗。實驗節點數為30個，節點在1 000 m×1 000 m區域內移動。仿真時間為100 s，節點運動的速度和初始的位置隨機確定。最大移動速度分別為 5，10，15，20，25 m/s。本實驗采用CBR（constant bit rate）數據流，包的發送速率為10 個/s，包的大小為512 bytes。

3.2 性能評估參數

為了對DSR協議及改進協議IDSR進行性能比較，選取如下5個評估參數:

1）路由開銷:是指節點路由控制分組數（route_sum）和源節點發送的數據包（cbr_sum）的比值［1］。路由開銷計算公式如式（2）所示

2）平均時延:定義為從數據包產生到數據成功傳輸到目的節點所需的時間。

其中，tg為數據報產生的時刻，tr為數據報到達目的節點的時刻。

3）分組成功傳輸率（packet delivery fraction）:指成功到達目的節點的分組數（recv_pack）占總共發送分組數（send_pack）的比例［10］。計算公式為式（4）所示

4）平均跳數:為分組從源節點到目的節點平均需要的跳數，即轉發數據包（fowdpacket）與發送數據包（sendpacket）的比值再加1。計算公式如式（5）所示

5）網絡生存周期:為從網絡運行開始到第一個節點死亡的時間［6］。

3.3 仿真結果與分析

路由開銷與移動速度的關系如圖2所示。在速度不斷變化過程中，IDSR路由開銷低于 DSR，尤其當速度為25 m/s時，IDSR的路由開銷遠遠低于DSR。如圖3所示，IDSR比DSR平均時延要小，尤其當速度為15 m/s時，IDSR的平均時延遠遠小于DSR。雖然IDSR的預測點提前進行路由發現過程會產生許多路由控制分組，但是，如果預測準確，可以省去路由發現過程，即使預測不準確，提前探測到的路由信息可以提供給其它需要通信的節點。在選擇路由時，考慮到節點剩余能量，防止某個中間節點過早消耗完能量，重新發起路由發現過程。所以，IDSR協議的路由開銷低于DSR，時延小于DSR。

如圖4所示，在速度不斷變化過程中，IDSR協議的分組成功傳輸率高于DSR。如圖5所示，IDSR的平均跳數小于DSR。尤其當節點速度大于15m/s時，IDSR的平均跳數遠遠小于DSR。IDSR在選擇路由時，盡量選擇剩余能量多的節點，這樣不會因為某個節點過早消耗完能量而導致整條路徑失效，選擇的路由生存周期長，可以傳輸更多的數據，防止丟包，提高分組成功傳輸率，降低平均跳數。

節點數與網絡生存周期的關系如圖6所示。每個節點的初始能量為20 J，傳輸功率為1.0 W，接收功率為0.8 W，待機功率為0.1 W，最大移動速度為15 m/s。IDSR協議的網絡生存周期大于DSR協議，尤其當節點數為20時，IDSR的網絡生存周期遠遠大于DSR。在路由發現過程中，優先選擇剩余能量較多的節點，降低使用剩余能量較少的節點可能性，第三等級節點不參與傳輸數據，它只能作為源節點或目的節點，避免節點能量過度消耗。所以，IDSR的網絡生存周期和DSR相比有明顯提高。

圖2 不同速度的路由開銷Fig 2 Node velocity vs route cost

圖3 不同速度的平均時延Fig 3 Node velocity vs average delay

圖4 不同速度的分組成功傳輸率Fig 4 Node velocity vs packet delivery fraction

圖5 不同速度的平均跳數Fig 5 Node velocity vs average no.of hops

圖6 不同節點的網絡生存周期Fig 6 Node velocity vs network life time

4 結論

IDSR協議通過預測要發送數據的節點，提前進行路由發現過程，可以減少端到端時延;應用小世界理論，限制RREQ報文傳輸的范圍，避免過多浪費網絡帶寬資源;以時延和剩余能量作為路由選擇的標準，提供QoS支持。仿真實驗表明:改進后的IDSR協議在路由開銷、平均時延、分組成功傳輸率、平均跳數和網絡生存周期方面的性能都優于DSR協議。

［1］李向麗，魏凱敏，呂何平.一種具有小世界特征和沖突避免的DSR協議［J］.小型微型計算機系統，2010，31（8）:1546-1548.

［2］Al-Mekhlafi Z G，Hassan R.Evaluation study on routing information protocol and dynamic source routing in Ad-Hoc network［C］//Proceedings of 2011 7th International Conference on IT in Asia（CITA），Kuching Sarawak，2011:1-4.

［3］Sheng Linyang，Shao Jinbo，Ding Jinfeng.A novel energy-efficient approach to DSR-based routing protocol for Ad Hoc network［C］//Proceedings of 2010 International Conference on Electrical and Control Engineering，Wuhan，2010:2618-2620.

［4］Xu Zhen，Xiao Juan.Energy-aware and delay-aware QoS routing in mobile Ad Hoc networks［C］//Proceedings of IEEE ICCP，Leshan，2012:511-515.

［5］Sen J.An analysis of routing disruption attack on dynamic source routing protocol［C］//Proceedings of IEEE Wireless Communication，Vehicular Technology，Information Theory and Aerospace ＆Electronic Systems Technology（Wireless VITAE），Chennai，2011:1-5.

［6］文 浩，林 闖，任豐原，等.無線傳感器網絡的QoS體系結構［J］.計算機學報，2009，32（3）:432-440.

［7］Baisakh，Patel N R，Kumar S.Energy conscious DSR in MANET［C］//Proceedings of IEEE International Conference on Parallel，Distributed and Grid Computing，Solan，2012:784-789.

［8］Rajgopal G，Manikandan K，Sivakumar N.QoS routing using energy parameter in mobile Ad Hoc network［J］.International Journal of Computer Applications，2011，22（4）:11-17.

［9］馬志欣，趙鼎新，謝顯中，等.車載通信網中基于DSR分層機制的移動代理路由策略研究［J］.重慶郵電大學學報:自然科學版，2011，23（2）:207-213.

［10］Sarkar S，Datta R.A trust-based protocol for energy-efficient routing in self-organized MANETs［C］//Proceedings of IEEE India Conference（INDICON），Kochi，2012:1084-1089.