基于地理位置改進的動態源路由協議

戴箎

武漢理工大學計算機科學與技術學院 湖北 430063

0 前言

DSR(動態源路由協議)協議是一種基于源路由的按需路由協議。設計DSR的目的在于創建開銷非常低同時又能快速響應網絡變化的路由協議，以高度反應式的服務確保數據分組在節點移動或者其他網絡條件變化的情況下仍然能夠正確地提交。DSR使用源路由算法，每一個給定路線的數據分組都在報頭帶有完整、有序的此分組必經的節點列表。使用源路由可以保證無環路，轉發或者偵聽分組的節點可以緩存分組中的路由信息以備后用，而且由于要傳輸的數據分組已含有必要的路由信息，中間節點不必保存路由信息。圖1說明了一個應用源路由在自組網中傳輸數據分組的例子。網絡(圖1)中共8個節點，節點S向節點D發送數據分組，節點S建立路由之后，其路由路徑中的轉發節點信息將存入節點 S的路由緩存器中。發送數據分組時，將路由信息寫到數據分組報頭中，源節點按照該路徑轉發直到目的節點，圖中節點S按照S-＞B-＞E-＞F-＞D轉發，中間節點按照數據分組報頭的路由信息轉發分組，當到達節點F時各轉發節點的示意圖如圖中虛線所示。轉發路徑一直存在數據分組的報頭中直至到達目的節點D。

圖1 標準DSR協議路由過程圖

1 基于地理位置的路由思想

為了引入網絡中移動節點的地理位置信息，每個節點需要配置GPS接收裝置。如圖2中當節點S需要向節點D發送或者轉發一個數據分組時，它首先在自己的所有鄰節點中，選擇一個距離目的節點D最近的節點，作為數據分組的下一跳，然后將數據分組傳送給它。該過程一直重復，直到數據分組到達目的節點D或者某個最佳主機。為使網絡中的所有節點能獲得鄰節點的地理位置信息，采用一種簡單的信標發送機制(beaconing)，該機制規定每個節點利用 MAC廣播地址，周期性地向所有鄰節點發送信標(beacon)信號，該信號中包含了節點的身份標識(如 MAC地址)和當前的位置信息。節點的位置用一對4Byte的浮點數來表示，分別代表節點的x, y坐標值。對于某一個節點而言，它可能有多個鄰節點，這些節點之間發送的信標信號有可能發生沖突。為了避免這一機制，采用一種隨機選取信標發送時間間隔的策略。

圖2 基于地理位置定位的路由過程圖

在一定時間間隔內，如果節點沒有收到某一個鄰節點發送的信標信號，則認為該鄰節點已經失效或不在自己的一跳范圍之內，于是將其從自己的鄰居列表中刪除。

2 DSR協議的綜合改進算法

2.1 最優下一跳轉發節點的定義

對路由協議的緩存用路徑緩存和連接緩存來實現。總體思想是：全局拓撲采用路徑緩存，局部拓撲采用連接緩存，網絡中每個節點維護一個局部連接表，讓路由所經過的中間節點掌握半徑為幾跳范圍的局部網絡拓撲結構，局部范圍內的節點分為中心節點、邊界節點。對每條全局路由來說，只讓路由上的每個邊界節點維護整條路由。邊界節點到下一跳邊界節點間的局部路由采用以下辦法：

因為局部連接表內緩存的節點信息帶有地理位置坐標(x,y)，在當前節點的n跳范圍(包括0跳、1跳、2跳…n跳)內找一個滿足最小的值作為路由轉發節點。其中，坐標(x1, y1）、(x2, y2)分別為正在考察的節點、目的節點的地理位置坐標。這個節點我們稱之為當前節點相對于目的節點而取的最優節點。

2.2 協議改進的具體步驟

2.2.1 協議改進的主要數據結構

實現的原DSR協議中移動節點緩存的數據有：路由表緩存(RouteCache)，路由請求表(RequestTable)、分組發送緩存器(SendBuff)、無請求路由應答表等主要數據，要實現上述改進需要添加的主要數據結構如下：

struct Location

{

double x; //x坐標

double y; //y坐標

}

struct LimFlood

{

ID src_id; //節點標示符

ID mac_id; //節點mac值

int curHops; //分組所走過的跳數

Location loc_node; //節點地理位置

}

在系統中，每一個移動節點(MobileNode)能及時通過getLocation函數得到它當前的地理位置坐標值。

2.2.2 局部連接表的建立

在整個網絡中的每個節點都維護著一張局部連接表，連接表通過定期發送maxHops跳范圍內的洪泛包來建立，采用LimFlood結構體封裝分組內容來傳輸節點間局部連接的信息，當節點收到其他節點的 LimFlood包時也就獲得了以該節點為中心的maxHops跳范圍內其他節點的信息。

2.3 路由算法改進過程

2.3.1 請求分組算法處理過程

（1）通過 findRoute函數搜索該節點的路由緩存器，嘗試找出一條路由到達有該分組頭中的目的節點地址域給出的地址。

（2）如果沒有從其路由緩存器中找到所需路由，那么該節點執行路由尋找進程尋找到達整個目的節點地址路由。為了初始化一個路由尋找進程尋找這個目的節點地址，該節點在當前這個分組中的DSR選項頭中增加一個路由請求選項，或者將當前這個分組放入其發送緩存器中，然后通過單獨發送一個包含這個路由請求選項的分組來初始化路由尋找進程。

（3）如果該分組當前不包含路由請求選項，那么這個節點必須有一條路由到達該分組的目的節點地址。將該分組中的源路由初始化為所選定的到達該分組目的節點地址的路由。

（4）將該分組發送到所選源路由的第一跳節點地址，使用路由維護機制決定該跳的可達性。

2.3.2 路由尋找過程

（1）findRoute函數找不到可以到達目的節點的路徑，源節點S須生成到目的節點D的路由請求表RequestTable，運用在S的局部連接表的“鄰接節點”中找到距離D.location最近的節點T。

（2）節點T記錄下S到T的轉發序列當做路由表緩存。

（3）以T為新的源節點來重復步驟(1)直到可以得到到達目的節點 D的轉發路徑，如：發起節點 S、Address[1]、Address[2]… Address[n]、目的節點D。

2.3.3 改進后的協議應用

如圖3所示網絡拓撲結構中，以maxHops=2跳作為半徑，A、C、B、E作為節點S的邊界節點，由于局部范圍內采用了連接緩存(如圖4)，每個節點知道以自己為中心的2跳之內的能到達的最遠距離。按照基于地理位置改進后的 DSR協議，因為我們知道節點S兩跳范圍內能到達的所有節點的地理位置坐標，用公式dist計算，取滿足條件的最小值來作為下一跳的轉發節點(當然路由緩存中存有可行的路由路徑不在考慮之列)。當需要路由發現時，每個節點發送 RREQ前先查找自己的局部連接表，如果目的節點在表內則直接將RREQ發送目的節點；否則將RREQ通過該節點半徑范圍內的最優下一跳轉發節點(選擇的是物理位置上最短的路徑)。當該轉發節點收到RREQ后，再以自己為中心節點來查找自己的連接表，搜索其半徑范圍內是否有目的節點。重復上述過程直到RREQ到目的節點為止。產生的路由只記錄所經過的邊界轉發節點。這樣一直重復下去，可以得到可行的路由路徑。如按原DSR協議從S到D緩存的路徑為SACFGD，現在就有可能是SCGD。

圖3 網絡拓撲圖舉例

圖4 路徑緩存和局部連接緩存

3 協議分析與仿真

3.1 協議正確性分析

路由發現時，在半徑范圍內找最優下一跳轉發節點，因為查找的過程中比較了當前節點半徑為有限 maxHops跳范圍內的所有節點，其中也包括1跳范圍，1跳范圍就是原DSR路由協議的實現了，所以按照改進的協議路由發現機制時一定可以找到存在于網絡內的目的節點。

3.2 協議仿真驗證

傳輸時延是指一個站點從開始發送數據幀到數據幀發送完畢所需要的全部時間，也可是接收站點接收一個數據幀的全部時間。影響因素有路由發現的次數和時間、路由失效次數等。因為每個移動節點用一塊存儲空間來緩存了maxHops跳范圍內的拓撲結構——局部連接表，這樣，當路由發現時，可以從緩存中快速地找到到達目的節點的最優下一跳轉發節點，直至到達目的節點。這樣依靠每個節點的少量物理空間來換取協議的運行時時間減少，可以使整個Ad Hoc網絡的路由開銷顯著減少，因而在平均傳輸時延上改進的協議比原DSR協議會有一定的提高。尤其當節點移動速度變快時，因為原有路徑的斷路或路徑繞遠，原DSR協議適應快速變化的能力有限，這時改進的協議通過搜索局部連接表來替代斷路路由的維護方法比直接向源節點返回一個路由出錯分組RERR以讓源節點啟動新的路由發現的方法要高效很多，將使網絡中的傳輸時延性能得到明顯提高。

4 結束語

DSR是無線自組網絡路由協議中性能比較優越的一種協議，但是對于快速變化的網絡結構難以及時做出反應，造成網絡路由開銷比較大，針對該問題，本文在DSR的基礎上改進全網洪泛的路由發現策略，提出以有限跳作為半徑范圍來洪泛路由請求報文，半徑范圍內節點緩存中保存局部連接拓撲結構，在全局范圍內用地理位置最小值的原則來確定下一跳的最優中轉節點，從而有效改進了路由發現的時延，減少了自組織網絡中節點間端到端數據分組傳輸的平均時延，提高了網絡性能。

[1]屠梓浩,吳榮泉,錢立群等.無線Ad Hoc網絡DSR路由協議的優化設計[J].計算機工程.2009.

[2]于宏毅等著.無線移動自組織網[M].北京:人民郵電出版社.2005.

[3]陳林星,曾曦,曹毅等著.移動Ad Hoc網絡[M].北京:電子工業出版社.2006.

[4]The Network Simulator-ns-2.Project web page available at http://www.isi.edu/nsnam/ns.

[5]鄭少仁,王海濤,趙志峰.Ad Hoc 網絡技術[M].北京:人民郵電出版社.2005.