無線傳感器網(wǎng)絡(luò)中基于網(wǎng)絡(luò)嵌入的弱貪婪路由協(xié)議

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

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

1 引言

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

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

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

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

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

2 預(yù)備知識

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

2.1 圖標(biāo)記機(jī)制

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

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

2.1.2 距離標(biāo)記

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

2.2 圖嵌入技術(shù)

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

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

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

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

本節(jié)的核心思想是首先將網(wǎng)絡(luò)嵌入到一棵最短路徑樹上，然后在該最短路徑樹上進(jìn)行節(jié)點(diǎn)標(biāo)記工作。不失一般性，本文對傳感器網(wǎng)絡(luò)作以下假設(shè)：1) 傳感器網(wǎng)絡(luò)是連通無向圖；2) 傳感器節(jié)點(diǎn)不需要知道自身和其他節(jié)點(diǎn)的位置信息；3) 傳感器網(wǎng)絡(luò)是靜態(tài)的網(wǎng)絡(luò)，或者在一段時(shí)間內(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)計(jì)所有節(jié)點(diǎn)的個(gè)數(shù)；然后從根節(jié)點(diǎn)開始按照自上而下的方式為每個(gè)節(jié)點(diǎn)分配一個(gè)標(biāo)記。

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

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

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

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

3.1.2 標(biāo)記分配

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

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

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

3.2 TNEG的屬性

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

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

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

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

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

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

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

3.2.3 節(jié)點(diǎn)的知識

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

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

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

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

4 基于TNEG的路由算法

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

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

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

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

4.1 基本路由算法

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

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

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

4.3 弱貪婪路由算法

4.3.1 貪婪函數(shù)

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

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

該函數(shù)滿足：1) iS＜x2＜ x1＜iD且 y1＞rS，y2＞rS；2) iD＜ x1＜ x2＜ iS時(shí)，f (x1,y1) ＜ f(x2,y2)。1)和 2)給出了關(guān)于源節(jié)點(diǎn)和目的節(jié)點(diǎn)ID的不同關(guān)系。第1種情況說明當(dāng)iS＜ iD時(shí)，所有范圍(y值) 大于rS的當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)滿足關(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時(shí)，滿足iS＜iN＜iD或者當(dāng)iD＜iS時(shí)，滿足iD＜iN＜iS。

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

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

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

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

圖5 貪婪規(guī)則

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

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

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

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

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

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

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

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

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

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

8) 輸出N。

5 優(yōu)化討論

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

5.1 無交叉連接生成樹

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

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

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

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

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

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

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

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

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

6 性能測試

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

6.1 路徑伸展性

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

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

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

6.2 交叉鏈路使用情況

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

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

6.3 負(fù)載均衡

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

圖10 節(jié)點(diǎn)負(fù)載排序

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

圖11 3種算法的負(fù)載均衡因子

7 結(jié)束語

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