無(wú)線傳感器網(wǎng)絡(luò)高可靠低維護(hù)地理路由協(xié)議

方效林，高宏，熊蜀光

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

1 引言

無(wú)線傳感器網(wǎng)絡(luò)(WSN, wireless sensor networks)[1,2]通過(guò)大量部署在監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)，采集網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對(duì)象的信息，并通過(guò)多跳的無(wú)線通信方式，將收集處理后的信息提供給終端用戶(hù)。在無(wú)線傳感器網(wǎng)絡(luò)中，地理路由協(xié)議使得數(shù)據(jù)分組可以通過(guò)多跳無(wú)線傳輸?shù)竭_(dá)指定地理位置附近的節(jié)點(diǎn)，因而具備廣泛應(yīng)用[3～5]。

地理路由算法一般都假設(shè)每個(gè)節(jié)點(diǎn)已知鄰居節(jié)點(diǎn)的坐標(biāo)信息，源節(jié)點(diǎn)已知目的節(jié)點(diǎn)的坐標(biāo)信息。坐標(biāo)信息的獲取可以通過(guò)定位算法來(lái)實(shí)現(xiàn)。在地理路由過(guò)程中，節(jié)點(diǎn)選擇距離目的節(jié)點(diǎn)最近的鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)數(shù)據(jù)分組的方式被稱(chēng)為貪婪轉(zhuǎn)發(fā)模式。貪婪轉(zhuǎn)發(fā)模式由于其原理簡(jiǎn)單，計(jì)算復(fù)雜度很低，并且生成的路徑接近最優(yōu)化路徑等特點(diǎn)，成為地理路由算法中最常用的轉(zhuǎn)發(fā)策略。但在實(shí)際的傳感器網(wǎng)絡(luò)中，由于網(wǎng)絡(luò)部署不均勻或者部分傳感器節(jié)點(diǎn)因故障或者能量耗盡而失效，會(huì)導(dǎo)致網(wǎng)絡(luò)形成“空洞”。節(jié)點(diǎn)用貪婪路由算法轉(zhuǎn)發(fā)數(shù)據(jù)分組遇到空洞時(shí)，由于找不到比自身更接近目的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，因而數(shù)據(jù)分組無(wú)法繼續(xù)轉(zhuǎn)發(fā)，貪婪路由失敗。貪婪路由失敗時(shí)，就需要一種方法將數(shù)據(jù)分組繞過(guò)空洞傳輸?shù)侥康墓?jié)點(diǎn)。

數(shù)據(jù)分組以沿著空洞邊緣繞過(guò)空洞的轉(zhuǎn)發(fā)方式，稱(chēng)為周邊轉(zhuǎn)發(fā)模式?，F(xiàn)有的地理路由算法通常具有貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)2種模式，不同路由算法只是采用不同的模式切換機(jī)制。貪婪轉(zhuǎn)發(fā)是基本的轉(zhuǎn)發(fā)模式，當(dāng)貪婪轉(zhuǎn)發(fā)遇到路由空洞而失敗時(shí)，路由算法就轉(zhuǎn)入周邊轉(zhuǎn)發(fā)模式，直到能夠恢復(fù)貪婪轉(zhuǎn)發(fā)模式時(shí)又進(jìn)入貪婪轉(zhuǎn)發(fā)模式。貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)2種模式相互運(yùn)用能夠有效地繞過(guò)路由空洞，保證數(shù)據(jù)的可靠傳輸。

雖然基于貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)2種模式的地理路由算法需要維護(hù)的路由表小，路由效率高，但是它們都共同面臨網(wǎng)絡(luò)平面化問(wèn)題。網(wǎng)絡(luò)平面化需要將網(wǎng)絡(luò)在周邊轉(zhuǎn)發(fā)模式之前進(jìn)行平面化處理，即將網(wǎng)絡(luò)通過(guò)平面化算法，形成以節(jié)點(diǎn)為頂點(diǎn)、鏈路為邊，并且不存在交叉邊的圖。以前有關(guān)于地理路由算法的論文[4]，但是基于UDG圖。UDG圖是理想的節(jié)點(diǎn)通信方式，適用于理想環(huán)境下的理論分析，但在真實(shí)的網(wǎng)絡(luò)環(huán)境中并不可行[5]。

本文提出一種具有高可靠性和低維護(hù)成本的地理路由協(xié)議RPR，其基本思想是將網(wǎng)絡(luò)劃分為規(guī)則多邊形區(qū)域，并在貪心路由失敗時(shí)將多邊形區(qū)域內(nèi)的所有節(jié)點(diǎn)看作一個(gè)虛擬節(jié)點(diǎn)進(jìn)行周邊路由。多邊形區(qū)域間通信能夠降低平均路由路徑長(zhǎng)度，從而提高了路由的可靠性?；趨^(qū)域劃分的網(wǎng)絡(luò)平面化策略不需要檢測(cè)和刪除相交鏈路，因此減少了路由維護(hù)開(kāi)銷(xiāo)。

與現(xiàn)有平面化方法相比，基于地理位置劃分的平面化方法有以下優(yōu)勢(shì)：①網(wǎng)絡(luò)平面化方法簡(jiǎn)單有效；②可以實(shí)現(xiàn)多邊形間可靠路由算法；③能夠減少路由路徑長(zhǎng)度。

將地理位置劃分為規(guī)則多邊形區(qū)域可以有多種方法，如將網(wǎng)絡(luò)劃分為規(guī)則正方形、等邊三角形、正六邊形等。每種劃分方法都有各自的優(yōu)缺點(diǎn)，可以根據(jù)不同的應(yīng)用選用不同的劃分方式。在二維平面劃分方法中，正六邊形劃分方法能夠最好地保留網(wǎng)絡(luò)的連通性，從而提高路由的可靠性，本文于是選擇正六邊形的劃分方法進(jìn)行網(wǎng)絡(luò)平面化處理。

本文的主要貢獻(xiàn)如下。

1) 使用區(qū)域劃分的方法進(jìn)行網(wǎng)絡(luò)平面化處理。將網(wǎng)絡(luò)在地理上劃分為規(guī)則六邊形區(qū)域，該平面化處理方法簡(jiǎn)單有效，能降低平面化處理的通信開(kāi)銷(xiāo)。

2) 提出基于區(qū)域劃分的地理路由協(xié)議RPR仍具有貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)2種模式。在貪心路由失敗時(shí)，將多邊形區(qū)域當(dāng)作一個(gè)整體進(jìn)行周邊路由。此方法能夠減小平均路由路徑長(zhǎng)度，從而降低路由開(kāi)銷(xiāo)，提高路由的可靠性。

3) 分析了區(qū)域內(nèi)不連通情況。劃分的六邊形區(qū)域內(nèi)節(jié)點(diǎn)組成的圖可能不連通，本文給出不連通情況下的路由方法，并分析了區(qū)域內(nèi)不連通概率。

4) 對(duì)提出的平面化方法和地理路由策略與現(xiàn)有的方法作了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示本文方法具有維護(hù)代價(jià)低，路由可靠性高等優(yōu)點(diǎn)。

2 相關(guān)工作

目前已有很多關(guān)于地理路由算法的工作，其基本過(guò)程一致，都是在貪心模式失敗時(shí)轉(zhuǎn)入周邊模式。假設(shè)數(shù)據(jù)分組的目的節(jié)點(diǎn)為t，路由算法在節(jié)點(diǎn)s貪心轉(zhuǎn)發(fā)失敗進(jìn)入周邊轉(zhuǎn)發(fā)模式，以下是各種平面地理路由算法周邊轉(zhuǎn)發(fā)模式的轉(zhuǎn)發(fā)算法。GFG(greedy-face-greedy)算法[6]繞平面尋找與連線st相交的邊，以它們的交點(diǎn)p臨近目的節(jié)點(diǎn)的方式逐步向目的節(jié)點(diǎn)靠近。GFG算法繞平面的方向與進(jìn)入的面與平面圖的內(nèi)表面和外表面有關(guān)，進(jìn)入內(nèi)表面時(shí)算法按逆時(shí)針?lè)较蚶@平面轉(zhuǎn)發(fā)數(shù)據(jù)分組，進(jìn)入外表面時(shí)方向正好相反。Compass Routing II算法[7]與GFG類(lèi)似，不同的是Compass Routing II繞平面一周，找出與st相交并且距離目的節(jié)點(diǎn)最近的交點(diǎn)p，算法將數(shù)據(jù)分組轉(zhuǎn)發(fā)到交點(diǎn)p所在的另一個(gè)面。GPSR(greedy perimeter stateless routing)算法[3]按右手定則繞平面尋找一個(gè)頂點(diǎn)u，它與下一個(gè)頂點(diǎn)v組成的邊uv與st相交，算法從節(jié)點(diǎn)u開(kāi)始進(jìn)入下一個(gè)平面繼續(xù)路由。GPSR算法與GFG算法的不同之處在于，GPSR總是試圖進(jìn)入離目的節(jié)點(diǎn)更近的另一個(gè)平面，而GFG進(jìn)入的平面有可能沒(méi)有改變。GOAFR+(greedy other adaptive face routing)算法[8]繞平面一周，找出離目的節(jié)點(diǎn)最近的節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)開(kāi)始進(jìn)入下一個(gè)平面。為區(qū)分GOAFR+，文獻(xiàn)[4]中將 greedy other adaptive face routing[9]命名為GOAFR++。GOAFR++算法繞平面一周，找出平面上距離目的節(jié)點(diǎn)最近的點(diǎn)p(點(diǎn)p可以是某條邊上的一點(diǎn))，并從點(diǎn)p所在邊的2個(gè)頂點(diǎn)其中一個(gè)進(jìn)入下一個(gè)平面。GPVFR(greedy path vector face routing)算法[10]繞平面尋找頂點(diǎn)u，它與下一個(gè)頂點(diǎn)v組成的邊uv與st相交，算法從節(jié)點(diǎn)u開(kāi)始進(jìn)入下一個(gè)平面繼續(xù)路由，但是不再保存st，而以u(píng)t作為判斷與面相交的直線。文獻(xiàn)[4]對(duì)上面同種路由算法作了總結(jié)。

以上所有算法都需要預(yù)先將網(wǎng)絡(luò)進(jìn)行平面化處理。將網(wǎng)絡(luò)進(jìn)行平面化處理算法有 GG[11]、RNG[12]和LDT[13]，這3個(gè)算法都是基于UDG(unit-disk graph)或偽UDG圖的。在UDG圖中，任意2節(jié)點(diǎn)間有邊當(dāng)且僅當(dāng)它們之間的歐幾里德距離小于等于一個(gè)固定的發(fā)射半徑，這個(gè)發(fā)射半徑可以認(rèn)為是節(jié)點(diǎn)的無(wú)線發(fā)射半徑。偽UDG圖是UDG圖的擴(kuò)展，它的發(fā)射半徑不是固定值，而是夾在一個(gè)最大值和一個(gè)最小值之間的數(shù)。在GG圖中，任意2個(gè)頂點(diǎn)u和v間有邊當(dāng)且僅當(dāng)以(u,v)為直徑的圓內(nèi)不包含其他頂點(diǎn)。在RNG圖中，任意2個(gè)頂點(diǎn)u和v間有邊，當(dāng)且僅當(dāng)以u(píng)為圓心以(u,v)為半徑的圓和以v為圓心以(u，v)為半徑的圓的相交部分不包含其他頂點(diǎn)。局部Delaunay三角剖分(LDT)算法中，假設(shè)T為頂點(diǎn)集V的任意三角剖分，則T是V的一個(gè)Delaunay三角剖分，當(dāng)且僅當(dāng)T中的每個(gè)三角形的外接圓的內(nèi)部不包含V中任何的點(diǎn)。以上平面化算法在基于UDG圖的網(wǎng)絡(luò)中能夠很好地進(jìn)行平面化處理，但是在真實(shí)的傳感器網(wǎng)絡(luò)環(huán)境中這些算法不實(shí)用。

為了讓平面地理路由算法能夠適用于真實(shí)的傳感器網(wǎng)絡(luò)應(yīng)用，Y.J.Kim等人提出了CLDP平面化算法[5]。CLDP算法是目前提出的唯一適用于不滿(mǎn)足 UDG圖條件的傳感器網(wǎng)絡(luò)平面化地理路由算法。該算法對(duì)網(wǎng)絡(luò)中的每條鏈路都發(fā)送探測(cè)分組，等待探測(cè)分組返回之后，在確定刪除某些邊后不影響網(wǎng)絡(luò)連通性時(shí)才將該邊刪除，從而達(dá)到平面化。CLDP算法能夠保證周邊轉(zhuǎn)發(fā)機(jī)制在實(shí)際復(fù)雜的傳感器網(wǎng)絡(luò)中正確地運(yùn)行，但是每個(gè)節(jié)點(diǎn)都要發(fā)探測(cè)包以確定刪除一些邊，開(kāi)銷(xiāo)相當(dāng)大。平均每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)生存時(shí)間里大約需要發(fā)送幾百到上千個(gè)數(shù)據(jù)分組來(lái)進(jìn)行和維持平面化過(guò)程。LCR算法[14]針對(duì)CLDP算法在網(wǎng)絡(luò)初始化階段對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)進(jìn)行平面化而導(dǎo)致開(kāi)銷(xiāo)較大的缺陷得到改進(jìn)。LCR算法在初始化時(shí)節(jié)點(diǎn)并不進(jìn)行平面化處理，而是在數(shù)據(jù)分組路由過(guò)程中遇到路由回路時(shí)，才進(jìn)行局部CLDP平面化。在局部CLDP平面化處理結(jié)束后繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)分組。LCR算法不僅能在非 UDG網(wǎng)絡(luò)中保證數(shù)據(jù)的可靠傳輸，并且LCR在平面化處理中的開(kāi)銷(xiāo)比CLDP算法降低2個(gè)數(shù)量級(jí)。

3 區(qū)域劃分的平面化方法

文獻(xiàn)[15]假設(shè)傳感器節(jié)點(diǎn)的發(fā)射半徑是一個(gè)固定值，分析了三角形、正方形和六邊形3種網(wǎng)絡(luò)拓?fù)涞膬?yōu)劣，并得出三邊形拓?fù)淇煽啃宰罡叩慕Y(jié)論。如圖1所示，三角形網(wǎng)絡(luò)拓?fù)涿總€(gè)節(jié)點(diǎn)規(guī)則地與6個(gè)節(jié)點(diǎn)相連，正方形拓?fù)渑c4個(gè)節(jié)點(diǎn)相連，六邊形拓?fù)渑c3個(gè)節(jié)點(diǎn)相連。其中，三角形網(wǎng)絡(luò)的可靠性最好，六邊形網(wǎng)絡(luò)的連通覆蓋性最好，正方形網(wǎng)絡(luò)的可靠性和網(wǎng)絡(luò)連通覆蓋性介于前2個(gè)之間，但是它的實(shí)現(xiàn)最簡(jiǎn)單。由于傳感器網(wǎng)絡(luò)具有不確定性，如何提高路由算法的成功率成為一個(gè)主要研究問(wèn)題。本文選擇可靠性最好的三角形網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)路由算法，最大限度地保持網(wǎng)絡(luò)的連通性和可靠性，提高路由算法的成功率。

圖1 幾種規(guī)則多邊形網(wǎng)絡(luò)拓?fù)?/p>

在真實(shí)的傳感器網(wǎng)絡(luò)中，規(guī)則多邊形網(wǎng)絡(luò)拓?fù)涫遣淮嬖诘?。但是通過(guò)對(duì)地理位置進(jìn)行劃分，將每個(gè)小區(qū)域內(nèi)的所有節(jié)點(diǎn)看成一個(gè)虛擬節(jié)點(diǎn)，小區(qū)域之間通信變成虛擬節(jié)點(diǎn)之間通信，這樣得到的虛擬網(wǎng)絡(luò)具有多邊形網(wǎng)絡(luò)拓?fù)涞男再|(zhì)。本文通過(guò)以下步驟得到多邊形網(wǎng)絡(luò)拓?fù)洌簩⒄麄€(gè)網(wǎng)絡(luò)平面進(jìn)行正六邊形區(qū)域劃分，每個(gè)正六邊形區(qū)域內(nèi)的所有節(jié)點(diǎn)都被當(dāng)作一個(gè)虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)的地理坐標(biāo)為正六邊形的中心，一個(gè)區(qū)域只與它的相鄰區(qū)域進(jìn)行通信。正六邊形劃分得到的虛擬網(wǎng)絡(luò)拓?fù)鋵?shí)際上是三角形網(wǎng)絡(luò)拓?fù)?，如圖2所示。

圖2 虛擬三角形網(wǎng)絡(luò)拓?fù)?/p>

給定一個(gè)網(wǎng)絡(luò)，假設(shè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都知道自身的地理位置信息，本文將地理位置進(jìn)行正六邊形區(qū)域劃分。只要?jiǎng)澐执笮∫恢?，每個(gè)節(jié)點(diǎn)都可以很容易計(jì)算出自身處于哪個(gè)六邊形區(qū)域，如圖3所示。很顯然，按照?qǐng)D3的劃分方式對(duì)地理位置進(jìn)行劃分得到的虛擬網(wǎng)絡(luò)拓?fù)涫且粋€(gè)平面圖。為了敘述簡(jiǎn)便，下面給出區(qū)域劃分的符號(hào)描述。

圖3 正六邊形地理位置劃分

給定一個(gè)網(wǎng)絡(luò)G=(V,E)，其中，V為網(wǎng)絡(luò)中節(jié)點(diǎn)集合，E為網(wǎng)絡(luò)中鏈路的集合。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都知道自身的地理位置坐標(biāo)信息。

圖3中，網(wǎng)絡(luò)放置在一個(gè)二維平面R上，其中，R由許多正六邊形區(qū)域組成，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)屬于一個(gè)六邊形區(qū)域。每個(gè)小六邊形區(qū)域表示為R(i,j)，其中，0 ≤i＜ ∞, 0≤j＜ ∞ ，六邊形區(qū)域邊長(zhǎng)為L(zhǎng)。區(qū)域R(i，j)的中心O(i,j)=(x,y)，其中，x=(1/2+3i/2)L。若i為偶數(shù)，則y=(1+2j)L；若i為奇數(shù)，則y=2jL。

定義1 對(duì)于給定網(wǎng)絡(luò)G=(V,E)，區(qū)域R(i,j)是連通的，當(dāng)且僅當(dāng)以區(qū)域R(i,j)內(nèi)的頂點(diǎn)組成的圖G’=(V’,E’)是連通的，其中，V' ={v|v∈R(i,j)}，E' = {uv|u,v∈R(i,j),uv∈E}。

定義2 節(jié)點(diǎn)v所在的六邊形區(qū)域?yàn)镽(v)。

定義3 節(jié)點(diǎn)v在區(qū)域R(v)中的連通分量記為CP(v)，其中，CP(v)是以區(qū)域R(v)內(nèi)的頂點(diǎn)組成的圖G’=(V’,E’)的連通子圖。

定義4 節(jié)點(diǎn)v所在六邊形區(qū)域的中心為O(v)。

定義5 如果2個(gè)六邊形區(qū)域R(i,j)和R(r,s)相連，則區(qū)域R(i,j)中至少存在一個(gè)節(jié)點(diǎn)u和區(qū)域R(r,s)中的某節(jié)點(diǎn)v之間有鏈路，即 ?u∈R(i,j) ，?v∈R(r,s)且uv∈E，記作R(i,j)∝R(r,s)。記區(qū)域R(i,j)的相連區(qū)域集合為C(i,j)。記節(jié)點(diǎn)u的相連區(qū)域集合為C(u)。

定義6 區(qū)域R(i,j)的相鄰區(qū)域N(i,j)是圍繞區(qū)域R(i,j)的6個(gè)六邊形區(qū)域，即R(i,j)的相鄰區(qū)域?yàn)镹(i,j) = {R(i,j± 1 ),R(i± 1 ,j),R(i± 1 ,j+ 1 )}。

由定義5和定義6，顯然相連區(qū)域與相鄰區(qū)域是不同的概念，但是為了簡(jiǎn)化平面化過(guò)程，本文令六邊形區(qū)域的路由相連區(qū)域RC(i,j) =C(i,j) ∩N(i,j)。這種設(shè)置是合理的，因?yàn)橹灰呅蔚倪呴L(zhǎng)選取得足夠長(zhǎng)，跨區(qū)域的2個(gè)節(jié)點(diǎn)一般不能互相通信，這樣就可以保證得到的虛擬圖是一個(gè)平面圖，并且不需要?jiǎng)h除鏈路。

4 區(qū)域邊長(zhǎng)選擇

六邊形區(qū)域邊長(zhǎng)L的選取很重要，它會(huì)影響到平面化算法的好壞。由于傳感器節(jié)點(diǎn)具有一定的通信范圍，距離在通信范圍內(nèi)的節(jié)點(diǎn)間有可能互相通信，但是距離超過(guò)通信范圍的節(jié)點(diǎn)間一般不能互相通信。如果選擇邊長(zhǎng)L的值過(guò)小，二維平面R的劃分太細(xì)，會(huì)導(dǎo)致有些小區(qū)域內(nèi)可能沒(méi)有傳感器節(jié)點(diǎn)。而且L選取過(guò)小，還會(huì)導(dǎo)致有些不相鄰的區(qū)域相連。此時(shí)為了得到路由相連區(qū)域，平面化過(guò)程會(huì)刪除一些跨區(qū)域的鏈路，這降低了網(wǎng)絡(luò)的連通性。

六邊形區(qū)域邊長(zhǎng)L的選取也會(huì)影響路由算法性能。如果L選取過(guò)小，網(wǎng)絡(luò)的連通性降低，這有可能降低路由的可靠性。另一方面，L選取過(guò)大，R的劃分太粗糙，每個(gè)區(qū)域內(nèi)傳感器節(jié)點(diǎn)多，這樣會(huì)增加區(qū)域內(nèi)節(jié)點(diǎn)之間的通信開(kāi)銷(xiāo)，增加維護(hù)路由相連區(qū)域的開(kāi)銷(xiāo)。而且L選取過(guò)大，也會(huì)導(dǎo)致每個(gè)區(qū)域內(nèi)不連通的概率增大。區(qū)域內(nèi)不連通，會(huì)使路由算法設(shè)計(jì)困難，這將在后面的章節(jié)介紹。本文先考慮每個(gè)區(qū)域內(nèi)的節(jié)點(diǎn)組織成的局部網(wǎng)絡(luò)是連通的情況，然后再介紹區(qū)域內(nèi)不連通情況。

判斷區(qū)域劃分的好壞主要有2個(gè)方面，一方面是平面化使刪除的鏈路越少越好；另一方面是區(qū)域內(nèi)聚性越強(qiáng)越好，即區(qū)域內(nèi)任意2節(jié)點(diǎn)之間距離越短越好。

令節(jié)點(diǎn)的通信距離為r’。為了簡(jiǎn)化平面化過(guò)程，本文令六邊形區(qū)域邊長(zhǎng)L大于通信半徑，即'Lr≥。這種劃分不會(huì)對(duì)網(wǎng)絡(luò)的連通性產(chǎn)生影響，并且能最大限度地保留網(wǎng)絡(luò)連通狀態(tài)。另外，為了降低區(qū)域內(nèi)不連通概率，減小路由相連區(qū)域維護(hù)開(kāi)銷(xiāo)，平面化過(guò)程應(yīng)當(dāng)盡可能選擇較小的區(qū)域邊長(zhǎng)。綜合以上2方面因素，本文選取區(qū)域邊長(zhǎng) 'Lr= 。

5 區(qū)域平面化路由算法

第4節(jié)介紹了如何將網(wǎng)絡(luò)平面化，網(wǎng)絡(luò)平面化是進(jìn)行平面地理路由的前提。解決了網(wǎng)絡(luò)平面化問(wèn)題后使用多種已有的平面路由算法。本文提出一種針對(duì)平面化區(qū)域網(wǎng)絡(luò)的路由算法，稱(chēng)為PGR算法。PGR算法有3種工作模式：節(jié)點(diǎn)貪心模式、區(qū)域貪心模式和區(qū)域周邊模式。算法從節(jié)點(diǎn)貪心模式開(kāi)始，節(jié)點(diǎn)貪心模式中若存在距離目的節(jié)點(diǎn)更近的鄰居節(jié)點(diǎn)，則將數(shù)據(jù)分組轉(zhuǎn)發(fā)給離目的節(jié)點(diǎn)最近的那個(gè)鄰居節(jié)點(diǎn)。若不存在距離目的節(jié)點(diǎn)更近的鄰居節(jié)點(diǎn)，算法進(jìn)入?yún)^(qū)域貪心模式。在區(qū)域貪心模式中，如果區(qū)域的路由相連區(qū)域中存在距離目的節(jié)點(diǎn)更近的節(jié)點(diǎn)，則將數(shù)據(jù)分組通過(guò)區(qū)域間傳輸轉(zhuǎn)發(fā)到這個(gè)節(jié)點(diǎn)所在的區(qū)域。如果路由相連區(qū)域中不存在距離目的節(jié)點(diǎn)更近的節(jié)點(diǎn)，則算法進(jìn)入?yún)^(qū)域周邊模式。在區(qū)域周邊模式中，將每個(gè)六邊形小區(qū)域看作是一個(gè)節(jié)點(diǎn)。根據(jù)右手定則，區(qū)域周邊算法將數(shù)據(jù)分組繞空洞沿空洞邊緣區(qū)域路由，直到到達(dá)一個(gè)能夠進(jìn)入?yún)^(qū)域貪心模式的區(qū)域，或者到達(dá)一個(gè)能夠進(jìn)入節(jié)點(diǎn)貪心模式的節(jié)點(diǎn)。假設(shè)節(jié)點(diǎn)s要路由數(shù)據(jù)分組給目的節(jié)點(diǎn)t，平面化區(qū)域路由策略1所示。

策略1 平面化區(qū)域路由策略

5.1 節(jié)點(diǎn)貪心路由模式

節(jié)點(diǎn)貪心路由是最基本的路由策略，節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)分組時(shí)首先判斷是否能進(jìn)行節(jié)點(diǎn)貪心路由。如果轉(zhuǎn)發(fā)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中存在距離目的節(jié)點(diǎn)t更近的節(jié)點(diǎn)，則將數(shù)據(jù)分組轉(zhuǎn)發(fā)給距離t最近的節(jié)點(diǎn)。

5.2 區(qū)域貪心路由模式

路由策略只有在節(jié)點(diǎn)貪心路由失敗時(shí)才進(jìn)入?yún)^(qū)域貪心路由模式。區(qū)域貪心模式如圖4所示，黑點(diǎn)表示傳感器節(jié)點(diǎn)，節(jié)點(diǎn)之間的連線表示節(jié)點(diǎn)之間存在雙向鏈路。假設(shè)節(jié)點(diǎn)s有一數(shù)據(jù)分組要傳輸?shù)侥康墓?jié)點(diǎn)t，圖中節(jié)點(diǎn)s沒(méi)有距離目的節(jié)點(diǎn)t更近的鄰居節(jié)點(diǎn)，算法進(jìn)入?yún)^(qū)域貪心模式。在區(qū)域貪心模式中，節(jié)點(diǎn)s在區(qū)域R(s)內(nèi)存在節(jié)點(diǎn)n1與另一個(gè)區(qū)域內(nèi)節(jié)點(diǎn)n2有鏈路，且節(jié)點(diǎn)n2比節(jié)點(diǎn)s距離目的節(jié)點(diǎn)更近，因此節(jié)點(diǎn)s可以將數(shù)據(jù)分組通過(guò)區(qū)域間通信轉(zhuǎn)發(fā)給節(jié)點(diǎn)n2所在區(qū)域R(n2)。

圖4 區(qū)域貪心路由

通過(guò)以上例子，現(xiàn)給出區(qū)域貪心模式形式化描述。假設(shè)目的節(jié)點(diǎn)為t，算法在節(jié)點(diǎn)s進(jìn)入?yún)^(qū)域貪心模式。節(jié)點(diǎn)s所在區(qū)域?yàn)镽(s)，如果 ?n∈C(s) ∪R(s)，s'∈R(s),使得s'∈CP(s),s'n∈E,且D(n,t)＜D(s,t)，則算法將數(shù)據(jù)分組轉(zhuǎn)發(fā)給使得D(n,t)最小的n所在區(qū)域R(n)，其中，D(u,v)為節(jié)點(diǎn)u和v間的距離。

5.3 區(qū)域周邊路由模式

區(qū)域周邊模式將六邊形區(qū)域當(dāng)作一個(gè)虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)的坐標(biāo)為六邊形區(qū)域的中心，虛擬節(jié)點(diǎn)的路由表中存放的是路由相連區(qū)域。以虛擬節(jié)點(diǎn)組成的網(wǎng)絡(luò)是一個(gè)平面網(wǎng)絡(luò)，對(duì)于平面網(wǎng)絡(luò)已有多種算法可實(shí)現(xiàn)地理路由算法。

區(qū)域周邊模式如圖5所示，黑色圓點(diǎn)表示節(jié)點(diǎn)，陰影部分表示空洞，假設(shè)數(shù)據(jù)分組的目的節(jié)點(diǎn)為t，路由算法在節(jié)點(diǎn)s區(qū)域貪心模式失敗進(jìn)入?yún)^(qū)域周邊模式。連線O(s)O(t)表示源區(qū)域R(s)與目的區(qū)域R(t)中心的連線。區(qū)域周邊路由算法以連線O(s)O(t)為基準(zhǔn)，使用右手法則逆時(shí)針尋找到第一個(gè)相鄰區(qū)域R(v2)并通過(guò)區(qū)域間通信將數(shù)據(jù)轉(zhuǎn)發(fā)到區(qū)域R(v2)。區(qū)域R(v2)收到數(shù)據(jù)分組后以連線O(v2)O(v1)為基準(zhǔn)，逆時(shí)針尋找到第一個(gè)相鄰區(qū)域R(v3)。如此反復(fù)，一直到目的區(qū)域，最后通過(guò)區(qū)域內(nèi)通信方式將數(shù)據(jù)分組轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。數(shù)據(jù)分組先后經(jīng)過(guò)的區(qū)域如圖5箭頭所示。

圖5 區(qū)域周邊路由

綜上所述，假設(shè)節(jié)點(diǎn)s要路由數(shù)據(jù)分組給目的節(jié)點(diǎn)t，具體的平面化區(qū)域路由策略2如下。

策略2 平面化區(qū)域路由策略

6 區(qū)域內(nèi)不連通性

前面給出了平面化方法和地理路由方法?；诹呅尉W(wǎng)絡(luò)的平面化方法非常簡(jiǎn)單，它不需要?jiǎng)h除交叉鏈路，從而最大限度地保留了網(wǎng)絡(luò)的連通性。以虛擬節(jié)點(diǎn)為頂點(diǎn)的平面網(wǎng)絡(luò)是將六邊形區(qū)域當(dāng)成一個(gè)整體，因此，現(xiàn)有的平面地理路由算法都可以應(yīng)用到基于六邊形區(qū)域劃分的平面地理路由中。但是基于區(qū)域劃分的平面化方法可能會(huì)出現(xiàn)區(qū)域內(nèi)不連通情況，如圖6所示。在圖6中，區(qū)域Rs內(nèi)有2個(gè)連通分量CP1和CP2。假設(shè)數(shù)據(jù)分組要從節(jié)點(diǎn)s轉(zhuǎn)發(fā)到節(jié)點(diǎn)t，通過(guò)區(qū)域周邊路由，數(shù)據(jù)分組會(huì)從區(qū)域Rs到達(dá)區(qū)域R1后又回到區(qū)域Rs，假設(shè)數(shù)據(jù)分組仍舊返回到連通分量CP1，此時(shí)出現(xiàn)路由環(huán)。路由環(huán)是所有路由算法應(yīng)該避免的問(wèn)題。下面給出解決圖6所示路由環(huán)問(wèn)題的方法。

圖6 區(qū)域內(nèi)不連通情況

對(duì)路由相連區(qū)域中每個(gè)連通分量給定一個(gè)標(biāo)識(shí)(本文以簇頭節(jié)點(diǎn)號(hào)為一個(gè)連通分量的標(biāo)識(shí))。周邊模式路由表中每個(gè)連通分量都初始化為clean。對(duì)于數(shù)據(jù)分組P，若P從路由相連區(qū)域RCi的連通分量CPj轉(zhuǎn)發(fā)而來(lái)，則將這個(gè)連通分量標(biāo)記為Pin。數(shù)據(jù)分組若轉(zhuǎn)發(fā)給路由相連區(qū)域RCi的連通分量CPj，則將這個(gè)連通分量標(biāo)記為Pout。顯然，如果向已經(jīng)被標(biāo)記為Pout的連通分量轉(zhuǎn)發(fā)數(shù)據(jù)分組，則會(huì)發(fā)生路由環(huán)。因此虛擬節(jié)點(diǎn)只能向標(biāo)記為clean或者Pin的連通分量轉(zhuǎn)發(fā)數(shù)據(jù)分組。并且，虛擬節(jié)點(diǎn)應(yīng)當(dāng)首先向標(biāo)記為 clean的連通分量轉(zhuǎn)發(fā)數(shù)據(jù)分組，若找不到標(biāo)識(shí)為clean的連通分量時(shí)，才向標(biāo)記為Pin的連通分量轉(zhuǎn)發(fā)數(shù)據(jù)分組。在向標(biāo)記為Pin的連通分量轉(zhuǎn)發(fā)數(shù)據(jù)分組時(shí)，應(yīng)對(duì)標(biāo)記為Pin的連通分量按標(biāo)記時(shí)間先后排序，每次尋找時(shí)間最靠后的連通分量轉(zhuǎn)發(fā)。

除了路由中間區(qū)域內(nèi)不連通，目的節(jié)點(diǎn)所在區(qū)域也可能不連通。由于任意2個(gè)傳感器節(jié)點(diǎn)之間邊長(zhǎng)都不超過(guò)區(qū)域邊長(zhǎng)，因此數(shù)據(jù)分組必須通過(guò)目的區(qū)域的相鄰區(qū)域才能轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。如圖7所示，假設(shè)數(shù)據(jù)分組傳輸?shù)焦?jié)點(diǎn)s，節(jié)點(diǎn)s和目的節(jié)點(diǎn)t在同一個(gè)區(qū)域但不在同一個(gè)連通分量，此時(shí)讓數(shù)據(jù)分組繞著區(qū)域R(s)的相鄰區(qū)域行走，則可以找到某個(gè)與目的節(jié)點(diǎn)t所在的連通分量相連的相鄰區(qū)域。

圖7 區(qū)域內(nèi)不連通情況

7 區(qū)域內(nèi)不連通概率分析

假設(shè)節(jié)點(diǎn)是隨機(jī)布置在一個(gè)區(qū)域內(nèi)，則在布置節(jié)點(diǎn)之前，任意2個(gè)節(jié)點(diǎn)間都以一定的概率p可以互相通信，此時(shí)所有節(jié)點(diǎn)組成的圖可以看作一個(gè)隨機(jī)圖。給定n個(gè)頂點(diǎn)，任意兩頂點(diǎn)之間有邊的概率為p，則這個(gè)隨機(jī)圖不連通的概率的上界qn如式(1)所示[16]。

式(1)給出了隨機(jī)圖不連通概率的上界，為了計(jì)算qn，還需要給出2個(gè)節(jié)點(diǎn)間能通信的概率p。

圖8給出幾種不同通信概率p時(shí)隨機(jī)圖不連通的概率。從圖可知，在六邊形區(qū)域內(nèi)隨機(jī)布置節(jié)點(diǎn)，當(dāng)區(qū)域內(nèi)節(jié)點(diǎn)的個(gè)數(shù)為2個(gè)或3個(gè)時(shí)，區(qū)域內(nèi)節(jié)點(diǎn)不連通的概率最高(注意，區(qū)域內(nèi)不連通和區(qū)域間不連通不是一個(gè)概念，當(dāng)區(qū)域內(nèi)節(jié)點(diǎn)個(gè)數(shù)為1時(shí)，區(qū)域內(nèi)不連通概率為0)。隨著節(jié)點(diǎn)個(gè)數(shù)增加，區(qū)域內(nèi)不連通概率急劇減小，但是當(dāng)區(qū)域內(nèi)的節(jié)點(diǎn)個(gè)數(shù)達(dá)到一定數(shù)量后，區(qū)域內(nèi)不連通的概率變化趨于平緩。因此，只要當(dāng)節(jié)點(diǎn)布置達(dá)到一定密度后，就能以較高的概率使得區(qū)域連通。

圖8 不同通信概率下隨機(jī)圖不連通的概率

假設(shè)有n個(gè)節(jié)點(diǎn)落入了某個(gè)六邊形區(qū)域R0內(nèi)，則這n個(gè)節(jié)點(diǎn)在區(qū)域R0內(nèi)也是隨機(jī)分布的。為了計(jì)算區(qū)域R0內(nèi)任意兩節(jié)點(diǎn)(x1,y1)和(x2,y2)之間距離的分布，如圖9所示，節(jié)點(diǎn)與某一點(diǎn)v的距離為r的概率為，其中，l是以v為圓心，以r為半徑的圓，與六邊形區(qū)域重疊部分的弧長(zhǎng)。任意2個(gè)節(jié)點(diǎn)之間距離為r的概率分布如式(2)所示。

其中，積分區(qū)域?yàn)榱呅螀^(qū)域R0。重疊弧長(zhǎng)l隨著圓心和半徑的變化而變化，不能用一個(gè)簡(jiǎn)單的公式來(lái)刻畫(huà)，因此用數(shù)學(xué)公式精確計(jì)算六邊形區(qū)域內(nèi)任意2個(gè)點(diǎn)距離r的分布很復(fù)雜。本文使用隨機(jī)算法近似計(jì)算兩點(diǎn)的距離分布，如圖 10所示。在六邊形區(qū)域內(nèi)隨機(jī)選取2個(gè)點(diǎn)，并計(jì)算這2個(gè)點(diǎn)之間的距離，從而得到距離r的分布。

圖9 與點(diǎn)v距離為r的點(diǎn)

假設(shè)在通信距離內(nèi)的節(jié)點(diǎn)之間都可以互相通信，則區(qū)域內(nèi)2個(gè)點(diǎn)能互相通信的概率p(r≤r')=p(r≤L) = 0.65。從而由式(1)得，當(dāng)區(qū)域內(nèi)落入5個(gè)節(jié)點(diǎn)時(shí)，區(qū)域內(nèi)不連通的概率已經(jīng)小于9.3%；落入6個(gè)節(jié)點(diǎn)時(shí)，不連通概率小于3.6%。

圖10 六邊形區(qū)域內(nèi)任意2個(gè)點(diǎn)距離的概率分布

8 實(shí)驗(yàn)結(jié)果

目前在真實(shí)環(huán)境中可用的平面化方法只有交叉鏈路檢測(cè)算法（CLDP），但是 CLDP需要檢測(cè)和刪除某些相交鏈路，增加了路由維護(hù)的復(fù)雜性。本文提出的方法將網(wǎng)絡(luò)劃分為規(guī)則多邊形區(qū)域，在貪心路由失敗時(shí)將多邊形區(qū)域內(nèi)的所有節(jié)點(diǎn)看成一個(gè)虛擬節(jié)點(diǎn)進(jìn)行周邊路由，它不需要檢測(cè)和刪除相交鏈路，能夠顯著減少路由維護(hù)開(kāi)銷(xiāo)，提高路由的可靠性。

本文實(shí)驗(yàn)使用TOSSIM模擬器結(jié)合C++編程語(yǔ)言實(shí)現(xiàn)。網(wǎng)絡(luò)拓?fù)涫褂肅++隨機(jī)生成。在給定1 000×1 000大小的區(qū)域中隨機(jī)生成不同節(jié)點(diǎn)數(shù)和不同通信距離的網(wǎng)絡(luò)拓?fù)洹１疚姆謩e模擬了200、400、600、800和1 000個(gè)節(jié)點(diǎn)時(shí)不同通信距離的路由維護(hù)開(kāi)銷(xiāo)以及平均路由路徑長(zhǎng)度。

以下實(shí)驗(yàn)結(jié)果中，x軸(n,r)表示1 000×1 000的網(wǎng)絡(luò)區(qū)域內(nèi)隨機(jī)布置n個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)間的通信距離為r。如(200, 88)表示整個(gè)網(wǎng)絡(luò)區(qū)域內(nèi)隨機(jī)布置 200個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)間的通信距離為 88。圖11中，不同節(jié)點(diǎn)、不同通信距離的實(shí)驗(yàn)數(shù)據(jù)表明，CLDP的路由維護(hù)開(kāi)銷(xiāo)明顯大于RPR。CLDP的路由維護(hù)開(kāi)銷(xiāo)包括探測(cè)交叉鏈路數(shù)據(jù)分組和刪除交叉鏈路數(shù)據(jù)分組2種，而RPR的路由維護(hù)開(kāi)銷(xiāo)只包括區(qū)域內(nèi)建樹(shù)數(shù)據(jù)分組。即使多邊形區(qū)域內(nèi)所有節(jié)點(diǎn)互相交換信息，RPR平均維護(hù)開(kāi)銷(xiāo)也只是多邊形區(qū)域內(nèi)節(jié)點(diǎn)個(gè)數(shù)的常數(shù)倍。多邊形區(qū)域內(nèi)的節(jié)點(diǎn)個(gè)數(shù)越多，路由維護(hù)開(kāi)銷(xiāo)增大；反之維護(hù)開(kāi)銷(xiāo)減小。只要多邊形區(qū)域內(nèi)節(jié)點(diǎn)個(gè)數(shù)不多，RPR的路由維護(hù)開(kāi)銷(xiāo)將保持在很低范圍內(nèi)。

圖11 CLDP和RPR算法的維護(hù)開(kāi)銷(xiāo)比較

CLDP和 RPR路由算法的平均路由長(zhǎng)度如圖12所示。RPR路由算法中的區(qū)域貪心和區(qū)域周邊模式都是以一個(gè)小區(qū)域?yàn)閱挝贿M(jìn)行路由，因此數(shù)據(jù)分組在小區(qū)域內(nèi)路由時(shí)可以選擇優(yōu)化的局部路由路徑，從而減少路由路徑長(zhǎng)度。本文實(shí)驗(yàn)中，RPR路由算法的平均路由路徑長(zhǎng)度較 CLDP優(yōu)勢(shì)不是很明顯，其原因是，RPR的區(qū)域劃分邊長(zhǎng)選擇較小。區(qū)域劃分邊長(zhǎng)較小，則每個(gè)小區(qū)域內(nèi)的節(jié)點(diǎn)個(gè)數(shù)少，從而可優(yōu)化的路徑選擇也少。如果區(qū)域劃分邊長(zhǎng)增大，區(qū)域內(nèi)節(jié)點(diǎn)個(gè)數(shù)增多，從而導(dǎo)致區(qū)域內(nèi)不連通概率增大，以及區(qū)域內(nèi)路由維護(hù)開(kāi)銷(xiāo)提高，這是RPR路由算法所不希望的。但是區(qū)域內(nèi)節(jié)點(diǎn)個(gè)數(shù)增多，會(huì)為區(qū)域間通信提供更多的優(yōu)化路徑，從而有效地減少路由路徑長(zhǎng)度。在網(wǎng)絡(luò)密度足夠高時(shí)，適應(yīng)增長(zhǎng)多邊形區(qū)域邊長(zhǎng)，能夠顯著減少路由路徑長(zhǎng)度。

圖12 CLDP和RPR的平均路由長(zhǎng)度比較

以通信距離為半徑的圓內(nèi)布置的節(jié)點(diǎn)越多，其路由的平均長(zhǎng)度越小，這是由于通信距離的增大使得貪心路由的比例增大。例如圖12中，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為600，通信距離分別為55、62和70時(shí)，平均路由路徑長(zhǎng)度逐步降低。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度足夠高時(shí)，貪心路由占主要部分，路由長(zhǎng)度顯著降低；相反，如果網(wǎng)絡(luò)節(jié)點(diǎn)稀疏，周邊路由比例增加導(dǎo)致路由長(zhǎng)度增長(zhǎng)。

路由成功率和網(wǎng)絡(luò)中節(jié)點(diǎn)密度以及節(jié)點(diǎn)的通信距離都有關(guān)系，如圖 13所示。通常情況下，以通信距離為半徑的圓內(nèi)布置的節(jié)點(diǎn)越多，其路由的成功率越高。圖13中，以400個(gè)節(jié)點(diǎn)為例，當(dāng)通信半徑分別為65、70和80時(shí)，路由的成功率明顯提高；RPR算法的路由成功率比CLDP路由成功率高，其原因是RPR算法中多邊形區(qū)域內(nèi)節(jié)點(diǎn)知道幾跳內(nèi)鄰居節(jié)點(diǎn)信息，從而提高區(qū)域貪心路由和區(qū)域周邊路由成功率。

圖13 CLDP和RPR的路由成功率比較

9 結(jié)束語(yǔ)

目前的地理路由算法都共同面臨網(wǎng)絡(luò)平面化問(wèn)題。現(xiàn)有的平面化算法大多都假設(shè)節(jié)點(diǎn)的通信半徑固定，然而這種假設(shè)在真實(shí)的網(wǎng)絡(luò)環(huán)境下不合理。CLDP算法需要檢測(cè)和刪除某些相交鏈路，增加了路由維護(hù)成本。本文提出的基于區(qū)域劃分的平面化方法，將網(wǎng)絡(luò)劃分為規(guī)則多邊形區(qū)域，它不需要檢測(cè)和刪除相交鏈路，從而降低路由維護(hù)開(kāi)銷(xiāo)。而且，在區(qū)域貪心和區(qū)域周邊2種模式中，算法以小區(qū)域作為路由的基本單元，能夠減短路由平均路徑長(zhǎng)度，提高路由的可靠性。

[1] 李建中, 李金寶, 石勝飛. 傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問(wèn)題與進(jìn)展[J]. 軟件學(xué)報(bào), 2003, 14 (10): 1717-1727.LI J Z, LI J B, SHI S F. Concepts, issues and advance of sensor networks and data management of sensor networks[J]. Journal of Software, 2003, 14 (10): 1717-1727.

[2] 孫利民, 李建中, 陳渝等. 無(wú)線傳感器網(wǎng)絡(luò)[M]. 北京: 清華大學(xué)出版社, 2005.SUN L M, LI J Z, CHEN Y,et al. Wireless Sensor Networks[M]. Beijing: Tsinghua University, Press, 2005.

[3] KARP B, KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[A]. Mobicom'00[C]. Boston, Massachusetts, USA, 2000.

[4] FREY H, STOJMENOVIC I. On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks[A]. MobiCom’06[C].Los Angeles, CA, USA, 2006. 390-401.

[5] KIM Y J, GOVINDAN R, KARP B. Geographic routing made practical[A]. Proc of USENIX Symposium on Network Systems Design and Implementation[C]. Boston, Massachusetts, USA, 2005.

[6] BOSE P, MORIN P, STOJMENOVIC I. Routing with guaranteed delivery in ad hoc wireless networks[A]. 3rd Int Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications[C]. Seattle, USA, 1999. 48-55.

[7] KRANAKIS E, SINGH H, URRUTIA J. Compass routing on geometric networks[A]. Proc of the 11th Canadian Conference on Computational Geometry (CCCG’99)[C]. Vancouver, Canada, 1999. 51-54

[8] KUHN F, WATTENHOFER R, ZHANG Y. Geometric ad-hoc routing:Of theory and practice[A]. Proc of the 22nd ACM Int. Symposium on the Principles of Distributed Computing (PODC)[C]. Boston, Massachusetts, USA, 2003.

[9] KUHN F, WATTENHOFER R, ZOLLINGER A. Worst-case optimal and average-case efficient geometric ad-hoc routing[A]. Proc of the 4th ACM International Symposium on Mobile Computing and Networking (MobiHoc 2003)[C]. Annapolis, Maryland, USA, 2003.

[10] LEONG B, MITRA S, LISKOV B. Path vector face routing: geographic routing with local face information[A]. Proc of the 13th IEEE International Conference on Network Protocols (ICNP'05)[C]. Boston,Massachusetts, USA, 2005. 147-158.

[11] GABRIEL K R, SOKAL R R. A new statistical approach to geographic variation analysis[J]. Systematic Zoology, 1969,18: 259-278.

[12] TOUSSAINT G. The relative neighborhood graph of a finite planar set[J]. Pattern Recognition, 1980 , 12(4): 261-268.

[13] LI X Y, CALINESCU G, WAN P J. Distributed construction of a planar spanner and routing for ad hoc wireless networks[A]. Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM’02)[C]. New York, USA, 2002.1268-1277.

[14] KIM Y J, GOVINDAN R, KARP B. Lazy cross-link removal for geographic routing[A]. Proc of the 4th International conference on Embedded Networked Sensor Systems[C]. Boulder, Colorado, USA,2006. 112-124.

[15] TIAN H, SHEN H, MATSUZAWA T. Developing energy-efficient topologies and routing for wireless sensor networks[A]. Proc of International Conference on Network and Parallel Computing[C]. Beijing,China, 2005.

[16] GILBERT E N. Random graphs[J]. Ann Math Statist, 1959, 30(4):1141-1144.