一種基于地理位置信息的Ａｄ ｈｏｃ網(wǎng)絡路由算法

（電子科技大學 通信與信息工程學院，成都 610054）



摘要：

在Ad hoc網(wǎng)絡等無線網(wǎng)絡中，GPSR是一種健壯的地理路由協(xié)議，但是當有較多的分組傳遞給同一個目的節(jié)點時，其周邊轉發(fā)模式產(chǎn)生的過多跳數(shù)的路由會成為一個突出問題。在此分析的基礎上，提出了一個優(yōu)化的路由算法——OGPSR路由算法。在第一個分組經(jīng)歷了與GPSR算法相同的周邊轉發(fā)模式傳遞后，該路由算法能夠減少很大一部分路由的跳數(shù)。

關鍵詞：地理位置信息路由協(xié)議； 周邊轉發(fā)； 改進的路由算法； 路由協(xié)議

中圖分類號：TP393文獻標志碼：A

文章編號：10013695(2009)03101003



Geographic routing algorithm in Ad hoc networks



YANG Jianjun， MAO Yuming， SUN Jian



（School of Communication Information Engineering，University of Electronic Science Technology of China，Chengdu 610054， China）



Abstract:

GPSR is a robust geographical routing protocol for Ad hoc networks， but the excessive number of hops commonly created by the perimeter mode can become an issue when multiple packets are generated for the same destination. This paper proposed a simple yet effective routing algorithm OGPSR (optimal greedy perimeter stateless routing algorithm). OGPSR algorithm was capable of reducing a large portion of hops if the first packet delivered by GPSR ever enters perimeter mode.

Key words：greedy perimeter stateless routing(GPSR); perimeter forwarding; optimal GPSR; routing protocol



隨著GPS 等定位技術的發(fā)展和具體應用，基于地理位置信息的路由協(xié)議較好地解決了傳統(tǒng)路由協(xié)議在無線傳感器網(wǎng)絡和移動Ad hoc網(wǎng)絡等無線網(wǎng)絡中的低效問題。典型的基于地理位置信息的路由協(xié)議有LAR(location aided routing)[1]協(xié)議、GPSR(greedy perimeter stateless routing)[2]協(xié)議和TBF(trajectory based forwarding)[3] 協(xié)議等，這類協(xié)議非常適合存儲空間有限和計算能力較小的無線節(jié)點，且具有更好的可擴展性和對無線網(wǎng)絡更好的適應性。

基于地理位置信息路由協(xié)議在路由時只需要知道鄰居節(jié)點的位置信息，而不需要其他的全局信息。但是，由于沒有更多的全局信息，這類協(xié)議對應的具體算法可能會終止于一個局部最優(yōu)點，而非全局最優(yōu)點。

目前主要有兩種解決局部優(yōu)化問題的方法，即遭遇最佳主機時的啟動恢復機制[2，4]或構造無最佳主機節(jié)點的拓撲子圖[5，6]。文獻[4]采用泛洪策略作為恢復機制，這種機制在資源受限的無線網(wǎng)絡中并不可行。文獻[5]利用Voronoi圖來構造原網(wǎng)絡拓撲的無最佳主機節(jié)點的子圖。基于同樣的思想，文獻[6]通過構造危險區(qū)域消除最佳主機節(jié)點，從而支持有保證的路由。這種解決方法為了維持底層的拓撲結構，需要一定的通信開銷。而基于GPSR協(xié)議[2]的路由算法則采用perimeter forwarding （周邊轉發(fā)）模式較好地解決了局部優(yōu)化問題，perimeter轉發(fā)模式提供了有保證的單路徑分組轉發(fā)，但是增加了路徑長度，導致網(wǎng)絡路由性能的降低。

本文在分析GPSR協(xié)議中周邊轉發(fā)機制的基礎上，提出了一種改進的路由算法OGPSR（optimal GPSR）。該路由算法能夠有效地減少了周邊轉發(fā)模式中路由的跳數(shù)，改善網(wǎng)絡的路由性能，并通過仿真進行了論證。

1OGPSR路由算法

首先通過一個具體的例子，分析了GPSR協(xié)議在邊界轉發(fā)模式下的不足，然后在此基礎上提出了支持OGPSR路由協(xié)議的策略。給出了相應的算法，并且說明了該算法是如何減少路由的跳數(shù)。

1.1GPSR協(xié)議周邊轉發(fā)模式

例如，一個有10個節(jié)點的簡單網(wǎng)絡，節(jié)點s和d分別是源節(jié)點和目的節(jié)點。網(wǎng)絡拓撲如圖1所示，用線段連接起來的兩個點互為鄰居節(jié)點。以d為圓心的圓 ，半徑等于s與d之間的距離，以s為圓心的圓弧表示了s能夠傳送的距離半徑。兩個圓的重疊部分為空區(qū)域。

根據(jù)GPSR協(xié)議，當節(jié)點s有一個分組要發(fā)送給d時，因為在s的一跳鄰居節(jié)點中，沒有一個鄰居節(jié)點比它更靠近d，該分組就進入周邊轉發(fā)模式。使用右手準則，該分組經(jīng)過a、b、c、e、f被傳遞，然后才到達g。當該分組到達g時，它處于一個比s離d更近的地理位置，這就是該分組最后進入周邊轉發(fā)模式的位置，然后該分組的轉發(fā)切換到貪婪模式。之后該分組按照貪婪算法依次經(jīng)過h、i兩節(jié)點后到達目的節(jié)點d。這條由GPSR協(xié)議發(fā)現(xiàn)的路徑如圖2所示。

從圖2中可以看出，GPSR路由協(xié)議在周邊轉發(fā)模式中要遍歷的面(圖中的重疊部分)很可能是一塊很大的區(qū)域，如果僅僅簡單地采用右手法則進行分組轉發(fā)，分組每一跳的物理距離通常很短，并且連續(xù)幾跳，甚至會產(chǎn)生小段多余的繞路，這無疑會增加整條路由的跳數(shù)，如圖2所示。由于移動Ad hoc網(wǎng)絡等無線網(wǎng)絡的拓撲易變性，任何一對節(jié)點間的鏈路隨時有可能中斷，過多的路由跳數(shù)會加大該條路由上傳輸分組的丟失概率，延長分組的傳輸時延，降低網(wǎng)絡的整體性能。單就路由跳數(shù)指標而言，可以看出GPSR協(xié)議選擇的路由并不是最佳路由。

在上述分析的基礎上，借助一些路由節(jié)點上存儲的少量關于路由的狀態(tài)信息（分組、分組到達某個節(jié)點時經(jīng)歷的跳數(shù)、該分組的下一跳節(jié)點），本文提出了一種改進的策略和相應的路由算法，該路由算法能夠有效地減少GPSR協(xié)議在周邊轉發(fā)模式中由于繞道產(chǎn)生的跳數(shù)。當多個分組傳到相同的目的節(jié)點時，該路由算法能夠在傳遞完第一個分組后，快速地找到一條較短的路由，以便后續(xù)分組的傳遞能夠經(jīng)過較少的跳數(shù)。在移動Ad hoc等無線網(wǎng)絡中，每個節(jié)點都通過主動偵聽信道以獲取傳遞給它的分組。所以節(jié)點能夠確定一個分組以前是否轉發(fā)過，并且能從分組頭部信息，確定分組到達當前發(fā)送者所經(jīng)過的跳數(shù)。

當節(jié)點m向它的鄰居節(jié)點n發(fā)送一個分組后，如果節(jié)點m偵聽到相同的分組又被其另一個鄰居節(jié)點k轉發(fā)，那么可以認為節(jié)點 m到k的連接是一條捷徑。這一簡單策略的執(zhí)行只要求每個節(jié)點能夠在一段時間內保持少量的路由狀態(tài)信息，以確定該分組之前是否被轉發(fā)過。基于以上策略的OGSGR算法如下。

1.2OGPSR算法路由發(fā)現(xiàn)

首先，采用與GPSR算法相同的機制為第一個分組找到路由之后，無線網(wǎng)絡中的節(jié)點遵循下列路由算法傳遞分組。

1) if m holding a packet P then

if m=s then

m.hop=0

else

m.hop=P.hop+1

P.hop=m.hop

if m≠d then

m forwardsP to m.next

2)if m hears a noden∈nbr(m)

transmitting the same P with

P.then＞m.hop+1 then

m.next=n

3)m recounts its m.hop when the next packet of the same connection is delivered throughm.

其中:S表示源節(jié)點；d表示目的節(jié)點；m和n表示中間節(jié)點；P表示分組，定義為P.id。

P.id=(s，d，seq)。nbr(m)表示節(jié)點m的所有一跳鄰居節(jié)點，每個參與了周邊轉發(fā)模式的節(jié)點m記錄分組的下一跳m.next，以及該分組到達m時所經(jīng)歷的跳數(shù)m.hop。m.next和m.hop的記錄由一個計時器控制。對于一個給定的連接，如果節(jié)點m在一定的時間內沒有收到下一個分組，那么該節(jié)點將丟棄路由信息m.next和m.hop，這個連接將被裁減。在轉發(fā)一個分組P之前，節(jié)點m將信息m.hop保存到分組P頭部，表示為P.hop。

在OGPSR算法中，當?shù)谝粋€分組采用與GPSR算法相同的機制轉發(fā)時，相關路由節(jié)點將偵聽信道并且在其轉發(fā)完第一個分組后確定所有可能的捷徑。在圖2中，節(jié)點s將偵聽到它發(fā)送給a的分組又從節(jié)點b和f相繼被傳送，那么它將設置s.next=b，以及s.next=f。節(jié)點A也將設置a.next=f，但是這個路由狀態(tài)信息將很快被丟掉，因為之后不再有分組從s傳到a。與節(jié)點a類似，在節(jié)點b丟掉這一路由狀態(tài)信息時，它先設置b.next=e以及b.next=f，在節(jié)點h轉發(fā)分組后，節(jié)點f將設置f.next=h。結果，當?shù)谝粋€分組使用GPSR算法轉發(fā)完成后，后面的分組將從節(jié)點s開始，依次通過節(jié)點f、h、i最終到達目的節(jié)點d。這一最優(yōu)路徑就是被OGPSR算法發(fā)現(xiàn)的，如圖3所示。

2OGPSR路由算法性能分析

與GPSR算法相比較，OGPSR算法有以下優(yōu)點：a）減少了路由的跳數(shù)；b)任意一個節(jié)點在一跳傳輸范圍內，有確定的下一跳；c)裁減后，第二個分組以及后續(xù)分組的路由收斂；d)降低了路由的復雜度；e)沒有額外的環(huán)路；f)不改變貪婪模式的傳遞路徑。

證明假設GPSR算法中，路由節(jié)點的集合為NGPSR={mi}ki=1。那么OGPSR路由的節(jié)點集合NOGPSR將是NGPSR節(jié)點集合的一個子集。

根據(jù)OGPSR路由算法，如果在GSGR算法中存在一條捷徑，那么將至少存在一個節(jié)點mc∈NGPSR將在OGPSR算法中被裁減。因此，OGPSR算法中的跳數(shù)等于或者小于GPSR算法中的跳數(shù)。

假設一個節(jié)點mi∈NOGPSR，如果在mi的一跳傳輸范圍內存在兩個節(jié)點同時屬于NOGPSR，那么將存在一個裁減的過程以進一步減少路由跳數(shù)，因此，OGPSR算法中能夠提供確定的只有一個鄰居節(jié)點的下一跳的路由。

在OGPSR算法中，第一個分組采用與GPSR路由算法相同的機制傳遞，同時，路由相關的節(jié)點偵聽并建立其路由狀態(tài)信息(m.next、m.hop和P.id)。當?shù)谝粋€分組完成路由之后，所有的節(jié)點都已經(jīng)建立起各自的路由狀態(tài)信息，并且整個的路由已被裁減。從第二個分組開始，所有剩余的分組通過已經(jīng)建立的路由狀態(tài)信息，將在裁減過的路徑上路由。因而裁減后，第二個及以后分組路由的傳遞將收斂。在第一個分組傳遞完成之后，后面分組的傳送不需要更多地比較鄰居節(jié)點的位置。所以，OGPSR協(xié)議仍保持有低路由復雜性的特性。

如果在GPSR算法中，節(jié)點集合NGPSR中的路由沒有環(huán)路，那么在不需要改變節(jié)點的順序的集合NOGPSRNGPSR中也沒有環(huán)路。

節(jié)點在貪婪模式下轉發(fā)分組與GPSR算法中貪婪轉發(fā)模式完全相同，在該節(jié)點所有的一跳鄰居節(jié)點中，選取距離目的節(jié)點最近的那個鄰居節(jié)點作為分組轉發(fā)的下一跳節(jié)點，所以，不存在捷徑和裁減路由的問題，即OGPSR算法不會改變分組貪婪模式的傳遞路徑。

3仿真結果及分析

本文采用NS2[7]作為網(wǎng)絡仿真工具，重點比較了OGPSR算法和GPSR算法在平均分組丟失率、平均分組傳輸時延、路由分組開銷和網(wǎng)絡吞吐量等方面的性能。仿真場景如下：在1 200 m×1 200 m的區(qū)域里分布200個節(jié)點，MAC層協(xié)議采用802.11；使用CBR作為數(shù)據(jù)業(yè)務流，數(shù)據(jù)包大小為521 Byte，包發(fā)送率為4包/s；選擇Random Waypoint為節(jié)點的移動模型，最小移動速度為0，最大移動速度為20 m/s。所有仿真結果均為多次實驗的平均值。

圖4是OGPSR算法和GPSR算法在網(wǎng)絡節(jié)點移動時分組丟失率的對比圖，可以看出，隨著節(jié)點在運動區(qū)域中某一位置上停留時間(pause time)的逐漸增大(節(jié)點移動性較弱)，這兩種路由算法的分組丟失率呈下降趨勢，但是OGPSR路由算法的分組丟失率始終小于GPSR的分組丟失率。

圖5是OGPSR算法和GPSR算法的平均分組傳輸時延的對比圖，從仿真結果可以看出，隨著節(jié)點移動性的降低，OGPSR和GPSR路由算法的數(shù)據(jù)分組平均傳輸時延均增大，這是因為在移動Ad hoc網(wǎng)絡中的某個區(qū)域內存在嚴重的網(wǎng)絡擁塞和多址訪問干擾。從圖5中還可以看出，在節(jié)點停留時間大于400 s時，OGPSR路由算法的平均分組傳輸時延呈下降趨勢，在節(jié)點暫停時間較長時，OGPSR路由算法的數(shù)據(jù)分組平均傳輸時延明顯優(yōu)于GPSR，這是因為OGPSR路由算法有效地降低了源到目的的分組轉發(fā)跳數(shù)，盡可能減少了周邊轉發(fā)模式中分組傳輸時延。

圖6是OGPSR和GPSR算法的路由分組開銷對比圖。可以看出，隨著節(jié)點移動性的增強，GPSR路由協(xié)議的路由分組開銷大大低于OGPSR路由協(xié)議帶來的路由分組開銷。這主要是由于GPSR不需要建立和維護路由，節(jié)點不需要存儲路由信息表，也不需要發(fā)送路由更新信息，源節(jié)點到目的節(jié)點的數(shù)據(jù)傳輸只需要知道目的節(jié)點的地理位置和每次數(shù)據(jù)轉發(fā)時下一跳節(jié)點的地理位置即可實現(xiàn)。而OGPSR路由協(xié)議則需要更新和維持路由的狀態(tài)信息(m.next、m.hop和P.id)，因此帶來了較多的控制消息開銷。隨著節(jié)點移動性的降低，OGPSR路由協(xié)議路由分組開銷會明顯下降，這是因為網(wǎng)絡穩(wěn)定后，OGPSR路由協(xié)議的只需很小的開銷就能維持路由的狀態(tài)信息。

圖7表示OGPSR和GPSR路由算法的網(wǎng)絡吞吐量的對比。隨著節(jié)點移動性的降低，網(wǎng)絡吞吐量呈上升趨勢，OGPSR路由協(xié)議始終具有較穩(wěn)定而又相對較高的網(wǎng)絡吞吐量。這主要是由于OGPSR在建立路由時，根據(jù)較少的路由跳數(shù)來路由，有效地降低了鏈路中斷引起的傳輸分組丟失概率，從而提高了網(wǎng)絡吞吐量。

4結束語

本文在分析GPSR路由協(xié)議的基礎上，提出了一種改進的路由算法OGPSR。該算法通過增加路由探測的過程，達到了節(jié)省路徑的效果，從而減少了Ad hoc網(wǎng)絡中端對端的路由跳數(shù)和路徑長度。仿真結果表明，OGPSR算法雖然在路由協(xié)議開銷方面相比GPSR算法有所增加，但在分組丟失率、分組傳輸時延以及網(wǎng)絡吞吐量等方面均要優(yōu)于GPSR，所以可以認為OGPSR算法改進了GPSR算法的網(wǎng)絡性能。

另外，結合對Ad hoc網(wǎng)絡的底層拓撲結構動態(tài)變化的控制，進一步改善OGPSR算法的路由性能，這也是后續(xù)的研究工作之一。

參考文獻：

[1]KO YoungBae，VAIDYA N H. Locationaided routing in mobile Ad hoc networks[J]. Wireless Networks， 2000， 6 (4) :307321.

[2]KARP B， KUNG H T. Greedy Perimeter stateless routing for wireless networks[C]//Proc of the 6th Annual International Conference on Mobile Computing and Networking. New York:ACM Press， 2000: 243254.

[3]NICULESCU D， NATH B. Trajectory based forwarding and its applications[C]//Proc of the 9th Annual International Conference on Mobile Computing and Networking. New York :ACM Press，2003: 260272.

[4]STOJMENOVIC I， LIN Xu. Loopfree hybrid singlepath /flooding routing algorithms with guaranteed delivery for wireless networks [J]. IEEE Trans on Parallel and Distributed System ，2001，12(10):10231032.

[5]XING Guoliang， LU Chenyang， PLESS R， et al. On greedy geographic routing algorithms in sensingcovered networks[C]//Proc of the 5th ACM International Symposium on Mobile Ad hoc Networking and Computing. New York :ACM Press，2004:3142.

[6]ZOU Le， LU Mi， XIONG Zixiang. A distributed algorithm for the deadend problem of location based routing in sensor networks [J]. IEEE Trans on Vehicular Technology， 2005， 54(4):15091522.

[7][EB/OL].http://www.isi.edu/nsnam/ns/.