嚴(yán)利民，張 健，王 峰

(上海大學(xué) 微電子研究與開發(fā)中心，上海 200444)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是物聯(lián)網(wǎng)的重要組成部分[1]，但是，WSN節(jié)點受到能量資源的限制，因此降低節(jié)點能耗具有重要意義。同時，人們對節(jié)能路由的研究也在進(jìn)一步深入，節(jié)能路由目標(biāo)主要包括以下3個：

(1)控制數(shù)據(jù)包的數(shù)量最小化：無線傳感器網(wǎng)絡(luò)通常實現(xiàn)融合流量模式，即所有數(shù)據(jù)包都必須通過匯聚節(jié)點(sink)，網(wǎng)關(guān)路由再傳到Internet。主動路由協(xié)議在轉(zhuǎn)發(fā)數(shù)據(jù)到sink中時，能夠有效限制控制數(shù)據(jù)包的數(shù)量。例如梯度路由RPL[2]協(xié)議；

(2)避免最弱的節(jié)點：在匯聚融合流量模式下，sink周邊的節(jié)點需要轉(zhuǎn)發(fā)更多的數(shù)據(jù)流量，因此會消耗更多的帶寬和能量。這種現(xiàn)象會導(dǎo)致MAC層中產(chǎn)生漏斗效應(yīng)，增加了碰撞次數(shù)[3]。對于路由層而言，負(fù)載必須在節(jié)點之間盡可能均勻地分布，特別是在sink點周圍。因此我們將這些瓶頸節(jié)點作為關(guān)鍵節(jié)點來優(yōu)化網(wǎng)絡(luò)生存期；

(3)可靠且節(jié)能的鏈路：不可靠的無線鏈路也會消耗能量，因為發(fā)送點必須在下一跳節(jié)點確認(rèn)之前發(fā)送多個相同數(shù)據(jù)包，所以這些節(jié)點很快將耗盡其能量。

因此，本文提出了節(jié)能路由層來解決以上問題。采用一種路由度量標(biāo)準(zhǔn)ELT(expected lifetime)，根據(jù)剩余能量，鏈路質(zhì)量來估計節(jié)點的預(yù)期使用壽命。并探討如何估計每個節(jié)點的ELT值，同時基于這種節(jié)點度量來設(shè)計路徑算法，從而全局地優(yōu)化網(wǎng)絡(luò)生命周期。

1 相關(guān)工作內(nèi)容

1.1 RPL路由協(xié)議

低功耗有損網(wǎng)絡(luò)路由協(xié)議(routing protocol for low power and lossy network，RPL)[4]，是一個距離矢量協(xié)議，它使用一個或多個路由度量標(biāo)準(zhǔn)構(gòu)造一個面向目標(biāo)的有向無環(huán)圖(destination oriented directed acyclic graph，DODAG)。DODAG的構(gòu)建是基于節(jié)點的等級，而目標(biāo)函數(shù)定義了如何使用路由度量來計算等級，此外，DODAG的構(gòu)建和維護(hù)都是通過所有節(jié)點周期性廣播DODAG的信息對象(DODAG information object，DIO)消息來保證。在DODAG中，目標(biāo)函數(shù)利用度量和約束條件信息選擇最優(yōu)轉(zhuǎn)發(fā)節(jié)點，構(gòu)建有向無環(huán)圖(directed acyclic graph，DAG)，通過選擇最優(yōu)父節(jié)點找到最佳的數(shù)據(jù)包傳輸路徑，降低能量消耗，提高網(wǎng)絡(luò)壽命。

1.2 WSN中能量感知路由

目前，基于能量消耗問題，主要有3種不同度量的RPL路由協(xié)議，分別是基于鏈接質(zhì)量、剩余能量以及其它機(jī)制。

1.2.1 基于鏈接質(zhì)量的標(biāo)準(zhǔn)

文獻(xiàn)[5]提出了評估射頻環(huán)境中的鏈路可靠性，定義預(yù)期發(fā)送次數(shù)(expected transmission count，ETX)，用來估計在正確確認(rèn)接收之前所需的發(fā)送次數(shù)。

計算式為

(1)

其中，Df表示一個數(shù)據(jù)包被鄰居節(jié)點收到的實測概率，Dr表示鄰居節(jié)點發(fā)來的ACK應(yīng)答包被接收的實測概率。在ETX的度量方式中，選擇父節(jié)點和默認(rèn)路由的時候考慮到了鏈路質(zhì)量的因素，相比簡單的將跳數(shù)作為路由度量標(biāo)準(zhǔn)，更加貼近低功耗有損網(wǎng)絡(luò)的實際特征。

但是，采用該標(biāo)準(zhǔn)將形成一個最小能量路徑，通過使用最小能量路徑來路由所有數(shù)據(jù)包，該路徑上的節(jié)點能量將快速耗盡，這樣做不會改善整個網(wǎng)絡(luò)的生命周期，并且產(chǎn)生的拓?fù)浣Y(jié)構(gòu)將不能進(jìn)行能量平衡。

如圖1(a)中的拓?fù)浣Y(jié)構(gòu)，其中路由DAG是基于ETX構(gòu)建的。E節(jié)點可以選擇B或C節(jié)點作為下一跳。C節(jié)點是最合適的選擇，因為它相對邊界路由器而言，ETX值最低。但是，如果所有節(jié)點都產(chǎn)生相同的數(shù)據(jù)流量，則應(yīng)優(yōu)先選B節(jié)點平衡能量消耗。

圖1 不同路由機(jī)制構(gòu)建的DODAG網(wǎng)絡(luò)

1.2.2 基于剩余能量的度量

為了提高網(wǎng)絡(luò)生命周期，節(jié)點應(yīng)該避免選擇具有低剩余能量的節(jié)點作為下一跳。文獻(xiàn)[6]提出了使用剩余能量度量的RPL，但是，他們一方面沒有考慮射頻鏈路質(zhì)量，另一方面，即使將剩余能量與ETX結(jié)合成一個加權(quán)函數(shù)，其中每一個的權(quán)重為0.5[7]。盡管如此，他們?nèi)圆荒茏R別能量最受約束的節(jié)點并使其壽命最長。

如圖1(b)所示的拓?fù)浣Y(jié)構(gòu)，其中路由DAG是基于剩余能量構(gòu)建的。節(jié)點G可以選擇節(jié)點F或節(jié)點C作為下一跳，因為節(jié)點F的剩余能量更大，所以它會選擇其作為父節(jié)點，即使相應(yīng)的鏈路質(zhì)量非常低(ETX=3)，但這將導(dǎo)致節(jié)點G重發(fā)次數(shù)增多，從而G節(jié)點的電池快速耗盡，所以C節(jié)點將是更合適的選擇。

1.2.3 其它機(jī)制

文獻(xiàn)[8]建議動態(tài)調(diào)整傳感器的傳輸功率以減少實時通信延遲。正常發(fā)送的數(shù)據(jù)包以較低的功率傳輸，可以降低能耗。但是，即使此解決方案具有高能效，也不會延長網(wǎng)絡(luò)的使用壽命。以及文獻(xiàn)[9]提到的利用節(jié)點剩余能量的損耗率，來避免節(jié)點能量的快速消耗，選擇下一跳節(jié)點時考慮剩余能量消耗的大小，實現(xiàn)能量的均衡消耗，避免某些節(jié)點的過早失效，但沒有考慮路徑的可用性，雖然消耗能量均衡但某些路徑傳輸質(zhì)量較差。

2 預(yù)期壽命

2.1 問題陳述

正如前面所示，在WSN分布式的方式中，并沒有對創(chuàng)建的一個路由拓?fù)溥M(jìn)行管理，使其網(wǎng)絡(luò)的生命周期達(dá)到最大化。因此，本文提出了一種路由度量標(biāo)準(zhǔn)，不僅考慮到鏈路的質(zhì)量，同時平衡該路徑上節(jié)點可用能量的負(fù)載，全局性地最大化網(wǎng)絡(luò)生存期[10]。這里所說的能量平衡是指花費相同能量構(gòu)建的路徑。

簡而言之，路由度量應(yīng)滿足以下屬性：

(1)動態(tài)捕獲鏈路質(zhì)量的變化；

(2)可靠性最大化；

(3)瓶頸的能量消耗最小化(即消耗能量最多的節(jié)點)。應(yīng)優(yōu)先平衡該部分能量以延長網(wǎng)絡(luò)壽命。

在本文中，我們提出了一種路由度量ELT，通過構(gòu)建能量平衡拓?fù)浣Y(jié)構(gòu)，使得全局網(wǎng)絡(luò)生命周期最大化。

2.2 ELT的估算方法

我們提出了預(yù)估壽命這種路由度量機(jī)制。節(jié)點N通過以下步驟進(jìn)行ELT值計算。相關(guān)符號見表1。

表1 文中符號定義

(1)估算節(jié)點N轉(zhuǎn)發(fā)的數(shù)據(jù)流量，包括自己產(chǎn)生的和子節(jié)點即將傳送過來的

(2)將N必須傳輸?shù)牧髁砍艘云涫走x父節(jié)點的平均重傳次數(shù) (ETX(N,PN))，需要的重傳次數(shù)越多，消耗的能量就越多

ELT(N)=Ttotal(N)×ETX(N,PN)

(3)通過考慮數(shù)據(jù)發(fā)送速率來計算占用率

(4)通過將占用率與其無線電的發(fā)射功率相乘來計算用于傳輸所有流量所消耗的能量

(5)最后，計算N的剩余壽命，將剩余能量與傳輸其流量所花費的能量之間的比率作為其值

(2)

我們將ELT與其它指標(biāo)進(jìn)行比較，可以看到該路由度量設(shè)法克服了其它的限制，如表2所示，它使用被動測量技術(shù)來估計鏈路質(zhì)量，并考慮到重傳次數(shù)和剩余能量以減少能量消耗。由于ETX減少了路徑上的重傳次數(shù)，因此間接地減少了延遲。通過在度量中使用ETX，也設(shè)法減少部分延遲。

表2 路由度量機(jī)制

3 基于RPL的ELT協(xié)議

本文的目標(biāo)是改善網(wǎng)絡(luò)壽命，因此，我們需要最大限度地減少最受限制節(jié)點(瓶頸)的能耗，也就是讓最受約束節(jié)點的生存期達(dá)到最大化。

為了在RPL梯度路由方案中實現(xiàn)這個最小路徑度量，主要需要以下幾步：

步驟1 計算瓶頸節(jié)點的ELT并沿著DIO中的路徑發(fā)送該信息；

步驟2 給出算法選擇最優(yōu)下一跳父節(jié)點；

步驟3 計算節(jié)點的Rank值且要避免網(wǎng)絡(luò)中出現(xiàn)回路。

3.1 瓶頸節(jié)點ELT

本文首先提出度量期望壽命，然后根據(jù)式(2)計算節(jié)點N的ELT。

假設(shè)當(dāng)節(jié)點N想要加入DODAG時，由于瓶頸節(jié)點最有可能成為第一個死亡節(jié)點，因此新節(jié)點必須估計自己的數(shù)據(jù)包對瓶頸節(jié)點壽命的影響。為了估計瓶頸節(jié)點B的ELT，節(jié)點N需要知道以下信息：

(1)節(jié)點B的剩余能量Eres(B)；

(2)考慮瓶頸節(jié)點到其父節(jié)點的重傳次數(shù)ETX(B,PB)，計算出瓶頸節(jié)點傳輸一位數(shù)據(jù)每秒消耗的能量

ETX(B,PB)×PTx(B)

(3)

(3)瓶頸節(jié)點處理的總流量

(4)

(4)瓶頸節(jié)點傳輸?shù)乃俾?(DATA_RATE)，然后，根據(jù)式(2)節(jié)點B可以估算出自己的生命周期

(5)

為了節(jié)省內(nèi)存和能量，我們需要壓縮信息，盡量減少在DIO中插入的字段信息數(shù)量。因此把式(5)拆分成以下兩個變量，分別是：

隨著通信技術(shù)的發(fā)展,常見的無線通信技術(shù)及其性能參數(shù)如表1所示,車輛檢測系統(tǒng)對無線通信方式的性能要求體現(xiàn)在兩個方面:傳輸速率和傳輸距離[8]。對比不同的無線通信方式可知WIFI技術(shù)在傳輸速度和通信距離面存在明顯的優(yōu)勢,故本文采用無線WIFI通信方式搭建無線傳感網(wǎng)絡(luò)。

1)瓶頸節(jié)點為下一跳準(zhǔn)確接收數(shù)據(jù)包所消耗的平均能量

(6)

2)由瓶頸節(jié)點轉(zhuǎn)發(fā)的現(xiàn)有流量

Ttotal(N)

(7)

通過平均能量和現(xiàn)有流量，可以讓新節(jié)點N準(zhǔn)確估計其數(shù)據(jù)流量對瓶頸節(jié)點B的影響

(8)

其中，Ttotal(N) 是新節(jié)點通過瓶頸節(jié)點B的路徑上所注入的數(shù)據(jù)流量，每次接收到DIO時，都會更新節(jié)點的ELT。因此，每個節(jié)點保持最新的信息。

3.2 首選父節(jié)點

在選擇自己父節(jié)點時，節(jié)點必須考慮自己的生命周期和瓶頸節(jié)點的壽命，以便估計哪個節(jié)點成為新的瓶頸節(jié)點。因此，我們提出路由算法來選擇最佳的父節(jié)點。對于每個可能的父節(jié)點，即一個小于自身Rank值的鄰居節(jié)點，節(jié)點N將：

(1)選擇此父節(jié)點時計算其生命周期(第(2)行)；

(2)用該節(jié)點注入新數(shù)據(jù)流量，計算更新該路徑上瓶頸節(jié)點的生存期(第(3)行)；

(3)保存兩者中的最小壽命(第(4)行)。

最后，選擇最小壽命里面最大的父節(jié)點作為首選父節(jié)點，然后計算路徑的新瓶頸節(jié)點的壽命并更新其DIO中的相應(yīng)信息。見表3。

表3 選擇最優(yōu)父節(jié)點

3.3 改進(jìn)節(jié)點Rank值計算

RPL并未指定如何計算DODAG中節(jié)點的等級，因為它取決于所使用的約束條件和路由度量。但是，又明確規(guī)定它必須嚴(yán)格單調(diào)遞減到邊界路由節(jié)點(sink)，以避免形成環(huán)路。由于預(yù)期壽命代表沿路徑的最小度量，因此其值不能用于計算Rank，這樣會使得子DODAG網(wǎng)絡(luò)中的所有節(jié)點都將具有相同的Rank值。

然而，節(jié)點可以通過向其首選父節(jié)點的Rank添加一個常數(shù)步長值和剩余能量來計算

Rank(N)=Rank(PN)+Rank_increase
Rank_increase=Step×MinHopRankIncrease+Eres(N)

(9)

其中，Step是一個標(biāo)量值，MinHopRankIncrease是RPL參數(shù)[12]，取值256。RPL禁止下一跳節(jié)點是一個Rank值比自身更大的鄰居節(jié)點，因此，我們要確保Rank值是單調(diào)的，保證無環(huán)路[13]。文中通過等級修復(fù)和最優(yōu)父節(jié)點的選擇，保持最長的網(wǎng)絡(luò)生命期，同時避免形成循環(huán)。

3.4 ELT構(gòu)建DAG

如圖2所示，A、B、C、D、E、F、G分別表示各個節(jié)點，其右下角表示ELT值，例如，節(jié)點A的ELT為80，節(jié)點B的ELT為40。圖中有兩條鏈路，分別是D→B→A和G→F→E→C→A且節(jié)點A為sink節(jié)點，B、C為瓶頸節(jié)點，因為B、C在其鏈路上的ELT值最小。圖中虛實線上的值表示ETX，即數(shù)據(jù)包成功發(fā)送所需要的次數(shù)，該值越小說明路徑上的鏈路質(zhì)量越好。假設(shè)傳輸一個數(shù)據(jù)包需要5個單位的ELT。

圖2 基于ELT的DAG構(gòu)建

在圖2中，節(jié)點G可以選擇節(jié)點D或F作為首選父節(jié)點，如果它選擇了瓶頸能量最大的ELT路徑，即選擇D→B→A，G節(jié)點的ELT值降為25，因為G和D節(jié)點之間的鏈路質(zhì)量很差(ETX=5)，所以它需要重傳很多次才能成功到達(dá)D節(jié)點，而節(jié)點B的ELT值降為35，根據(jù)首選父節(jié)點算法中Pathp(Bp)=min{eltN,eltB} 可得，它自身將成為新的瓶頸且Pathp(Bp)=min{eltG,eltB}=25。 另一方面，如果節(jié)點G選擇F節(jié)點作為首選父節(jié)點，G節(jié)點ELT值降為45，F(xiàn)節(jié)點的ELT降為42.5，C節(jié)點的ELT降為30，根據(jù)首選父節(jié)點算法可得，Pathp(Bp)=min{eltG,eltC}=30，它將對瓶頸節(jié)點C和其自身產(chǎn)生較小影響。所以，節(jié)點G將選擇節(jié)點F，因為它使網(wǎng)絡(luò)中所有節(jié)點之間最小的ELT得到最大化。

3.5 證明網(wǎng)絡(luò)壽命最大化

設(shè)N是無線傳感器網(wǎng)絡(luò)中的一個節(jié)點，必須在P和Q節(jié)點之間選擇其首選父節(jié)點，其中P節(jié)點提供最佳路徑(即最大的ELT)。分別設(shè)為ELT(Np) 和ELT(NQ)，如果P、Q節(jié)點分別是其首選父節(jié)點，則估計節(jié)點N的預(yù)期壽命。并做一個矛盾的證明。

P節(jié)點提供了最優(yōu)路徑，意味著在節(jié)點N選擇了它作為首選父節(jié)點后，通過P節(jié)點的新瓶頸節(jié)點的ELT大于通過Q節(jié)點的瓶頸節(jié)點。由于通過P節(jié)點的瓶頸可能是P(Bp) 或N(如果其ELT小于ELT(Bp))，我們可以區(qū)分兩種情況：

(1)new_BP=BP?

ELT(BP)>ELT(BQ)&ELT(BP)>ELT(NQ)

(10)

(2)new_Bp=N?

ELT(NP)>ELT(BQ)&ELT(NP)>ELT(NQ)

(11)

假設(shè)現(xiàn)在不是選擇最佳路徑，而是選擇通過Q節(jié)點的路徑。這意味著

ELT(new_BQ)>ELT(BP)&ELT(new_BQ)>ELT(NP)

我們可以區(qū)分兩種情況：

(1)new_BQ=BQ?

ELT(BQ)>ELT(BP)&ELT(BQ)>ELT(NP)

(12)

(2)new_BQ=N?

ELT(NQ)>ELT(BP)&ELT(NQ)>ELT(NP)

(13)

可以看到這兩種情況都是矛盾的，所以一個節(jié)點將始終選擇最優(yōu)化的父節(jié)點，以最大限度地延長網(wǎng)絡(luò)的瓶頸和時間。

4 仿真結(jié)果及分析

為了對ELT路由度量算法做出一個合理的評價，本文采用仿真器Contiki建立仿真平臺，使用Cooja[14]仿真工具進(jìn)行了仿真實驗，網(wǎng)絡(luò)中的所有節(jié)點分別使用ELT、ETX和剩余能量3種度量方式，其余的環(huán)境和參數(shù)都不發(fā)生變化。采用802.15.4 MAC層協(xié)議，在物理層使用路徑衰落陰影模型，傳輸率RateData=1 pkt /min。仿真區(qū)域設(shè)定為300m×300m，節(jié)點數(shù)分別30、50、70、90且隨機(jī)分布，仿真時間1小時，每次仿真重復(fù)20次，取其平均值作為最終的仿真結(jié)果。如表4所示，并通過以下幾個方面進(jìn)行比較。

表4 仿真參數(shù)

(1)數(shù)據(jù)包傳輸率

3個不同度量標(biāo)準(zhǔn)的RPL的數(shù)據(jù)包傳輸率曲線如圖3所示。

圖3 數(shù)據(jù)包傳輸率

從圖3可知，數(shù)據(jù)包的傳輸率隨著節(jié)點數(shù)增加而增加。ETX的數(shù)據(jù)包傳輸率最高，因為ETX方案只考慮鏈路質(zhì)量為度量標(biāo)準(zhǔn)，而提出的ELT方案的數(shù)據(jù)包傳輸率逼近于ETX方案。此外，剩余能量方案的數(shù)據(jù)包傳輸率最低，它傾向于以節(jié)能的方式對節(jié)點進(jìn)行特殊優(yōu)化，而不考慮鏈路質(zhì)量，會導(dǎo)致選擇錯誤的鏈路來轉(zhuǎn)發(fā)數(shù)據(jù)包，導(dǎo)致更多的數(shù)據(jù)包傳輸率下降。

(2)網(wǎng)絡(luò)壽命

根據(jù)式(2)，繪制了節(jié)點的網(wǎng)絡(luò)壽命，即網(wǎng)絡(luò)中第一個節(jié)點能量耗盡的時間。最初，能量相同為10 J，保持同樣的仿真區(qū)域，并增加了節(jié)點數(shù)量，當(dāng)網(wǎng)絡(luò)變得更密集時，由于瓶頸節(jié)點將不得不轉(zhuǎn)發(fā)更多的數(shù)據(jù)包，所以網(wǎng)絡(luò)壽命會減少。

從圖4中可以看出ELT的壽命仍然優(yōu)于ETX和剩余能量，與ETX相比，ELT使網(wǎng)絡(luò)生命周期增加一倍。ETX擁有比剩余能量更好的生命周期，因為它選擇了不需要重傳很多次的高質(zhì)量鏈路。

圖4 網(wǎng)絡(luò)壽命

(3)能量消耗

圖5繪制了能量消耗隨離sink節(jié)點距離的變化情況。從圖5可知，剩余能量的平均能量消耗最少，但是這是以低的PDR為代價的，PDR越低，傳輸?shù)臄?shù)據(jù)包數(shù)量越少，相應(yīng)地，消耗的能量越少。

圖5 能量消耗

與ETX協(xié)議相比，ELT的能量消耗更小。此外，ELT設(shè)法平衡所有節(jié)點的能量消耗，無論距邊界路由器的距離如何，平均消耗在60 J左右，這也表明了ELT基本實現(xiàn)了我們的能量平衡目標(biāo)。

5 結(jié)束語

基于網(wǎng)絡(luò)壽命，本文設(shè)計了一個路由度量標(biāo)準(zhǔn)ELT來構(gòu)建DAG，通過選擇最優(yōu)父節(jié)點達(dá)到能量平衡負(fù)載，以延長網(wǎng)絡(luò)生命周期。仿真結(jié)果表明，通過使用ELT度量，RPL協(xié)議在數(shù)據(jù)包傳輸率方面，其性能接近ETX，但是，在網(wǎng)絡(luò)壽命方面是ETX的兩倍，在能量消耗方面也實現(xiàn)了一個很好的均衡。后期將對瓶頸節(jié)點再預(yù)估進(jìn)一步研究，盡量避免后續(xù)節(jié)點誤選瓶頸節(jié)點的情況。