一種基于位置信息輔助的移動自組織網(wǎng)絡路由算法

周翔

?

一種基于位置信息輔助的移動自組織網(wǎng)絡路由算法

周翔

東南大學 網(wǎng)絡與信息中心, 江蘇 南京 210096

在移動自組織網(wǎng)絡中，由于節(jié)點的移動沒有固定的模式，很多情況下無法得到穩(wěn)定的網(wǎng)絡拓撲，因此傳統(tǒng)的無線多跳網(wǎng)絡路由協(xié)議很難直接運用于移動自組織網(wǎng)絡。本文分析了基于地理位置的路由模型，引入移動節(jié)點的當前位置信息和目標位置信息，結合報文的投遞目標進行在報文轉發(fā)中做最優(yōu)路由選擇?；谟绊懧酚蛇x擇的三個要素：移動節(jié)點目標位置與報文目標位置的距離、移動節(jié)點目標位置與報文目標位置的夾角和移動節(jié)點本身的移動速度，提出了一種基于位置信息輔助的移動自組織網(wǎng)絡路由算法(LIBR)。仿真結果表明，所提算法在轉發(fā)成功率、轉發(fā)延時以及轉發(fā)次數(shù)等性能參數(shù)方面與現(xiàn)有的路由算法相比，具有更好的性能表現(xiàn)。

移動自組織網(wǎng)絡；路由算法；路由選擇；位置信息輔助

移動自組織網(wǎng)（Mobile Ad hoc Networks, MANETs）是由一組可自由移動和相互通訊的節(jié)點，通過自動配置組成的多跳無線通訊網(wǎng)絡，不需要提前布置任何固定的網(wǎng)絡基礎設施。隨著研究的發(fā)展，移動自組織網(wǎng)絡的應用越來越廣泛，如軍事戰(zhàn)場上[1]，深空環(huán)境下[2]和游牧監(jiān)控網(wǎng)絡[3]等。移動自組織網(wǎng)絡具有特殊的網(wǎng)絡結構配置，由于節(jié)點高移動性所導致的拓撲頻繁變化，使得節(jié)點之間不能頻繁進行通信，從而任意節(jié)點之間的鏈路無法保持穩(wěn)定，因此傳統(tǒng)的多跳無線路由協(xié)議無法運用于移動自組織網(wǎng)絡中。

近年來，在移動自組織網(wǎng)絡的路由研究方面，國內外許多研究機構對基于地理位置信息的路由協(xié)議展開了研究?；诘乩砦恢眯畔⒌穆酚傻闹饕枷胧菍⑾⑥D發(fā)給特定的地理位置，而不是一般路由算法中的以特定節(jié)點為目標。現(xiàn)有的基于地理位置信息的路由協(xié)議，主要是基于與目標位置距離的方法，把消息距離目標位置的路程作為判定下一個中繼的標準[4-7]。但是對于大規(guī)模的移動自組織網(wǎng)絡來說，基于距離的路由方法并不能夠獲得很好的表現(xiàn)，主要原因有以下幾點：1）移動自組織網(wǎng)絡中的高移動性導致了距離快速地變化，進而降低了算法的性能表現(xiàn)；2）這樣的算法需預先知道網(wǎng)絡的拓撲，對于在大規(guī)模的移動自組織網(wǎng)絡中這樣的知識難以獲?。?）現(xiàn)有的算法沒有考慮到節(jié)點本身具有的一些有用的路由信息，比如說當前節(jié)點的目的地，可以通過一些方法提前獲得，比如車輛的導航系統(tǒng)以及出租車乘客提供的目的地址。

本文通過考察移動節(jié)點和消息的位置信息（包當前位置信息和目標位置信息），將這些信息運用到移動自組織網(wǎng)絡的路由算法中，在了解了移動節(jié)點和消息的當前位置和目標位置后，路由算法總是將消息轉發(fā)給更有可能移動到消息目標投遞區(qū)域的節(jié)點，減少了無效的投遞，增加路由算法的投遞成功率和轉發(fā)延遲，提高路由轉發(fā)效率。移動節(jié)點的當前位置信息可以通過全球定位系統(tǒng)（Global Positioning System, GPS）[8,9]獲得。由于是基于地理位置的路由，所以消息的目標位置信息在消息生成時已經確定。移動節(jié)點目標位置可以通過一些方法間接獲得，隨著科技的不斷發(fā)展，現(xiàn)在的車輛上一般都配備有導航系統(tǒng)，在一段行程開始前會設置目標位置。此外，還有一種情景是城市交通中的出租車和公交車，公交車的目標位置是相對固定的；出租車在有乘客的情況下，目的地通常都是固定的，所以我們也可以假設預先了解到了移動節(jié)點的目標位置。

本文的組織結構如下：第2部分介紹與分析移動自組織網(wǎng)路由算法以及基于位置信息輔助的路由算法的相關工作；第3部分提出了的基于位置信息輔助的移動自組織網(wǎng)絡路由算法；第4部分通過仿真實驗，將提出的路由算法與其他路由算法進行比較分析；第5部分給出本文的結論。

1 相關工作

1.1 傳統(tǒng)移動自組織網(wǎng)絡路由算法

在文獻[10,11]（WCNC）中提出了基于泛洪的多副本路由算法，從源節(jié)點開始產生消息，并且將副本轉交給每一個相遇的節(jié)點，盡可能覆蓋到每一個網(wǎng)絡中的節(jié)點以提高傳輸成功率。盡管泛洪路由在沒有條件約束的場景中路由效果是最優(yōu)的，但在實際的應用場景中泛洪路由算法帶來的巨大的網(wǎng)絡負載使其無法運用在大多數(shù)真實場景中。為了降低泛洪路由帶來的網(wǎng)絡負載，文獻[12]提出了PROHET路由算法，該算法利用節(jié)點間的歷史相遇記錄信息來預測未來轉發(fā)的可能性。PROHET中的路由指標是節(jié)點成功地從源節(jié)點轉發(fā)到目標節(jié)點的可能性，即報文總是轉發(fā)給更有可能遇到目標節(jié)點的移動節(jié)點。除此之外，為了控制報文副本在網(wǎng)絡中的數(shù)量，文獻[13,14]提出了基于K-副本的Spray-and-Wait算法和Spray-and-focus算法，有效控制網(wǎng)絡中副本數(shù)量的同時降低了網(wǎng)絡負載并提高了轉發(fā)效率。另外，單副本的路由算法也有許多相關的研究成果，用于減少路由的開銷。文獻[15]基于節(jié)點間相關聯(lián)的信息提出了MED算法，該算法對每對節(jié)點相遇的期望時間進行量化處理，生成節(jié)點之間聯(lián)系的加權圖，最后利用Dijkstra算法計算節(jié)點間最短路徑；文獻[16]提出了SimBet算法，該算法基于社會關系定義了中心性和相似度的概念，通過計算所遇節(jié)點的向心性和相似度來決定是否向其轉發(fā)報文，主要利用社會網(wǎng)絡中呈現(xiàn)出的“小世界”的現(xiàn)象來增加消息的轉發(fā)成功率。

1.2 基于地理位置的路由算法

基于地理位置的路由算法的研究也具有相當長的歷史。在較早的文獻[4]中，只有單副本路由被考慮進來。為了提高轉發(fā)成功率，多副本路由開始被廣泛使用，運用最多的就是泛洪路由算法，被許多基于地理位置的路由算法采用。文獻[6]提出了基于泛洪路由算法的方法，該方法在消息源節(jié)點和目標位置之間定義了方形的轉發(fā)區(qū)域，在路由選擇中消息總是轉發(fā)給離目標位置距離更近的節(jié)點來增加轉發(fā)成功率。文獻[17]引入了泰森多邊形來幫助轉發(fā)區(qū)域的選擇。另外，文獻[5]提出了基于分簇的路由方法，具體方法是將網(wǎng)絡區(qū)域劃分為邏輯網(wǎng)格，在網(wǎng)格中挑選出簇頭作為網(wǎng)關進行數(shù)據(jù)的轉發(fā)。在文獻[5]的基礎上，文獻[7]引入了額外的簇頭，用于收集移動節(jié)點的消息并轉發(fā)到目標位置。然而分簇算法帶來的問題是簇頭的負載增加而導致的網(wǎng)絡瓶頸。除此之外，文獻[18,19]利用車輛本身帶有的一些位置信息來輔助路由選擇，比如說車輛中一般安裝有GPS系統(tǒng)和導航系統(tǒng)，這些額外的信息可以用來提高路由效率。本文提出的基于地理位置信息輔助的路由算法是綜合利用節(jié)點本身以及消息的位置信息和目標位置信息進行路由選擇。

2 基于位置信息輔助的移動自組織網(wǎng)絡路由算法

2.1 網(wǎng)絡模型

基于地理位置的移動自組織網(wǎng)絡路由算法與傳統(tǒng)的移動自組織路由算法的區(qū)別在于前者是以地理位置或地理區(qū)域為轉發(fā)目標的路由算法，而后者的目標是網(wǎng)絡中的節(jié)點?；诘乩砦恢玫囊苿幼越M織路由算法的目的是基于移動節(jié)點的移動特性實現(xiàn)地理位置之間的報文信息的轉發(fā)。報文在指定的地理位置產生并且報文以另外一個地理位置為目標。我們假設移動節(jié)點可以存儲攜帶這些報文并且在移動到下一個地理位置時由路由算法決定是否卸載緩存中的一個或多個報文。同時，移動自組織網(wǎng)絡中的移動節(jié)點的頻繁相遇可以為報文的快速轉發(fā)帶來一些潛在的機會，所以移動節(jié)點與移動節(jié)點之間也會進行交互來提高報文的轉發(fā)成功率。

假設網(wǎng)絡中有個具體的地理位置，并且在這些位置都是相對固定的，假設L代表位置的地理位置。除此之外，我們假設在這些位置上都有接受無線傳感器網(wǎng)絡信號的節(jié)點，我們稱之為靜態(tài)節(jié)點。這些靜態(tài)可以通過無線信號和移動節(jié)點進行通信。本文中將由這些靜態(tài)節(jié)點代替指定的轉發(fā)位置進行路由轉發(fā)，并且假設這些靜態(tài)節(jié)點的緩存足夠大。上文中我們提到在一個指定的地理位置產生的報文是以另外一個地理位置為目標，所以假設消息的目標位置為()。另外，假設網(wǎng)絡中具有個移動節(jié)點，并且這些移動節(jié)點都知道自己的當前位置以及目標地點的信息，其中結點當前位置用L來表示，目標位置用()來表示（圖1）。

圖 1 節(jié)點移動模型

在本文中，我們只考慮基于地理位置的移動自組織網(wǎng)絡中的單播網(wǎng)絡模型，即單條消息只有一個確定位置。另外，我們假設節(jié)點的移動模型是改進的隨機路點（Random Way Point, RWP）模型[20]，RWP模型隨機地選擇目標節(jié)點位置并按隨機的速度沿直線移動到該位置并產生下一路點循環(huán)重復以上的步驟進行移動。我們改進的地方在于將按直線路徑移動改為沿隨機路徑移動到目標位置，這樣能過更適用于我們提出的算法。

2.2 算法實現(xiàn)

基于車輛本身的地理位置信息以及報文的地理位置信息我們設計并實現(xiàn)了一種基于地理位置信息輔助的移動自組織網(wǎng)絡路由算法（Location Information Based Routing, LIBR）。LIBR算法的主要思想是將報文更快、更準地轉發(fā)到目標位置。如果能夠盡可能多地解到移動節(jié)點的運動趨勢，對于基于地理位置信息的路由算法的性能的提高有很大幫助。在所有節(jié)點做報文的路由選擇是需要考慮周全，因此我門列出了3個最有可能影響路由選擇的因素：

1）移動節(jié)點目標位置與報文目標位置的距離：如果移動節(jié)點能夠將報文轉發(fā)至離報文目標位置更近的地方，在路由選擇上這樣的移動節(jié)點應該具有較大的優(yōu)先級；

2）移動節(jié)點目標位置與報文目標位置的夾角：考慮到移動節(jié)點分布的不均勻性以及移動節(jié)點目標位置的隨機分布，可能沒有辦法將報文通過捎帶或者簡單的一兩跳將報文轉發(fā)到目標位置，此時需要考慮到節(jié)點當前的目標方向（不同于移動方向，該方向向量由移動節(jié)點的當前位置和目標位置構成）；

3）移動節(jié)點的移動速度：移動節(jié)點的速度將影響報文轉發(fā)的速率，移動越快的節(jié)點將會被賦予更高的路由優(yōu)先級，這樣不僅能夠使報文具有更高的概率投遞給優(yōu)勢更大的下一跳節(jié)點，并且加快報文在網(wǎng)絡中的傳播速率，從而提高報文的轉發(fā)成功率。

算法LIBR

輸入:n,n,m

輸出:n

1:ifnwithin(m) then

2:n?n

3: else if(n,m)>(n,m) then

4:n?n

5: else

6:n?n

7: end if

8: end if

9: returnn

其中++=1，顯然(n,m) (0,1)，根據(jù)三個因素的重要程度對、和分別進行調整，考慮到方向因素相對較為重要，本文中三個數(shù)值的取值分別是0.5、0.25以及0.25。

LIBR算法的核心在于計算移動節(jié)點和待轉發(fā)消息的轉發(fā)概率值，路由總是選擇概率值高的移動節(jié)點作為下一跳轉發(fā)節(jié)點，這樣才能夠保證報文更快、更準確地轉發(fā)到目標位置。

由于移動自組織網(wǎng)絡本身具有的一些特性，LIBR算法能夠充分利用各個移動節(jié)點的相遇機會來不斷增加概率值。顯然倒數(shù)第二跳的節(jié)點具有最高的報文轉發(fā)概率值，所以LIBR算法的高效性得以保證。

3 仿真實驗

下面，將對所提出的算法進行性能評估與分析，本文使用ONE[21]仿真平臺進行實驗。首先需要獲得節(jié)點的相遇信息和移動路徑信息，然后輸入到ONE仿真器中進行仿真，最后獲得ONE輸出的性能參數(shù)對算法進行評估與分析。為了對比本文提出的算法，我們加入了一些經典算法進行對比，仿真中涉及的路由算法包括：1）泛洪路由算法（Epidemic）；2）基于二分方法Spray-and-wait的副本路由算法（簡稱SAW），設置了兩個不同的值進行對比；3）基于距離的地理位置路由算法（Geo-Dist）[22]。

本文假定在一個方形的大小為500 m×500 m的區(qū)域中進行試驗。移動節(jié)點的移動模型采用改進的RWP模型，移動速度在5 m/s~10 m/s之間隨機選擇，隨機停留時間在5~10 s之間取值。假設節(jié)點間的通信半徑為20 m，設置報文的TTL值為1300 s。為了對比各個算法的性能表現(xiàn)，即設置不同的報文產生速率來觀察算法在不同的網(wǎng)絡負載下的表現(xiàn)情況，范圍是1 pkt/s~5 pkt/s，此外節(jié)點的緩存大小被設置為固定值20 pkt。我們從三個方面來評估算法的性能表現(xiàn)：報文投遞成功率、報文的平均投遞延遲和報文的總轉發(fā)次數(shù)。為了消除仿真中數(shù)據(jù)的隨機性，每個結果都是來自于1000組測試結果的均值。

首先考察投遞成功率，如圖2所示，隨著報文生成速率的增加，投遞成功率都會有不同程度的下降，這是因為報文的增加使得緩存有限的節(jié)點產生丟包現(xiàn)象。特別是多副本算法，由于拷貝數(shù)量的增加讓原本就緊張的緩存資源無法承受過高網(wǎng)絡負載而丟失大量報文。但是在報文負載較低時，多副本路由算法的表現(xiàn)較好，特別是泛洪路由算法和取值較大時的SAW算法。可以清楚地看出我們提出的LIBR算法在不同的網(wǎng)絡負載情況下表現(xiàn)均很不錯，特別是在5 pkt/s的報文產生速率下依然能夠保持90%以上的投遞成功率。另外，Geo-Dist算法只考慮了距離因素，所以投遞率比LIBR算法低一些，但是也能夠保持在比較高的水準。

圖 2 報文生成速率vs.投遞成功率

其次，我們考察報文的平均投遞延遲，從圖3中可以看出，多副本路由算法具有更低的延遲，這是由于網(wǎng)絡中同一報文有多個副本的存在，使得報文能夠更快地尋找到目標位置。但是多副本網(wǎng)絡中會有大量的報文丟失現(xiàn)象，所以隨著報文生成速率的增加，網(wǎng)絡中存在的時間越長的報文就越容易被丟棄，最終導致了平均延遲的降低現(xiàn)象。LIBR算法和Geo-Dist都具有較高的延遲，這是由于單副本路由算法存在的普遍問題，不過本文提出的算法相比Geo-Dist具有更低的投遞延遲，所以在做路由選擇時全面地利用節(jié)點和報文的信息可以用來降低投遞延遲。

最后考察報文的累積轉發(fā)次數(shù)，從圖4可以看出，多副本路由算法具有更多的轉發(fā)次數(shù)，特別是泛洪路由算法，這樣的結果是顯而易見的。更多的轉發(fā)次數(shù)意味著更多的能量消耗，這也是泛洪路由算法無法廣泛運用于實際場景的一個主要原因。本文提出的算法與Geo-Dist具有相近的轉發(fā)次數(shù)，并且LIBR算法的表現(xiàn)得稍微好一些，這是由于我們提出的算法中報文的有效轉發(fā)次數(shù)增加并且不斷累計的結果。

圖 3 報文生成速率vs.平均投遞延遲

圖 4 報文生成速率vs.轉發(fā)次數(shù)

綜上所述，本文提出的算法在投遞成功率表現(xiàn)最為出色，在不同的網(wǎng)絡負載下都能夠獲得很高的投遞成功率，在轉發(fā)次數(shù)方面也具有良好的表現(xiàn)，盡管在投遞延遲方面的表現(xiàn)稍微差一些，但是從總體上來看，LIBR算法和本文所列出的其他算法相比，具有更好的表現(xiàn)。

4 結語

本文首先簡單的介紹了基于地理位置的移動自組織路由算法的研究現(xiàn)狀，通過對移動節(jié)點本身具有的一些位置信息的發(fā)掘，提出了一種基于位置信息輔助的移動自組織網(wǎng)絡路由算法。然后加入了仿真實驗，測試所提出算法的性能表現(xiàn)，并與現(xiàn)有的一些算法進行了對比分析，實驗結果表明我們的算法可以較好的提高消息的投遞率、降低網(wǎng)絡負載以及更快、更準確地將報文投遞到目標位置。在以后的工作中將考慮將我們的算法運用到實際的運用場景中，進一步驗證所提算法的實用性能。

[1] McMahon A, Farrell S. Delay-and disruption-tolerant networking[J]. Internet Computing, IEEE, 2009,13(6):82-87

[2] Burleigh S, Hooke A, Torgerson JL,. Delay-tolerant networking: an approach to interplanetary internet[J]. IEEE Communications Magazine, 2003,41(6):128-136

[3] Doria A, Uden M, Pandey DP. Providing connectivity to the saami nomadic community[C]. Proc. 2nd Int. Conf. on Open Collaborative Design for Sustainable Innovation, 2002

[4] Ko YB, Vaidya NH. GeoTORA: A protocol for geocasting in mobile ad hoc networks[C]. Proc. IEEE Int. Conf. on Networking Protocols, 2000:240-250

[5] Liao WH, Tseng YC, Lo KL,. “GeoGRID: A geocasting protocol for mobile ad hoc networks based on grid[J]. J. Internet Tech., 2000,1(2):23-32

[6] Ko YB, Vaidya NH. Flooding-based geocasting protocols for mobile ad hoc networks[J]. Mobile Networks and Applications, 2002,7(6):471-480

[7] Imieliński T, Navas JC. GPS-based geographic addressing, routing, and resource discovery[J]. Communications of the ACM, 1999,42(4):86-92

[8] Dommety G, Jain R. Potential networking applications of global positioning systems (GPS)[R]. Computer Science, 1998:22-42

[9] Parkinson BW, Gilbert SW. NAVSTAR: global positioning system – ten years later[J]. Proceedings of the IEEE,1983, 71(10):1177-1186

[10] Spyropoulos T, Psounis K, Raghavendra CS. Single-copy routing in intermittently connected mobile networks[C]. IEEE Secon First IEEE Communications Society Conference on sensor & Ad Hoc Communications & Networks, 2004:235-244

[11] Tseng Y, Ni S, Chen Y,. The broadcast storm problem in a mobile ad hoc network[J]. Wireless networks, 2002,8(2-3):153-167

[12] Lindgren A, Doria A, Scheln O. Probabilistic routing in intermittently connected networks[J]. Acm Sigmobile, 2003,7(3):19-20

[13] Spyropoulos T, Psounis K, Raghavendra CS. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[C]. Proc. of Acm Sigcomm Workshop on Delay-Tolerant Networking, 2005:252-259

[14] Spyropoulos T, Psounis K, Raghavendra C. Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility[C]. Proc. of IEEE PERCOMW, 2007:79-85

[15] Jones EPC, Li L, Schmidtke JK,Practical routing in delay-tolerant networks[J]. , IEEE Transactions on Mobile Computing, 2007,6(8):943-959

[16] Daly EM, Haahr M. Social network analysis for information flow in disconnected delay-tolerant MANETs[J]. IEEE Transactions on Mobile Computing, 2009,8(5):606-621

[17] Stojmenovic I, Ruhil A, Lobiyal D. Voronoi diagram and convex hull based geocasting and routing in wireless networks[J]. Wireless communications and mobile computing, 2006,6(2):247-258

[18] Leontiadis I, Mascolo C. GeOpps: Geographical opportunistic routing for vehicular networks[C]. IEEE International Symposium on World of Wirele Mobile & Multimedia Networks, 2007:1-6

[19] Cheng P, Lee K, Geria M,. GeoDTN+Nav: geographic DTN routing with navigator prediction for urban vehicular environments[J]. Springer Mobile Networks and Applications, 2010,15(1):61-82

[20] Lin G, Noubir G, Rajaraman R. Mobility models for ad hoc network simulation[C]. Twenty-third Annual Joint conference of the IEEE Computer and Communications Societies, 2004:454-463

[21] Ker?nen A, Ott J, K?rkk?inen T. The ONE simulator for DTN protocol evaluation[C]. International Conference on Simulation Tools and Techniques, 2009:55

[22] Hall R. An improved geocast for mobile ad hoc networks[J]. IEEE Trans. on Mobile Computing, 2011,10(2):254-266

A Mobile Ad hoc Networks Routing Algorithm with Location Information

ZHOU Xiang

210096,

In Mobile Ad hoc Networks, since the mobile node does not exist a fixed pattern, it is unable to obtain a stable network topology in many cases. So traditional wireless multi-hop routing protocols are difficult to apply in MANETs directly. By analyzing the geographic-based routing model, mobile nodes’ current information and the destination information is introduced to help the optimal routing selection. Based on three main factors of the routing selection, i.e., the distance between node’s destination and message’s destination, the angle between node’s moving direction and message’s forwarding direction and the moving speed of mobile node, we propose a location information based routing algorithm. Simulation results show that the proposed algorithm outperform the existing routing algorithms in delivery rate and other performance parameters.

Mobile Ad hoc Networks; routing algorithm; routing selection; location information based

TN929.5

A

1000-2324(2018)05-0856-06

10.3969/j.issn.1000-2324.2018.05.027

2017-09-20

2017-10-25

周翔(1984-),男,碩士,助理工程師,主要從事網(wǎng)絡研究與數(shù)據(jù)中心建設工作. E-mail:xzhou@seu.edu.cn