基于泛洪區(qū)域限定的改進DSR

張淵博

（中鐵第一勘察設(shè)計院集團有限公司，陜西西安 710043）

動態(tài)源路由(Dynamic Source Routing,DSR)是移動Ad hoc 網(wǎng) 絡(luò)(Mobile Ad hoc Network,MANET)[1-2]的典型路由，其主要有路由發(fā)現(xiàn)和路由維護兩個階段[3-4]。在路由發(fā)現(xiàn)階段，源節(jié)點通過廣播RREQ，構(gòu)建連通目的節(jié)點的路由。

然而，若盲目地泛洪RREQ 包，增加了網(wǎng)絡(luò)開銷，也容易引起廣播風(fēng)暴問題[5]。針對這些問題，研究人員提出不同的泛洪改進算法，如N 跳泛洪[6]、概率泛洪[7-8]。

該文針對源路由的RREQ 的泛洪問題，提出區(qū)域的路由發(fā)現(xiàn)機制的DSR 路由(Zone-based Route Discovery Mechanism,ZRDM)。ZRDM 路由通過限定泛洪RREQ 的區(qū)域，減少RREQ 包重傳的次數(shù)，進而控制開銷，提高數(shù)據(jù)包傳遞率。仿真結(jié)果表明，提出的ZRDM 路由降低了路由開銷，提高了數(shù)據(jù)包傳遞率。

1 ZRDM路由

ZRDM 路由主要由三個階段構(gòu)成：1）鄰居節(jié)點分類；2）RREQ 泛洪區(qū)域的選定；3）路由發(fā)現(xiàn)。

1.1 鄰居節(jié)點分類

令R表示節(jié)點的傳輸范圍。依據(jù)信號強度[9-10]將其劃分為三個子區(qū)域：1）最外區(qū)域(OutSide Area,OSA)；2）中間區(qū)域(InterMediate Area,IMA)；3）最內(nèi)區(qū)域(InSide Area,ISA)，如圖1 所示。將半徑R至3R/4內(nèi)的環(huán)形區(qū)域作為OSA 區(qū)域；將半徑3R/4 至的環(huán)形區(qū)域作為IMA；將半徑的圓形區(qū)域作為ISA區(qū)域。

圖1 傳輸范圍的區(qū)域劃分

令γi←j表示源節(jié)點si從其鄰居節(jié)點sj接收的信號強度，可通過式(1)計算γi←j：

式中，Pt表示發(fā)射功率；λ為控制參數(shù)；α表示衰減因素；d表示源節(jié)點si與鄰居節(jié)點sj之間的距離。

1.2 RREQ泛洪區(qū)域

傳統(tǒng)的DSR 路由采用泛洪方式[11-12]傳輸RREQ包,如圖2 所示。通過不斷地傳遞RREQ，直到目的節(jié)點接收到RREQ。由于RREQ 包中攜帶了其傳輸路徑，目的節(jié)點可從RREQ 獲取連通源節(jié)點的路徑信息，目的節(jié)點再沿此路徑向源節(jié)點傳輸回復(fù)包(Route Reply,RREP)。最終，通 過RREQ 和RREP 的傳輸構(gòu)建了路由[13-14]。

圖2 DSR路由發(fā)現(xiàn)階段

為了更好地減少控制開銷，將源節(jié)點傳輸方向劃分為四個象限。令(xi,yi)表示源節(jié)點si的位置坐標，將源節(jié)點si的傳輸區(qū)域劃分為Q1、Q2、Q3和Q4，如圖3 所示。

圖3 泛洪區(qū)域的劃分

對于任意鄰居節(jié)點sj∈Ni，如果xj＞xi且yj＞yi，則鄰居節(jié)點sj位于Q1，如式（3）所示：

如果滿足式（4），則鄰居節(jié)點sj位于Q2：

若滿足式（5），則鄰居節(jié)點sj位于Q3：

若滿足式（6），則鄰居節(jié)點sj位于Q4：

為了避免形成路由循環(huán)，減少路由跳數(shù)，源節(jié)點泛洪RREQ 區(qū)域內(nèi)至少包含一個鄰居節(jié)點；若未能包含一個鄰居節(jié)點，就選擇其他區(qū)域傳輸RREQ 包。

1.3 路由發(fā)現(xiàn)策略

首先，源節(jié)點（假定為節(jié)點si）先產(chǎn)生RREQ 數(shù)據(jù)包，其包含自己的序列號、目的地址和源節(jié)點的地址。如果目的節(jié)點在源節(jié)點一跳范圍，則源節(jié)點就直接將RREQ 包傳輸至目的節(jié)點。接收RREQ 后，目的節(jié)點就向源節(jié)點傳輸RREP 包，如圖4 所示。

圖4 傳輸RREQ的流程

若目的節(jié)點不在自己一跳傳輸范圍內(nèi)，源節(jié)點就需向鄰居節(jié)點泛洪RREQ 包。但與DSR 路由不同，ZRDM 路由為了減少參與傳輸RREQ 包和接收RREQ 包的節(jié)點數(shù)，ZRDM 路由并非向所有區(qū)域泛洪RREQ 包，而是依據(jù)算法1 設(shè)置泛洪RREQ 包的區(qū)域。

1.4 算法1

算法1 完成泛洪RREQ 子區(qū)域的選擇。令表示節(jié)點si的泛洪RREQ 的區(qū)域。DSR 是將OSA、IMA 和ISA 三個子區(qū)域都作為泛洪RREQ 的區(qū)域，即ΩFi={O SA,IMA,ISA} 。但是ZRDM 路由并不是固定地將OSA、IMA 和ISA 三個子區(qū)域作為泛洪RREQ 的區(qū)域，而是依據(jù)節(jié)點的分布情況，有目的性地選擇泛洪RREQ 的區(qū)域，如算法1 所示：

算法1：選擇泛洪RREQ 的區(qū)域

如果節(jié)點si的四個區(qū)域(Q1、Q2、Q3和Q4)內(nèi)均有節(jié)點，就只選節(jié)點si的OSA 區(qū)域作為泛洪區(qū)域。具體而言，若滿足式（7），則將OSA 子區(qū)域作為泛洪RREQ 的區(qū)域：

若不滿足式（7），為了保證構(gòu)建穩(wěn)定路由，先將OSA 作為泛洪RREQ 的區(qū)域，然后，再考慮是否將IMA 區(qū)域作為泛洪區(qū)域。如果IMA 區(qū)域內(nèi)四個象限區(qū)域均有節(jié)點，就將IMA 區(qū)域作為泛洪區(qū)域。即再判斷是否滿足式（8）。若滿足式（8），則將IMA 和OSA 區(qū)域共同作為泛洪RREQ 的區(qū)域：

若既不滿足式（7）也不滿足式（8），就將OSA、IMA 和ISA 三個子區(qū)域都作為泛洪RREQ 的區(qū)域,即={O SA,IMA,ISA} 。在這種情況下，ZRDM 路由與DSR 路由一樣，向所有區(qū)域泛洪RREQ 包。

一旦確認了泛洪RREQ 包的子區(qū)域，源節(jié)點si就將區(qū)域的節(jié)點加入廣播重傳鄰居列表(Neighbors to Rebroadcast RREQ,NRR)。只有NRR列表內(nèi)的節(jié)點才可以轉(zhuǎn)發(fā)RREQ 包。

1.5 選擇泛洪區(qū)域的示例

為了更好理解算法1 所選擇的泛洪RREQ 區(qū)域，圖5 給出示例說明。接下來分別考慮了三種情況：Case1、Case2 和Case3。

圖5 泛洪RREQ包的區(qū)域示例(Case1)

Case1：節(jié)點密度較高，如圖5 所示。OSA 區(qū)四個象限內(nèi)均有鄰居節(jié)點。在這種情況，就只將OSA 區(qū)域作為泛洪區(qū)域；只在OSA 區(qū)內(nèi)泛洪RREQ 包。

Case2：節(jié)點密度不高，如圖6 所示。并非OSA區(qū)的四個象限內(nèi)均有鄰居節(jié)點，而IMA 區(qū)的四個象限內(nèi)都有鄰居節(jié)點。在這種情況，只在OSA 區(qū)和IMA 內(nèi)泛洪RREQ 包。

圖6 泛洪RREQ包的區(qū)域示例(Case2)

Case3：節(jié)點密度稀疏，如圖7 所示。OSA 和IMA區(qū)域內(nèi)的Q4象限內(nèi)沒有鄰居節(jié)點。在這種情況下，為了提高建立可靠路由，將OSA、IMA 和ISA 三個區(qū)作為泛洪RREQ 的區(qū)域。

圖7 泛洪RREQ包的區(qū)域示例(Case3)

1.6 鄰居節(jié)點接收RREQ的處理策略

一旦收到RREQ 包后，鄰居節(jié)點從RREQ 包中提取NRR 的信息，并判斷自己是否在NRR 內(nèi)。若不在NRR 列表內(nèi)，就直接丟失RREQ 包；若在NRR 列表內(nèi)，就繼續(xù)判斷是否為目的節(jié)點。若是目的節(jié)點，就直接向該目的節(jié)點傳輸RREQ 包。若不是目的節(jié)點，就利用算法1 選擇泛洪RREQ 包區(qū)域。處理RREQ 包的流程如圖8 所示。

圖8 接收RREQ包后的處理流程

2 數(shù)值分析

2.1 仿真場景

通過NS3 仿真軟件建立仿真平臺[15]。N個節(jié)點隨機分布于300 m×1 500 m 區(qū)域，節(jié)點的傳輸范圍為250 m。具體的仿真參數(shù)如表1 所示。

表1 仿真參數(shù)

為了更好地分析ZRDM 路由性能，選擇文獻[3]提出的可靠DSR 路由(DSR)作為參照，并分析數(shù)據(jù)包傳遞率和歸一化的吞吐量。

2.2 數(shù)據(jù)包傳遞率

首先，分析節(jié)點數(shù)的變化對數(shù)據(jù)包傳遞率的影響，其中，數(shù)據(jù)包傳遞率等于目的節(jié)點成功接收了的數(shù)據(jù)包數(shù)與源節(jié)點發(fā)送的數(shù)據(jù)包數(shù)之比。

從圖9 可知，在節(jié)點數(shù)從20 至40 變化，ZRDM 路由與DSR 路由的數(shù)據(jù)包傳遞率相近，它們的數(shù)據(jù)包傳遞率分別約為88%、86%。原因在于：當節(jié)點數(shù)較少，節(jié)點密度分布較低時，DSR 和ZRDM 路由一樣，都采用OSA、IMA 和ISA 區(qū)作為泛洪RREQ 包區(qū)。

圖9 數(shù)據(jù)包傳遞率

然而，隨著節(jié)點數(shù)的增加，ZRDM 路由的數(shù)據(jù)包傳遞率逐步優(yōu)于DSR 路由。這主要是因為節(jié)點數(shù)的增加，使OSA 區(qū)域內(nèi)的四個象限均有節(jié)點的概率增加，從而實現(xiàn)了只在OSA 區(qū)域內(nèi)泛洪RREQ 包，這就減少了節(jié)點傳遞RREQ 包的次數(shù)，降低了擁塞的概率，增加了數(shù)據(jù)包傳遞率。當節(jié)點數(shù)增加至140時，相比于DSR 路由，ZRDM 路由的數(shù)據(jù)包傳遞率提高約2.78%。

2.3 歸一化路由開銷

分析歸一化路由開銷隨節(jié)點數(shù)的變化情況，如圖10 所示。

圖10 歸一化路由開銷

從圖10 可知，相比于ZRDM 路由，DSR 路由產(chǎn)生更多的RREQ 包。原因在于每個節(jié)點都接收RREQ的復(fù)本。如當節(jié)點數(shù)為80 個時，DSR 路由的歸一化路由開銷近11.93%，而ZRDM 路由的歸一化路由開銷近8.10%，比DSR 路由下降近3.83%。

2.4 節(jié)點移動速度對數(shù)據(jù)包傳遞率的影響

分析節(jié)點移動速度對數(shù)據(jù)包傳遞率的影響,其中節(jié)點移動速度從5 m/s變化至35 m/s，如圖11所示。

圖11 節(jié)點移動速度對數(shù)據(jù)包傳遞率的影響

從圖11 可知，ZRDM 路由和DSR 路由的數(shù)據(jù)包傳遞率均隨節(jié)點移動速度增加而下降。原因在于：節(jié)點移動速度越快，網(wǎng)絡(luò)拓撲變化加快，降低了鏈路的連通時間。相比于DSR 路由，提出的ZRDM 路由提高了數(shù)據(jù)包傳遞率。例如，當節(jié)點移動速度增加至10 m/s，ZRDM 路由的數(shù)據(jù)包傳遞率達到98%，而DSR 路由的數(shù)據(jù)包傳遞率約為88%，提高了近10%。原因在于節(jié)點移動速度的增加,加劇了鏈路斷裂數(shù),這影響了DSR 路由的數(shù)據(jù)包傳遞率。而構(gòu)建ZRDM路由時考慮了鏈路的可靠性。

當節(jié)點移動速度提高至15 m/s 時，ZRDM 路由的數(shù)據(jù)包傳遞率約為83.1%,而DSR 路由的數(shù)據(jù)包傳遞率只有50.1%。相比于DSR 路由,ZRDM 路由將數(shù)據(jù)包傳遞率提升了約65.9%。當節(jié)點移動速度分別提高至20 m/s、25 m/s、30 m/s、35 m/s，ZRDM 和DSR 路由的數(shù)據(jù)包傳遞率迅速下降。但是ZRDM 路由的數(shù)據(jù)包傳遞率的下降速度低于DSR 路由。

2.5 節(jié)點移動速度對平均端到端時延的影響

分析節(jié)點的移動速度對端到端傳輸時延的影響，其中，節(jié)點移動速度從5 m/s至35 m/s變化，如圖12所示。

圖12 節(jié)點移動速度對平均端到端時延的影響

從圖12 可知，在節(jié)點移動速度為10 m/s、20 m/s、25 m/s 和35 m/s 時,提出的ZRDM 路由的平均端到端時延低于DSR 路由的時延。例如，在節(jié)點移動速度為10 m/s 時，ZRDM 路由的平均端到端時延約為7.45 ms，而DSR路由的平均端到端時延達到18.13 ms。相比于DSR 路由，ZRDM 路由的平均端到端時延下降了10.68 ms，并且隨著移動速度的提升，ZRDM 路由在時延性能方面的優(yōu)勢越明顯。

2.6 節(jié)點移動速度對歸一化路由開銷的影響

分析節(jié)點移動速度對歸一化路由開銷的影響，其中節(jié)點移動速度從5 m/s 至35 m/s 變化，如圖13所示。

圖13 節(jié)點移動速度對歸一化路由開銷的影響

當節(jié)點移動速度為5 m/s 時,ZRDM 路由的歸一化路由開銷為8.44%，而DSR 路由的歸一化路由開銷達到17.73%。相比之下，ZRDM 路由將歸一化路由開銷下降了52.40%。當節(jié)點移動速度增加，鏈路斷開的概率也隨之增加，這就增加消息傳輸失敗的次數(shù)。一旦消息傳輸失敗，就需要源節(jié)點重新構(gòu)建新的路由，這就增加了路由開銷。而ZRDM 路由通過限定RREQ 的傳輸區(qū)域，降低了路由開銷。

3 結(jié)論

針對DSR 盲目地泛洪RREQ 包問題，提出基于區(qū)域的路由發(fā)現(xiàn)機制ZRDM。ZRDM 路由先依據(jù)信號強度將鄰居節(jié)點劃分為三個子區(qū)域，并依據(jù)每個子區(qū)域的節(jié)點分布情況，選擇泛洪RREQ 包的區(qū)域，進而控制重播RREQ 的次數(shù)。仿真結(jié)果表明，提出的ZRDM 路由降低了開銷，并提高了數(shù)據(jù)包傳遞率。