改進的基于網絡壽命的RPL路由協議

嚴利民，張 健，王 峰

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

0 引 言

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

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

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

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

因此，本文提出了節能路由層來解決以上問題。采用一種路由度量標準ELT(expected lifetime)，根據剩余能量，鏈路質量來估計節點的預期使用壽命。并探討如何估計每個節點的ELT值，同時基于這種節點度量來設計路徑算法，從而全局地優化網絡生命周期。

1 相關工作內容

1.1 RPL路由協議

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

1.2 WSN中能量感知路由

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

1.2.1 基于鏈接質量的標準

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

計算式為

(1)

其中，Df表示一個數據包被鄰居節點收到的實測概率，Dr表示鄰居節點發來的ACK應答包被接收的實測概率。在ETX的度量方式中，選擇父節點和默認路由的時候考慮到了鏈路質量的因素，相比簡單的將跳數作為路由度量標準，更加貼近低功耗有損網絡的實際特征。

但是，采用該標準將形成一個最小能量路徑，通過使用最小能量路徑來路由所有數據包，該路徑上的節點能量將快速耗盡，這樣做不會改善整個網絡的生命周期，并且產生的拓撲結構將不能進行能量平衡。

如圖1(a)中的拓撲結構，其中路由DAG是基于ETX構建的。E節點可以選擇B或C節點作為下一跳。C節點是最合適的選擇，因為它相對邊界路由器而言，ETX值最低。但是，如果所有節點都產生相同的數據流量，則應優先選B節點平衡能量消耗。

圖1 不同路由機制構建的DODAG網絡

1.2.2 基于剩余能量的度量

為了提高網絡生命周期，節點應該避免選擇具有低剩余能量的節點作為下一跳。文獻[6]提出了使用剩余能量度量的RPL，但是，他們一方面沒有考慮射頻鏈路質量，另一方面，即使將剩余能量與ETX結合成一個加權函數，其中每一個的權重為0.5[7]。盡管如此，他們仍不能識別能量最受約束的節點并使其壽命最長。

如圖1(b)所示的拓撲結構，其中路由DAG是基于剩余能量構建的。節點G可以選擇節點F或節點C作為下一跳，因為節點F的剩余能量更大，所以它會選擇其作為父節點，即使相應的鏈路質量非常低(ETX=3)，但這將導致節點G重發次數增多，從而G節點的電池快速耗盡，所以C節點將是更合適的選擇。

1.2.3 其它機制

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

2 預期壽命

2.1 問題陳述

正如前面所示，在WSN分布式的方式中，并沒有對創建的一個路由拓撲進行管理，使其網絡的生命周期達到最大化。因此，本文提出了一種路由度量標準，不僅考慮到鏈路的質量，同時平衡該路徑上節點可用能量的負載，全局性地最大化網絡生存期[10]。這里所說的能量平衡是指花費相同能量構建的路徑。

簡而言之，路由度量應滿足以下屬性：

(1)動態捕獲鏈路質量的變化；

(2)可靠性最大化；

(3)瓶頸的能量消耗最小化(即消耗能量最多的節點)。應優先平衡該部分能量以延長網絡壽命。

在本文中，我們提出了一種路由度量ELT，通過構建能量平衡拓撲結構，使得全局網絡生命周期最大化。

2.2 ELT的估算方法

我們提出了預估壽命這種路由度量機制。節點N通過以下步驟進行ELT值計算。相關符號見表1。

表1 文中符號定義

(1)估算節點N轉發的數據流量，包括自己產生的和子節點即將傳送過來的

(2)將N必須傳輸的流量乘以其首選父節點的平均重傳次數 (ETX(N,PN))，需要的重傳次數越多，消耗的能量就越多

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

(3)通過考慮數據發送速率來計算占用率

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

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

(2)

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

表2 路由度量機制

3 基于RPL的ELT協議

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

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

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

步驟2 給出算法選擇最優下一跳父節點；

步驟3 計算節點的Rank值且要避免網絡中出現回路。

3.1 瓶頸節點ELT

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

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

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

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

ETX(B,PB)×PTx(B)

(3)

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

(4)

(4)瓶頸節點傳輸的速率 (DATA_RATE)，然后，根據式(2)節點B可以估算出自己的生命周期

(5)

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

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

1)瓶頸節點為下一跳準確接收數據包所消耗的平均能量

(6)

2)由瓶頸節點轉發的現有流量

Ttotal(N)

(7)

通過平均能量和現有流量，可以讓新節點N準確估計其數據流量對瓶頸節點B的影響

(8)

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

3.2 首選父節點

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

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

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

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

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

表3 選擇最優父節點

3.3 改進節點Rank值計算

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

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

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

(9)

其中，Step是一個標量值，MinHopRankIncrease是RPL參數[12]，取值256。RPL禁止下一跳節點是一個Rank值比自身更大的鄰居節點，因此，我們要確保Rank值是單調的，保證無環路[13]。文中通過等級修復和最優父節點的選擇，保持最長的網絡生命期，同時避免形成循環。

3.4 ELT構建DAG

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

圖2 基于ELT的DAG構建

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

3.5 證明網絡壽命最大化

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

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

(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)

假設現在不是選擇最佳路徑，而是選擇通過Q節點的路徑。這意味著

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

我們可以區分兩種情況：

(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)

可以看到這兩種情況都是矛盾的，所以一個節點將始終選擇最優化的父節點，以最大限度地延長網絡的瓶頸和時間。

4 仿真結果及分析

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

表4 仿真參數

(1)數據包傳輸率

3個不同度量標準的RPL的數據包傳輸率曲線如圖3所示。

圖3 數據包傳輸率

從圖3可知，數據包的傳輸率隨著節點數增加而增加。ETX的數據包傳輸率最高，因為ETX方案只考慮鏈路質量為度量標準，而提出的ELT方案的數據包傳輸率逼近于ETX方案。此外，剩余能量方案的數據包傳輸率最低，它傾向于以節能的方式對節點進行特殊優化，而不考慮鏈路質量，會導致選擇錯誤的鏈路來轉發數據包，導致更多的數據包傳輸率下降。

(2)網絡壽命

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

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

圖4 網絡壽命

(3)能量消耗

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

圖5 能量消耗

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

5 結束語

基于網絡壽命，本文設計了一個路由度量標準ELT來構建DAG，通過選擇最優父節點達到能量平衡負載，以延長網絡生命周期。仿真結果表明，通過使用ELT度量，RPL協議在數據包傳輸率方面，其性能接近ETX，但是，在網絡壽命方面是ETX的兩倍，在能量消耗方面也實現了一個很好的均衡。后期將對瓶頸節點再預估進一步研究，盡量避免后續節點誤選瓶頸節點的情況。