李志剛，陳衛(wèi)衛(wèi)，肖儂，夏戈明

(1. 解放軍理工大學(xué) 指揮自動化學(xué)院，江蘇 南京 210007；2. 國防科學(xué)技術(shù)大學(xué) 計算機學(xué)院，湖南 長沙 410073)

1 引言

傳感器網(wǎng)絡(luò)路由協(xié)議負責(zé)將數(shù)據(jù)從某個源節(jié)點通過網(wǎng)絡(luò)多跳轉(zhuǎn)發(fā)到目的節(jié)點，主要包括2方面的功能：尋找源節(jié)點和目的節(jié)點間的優(yōu)化路徑，將數(shù)據(jù)分組沿著優(yōu)化路徑正確轉(zhuǎn)發(fā)[1,2]。傳感器節(jié)點的能量、處理器、存儲容量和帶寬等性能上的局限性，使得傳感器網(wǎng)絡(luò)的路由協(xié)議設(shè)計和傳統(tǒng)的網(wǎng)絡(luò)具有很大的區(qū)別。比如說，在因特網(wǎng)的路由器上可以存儲路由表，通過查詢路由表來決定節(jié)點之間的路由和數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳節(jié)點應(yīng)該如何選擇。因為傳感器節(jié)點的存儲能力和資源不足，傳感器節(jié)點不能保存大量的與路由相關(guān)的信息，所以通常采用“無狀態(tài)”路由方式[3,4]。

貪婪路由就屬于一種常見的“無狀態(tài)”路由。在貪婪路由中，通常存在一個貪婪函數(shù)，該貪婪函數(shù)滿足一定的單調(diào)性，節(jié)點可以將鄰居的某些信息作為貪婪函數(shù)的參數(shù)，得到一個函數(shù)值。比較所有鄰居節(jié)點的貪婪函數(shù)值大小，節(jié)點可以決定如何選擇下一跳節(jié)點。其中基于地理坐標(biāo)信息的貪婪路由是經(jīng)常使用的路由算法。在地理貪婪路由中，貪婪函數(shù)為節(jié)點到目的節(jié)點的歐式距離，當(dāng)前節(jié)點總是選擇距離目的節(jié)點最近的鄰居節(jié)點作為下一跳節(jié)點傳輸數(shù)據(jù)。地理貪婪路由的最大挑戰(zhàn)是局部極小值問題，即當(dāng)前節(jié)點找不到距離目的節(jié)點更近的鄰居節(jié)點，即使當(dāng)前節(jié)點到目的節(jié)點確實存在一條連通的路徑，在這種情況下仍然不能保證路由的可達性。局部極小值問題是因為網(wǎng)絡(luò)節(jié)點分布的不規(guī)則和“洞”的原因造成的[5]。為了解決該問題，研究者提出了2種方式。這2種方式可以劃分為：弱貪婪路由和強貪婪路由。

弱貪婪路由方式仍然基于地理位置信息，試圖“修補”貪婪路由規(guī)則?；谄矫婊拿媛酚刹呗詫儆谠摲绞?。在面路由中，如果當(dāng)前節(jié)點不能找到一個距離更接近目標(biāo)節(jié)點的下一跳節(jié)點的話，則放棄使用貪婪路由策略，然后按照一定的規(guī)則通過面路由繞過當(dāng)前的“洞”，再重新使用貪婪路由策略。文獻[4]提出如何通過平面化，以及使用左手規(guī)則(或者右手規(guī)則)來具體實現(xiàn)面路由。文獻[6]總結(jié)了幾種不同的面路由的原理和性能。不過在傳感器網(wǎng)絡(luò)中對節(jié)點進行定位是一件具有挑戰(zhàn)性的工作，現(xiàn)有的定位算法計算開銷和通信開銷都比較大，不適合資源有限的傳感器節(jié)點[7]。

強貪婪路由方式是通過找到網(wǎng)絡(luò)的貪婪嵌入圖[8]，滿足全網(wǎng)范圍內(nèi)的貪婪屬性。貪婪嵌入的定義為，在空間(X, d)上為無向圖G定義一個映射f：V(G)→X，滿足V(G)中任意2個不同的節(jié)點s，t，存在節(jié)點s的相鄰節(jié)點u，滿足d(f(u), f(t))＜ d(f(s),f(t))。非常遺憾的是，不是所有的有限無向圖都存在一個到歐式空間的嵌入。即使某些有限圖理論上存在貪婪嵌入，對于現(xiàn)實網(wǎng)絡(luò)如何通過分布式算法獲得該嵌入也是非常具有挑戰(zhàn)性的問題。對傳感器網(wǎng)絡(luò)來說，為了得到貪婪嵌入將耗費巨大的能量。

本文的目標(biāo)是設(shè)計一種新的弱貪婪路由協(xié)議。該路由協(xié)議要滿足不需要地理位置信息或者貪婪嵌入的支持。本文的思路是首先在網(wǎng)絡(luò)中構(gòu)建基于樹的網(wǎng)絡(luò)嵌入圖。在基于樹的網(wǎng)絡(luò)嵌入圖中，給每個節(jié)點分配一個區(qū)間標(biāo)記：[i, r]。利用節(jié)點的標(biāo)記信息，設(shè)計了一種新的弱貪婪路由算法TGR。該路由算法的基本思想主要基于2種路由規(guī)則，貪婪規(guī)則和缺省規(guī)則。如果當(dāng)前節(jié)點通過貪婪規(guī)則找不到滿足條件的下一跳節(jié)點，則采用缺省規(guī)則尋找下一跳節(jié)點。缺省規(guī)則可以保證當(dāng)前節(jié)點一定能發(fā)現(xiàn)下一跳節(jié)點。TGR算法能夠保證無環(huán)路由，即滿足任意一個節(jié)點都不可能在一條路徑上出現(xiàn)2次或2次以上。TGR算法的另一個優(yōu)點是源節(jié)點并不需要掌握目的節(jié)點的全部標(biāo)記信息。通過大規(guī)模的模擬測試，TGR算法在路徑長度和負載平衡方面能達到良好的性能。本文第5節(jié)還討論了基于雙樹的網(wǎng)絡(luò)嵌入圖思想，在條件允許的情況下進一步提高路由算法在路徑伸展因子上的性能。

2 預(yù)備知識

本文將無線傳感器網(wǎng)絡(luò)看作連通的有限無向圖，下面介紹一下與本文工作相關(guān)的圖論當(dāng)中的圖標(biāo)記和圖嵌入技術(shù)。

2.1 圖標(biāo)記機制

圖標(biāo)記機制是為圖上的節(jié)點(或者邊)按照一定的條件和規(guī)則分配一個標(biāo)記的技術(shù)，被標(biāo)記的圖稱為標(biāo)記圖。自 1960年以來，關(guān)于圖標(biāo)記機制已經(jīng)有很多研究工作[9]。根據(jù)不同的目的有很多不同的種類，比如區(qū)間路由標(biāo)記、距離標(biāo)記、完美標(biāo)記、和諧標(biāo)記等。下面介紹一下與本文相關(guān)的區(qū)間路由標(biāo)記和距離標(biāo)記。

2.1.1 區(qū)間路由標(biāo)記

區(qū)間路由又稱作緊致路由機制，起源于并行和分布處理系統(tǒng)中處理器之間相互通信的研究[10]。 隨著技術(shù)的進步，多處理器系統(tǒng)的規(guī)模約來越大， 但是每個處理器的存儲開銷是有限的，因此處理器與處理器之間的相互通信同樣不能依賴于類似路由器存儲表的機制。區(qū)間路由技術(shù)就是為解決這一問題提出的。其基本的思想是為處理器的每個端口標(biāo)記一個區(qū)間，通過查看和比較端口的區(qū)間，當(dāng)前節(jié)點可以決定將數(shù)據(jù)報文發(fā)送到哪個端口，從而實現(xiàn)處理器節(jié)點與節(jié)點之間的通信。圖1所示為一個簡單的區(qū)間路由標(biāo)記圖，如果節(jié)點2需要給節(jié)點4發(fā)送數(shù)據(jù)，則將數(shù)據(jù)首先發(fā)送至[3,5]標(biāo)記的端口即可。

圖1 區(qū)間路由標(biāo)記[10]

2.1.2 距離標(biāo)記

距離標(biāo)記機制首次在文獻[11]中提出，其目的是希望能夠根據(jù)節(jié)點的標(biāo)記來計算節(jié)點之間的距離。 距離標(biāo)記的定義如下：給定一無向圖G，d(u,v)表示圖G中2點u和v之間的跳步距離。為每一個節(jié)點u賦值一個非負數(shù)的整數(shù)標(biāo)記L(u)。距離解碼函數(shù)f負責(zé)計算2標(biāo)記之間的距離，即給定2個標(biāo)記L(u)，L(v)，函數(shù)f返回f(L(u),L(v))。如果對圖中的所有的節(jié)點滿足 f(L(u),L(v))=d(u,v)，稱(L,f)為距離標(biāo)記，或者距離標(biāo)記機制。

2.2 圖嵌入技術(shù)

圖嵌入是將Guest圖G映射到Host圖H上的技術(shù)。在文獻[12]中定義圖G的嵌入包括2個映射：1) 節(jié)點分配函數(shù)α將圖G的節(jié)點一對一的映射到H的節(jié)點上；2)邊路由函數(shù)ρ為圖 G 的每條邊(u,v)分配一條H中的路徑連接α(u)和α(v)。

文獻[13]利用雙曲幾何的理論將樹狀網(wǎng)絡(luò)嵌入到雙曲平面上，并且證明每個網(wǎng)絡(luò)都可以通過構(gòu)建生成樹，再得到該生成樹的雙曲空間貪婪嵌入，從而找到原始網(wǎng)絡(luò)的一種貪婪嵌入。該方案的問題是網(wǎng)絡(luò)只依賴于生成樹子圖上的貪婪路由，浪費了有其他不在生成樹上的鏈接，造成網(wǎng)絡(luò)負載不均衡。

最近有關(guān)瑞奇流(racci flow)[14]應(yīng)用在無線傳感器網(wǎng)絡(luò)中的工作是這方面研究的最新成果。 利用瑞奇流和雙曲幾何，可以通過分布式算法將網(wǎng)絡(luò)映射到一個只含有凸洞的圓盤區(qū)域內(nèi)，新的網(wǎng)絡(luò)嵌入?yún)^(qū)域滿足貪婪屬性。不過該方案需要基于節(jié)點原來的坐標(biāo)位置信息，而不是純粹基于連接信息。

3 基于樹的網(wǎng)絡(luò)嵌入圖

本節(jié)的核心思想是首先將網(wǎng)絡(luò)嵌入到一棵最短路徑樹上，然后在該最短路徑樹上進行節(jié)點標(biāo)記工作。不失一般性，本文對傳感器網(wǎng)絡(luò)作以下假設(shè)：1) 傳感器網(wǎng)絡(luò)是連通無向圖；2) 傳感器節(jié)點不需要知道自身和其他節(jié)點的位置信息；3) 傳感器網(wǎng)絡(luò)是靜態(tài)的網(wǎng)絡(luò)，或者在一段時間內(nèi)保持穩(wěn)定狀態(tài)。

3.1 基于樹的網(wǎng)絡(luò)嵌入圖構(gòu)建

基于樹的網(wǎng)絡(luò)嵌入圖(TNEG, tree-based network embedding graph)構(gòu)建包括2步。首先在網(wǎng)絡(luò)中構(gòu)建一棵樹并且統(tǒng)計所有節(jié)點的個數(shù)；然后從根節(jié)點開始按照自上而下的方式為每個節(jié)點分配一個標(biāo)記。

3.1.1 通過最短路徑樹統(tǒng)計節(jié)點總數(shù)

首先隨機選擇一個節(jié)點作為根節(jié)點。然后根節(jié)點向網(wǎng)絡(luò)中其他的節(jié)點廣播“HELLO”消息。其他的節(jié)點通過收到的消息計算到根節(jié)點的最短跳步數(shù)。在該過程中，每個節(jié)點選擇一個節(jié)點作為自己的父節(jié)點，所選節(jié)點的跳步數(shù)要小于當(dāng)前節(jié)點的跳步數(shù)。當(dāng)該過程結(jié)束以后，在網(wǎng)絡(luò)中便構(gòu)建了一棵最短路徑樹。此時除葉節(jié)點以外的每個中間節(jié)點可以看作一棵子樹的根節(jié)點。然后每個葉節(jié)點向其父節(jié)點發(fā)送一個“COUNTER=1”的消息，當(dāng)葉節(jié)點的父節(jié)點P收到所有孩子節(jié)點的“COUNTER=1”消息以后，則向自己的父節(jié)點發(fā)送一個“COUNTER=m”的消息，其中，m等于P的孩子節(jié)點的個數(shù)加 1。所有的中間節(jié)點都重復(fù)同樣的操作， 直到根節(jié)點收到“COUNTER=n-1”的消息。然后根節(jié)點可以計算出整個網(wǎng)絡(luò)的節(jié)點總數(shù)n。

在以上所有的過程中，每個節(jié)點最多只發(fā)送 2個消息，一個為“HELLO”消息，一個為“COUNTER=i”消息。每個節(jié)點可能會收到多條消息，這依賴于節(jié)點的度數(shù)。所以每個節(jié)點的收發(fā)開銷平均為2Es+dEr，整個網(wǎng)絡(luò)的能量開銷為

其中，d為網(wǎng)絡(luò)的平均度數(shù)，Ew代表整個網(wǎng)絡(luò)的能量開銷，Es為節(jié)點發(fā)送一個消息的能量開銷，Er為節(jié)點收到一個消息的能量開銷。

3.1.2 標(biāo)記分配

第一步完成以后在網(wǎng)絡(luò)中就生成了一棵最短路徑樹(SPT)，同時根節(jié)點也計算出網(wǎng)絡(luò)的節(jié)點總數(shù)，而且每個中間節(jié)點也都計算出以自己作為根節(jié)點的子樹的節(jié)點個數(shù)。接下來根節(jié)點就開始進行標(biāo)記分配的過程。一開始根節(jié)點R為自己分配區(qū)間[1, n]作為其標(biāo)記。查詢子節(jié)點，根節(jié)點可以獲得每個子節(jié)點作為根節(jié)點的子樹的節(jié)點總數(shù)。假設(shè)根節(jié)點有 k個子節(jié)點C1,C2,…,Ck。Ci.count表示以Ci為根節(jié)點的子樹的節(jié)點總數(shù)。根節(jié)點R保留區(qū)間[1,n] 的左邊界1，然后將區(qū)間[2,n]按照 C1.count, C2.count,…,Ck.count的比例劃分為k個子區(qū)間。舉例說明，可以按下面的方式進行分配，將[2,C1.count+1], [C1.count+2, C1.count+C2.count+1],…, [n-Ck.count+1,n]分別分配給子節(jié)點C1,C2,…,Ck。更一般的，對中間節(jié)點 N，如果其標(biāo)記為[i, r]，且有 l 個子節(jié)點 Ci1,Ci2,…,Cil，那么可以將[i+1,i+Ci1.count],[i+Ci1.count+1,i+Ci1.count+Ci2.count],…,[r-Cil.count+1,r]分別分配給子節(jié)點Ci1, Ci2,…, Cil，分配過程和根節(jié)點是一樣的。標(biāo)記分配過程的區(qū)間劃分方式可以有多種，本節(jié)暫時不考慮具體的分配方案，在下面第5節(jié)會討論一種基于雙樹的標(biāo)記分配方案。

圖2給出了TNEG網(wǎng)絡(luò)的一個具體的例子。在TNEG網(wǎng)絡(luò)中，每個節(jié)點都對應(yīng)一個[i,r]的標(biāo)記，稱i為節(jié)點的ID，r為節(jié)點的范圍。節(jié)點N的標(biāo)記[i,r]作為一個整數(shù)區(qū)間包含了所有以N為根節(jié)點的子樹節(jié)點的ID。

圖2 基于樹的網(wǎng)絡(luò)嵌入標(biāo)記

3.2 TNEG的屬性

3.2.1 標(biāo)記性質(zhì)

對每個節(jié)點來說，其標(biāo)記[i,r]滿足 i≤r。通過該性質(zhì)，可以將所有的節(jié)點分成3類。如果i=1，則該節(jié)點為根節(jié)點；如果i=r，則該節(jié)點為葉節(jié)點；如果i＜r且i＞1，該節(jié)點為中間節(jié)點。以節(jié)點N為根節(jié)點的子樹的節(jié)點個數(shù)為r-i+1。

3.2.2 標(biāo)記間的關(guān)系

假設(shè)有2個節(jié)點S：[iS, rS]和D：[iD, rD]。不失一般性，假設(shè)iS＜ iD。因為iD≤rD，所以iS＜rD。但是對節(jié)點D來說, rS有如下2種情況（如圖3所示）。

圖3 標(biāo)記之間的關(guān)系

1) rS≥rD: 這種情況下，D是以S為根節(jié)點的子樹中的一個節(jié)點。這種情況稱為S覆蓋了D。

2) rS＜iD: 在這種情況下，S和D分別為2棵獨立子樹的根，即這2棵子樹沒有共同的節(jié)點和邊。

3.2.3 節(jié)點的知識

在TNEG中，節(jié)點N的所有鄰居節(jié)點可以分成3類：一個父節(jié)點、N的孩子節(jié)點和滿足第2種情況的其他鄰居節(jié)點。每個節(jié)點都可以收集一跳鄰居的標(biāo)記信息。

定義 1 節(jié)點知識。節(jié)點自身以及所有一跳鄰居節(jié)點的標(biāo)記區(qū)間的并集。

通過圖4可以發(fā)現(xiàn)以下2個性質(zhì)：1)節(jié)點的知識分布是不平衡的；2)節(jié)點的知識具有局部性。下面設(shè)計的貪婪算法主要是基于節(jié)點知識具有局部性進行的。

圖4 節(jié)點知識分布(網(wǎng)絡(luò)節(jié)點個數(shù)138)

4 基于TNEG的路由算法

假設(shè)源節(jié)點為S：[iS, rS]，目的節(jié)點為D：[iD, rD]。如前所述S和D的關(guān)系如下。

1) 包含情形：iD∈ [iS, rS]；

2) 獨立情形：iD? [iS, rS]。

對包含情形來說，肯定存在S的一個子節(jié)點C：[iC, rC]，滿足iC≤iD≤rC，因此源節(jié)點S可以直接將數(shù)據(jù)發(fā)送給C。但是對獨立情形而言，源節(jié)點S找不到滿足 iC≤iD≤rC的子節(jié)點作為下一跳節(jié)點。對獨立情形而言,可以設(shè)計以下3種算法。

4.1 基本路由算法

顯然，根節(jié)點[1, n]在最短路徑樹上能夠發(fā)現(xiàn)到網(wǎng)絡(luò)中其他節(jié)點的路由方式。同理節(jié)點[i, r]能夠發(fā)現(xiàn)ID從i到r的所有節(jié)點的路由方式。所以基本路由算法TBR(tree based routing)的思想是將數(shù)據(jù)發(fā)送給當(dāng)前節(jié)點的父親節(jié)點直到遇到包含情形為止。

4.2 基于節(jié)點知識基本路由算法

在基本路由算法中，僅使用了最短路徑樹上的信息，即所有的路徑都是樹上的路徑，而不會用到除最短路徑樹上的鏈接以外的其他鏈接。不過在某些情況下，節(jié)點可以從非父節(jié)點和非子節(jié)點的其他節(jié)點上獲得信息。如圖2所示，當(dāng)節(jié)點[7,8]需要查找[12,12]時，可以發(fā)現(xiàn)鄰居節(jié)點[11,12]覆蓋了節(jié)點[12,12]，因此節(jié)點[7,8]可以直接將數(shù)據(jù)發(fā)送給[11,12]，而不用發(fā)送給其父節(jié)點[4,8]。因此基于節(jié)點知識基本路由算法(tree based and one hop knowledge routing)通過查看節(jié)點的知識，獲得更大的機會找到覆蓋目標(biāo)節(jié)點標(biāo)記的節(jié)點。

4.3 弱貪婪路由算法

4.3.1 貪婪函數(shù)

貪婪路由主要關(guān)注獨立情形。對第1種情況，同樣使用基本路由算法，該貪婪路由為弱貪婪路由算法。設(shè)計弱貪婪路由算法的關(guān)鍵在于尋找一個具有局部單調(diào)性的函數(shù)。本文設(shè)計了下面的函數(shù)作為貪婪函數(shù)：

其中，sgn(n)為符號函數(shù)，當(dāng) n＞0時，sgn(n)=1；當(dāng)n＜0時，sgn(n)=-1；sgn(0)=0。[x,y] 表示當(dāng)前節(jié)點要考察的鄰居節(jié)點的標(biāo)記，滿足x ≤ y。

該函數(shù)滿足：1) iS＜x2＜ x1＜iD且 y1＞rS，y2＞rS；2) iD＜ x1＜ x2＜ iS時，f (x1,y1) ＜ f(x2,y2)。1)和 2)給出了關(guān)于源節(jié)點和目的節(jié)點ID的不同關(guān)系。第1種情況說明當(dāng)iS＜ iD時，所有范圍(y值) 大于rS的當(dāng)前節(jié)點的鄰居節(jié)點滿足關(guān)于 x值在區(qū)間(iS, iD)的局部單調(diào)遞減性，x值越大函數(shù)f值越小。同理對第2種情況滿足關(guān)于x值在區(qū)間(iD, iS)的局部單調(diào)遞增性。

4.3.2 路由規(guī)則

定義2 候選鄰居集。C= {N|N ∈N(S)，當(dāng)iS＜iD時，滿足iS＜iN＜iD或者當(dāng)iD＜iS時，滿足iD＜iN＜iS。

其中，N(S) 表示節(jié)點S在網(wǎng)絡(luò)中的所有鄰居集合。根據(jù)貪婪函數(shù)，為獨立情形定義2個規(guī)則：

1) 貪婪規(guī)則。如果C不為空，下一跳為滿足min{f (iN,rN) ＞ 0, N ∈C}的節(jié)點；

2) 缺省規(guī)則。如果C=φ，下一跳節(jié)點為當(dāng)前節(jié)點的父節(jié)點。

圖5給出了貪婪規(guī)則。根據(jù)貪婪規(guī)則和缺省計劃，設(shè)計了TGR(tree based greedy routing)算法(算法1)。如前所述TGR為弱貪婪路由算法，因為當(dāng)根據(jù)貪婪規(guī)則找不到下一跳節(jié)點的時候，算法放棄使用貪婪規(guī)則而是使用缺省規(guī)則替代。算法的關(guān)鍵是TNEG網(wǎng)絡(luò)中節(jié)點的知識具有局部性。如果源節(jié)點和目標(biāo)節(jié)點之間的路徑都是通過貪婪規(guī)則獲得的，則根據(jù)貪婪函數(shù)的局部單調(diào)性可以保證該路徑無環(huán)。如果路徑當(dāng)中的某些節(jié)點是通過缺省規(guī)則選擇的，因為父節(jié)點的范圍要大于等于當(dāng)前節(jié)點的范圍，所以所有當(dāng)前節(jié)點不會在路徑中出現(xiàn)第2次。

圖5 貪婪規(guī)則

算法 1 基于 TNEG的弱貪婪路由算法 TGR(節(jié)點S)

輸入：節(jié)點S的標(biāo)記[i,r],目的節(jié)點ID，節(jié)點S的父節(jié)點P和在生成樹T上的S的子節(jié)點集合C，以及網(wǎng)絡(luò)上的其他一跳鄰居H。

輸出：下一跳節(jié)點N

1) 如果S. ID=j，則停止；

2) 否則,首先令N = P；

3) 如果i ＜ j ≤ r,則判斷集合C 中是否存在滿足C. ID ≤ j ≤ C. Range字節(jié)點C；

4) 如果存在,則 N = C,并輸出 N,算法停止;如果不存在轉(zhuǎn)到6)；

5) 判斷H中的是否存在節(jié)點 H滿足(H.Range-H. ID)＜R；

6) 如果存在,選擇滿足H. Range-H. ID最小的節(jié)點H0,N= H0；

7) 如果不存在，分為(a)、(b) 2種情況：(a)如果r ＜j，在H 中找到ID距離j最近的、滿足H. ID＜j的節(jié)點作為N；(b)如果i ＞ j，在H 中找到ID距離j最近的，滿足H. ID＞j的節(jié)點作為N；

8) 輸出N。

5 優(yōu)化討論

為了使基于樹嵌入的貪婪路由技術(shù)在性能上，特別是在路徑伸展因子上得到進一步改進，本節(jié)進一步討論并提出基于雙樹嵌入的弱貪婪路由技術(shù)。

5.1 無交叉連接生成樹

定義 3 交叉連接。假設(shè)相鄰節(jié)點的連接是一條直線段，如果2條直線段在幾何上存在非端點的相交點，則稱這2條連接是交叉連接。顯然，如果一個圖為非平面圖，則肯定存在交叉連接。

3.1節(jié)給出的構(gòu)建最短路徑生成樹的方法中，一個節(jié)點可能存在多個距離根節(jié)點小于當(dāng)前節(jié)點的鄰居節(jié)點，當(dāng)前節(jié)點通過隨機的方式選擇其中一個節(jié)點作為父節(jié)點。這種方法構(gòu)建的生成樹，在現(xiàn)實的網(wǎng)絡(luò)中有可能存在多個交叉連接。

圖6 同一個網(wǎng)絡(luò)的不同的標(biāo)記嵌入

5.2 隨機標(biāo)記與順序標(biāo)記

在3.1節(jié)中，構(gòu)建最短路徑樹的過程中并沒有考慮和避免交叉連接存在，而且在基于一棵樹的標(biāo)記分配算法中也沒有考慮節(jié)點之間標(biāo)記如何分配，只是按照節(jié)點覆蓋的節(jié)點個數(shù)按比例劃分標(biāo)記區(qū)間，并沒有考慮相同層次上的節(jié)點標(biāo)記區(qū)間的關(guān)系。這會導(dǎo)致圖6(a)所示的節(jié)點標(biāo)記在網(wǎng)絡(luò)中的分布雜亂。比如說，在圖 6(a)中，如果節(jié)點 D([4,4])需要訪問節(jié)點G([6,6])，按照TBR路由算法得到的路徑為[4,4]→[2,4]→[1,7]→[5,7]→[6,6]。但是如果得到的最短路徑樹和標(biāo)記如圖6(b)所示，從節(jié)點D到節(jié)點G的路徑為[3,3]→[4,4]→[6,6]→[7,7]。由此可見，對同一網(wǎng)絡(luò)的不同標(biāo)記嵌入，對路由的性能有很大的影響。造成這種現(xiàn)象的原因，一是構(gòu)建的最短路徑樹中存在交叉連接；二是在節(jié)點的標(biāo)記分配過程中，沒有考慮樹的同一層節(jié)點之間的順序關(guān)系，即節(jié)點標(biāo)記能在多大范圍之內(nèi)滿足單調(diào)性。在最短路徑樹中存在交叉連接，且沒有考慮同一層節(jié)點標(biāo)記之間關(guān)系的標(biāo)記分配方式稱為隨機標(biāo)記分配。而滿足：生成的樹在網(wǎng)絡(luò)中不存在交叉的連接；同一層次的節(jié)點的標(biāo)記滿足順序關(guān)系的標(biāo)記分配方式，稱為順序標(biāo)記分配。為了增加TNEG的局部單調(diào)性，希望得到的嵌入圖是順序標(biāo)記的。不過在傳感器網(wǎng)絡(luò)中，特別是在節(jié)點信息未知，在沒有全局拓撲信息的情況下，得到順序標(biāo)記非常具有挑戰(zhàn)性。本文的策略不追求完全的順序標(biāo)記，而是盡可能得到局部順序標(biāo)記的網(wǎng)絡(luò)嵌入。

5.3 基于雙樹的網(wǎng)絡(luò)嵌入

本文的策略是利用文獻[15]提出 Contour-cast技術(shù)，首先在網(wǎng)絡(luò)中構(gòu)建輪廓覆蓋網(wǎng)。當(dāng)選擇了 2個信標(biāo)節(jié)點(B信標(biāo)和R信標(biāo))，構(gòu)建出輪廓覆蓋網(wǎng)以后，相當(dāng)于構(gòu)建了一種虛擬坐標(biāo)系統(tǒng)，每個節(jié)點都擁有一個〈bluehop,redhop〉的坐標(biāo)值。在該坐標(biāo)系內(nèi)每個節(jié)點都可以根據(jù)所在的R型輪廓(B型輪廓)來判斷所在的B型輪廓(R型輪廓)的方向。基于雙樹網(wǎng)絡(luò)嵌入的過程如下。

首先構(gòu)建以B信標(biāo)為根節(jié)點的B型樹。每個節(jié)點要選擇一個節(jié)點作為自己的B型父節(jié)點，選擇的原則是：在所有bluehop小于當(dāng)前節(jié)點的鄰居中，選擇redhop最小的節(jié)點作為自己的B型父節(jié)點。以 R型信標(biāo)為根節(jié)點的R型樹也以同樣的規(guī)則建立。同樣在標(biāo)記分配過程中，比如說在B型樹上分配標(biāo)記，當(dāng)前節(jié)點總是將最小的標(biāo)記分配給redhop最小的孩子節(jié)點。

以上過程，通過B型和R型輪廓互為方向，保證了節(jié)點標(biāo)記在分配的過程中能夠在局部盡可能地達到順序標(biāo)記的要求。此時每個節(jié)點都有B型/R型2種標(biāo)記，節(jié)點需要存儲4個整數(shù)。稱在雙樹網(wǎng)絡(luò)嵌入上設(shè)計的路由為biTGR。biTGR算法原理上和前面基于TNEG的TGR沒有區(qū)別，只是通過B型/R型2種標(biāo)記，增加了節(jié)點標(biāo)記之間包含情形的概率，限于篇幅本文省略了biTGR的偽代碼。綜上所述，biTGR在網(wǎng)絡(luò)中的初始化要比TGR復(fù)雜，在內(nèi)存的使用上比TGR多2個字節(jié)。但通過下面的模擬，biTGR在路徑伸展性上要優(yōu)于TGR。

6 性能測試

本節(jié)通過仿真實驗比較上文提出算法的性能。本文的仿真環(huán)境使用NS2網(wǎng)絡(luò)模擬平臺，在一個正方形區(qū)域內(nèi)部署500個節(jié)點，節(jié)點的平均度數(shù)為14，網(wǎng)絡(luò)直徑為16跳,，在仿真環(huán)境中假設(shè)節(jié)點之間如果距離小于一個閾值，則能進行直接通信，否則不能通信。本文考慮的最重要的性能指標(biāo)為連接源節(jié)點和目標(biāo)節(jié)點(S-D對)的路徑長度、交叉鏈路使用情況以及負載均衡。

6.1 路徑伸展性

在本測試中，隨機地選擇1 000對S-D對，并分別利用TBR、TBHR和TGR產(chǎn)生相應(yīng)的路徑，最后統(tǒng)計各個算法的路徑情況。圖7中x軸表示源節(jié)點和目標(biāo)節(jié)點的最短路徑長度，y軸表示根據(jù)相應(yīng)的路由算法產(chǎn)生的路徑跳步長度。圖7計算出各種策略相對于最短路徑的平均路徑長度?？梢钥吹皆诒緶y試中當(dāng)S-D間最短路徑長度小于11的時候，TGR的平均路徑長度小于TBR；當(dāng)S-D距離小于8跳的時候，TGR的平均路徑長度要小于TBHR。同時看到：1)TBHR的路徑長度總是好于TBR，這說明節(jié)點知識是非常重要的；2)當(dāng)S-D的距離變大時，TGR的路徑長度要長于TBR和TBHR。這是因為當(dāng)節(jié)點的距離足夠大時，其通過訪問SPT得到的路徑長度(即TBR和TBHR產(chǎn)生的路徑)與最短的路徑長度已經(jīng)非常接近，而此時 TGR產(chǎn)生的路由中可能存在距離目標(biāo)節(jié)點較遠的中間節(jié)點。圖8給出了基于雙樹的網(wǎng)絡(luò)嵌入下，在路徑長度方面4種算法的性能比較。可以發(fā)現(xiàn)基于雙樹網(wǎng)絡(luò)嵌入標(biāo)記的路由biTGR在性能上要優(yōu)于其他3種。即使TGR的性能也獲得了較大提高，這是因為在雙樹網(wǎng)絡(luò)嵌入中存在更多的順序標(biāo)記。

圖7 3種算法的路徑平均情況

圖8 在雙樹嵌入下4種算法的路徑平均情況

6.2 交叉鏈路使用情況

SPT僅覆蓋了整個網(wǎng)絡(luò)的一小部分鏈路，因此TBR浪費了所有沒有在SPT上出現(xiàn)的交叉鏈路。對TBHR來說，最多有一次機會使用沒有在SPT上出現(xiàn)的鏈路。通過測試可以發(fā)現(xiàn)在使用沒有在SPT上出現(xiàn)的鏈路上，TGR具有的較大的優(yōu)勢。圖9顯示，TGR的交叉鏈路的使用率平均在 40%以上， 而TGHR的交叉鏈路使用率隨著路徑長度增加而逐漸下降，當(dāng)路徑長度超過 10以后，其交叉鏈路的使用率要低于10%。

圖9 2種算法的交叉鏈路使用情況

6.3 負載均衡

在數(shù)據(jù)為中心的傳感器網(wǎng)絡(luò)中，存儲的負載均衡是非常重要的因素[16]。一個好的存儲策略應(yīng)該可以平衡所有傳感器的負載分布。這可以避免某些節(jié)點成為瓶頸或者過早地耗盡電量，對延長整個網(wǎng)絡(luò)的生命周期起到至關(guān)重要的作用。本文采用所有節(jié)點負載的方差定義網(wǎng)絡(luò)的負載均衡性。在本測試中，隨機選擇1 500個S-D對。如果節(jié)點轉(zhuǎn)發(fā)過一個數(shù)據(jù)分組，則其負載計數(shù)器加1。對TBR、TBHR和TGR 3種策略分別進行測試，按照節(jié)點的負載計數(shù)器，對節(jié)點進行降序排序。在圖10中分別將3種策略的情況列出來?？梢园l(fā)現(xiàn)在500個節(jié)點當(dāng)中前50多個節(jié)點在TBR算法中的負載計數(shù)器是TGR算法的2倍多。這是因為在TBR和TBHR中，根節(jié)點和根節(jié)點附件的節(jié)點負責(zé)了較多數(shù)據(jù)的轉(zhuǎn)發(fā)。在TGR中，通過貪婪規(guī)則，某些節(jié)點可以繞過根節(jié)點和根節(jié)點附近的節(jié)點找到目的節(jié)點。

圖10 節(jié)點負載排序

圖11從單個節(jié)點的角度說明了傳輸負載情況。圖11中對同一網(wǎng)絡(luò)分別選擇不同規(guī)模的S-D對，規(guī)模程度從50對到1 500對，以50遞增?？梢园l(fā)現(xiàn)隨著 S-D對規(guī)模的增大，TBR、TBHR和 TGR的負載均衡因子都不斷增加。但是 TGR的負載增長速度明顯慢于TBR和TBHR。

圖11 3種算法的負載均衡因子

7 結(jié)束語

本文首先將傳感器網(wǎng)絡(luò)中的貪婪路由策略分為強貪婪和弱貪婪2種，分析了目前的策略的不足，提出了一種新的基于樹的網(wǎng)絡(luò)嵌入圖(TNEG)的構(gòu)建方法。在此基礎(chǔ)上設(shè)計了弱貪婪算法TGR。TGR可以應(yīng)用在傳感器網(wǎng)絡(luò)和分布式存儲等領(lǐng)域。本文通過模擬驗證了TGR的可行性和優(yōu)勢，而且討論了通過利用基于雙樹的網(wǎng)絡(luò)嵌入并進一步改進TGR的思想。未來的工作包括如何將TGR應(yīng)用到動態(tài)網(wǎng)絡(luò)中，特別是當(dāng)節(jié)點失效時，如何迅速恢復(fù)網(wǎng)絡(luò)嵌入標(biāo)記。

[1] 孫利民,李建中,陳渝等.無線傳感器網(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.

[2] 任豐原 ,黃海寧, 林闖. 無線傳感器網(wǎng)絡(luò)[J]. 軟件學(xué)報, 2003,14(7):1282-1291.REN F Y, HUANG H N, LIN C. Wireless sensor networks[J]. Journal of Software,2003,14(7):1282-1291.

[3] SAKAI K, HAMILTON B R, KU W S, et al. G-STAR: geometric STAteless routing for 3-D wireless sensor networks[J]. Ad Hoc Networks, 2010, 9(3): 341-354.

[4] KARP B, KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[A]. Proceedings of the MobiCom[C]. MA, USA,2000. 243-254.

[5] WU X B, CHEN G, DAS S K. Avoiding energy holes in wireless sensor networks with nonuniform node distribution[J]. IEEE Transactions on Parallel and Distributed Systems, 2008,19(5): 710-720.

[6] FREY H, STOJMENOVIC I. On delivery guarantees of face and combined greedy face routing in ad hoc and sensor networks[A]. Proceedings of the MobiCom[C]. CA, USA, 2006.390-401.

[7] 王福豹, 史龍, 任豐原. 無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J]. 軟件學(xué)報, 2005, 16(5):857-868.WANG F B, SHI L, REN F Y. Self-Localization systems and algorithms for wireless sensor networks[J]. Journal of Software,2005,16(5): 857-868.

[8] PAPADIMITRIOU C, RATAJCZAK D. On a conjecture related to geometric routing[J]. Theoretical Computer Science, 2005, 344(1): 3-14.

[9] GALLIAN J A. A dynamic survey of graph labeling[J]. The Electronic Journal of Combinatorics, 2010,17(1):1-246.

[10] GAVOILLE C. A survey on interval routing[J]. Theoretical Computer Science, 2000, 245(2): 217-253.

[11] PELEG D. Informative labeling schemes for graphs[A].Proceedings of MFCS[C]. Bratislava, Slovak, 2000. 579-588.

[12] NEWSOME J, SONG D. Gem: graph embed-ding for routing and datacentric storage in sensor net-works without geographic information[A]. Proceedings of SenSys[C]. CA, USA, 2003. 76-88.

[13] KLEINBERG R. Geographic routing using hyperbolic space[A].Proceedings of INFOCOM[C]. AL, USA, 2007.1902-1909.

[14] SARKAR R, YIN X T, GAO J, et al. Greedy routing with guaranteed delivery using Ricci flows[A]. Proceedings of the IPSN[C]. CA, USA,2009. 121-132.

[15] LI Z G, XIAO N, LIU Y H, et al. contour-cast: location-free data dissemination and discovery for wireless sensor networks[A]. Proceedings of the ICPADS[C]. Shenzhen, China, 2009. 88-95.

[16] 李貴林, 高宏. 傳感器網(wǎng)絡(luò)中基于環(huán)的負載平衡數(shù)據(jù)存儲方法[J].軟件學(xué)報, 2007, 18(5): 1173-1185.LI G L, GAO H. A load balance data storage method based on ring for sensor networks[J]. Journal of Software, 2007, 18(5):1173-1185.