張鵬明,李洪烈,林成浴

(海軍航空工程學院青島分院,山東 青島 266041)

1 引 言

20世紀七八十年代提出的Ad Hoc[1]網(wǎng)絡(luò)最開始主要用于軍事目的,其出發(fā)點是在無基礎(chǔ)設(shè)施的戰(zhàn)場環(huán)境下迅速構(gòu)建通信網(wǎng)絡(luò)。Ad Hoc網(wǎng)絡(luò)沒有中心節(jié)點,任何節(jié)點均可自由移動、進出網(wǎng)絡(luò),同時每個節(jié)點還具有路由功能,中繼轉(zhuǎn)發(fā)數(shù)據(jù)至目的節(jié)點。

由于無中心、任何節(jié)點均可自由移動,因此Ad Hoc網(wǎng)絡(luò)具有較強的抗毀性、拓撲動態(tài)變化、可多跳覆蓋等特點,故一經(jīng)提出,立即成為軍事和民用研究的熱點。近年來,民用方面Ad Hoc網(wǎng)絡(luò)的研究主要集中在民航[2]、智能交通系統(tǒng)[3]和傳感器網(wǎng)絡(luò)[4]等方向,軍事方面則主要集中在移動自組網(wǎng)[5]、傳感器網(wǎng)絡(luò)[6]等方向。

移動自組網(wǎng)(Mobile Ad Hoc Network,MANET)是一種典型的Ad Hoc網(wǎng)絡(luò),由一些移動的無線節(jié)點組成無線通信網(wǎng)絡(luò),可廣泛用于軍事通信、抗災救災等場合。由于移動自組網(wǎng)節(jié)點的移動特性會使網(wǎng)絡(luò)拓撲頻繁變化,導致已有的路由經(jīng)常失效,因此路由協(xié)議的設(shè)計和選取是關(guān)鍵。目前,對移動自組網(wǎng)的研究熱點主要集中在路由協(xié)議上,本文將對此進行綜述。

2 移動自組網(wǎng)路由協(xié)議

2.1 移動自組網(wǎng)路由協(xié)議的基本設(shè)計

由于移動自組網(wǎng)的動態(tài)特性,尤其是應用在運輸和航空等高動態(tài)場合,其對路由協(xié)議的要求更加嚴格,所以必須設(shè)計新的路由算法。路由算法的基本設(shè)計原則通常是下列原則的一個或多個。

(1)優(yōu)化

優(yōu)化指路由算法選擇最佳路徑的能力,根據(jù)設(shè)計的metric值來計算。移動自組網(wǎng)由眾多自由、移動的節(jié)點組成,要求具有優(yōu)化的算法。

(2)快速收斂

收斂是指網(wǎng)絡(luò)中的所有節(jié)點對最佳路徑達成一致的過程。移動自組網(wǎng)的節(jié)點可自由出入網(wǎng)絡(luò),而且節(jié)點自由移動,由此帶來路由途徑的不斷更新,所以要求路由算法必須具有快速收斂的能力;否則,會使網(wǎng)絡(luò)產(chǎn)生路由環(huán)或癱瘓。

(3)有效地控制開銷

控制開銷是指建立路由和傳輸數(shù)據(jù)的管理負載。移動自組網(wǎng)的無線傳輸帶寬有限,控制開銷分組不可避免地要消耗掉一部分帶寬資源,同時過大的控制開銷也會消耗網(wǎng)絡(luò)傳輸數(shù)據(jù)的能力,因此必須盡可能地減小控制開銷。

(4)健壯 、穩(wěn)定

健壯、穩(wěn)定是指路由算法在出現(xiàn)不正?；虿豢深A見事件的情況下仍能正常工作。移動自組網(wǎng)工作在無線移動模式,信道情況比較復雜,出現(xiàn)突發(fā)事件的概率比較大,對路由算法的健壯、穩(wěn)定要求更加迫切。

(5)靈活

路由算法必須迅速、準確地適應各種網(wǎng)絡(luò)環(huán)境。移動自組網(wǎng)的網(wǎng)絡(luò)環(huán)境可能隨時在變,進出網(wǎng)絡(luò)的各自由節(jié)點的情況也不一定完全一致。因此,路由算法的設(shè)計必須靈活,能夠自動適應諸如帶寬、延遲等不一致的情況。

良好的路由協(xié)議能夠以較低的計算負擔、網(wǎng)絡(luò)控制開銷、通信負載、能量消耗、通信時延獲得路由信息,因此設(shè)計路由協(xié)議時也往往從這幾方面著手,目前對移動自組網(wǎng)路由算法的設(shè)計思路主要有修改現(xiàn)有的常規(guī)路由協(xié)議以適應不同的應用環(huán)境、采用按需的原則設(shè)計路由或基于QoS(Quality of Service)設(shè)計路由3種。

2.2 移動自組網(wǎng)的路由協(xié)議分類

目前已經(jīng)提出的移動自組網(wǎng)的路由協(xié)議種類繁多,劃分的標準也不盡相同,通常有以下兩種:按照網(wǎng)絡(luò)的邏輯結(jié)構(gòu),可分為平面路由和分層路由;按照設(shè)計路由時所選取的信息類型,可分為基于拓撲結(jié)構(gòu)的路由協(xié)議和基于地理定位信息的路由協(xié)議。在此僅按后者進行分類。

(1)基于拓撲結(jié)構(gòu)的路由協(xié)議

基于拓撲結(jié)構(gòu)的路由協(xié)議其路由選取的信息是基于網(wǎng)絡(luò)節(jié)點之間的拓撲鏈接,按照發(fā)現(xiàn)路由的方式不同,又可分為主動型、按需路由型和混合型3種。

主動型路由協(xié)議要求網(wǎng)絡(luò)中的每個節(jié)點都維護一張到其他節(jié)點的相對穩(wěn)定的最新路由表,路由表由網(wǎng)絡(luò)周期性地廣播路由控制數(shù)據(jù)進行更新,路由表在節(jié)點通信之前就已經(jīng)建立。因此,主動型路由協(xié)議在發(fā)送數(shù)據(jù)時,只要目的節(jié)點存在于路由表中,查找建立路由所需的時延就很小。但是,隨著網(wǎng)絡(luò)規(guī)模的擴大,路由表的信息急劇增加,同時由于主動型路由協(xié)議需要周期性地更新路由信息來維護路由表,由此帶來網(wǎng)絡(luò)的控制開銷太大,動態(tài)變化的網(wǎng)絡(luò)拓撲更可能使花費較高代價得到的路由信息變成無用信息,從而使路由協(xié)議始終處于不收斂狀態(tài),因此,該類協(xié)議不大適合于移動自組網(wǎng),一般用在實時和有QoS要求的網(wǎng)絡(luò)通信。目前,典型的主動型路由協(xié)議有DSDV、OLSR等。

按需路由型協(xié)議只有在網(wǎng)絡(luò)節(jié)點需要發(fā)送數(shù)據(jù)時才開始路由查找,經(jīng)查找建立路由后,由路由維護程序維護路由,直到數(shù)據(jù)傳輸完畢,任務完成后才拆除路由。如果傳輸數(shù)據(jù)過程中發(fā)生路由中斷,則重新開始路由查找。由于只在有數(shù)據(jù)發(fā)送需求時才廣播控制數(shù)據(jù),網(wǎng)絡(luò)的控制開銷大大減少,節(jié)省了一定的網(wǎng)絡(luò)資源。按需路由協(xié)議具有路由發(fā)現(xiàn)和動態(tài)維護路由的功能,因此能夠滿足網(wǎng)絡(luò)的一般動態(tài)要求。但是,由于采用的是源驅(qū)動的路由機制,發(fā)送數(shù)據(jù)分組時,必須先開始路由查找,再建立路由,會造成一定的時延。在路由查找過程中通常采用全網(wǎng)泛洪方式進行搜索,在一定程度上減弱了其優(yōu)點。目前,典型的按需型路由協(xié)議有AODV、DSR等。

混合型路由協(xié)議汲取主動型路由協(xié)議和按需型路由協(xié)議的優(yōu)點,利用分層路由協(xié)議將網(wǎng)絡(luò)劃分為兩層,即內(nèi)層網(wǎng)絡(luò)節(jié)點維護路由表和外層網(wǎng)絡(luò)節(jié)點采用按需路由協(xié)議。在路由維護階段更新內(nèi)層網(wǎng)絡(luò)維護的路由表。該類協(xié)議能較好地利用上述兩種路由協(xié)議的優(yōu)點,但是節(jié)點的計算負載較大,由此帶來網(wǎng)絡(luò)的整體能耗較高,如何開發(fā)更好的混合型路由協(xié)議以適應大規(guī)模移動自組織網(wǎng)絡(luò)的需求將是以后研究的一個重點。目前,典型的混合型路由協(xié)議有ZRP、CEDAR 等。

(2)基于地理定位信息的路由協(xié)議

與基于拓撲結(jié)構(gòu)的路由協(xié)議不同,基于地理定位信息的路由協(xié)議其路由選取是基于地理定位坐標的。這種類型的路由協(xié)議更適合移動自組網(wǎng)的高動態(tài)要求。

基于地理定位信息的路由協(xié)議要求網(wǎng)絡(luò)中每個節(jié)點維護并周期性地更新一張位置信息表,表中包含所有鄰居節(jié)點的地理定位信息。當節(jié)點運動時,發(fā)送捎帶自身新位置的控制信息到所有鄰居節(jié)點,鄰居節(jié)點據(jù)此更新自己的位置信息表。由于建立位置信息表的信息量比建立鏈路查找表要小得多,所以可以有效地減少網(wǎng)絡(luò)的控制開銷。同時,基于地理定位信息的路由協(xié)議沒有普通路由協(xié)議所存在的收斂問題,因此比較適合高動態(tài)的通信網(wǎng)絡(luò)。

3 基于地理定位信息的移動自組網(wǎng)路由協(xié)議

目前,典型的基于地理定位信息的移動自組網(wǎng)路由協(xié)議有以下幾種。

3.1 LAR

LAR(Location Aided Routing)[7]協(xié)議是基于DSR(Dynamic Source Routing)路由協(xié)議的一種按需路由協(xié)議,其主要特點是在所有數(shù)據(jù)包中均發(fā)送地理定位信息,從而有效地利用節(jié)點的地理位置信息來減少路由發(fā)現(xiàn)過程的網(wǎng)絡(luò)控制開銷。LAR假定網(wǎng)絡(luò)中的節(jié)點知道自身的地理定位信息并且已經(jīng)獲得了目的節(jié)點的地理定位信息。基于以上兩點,LAR協(xié)議將目標節(jié)點的查找范圍限制為網(wǎng)絡(luò)中的某一部分區(qū)域,即請求區(qū)域(Request Zone)。只有在請求區(qū)域內(nèi)的節(jié)點才允許轉(zhuǎn)發(fā)RREQ消息。即:當路由中間節(jié)點收到RREQ包時,該節(jié)點首先檢查它是否屬于該RREQ消息所定義的請求區(qū)域,如果屬于,判斷自身是否是目的節(jié)點,是目的節(jié)點則返回RREP包,包中含有此刻的時間信息和該節(jié)點的地理定位信息,不是則轉(zhuǎn)發(fā)該RREQ包;如果不在請求區(qū)域內(nèi),則丟棄該RREQ包。如果RREQ包中設(shè)定的時間用完而該包仍未被送達目的節(jié)點,則轉(zhuǎn)發(fā)該RREQ包的最后節(jié)點向源節(jié)點發(fā)送RERR包,通知源節(jié)點此次路由查找失敗,由源節(jié)點再次發(fā)起路由查找。

LAR協(xié)議判斷節(jié)點是否在請求區(qū)域內(nèi)有兩種策略:區(qū)域策略和距離策略。區(qū)域策略假定源節(jié)點 S已經(jīng)知道了目的節(jié)點D在t0時刻的地理定位信息、平均移動速度v,從而可以算出在 t1時刻目標節(jié)點D所在的期望區(qū)域是以D在上一時刻t0所在的方位為圓心、v(t1-t0)為半徑的圓形區(qū)域。在路由查找過程,只有在請求區(qū)域內(nèi)的節(jié)點才參與路由查找,轉(zhuǎn)發(fā)RREQ消息;距離策略根據(jù)中間節(jié)點和目的節(jié)點的距離作為是否轉(zhuǎn)發(fā)RREQ消息的判決依據(jù)。在路由查找階段,假設(shè)中間節(jié)點i判定自己屬于請求區(qū)域,到目的節(jié)點D的距離為Disti,轉(zhuǎn)發(fā)RREQ的上一節(jié)點 S到目的節(jié)點D的距離為Dists,只有滿足α Dists+β≥Disti時中間節(jié)點i才轉(zhuǎn)發(fā)該RREQ包(α、β為待定參數(shù))。

綜上所述,LAR協(xié)議由于將路由查找限制在請求區(qū)中,因而相對于普通泛洪路由具有路由查找快、控制開銷小的特點,由于其只提出策略,并不限于某一確定的協(xié)議,因而適用范圍廣。但是必須要有額外獲取地理定位信息的設(shè)備予以支持,而且以上兩種策略都只是源節(jié)點對目的節(jié)點期望區(qū)域的估計。實際上,目標節(jié)點可能由于運動情況突變,并不在期望區(qū)域內(nèi),源節(jié)點也有可能一開始并未獲得目的節(jié)點的地理定位信息,這兩種情況均會造成源節(jié)點初次路由查找失敗,從而迫使源節(jié)點采用泛洪的方式在整個網(wǎng)絡(luò)中進行路由查找。泛洪方式會極大地增加網(wǎng)絡(luò)開銷,降低網(wǎng)絡(luò)效率。因此,盡可能多地獲得目的節(jié)點的移動信息,合理有效地設(shè)置請求區(qū)域、選擇最佳位置和數(shù)量的路由節(jié)點是LAR協(xié)議的關(guān)鍵所在。

目前,對LAR協(xié)議的研究主要集中在優(yōu)化請求區(qū)域、有效選取參與路由的中間節(jié)點這兩個方向,其本質(zhì)都是通過減少參與路由的中間節(jié)點、提高路由相對穩(wěn)定性進而提高效率。常采用的有基于概率特性、基于跳數(shù)、基于距離、基于位置、基于簇等改進方式。

牟強等人[8]提出了一種IM-LAR算法,通過在RREP包中將地理定位信息根據(jù)回送節(jié)點的信息進行調(diào)整,從而擴大了路由選擇的區(qū)域,仿真表明該算法能有效地改進LAR協(xié)議因為請求區(qū)域設(shè)置過小而漏選最佳路由的缺陷,從而減少路由查找階段RREQ包的轉(zhuǎn)發(fā)次數(shù),但同時該算法也會增大路由請求泛洪方式發(fā)生的概率。Hung[9]等提出了一種基于節(jié)點運動方向預測的DLAR協(xié)議,選擇與源節(jié)點運動方向一致或相似性最好的節(jié)點作為路由節(jié)點,以提高路由相對穩(wěn)定性。Nabendu Chaki[10]采用Dijkstra算法尋找最短路由路徑,在中間節(jié)點找不到下一跳鄰居節(jié)點時,增加該節(jié)點不在請求區(qū)域內(nèi)的鄰居節(jié)點以建立新的路由,從而提高了路由的相對穩(wěn)定性。Neelesh Gupta[11]等則從節(jié)省能量的角度引入GAF(Geographic Adaptive Fidelity)算法改進了LAR協(xié)議。

引進概率算法是改進LAR協(xié)議的另一種常用方式。由于LAR協(xié)議采用區(qū)域策略時,在節(jié)點密度較高的區(qū)域常常會有大量多余的節(jié)點進行轉(zhuǎn)發(fā),因而降低了網(wǎng)絡(luò)的可達性。基于概率的算法通過設(shè)置自適應轉(zhuǎn)發(fā)概率的機制可以有效地減少節(jié)點密度高的區(qū)域的轉(zhuǎn)發(fā)節(jié)點數(shù)量,而且并不影響網(wǎng)絡(luò)的可達性。其基本原理是:當節(jié)點收到RREQ包時,先判斷該包是否以前轉(zhuǎn)發(fā)過,若已經(jīng)轉(zhuǎn)發(fā)過,則丟棄該包;若沒有,則以概率Pt來轉(zhuǎn)發(fā)該包,每個節(jié)點最多只允許轉(zhuǎn)發(fā)該包一次。源節(jié)點是RREQ包的發(fā)出者,Pt通常設(shè)為1;中間節(jié)點Pt通常取0到1之間的某一個固定值,也可以通過概率分布函數(shù)來動態(tài)地選取。

基于概率的算法最早由Haas[12]等人提出,該算法在路由查找階段選取固定的概率 Pt來決定節(jié)點是否轉(zhuǎn)發(fā)RREQ包。不久Haas等人又提出在連續(xù)使用Pt<1之前將前h跳節(jié)點的Pt設(shè)為1,結(jié)果表明該協(xié)議能較普通泛洪協(xié)議減少35%的負載。H.Al-Bahadili等人將LAR協(xié)議的區(qū)域策略和基于概率的算法相結(jié)合,構(gòu)成一種適用于移動自組網(wǎng)的路由新算法LAR-1P,仿真表明該算法可以在不影響網(wǎng)絡(luò)可達性的情況下減少請求區(qū)域中的轉(zhuǎn)發(fā)節(jié)點數(shù)量。隨后他們[13]對該協(xié)議的詳細性能進行了分析,證明了LAR-1P協(xié)議在節(jié)點密度高的區(qū)域確實能有效減少轉(zhuǎn)發(fā)的節(jié)點數(shù)量,而在節(jié)點密度低的區(qū)域則和LAR區(qū)域策略的性能相似。

基于概率特性、基于跳數(shù)、基于距離、基于位置、基于簇等改進方式的實質(zhì)都是在與如何選擇參與路由的中間節(jié)點,中間節(jié)點選得過多,則會造成較大的網(wǎng)絡(luò)負擔;選得過少,又容易迫使路由進入泛洪方式,從而降低效率。目前研究方向主要集中在基于距離、基于位置和基于概率特性這3種方式。如何合理選取參與路由的中間節(jié)點仍將是LAR協(xié)議今后研究的重點。

3.2 RDMAR

相對距離微觀發(fā)現(xiàn)路由(Relative Distance Microdiscovery Ad Hoc Routing Protocol,RDMAR)協(xié)議是由George Aggelou[14]等人提出的一種按需路由協(xié)議,其核心思想是在兩個節(jié)點之間進行路由查找時,采用迭代算法根據(jù)平均節(jié)點移動速度和節(jié)點的路由信息距離上一次更新的時間估計兩者之間的當前相對距離(Relative Distance,RD),由此限制那些在源節(jié)點為圓心、RD為最大半徑的圓內(nèi)節(jié)點才可轉(zhuǎn)發(fā) RREQ包,從而比普通泛洪協(xié)議減少了轉(zhuǎn)發(fā)RREQ包的節(jié)點數(shù)量,從而減小了路由負載和擁塞的可能。

按照該協(xié)議,每個節(jié)點維護一張包含該節(jié)點所有可達目的節(jié)點的路由表,每個可達目的節(jié)點的路由信息包括:當前節(jié)點所能到達的目的節(jié)點的下一跳節(jié)點的路由區(qū)域、當前節(jié)點與目的節(jié)點的相對距離的估計值(跳數(shù))、當前節(jié)點關(guān)于目的節(jié)點路由信息的上一次更新時間(Time-Last-Update,TLU)、當前節(jié)點到目的節(jié)點有效路由的剩余時間、當前節(jié)點到目的節(jié)點路由是否有效的標志這5項內(nèi)容。協(xié)議由路由查找和路由維護兩部分組成。

(1)路由查找

當網(wǎng)絡(luò)中某一節(jié)點需要查找到目的節(jié)點的路由卻沒有有效路由時,該節(jié)點根據(jù)路由表內(nèi)上一次到目的節(jié)點的距離、路由表上一次更新的時間、目的節(jié)點的平均移動速度,計算出當前時刻該節(jié)點與目的節(jié)點的相對距離,由相對距離得出TTL(Time to Live)值,從而將轉(zhuǎn)發(fā)RREQ文件的節(jié)點限制在以自己為圓心、半徑為與相對距離有關(guān)的RDM-Radius的圓形范圍內(nèi)。當RDM-Radius為全網(wǎng)絡(luò)尺寸時,等同泛洪查找。RREQ包在查找區(qū)域內(nèi)逐跳轉(zhuǎn)發(fā),每個收到RREQ的節(jié)點在自己的路由表內(nèi)建立一條到RREQ源節(jié)點的反向路徑,并在RREQ包中添加本節(jié)點的路由信息,設(shè)置下一跳信息,繼續(xù)轉(zhuǎn)發(fā)RREQ包,直至RREQ包到達目的節(jié)點。

只有當RREQ包到達目的節(jié)點后,目的節(jié)點才產(chǎn)生應答RREP包。路由查找過程中的任何中間節(jié)點都不能產(chǎn)生RREP包,由此可以保證RDMAR協(xié)議的路由信息不會過時,同時也減小了網(wǎng)絡(luò)開銷。RREP文件沿各個節(jié)點記錄的到源節(jié)點的反向路徑回傳至發(fā)起路由查找節(jié)點,RREP中攜帶發(fā)起路由查找的節(jié)點到目的節(jié)點的路由信息。中間節(jié)點在轉(zhuǎn)發(fā)RREP包至路由查找發(fā)起節(jié)點的同時,也將RREP包發(fā)給那些曾轉(zhuǎn)發(fā)RREQ包到目的節(jié)點卻未收到應答的節(jié)點。

在路由建立過程中,如果某一節(jié)點發(fā)現(xiàn)到目的節(jié)點的新路由,該節(jié)點將自己路由表中的已有路由信息的RD值與新路由比較,若新路由RD值的跳數(shù)比原來的小,則將新路由更新到自己的路由表中,如果原先路由表中沒有到目的節(jié)點的路由,則自動將該路由添加到自己的路由表中。

(2)路由維護

中間節(jié)點收到數(shù)據(jù)包時,按照路由頭文件將該數(shù)據(jù)包轉(zhuǎn)發(fā)到下一跳。如果中間節(jié)點發(fā)現(xiàn)沒有前往目的節(jié)點的有效路由或是收到RERR包,則按照設(shè)定的最大次數(shù)重發(fā)該數(shù)據(jù)包,因為路由失效往往可能是由突發(fā)噪聲、節(jié)點進入無線信號衰落區(qū)域等暫時因素造成的。如果重傳達到最大次數(shù),則該中間節(jié)點判斷自己與源節(jié)點和目的節(jié)點之間的距離,若距目的節(jié)點近,則該節(jié)點自己發(fā)起相對微觀距離查找,否則通知源節(jié)點路由斷開,由源節(jié)點重新發(fā)起路由查找。

RDMAR協(xié)議的路由維護可以選擇局部修復,因而較其他路由協(xié)議可以減小控制開銷、降低時延,而且路由查找也限制在請求區(qū)內(nèi),路由查找速度快,不需要周期性的廣播分組,可以有效節(jié)省帶寬資源。但當節(jié)點的運動速度超過源節(jié)點的記錄速度時,會造成初次查找失敗,從而擴大查找范圍,增加了初始路由的時延和網(wǎng)絡(luò)開銷。但RDMAR協(xié)議不需要額外的GPS設(shè)備的支持,在一些特定條件下(如極端戰(zhàn)場環(huán)境下)會具有更廣的使用價值。

RDMAR協(xié)議的性能依賴于路由查找算法的成功率,因此對其進行優(yōu)化改進比較困難。Omar F Hamad[15]等人提出一種分簇的思想,將微觀相對距離搜索區(qū)域通過算法進一步分成若干區(qū)域,但是這種協(xié)議只適合學?；蜻\動場等區(qū)域特性較強的地方。Nadeem Akhtar[16]等人提出一種多徑路由的思想來增加RDMAR協(xié)議的健壯性,仿真表明,改進后的協(xié)議能提升實時和非實時的數(shù)據(jù)傳輸性能。

3.3 GeoCast

地理定位信息尋址路由協(xié)議(Geographic Addressing and Routing Protocol,GeoCast)是Julio C.Navas等人[17]提出的一種將信息送到某一地理區(qū)域的部分或全部節(jié)點的路由協(xié)議,它是多播路由協(xié)議的一個子集,可以通過將某一特定地理區(qū)域定義為多播群組而實現(xiàn)多播功能,具有分級的結(jié)構(gòu)。

實現(xiàn)地理定位信息尋址路由協(xié)議的系統(tǒng)由GeoHosts、GeoNodes、GeoRouter3部分組件構(gòu)成 。GeoRouter(Geographic Routers)負責地理定位信息的路由傳送。GeoNodes是地理定位信息尋址路由系統(tǒng)的出入點,負責將接收到的地理定位信息轉(zhuǎn)發(fā)給自己的鄰居節(jié)點。GeoHost負責地理定位信息的發(fā)送與接收,告知地理定位信息的有效性、當前節(jié)點的地理位置、當前GeoNode的地址。

在地理定位信息尋址路由協(xié)議中,地理定位信息在協(xié)議中的作用與IP地址在TCP/IP協(xié)議中的作用相似,主要目的是把網(wǎng)絡(luò)協(xié)議和地理位置相結(jié)合,方便提供一些與地理位置相關(guān)的網(wǎng)絡(luò)服務。地理信息尋址路由協(xié)議將地理位置信息引入節(jié)點地址和路由,在有效地理區(qū)域內(nèi)提供群組通信,因此可實現(xiàn)組播功能。其具有一定層次和結(jié)構(gòu),網(wǎng)絡(luò)擴展性好,但是要求路由節(jié)點位置比較固定,其余節(jié)點可以是移動的,因而適用范圍又受到一定的限制。

關(guān)于GeoCast研究的論文較多借鑒了單播路由協(xié)議的思想。GeoCast協(xié)議的研究目前主要集中在城市智能交通系統(tǒng)中的應用,關(guān)于多播信號的跨地理區(qū)域連續(xù)傳播是該協(xié)議研究的一個熱點。Zhu[18]等人針對現(xiàn)有的地理定位信息尋址路由協(xié)議很少能支持不同地理區(qū)域間的操作,提出了基于地理定位信息輔助和基于簇拓撲結(jié)構(gòu)的GMIDR(Geo-Assisted Multicast Inter-Domain Routing)協(xié)議。該協(xié)議能在保持高效路由的同時,實現(xiàn)不同地理區(qū)域間的可靠多播路由。Yoh Shiraishi[19]等人則針對移動自組網(wǎng)中節(jié)點可能移動到多播區(qū)域外造成多播數(shù)據(jù)不能持續(xù)傳輸?shù)膯栴},提出了一種將Geocast和GPSR(Greedy Perimeter Stateless Routing)兩者相結(jié)合的模式,通過該模式可以實現(xiàn)多播信息的不間斷傳遞。Ting Wang[20]等人提出了“擺渡(Ferry)”方案,通過地理定位信息選擇出網(wǎng)絡(luò)中特定區(qū)域的部分節(jié)點作為“渡船”,幫助傳遞多播信息,從而解決了多播信息連續(xù)傳遞的問題。

3.4 DREAM

移動距離效應路由(Distance Routing Effect Algorithm for Mobility,DREAM)協(xié)議是 Basagni等人[21]提出的一種基于距離效應和地理定位信息的路由協(xié)議。所謂距離效應是指兩個節(jié)點間的距離越遠,它們之間的相對運動看起來就越慢。

DREAM協(xié)議具有按需型路由協(xié)議的工作方式。在協(xié)議中,每個節(jié)點維護包含網(wǎng)絡(luò)中其他節(jié)點地理定位信息的路由表(地理定位信息可由GPS等定位設(shè)備得到)。當網(wǎng)絡(luò)中某個節(jié)點(源節(jié)點)需要傳遞信息到目的節(jié)點時,源節(jié)點根據(jù)自己路由表中目的節(jié)點的地理定位信息解算出目的節(jié)點的方向,然后將數(shù)據(jù)傳往自己在目的節(jié)點方向的一跳鄰居節(jié)點,所有鄰居節(jié)點繼續(xù)采用相同的方式傳遞數(shù)據(jù)到自己的下一跳鄰居節(jié)點,直至信息傳遞至目的節(jié)點。

該協(xié)議的關(guān)鍵在于找到目的節(jié)點的方向,而目的節(jié)點的方向取決于地理定位信息在網(wǎng)絡(luò)中的傳播方式。在DREAM協(xié)議中,每個節(jié)點是根據(jù)當前自身相對于其他節(jié)點的位置來傳遞控制信息的。其依據(jù)可以是以下兩點。

(1)控制信息更新頻率

根據(jù)距離效應,兩個節(jié)點相隔的距離越遠,其相對運動看起來更慢,因此兩個節(jié)點相互地理定位信息的更新頻率比那些相對距離近的節(jié)點低?？梢愿鶕?jù)源節(jié)點發(fā)送的信息傳送距離的遠近來設(shè)定一個控制信息的“年齡”,更新頻率可以據(jù)此設(shè)定。

(2)節(jié)點運動速率

節(jié)點運動越快,需要廣播自己地理定位信息的頻率就越高。因此,每個節(jié)點可以根據(jù)自身運動速率來有效地選擇自身控制信息的更新頻率。

由于DREAM協(xié)議選取距離和運動速率作為度量值,在網(wǎng)絡(luò)中不存在大量控制信息的交換,也不存在按需路由協(xié)議的延遲,所以具有高效、節(jié)省帶寬、無環(huán)、高健壯性、適合移動網(wǎng)絡(luò)的優(yōu)點。但是,由于節(jié)點的地理定位信息需要在全網(wǎng)絡(luò)傳遞,因此,當網(wǎng)絡(luò)規(guī)模達到一定程度或網(wǎng)絡(luò)內(nèi)節(jié)點的運動速度較快時,控制開銷會顯著增加,故該協(xié)議的擴展性不強,因此目前對DREAM協(xié)議的研究相對較少。Hu等人[22]將DREAM協(xié)議與邊界傳輸算法相結(jié)合,提出了一種應用于水下聲學移動組網(wǎng)的 BFDREAM協(xié)議。Bakhouya等人[23]采用實際運動模型,對DREAM協(xié)議在不同交通負載和不同速度下的智能交通系統(tǒng)的性能進行了仿真,得出DREAM協(xié)議隨著交通負載的增加效率降低比較明顯,對節(jié)點運動速度的增加反應則不那么明顯。

3.5 GPSR

貪婪型轉(zhuǎn)發(fā)和沿周邊轉(zhuǎn)發(fā)路由(Greedy Perimeter Stateless Routing,GPSR)協(xié)議是 Brad Karp等人[24]提出的一種用于無線數(shù)據(jù)報網(wǎng)絡(luò)的基于地理定位信息的路由協(xié)議。GPSR協(xié)議要求每個節(jié)點周期性地向其鄰居節(jié)點廣播自己的地址和地理定位信息,每個節(jié)點只保存自己鄰居節(jié)點的路由信息,因此路由表中僅含一跳的、最小的拓撲信息。為進一步減小控制開銷,各個節(jié)點的地理定位信息捎帶在數(shù)據(jù)分組中進行傳送。

源節(jié)點在發(fā)送數(shù)據(jù)分組時,將目的節(jié)點的地理位置信息也捎帶進去,因此每個中間節(jié)點可以根據(jù)自己保存的路由信息來選擇最佳(地理位置上離目的節(jié)點最近)的下一跳貪婪型轉(zhuǎn)發(fā)節(jié)點,下游節(jié)點繼續(xù)采用這種方式,直至數(shù)據(jù)分組成功傳遞到目的節(jié)點。

只要條件允許,GPSR協(xié)議優(yōu)先采用貪婪型轉(zhuǎn)發(fā)模式,而當貪婪型轉(zhuǎn)發(fā)模式失效時,則轉(zhuǎn)入沿周邊轉(zhuǎn)發(fā)模式,即沿著自己轉(zhuǎn)發(fā)的路由空洞(在該節(jié)點的傳輸范圍內(nèi),沒有比該節(jié)點離目的節(jié)點更近的節(jié)點)周邊采用右手法則尋找新的路由。右手法則的基本思想是按照順時針方向遍歷一個封閉多邊形區(qū)域的內(nèi)部邊線,若在封閉多邊形區(qū)域的外部時,則以反時鐘方向遍歷。在GPSR協(xié)議中,右手法則的使用是通過啟發(fā)式算法來完成的。當節(jié)點采用沿周邊轉(zhuǎn)發(fā)模式發(fā)送數(shù)據(jù)分組時,只要條件滿足,可以自動轉(zhuǎn)回貪婪型轉(zhuǎn)發(fā)模式,直到數(shù)據(jù)分組發(fā)送到目的節(jié)點。

GPSR協(xié)議由于采用了貪婪型轉(zhuǎn)發(fā)模式,因此只依賴一跳鄰居節(jié)點的信息,大大減小了網(wǎng)絡(luò)的控制開銷,提高了路由的穩(wěn)定性,同時采用了沿周邊轉(zhuǎn)發(fā)模式,可以有效地防止路由空洞的出現(xiàn),所以比較適合在節(jié)點密度大的自組網(wǎng)中使用。但貪婪型轉(zhuǎn)發(fā)模式所選擇的節(jié)點依據(jù)是地理位置距離目的節(jié)點最近,因而路由的選擇并非一定最佳,少數(shù)情況下,得到的路由可能是一條很長的路徑。貪婪型轉(zhuǎn)發(fā)模式只依賴一跳鄰居節(jié)點的地理定位信息,節(jié)點的運動速度過大時,容易出現(xiàn)鄰居節(jié)點移動出節(jié)點的傳輸范圍,從而導致丟包情況的發(fā)生。由于無線信道的傳輸特性,GPSR協(xié)議還容易出現(xiàn)節(jié)點和鄰居節(jié)點無法正常通信,從而導致節(jié)點誤刪鄰居節(jié)點的路由信息。

GPSR協(xié)議的健壯性已經(jīng)得到充分證明,目前其研究主要集中在改進協(xié)議的仿真運動模型、改進路由協(xié)議以適用不同應用需求這兩個方向。不同的運動模型導致對現(xiàn)實模擬的近似程度不同,因此模型的設(shè)計和選取對路由協(xié)議的仿真至關(guān)重要。Majid Shakeri[25]采用不同的移動模型(Random Waypoint Model(RWM)、Fluid Traffic Model(FTM)、Intelligent Driver Model with Intersection Management(IDM-IM))對GPSR、SIFT和GOSR 3種協(xié)議在城市智能交通系統(tǒng)中的性能進行了分析,結(jié)果表明RWM、FTM兩種模型不適合用來模擬仿真城市智能交通系統(tǒng),只有IDM-IM模型可以采用,同時作者還表明城市地形會降低GPSR協(xié)議的性能。N.Premalatha等人[26]則采用GPSR協(xié)議用于路由,采用新的沖突避免、ACK順序機制和分裂算法,提出了一種適用于自組網(wǎng)的QoS模型?，F(xiàn)有的GPSR協(xié)議只有經(jīng)過改進才能應用于城市智能交通系統(tǒng),由于城市交通系統(tǒng)具有一定的規(guī)律性,目前研究的方向多為引入城市電子地圖信息系統(tǒng)改進GPSR協(xié)議的運動模型,進而改進GPSR協(xié)議的實用性能。

Nguyen[27]等人針對城市智能交通系統(tǒng)高動態(tài)的特點,提出了一種GPSR-MA-LA協(xié)議。該協(xié)議要求節(jié)點周期性地廣播自己的地理定位信息,同時采用節(jié)點負載均衡路由算法,將節(jié)點的運動性和負載均衡綜合考慮。通過NS-2仿真表明,該協(xié)議能比GPSR協(xié)議有效地降低丟包率,減小時延。SUN等人[28]針對城市智能交通系統(tǒng)中由于交通工具的不規(guī)則分布導致GPSR性能低下的現(xiàn)象,采用電子地圖信息輔助進行改進,仿真表明該方案確實能降低丟包率。Shu[29]等人針對GPSR協(xié)議地理定位信息的更新時間間隔難題(需滿足不同網(wǎng)絡(luò)密度和應用需求),采用NAU(Neighbor-Awareness Position Update)根據(jù)節(jié)點的鄰居節(jié)點數(shù)量和地理方位來動態(tài)設(shè)置GPSR協(xié)議的地理定位信息更新時間間隔,將BGF(Beacon-assist Geographic Forwarding)策略與GPSR協(xié)議相結(jié)合,提出適用于城市智能交通系統(tǒng)的GPSRN&B協(xié)議。如何合理設(shè)置GPSR協(xié)議的地理定位信息更新時間間隔以使GPSR協(xié)議適用于不同的場景仍是今后GPSR協(xié)議應用于城市智能交通系統(tǒng)研究的一個重點方向。

總之,上述幾種典型的基于地理定位信息的路由協(xié)議都是通過某種策略限制參與路由的節(jié)點數(shù)量,從而減小網(wǎng)絡(luò)的控制開銷和負載。LAR和RDMAR協(xié)議由于將路由查找區(qū)域限制在一定的請求區(qū)域內(nèi),參與路由的節(jié)點少,因而路由查找速度快、控制開銷小,隨著網(wǎng)絡(luò)規(guī)模的增大,路由的成功率和可靠性顯著增加,因而網(wǎng)絡(luò)的可擴展性能好,但如果初始查找時無法獲取目的節(jié)點地理定位信息或地理定位信息不準確,兩者都需要擴大查找范圍或等同于全網(wǎng)泛洪方式,從而會增加網(wǎng)絡(luò)延遲和開銷,因而適用于節(jié)點密度中等或高的網(wǎng)絡(luò)。GeoCast協(xié)議由于可以分層,因而其網(wǎng)絡(luò)擴展能力更強,適用于規(guī)模較大的網(wǎng)絡(luò),同時還可以實現(xiàn)多播功能,但由于某些節(jié)點的位置需要相對固定,因而適用性受到一定限制。DREAM協(xié)議每個節(jié)點均需要維護路由表,因此路由的穩(wěn)定性較其他協(xié)議強,但當網(wǎng)絡(luò)規(guī)模擴大時,其控制開銷會急劇增大,因而網(wǎng)絡(luò)的擴展性較其他協(xié)議差,只適用于規(guī)模較小的網(wǎng)絡(luò)。GPSR協(xié)議依靠的是一跳協(xié)議,網(wǎng)絡(luò)控制開銷較其他協(xié)議小,但是其路由長度不是最優(yōu),而且在路由過程中,較其他協(xié)議容易遭遇“路由空洞”和“隱蔽終端”的問題,不過已有較多的學者就這一問題進行了研究,提出了眾多解決方案。目前已有的研究表明:LAR協(xié)議和GPSR協(xié)議具有較強的健壯性,移動性能也較其他協(xié)議強,因而其適用的網(wǎng)絡(luò)較多,當前已有學者試著將兩者應用到航空領(lǐng)域。

4 總結(jié)與展望

移動自組網(wǎng)的動態(tài)特性使得傳統(tǒng)的路由協(xié)議不再適用,必須開發(fā)新的路由協(xié)議才能滿足需求。現(xiàn)有的研究大多只就移動自組織網(wǎng)絡(luò)的某一路由協(xié)議進行研究。本文首先介紹了路由協(xié)議的設(shè)計基本原則,并按設(shè)計路由時選取的信息類型進行了分類。然后對當前典型的基于地理定位信息的移動自組網(wǎng)路由協(xié)議的原理和關(guān)鍵點進行了解析,對近年來的研究情況進行了分析歸納,指明了當前研究的主要思路和熱點方向,希望能給以后的研究提供借鑒和幫助。

近年來由于WiFi技術(shù)的興起,使得移動自組網(wǎng)技術(shù)在民用領(lǐng)域的需求不再那么迫切,民用方面移動自組網(wǎng)的研究主要集中在一些需要臨時通信而沒有基礎(chǔ)設(shè)施的場合,如城市智能交通系統(tǒng)、救援、民航等領(lǐng)域;軍事方面,移動自組網(wǎng)的研究已經(jīng)遍布各個領(lǐng)域,水下組網(wǎng)、陸地戰(zhàn)場組網(wǎng)、航空組網(wǎng)都已成為研究的對象,特別是航空自組網(wǎng),由于其高動態(tài)的特性和迫切的需求(無人機控制、戰(zhàn)機組網(wǎng)等),更是重點的研究方向?；诘乩矶ㄎ恍畔⒌穆酚蓞f(xié)議由于采用地理定位信息作為路由的輔助手段,相對于傳統(tǒng)自組網(wǎng)路由協(xié)議可以大大減小網(wǎng)絡(luò)的控制開銷、減小時延、提高路由的可靠性,增強網(wǎng)絡(luò)的可擴展性,因而更適用于高動態(tài)的應用場合,但是高動態(tài)的運動環(huán)境帶來拓撲的頻繁變化,對路由協(xié)議的收斂性和可靠性提出了更高的要求,如何利用地理定位信息開發(fā)出更加快速可靠的路由協(xié)議必將成為未來移動自組網(wǎng)技術(shù)發(fā)展的重點。目前,國內(nèi)外對這方面的研究大多是基于以上協(xié)議的改進或擴展,隨著研究的深入,可以就該方向做進一步的研究。此外,一些基于地理定位信息的移動自組網(wǎng)路由協(xié)議如具有移動預測機制的路由協(xié)議DV-MP(Distance Vector with Mobility Prediction)、FORP(Flow Oriented Routing Protocol)、基于路徑的簡單前向協(xié)議(Simple Forwarding over Trajectory,SIFT)等由于其特殊性也可以引起適當?shù)年P(guān)注。

[1] Murphy A L,RomanG C,Varghese G.An exercise in formal reasoning about mobile communications[C]//Proceedings of 1998 IEEE Ninth International Workshop on Software Specification and Design.Ise-Shima:IEEE,1998:25-33.

[2] KarrasK,Kyritsis T,Amirfeiz M,et al.Aeronautical Mobile Ad hoc Networks[C]//Proceedings of the 14th European Wireless Conference.Prague:IEEE,2008:1-6.

[3] Tee C A T H,Lee A C R.Survey of Position Based Routing for Inter Vehicle Communication System[C]//Proceedings of First International Conference on Distributed Framework and Application.Penang:IEEE,2008:174-182.

[4] Lambrou T P,Panayiotou C G.A Survey on Routing Techniques supporting Mobility in Sensor Networks[C]//Proceedings of the 5th International Conference on Mobile Ad-hoc and Sensor Networks.Fujian:IEEE,2009:78-85.

[5] Rohrer J P,Jabbar A,Egemen K,et al.Airborne Telemetry Networks:Challenges and Solutions in the ANTP Suite[C]//Proceedings of Military Communications Conference.San Jose,CA:IEEE,2010:74-79.

[6] Okamoto S,Sycara K.Augmenting ad hoc networks for data aggregation and dissemination[C]// Proceedings of 2009 Military Communication Conference.Boston,MA:IEEE,2009:1-7.

[7] Ko Young-Bae,Vaidya N H.Location-Aided Routing in mobile Ad hoc networks[J].Journal of Wireless Network,2000,6(4):307-321.

[8] 牟強,姚丹霖,姚宗福.一種改進的LAR方向路由算法[J].微電子學與計算機,2011,28(4):30-33.MOU Qiang,YAO Dan-lin,YAO Zong-fu.An Improved Direction Routing Algorithm Based on LAR[J].Microelectronics&Computer,2011,28(4):30-33.(in Chinese)

[9] Jang Hung-Chin,Hung Chih-Chia.Direction Based Routing Strategy to Reduce Broadcast Storm in MANET[C]//Proceedings of 2010 IEEE International Computer Symposium.Tainan:IEEE,2010:445-450.

[10] Chaki N.LAR2P:A Location Aided Reactive Routing Protocol for Near-Optimal Route Discovery in MANET[C]//Proceedings of 2010 International Conference on Computer Information Systems and Industrial Management Applications.Krackow:IEEE,2010:259-264.

[11] Gupta N,Gupta R.Proposed Energy Conserving Routing Technique using LAR[C]//Proceedings of 2011 International Conference on Computational Intelligence and Communication Systems.Gwalior:IEEE,2011:626-630.

[12] Al-Bahadili H,Al-Basheer O,Al-Thaher A.A Location Aided Routing-Probabilistic Algorithm for Flooding Optimization in MANETs[C]//Proceedings of Mosharaka International Conference on Communications,Networking and Information Technology.Amman Jordan:IEEE,2007:6-8.

[13] Al-Bahadili H,Maqousi A.On the Effect of Nodes Desnity on the Performance of the LAR-1P Route Discovery Algorithm[C]//Proceedings of 2011 IEEE Jordan Conference on Applied Electrical Engineering and Computing Technologies.Amman,Jordan:IEEE,2011:1-6.

[14] Aggelou G,Tafazolli R.RDMAR:A Bandwidth-efficient Routing Protocol for Mobile Ad Hoc Networks[C]//Proceedings of the 2nd ACM International Workshop on Wireless Mobile Multimedia.Seattle,Washington:ACM,1999:26-33.

[15] Hamad O F,Kang Mi-Young,Jeon Jin-Han,et al.Neural Network′s k-means Distance-Based Nodes-Clustering for Enhanced RDMAR Protocol in a MANET[C]//Proceedings of 2008 IEEE International Symposium on Signal Processing and Information Technology.Sarajevo:IEEE,2008:192-197.

[16] Akhtar N,Tafazolli R.Traffic-based Multipath Routing for Mobile Ad hoc Networks[C]//Proceedings of 2004 International Workshop on Wireless Ad-Hoc Networks.Oulu,Finland:IEEE,2004:201-206.

[17] Navas JC,Imielinski T.Geocast-geographic addressing and routing[C]//Proceedings of the 3rdAnnual ACM/IEEE International Conference on Mobile Computing and Networking.Buapest,Hungary:IEEE,1997:66-76.

[18] Zhu Konglin,Zhou Biao,Fu Xiaoming,et al.Geo-assisted Multicast Inter-Domain Routing(GMIDR)Protocol for MANETs[C]//Proceedings of 2011 IEEE International Conference on Communications.Kyoto:IEEE,2011:1-5.

[19] Shiraishi Y,Takahashi O,Miki R.A Geocast-based Multicast Method for Continuous Information Delivery in MANET[C]//Proceedings of 2010 International Conference on P2P,Parallel,Grid,Cloud and Internet Computing.Fukuoka:IEEE,2010:511-516.

[20] Wang Ting,Low Chor Ping.A Ferry Scheme for Geocast in MANETs[C]//Proceedings of the 5thAnnual ICST Wireless Internet Conference.Singapore:IEEE,2010:1-8.

[21] Basagni S,Chlamtac I,Syrotiuk V R,et al.A Distance Routing Effect Algorithm for Mobility(DREAM)[C]//Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking Mobicom.Dallas:ACM,1998:76-84.

[22] Hu Hongning,Liu Zhong,Yang Bin.BFDREAM:A new routing protocol for deep sea acoustic network[C]//Proceedings of 2010 IEEE 10th International Conference Signal Processing.Beijing:IEEE,2010:2377-2381.

[23] Bakhouya M,Gaber J,WackM.Performance Evaluation of DREAM Protocol for Inter-vehicle Communication[C]//Proceedings of 1st International Conference on Wireless Communication,Vehicle Technology,Information Theory and Aerospace&Electronic Systems Technology.Aalborg:IEEE,2009:289-293.

[24] Brad Karp,Kung H T.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks[C]//Proceedings of the 6th Annual International Conference on Mobile Computing and Networking.Boston:IEEE,2000:243-254.

[25] Shakeri M.Simulation and Evaluation of Routing Protocols in Vehicular Ad Hoc Network[C]//Proceedings of 2011 Eighth International Conference on Wireless and Optical Communications Networks.Paris,France:IEEE,2011:1-3.

[26] Premalatha N,Natarajan A M.Congestion Control and QoS Enhancement of Ad hoc Networks[C]//Proceedings of 2010 International Conference on Communication and Computational Intelligence.Erode,India:IEEE,2010:40-46.

[27] Nguyen T D,Van T P,Trong T D,et al.A Load-balanced and Mobility-aware Routing Protocol for Vehicular Ad-hoc Networks[C]//Proceedings of 2011 International Conference on Advanced Technologies for Communications.Danang,Vietnam:IEEE,2011:36-39.

[28] SUN Shupeng,HU Jianming,LUO Xixi,et al.Improved GPSR in Inter-Vehicle Communication[C]//Proceedings of 2010 International Conference on Communications and Mobile Computing.Shenzhen:IEEE,2010:259-265.

[29] Shu Wenjie,Wang Ping,Guo Aihuang,et al.Enhanced GPSR using Neighbor-Awareness position Update and Beacon-assist Geographic Forwarding in vehicular ad hoc networks[C]//Proceedings of 2009 IEEE Intelligent Vehicles Symposium.Xi′an:IEEE,2009:1143-1147.