基于擁塞感知的多路徑RPL路由協議

郭戈

摘 要：基于6LoWPAN標準的RPL協議實現了低功耗有損網絡上運行IPv6協議的節點間路由功能，但是現有的RPL協議并未包含擁塞避免機制。文中提出一種擁塞感知負載均衡多徑RPL協議，將緩沖區占用率引入RPL協議，實現擁塞感知，并采用多徑傳輸的方式進行負載均衡。仿真結果表明，協議達到了提高數據傳輸成功率、平衡節點能量消耗的目的。

關鍵詞：低功耗有損網絡；RPL路由協議；負載均衡；擁塞避免

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2018）09-00-04

0 引 言

物聯網技術是新一代信息革命的核心技術之一，它基于低功耗有損網絡（Low Power and Lossy Networks，LLNs）實現物與物的通信，能夠極大地拓展人類感知與控制的范圍。低功耗有損網絡由許多能量與計算能力有限的節點組成，節點間通過低速、不穩定的無線或有線網絡進行連接。由于IP協議對內存與帶寬的需求較高，以往被認為不適合直接在低功耗有損網絡上使用，需要ZigBee等專有協議通過復雜的應用網關轉換，才能實現低功耗有損網絡節點接入互聯網的功能。但6LoWPAN[1]標準的制定改變了這種狀況，它基于IEEE 802.15.4[2]運行輕量級IPv6協議棧，實現了低功耗有損網絡節點無縫接入下一代互聯網的目標，為物聯網的大規模應用奠定了堅實的基礎。

由于傳統的路由協議都不適合低功耗有損網絡，IETF的ROLL工作組制定了RPL[3]協議，以滿足低功耗、低速率、鏈路動態變化等低功耗有損網絡的路由需求。RPL是一種距離向量協議，以一個Sink節點為根，通過某種目標函數（Object Function，OF）把網絡中的節點組織到一個或多個有向無環圖（Destination Oriented Directed Acyclic Graph，DODAG）中，從而實現節點間數據的傳輸。DODAG以類似樹結構的形式進行構造，在一組鄰居節點中選擇一個作為其最優父節點（preferred parent），并將其設為默認路由，把數據傳給根Sink或者其他節點。

但是RPL協議標準并未包含擁塞避免機制。當某個節點數據包到達的速度超過其轉發出去的速度時，便會產生擁塞。在使用RPL協議構建的網絡中，擁塞多發生于兩處節點。一處是距離Sink節點較近的節點，這是由于RPL協議采用類似樹形的結構構建DODAG，因此靠近根的節點有最多的數據轉發量；另一處是臨近事件突發處的節點，由于需要轉發大量檢測到的突發事件信息而產生擁塞。嚴重的擁塞會導致大量數據包的丟失與重傳，節點的能量被浪費，網絡的生存時間會因此而縮短。

此外，由于DODAG中每個非根節點只選擇一個最優父節點將其作為發往Sink節點數據的唯一途徑，因此會導致子節點較多的節點承擔更大的數據轉發壓力。這種負載不均衡的狀況使得某些節點因為能量消耗過大而過早死亡，可能造成網絡空洞甚至網絡分區。

為此，本文提出一種RPL改進算法，即擁塞感知負載均衡多徑RPL（Congestion Awareness Load Balanced Multipath RPL，CALBM-RPL）協議。該算法將緩沖區占用率引入RPL協議，實現擁塞感知，并采用多徑傳輸的方式進行負載均衡，從而達到提高數據傳輸成功率（Packet Delivery Ratio，PDR）、平衡節點能量消耗的目的。

1 RPL概述

RPL協議包含用來與其他網絡相連接的根節點（Sink節點）、用以將數據轉發給根節點的中間節點以及葉子節點。RPL可對網絡變化做出快速反應，能在通往根節點的缺省路徑無法連通時選取一條替代路徑。

RPL使用基于ICMPv6的DIO（DODAG Information Object，DIO），DIS（DODAG Information Solicitation，DIS）及DAO（Destination Advertisement Object，DAO）三種控制消息實現DODAG的構建。DODAG根節點首先使用DIO控制消息向周圍鄰居進行廣播，宣布自己作為父節點。其他節點收到廣播后，會根據其中包含的信息計算自身的rank值，產生新的DIO消息繼續向外廣播。節點在收到多個DIO消息時，會使用相應的OF進行計算比較，選擇結果值最小的節點作為自己的最優父節點，并根據該節點的rank和到達的路徑開銷得到自身的rank值。這一過程持續進行，最終將網絡中所有可達節點包含進DODAG中，每個加入的節點便擁有了送往Sink的上行路徑。

為了獲得自Sink節點至其他節點的下行路徑，每個節點在選擇出最優父節點后，向最優父節點發送DAO控制消息。收到DAO控制消息后，父節點將該子節點加入到路由表（存儲模式）或包含在下一個DAO消息中（非存儲模式），并把新生成的DAO消息繼續向上傳遞，直至Sink節點。

如果某個節點在一段時間內未收到DIO消息，那么廣播一個DIS消息以請求加入DODAG。收到該消息的鄰居節點會重置DIO時鐘以加快DIO消息的發送頻率。為了節省重復發送DIO消息的能量消耗，RPL使用涓流時鐘（Trickle Timer）控制DIO的發送頻率。每收到一個顯示網絡狀態穩定的DIO，該時鐘就以幾乎加倍的數量延長定時時長，以降低發送頻率，減少發送DIO包數量。而一旦發現網絡狀態發生改變，如最優父節點的rank值改變或與其失聯，則該時鐘會重置為最小值，提高DIO的發送頻率，使網絡盡快收斂。

2 相關工作

文獻[4]提出一種通過均衡負載延長網絡生命周期的多徑路由機制。在該機制中，網絡被劃分成多個區域。Sink節點向所有其他節點發送區域的信息，每個節點收到后都會根據自己的位置加入一個區域，并把自己的剩余能量和流量情況發送給Sink節點。Sink節點計算每個區域的剩余能量后，通知信息源節點沿著最少被使用（即剩余能量最多）的多個區域發送數據。這種多徑傳輸的機制實現了流量和能量的均衡。

文獻[5]提出一種負載均衡RPL（LB-RPL）協議，用以解決RPL中由于緩沖區有限導致的丟包問題。當一個節點檢測到網絡負載增大，緩沖區占有率超過門限值后，便暫緩DIO消息的發送。擁塞的程度越高，暫緩的時間越長。這就使得該節點的子節點因為長時間收不到DIO消息而切換其最優父節點，從而將流量均衡分配。但是該機制一方面可能會導致“羊群效應”（Herding Effect），即多個子節點同時切換到另一個父節點而將新的父節點擁塞；另一方面，因為采用涓流算法發送的DIO消息間隔周期可能會長至數分鐘之久，所以不能及時傳遞擁塞情況。

文獻[6]提出一種針對移動Sink的基于DAG的多徑路由協議，該協議使得節點在與主Sink節點的連接丟失時，可通過替代路徑連接到其他Sink節點。替代路徑的尋找采用被動按需的方式，當一個節點檢測到與主Sink節點連接失效時，會向其他Sink節點發起連接請求，一個新的DODAG會隨之建立，進而實現向Sink數據傳輸的恢復。

文獻[7]提出的多徑RPL協議工作于IEEE 802.15.4之上。該協議的目標是為數據傳輸提供QoS服務。它采用跨層設計的方式實現，構造DAG的過程使用由IEEE 802.15.4層提供的鏈路質量信息。普通數據仍然使用單徑轉發，只有對延遲敏感的高優先級數據才會以多徑的方式進行轉發，以保證傳輸質量。

文獻[8]提出一種帶時間因子的擁塞避免多徑路由協議。由于針對危險氣體檢測的應用場景對數據傳輸的時延要求非常嚴格，因此該協議設計了一種新的路由度量，使發送至Sink節點的時延減到最小。綜合考慮該度量與ETX，rank值及接收數據包的個數，計算路徑的權重大小，將其作為多徑路由時的選擇依據。

3 CALBM-RPL協議

如前所述，當數據包到達的數量超過節點發送能力時，便會產生擁塞。距離Sink節點較近的節點、子節點數目較多的節點以及突發事件發生處周邊的節點，都會因為轉發的數據包較多而發生擁塞。為了降低擁塞對網絡性能帶來的影響，需要將節點的擁塞狀況通知其周邊的節點，從而能讓一個子節點在其最優父節點發生擁塞時選擇其他路徑轉發數據包。

本文CALBM-RPL協議分成擁塞檢測和擁塞避免兩個部分。

3.1 擁塞檢測

CALBM-RPL協議將緩沖區的占用率作為擁塞狀況的指標。每個節點設定一個用以計算緩沖區占用率的定時器，定時器的時長設為發送DIO消息的最小間隔值Imin（4 s）。每當一個數據包到達時，節點發送緩沖區的大小就會被累加。定時器到期時，這段時間內的緩沖區平均占用率便會計算出來。正常情況下，該指標數值會在發送DIO消息時一并捎帶給周邊的鄰居節點，以避免產生額外的通信負擔。然而，如果緩沖區占用率超過了設定的擁塞門限值，那么一個用于緊急通知擁塞發生的DIO消息會被馬上發出，以使其子節點能夠盡快調整轉發路徑。之所以使用平均占用率而非即時占用率，是為了避免出現持續時間較短的通信量陡變的情形導致網絡震蕩。

當擁塞發生時，發送緩沖區被占滿，隨后待發的數據都會被丟棄。由于節點發送的所有數據包共用同一塊緩沖區，因此用來通知周邊節點已經發生擁塞的DIO消息也會被丟棄。這種不分優先級的丟棄策略會導致子節點繼續向擁塞的父節點發送數據，繼而導致擁塞的進一步惡化，更多的數據被丟棄。為了避免這一問題，CALBM-RPL協議中將DIO消息設置為高優先級。因為前者包含了最新的緩沖區占用率，所以一旦有DIO消息發送，若緩沖區已被占滿，且已經有一個待發送的DIO消息，則將用新的DIO消息替換掉舊的；若緩沖區中無目的地址為廣播地址的DIO消息，則刪除最后一個進入隊列的數據包，并將其空間分給DIO消息，保證DIO通知消息不會因為擁塞而被丟棄。

3.2 擁塞避免

每個節點在收到鄰居節點發來的DIO消息時，將其中的緩沖區占用率記錄在該鄰居節點的屬性中。

每個節點在發送數據包時，首先判斷該數據包的下一跳節點是否為自己的最優父節點，若是，則檢查最優父節點的緩沖區占用率是否超過擁塞門限。如果超過，則尋找緩沖區占用率小于擁塞門限的次優父節點。找到后，子節點會將該節點設為數據包的下一跳并進行發送。如此，協議便增加了發送路徑，實現多徑傳輸與負載均衡，從而達到提高吞吐量與數據傳輸成功率的目的。

4 性能評估

4.1 仿真模型及參數

為了測試CALBM-RPL協議的性能，在Cooja[9]模擬器上進行仿真與評估。Cooja是運行于Contiki[10]之上基于Java編寫的無線傳感網絡模擬器，是一個能在真實硬件設備上運行的物聯網微操作系統，具有開源、可移植、多任務、支持6LoWPAN等特性，在科研和商用領域都有著廣泛應用。本文采用Cooja模擬環境的相關參數見表1所列。

考慮到真實應用中的不同場景，分別在格狀排列和隨機排列兩種場景中進行協議測試。兩個場景的拓撲結構分別如圖1、圖2所示。兩種場景中都有三種類型的節點：1個Sink節點，位于網絡一角；25個低頻率發送數據節點，每分鐘分別向Sink節點發送1個數據包；5個高頻率發送數據節點，用以模擬由于檢測到某種事件的發生而向Sink節點密集發送通知信息，位于網絡中Sink節點的對角處，分別在0.5個/s，

1個/s，2個/s，4個/s的發送頻率下進行測試。為了保證結果的準確性，每種測試都以隨機的初始種子值運行10次然后取平均值作為實驗結果。

為了全面評估CALBM-RPL協議，分別從傳輸成功率、端到端時延和能量消耗等三個方面進行分析，并與標準RPL進行性能比較。為了簡化描述，格狀拓撲在性能對比圖中以“G-”標注表示，隨機拓撲的標注則以“R-” 標注表示。

4.2 仿真結果分析

4.2.1 數據傳輸成功率

Sink節點在兩種場景不同發送頻率下接收數據包的傳輸成功率如圖3所示。從圖3的數據可以看出，CALBM-RPL協議在兩種場景中傳輸成功率都優于標準RPL協議。其中，在格狀拓撲下數據包以2個/s的頻率發送時，CALBM-RPL較標準RPL高出54%。同時，格狀拓撲中由于替代的路徑更多而比隨機拓撲擁有更好的傳輸成功率，并且伴隨事件檢測節點發送頻率的升高，傳輸成功率會由于擁塞逐漸嚴重而相應降低。

4.2.2 端到端時延

在事件監測節點數據包以4個/s的頻率發送時，數據到達Sink節點的端到端時延情況如圖4所示。由圖4可知，兩種場景下CALBM-RPL協議較標準RPL的傳輸時延更大，因為最優父節點發生擁塞后，數據要選擇次優父節點進行轉發，導致這些數據需要經過ETX較差的鏈路或者更多的跳數才能到達Sink，從而增加了時延。這是提高數據傳輸率所付出的代價。

此外，格狀拓撲場景下平均端到端時延明顯少于隨機拓撲場景，這是由于隨機場景下傳感節點距Sink節點的跳數更多所致。

4.2.3 能量消耗

在不同發送頻率下兩種協議每比特平均傳輸能耗如圖5所示，該指標通過在模擬時間內總的能耗除以總發送及接收比特數計算而得。由圖5可知，雖然CALBM-RPL協議會在擁塞發生時以多路徑的方式進行傳輸，但是并未帶來能量消耗的大幅提高，反而比標準RPL還要略低一點。這是由于CALBM-RPL較高的傳輸成功率使其丟失的數據包相對較少，從而減少了中間節點轉發數據時由于丟失導致的能量浪費。

5 結 語

本文提出擁塞感知負載均衡多徑RPL，該算法將緩沖區占用率引入數據轉發過程，在最優父節點的緩沖區占用率超過設定門限值后觸發負載均衡機制，將一定的流量分發給次優父節點，通過增加路徑減輕最優父節點的轉發壓力，從而達到提高PDR和網絡性能的目的。仿真結果表明，該協議的數據傳輸率明顯提升，并且保持能量消耗基本不變，但同時也付出了端到端時延增加的代價。因此，該協議適用于需要高傳輸率而對時延性能要求不嚴的場景。未來計劃進一步擴展該協議功能，使其支持移動節點和多Sink場景。

參考文獻

[1] KUSHALNAGAR N，MONTENEGRO G，SCHUMACHER C.IPv6 over Low-Power Wireless Personal Area Networks（6LoWPANs）：overview，assumptions，problem statement，and goals [J].Heise Zeitschriften Verlag ，2007.

[2] IEEE 802.15.4-2011：IEEE standard for local and metropolitan area networks – Part.15.4：Wireless Medium Access Control（MAC）and Physical Layer（PHY）Specifications for Low-Rate Wireless Personal Area Networks（LR-WPANs）[S].Standard for Information Technology，2011.

[3] WINTER T，THUBERT P，BRANDT A，et al.RPL：IPv6 routing protocol for low power and lossy networks，RFC 6550[S].IETF，2012.

[4] LI B，CHUANG P.Efficient multimedia transmission in wireless sensor networks[C]// Intelligent Signal Processing and Communications Systems（ISPACS），Taiwan，2012.

[5] LIU X，GUO J，BHATTI G，et al.Load balanced routing for low power and lossy networks[C]// Proceedings of Wireless Communications and Networking Conference（WCNC），China，2013.

[6] XU G，LU G.Multipath routing protocol for DAG-based WSNs with mobile sinks[C]// Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering（ICCSEE），China，2013.

[7] PAVKOVI B，THEOLEYRE F，DUDA A.Multipath opportunistic RPL routing over IEEE 802.15.4[C]// Proceedings of the 14th ACM International Conference on Modeling，Analysis and Simulation，USA，2011.

[8] TANG W，MA X，HUANG J，et al.Toward improved RPL：a congestion avoidance multipath routing protocol with time factor for wireless sensor networks[J].Journal of sensors，2016（7）：1-7.

[9] OSTERLIND F，DUNKELS A，ERIKSSON J，et al.Cross-Level sensor network simulation with COOJA[C]// Local computer networks，proceedings 2006 31st IEEE conference，2006.

[10] DUNKELS A，GRONVALL B，VOIGT T.Contiki - a lightweight and flexible operating system for tiny networked sensors[C]// Proceedings of the IEEE workshop on embedded networked sensors，USA，2004.