基于地理定位信息的移動自組網路由協議綜述

張鵬明,李洪烈,林成浴

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

1 引 言

20世紀七八十年代提出的Ad Hoc[1]網絡最開始主要用于軍事目的,其出發點是在無基礎設施的戰場環境下迅速構建通信網絡。Ad Hoc網絡沒有中心節點,任何節點均可自由移動、進出網絡,同時每個節點還具有路由功能,中繼轉發數據至目的節點。

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

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

2 移動自組網路由協議

2.1 移動自組網路由協議的基本設計

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

(1)優化

優化指路由算法選擇最佳路徑的能力,根據設計的metric值來計算。移動自組網由眾多自由、移動的節點組成,要求具有優化的算法。

(2)快速收斂

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

(3)有效地控制開銷

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

(4)健壯 、穩定

健壯、穩定是指路由算法在出現不正常或不可預見事件的情況下仍能正常工作。移動自組網工作在無線移動模式,信道情況比較復雜,出現突發事件的概率比較大,對路由算法的健壯、穩定要求更加迫切。

(5)靈活

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

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

2.2 移動自組網的路由協議分類

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

(1)基于拓撲結構的路由協議

基于拓撲結構的路由協議其路由選取的信息是基于網絡節點之間的拓撲鏈接,按照發現路由的方式不同,又可分為主動型、按需路由型和混合型3種。

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

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

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

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

與基于拓撲結構的路由協議不同,基于地理定位信息的路由協議其路由選取是基于地理定位坐標的。這種類型的路由協議更適合移動自組網的高動態要求。

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

3 基于地理定位信息的移動自組網路由協議

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

3.1 LAR

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

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

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

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

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

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

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

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

3.2 RDMAR

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

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

(1)路由查找

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

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

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

(2)路由維護

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

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

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

3.3 GeoCast

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

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

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

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

3.4 DREAM

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

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

該協議的關鍵在于找到目的節點的方向,而目的節點的方向取決于地理定位信息在網絡中的傳播方式。在DREAM協議中,每個節點是根據當前自身相對于其他節點的位置來傳遞控制信息的。其依據可以是以下兩點。

(1)控制信息更新頻率

根據距離效應,兩個節點相隔的距離越遠,其相對運動看起來更慢,因此兩個節點相互地理定位信息的更新頻率比那些相對距離近的節點低。可以根據源節點發送的信息傳送距離的遠近來設定一個控制信息的“年齡”,更新頻率可以據此設定。

(2)節點運動速率

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

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

3.5 GPSR

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

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

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

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

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

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

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

4 總結與展望

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

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

[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.