張淵博

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

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

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

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

1 ZRDM路由

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

1.1 鄰居節(jié)點分類

令R表示節(jié)點的傳輸范圍。依據信號強度[9-10]將其劃分為三個子區(qū)域：1）最外區(qū)域(OutSide Area,OSA)；2）中間區(qū)域(InterMediate Area,IMA)；3）最內區(qū)域(InSide Area,ISA)，如圖1 所示。將半徑R至3R/4內的環(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é)點傳輸回復包(Route Reply,RREP)。最終，通 過RREQ 和RREP 的傳輸構建了路由[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ū)域內至少包含一個鄰居節(jié)點；若未能包含一個鄰居節(jié)點，就選擇其他區(qū)域傳輸RREQ 包。

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

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

圖4 傳輸RREQ的流程

若目的節(jié)點不在自己一跳傳輸范圍內，源節(jié)點就需向鄰居節(jié)點泛洪RREQ 包。但與DSR 路由不同，ZRDM 路由為了減少參與傳輸RREQ 包和接收RREQ 包的節(jié)點數(shù)，ZRDM 路由并非向所有區(qū)域泛洪RREQ 包，而是依據算法1 設置泛洪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ū)域，而是依據節(jié)點的分布情況，有目的性地選擇泛洪RREQ 的區(qū)域，如算法1 所示：

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

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

若不滿足式（7），為了保證構建穩(wěn)定路由，先將OSA 作為泛洪RREQ 的區(qū)域，然后，再考慮是否將IMA 區(qū)域作為泛洪區(qū)域。如果IMA 區(qū)域內四個象限區(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列表內的節(jié)點才可以轉發(fā)RREQ 包。

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

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

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

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

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

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

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

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

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

一旦收到RREQ 包后，鄰居節(jié)點從RREQ 包中提取NRR 的信息，并判斷自己是否在NRR 內。若不在NRR 列表內，就直接丟失RREQ 包；若在NRR 列表內，就繼續(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ù)據包傳遞率和歸一化的吞吐量。

2.2 數(shù)據包傳遞率

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

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

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

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

2.3 歸一化路由開銷

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

圖10 歸一化路由開銷

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

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

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

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

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

當節(jié)點移動速度提高至15 m/s 時，ZRDM 路由的數(shù)據包傳遞率約為83.1%,而DSR 路由的數(shù)據包傳遞率只有50.1%。相比于DSR 路由,ZRDM 路由將數(shù)據包傳遞率提升了約65.9%。當節(jié)點移動速度分別提高至20 m/s、25 m/s、30 m/s、35 m/s，ZRDM 和DSR 路由的數(shù)據包傳遞率迅速下降。但是ZRDM 路由的數(shù)據包傳遞率的下降速度低于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é)點重新構建新的路由，這就增加了路由開銷。而ZRDM 路由通過限定RREQ 的傳輸區(qū)域，降低了路由開銷。

3 結論

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