無線傳感器網絡中基于網絡嵌入的弱貪婪路由協議

李志剛，陳衛衛，肖儂，夏戈明

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

1 引言

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

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

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

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

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

2 預備知識

本文將無線傳感器網絡看作連通的有限無向圖，下面介紹一下與本文工作相關的圖論當中的圖標記和圖嵌入技術。

2.1 圖標記機制

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

2.1.1 區間路由標記

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

圖1 區間路由標記[10]

2.1.2 距離標記

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

2.2 圖嵌入技術

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

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

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

3 基于樹的網絡嵌入圖

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

3.1 基于樹的網絡嵌入圖構建

基于樹的網絡嵌入圖(TNEG, tree-based network embedding graph)構建包括2步。首先在網絡中構建一棵樹并且統計所有節點的個數；然后從根節點開始按照自上而下的方式為每個節點分配一個標記。

3.1.1 通過最短路徑樹統計節點總數

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

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

其中，d為網絡的平均度數，Ew代表整個網絡的能量開銷，Es為節點發送一個消息的能量開銷，Er為節點收到一個消息的能量開銷。

3.1.2 標記分配

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

圖2給出了TNEG網絡的一個具體的例子。在TNEG網絡中，每個節點都對應一個[i,r]的標記，稱i為節點的ID，r為節點的范圍。節點N的標記[i,r]作為一個整數區間包含了所有以N為根節點的子樹節點的ID。

圖2 基于樹的網絡嵌入標記

3.2 TNEG的屬性

3.2.1 標記性質

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

3.2.2 標記間的關系

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

圖3 標記之間的關系

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

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

3.2.3 節點的知識

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

定義 1 節點知識。節點自身以及所有一跳鄰居節點的標記區間的并集。

通過圖4可以發現以下2個性質：1)節點的知識分布是不平衡的；2)節點的知識具有局部性。下面設計的貪婪算法主要是基于節點知識具有局部性進行的。

圖4 節點知識分布(網絡節點個數138)

4 基于TNEG的路由算法

假設源節點為S：[iS, rS]，目的節點為D：[iD, rD]。如前所述S和D的關系如下。

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

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

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

4.1 基本路由算法

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

4.2 基于節點知識基本路由算法

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

4.3 弱貪婪路由算法

4.3.1 貪婪函數

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

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

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

4.3.2 路由規則

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

其中，N(S) 表示節點S在網絡中的所有鄰居集合。根據貪婪函數，為獨立情形定義2個規則：

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

2) 缺省規則。如果C=φ，下一跳節點為當前節點的父節點。

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

圖5 貪婪規則

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

輸入：節點S的標記[i,r],目的節點ID，節點S的父節點P和在生成樹T上的S的子節點集合C，以及網絡上的其他一跳鄰居H。

輸出：下一跳節點N

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

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

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

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

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

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

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

8) 輸出N。

5 優化討論

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

5.1 無交叉連接生成樹

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

3.1節給出的構建最短路徑生成樹的方法中，一個節點可能存在多個距離根節點小于當前節點的鄰居節點，當前節點通過隨機的方式選擇其中一個節點作為父節點。這種方法構建的生成樹，在現實的網絡中有可能存在多個交叉連接。

圖6 同一個網絡的不同的標記嵌入

5.2 隨機標記與順序標記

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

5.3 基于雙樹的網絡嵌入

本文的策略是利用文獻[15]提出 Contour-cast技術，首先在網絡中構建輪廓覆蓋網。當選擇了 2個信標節點(B信標和R信標)，構建出輪廓覆蓋網以后，相當于構建了一種虛擬坐標系統，每個節點都擁有一個〈bluehop,redhop〉的坐標值。在該坐標系內每個節點都可以根據所在的R型輪廓(B型輪廓)來判斷所在的B型輪廓(R型輪廓)的方向?；陔p樹網絡嵌入的過程如下。

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

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

6 性能測試

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

6.1 路徑伸展性

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

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

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

6.2 交叉鏈路使用情況

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

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

6.3 負載均衡

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

圖10 節點負載排序

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

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

7 結束語

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

[1] 孫利民,李建中,陳渝等.無線傳感器網絡[M]. 北京：清華大學出版社, 2005.SUN L M, LI J Z, CHEN Y, et al. Wireless Sensor Networks[M]. Beijing: Tsinghua University Press, 2005.

[2] 任豐原 ,黃海寧, 林闖. 無線傳感器網絡[J]. 軟件學報, 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] 王福豹, 史龍, 任豐原. 無線傳感器網絡中的自身定位系統和算法[J]. 軟件學報, 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] 李貴林, 高宏. 傳感器網絡中基于環的負載平衡數據存儲方法[J].軟件學報, 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.