無線傳感器網(wǎng)絡中一種躲避障礙物的地理路由算法

李金寶,郭曉行,張守娟

(1.黑龍江大學 a.計算機科學技術學院;b.物理科學與技術學院,哈爾濱 150080;2.黑龍江省數(shù)據(jù)庫與并行計算重點實驗室,哈爾濱 150080)

0 引 言

地理路由因其簡單易用而被廣泛地應用在無線傳感器網(wǎng)絡中。地理路由中每個節(jié)點需要確定其位置坐標,該坐標分為真實坐標和虛擬坐標兩類。真實坐標一般需要通過定位設備(如GPS)來確定,而定位設備存在著價格昂貴、不能在室內操作以及容易出現(xiàn)測量錯誤等缺點。然而,采用基于跳數(shù)建立虛擬坐標的方法不需要額外的硬件支持,而且能夠較好地反映節(jié)點間的相對位置以及相通性。

在真實的傳感器網(wǎng)絡中,常常會存在形狀不規(guī)則的障礙物,這使得數(shù)據(jù)包轉發(fā)到障礙物附近時容易產生 “死端”節(jié)點。當出現(xiàn) “死端”節(jié)點時,無論是基于真實坐標還是虛擬坐標的地理路由,通常只能通過局部洪泛或FACE[1]算法來解決死端節(jié)點問題,但上述方法耗費能量較多,而且會增加路徑長度及丟包率。因此,文獻 [2]、文獻 [3]提出了基于虛擬坐標的地理路由算法,這些算法能夠有效地躲避障礙物,避免遇到障礙物附近的 “死端”節(jié)點,但增加了路徑長度。為了在不增加路徑長度的同時解決 “死端”節(jié)點問題,可以沿著障礙物的凸點建立路徑。根據(jù)計算幾何學[4],該路徑是最短路徑。

針對存在障礙物的網(wǎng)絡,本文提出了一種躲避障礙物的分布式地理路由算法 (A Geographic Routing for avoiding obstacles,GRdo)。在使用該算法前的網(wǎng)絡初始階段,本文首先提出一種建立虛擬坐標的方法,并引入可見圖 (簡稱CS圖),該圖輔助路由階段以最短的路徑繞開障礙物。在以上準備工作的基礎上,GRdo采用沿著障礙物凸點建立路徑的策略,不僅可以避免障礙物附近的 “死端”節(jié)點問題,而且可以得到較短的路徑。理論分析與實驗結果表明:本文提出的路由算法以較短的路徑繞開障礙物,有效地完成路由選擇過程,降低數(shù)據(jù)丟包率。

1 相關工作

在對傳感器網(wǎng)絡地理路由協(xié)議的研究中,一些研究人員提出了支持地理路由協(xié)議的虛擬坐標建立方法。文獻 [5]選擇3個邊界節(jié)點作為信標節(jié)點,每個節(jié)點根據(jù)到信標節(jié)點的跳數(shù)建立虛擬坐標,該方法所確定的坐標并不唯一,這可能導致路由的失敗;文獻 [6]選擇更多的節(jié)點作為信標,這提高了算法的正確性,但是卻增加了空間開銷;文獻[7]提出了一種建立唯一坐標的方法,從而保證了傳輸?shù)目煽啃?。在上述路由協(xié)議中,都沒有考慮障礙物問題。

針對存在障礙物的網(wǎng)絡,文獻 [8]將網(wǎng)絡劃分成多個子區(qū)域,源節(jié)點將數(shù)據(jù)包從當前子區(qū)域發(fā)送到目的節(jié)點所在的子區(qū)域。由于子區(qū)域形狀不規(guī)則,在子區(qū)域內仍然存在障礙物,這將導致 “死端”節(jié)點的出現(xiàn)從而降低算法性能;文獻[2]將網(wǎng)絡劃分成多個凸形狀的子區(qū)域,由于子區(qū)域內無障礙物而避免了 “死端”節(jié)點的產生,但是劃分區(qū)域的算法比較復雜,需要大量的洪泛信息;文獻[3]針對形狀規(guī)則的障礙物,建立中軸圖(MAG)作為路由的向導,每個節(jié)點需要計算和存儲反映全局拓撲特征的MAG,但由于MAG信息量較大,增加了存儲空間的開銷;文獻 [2]、文獻 [3]提出的路由算法雖然可以有效地繞開障礙物,但是卻增加了平均路徑長度。

2 網(wǎng)絡初始化

本文基于以下假設:①網(wǎng)絡環(huán)境中存在著形狀復雜的障礙物,并且障礙物的面積較大;②不存在障礙物互相包圍的情況。

2.1 預備知識

網(wǎng)絡初始時有N個節(jié)點,每個節(jié)點p有一個唯一的ID,表示為ID(p);障礙物所形成的“空白區(qū)”稱做 “面”,每個面對應著一個唯一的標識號,記為FID;邊界節(jié)點是面邊界上的節(jié)點,內角＜(＞)180°的邊界節(jié)點稱為凸點(凹點)。應用文獻 [9]提出的算法,可以確定邊界節(jié)點,每個邊界節(jié)點記錄所在面的FID。應用文獻[2]中的算法可以確定面的凸點及凹點。對于任意節(jié)點p和q,若p到q的最短路徑不經(jīng)過任何凸點,那么q和p是可見的,p是q的一個可見點。如圖1,s對于凸點5是可見的,但s對于凸點q是不可見的,因為最短路徑是經(jīng)過凸點1的折線。

定義1:凸面。凸面是面對應的最小凸多邊形區(qū)域。如圖1,face2本身就是凸面,而face1對應的凸面是由凸點 {1,q,2,3,4,5}圍成的凸多邊形區(qū)域。構成凸面的凸點稱為頂點。

定義2:CS圖。整個網(wǎng)絡構建成一個CS圖= (V,E),其中V是頂點集合,E是可見頂點對間建立的最短路徑集合,即V={v|節(jié)點v是頂點},E={(v1,v2)|v1和v2是可見的}。如圖1,CS圖的頂點集合為 {1,q,2,3,4,5,6, 7,8},邊集合為{(1,q),(q,2),(2,3), (3,4),(4,5),(5,1),(5,6),(5,7),(6, 7),(7,8),(6,8),(4,7),(4,8)}。

2.2 CS圖的建立

2.2.1 確定CS圖的頂點集

定義3:關鍵鄰居。邊界節(jié)點p的兩個關鍵鄰居為節(jié)點p在順(和逆)時針方向沿著所在面的邊界遇到的第一個凹點或凸點。用CN(p)表示邊界節(jié)點p的關鍵鄰居集合,如圖1中,CN(p)= {1,q}。

為了構建CS圖,首先需要確定頂點集合V。對于每個凸點p,CN(p)={p1,p2},若p1和p2不同時為凹點,則節(jié)點p是一個頂點。如圖1,該方法確定的頂點集合為 {v1,v2,v3,v4,v5, v6,v7,v8},但此時忽略了頂點q,在2.2.2節(jié)建立CS圖的邊時將檢測出頂點q。

以上方法要求每個凸點知道其關鍵鄰居的信息。確定關鍵鄰居的具體過程如下:每一個凹點和凸點發(fā)起包含自身信息的消息包,收到該消息的鄰居節(jié)點q做以下處理:

1)若q為普通節(jié)點或者q的FID與發(fā)起者p的FID不同,那么q丟棄該消息包,不予處理;

2)若q的FID與p的FID相同,則繼續(xù)轉發(fā);

3)若q為凸點或凹點,則停止轉發(fā)該消息,q設置p為自己的關鍵鄰居,并記下p的信息。

2.2.2 確定CS圖的邊集

CS圖的邊集合E定義為頂點集合中所有可見的兩個頂點建立的最短路徑集合。在確定CS圖的頂點后,可見的兩頂點建立最短路徑即完成CS圖邊的建立。

判斷兩個頂點是否可見的方法如下:每個頂點建立到其他所有頂點的最短路徑,如頂點v1和v2建立了一條最短路徑,若該最短路徑經(jīng)過其他頂點,則說明v1和v2這兩個頂點不可見;否則可見,且該路徑則為CS圖的一條邊。CS圖邊上的點簡稱為邊點,每個邊點記錄到其鄰居頂點的跳數(shù)。如果存在凸點q在該最短路徑上,則q為在2.2.3部分忽略的頂點。

每個節(jié)點需要存儲CS圖,只需存儲CS圖的頂點集合及頂點間的距離即可。CS圖的大小與網(wǎng)絡規(guī)模無關,只與網(wǎng)絡中障礙物復雜度有關。

2.3 建立虛擬坐標

對于凸面上的節(jié)點,若其不是凸面邊(即可見邊)上的節(jié)點或頂點,則為凸面內部節(jié)點。我們觀察到,當前網(wǎng)絡中有以下4類節(jié)點:頂點、CS圖邊點、凸面內部節(jié)點以及網(wǎng)絡中的其他普通節(jié)點。

每個節(jié)點p建立虛擬坐標向量,該向量包括兩部分:VID坐標和距離坐標,分別記錄p的可見頂點的ID號和到可見頂點的距離。建立坐標的方法如下:

1)若節(jié)點 p不是凸面內部節(jié)點,則p建立VID坐標{ID(v1),ID(v2),…,ID(vk)},vk是p的可見頂點,k是p的可見頂點個數(shù);p建立距離坐標 (d1,d2,…,dk),dk是p到可見頂點vk的跳數(shù)距離;

2)若節(jié)點p是凸面內部節(jié)點,則p的坐標與距離p最近的邊點坐標相同,并記錄到邊點的距離為偏移距離。如圖 1,s的可見頂點集為 {v1, v5},假設s到v1的跳數(shù)為5,到v5的跳數(shù)為10,則s節(jié)點建立的 VID坐標為 (ID(v1),ID (v5)),距離坐標為(5,10)。

3 躲避障礙物的路由算法GRdo

為了以較短的路徑躲避障礙物,GRdo首先依據(jù)源和目的節(jié)點的VID坐標判斷兩節(jié)點是否存在共同的可見頂點,若不存在,則借助CS圖確定路徑,否則,根據(jù)距離坐標確定路徑。給定源節(jié)點s和目的節(jié)點t,s根據(jù)s和t的VID坐標判斷出它們共同的可見頂點集合為CV={v1,v2,…,vk}, GRdo根據(jù)CV=?或CV≠?兩種情況給出兩個相應的子算法。

3.1 GRdo的兩個子算法

3.1.1 GRdo_NCV算法

此算法針對源節(jié)點s和目的節(jié)點t無共同的可見頂點的情況,即CV=?。s根據(jù)可視圖在多條路徑中找出到t的最短路徑,并記錄該最短路徑經(jīng)過的可視圖頂點數(shù)據(jù)包沿著該最短路徑到達 t的可視頂點,然后遞歸調用VCBR策略確定到目的節(jié)點t的路徑。如圖1,s根據(jù)可視圖確定最短路徑為。

定理1:GRdo_NCV算法確定的路徑為最短路徑。

證明:首先證明該情況下的s和t互不可見。假設s和t不可視即線段st(用st表示)不與任何凸面相交,則一定存在距離st最近的頂點v,使得sv和tv都不與任何凸面相交,即v是s和t的共同可視頂點,這與s和t無共同可視頂點的條件相違背,所以s和t互不可視。由計算幾何學可知,此時s到t的最短路徑經(jīng)過凸面上的某些頂點,該最短路徑即為GRdo_NCV算法所確定的路徑。

3.1.2 GRdo_CV算法

此算法針對s和t有共同的可見頂點的情況,并根據(jù)共同頂點所在面的信息分以下3種情況:

1)不存在兩個共同可見頂點在一個面的情況,即CV≠?且任意兩頂點vi、vj∈CV滿足FID(vi)≠FID(vj)。s確定最短路徑為s→vi→t,其中vi∈SV且使得路徑最短。如圖1,v6的VID坐標為(ID(v5),ID(v6),ID(v7),ID(v8)),s與v6只有一個共同可見頂點v5,確定路徑為s→v5→v6。

2)存在兩個共同頂點在同一面的情況,即CV≠?,vi、vj∈CV且FID(vi)=FID(vj),此時顯然存在邊 (vi,vj)∈CS圖。源節(jié)點s采用如下算法判斷s和t在直線vivj的同側還是異側:設與s距離最近的可見頂點為vk且FID(vk)= FID(vi),若vk≠vi∧vk≠vj,或者t符合上述情況,說明s和t在直線vivj異側,否則s和t在直線vivj同側。

定理2:上述判斷算法總能正確地判斷出s和t在直線vivj的同側還是異側。

證明:如圖2,區(qū)域2和4內的所有節(jié)點的可見頂點集合中都包含vi和vj,在區(qū)域2內的節(jié)點,到該凸面的最近可見頂點一定為vi或vj,而區(qū)域4內的節(jié)點到該凸面的最近可見頂點一定不是vi和vj,如圖中是vk(忽略了使區(qū)域4內節(jié)點對于vk不可見的小凸面),因此該算法可以判斷出區(qū)域2和區(qū)域4內的節(jié)點在直線vivj的異側且互不可見。

1)GRdo_CV異側路由算法:若s和t在直線vivj異側,此時可以應用GRdo_CV的情況1)算法確定最短關鍵路徑為s→vi→t或s→vj→t。如圖2,s與t有共同的可見頂點vi和vj,s在該面最近的可見頂點為vi,t在該面最近的可見頂點為vk,則s判斷出其與t在直線vivj的異側,并確定最短路徑為

源節(jié)點s估算出d(s,t)后,采用貪心算法在鄰居節(jié)點集合中選擇d(s,t)最小的鄰居作為下一跳節(jié)點,n表示s的鄰居。若s采用貪心算法到達中間節(jié)點p,且p的鄰居節(jié)點的可見頂點集合中不包含或時,說明p與t不是可見的,p遞歸調用GRdo算法確定到t的路徑。如圖4,s判斷s、t有共同可見頂點且在直線的同側,應用余弦定理估算出d(s,t),采用貪心轉發(fā)算法,當?shù)竭_節(jié)點p時,p無法應用貪心算法找到下一跳,且p存在鄰居節(jié)點q,q對于不可見,則p遞歸調用GRdo算法判斷屬于GRdo_CV的情況1),采用GRdo_CV的情況1)算法確定路徑為最終s到t的路徑為

3)存在兩個以上的共同可見頂點在同一面上的情況。即存在頂點集合CV,其中根據(jù)距離坐標,從CV中選擇距離s最近的可見頂點和距離t最近的可見頂點vj,若則和作為被選擇的兩個共同可見頂點,此時s和t應用GRdo_CV同側路由算法;否則任意選擇vi的鄰居頂點vk,應用GRdo_CV同側路由算法。

3.2 GRdo算法描述及理論分析

基于以上兩種子算法,GRdo的算法如下所示。

算法1 躲避障礙物的路由算法GRdo當前節(jié)點為u(包括源節(jié)點s),目的節(jié)點t 1:If(u、t的坐標相同)如果u、t的ID也相同,則GRdo算法成功找到目的節(jié)點t;否則說明 t是凸面內部節(jié)點,采用貪心算法根據(jù)偏移距離到達目的t。3:Else(判斷由u、t的共同可見頂點情況) 4:If(u、t無共同可見頂點) 2:根據(jù)G Rdo_NCV路由算法,確定最短路徑經(jīng)過的可視圖頂點為vi→vk→…→vl,→vj,此時應用貪心算法轉發(fā)數(shù)據(jù)包到達vj,u=vj,goto行1。6:If(u、t在某面有一個共同可見頂點) 7: 根據(jù)G Rdo_CV情況1)路由算法,確定最近的可見頂點v,貪心地將數(shù)據(jù)包轉發(fā)到頂點v,u=v,goto行1。8:If(u、t在某面有兩個共同可見頂點vi和vj) 9:If(u、t在直線vivj異側) 10:goto行7; 11:else 5: 12:應用G Rdo_CV同側路由算法,貪心地選|sp(n,t)|最小的鄰居節(jié)點 n,直到成功轉發(fā)給 t,若遇到點p,且p的鄰居節(jié)點的可見頂點集合中不包含vi或vj,u=p,goto行1。13: If(u、t在某面有兩個以上共同可見頂點)根據(jù)GRdo_ CV情況3)下的選擇算法選擇出兩個共同可見頂點vi和vj,g oto行9

綜上所述,給定源節(jié)點及目的節(jié)點的坐標,源節(jié)點首先通過VID坐標判斷共同可見頂點的情況,然后根據(jù)距離坐標或CS圖采用相應的算法到達目的節(jié)點。若目的節(jié)點是凸面內部節(jié)點,到達坐標相同的邊節(jié)點后,貪心地選擇偏移距離遞增的節(jié)點作為下一跳,最終達到目的節(jié)點。下面證明GRdo算法總能找到路徑。

定理3:在網(wǎng)絡空間連續(xù)的條件下,GRdo算法總是能夠找出s到t的路徑。

證明:根據(jù)GRdo算法的描述,GRdo首先判斷源與目的節(jié)點間是否存在障礙物,若存在,則總是成功地將數(shù)據(jù)包轉發(fā)到某個中間頂點,此時只需某頂點v總是能夠找出到達t的路徑。下面證明v與t至少有一個共同可視頂點v1,v1≠v,即可應用GRdo策略。因為v是t的可視點,即vt不與任何凸面相交,設v1是距離vt最近的頂點,則線段vv1和tv1都不與任何凸面相交,即v1是v與t的共同可視頂點,且由于網(wǎng)絡中每個節(jié)點至少有兩個可視頂點,所以必存在頂點v1,得證。

綜上所述,GRdo在連續(xù)空間內總能保證找到路徑。對于離散空間,由于GRdo_CV情況1)路由算法是以歐氏距離來度量路徑長度,因而不能保證絕對避免死端節(jié)點,但網(wǎng)絡節(jié)點密度較大時,節(jié)點間跳數(shù)距離近似于歐氏距離[8],保證了GRdo算法的有效性。由上述分析可知,GRdo_NCV, GRdo_CV情況2)和情況3)路由算法總能正確地判斷出源與目的節(jié)點是否可見,并根據(jù)距離坐標或CS圖確定最短路徑,雖然GRdo_CV情況1)不能總是保證其確定的路徑最短,但實驗表明, GRdo總體確定的路徑近似最短。

4 實驗與結果分析

本節(jié)對GRdo和其它路由算法進行模擬對比實驗以驗證GRdo的實際性能。模擬環(huán)境設置如下: 7 989個傳感器節(jié)點均勻隨機地分布在一個存在障礙物的網(wǎng)格網(wǎng)絡內,其面積為100 m×100 m。如圖5所示,白色區(qū)域表示障礙物,黑點表示傳感器節(jié)點。不失一般性,設每個節(jié)點隨機分布在1 m× 1 m的網(wǎng)格內。通信半徑設置為2 m;網(wǎng)絡平均密度為8.66。本節(jié)將GRdo與以下兩個基于虛擬坐標的路由算法進行比較:

1)VCAP路由算法:VCAP是一種基于3個信標節(jié)點的路由算法;

2)GLIDER算法:GLIDER考慮了網(wǎng)絡中形狀規(guī)則的障礙物問題,試驗中共選擇13個節(jié)點作為信標節(jié)點,其中8個位于網(wǎng)絡邊界,剩余5個位于障礙物邊界。

本節(jié)共選取600組源與目的節(jié)點對進行實驗,其中100組為隨機選取的可見節(jié)點對;200組為隨機選取的不可見節(jié)點對;剩余300組為隨機的節(jié)點對。并通過貪心轉發(fā)成功率和平均路徑長度近似比兩個參數(shù)來比較GRdo,VCAP和GLIDER的性能。

圖5 網(wǎng)絡拓撲圖Fig.5 Network topology graph

定義4:貪心轉發(fā)成功率(GFSR)。若一個數(shù)據(jù)包能夠利用貪心轉發(fā)算法到達目的節(jié)點,稱該包貪心轉發(fā)成功,即該類數(shù)據(jù)包不包含通過局部洪泛到達目的節(jié)點的數(shù)據(jù)包。貪心轉發(fā)成功的數(shù)據(jù)包與總數(shù)據(jù)包數(shù)的比值稱為貪心轉發(fā)成功率。

定義5:平均路徑長度近似比(APLS)。貪心轉發(fā)成功的數(shù)據(jù)包所經(jīng)過的路徑長度與應用最短路徑算法所確定的路徑長度的比值稱為平均路徑長度近似比。

A.貪心轉發(fā)成功率(GFSR)

GFSR的實驗結果見圖6。對于100組可見節(jié)點對,VCAP的GFSR為63%;對于200組不可見節(jié)點對,VCAP的GFSR為31%;而對于300組隨機節(jié)點對,VCAP的GFSR僅為42%。這主要是由于VCAP算法僅利用3個節(jié)點作為信標節(jié)點,因此該機制確定的虛擬坐標不能夠較好地反映出節(jié)點間的相對位置。所以,在存在障礙物的網(wǎng)絡中,VCAP算法由于障礙物的干擾產生大量的“死端”節(jié)點,而這些 “死端”節(jié)點降低了該算法的GFSR。與VCAP相比,GLIDER算法的性能較好,該算法的平均GFSR可以達到75%。這是因為GLIDER算法隨機選擇多個障礙物附近的節(jié)點及障礙物的邊界點作為信標節(jié)點,從而以這些信標節(jié)點為基準劃分的子區(qū)域的復雜度與整個網(wǎng)絡的復雜度相比有所降低,見圖7。但是由于GLIDER算法隨機地選取信標節(jié)點,不能保證較為規(guī)則的子區(qū)域劃分。所以在GLIDER算法中,障礙物附近仍然容易產生 “死端”節(jié)點,這就降低了其GFSR。而本文針對障礙物的干擾提出的GRdo路由算法,對于3類節(jié)點對,其平均GFSR都可達到90%以上,相對于其它兩種算法性能有較大提高。這表明GRdo在較大程度上解決了VCAP算法和GLIDER算法中 “死端”節(jié)點較多的問題,提高了轉發(fā)成功率,減少了局部洪泛次數(shù),從而節(jié)省了由洪泛產生的能量消耗。

B.平均路徑長度近似比(APLS)

APLS的實驗結果見圖 8,其縱軸的參數(shù)APLS反映了該算法確定的路徑長度。APLS越接近于1,表示該算法確定的路徑越接近于最短路徑。從圖中可以看出,VCAP和GRdo算法的APLS值＜1.05,其路徑長度與最短路徑長度相差較小。而GLIDER的平均APLS為1.129,這是由于GLIDER為了避免數(shù)據(jù)包轉發(fā)到障礙物附近的“死端”節(jié)點,采取 “繞道”的策略來躲避障礙物,該策略雖然有效地提高了GFSR,卻增加了路徑長度。

圖8 平均路徑長度近似比Fig.8 Simulation results of APLS

5 結論與未來工作

針對WSN中障礙物的存在問題,本文提出了一種分布式的路由算法GRdo。GRdo由節(jié)點的虛擬坐標估算出最短路徑,針對不同情況根據(jù)距離坐標或CS圖確定路徑。理論分析和實驗結果表明:在存在障礙物的網(wǎng)絡中,本文提出的路由算法能夠有效地降低丟包率,并得到較短的路由路徑。未來工作包括設計一種考慮鏈路質量或時延等多方面因素的路由算法。

[1] Yujun Li,Yaling Yang,and Xianliang Lu.Routing Metric Designs for Greedy Face and Combined-Greedy-Face Routing[C]//INFOCOM'09,April,Rio de Janeiro,Brazil,2009:64-72.

[2]G.Tan,M..Bertier,and A.M.Kermarrec.Convex Partition of Sensor Networks and Its Use in Virtual Coordinate GeographicRouting[C]//.INFOCOM' 09,April,Rio de Janeiro,Brazil,2009:1 746-1 754.

[3]J.Bruck,J.Gao,and A.Jiang,MAP:Medial Axis based Geometric Routing in Sensor Networks[C]// MOBICOM'05,August,Cologne,Germany,2005: 88-102.

[4]H.Alt and E.Welzl.Visibility Graphs and Obstacleavoiding Shortest Paths[J].Zor-Zeitschrift fur Operation Research,1988,32:145-164.

[5]A.Caruso,A.Urpi,S.Chessa,and S.De.GPS Free Coordinate Assignment and Routing in Wireless Sensor Networks[C]//INFOCOM' 05,March,Miami, 2005:150-160.

[6]R.Fonseca,S.Ratnasamy,J.Zhao,et al.Beacon VectorRouting:Scalable Point-to-point Routingin Wireless Sensornets[C]//NSDI'05,May,Boston, 2005:329-342.

[7]Y.Liu,L.M.Ni,and M.Li.A Geography-free Routing Protocol for Wireless Sensor Networks[C]// HPSR'05,Hongkong,May,2005:351-355.

[8]Q.Fang,J.Gao,L.Guibas,et al.GLIDER:Gradient Landmark-based Distributed Routing for Sensornetworks[C]//INFOCOM'05,March,Miami,2005: 339-350.

[9]Y.Wang,J.Gao,J.S.B.Mitchell.Boundary Recognition in Sensor Networks byTopological Methods [C]//MobiCom'06,September,Los Angeles,CA, USA,2006:122-133.