ＤＤＲＬＤ：支持局部擴(kuò)散的定向擴(kuò)散算法

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)； 數(shù)據(jù)融合； 定向擴(kuò)散； 擴(kuò)散深度； 剩余能量

中圖分類號：TP301文獻(xiàn)標(biāo)志碼：A

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

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

定向擴(kuò)散(directed diffusion，DD)是針對無線傳感器網(wǎng)絡(luò)而設(shè)計的，提供了一種以數(shù)據(jù)為中心的路由協(xié)議體系結(jié)構(gòu)。DD采用泛洪的機(jī)制建立路徑，不具有網(wǎng)內(nèi)數(shù)據(jù)融合功能，導(dǎo)致了網(wǎng)絡(luò)能源的浪費。本文以傳統(tǒng)DD協(xié)議為基礎(chǔ)，設(shè)計了一種支持局部擴(kuò)散、以數(shù)據(jù)為中心的路由協(xié)議——DDRLD，對興趣報文的擴(kuò)散范圍和節(jié)點被選取為轉(zhuǎn)發(fā)節(jié)點的概率進(jìn)行了優(yōu)化。

1定向擴(kuò)散算法分析

DD是基于查詢的路由機(jī)制[2]，它由查詢擴(kuò)散階段、梯度建立階段、路徑加強(qiáng)和數(shù)據(jù)傳輸階段組成，如圖1所示。

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

1)初始梯度建立階段

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

2)路徑加強(qiáng)與數(shù)據(jù)傳輸階段

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

在定向擴(kuò)散中，興趣報文擴(kuò)散的同時對網(wǎng)絡(luò)進(jìn)行了配置，建立了興趣報文從sink節(jié)點到源節(jié)點的通道，同時建立了數(shù)據(jù)報文從源節(jié)點到sink節(jié)點的通道。興趣擴(kuò)散的規(guī)則是基于本地信息的，無須對網(wǎng)絡(luò)拓?fù)溆型暾牧私狻Ｒ粋€興趣報文傳遍整個網(wǎng)絡(luò)后，從源節(jié)點到sink節(jié)點之間的梯度（加強(qiáng)路徑）就建立起來了。

2支持局部擴(kuò)散的定向擴(kuò)散算法：DDRLD 

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

2．1DDRLD描述

a）在興趣報文擴(kuò)散的過程中，利用轉(zhuǎn)發(fā)節(jié)點的剩余能量和到鄰居節(jié)點的最小跳數(shù)來建立梯度。在源節(jié)點處，某個鄰居節(jié)點梯度大小表明了從該鄰居節(jié)點轉(zhuǎn)發(fā)興趣報文到sink節(jié)點的最小跳數(shù)。最小跳數(shù)是sink節(jié)點到源節(jié)點多條路徑跳數(shù)的最小值，反映了路徑的最優(yōu)延遲指標(biāo)。節(jié)點的剩余能量體現(xiàn)了轉(zhuǎn)發(fā)節(jié)點所在路徑最長可能持續(xù)的時間。

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

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

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

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

c）梯度的建立過程實質(zhì)。通過設(shè)置梯度擴(kuò)散深度閾值來減少興趣報文擴(kuò)散范圍或轉(zhuǎn)發(fā)次數(shù)；通過設(shè)置節(jié)點剩余能量的門限值來增加每個節(jié)點被選取為轉(zhuǎn)發(fā)節(jié)點的概率，用來延長節(jié)點的平均工作時間和改善網(wǎng)絡(luò)負(fù)載平衡；同時還要滿足傳統(tǒng)DD中對梯度的要求。

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

2．2DDRLD分析

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

3仿真實驗與結(jié)果分析

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

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

3．1平均延遲分析

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

3．2剩余能量分析

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

參考文獻(xiàn)：

[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－h(huán)ui， 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.

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