李向麗，李超超

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

0 引言

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

1 DSR協(xié)議概述

DSR協(xié)議是一種按需路由協(xié)議，包括路由發(fā)現(xiàn)和路由維護2個過程。

1.1 路由發(fā)現(xiàn)

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

1.2 路由維護

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

2 IDSR協(xié)議

下面描述IDSR的設計思想和實現(xiàn)技術(shù)。

2.1 小世界理論與應用

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

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

即使預測點在不久之后并沒有發(fā)送數(shù)據(jù)，經(jīng)過該過程之后所得到的節(jié)點中緩存信息可以用到其它節(jié)點通信中，降低路由發(fā)現(xiàn)過程時延。節(jié)點在被定義為預測點之前通信過，它的緩存中會有到舊通信對端的路由緩存信息，但新的通信對端和舊通信對端可能不是一個節(jié)點，可能之前緩存的路由信息已經(jīng)過期，所以，預測點提前探測所在網(wǎng)絡拓撲結(jié)構(gòu)是有必要的。

2.2 支持QoS的路由

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

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

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

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

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

A節(jié)點和D節(jié)點通信后，把A定義為預測點，猜測新的通信對端距離它6跳之內(nèi)。A廣播發(fā)送RREQ報文，TTL為6。當TTL減為0時，收到該報文的節(jié)點會向源節(jié)點發(fā)送RREP，收到RREP的中間節(jié)點記錄下相應的路由信息。A節(jié)點可以得到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有數(shù)據(jù)要發(fā)送到節(jié)點F，A節(jié)點在緩存中有2條路徑可以到達F，一條是A-B-C-D-E-F（記為P1），另一條是A-H-I-C-D-E-F（記為P2）。提前探測網(wǎng)絡拓撲結(jié)構(gòu)時，每個節(jié)點會記錄下收到RREQ報文的時間，并根據(jù)自己能量計算轉(zhuǎn)發(fā)RREQ的延時。A節(jié)點比較P1和P2路徑的時延，選擇時延較小的一條路徑作為主路徑，并進行數(shù)據(jù)傳輸，剩余的路徑作為備選路徑。

在此之后，假設P節(jié)點有數(shù)據(jù)要發(fā)送到K，P廣播發(fā)送RREQ報文，M節(jié)點已經(jīng)知道到K節(jié)點的路徑（M-L-K），收到RREQ后，M發(fā)送RREP到P節(jié)點。

圖1 預測點發(fā)現(xiàn)路徑Fig 1 Prediction node discovers path

3 仿真實驗與性能分析

3.1 仿真模型

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

3.2 性能評估參數(shù)

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

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

2）平均時延:定義為從數(shù)據(jù)包產(chǎn)生到數(shù)據(jù)成功傳輸?shù)侥康墓?jié)點所需的時間。

其中，tg為數(shù)據(jù)報產(chǎn)生的時刻，tr為數(shù)據(jù)報到達目的節(jié)點的時刻。

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

4）平均跳數(shù):為分組從源節(jié)點到目的節(jié)點平均需要的跳數(shù)，即轉(zhuǎn)發(fā)數(shù)據(jù)包（fowdpacket）與發(fā)送數(shù)據(jù)包（sendpacket）的比值再加1。計算公式如式（5）所示

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

3.3 仿真結(jié)果與分析

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

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

節(jié)點數(shù)與網(wǎng)絡生存周期的關(guān)系如圖6所示。每個節(jié)點的初始能量為20 J，傳輸功率為1.0 W，接收功率為0.8 W，待機功率為0.1 W，最大移動速度為15 m/s。IDSR協(xié)議的網(wǎng)絡生存周期大于DSR協(xié)議，尤其當節(jié)點數(shù)為20時，IDSR的網(wǎng)絡生存周期遠遠大于DSR。在路由發(fā)現(xiàn)過程中，優(yōu)先選擇剩余能量較多的節(jié)點，降低使用剩余能量較少的節(jié)點可能性，第三等級節(jié)點不參與傳輸數(shù)據(jù)，它只能作為源節(jié)點或目的節(jié)點，避免節(jié)點能量過度消耗。所以，IDSR的網(wǎng)絡生存周期和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 不同速度的平均跳數(shù)Fig 5 Node velocity vs average no.of hops

圖6 不同節(jié)點的網(wǎng)絡生存周期Fig 6 Node velocity vs network life time

4 結(jié)論

IDSR協(xié)議通過預測要發(fā)送數(shù)據(jù)的節(jié)點，提前進行路由發(fā)現(xiàn)過程，可以減少端到端時延;應用小世界理論，限制RREQ報文傳輸?shù)姆秶苊膺^多浪費網(wǎng)絡帶寬資源;以時延和剩余能量作為路由選擇的標準，提供QoS支持。仿真實驗表明:改進后的IDSR協(xié)議在路由開銷、平均時延、分組成功傳輸率、平均跳數(shù)和網(wǎng)絡生存周期方面的性能都優(yōu)于DSR協(xié)議。

［1］李向麗，魏凱敏，呂何平.一種具有小世界特征和沖突避免的DSR協(xié)議［J］.小型微型計算機系統(tǒng)，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］文 浩，林 闖，任豐原，等.無線傳感器網(wǎng)絡的QoS體系結(jié)構(gòu)［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］馬志欣，趙鼎新，謝顯中，等.車載通信網(wǎng)中基于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.