一種用于移動自組網的方向性路由協議

摘要：提出了一種混合式的路由協議AODV－DFR，它不僅具有先驗式及反應式路由協議的特點，而且還融入了某些具有地理位置輔助的路由協議的特性。在路由失敗的情況下，AODV－DFR能在斷點立刻進行方向轉發，快速找到合適的下一跳節點，建立新的路由。大量的仿真實驗證明AODV－DFR路由協議對網絡性能有較大的提高。

關鍵詞：移動自組網； 自組網按需距離矢量路由－DFR； DFR； 方向轉發； 備份路由

中圖分類號：TP393.17文獻標志碼：A

文章編號：1001－3695(2008)04－1193－03

無線Ad hoc網絡是指一組無線移動節點組成的、多跳的、臨時性的、無基礎設施支持的無中心網絡。它可以在任何時刻、任何地點不需要硬件基礎網絡設施的支持，快速構建起一個移動通信網絡。它的建立不依賴于現有的網絡通信設施，使得其應用范圍正逐步擴大，如軍事、災難救助、偏遠地區通信、移動會議等。可以預測，這種技術在未來移動通信的領域中將起到非常重要的作用。節點多且不固定、誤碼率高及帶寬能量有限是設計無線Ad hoc網絡（MANET）路由協議面臨的挑戰。目前，在這個領域已有大量廣泛深入的研究。

1路由協議研究背景

傳統的MANET路由協議一般可被分為兩類，即先驗式路由協議和反應式路由協議。前者每個節點均維護一張包含到達其他所有節點的路由信息的路由表，并根據網絡拓撲的變化隨時更新路由表，所以路由表可以準確地反映網絡的拓撲結構。這種路由協議的時延較小，但是開銷較大、可擴展性差。常用的先驗式路由協議有DSDV(destination－sequenced distance－vector routing protocol，目的序列距離矢量路由)[1]、OLSR(optimized link state routing protocol，優化鏈路狀態路由)[2]等。后者是一種當需要發送數據時才查找路由的算法。在這種路由協議中，節點不需要周期性地維護到其他節點的及時準確的路由信息。當需要向目的節點發送報文時，源節點才在網絡中發起路由查找過程，找到相應的路由。與先驗式路由協議相比，反應式路由協議的開銷較小，但是數據包傳送的時延較大，自適應性差，隨著節點移動性增加，隨機丟失現象也越嚴重[3]。常用的反應式路由協議有AODV(Ad hoc on－demand distance vector routing protocol，Ad hoc按需距離矢量路由) [4]、DSR(dynamic source routing protocol，動態源路由)[5]等。

相對于傳統路由協議而言，基于地理位置信息輔助的路由協議，如GPSR(greedy perimeter stateless routing，貪婪無狀態周邊路由)[6]更適合節點高速移動的無線Ad hoc網絡。使用這種協議的節點僅需要根據鄰居節點和目的節點的位置信息就可以發送數據。大多數基于地理位置輔助的路由協議均采用貪婪轉發的方式，即選擇離目的節點最近的鄰居節點作為下一跳節點。從路由開銷角度來看，基于地理位置輔助的路由協議具有很好的可擴展性，因為它僅僅需要知道鄰居節點和目的節點的坐標信息，而無須建立端到端的路徑。然而，在空洞(void)[6]存在的情況下，貪婪轉發會失效。為了產生正確的路由，當這種情況發生時，基于地理位置信息輔助的路由協議就會觸發周邊算法(perimeter algorithm)。周邊算法雖然能在一定程度上解決空洞帶來的問題，但是它卻會使數據包走一條很長的路，占用更多的信道時間，甚至導致了路由環路的產生，使網絡變得更加糟糕。

為了平衡優化無線Ad hoc網絡的性能，目前已有一些混合式路由協議相繼被提出，如ADV(adaptive distance vector routing protocol，自適應距離向量路由)[3]協議等。ADV是通過反應式建立路由，通過先驗式的方式進行路由更新。相對于單一的路由協議，ADV能獲得更好的性能。

本文提出了一種混合路由協議AODV－DFR，它可以說成是具有方向轉發功能的AODV路由協議。AODV－DFR不僅融入了先驗式和反應式路由協議的優點，同時還引入了基于地理位置信息輔助路由協議的某些特性。AODV－DFR與ADV的路由發現和路由維護過程很相似，它們最大的區別在于路由失敗時，AODV－DFR通過方向選擇新鄰居節點重建路由并采用魚眼技術fisheye[7]的方法降低路由開銷。

2AODV－DFR

2．1AODV－DFR概述

AODV－DFR融合了先驗式和反應式路由協議的優點，以反應式的方式進行路由發現，而以先驗式的方式進行路由維護。AODV－DFR的路由發現類似于AODV：假如源節點沒有到目的節點的路由，則采用洪泛方式廣播路由請求去發現路由，目的節點接收到路由請求后，則返回一個路由應答給源節點。除此之外，AODV－DFR同時也引入了一些新的特性。目的節點發送路由應答后，開始定期向周圍節點廣播更新包，以表示它的存在。鄰居節點接收到更新包后，刷新其到目的節點的路由表條目。依次地，每個節點都周期性地廣播其到那些有數據接收的目的節點的路由信息給鄰居節點。這樣，在源節點發起路由請求后，一個先驗式的路由更新過程也隨后建立，用于在初始路由失效的情況下提供備份路由。在未接收到任何數據包的一段時間之后，目的節點需要終止更新包的廣播。

AODV－DFR的路由更新包主要包括目的節點ID、發送此更新包的節點ID及其坐標信息。這里所指的目的節點是那些有數據需要接收的目的節點，而非像傳統的先驗式路由所指的所有節點。另外，AODV－DFR也采用了魚眼技術，根據到目的節點的距離決定更新包交互的頻率，在初始路由失效時在斷點進行方向轉發。

2．2路由表和方向緩存

AODV－DFR繼承了距離向量算法的特性，每個中間節點選擇具有到目的節點最小跳數的先序節點作為路由的下一跳。中間節點除了記錄先序節點的ID，同時也記錄到先序節點的方向。方向是由更新包中先序節點的坐標及本節點的坐標計算而得的。在GPS無效的情況下，可以采用虛擬坐標系統獲得本地坐標。在本文中，筆者假定GPS總是有效的。

假如從多個節點接收到同一目的節點，且具有相同跳數、序列號的更新包時，需要通過向量計算獲得更加精確的方向。如圖1所示，節點A從B和C處接收兩個具有相同跳數、序列號的更新包。

為了運行AODV－DFR，每個節點擁有兩個數據結構，即方向緩存表和路由表。方向緩存表記錄引起相應目的節點路由條目更新的更新包來自的方向，它們需要不斷地被更新，否則超時廢棄。路由表提供完整的路由信息，如下一跳節點ID、跳數及超時等。超時時間可由鄰居節點的移動速度決定。速度越快，超時時間也短；反之亦然。移動速度可由兩次接收同一鄰居節點的更新包的時間間隔及其坐標變化來估算。通常，路由表在以下兩種情況被更新：有效的更新包到達或是初始路由失敗，通過方向選擇重新建立路由。

2．3數據包轉發

當路由失效時，AODV－DFR能在斷點快速有效地重建路由。數據包通常都是轉發給到目的節點跳數最小的鄰居節點。如果此鄰居節點移出了傳輸范圍，則數據包必須重新路由。節點首先訪問方向緩存表，根據序列號、跳數及方向選擇最佳的鄰居節點作為下一跳，重新建立路由。如果有多個鄰居節點作為下一跳候選節點，則需要選擇與當前目的節點方向夾角最小的鄰居節點。如果沒有合適的鄰居節點，數據包將被丟棄，同時向上游節點廣播error包以示此路不通。接收到error包的節點也將從鄰居路由緩存表選擇最佳的鄰居節點重新建立路由，如此遞歸。數據包的發送流程如下：

a) 節點需要外發數據，先訪問路由表，查找相應路由。

b) 如果有路由，則直接轉發數據包給路由表中下一跳節點;否則進行方向轉發，訪問方向緩存表，在候選鄰居節點中尋找與當前失效路由方向夾角最小的鄰居節點。

c)如果存在這樣的候選鄰居節點，則用它作為下一跳節點更新路由表，然后轉發數據包；如果沒有任何有效候選鄰居節點，則丟棄數據包，并發送error包通知其上游節點此路不通。

d) 上游節點在接收到error包后，認為先序節點斷路，也進行方向轉發。

2．4控制路由開銷

由于更新包包含所有到有數據需要接收的目的節點的路由信息，當流的數目越大，路由開銷則也越大。為了降低路由開銷，增加可擴展性， AODV－DFR采用了根據節點到那些目的節點的跳數調整其發送更新包的頻率。跳數越小，發送越頻繁。這種方法類似于 FSR(fisheye state routing，魚眼狀態路由)[7]。

3仿真結果及分析

本文在仿真工具NS－2[8]上實現AODV－DFR算法。仿真的MAC層為802.11b DCF協議，帶寬為2 Mbps，傳輸范圍為250 m，仿真時間為200 s。為了多角度評估AODV－DFR的性能，筆者選取AODV[4]、ADV[3]及GPSR[6]三種路由協議作為參照比較。在本文中，假定GPS服務在NS－2中有效。

為了更具真實性，本文采用美國德克薩斯州休斯敦Afton Oaks area的真實城市街道作為仿真場景[9]，如圖2所示。250個節點在1 900 m×1 900 m區域內作random trip mobility模型運動[10]，每個節點只能沿著街道移動，并均以最大速率（5，10，15或20 m/s）運動，暫停時間為0。CBR業務流分別為20，40，60，80條。本文選取了最具代表性的一組結果，見圖3，運行了10個隨機種子，取平均值。高負載下，所有協議的性能均隨速度的遞增而下降。

圖3(a)是投遞率的比較。由于街道的影響，AODV協議頻繁斷路，觸發路由更新，導致其投遞率下降。對于GPSR來說，其投遞率下降較大的主要原因是由于街道及建筑物的影響及節點的高移動性造成網絡擁塞而引起的。它們加大了MAC層的沖突概率，導致大量hello包丟失，無法正常地與鄰居節點進行交互，產生空洞，從而觸發周邊算法，而周邊算法正如第1章所述，會降低協議的性能。負載越大速度越快，性能下降得就越多。對于ADV來說，由于街道及建筑物的影響，節點斷路后通過與鄰居節點交互重新發現路由的效果也不理想。AODV－DFR雖然也在一定程度上受到街道及建筑物的影響，但是其性能在各速度下均要大大優于其他三種協議。

圖3(b)展示了路由開銷的情況。由于街道的影響，各節點間斷路頻繁，AODV與ADV協議需要發送大量的路由控制包重新發現路由，因而它們的路由開銷很大。GPSR的開銷比AODV－DFR的小，主要是由于在統計GPSR時，未考慮地理位置信息服務的開銷。

圖3(c)是平均端到端延遲。由于街道的影響，AODV頻繁斷路，需要重新發送路由控制包建立新路由，而GPSR會因空洞的增多而性能下降，其平均延遲較大。對于ADV來說，它的平均延遲很大的原因主要在于中間節點在數據包未發送成功的情況下，會緩存此數據包直到新路由建立，重發一次。而AODV－DFR的方向轉發可以提供備份路由，數據包不需要等待，所以平均延遲較小。

4結束語

本文提出了一種混合路由協議AODV－DFR，它融合了先驗式和反應式路由協議的優點。通過理論和仿真實驗分析，AODV－DFR要明顯優于其他三種路由協議，即先驗式路由協議AODV、基于地理位置信息輔助的路由協議GPSR和混合路由協議ADV，尤其是在高速、高負載的城市街道場景下。



參考文獻：

[1]PERKINS C， BHAGWAT P. Highly dynamic destination－sequenced distance－vector routing (DSDV) for mobile computers[C]//Proc of ACM SIGCOMM’94. 1994.

［2]CLAUSEN T， JACQUET P. RFC 3626， Optimized link state routing protocol (OLSR)[S].2003.

［3]BOPPANA R， KONDURU S. An adaptive distance vector routing algorithm for mobile Ad hoc networks[C]// Proc of IEEE INFOCOM. 2001.

［4]PERKINS C E， ROYER E M. Ad hoc on－demand distance vector routing[C]//Proc of IEEE WMCSA’99. 1999.

［5]JOHNSON D B， MALTZ D A. Dynamic source routing in Ad hoc wireless networks[M]. New York:kluwer Academic Publishers，1996. H， Chapter 5.

［6]KARP B， KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[C]//Proc of ACM Mobi－Com’00. 2000.

［7]PEI G， GERLA M， CHEN T M. Fisheye state routing in mobile Ad hoc networks[C]//Proc of ICDCS 2000 Workshops. 2000.

［8]The network simulator－ ns2[EB/OL]. http://www.isi.edu/nsnam/ns.

［9]SAHA A K， JOHNSON D B. Modeling mobility for vehicular Ad hoc networks[M].[S.l.]: ACM Vanet， 2004.

［10]BOUDEC J Y L， VOJNOVIC M. Perfect simulation and stationarity of a class of mobility models[C]//Proc of IEEE INFOCOM. 2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”