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

戴箎

武漢理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 湖北 430063

0 前言

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

圖1 標(biāo)準(zhǔn)DSR協(xié)議路由過程圖

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

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

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

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

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

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

對路由協(xié)議的緩存用路徑緩存和連接緩存來實現(xiàn)?？傮w思想是：全局拓?fù)洳捎寐窂骄彺?，局部拓?fù)洳捎眠B接緩存，網(wǎng)絡(luò)中每個節(jié)點維護(hù)一個局部連接表，讓路由所經(jīng)過的中間節(jié)點掌握半徑為幾跳范圍的局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，局部范圍內(nèi)的節(jié)點分為中心節(jié)點、邊界節(jié)點。對每條全局路由來說，只讓路由上的每個邊界節(jié)點維護(hù)整條路由。邊界節(jié)點到下一跳邊界節(jié)點間的局部路由采用以下辦法：

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

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

2.2.1 協(xié)議改進(jìn)的主要數(shù)據(jù)結(jié)構(gòu)

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

struct Location

{

double x; //x坐標(biāo)

double y; //y坐標(biāo)

}

struct LimFlood

{

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

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

int curHops; //分組所走過的跳數(shù)

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

}

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

2.2.2 局部連接表的建立

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

2.3 路由算法改進(jìn)過程

2.3.1 請求分組算法處理過程

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

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

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

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

2.3.2 路由尋找過程

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

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

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

2.3.3 改進(jìn)后的協(xié)議應(yīng)用

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

圖3 網(wǎng)絡(luò)拓?fù)鋱D舉例

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

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

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

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

3.2 協(xié)議仿真驗證

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

4 結(jié)束語

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

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

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

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

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

[5]鄭少仁,王海濤,趙志峰.Ad Hoc 網(wǎng)絡(luò)技術(shù)[M].北京:人民郵電出版社.2005.