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

李向麗，李超超

（鄭州大學(xué)信息工程學(xué)院，河南鄭州 450001）

0 引言

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

1 DSR協(xié)議概述

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

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

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

1.2 路由維護(hù)

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

2 IDSR協(xié)議

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

2.1 小世界理論與應(yīng)用

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

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

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

2.2 支持QoS的路由

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

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

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

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

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

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

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

圖1 預(yù)測(cè)點(diǎn)發(fā)現(xiàn)路徑Fig 1 Prediction node discovers path

3 仿真實(shí)驗(yàn)與性能分析

3.1 仿真模型

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

3.2 性能評(píng)估參數(shù)

為了對(duì)DSR協(xié)議及改進(jìn)協(xié)議IDSR進(jìn)行性能比較，選取如下5個(gè)評(píng)估參數(shù):

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

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

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

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

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

5）網(wǎng)絡(luò)生存周期:為從網(wǎng)絡(luò)運(yùn)行開始到第一個(gè)節(jié)點(diǎn)死亡的時(shí)間［6］。

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

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

如圖4所示，在速度不斷變化過(guò)程中，IDSR協(xié)議的分組成功傳輸率高于DSR。如圖5所示，IDSR的平均跳數(shù)小于DSR。尤其當(dāng)節(jié)點(diǎn)速度大于15m/s時(shí)，IDSR的平均跳數(shù)遠(yuǎn)遠(yuǎn)小于DSR。IDSR在選擇路由時(shí)，盡量選擇剩余能量多的節(jié)點(diǎn)，這樣不會(huì)因?yàn)槟硞€(gè)節(jié)點(diǎn)過(guò)早消耗完能量而導(dǎo)致整條路徑失效，選擇的路由生存周期長(zhǎng)，可以傳輸更多的數(shù)據(jù)，防止丟包，提高分組成功傳輸率，降低平均跳數(shù)。

節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)生存周期的關(guān)系如圖6所示。每個(gè)節(jié)點(diǎn)的初始能量為20 J，傳輸功率為1.0 W，接收功率為0.8 W，待機(jī)功率為0.1 W，最大移動(dòng)速度為15 m/s。IDSR協(xié)議的網(wǎng)絡(luò)生存周期大于DSR協(xié)議，尤其當(dāng)節(jié)點(diǎn)數(shù)為20時(shí)，IDSR的網(wǎng)絡(luò)生存周期遠(yuǎn)遠(yuǎn)大于DSR。在路由發(fā)現(xiàn)過(guò)程中，優(yōu)先選擇剩余能量較多的節(jié)點(diǎn)，降低使用剩余能量較少的節(jié)點(diǎn)可能性，第三等級(jí)節(jié)點(diǎn)不參與傳輸數(shù)據(jù)，它只能作為源節(jié)點(diǎn)或目的節(jié)點(diǎn)，避免節(jié)點(diǎn)能量過(guò)度消耗。所以，IDSR的網(wǎng)絡(luò)生存周期和DSR相比有明顯提高。

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

圖3 不同速度的平均時(shí)延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é)點(diǎn)的網(wǎng)絡(luò)生存周期Fig 6 Node velocity vs network life time

4 結(jié)論

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

［1］李向麗，魏凱敏，呂何平.一種具有小世界特征和沖突避免的DSR協(xié)議［J］.小型微型計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)的QoS體系結(jié)構(gòu)［J］.計(jì)算機(jī)學(xué)報(bào)，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ī)制的移動(dòng)代理路由策略研究［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，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.