基于剩余級別負載均衡的RPL路由協議

馮馨于,仇英輝

(華北電力大學電氣與電子工程學院,北京 102206)

低功耗有損網絡[1]LLNs(Low Power and Lossy Networks),一種比較特殊的無線傳感器網絡。由于構成該網絡的嵌入式設備在功率、存儲空間、處理能力等資源方面受到制約,容易造成數據在網絡傳輸過程中的丟失。為了設計適用于 LLNs的路由協議,IETF(Internet Engineering Task Force)的ROLL(Routing Over Low power and Lossy)工作組提出了一種針對LLNs的路由協議RPL[2](Routing Protocol for Low-Power and Lossy Networks)。RPL路由協議對節點能量受限、鏈路不穩定等網絡有較強的適應能力,因此有十分廣闊的應用前景。

目前,國內外學者針對RPL的研究主要集中在能量均衡、負載均衡等方面。能量均衡方面,文獻[3]提出了一種基于三角模算子的 RPL 協議路由優化算法,基于三角模融合算法,重新定義了網絡節點的能量指標和邏輯距離隸屬度并進行了融合,更為合理地進行父節點選定,降低了能量損耗。在負載均衡方面,文獻[4]提出了一種基于普通節點負載均衡的RPL路由協議OLB-RPL,采用劃分能量級別和改變通信半徑兩重負載均衡辦法。但是文章對能量級別的劃分不夠靈活,這樣在負載均衡進行到一定程度的時候無法繼續進行負載均衡。為了更好地實現負載均衡,本文提出了一種基于剩余級別進行負載均衡的RPL路由協議的優化算法WLB-RPL。

1 RPL路由協議

RPL是規定在IPV6無線傳感器網絡WSN(Wireless Sensor Networks)中的一種距離路由矢量協議。RPL的核心思想是通過建立面向根節點的有向無環圖DODAG(Destination Oriented Directed Acyclic Graph),最終實現網絡中每一個節點都有一條到達根節點的路徑,進而完成整個網絡的路由拓撲圖[5-6]。在這一過程中,RPL是通過使用目標函數和路由度量約束條件來完成DODAG構建的。

1.1 RPL路由過程

1.1.1 RPL控制消息

在RPL路由協議的整個組網過程中,DODAG拓撲的構建依靠RPL控制消息的交互。RPL嚴格的遵從IPV6架構,主要使用3種控制消息,分別是DIO,DAO,DIS。

①DODA信息對象DIO(DODAG Information Objection):是DODAG向下路徑中的消息,主要包含節點所在DODAG相關的信息,比如DODAGID,Rank值等。

②DODAG目的廣播對象DAO(Destination Advertisement Object):沿DODAG向上傳播目的地信息通告。

③DODAG請求信息DIS(DODAG Information Solicitation):節點未收到DIO消息時,可以向周圍節點廣播DIS,用來請求DIO消息。

1.1.2 DODAG構建過程

DODAG的構建過程基于鄰居發現機制,步驟具體如下:

①DODAG根節點廣播DIO消息;

②節點A、B收到來自根節點的DIO消息,包括DODAGID、Rank值、目標函數等信息,節點據此判斷是否加入該DODAG。如果節點決定加入該DODAG,就將帶有自身路由前綴信息的DAO消息回復給根節點。節點B在決定加入DODAG之后,更新自己的Rank值并繼續周期性的廣播DIO消息。

③同理,節點C在收到來自節點B的DIO消息之后,判斷是否加入該DODAG,若加入,則回復給父節點B一個DAO消息。

④節點B收到來自節點C的路由前綴信息DAO后,節點B也重復這一步驟,傳回到根節點。

⑤假設節點D一直沒有收到來自DODAG中的DIO消息,節點D可以主動給節點A發送一個DIS請求信息,請求加入DODAG。

⑥節點A發送DIO消息給節點D。

⑦節點將整合之后的路由前綴信息(包括自己及子節點的信息)傳給父節點,該父節點再傳給其父節點,節點反復重復這一步驟,直到根節點已經獲得整個DODAG的前綴信息。至此,DODAG構建完成。

1.1.3 路由構建過程

①向上路由:由葉子節點向根節點的數據傳輸過程。

②向下路由:由根節點向葉子節點的數據傳輸過程。向下路由按照實際情況可以分為非存儲模式和存儲模式。

(a)非存儲模式:所有的前綴信息由DODAG根節點保存,普通節點不保存任何子節點的前綴信息。例如圖1中的C,傳送DAO消息直到到達根節點。需要向下路由時,需要從根節點處查詢到目的節點的轉發路徑。

圖1 DODAG構建過程

(b)存儲模式:節點保存其子節點的前綴信息。在構建向下路由的時候,只需要查找路由表,匹配子節點的前綴信息即可。父節點在收到子節點的DAO消息后,會將DAO消息中的地址信息存儲在路由表中,整合之后傳給根節點。據此,根節點和每個路由節點均知道通往子孫節點的下一跳信息。需要向下路由時直接查詢路由表項即可。

1.2 RPL的路由策略

RPL的路由策略,取決于RPL關于目標函數OF(Objection Function)的定義。在同一個RPL實例中,必須使用同一個于目標函數。OF定義了怎么選取最佳父節點,怎么確定每個節點的Rank值以及根據哪一種路由度量和約束條件進行路徑的選擇。值得注意的是,OF表明了應該采用哪一種路由選取策略。此外,OF本身是多個函數的集合體,而不是指某一個單一的函數。不同的目標函數對應不同的應用場景。

1.2.1 RPL的路由度量和約束條件

無線傳感器網絡WSN(Wireless Sensor Network)不同于傳統的網絡以及ad hoc網絡,據此,RPL在進行路徑計算的時候采用的是特殊的度量和路由約束條件。

WSN中存在多種路由度量[7],主要分類如表1所示。

節點度量包括節點狀態和屬性、節點能量及節點跳數。節點能量描述的是和節點能量相關的信息,比如剩余能量所占百分比的估值以及供電模式(電源供電還是電池供電等)。

鏈路度量則包括節點的吞吐量、時延、可靠性等。

表1 不同的路由度量

在構建DODAG的時候,不同的應用場景要求不同的路由選擇標準。例如在對網絡生存時間要求較高或者能量極度受限的情況下,節點選擇最佳路由的標準是剩余能量。

1.2.2 目標函數的實施

父節點的選取是目標函數的重要任務之一。任何可能會引起下一跳信息更新的事件比如父節點失效、定時器過期等,都會引發目標函數進行父節點的選擇。

而Rank值也取決于目標函數。節點Rank值的計算方法如下面公式所示:

newRank=Rank+RankIncrease

(1)

newRank表示節點的新Rank值,Rank表示候選節點的Rank值,RankIncrease表示路由度量的增量值,即節點到候選父節點的相對位置的值。RankIncrease的具體數值取決于目標函數。

典型的目標函數如表2所示,主要包括OF0[8]、MRHOF[9]以及 ETXOF這3種。

表2 幾種典型的目標函數

2 基于剩余級別進行負載均衡的RPL路由協議

目前提到的諸多RPL路由協議在一定程度上延長了網絡壽命,但仍存在諸多能量消耗不均勻,負載不均衡等問題。文獻[3]中提到的OLB-RPL引入剩余能量級別,以尋找最優傳感器網絡鄰居節點范圍為路由算法來實現RPL網絡中普通節點的負載均衡。當負載數大于設置的對應閾值的時候,采取的辦法是調整當前節點的通信半徑(縮小通信半徑)。因為能量的消耗,節點剩余能量級別會越來越小,對應的閾值也會相應的減小,所以在節點輪數更新的時候,會及時調整通信半徑減少負載數來達到相應的負載均衡的效果。但是隨著輪數的增加,剩余能量級別的下降趨勢會趨于穩定,不利于負載均衡的繼續進行。本文提出統計節點當前剩余能量的分布情況,然后對能級密集分布的節點進行更細的能量分級,以期達到更好的負載均衡。

2.1 參考度量

文獻[3]RPL路徑選擇的主要依據是節點鄰居距離di以及節點剩余能量級別REL,然而在考慮到節點能耗問題時應該考慮到節點的總能耗會隨著鄰居節點距離的增大而增大,所以定義了新的參考度量:節點剩余級別RL,在考慮節點的剩余能量的同時也考慮到了鄰居節點的平均距離,通過加權來完善這一參考度量。

2.1.1 節點鄰居距離

在網絡初始時刻,設每個節點的通信半徑為R0,也就是每個節點的功率發送的半徑范圍。每個節點都有自己的鄰居節點集,對節點i而言,鄰居節點集是指處于自己通信半徑范圍之內的節點的集合。通過測試信號i來記錄各鄰居節點到該節點的距離,該距離即為節點鄰居距離d(i)neighbor:

d(i)neighbor=Dist(nodei,nodeineighbork)

(2)

式中:k表示第k個鄰居節點。

2.1.2 剩余級別RL

本文引入剩余級別RL,通過對節點的的當前剩余能量以及節點之間的平均距離進行加權[10-14]來綜合考慮能耗。另外,文章設置了每個能級RL對應的負載數目閾值Fi來實現負載均衡,即剩余能量少且平均鄰居距離大的節點對應的負載少一點,剩余能量多且平均距離小的節點對應的負載相對多一點。剩余級別定義如下:

(3)

式中:Eicur(r)表示每個節點i的當前剩余能量,Eaverage表示每個等級的能量,其定義為:

Eaverage=E0/m

(4)

式中:E0表示節點最初能量,m表示節點有m個能量級別,D為到鄰居節點的平均距離,其定義為:

(5)

式中:d(i)neighbor為節點鄰居距離,n為周圍鄰居節點的總數。

(6)

式中:α是自適應調節因子,β為能量調節因子。隨著采集輪數r的逐漸增加,節點當前剩余能量Eiour(r)逐漸減小。與此對應的是,β在區間[0,1]內逐漸減小,而a在區間[1/2,1]呈現逐漸增大的趨勢。這樣隨著信息采集輪數的增多,a的逐漸增大,剩余能量這一權值因子在剩余級別中所占的比例會越來越大,以保證剩級別這一參數的合理性。

圖2 流程圖

2.2 WLB-RPL路由協議

圖2為改進之后的動態的m的流程圖。

步驟如下:

S1 初始化,設置節點初始半徑。發送測試信號,統計鄰居節點及節點鄰居距離di;

S2 對每個節點進行能級劃分,設每個節點有m個能量級別,取m=10;

S3 統計每個節點的當前剩余能量,記為Ei_cur;

S4 找出最多節點數的能級,記為n;

S5 統計該能級以及該能級前后的能級,即能級數分別為n,n+1,n-1這3個能級的節點總數,若節點總數沒有占到當前存活節點總數的一半以上,如下公式所示。

(7)

則每個節點各自計算自己的剩余級別RLi_cur,并確認當前剩余能量級別RELi_cur所對應的負載門限Fi。統計自己所攜帶的負載數fi,判斷Fi是否小于fi;

S6 若Fi小于fi,則對當前通信半徑進行調整,減少通信半徑。通信半徑調整策略描述如下:

設某一時刻節點i的通信半徑為Ri,調整后的通信半徑為Ri+1,起初節點i通信半徑范圍覆蓋的子節點有節點1～n,當檢測到負載門限Fi小于攜帶負載數fi時,計算通信半徑的調整值Δ:

Δ=(d1+d2+d3+…+dn)/n

(8)

則新的通信半徑為

Ri+1=Ri-Δ

(9)

顯然,Ri+1

若Fi大于fi,則保持通信半徑不變,不必進行接下來的負載均衡機制。

S7 若這3個能級的節點總數占到了當前存活節點總數的一半以上,如下公式所示。

(10)

則對位于這3個能級的節點進行更細的節點能量分級(取m=20),負載均衡機制參考S5,S6。

3 仿真實驗結果

本文對算法性能進行了評估,通過與RPL相比較,驗證了WLB-RPL在數據采集輪數下的網絡總能耗、網絡死亡節點數等方面的性能。

本文通過MATLAB仿真平臺進行仿真實驗,在實驗中設置了250個網絡節點,隨機分布在100×100的區域內。把區域劃分成兩個DODAG,并手動選取區域內橫縱坐標最小的節點作為DODAG分區內各自的Sink節點。Sink節點的初始能量設置為1.0,普通節點的能量則設置為0.45～1.0之間的隨機值。

表3 仿真參數設置

仿真參數的設置能夠根據網絡大小等具體情況來實現靈活地配置,但也應該擬合實際系統的通信的需求。因此,仍需要增加以下假設:①當節點剩余能量小于5%時,即認為節點失效死亡。②仿真中RPL和WLB-RPL的更新周期都是96,但WLB-RPL也是實時更新的,每50輪更新一次。③發送信息能耗采用的能量模型是E=δ·d3,δ取值為δ=0.000 1(1/253)。

負載均衡的主要指標有網絡總能耗以及網絡死亡節點數目。網絡總能耗可以直觀反映節點能量消耗的平均情況。由于負載過重的節點容易提前死亡,所以網絡節點死亡數目可以體現網絡的通信負載均衡性能。

為了驗證WLB-RPL性能的優越性,本文分別比較了RPL和WLB-RPL在一定數據采集輪數下的網絡死亡節點數和網絡總能耗。

圖3 網絡平均能耗對比圖

WLB-RPL和RPL的網絡平均能量消耗對比圖如圖3所示。由圖3可知改進的算法能量消耗更加均衡,各個階段的能量消耗都少于RPL算法。網絡初始化階段,由于RPL和WLB-RPL使用相同的路由建立過程,因此初始能耗一致。隨著采集輪數的增加,RPL的網絡總能耗穩步增加,而WLB-RPL出現了一段驟降。本文的WLB-RPL算法中網絡的拓撲更新周期是50,即每50輪重新進行一次動態路由選擇。依據算法的原理,網絡中的節點負載數超過能級對應的閾值時,節點通過調整通信半徑的方法把自己的負載數調整到閾值范圍內,網絡得到均衡優化,這就是出現驟降的原因;隨著時間的推移,能耗逐漸增加,直至最后達到動態平衡。

圖4呈現的是數據采集輪數和網絡死亡節點數目的關系。由圖4可得,RPL最早出現死亡節點數出現在105輪,而WLB-RPL的死亡節點數最早出現在227 輪,比未改進的RPL延遲了122輪;而同一輪內的死亡節點數也明顯減少,相比RPL平均減少39.6%的死亡節點。從縱向的角度觀察可得出,在橫坐標相同的時候,即同樣的數據采集輪數下,WLB-RPL的網絡死亡節點數也少的多。由此證明達到了網絡負載均衡的效果。

圖4 網絡節點死亡數對比圖

從橫向的角度觀察可得出,當網絡的死亡節點數達到同樣的水平時,WLB-RPL所完成的數據采集輪數遠遠大于RPL協議。從這個角度來說,該算法大大提高了網絡的生命周期。同時,當死亡節點數分別為50,100,150的時候,WLB-RPL相對RPL算法的數據采集輪數提高的比例分別是49.27%,33.89%,41.79%。總之,可見本算法有效提升了網絡的生命周期,延長了節點平均壽命,保證了系統的經濟性和環保性。

4 結論

本文針對低功耗有損網絡的特點,在原有負載均衡的基礎上,提出了一種基于加權的WLB-RPL路由協議,降低了網絡能耗,實現了更好的負載均衡。本文提出的算法針對能級降到一定程度無法繼續進行負載均衡的情況,對于能級分布過于密集的節點采用更細的能級劃分,并提出了關于能級的新的加權的函數,更好的完善了負載均衡機制。仿真實驗表明,算法有效均衡了網絡負載,降低了能量損耗,延長了網絡生命周期。

參考文獻:

[1] Kulau U,Müller S,Schildt S,et al. Energy Efficiency Impact of Transient Node Failures when Using RPL[C]//IEEE,International Symposium on A World of Wireless,Mobile and Multimedia Networks. IEEE,2017:1-6.

[2] Tahir Y,Yang S,Mccann J A. BRPL:Backpressure RPL for High-Throughput and Mobile IoTs[J]. IEEE Transactions on Mobile Computing,2017,PP(99):1-1.

[3] 仇英輝,何霖. 基于三角模算子的RPL協議路由優化算法[J]. 傳感技術學報,2015,28(12):1861-1866.

[4] 仇英輝,陳玲. 基于普通節點負載均衡的RPL路由協議[J]. 傳感技術學報,2016,29(7):1077-1082.

[5] 楊及開. 無線傳感器網絡中的RPL路由協議研究[D]. 重慶:重慶郵電大學,2016.

[6] 高筱菲. 基于RPL的無線傳感器網絡分簇路由研究與實現[D]. 北京:北京交通大學,2014.

[7] 周蘭. IPv6無線傳感網網絡層協議研究[D]. 南京:南京郵電大學,2013.

[8] Thubert P. Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks(RPL)[J]. 2012,rfc 6552.

[9] Gnawali O. The Minimum Rank with Hysteresis Objective Function The[J]. RFC 6719(Proposed Standard,2012.).

[10] 張祎江,余金森,郝平. 基于線性參數加權評估機制的無線傳感器網絡節點定位[J]. 計算機工程,2017,43(2):156-162.

[11] 周蘭. IPv6無線傳感網網絡層協議研究[D]. 南京:南京郵電大學,2013.

[12] 胥楚貴,鄧曉衡,鄒豪杰. 無線傳感器網絡通信半徑動態調整的能耗均衡策略[J]. 傳感技術學報,2009,22(5):712-716.

[13] 朱光輝,張修如,劉衛彪. 無線傳感器網絡中能量有效的加權分簇算法[J]. 傳感器世界,2007,26(4):102-105.

[14] 陳海坤. 基于通信半徑動態調整的無線傳感器網絡密鑰管理方案[D]. 哈爾濱:哈爾濱工業大學,2007.