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

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

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

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

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

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

圖1 空曠域(Void)

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

1 算法的構建

1.1 平面化網絡拓撲結構與凸包

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

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

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

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

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

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

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

圖2 Hull樹存儲結構

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

圖4 路由尋路過程數據分組報頭

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

表2 路由尋路過程數據分組報頭格式及功能

2 算法設計

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

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

2.1 初始化階段

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

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

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

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

算法1 包裹法構建凸包

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

存儲凸包結構HullTree(nodes)

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

2.2 數據分組轉發階段

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

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

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

(1)Tree模式下:

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

(2)Tree-Greedy模式下:

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

(3)Greedy模式下:

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

3 算法仿真與分析

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

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

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

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

圖6 不同算法節點轉發次數比較

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

圖7 單位區域中不同節點密度報文轉發數量

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

圖8 不同空曠域數量下節點轉發路徑跳數

4 總結

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

未來對于GHTGR算法來說，如何與地理區域廣播(GEOCAST)結合起來，進一步擴展地理路由算法的使用范圍。同時，針對實際應用中可能出現的當實際網絡中出現例如電磁干擾、輻射危害，或者其他雖然兩點之間仍可以通訊，但現實要求數據分組不能經過這兩點之間傳播的特殊情形。如何增加適當的權重，從而令算法能夠選擇更合適的轉發路徑。仍然是一個有待研究的問題。

［1］ 張衡陽，李瑩瑩，劉云輝.基于地理位置的無線傳感器網絡路由協議研究進展［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］ 毛科技，趙小敏，宦若虹，等.基于散列值的以數據為中心路由協議［J］.傳感技術學報，2010，23(9):1308－1316.

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

［10］杜群，李偉華，蔣衛華.一種適用于無線自組織網絡的安全路由優化算法［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］路綱，周明天，牛新征，等.無線網絡鄰近圖綜述［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.