采用Hull樹的貪婪地理位置路由算法的設計*

毛科技，趙小敏，衣俊艷，夏 明，雷艷靜，王 堯，陳慶章

(浙江工業(yè)大學計算機科學與技術學院，杭州310023)

無線傳感網(wǎng)絡在森林監(jiān)測、氣候監(jiān)控、軍事戰(zhàn)場、數(shù)字城市方面有廣泛的應用前景。在諸多應用領域中，不僅要求隨時獲取目標的一些物理量數(shù)據(jù)，還要求得到目標的地理位置，由此推出很多WSN定位技術。隨著無線傳感網(wǎng)絡應用深入，很多應用不僅要求攜帶地理位置信息，還要求數(shù)據(jù)能夠根據(jù)地理位置信息向特定的地理位置轉發(fā)，節(jié)點接收由特定地理位置傳來的信息，數(shù)據(jù)沿著特定的地理路徑傳遞。為了滿足這些應用需求，人們需要研究依靠節(jié)點的地理位置信息來進行報文轉發(fā)與數(shù)據(jù)尋路的路由技術，這就是所謂基于地理位置的路由協(xié)議。地理位置路由協(xié)議一般可以分為使用地理位置信息進行輔助路由尋路的路由協(xié)議與基于地理位置信息的路由協(xié)議兩類［1］。后者又可以按其主要實現(xiàn)方式不同分為定向區(qū)域泛洪、貪婪路由算法和分層路由算法等路由協(xié)議。

基于貪婪路由算法的地理位置路由協(xié)議是目前研究比較深入的一類地理位置路由協(xié)議。此類協(xié)議是在貪婪路由轉發(fā)策略的基礎上，通過各種方法改進其尋路表現(xiàn)。簡單的說，貪婪路由轉發(fā)策略就是轉發(fā)節(jié)點將數(shù)據(jù)傳給離目的節(jié)點更近的節(jié)點。地理位置中的貪婪路由算法主要面臨的問題是如何解決由于實際節(jié)點布設位置不均勻而導致的網(wǎng)絡拓撲結構中空曠域(Voids)［2］引起的路由轉發(fā)失敗的情況。為了解決這一問題，學者提出了一系列的路由算法。GFG(greedy-face-greedy)算法［3］是最早提出了采用GG圖(Gabriel graph)來平面化網(wǎng)絡圖，從而在貪婪路由尋路失敗時使用face routing的尋路方法來繼續(xù)轉發(fā)報文的貪婪路由協(xié)議;GPSR協(xié)議［4］采用類似的方法，但是由于在網(wǎng)絡的平面化以及尋路方式細節(jié)方面的改變，使得GPSR協(xié)議得到了更好的性能表現(xiàn)和實用性，從而成為在地理位置路由領域最為認可的協(xié)議之一。文獻［5－6］提出了face routing的尋路何時切換回貪婪路由尋路，并在得出切換的最佳時機上開發(fā)出了GOAFR(Greedy and(Other A-daptive)Face Routing)與 GOAFR+路由協(xié)議。MIT的Ben Leong提出了GDSTR和GSpring算法［7］。還有基于散列值的路由協(xié)議［8］，基于能量優(yōu)化的路由算法［9］，通過改進蟻群算法的路由算法［10］等。

所謂空曠域，是指在實際的無線傳感網(wǎng)絡中，不管是人工的放置節(jié)點在固定的位置，還是撒播，總會遇見某些地方是節(jié)點無法存在的區(qū)域，或者是位于此地的節(jié)點無法正常工作的區(qū)域，比如沼澤，湖泊，大河，高樓，具有強電磁干擾的地方等;即使是均勻的放置，也會由于網(wǎng)絡中某些節(jié)點因為斷電或異常等情況失效，從而在網(wǎng)絡中形成大小不等的“空洞”。在這些空洞內部，沒有節(jié)點來進行數(shù)據(jù)分組的接力轉發(fā)。在實際的路由過程中，往往需要繞過這些空洞來轉發(fā)數(shù)據(jù)。正如圖1所表示的那樣，轉發(fā)節(jié)點x無法找到比自己距離D點更近的節(jié)點，然而確實存在這樣的一條路徑(x，w，v)可以使報文得到順利的轉發(fā)。這時原有的貪婪轉發(fā)策略就失敗了，需要新的方案來解決這一問題。

圖1 空曠域(Void)

本文借用圖形學上凸包(convex hull)的概念，結合原有的貪婪轉發(fā)策略，提出了GHTGR(Greedy Hull Tree Geographic Routing)算法。這是一個面向無線傳感網(wǎng)絡的分布式地理路由算法。通過Hull樹，它構建一個以本地節(jié)點為中心的多層次凸包結構，用于描述節(jié)點周圍的局部網(wǎng)絡拓撲結構，報文只需在節(jié)點內部的Hull樹內進行搜索，從而獲得數(shù)據(jù)分組的轉發(fā)路徑(包括繞過空曠域的路徑)。實驗表明，本算法相比于GPSR算法，不僅能夠正確地尋找到數(shù)據(jù)分組的轉發(fā)路徑，同時在初始的報文交換方面，盡可能地將報文交換局限在局部區(qū)域以內，有效地減少了全網(wǎng)報文廣播對網(wǎng)絡負載與性能的影響。由于此算法只需得知局部的網(wǎng)絡拓撲結構，從而比之于GPSR算法靈活性與適應性更高。

1 算法的構建

1.1 平面化網(wǎng)絡拓撲結構與凸包

對于GPSR算法中face routing方法來說，得以運行的一個首要條件就是要構造一個平面圖來描述實際的網(wǎng)絡拓撲。這樣的圖須滿足:網(wǎng)絡拓撲結構應當是平面化的［11］;平面圖中任意兩邊都不相交;平面圖中不存在不封閉的多邊形結構。任何基于網(wǎng)絡拓撲結構進行尋路的路由協(xié)議，首先要解決的問題就是如何將現(xiàn)實的、由節(jié)點之間的通訊關系所形成的網(wǎng)絡拓撲記錄下來，并經(jīng)過某種算法的處理，形成節(jié)點可以識別、處理、存儲的平面圖形結構。常用的網(wǎng)絡拓撲圖［12］的方法有 UDG(unit disk graph)圖、最小生成樹(MST)、RNG圖(Relative Neighbor Graph)與GG圖(Gabriel Graph)。

凸包(Convex Hull)［13］是這樣的一個圖形:給定平面上的一個(有限)點集(即一組點)，這個點集的凸包就是包含點集中所有點的最小面積的凸多邊形?！白钚∶娣e”這個限制條件，保證了凸包的唯一性，因為除了凸包以外，還有無限多個包含點集中所有點的凸多邊形。例如，只要畫一個面積足夠大的四邊形，便可包圍任意給定的點集。因此假如沒有這個限制條件，求凸包就變成非常容易但卻沒有唯一解的運算。它的數(shù)學描述如下:

在一個實數(shù)向量空間V中，對于給定集合X，所有包含X的凸集K的交集S被稱為X的凸包。

X的凸包可以用X內所有點(x1，…，xn)的線性組合來構造

在路由算法中，凸包一般被應用于如下的場合。當節(jié)點分布比較密集時，逐個比較每個節(jié)點到目標區(qū)域的前進距離所需要的計算開銷很大。而凸包是一個節(jié)點集合中處于“外圍”的節(jié)點連線構成的凸多邊形。當轉發(fā)節(jié)點計算報文轉發(fā)路徑時，只需要比較凸包上的點到目的節(jié)點的距離即可。在節(jié)點密度較大時，節(jié)點就不需要比較自己的所有鄰居節(jié)點信息，大大降低了節(jié)點在尋找下一條轉發(fā)路徑計算量。常用的凸包構建算法有增量式算法(Incremental algorithm)、包裹法(Gift wrapping algorithm)、快包法(QuickHull)、分治法(Divide and Conquer algorithm)等多種方法。

1.2 Hull樹存儲結構與報文結構

在本算法中，采取了如圖2所示的Hull樹存儲結構，以及如圖3、圖4報文結構。(表1與表2分別說明了這兩種報文結構中各個域的功能定義)

圖2 Hull樹存儲結構

圖3 Hull樹構建維護過程報文結構

圖4 路由尋路過程數(shù)據(jù)分組報頭

表1 Hull樹構建維護過程報文格式及功能

表2 路由尋路過程數(shù)據(jù)分組報頭格式及功能

2 算法設計

在介紹算法運行過程之前，首先介紹本算法運行的假設前提條件。正如大多數(shù)地理路由算法所要求的那樣，實行地理路由算法的無線傳感網(wǎng)絡中的節(jié)點，應當具備通過獨立設備或者交換報文從而得到節(jié)點地理位置信息的能力。同時，該網(wǎng)絡的拓撲結構應當比較穩(wěn)定，節(jié)點位置不會經(jīng)常性地發(fā)生改變，一般處于靜止固定的狀態(tài)，不會長時間地處于移動狀態(tài)之中［14］。

算法在實際運行過程中分為兩個部分:①初始化階段;②數(shù)據(jù)分組轉發(fā)階段。

2.1 初始化階段

在初始化階段，整個無線傳感網(wǎng)絡每個節(jié)點通過與相鄰節(jié)點之間的報文交換，分布式地在每個節(jié)點上建立一個局部HULL樹。具體實現(xiàn)過程如下:

(1)當節(jié)點p開啟時，它首先向周圍廣播查詢報文Inquiry message，詢問所有鄰居節(jié)點是否可以將其自身存儲的Hull樹寄送到p，以使p加入網(wǎng)絡，并構建自身Hull樹。當節(jié)點p廣播查詢報文Inquiry message時，任何鄰居節(jié)點如果接收到這樣的報文，則有以下三種反饋情況:①鄰居w已經(jīng)存儲有Hull樹，此時返回Hull樹報文;②鄰居節(jié)點并未構建Hull樹，則返回Hull樹構建命令報文(Hull build message);③p節(jié)點直接通訊范圍之內沒有任何節(jié)點，因此接受不到任何反饋報文。如果p接收到鄰居反饋的Hull樹報文(Hull tree message)，則等待足夠數(shù)量的鄰居發(fā)來Hull樹報文之后，依據(jù)算法在其中構建一個凸包，并將凸包上的點的Hull樹添加到p節(jié)點的Hull樹中，再向周圍鄰居節(jié)點廣播p的Hull樹。第②種情況下轉入(2)，第③種情況下轉入(3)。

(2)節(jié)點 p收到Hull樹構建命令報文(Hull build message)，表示在這個局部范圍內未構建Hull樹，于是P首先以自己為根節(jié)點，接受足夠數(shù)量的鄰居返回報文之后，建立本地Hull樹，并將自身Hull樹向鄰居節(jié)點廣播。在這個過程中可能會出現(xiàn)以下兩種情況:①p節(jié)點只收到了返回的Hull樹構建命令報文，此時說明P的鄰居節(jié)點中都未構建Hull，這時p依據(jù)鄰居節(jié)點的Hull樹構建命令報文構建的Hull必然是一個一層無子樹的Hull樹結構;②p節(jié)點收到的所有報文中，既有返回Hull樹構建命令報文，也有返回的Hull樹報文，此時對p來說，同樣是先根據(jù)這些報文構建本地Hull樹，同時判斷哪些返回Hull樹報文的鄰居節(jié)點是否是本地Hull樹的子節(jié)點，如是，則將其Hull樹添加進本地Hull樹;如否，則拋棄。

(3)節(jié)點p收不到任何反饋報文。這說明p沒有任何鄰居，此時建立的Hull是一個僅有以p為根節(jié)點的樹。這個過程中，節(jié)點通過接收鄰居節(jié)點的報文，從中選擇符合要求的Hull樹上的(凸包上的)節(jié)點加入自身的Hull樹中。同時，通過交換初始報文，也很容易地為每個子節(jié)點添加上屬于它的hull樹結構。網(wǎng)絡初始時的Hull樹構建過程，是一個較為漫長的過程，在這個過程中，節(jié)點要一直等待鄰居節(jié)點發(fā)來的各類報文，根據(jù)Hull樹構建算法對自身的Hull樹進行修剪，再將自身的Hull樹向鄰居節(jié)點廣播。本算法中采用包裹法構建Hull樹的算法如下:

算法1 包裹法構建凸包

標記p節(jié)點所有鄰居節(jié)點的鏈表List(N1、N2、N3…Ni)，其中Ni由節(jié)點標志與位置信息X、Y構成。

存儲凸包結構HullTree(nodes)

在完成了Hull樹的構建工作之后，在整個路由算法運行過程之中，需要不停地依據(jù)實際情況維護各節(jié)點上Hull樹。一般有如下三種情況并采取相應的措施:①新節(jié)點的加入。這種情況下，可以根據(jù)以上Hull構建階段的方法，為節(jié)點構造Hull樹，并將其信息通知到各個鄰居節(jié)點;②節(jié)點移動或者從暫時的休眠中恢復。在這種情況下，節(jié)點仍保存有原有的Hull樹，但此時的Hull樹信息可能已經(jīng)過時，應當重新發(fā)出查詢請求報文來取得新位置下，鄰居節(jié)點的位置及其存儲的Hull樹信息，通過對自身原有Hull樹的對比，修正自生Hull樹;③節(jié)點的離開。節(jié)點為它的每個鄰居節(jié)點設立一個時間閾值。這一閾值也是節(jié)點和它鄰居節(jié)點進行信息交換的周期。當節(jié)點在下一周期向某個鄰居節(jié)點發(fā)出信息交換請求而在限定時間內未收到回應時，將刪去自身Hull樹中以這個鄰居節(jié)點為根節(jié)點的子樹，并廣播自身狀態(tài)信息。

2.2 數(shù)據(jù)分組轉發(fā)階段

當源節(jié)點s產(chǎn)生一個需要發(fā)往目的節(jié)點t的數(shù)據(jù)分組M時，它會為數(shù)據(jù)分組添加上文所述的報頭，并將路由轉發(fā)模式(ROUTE MODE)設為初始的Tree模式，然后根據(jù)報文模式與節(jié)點自身的狀態(tài)信息，來判斷下一步應采取的動作。同樣，中間節(jié)點v收到由源節(jié)點s、鄰居節(jié)點w發(fā)來的目的節(jié)點t的報文M，也會檢查報文中所標記的路由轉發(fā)模式，進而根據(jù)相關信息(自身Hull樹以及目的節(jié)點、自身節(jié)點的位置信息)選擇下一步的行為。

在此我們假設某一中間節(jié)點v收到由源節(jié)點s、鄰居節(jié)點w發(fā)來的目的節(jié)點為t的報文M。具體來說，報文在發(fā)送過程中，由于轉發(fā)模式的不同，大致有以下幾種情況。

首先，節(jié)點v檢查自身是否為報文M的目的節(jié)點。若是，則接收報文并停止報文的轉發(fā);若否，則檢查是否是報文中P NODE域所表示的中間目的節(jié)點。若是，按照報文中所載的節(jié)點轉發(fā)序列，向下一跳節(jié)點轉發(fā)報文;若否，則進入模式檢查。檢查報文轉發(fā)模式。

(1)Tree模式下:

v搜索自身的HULL樹，首先判斷目的節(jié)點是否是v的鄰居節(jié)點(目的節(jié)點是否在Hull樹根節(jié)點的直接子節(jié)點所構成的凸包范圍以內)，若是，則直接廣播報文即可;否則，判斷目的節(jié)點t是否存在v的hull樹的子樹所形成的凸包中，如果是，則將v到該子樹根節(jié)點在v的Hull樹中查找的節(jié)點序列作為報文的轉發(fā)路徑，添加到報頭的P NODE域中，其中ID和Location為子樹根節(jié)點的標識與位置，trace域存儲節(jié)點序列，然后轉發(fā)報文到下一節(jié)點;否則設報文模式為Tree-Greedy。

(2)Tree-Greedy模式下:

節(jié)點搜索存儲在本地的Hull樹，選擇其中距離目的節(jié)點位置最近的子節(jié)點作為報文在本模式下所傳輸?shù)哪康墓?jié)點，其中從根節(jié)點到此葉子節(jié)點在Hull樹中查找到的節(jié)點序列，即為此報文的轉發(fā)路徑。這一模式采取的轉發(fā)方式同單純的貪婪法很像，都是尋找距離目的節(jié)點最近的節(jié)點。不同的是，一般的貪婪法是在鄰居節(jié)點中尋找距離目的節(jié)點更近的節(jié)點，然而在本算法中，是在節(jié)點本地的Hull樹中搜索距離目的節(jié)點最近的節(jié)點。由于節(jié)點Hull樹中存儲的是一個局部網(wǎng)絡拓撲，因此所查找到的轉發(fā)路徑就可以保證數(shù)據(jù)分組被傳遞出更廣的范圍。同時，貪婪法需要比較目的節(jié)點同中間轉發(fā)節(jié)點的所有鄰居節(jié)點的距離，并從中選擇距離目的節(jié)點最近的鄰居節(jié)點，而且在每經(jīng)過一個節(jié)點時都需要做這樣的比較，然而本算法中只需判斷是否在Hull樹中規(guī)劃的凸包以內即可，并在到達某個中間轉發(fā)節(jié)點時才需要做位置比較工作，大大提高了運行效率。

(3)Greedy模式下:

報文進入Greedy模式，就意味著數(shù)據(jù)報文在轉發(fā)時進入到了算法中止情況。算法中止存在三種情況:①目的節(jié)點的地理位置處于網(wǎng)絡覆蓋范圍以內，網(wǎng)絡中不存在目的節(jié)點。此時，報文已轉發(fā)到某一節(jié)點q，q對報文檢查時發(fā)現(xiàn)目的節(jié)點在其本地凸包內，只需廣播發(fā)送報文即可，然而廣播此報文不能得到回應，或者說目的節(jié)點不存在，此時只需簡單地丟棄報文即可。當然，如果對路由協(xié)議做可靠性擴展，可以要求q向源節(jié)點返回報文轉發(fā)失敗的信息;②節(jié)點為網(wǎng)絡圖的局部達到頂點。在這種情況下，報文到達的節(jié)點v將是網(wǎng)絡拓撲的某個局部頂點。在v自身的Hull樹中無法查找到比v距離目的節(jié)點t更近的節(jié)點。當協(xié)議規(guī)定v只存儲一層的Hull樹時，那么Hull樹就沒法涵蓋到比v節(jié)點距離目的節(jié)點更近的節(jié)點x。顯而易見，這是一個比較大的空曠域。如果增加節(jié)點中Hull樹的層數(shù)，就可以增加Hull樹的覆蓋范圍，直至覆蓋到一個比當前節(jié)點更靠近目的節(jié)點的轉發(fā)節(jié)點。當然，這里既然出現(xiàn)了空曠域，那么采用邊界轉發(fā)策略同樣也可以解決問題;③目的節(jié)點的地理位置處于網(wǎng)絡覆蓋范圍以外。出現(xiàn)這種情況，意味著目的節(jié)點在網(wǎng)絡之外時，數(shù)據(jù)報文到達了整個網(wǎng)絡的邊緣的某個節(jié)點，這個節(jié)點相比于網(wǎng)絡中其他節(jié)點，距離目的節(jié)點最近。并且顯然，此時報文所在節(jié)點是它Hull樹中凸包上的節(jié)點，并非位于凸包的中心。在這種情況下，路由協(xié)議簡單地標記此報文的目的節(jié)點不可達即可。

3 算法仿真與分析

本論文基于MATLAB7進行路由算法的仿真。網(wǎng)絡模型為在一個覆蓋區(qū)域為100×100范圍內隨機生成由50到500數(shù)量不等節(jié)點組成的網(wǎng)絡。為了保持網(wǎng)絡通訊在節(jié)點密度較大時，不會由于節(jié)點通訊距離過長從而導致路徑選擇過早地擬合成為貪婪法下的最優(yōu)路徑，因此隨著網(wǎng)絡節(jié)點密度的增大，將適當?shù)販p小節(jié)點間的通訊距離。

圖5 網(wǎng)絡中的Hull樹結構以及算法兩點路由尋路路徑

圖5表示了一個面積為100×100的網(wǎng)絡區(qū)域內隨機分布了150個節(jié)點，每個節(jié)點的通訊距離為15單位的網(wǎng)絡分布。圖5(a)表示出了初始化完成時，從全網(wǎng)絡選擇某幾個節(jié)點表現(xiàn)出的Hull樹結構。當然，即使是選取的幾個節(jié)點，也沒有表現(xiàn)出它們所有的Hull樹結構，只是有選擇地選取若干子節(jié)點Hull樹表現(xiàn)出來。圖5(b)中實線線條表示GHTGR算法在運行時一次具體的路徑轉發(fā)。虛線線條表示GPSR算法在相同節(jié)點下的轉發(fā)路徑。由圖5(b)中可以看出，大多數(shù)情況下實線線條覆蓋了虛線線條，這表示GHTHR算法與GPSR算法尋找到的轉發(fā)路徑是一致的。由于GPSR算法同樣是以貪婪策略為基礎的路由轉發(fā)，一般情況下，在貪婪模式下兩算法選擇下一跳轉發(fā)節(jié)點的差異不會很大。具體的差異表現(xiàn)在GHTGR算法在Hull樹查詢方面，可能在Tree-Greedy模式下，出現(xiàn)Hull樹第一層的某子節(jié)點的凸包上的點(即Hull樹的第2層)比其他子節(jié)點凸包上的點更靠近目的節(jié)點，然而此子節(jié)點(在Hull樹第一層中)并非距離目的節(jié)點更近節(jié)點。于是，GHTGR算法會直接選擇底層距離目的節(jié)點最近的孫子節(jié)點(在只有兩層的Hull樹結構中就是第二層)，將根節(jié)點到此子節(jié)點的路徑作為轉發(fā)序列，而不像GPSR算法那樣直接選取鄰居節(jié)點中距離目的節(jié)點更近的節(jié)點。

如圖6所示，當節(jié)點密度少于120時，GHTGR算法所采用的轉發(fā)次數(shù)比GPSR算法稍高，這是由于節(jié)點密度很低時，網(wǎng)絡中的空曠域的面積會很大，而此時GPSR算法只要沿著空曠域的邊緣來走，就會是最短路徑;GHTGR算法在Hull樹中的搜索，或許會偏離一到兩次空曠域的邊緣，因此轉發(fā)次數(shù)稍多。隨著節(jié)點密度的增大，GHTGR算法的平均轉發(fā)次數(shù)降至了GPSR的曲線以下，說明此時GHTGR比GPSR算法更能尋找到更短的轉發(fā)路徑。這通常是因為在GHTGR算法中，數(shù)據(jù)分組直接被送往凸包上的點，避免了在節(jié)點直接通訊范圍內的多次轉發(fā)。當節(jié)點密度增加到空曠域可以忽略不計時，即每個節(jié)點的直接通訊范圍內都可以找到符合貪婪法策略的下一跳節(jié)點，GHTGR與GPSR算法就向GREEDY算法靠近，接近于最短路徑算法。從圖形上來看，GHTGR算法與GPSR算法在路徑轉發(fā)次數(shù)(即路徑選擇)方面的差距不是很大，這說明每個算法基本上都找到一條與節(jié)點之間實際最短路徑相近的路徑。

圖6 不同算法節(jié)點轉發(fā)次數(shù)比較

圖7表明了網(wǎng)絡初始化時，GPSR算法形成網(wǎng)絡整體平面圖所花費資源與GHTGR通過交換報文形成局部Hull樹所耗費資源的對比情況。具體的報文轉發(fā)數(shù)量受限于網(wǎng)絡通信MAC層所使用的具體協(xié)議。在這里我們衡量的報文數(shù)為節(jié)點向外廣播它的狀態(tài)信息的報文數(shù)。實驗表明，采用GHTGR算法的初始報文交換數(shù)量遠遠低于GPSR算法的報文交換數(shù)量。這是因為GHTGR算法不要求每個節(jié)點獲得整個網(wǎng)絡所有節(jié)點的平面化拓撲結構，從而將大多數(shù)的報文局限在一跳或者兩跳的范圍之內，不會類似于GPSR算法進行全網(wǎng)規(guī)模的數(shù)據(jù)報文交換。

圖7 單位區(qū)域中不同節(jié)點密度報文轉發(fā)數(shù)量

圖8表示了不同空曠域數(shù)量下的路由路徑選擇情況。可以看到，當圖中空曠域數(shù)量較小時，GPSR算法所尋找到的轉發(fā)路徑與GHTGR算法尋找到的路徑差不多，然而隨著空曠域的數(shù)量增多，GPSR算法尋找路徑的跳數(shù)比GHTGR算法的路徑跳數(shù)增長更快。這表明，隨著空曠域的增加，在GPSR算法尋路過程中，數(shù)據(jù)報文僅僅依賴于空曠域的邊界轉發(fā)措施，導致數(shù)據(jù)分組的轉發(fā)路徑序列不一定會是到達目的節(jié)點轉發(fā)的最短路徑序列。然而，由于GHTGR算法采用了Hull樹的搜索，當空曠域足夠小時，本地節(jié)點Hull樹中所尋找到的節(jié)點轉發(fā)序列，就可能會繞過此空曠域。仿真結果表明，GHTGR算法確實在多空曠域的數(shù)據(jù)尋路過程中，相對于GPSR算法找到了更好的轉發(fā)路徑。

圖8 不同空曠域數(shù)量下節(jié)點轉發(fā)路徑跳數(shù)

4 總結

仿真實驗表明，相比于GPSR算法，GHTGR算法在保證尋路正確性的基礎上，較大地降低了算法用于初始化網(wǎng)絡拓撲結構所進行報文交換的數(shù)量。當節(jié)點密度較大時，該報文交換被局限于局部范圍以內，不會引起報文的全網(wǎng)廣播，有效地限制了報文增長的幅度。其次，在網(wǎng)絡空曠域較多的情況下，GHTGR算法對路徑的選擇同樣優(yōu)于GPSR算法，這是由于規(guī)避了GPSR算法引起的在空曠域邊沿頻繁的模式切換。

未來對于GHTGR算法來說，如何與地理區(qū)域廣播(GEOCAST)結合起來，進一步擴展地理路由算法的使用范圍。同時，針對實際應用中可能出現(xiàn)的當實際網(wǎng)絡中出現(xiàn)例如電磁干擾、輻射危害，或者其他雖然兩點之間仍可以通訊，但現(xiàn)實要求數(shù)據(jù)分組不能經(jīng)過這兩點之間傳播的特殊情形。如何增加適當?shù)臋嘀兀瑥亩钏惴軌蜻x擇更合適的轉發(fā)路徑。仍然是一個有待研究的問題。

［1］ 張衡陽，李瑩瑩，劉云輝.基于地理位置的無線傳感器網(wǎng)絡路由協(xié)議研究進展［J］.計算機應用研究，2008，25(1):18－21.

［2］ Brad Nelson Karp.Geographic Routing for Wireless Networks［D］.Harvard University，2000.

［3］ Prosenjit Bose，Andrej Brodnik，Svante Carlsson，et al.Online Routing in Convex Subdivisions［C］//ISAAC 2000.Berlin Heidelberg:Springer-Verlag，2000，47－59.

［4］ Brad Karp，Kung H T.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks［C］//ACM/IEEE MOBICOM，Boston，ACM Press，2000.243－254.

［5］ Fabian Kuhn，Roger Wattenhofer，Yan Zhang，et al.Geometric Ad-Hoc Routing:Of theory and practice［C］//PODC 2003，Boston，Massachusetts，2003.63－72.

［6］ Ben Leong.Geographic Routing Network Simulator［EB/OL］.2004.http://web.mit.edu/benleong/www/netsim.

［7］ Ben Leong.New Techniques for Geographic Routing［D］.Massachusetts Institute of Technology，2006.

［8］ 毛科技，趙小敏，宦若虹，等.基于散列值的以數(shù)據(jù)為中心路由協(xié)議［J］.傳感技術學報，2010，23(9):1308－1316.

［9］ 劉鐵流，巫詠群.基于能量優(yōu)化的無線傳感器網(wǎng)絡分簇路由算法研究［J］.傳感技術學報，2011，24(5):764－770.

［10］杜群，李偉華，蔣衛(wèi)華.一種適用于無線自組織網(wǎng)絡的安全路由優(yōu)化算法［J］.傳感技術學報，2010，23(3):447－452.

［11］ Ozawa T，Takahashi H.A Graph-Planarization Algorithm and Its Application to Random Graphs［J］.Graph Theory and Algorithms，1981，108:95－107.

［12］路綱，周明天，牛新征，等.無線網(wǎng)絡鄰近圖綜述［J］.軟件學報，2008，19(4):888－911.

［13］ Kin Yin Li.Convex Hull［J］.Mathematical Excalibur，2007，12(3):1－4.

［14］ Young-Jin Kim，Ramesh Govindan，Brad Karp，et al.Geographic Routing Made Practical［C］//Proceedings of the 2nd conference on Symposium on Networked Systems Design ＆ Implementation.Boston:ACM Press，2005，2:217－230.