基于地理位置改進的動態(tài)源路由協(xié)議

戴箎

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

0 前言

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

圖1 標準DSR協(xié)議路由過程圖

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

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

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

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

2 DSR協(xié)議的綜合改進算法

2.1 最優(yōu)下一跳轉發(fā)節(jié)點的定義

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

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

2.2 協(xié)議改進的具體步驟

2.2.1 協(xié)議改進的主要數據結構

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

struct Location

{

double x; //x坐標

double y; //y坐標

}

struct LimFlood

{

ID src_id; //節(jié)點標示符

ID mac_id; //節(jié)點mac值

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

Location loc_node; //節(jié)點地理位置

}

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

2.2.2 局部連接表的建立

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

2.3 路由算法改進過程

2.3.1 請求分組算法處理過程

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

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

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

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

2.3.2 路由尋找過程

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

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

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

2.3.3 改進后的協(xié)議應用

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

圖3 網絡拓撲圖舉例

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

3 協(xié)議分析與仿真

3.1 協(xié)議正確性分析

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

3.2 協(xié)議仿真驗證

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

4 結束語

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

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

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

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

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

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