基于泛洪區域限定的改進DSR

張淵博

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

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

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

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

1 ZRDM路由

ZRDM 路由主要由三個階段構成：1）鄰居節點分類；2）RREQ 泛洪區域的選定；3）路由發現。

1.1 鄰居節點分類

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

圖1 傳輸范圍的區域劃分

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

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

1.2 RREQ泛洪區域

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

圖2 DSR路由發現階段

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

圖3 泛洪區域的劃分

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

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

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

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

為了避免形成路由循環，減少路由跳數，源節點泛洪RREQ 區域內至少包含一個鄰居節點；若未能包含一個鄰居節點，就選擇其他區域傳輸RREQ 包。

1.3 路由發現策略

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

圖4 傳輸RREQ的流程

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

1.4 算法1

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

算法1：選擇泛洪RREQ 的區域

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

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

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

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

1.5 選擇泛洪區域的示例

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

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

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

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

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

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

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

1.6 鄰居節點接收RREQ的處理策略

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

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

2 數值分析

2.1 仿真場景

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

表1 仿真參數

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

2.2 數據包傳遞率

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

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

圖9 數據包傳遞率

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

2.3 歸一化路由開銷

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

圖10 歸一化路由開銷

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

2.4 節點移動速度對數據包傳遞率的影響

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

圖11 節點移動速度對數據包傳遞率的影響

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

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

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

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

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

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

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

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

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

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

3 結論

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