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

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023)

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

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

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

圖1 空曠域(Void)

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

1 算法的構(gòu)建

1.1 平面化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與凸包

對(duì)于GPSR算法中face routing方法來說，得以運(yùn)行的一個(gè)首要條件就是要構(gòu)造一個(gè)平面圖來描述實(shí)際的網(wǎng)絡(luò)拓?fù)洹＿@樣的圖須滿足:網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)應(yīng)當(dāng)是平面化的［11］;平面圖中任意兩邊都不相交;平面圖中不存在不封閉的多邊形結(jié)構(gòu)。任何基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行尋路的路由協(xié)議，首先要解決的問題就是如何將現(xiàn)實(shí)的、由節(jié)點(diǎn)之間的通訊關(guān)系所形成的網(wǎng)絡(luò)拓?fù)溆涗浵聛恚⒔?jīng)過某種算法的處理，形成節(jié)點(diǎn)可以識(shí)別、處理、存儲(chǔ)的平面圖形結(jié)構(gòu)。常用的網(wǎng)絡(luò)拓?fù)鋱D［12］的方法有 UDG(unit disk graph)圖、最小生成樹(MST)、RNG圖(Relative Neighbor Graph)與GG圖(Gabriel Graph)。

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

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

X的凸包可以用X內(nèi)所有點(diǎn)(x1，…，xn)的線性組合來構(gòu)造

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

1.2 Hull樹存儲(chǔ)結(jié)構(gòu)與報(bào)文結(jié)構(gòu)

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

圖2 Hull樹存儲(chǔ)結(jié)構(gòu)

圖3 Hull樹構(gòu)建維護(hù)過程報(bào)文結(jié)構(gòu)

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

表1 Hull樹構(gòu)建維護(hù)過程報(bào)文格式及功能

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

2 算法設(shè)計(jì)

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

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

2.1 初始化階段

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

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

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

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

算法1 包裹法構(gòu)建凸包

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

存儲(chǔ)凸包結(jié)構(gòu)HullTree(nodes)

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

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

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

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

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

(1)Tree模式下:

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

(2)Tree-Greedy模式下:

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

(3)Greedy模式下:

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

3 算法仿真與分析

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

圖5 網(wǎng)絡(luò)中的Hull樹結(jié)構(gòu)以及算法兩點(diǎn)路由尋路路徑

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

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

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

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

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

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

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

4 總結(jié)

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

未來對(duì)于GHTGR算法來說，如何與地理區(qū)域廣播(GEOCAST)結(jié)合起來，進(jìn)一步擴(kuò)展地理路由算法的使用范圍。同時(shí)，針對(duì)實(shí)際應(yīng)用中可能出現(xiàn)的當(dāng)實(shí)際網(wǎng)絡(luò)中出現(xiàn)例如電磁干擾、輻射危害，或者其他雖然兩點(diǎn)之間仍可以通訊，但現(xiàn)實(shí)要求數(shù)據(jù)分組不能經(jīng)過這兩點(diǎn)之間傳播的特殊情形。如何增加適當(dāng)?shù)臋?quán)重，從而令算法能夠選擇更合適的轉(zhuǎn)發(fā)路徑。仍然是一個(gè)有待研究的問題。

［1］ 張衡陽，李瑩瑩，劉云輝.基于地理位置的無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展［J］.計(jì)算機(jī)應(yīng)用研究，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］.傳感技術(shù)學(xué)報(bào)，2010，23(9):1308－1316.

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

［10］杜群，李偉華，蔣衛(wèi)華.一種適用于無線自組織網(wǎng)絡(luò)的安全路由優(yōu)化算法［J］.傳感技術(shù)學(xué)報(bào)，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)絡(luò)鄰近圖綜述［J］.軟件學(xué)報(bào)，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.