ＤＤＲＬＤ：支持局部擴散的定向擴散算法

摘要：在定向擴散協議中，中間節點以泛洪的機制向網絡中的所有鄰居節點轉發接收到的興趣報文，導致網絡能源的浪費。為此，提出一種支持局部擴散的定向擴散算法DDRLD。它通過設置梯度擴散深度閾值，縮小了興趣報文擴散的范圍，降低了網絡中傳輸的數據量；通過設置節點剩余能量門限值，增加了每個節點被選取為轉發節點的概率，延長了節點的平均工作時間，改善了網絡負載平衡。仿真結果表明DDRLD大大縮短了數據報文端到端的平均延遲，降低了網絡功耗，增加了網絡生存時間。

關鍵詞：無線傳感器網絡； 數據融合； 定向擴散； 擴散深度； 剩余能量

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2008)05-1330-03

在無線傳感器網絡中，每個傳感器節點的監測范圍及能量都是有限的。為了增強整個網絡所能獲得的信息魯棒性和準確性，放置節點時必須使節點的監測范圍互相交疊。這樣，節點所采集到的數據就存在一定的冗余信息，網絡負載會隨之增加。在網絡層中將路由協議和數據融合機制結合起來，可以減少傳送的數據量，從而節約網絡功耗，延長網絡的生存時間。數據融合技術是WSN研究中的重要部分[1]。

定向擴散(directed diffusion，DD)是針對無線傳感器網絡而設計的，提供了一種以數據為中心的路由協議體系結構。DD采用泛洪的機制建立路徑，不具有網內數據融合功能，導致了網絡能源的浪費。本文以傳統DD協議為基礎，設計了一種支持局部擴散、以數據為中心的路由協議——DDRLD，對興趣報文的擴散范圍和節點被選取為轉發節點的概率進行了優化。

1定向擴散算法分析

DD是基于查詢的路由機制[2]，它由查詢擴散階段、梯度建立階段、路徑加強和數據傳輸階段組成，如圖1所示。

在WSN中，sink節點無法獲得目標數據源節點的地理信息。DD中，在查詢擴散階段，sink節點采用泛洪的機制周期性地向所有傳感器節點發送興趣報文（即描述目標數據報文的屬性值）；接收到的節點會緩存信息到cache，查找所有匹配的目標數據（即目標數據報文，以下簡稱數據報文），如圖1（a）所示。

1)初始梯度建立階段

在DD中，梯度（gradients）的概念非常重要。梯度概念的提出是為了按成本最小化的原則引導數據擴散的方向，它定義了一個數據的發送方向和傳輸速率。當節點從鄰居節點接收到查詢興趣報文時，若當前的cache中沒有相同查詢記錄，則加入新記錄，記錄中包含了鄰居節點指定的數據傳輸速率即梯度，如圖1（b）所示。初始梯度的建立階段實際上是與查詢擴散階段同時雙向進行的。Sink節點發送興趣報文，而源節點發送數據報文。當網絡中的任意節點收到興趣報文和數據報文時，查詢成功。采用與單向查詢相同的傳輸方式，可以通過增加興趣報文和數據報文的數目來提高路徑質量。

2)路徑加強與數據傳輸階段

在數據傳輸階段，源節點將會沿著初始建立的梯度方向將數據報文傳輸給sink節點，sink節點會對最先收到目標數據的鄰居節點發送一個加強信息；接收到加強選擇的鄰居節點同樣加強選擇它最先收到新數據的鄰居節點，最后形成一條梯度值的最大路徑。這樣以后收集到的數據報文就會沿著這條最大的路徑傳輸，如圖1（c）所示。

在定向擴散中，興趣報文擴散的同時對網絡進行了配置，建立了興趣報文從sink節點到源節點的通道，同時建立了數據報文從源節點到sink節點的通道。興趣擴散的規則是基于本地信息的，無須對網絡拓撲有完整的了解。一個興趣報文傳遍整個網絡后，從源節點到sink節點之間的梯度（加強路徑）就建立起來了。

2支持局部擴散的定向擴散算法：DDRLD 

傳統DD中，當中間節點第一次收到轉發的興趣報文時，便以泛洪的機制向所有鄰居節點進行擴散。隨著擴散深度的增加，網絡中轉發的興趣報文的數目也呈指數增長。當節點密度較大時，會造成網絡負載的急劇膨脹，網絡性能也迅速下降；而且，WSN中源節點個數有限，對全網進行擴散會造成極大的浪費。因此，在查詢擴散階段和更新查詢信息階段合理減少興趣報文的擴散范圍是十分必要的。另外，傳統 DD采用興趣報文的傳輸速率來建立梯度的模式，容易造成某些靠近sink節點或處于某些關鍵位置節點的能量很快耗盡，而另外一些節點還有剩余較多的能量。為了增加其他節點被選取為轉發節點的概率，改善網絡負載平衡，加入節點剩余能量的門限值也是十分必要的。

2．1DDRLD描述

a）在興趣報文擴散的過程中，利用轉發節點的剩余能量和到鄰居節點的最小跳數來建立梯度。在源節點處，某個鄰居節點梯度大小表明了從該鄰居節點轉發興趣報文到sink節點的最小跳數。最小跳數是sink節點到源節點多條路徑跳數的最小值，反映了路徑的最優延遲指標。節點的剩余能量體現了轉發節點所在路徑最長可能持續的時間。

b）梯度的建立過程。興趣報文攜帶上一跳節點的最小跳數和節點剩余能量等信息。當興趣報文通過多條路徑到達某節點時，如果該節點同時滿足以下三個條件才可以被選取為下一跳節點，即與sink節點建立梯度：

(a)節點自身能量高于設置的節點剩余能量門限值；

(b)節點所在的路徑跳數最小；

(c)興趣報文的擴散深度低于設置的梯度擴散深度閾值。

c）梯度的建立過程實質。通過設置梯度擴散深度閾值來減少興趣報文擴散范圍或轉發次數；通過設置節點剩余能量的門限值來增加每個節點被選取為轉發節點的概率，用來延長節點的平均工作時間和改善網絡負載平衡；同時還要滿足傳統DD中對梯度的要求。

d）在DDRLD中，每個興趣報文最多進行設置的擴散深度閾值次數擴散后停止，即如果擴散深度閾值為4，那么每個擴散興趣報文在退出網絡之前，最多可被轉發四次。如果在此之前節點的剩余能量低于設置的能量門限值，就提前終止該節點，繼續轉發興趣報文，選擇其他符合條件的節點作為下一跳節點。

2．2DDRLD分析

DDRLD假定運行在理想的MAC協議之上，在任意連接的節點對之間提供沖突避免的點對點的雙工通信。所以，在網絡層計算能源消耗時，可以根據網絡中的數據傳輸量來計算[3]。假定N個傳感器節點均勻分布在半徑為R，節點傳輸范圍為r的區域，則每個節點都具有r2N/R2-1個鄰居節點。節點的發送消耗功率為Ps，接收消耗功率為Pr。在傳統DD算法中，興趣報文以泛洪的機制向整個網絡擴散，所有網絡消耗的能源為

3仿真實驗與結果分析

仿真基于CMU的NS－2平臺。在網絡仿真性能評價指標中，主要在端到端的平均延遲和整個網絡的剩余能量兩個方面對DDRLD進行評估。端到端的平均延遲是指一個數據報文從源節點發送到sink節點所花費的平均時間。整個網絡的剩余能量反映了一個傳感器網絡的生命周期。

仿真環境中，節點隨機分布在670 m×670 m的矩形區域，1個sink節點，8個源節點；梯度的擴散深度閾值為4，節點剩余能量的門限值為初始能量的1/32；配置節點的傳輸范圍為R=20 m，采用S－MAC協議（USC/ISI于2005年在NS－2中成功實現了S－MAC）；采用較真實的節點能源消耗模型，興趣報文的發送間隔設為30 s。節點其他配置與文獻[2]相同。下面對兩種算法進行統計比較。

3．1平均延遲分析

在兩種算法模式下，節點數目N的變化對數據傳輸平均延遲的影響如圖2所示。每個源節點單位時間生成一個數據報文。隨著N的增加，兩種算法模式下的平均延遲都有所增大。當N為50~100時， DDRLD中，數據傳輸平均延遲從0．05 s上升到0．2 s；而傳統DD中，平均延遲卻從0．2 s上升到0．65 s。DD中的平均延遲增長的幅度比較大，這是因為在傳統DD中，需要更多的節點建立的梯度以接收數據，導致了較大的延遲。可以認為在DDRLD中，網絡性能比較穩定，不容易受網絡規模的影響。隨著節點數目的增大，DDRLD的性能就越明顯。

3．2剩余能量分析

在兩種算法模式下，整個網絡中的剩余能量隨時間變化的情況如圖3所示。設置網絡中節點的數目N為100，設每個節點的初始能量為10 J。從圖3中可以看出，在相同的仿真場景下，在DDRLD中，整個網絡的剩余能量要高于在傳統DD下整個網絡的剩余能量。這是因為DDRLD中，通過增設梯度的擴散深度閾值，在查詢擴散階段和更新查詢信息階段，減少了興趣報文擴散范圍，從而大大減少網絡中傳輸的數據量；通過設置節點剩余能量的門限值，增大了每個節點被選取為轉發節點的概率，延長了節點的平均工作時間，改善了網絡負載平衡，降低了網絡功耗，從而延長了整個網絡生存的時間。

參考文獻：

[1]BOULIS A， GANERIWAL S， SRIVASTAVA M B. Aggregation in sensor networks: an energy－accuracy trade－off[J].Elsevier Journal of Ad hoc Networks， 2003，1(2-3):317-331.

[2]INLANAGONWIWAT C， GOVINDAN R， ESTRIN D， et al. Direc-ted diffusion for wireless sensor net working[J]. IEEE/ACM Trans Networking，2003，11(1):2－16.

[3]HOU Rong－hui， SHI Hao－shan， YANG Shao－jun. RPDDP: an energy－efficient routing protocol supporting distributed data processing for wireless sensor networks[J]. Journal of Northwestern Polytechnical University，2006，24(10):614-618.

[4]SHAH R C， RABAEY J M. Energy aware routing for low energy Ad hoc sensor networks[C]//Proc of IEEE Wireless Communications and Networking Conference.[S.l.]: IEEE，2002:17-21.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”