多匯聚LLN中基于雙向父節點選擇的 高效RPL路由協議

王朝碩，朱克蘭，姚玉坤，趙子軍

(1.中國南方電網高壓輸電公司 信息通信運維中心，廣東 廣州 510000；2.重慶郵電大學 移動通信技術重慶市重點實驗室，重慶 400065)

0 引 言

低功耗有損網絡(low power and lossy network，LLN)[1,2]是無線傳感器網絡(wireless sensor networks，WSN)[3,4]的一類分支，目前被越來越廣泛地應用于智能電網[5]、智能建筑[6]、智能家居[7]和環境監測[8]等領域，RPL路由協議(routing protocol for LLN，RPL)[9]作為專為LLN制定的路由協議也受到了關注。當前，RPL路由協議的研究熱點為基于單sink的網絡負載均衡[10-12]，但相關研究表明基于多sink的LLN與基于單sink的LLN相比具有較大的網絡性能優勢。文獻[13,14]通過對比分析證明了隨著sink節點數目的增加，能夠有效提升網絡性能。然而當前基于多sink節點的RPL路由協議中的研究中仍存在一定的問題。文獻[15]提出通過多重身份節點實現數據流量在多個面向目的地的有向無循環圖(destination-oriented directed acyclic graph，DODAG)之間的自適應分配，從而均衡多個DODAG的網絡負載，但該協議對網絡性能的提升不算明顯。文獻[16]提出一種基于備用sink節點的優化RPL協議，為節點定義了一種壓力指數參數，當壓力指數超過閾值，節點將主動發起父節點切換過程，將父節點切換到備用sink，直至檢測到壓力指數低于閾值。但備用節點僅在網絡擁塞發生時啟用，浪費了網絡資源。文獻[17]提出一種基于協調框架的RPL路由協議，依據數據包的投遞率調整子節點的連接數目，實現了以sink為中心的多個子樹間的負載均衡，但該協議不能有效避免DODAG內發生網絡擁塞。

針對上述現有研究中存在的問題，本文提出一種多匯聚LLN中基于雙向父節點選擇的高效RPL路由協議——BPSM-ERPL(efficient RPL in LLNs based on bidirectional parent selection in multiple sinks)加以解決。

1 網絡模型及問題描述

1.1 RPL路由協議

RPL路由協議組網的消息交互如圖1所示。首先，sink節點廣播一個DODAG信息對象消息(DODAG information object，DIO)發起組網過程；sink通信范圍內的待入網節點收到DIO消息后，將sink的信息添加到自己的父節點列表，并用單播方式向sink回復一個包含自身信息的目的地通告對象消息(destination advertisement object，DAO)；sink節點對每個接收到的DAO消息均用單播方式回復一個目的地通告對象確認消息(destination advertisement object acknowledgement，DAO -ACK)；待入網節點收到DAO -ACK消息后記錄相關信息，至此一個節點的入網過程完成。節點入網后用廣播一個包含自身信息的DIO消息。

圖2 網絡拓撲

1.2 網絡模型

網絡模型如圖2所示，圖中S1與S2為sink節點，分屬不同的RPL實例。為便于表述，給出如下假設和定義：

(1)網絡節點均有路由功能，即節點可以收發消息，網絡中的節點分為兩種，普通路由節點以及邊界路由節點：①普通路由節點：普通節點僅能接收到一個RPL實例的DIO廣播消息，也僅能加入一個DODAG，例如節點1、節點2以及節點10；②邊界路由節點：邊界路由節點能夠接收到多個RPL實例的DIO廣播消息，故其可以加入多個DODAG，例如節點5、節點6以及節點7。

(2)主父節點指路由節點依據目標函數從備選父節點集中選擇的最優父節點，次父節點指路由節點依據目標函數從備選父節點選擇的次優父節點。

(3)網絡中的路由節點均不具備移動性，網絡中的節點除sink節點外均需要考慮路由節點處的能耗及數據處理能力。

1.3 問題描述

經過研究分析當前基于RPL路由協議的相關技術，發現仍存在以下問題：

(1)待入網節點唯一決定父節點選擇：在最優父節點的選擇中，待入網節點根據接收到的DIO消息從備選父節點集中選擇最優父節點，并向選擇的最優父節點發送一個DAO消息，接收到DAO消息的節點，不論當前的網絡連接狀態，都必須建立與子節點的連接。同時，向上繼續轉發來自子節點的DAO消息。在極端情況下，若此時最優父節點由于已連接的子節點數目較多，子節點均向最優父節點處發送大量數據，導致最優父節點需要承擔的轉發任務較重，然而受數據處理能力的限制，最優父節點無法處理如此高的數據流量進而造成隊列占用率急劇增加，最終導致最優父節點處遇到網絡擁塞，影響網絡正常數據傳輸。RPL路由協議針對網絡擁塞的問題提出切換最優父節點的策略，但該策略勢必導致網絡不穩定以及數據傳輸丟包率上升等問題。

(2)雷鳴效應：雷鳴效應指的是大量的待入網節點建立與網絡性能較優的節點的連接，導致節點處連接大量子節點的現象。

如圖3的雷鳴效應所示，以隊列利用率為路由度量，除sink外的所有節點(節點1-11)按照圖1所示的控制消息交互流程開展入網操作：如果節點能夠收到父節點廣播的DIO消息，則直接與sink節點交互完成入網；如果不能收到，則通過廣播DODAG信息請求(DODAG information solicitation，DIS)消息的方式與已入網節點建立聯系然后完成入網。節點1及節點3先入網，其隊列利用率分別為0.3和0.25，并將該信息添加在DIO消息中廣播。隨后節點2入網，其隊列利用率為0.2，同樣廣播添加了該信息的DIO消息；這樣將導致在其通信范圍內的待入網節點在對比備選父節點集中的其它節點后，均選擇該節點為最優父節點。而已經入網的節點，例如節點5以及節點6，也可能切換最優父節點，最終導致節點2處連接較多的子節點，也即在節點2上產生了雷鳴效應。在雷鳴效應的作用下，節點2的能量被快速地消耗，而節點1和節點3的資源卻未得到充分利用，這將導致網絡不穩定。

圖3 雷鳴效應

(3)多sink節點間的網絡負載不均衡：以每個sink節點為中心節點，可以構建一個DODAG圖。在多sink的LLN中，若某個RPL實例內由于網絡負載較重，僅在該RPL實例中進行優化，并未有效利用多sink節點的網絡拓撲特性，也即網絡資源的分配非最優。

2 BPSM-ERPL路由協議

BPSM-ERPL路由協議包括以下3個創新機制，針對問題(1)及問題(2)，提出攜帶咨詢信息的DAO消息機制以及雙向父節點選擇機制，針對問題(3)，提出一種自適應數據傳輸機制。下文詳細介紹BPSM-ERPL路由協議包含的新機制及具體操作。

2.1 攜帶咨詢信息的DAO消息

攜帶咨詢信息的DAO消息機制的核心思想為，通過改進的M-DAO請求消息，告知父節點當前待入網節點的預估數據傳輸速率。M-DAO消息的基本對象格式如圖4所示，圖中字段M代表主父節點，字段C代表強制。

圖4 M-DAO消息基本對象格式

與DAO消息的基本對象相比，M-DAO消息的基本對象在格式上改變不大，主要變化在Type字段和保留字段。首先，為了與當前RPL路由協議中的其它控制消息區分，新協議更改了M-DAO消息的Type字段；其次，對原DAO消息的保留字段進行了更改，重新劃分為字段M、字段C以及Data字段。字段M占1字節，主要用于通告父節點當前是否為主父節點。若接收M-DAO消息的節點為主父節點，則字段M設1。若接收M-DAO消息的節點為次父節點，則字段M設0。字段C占1字節，主要用于通告父節點當前的入網請求是否是強制請求。若當前待入網節點的備選父節點集中僅有一個節點，則待入網節點發送字段C置1的強制請求。若當前待入網節點的備選父節點集有多個節點，則待入網節點發送字段C置0的非強制請求。Data字段用于攜帶待入網節點請求的數據傳輸速率，以實現提前通告父節點的目的。

2.2 雙向父節點選擇機制

雙向父節點選擇機制的核心思想是父節點在接收到M-DAO消息后，根據M-DAO消息攜帶的信息，判斷是否建立與待入網節點的連接，詳細操作步驟如下。

步驟1 待入網節點發送M-DAO消息，最優父節點接收后，首先讀取字段C以及Data字段。首先最優父節點查看字段C，若字段C的值設為1，表明當前的入網請求為強制性請求，最優父節點依據M-DAO消息攜帶的信息更新路由表并向sink轉發M-DAO消息，否則直接執行步驟2。

步驟2 若字段C的值設為0，表明當前的入網請求為非強制性請求。此時，最優父節點將依據Data字段攜帶的信息判斷是否能夠在不影響當前的網絡服務質量的前提下，建立與待入網節點的連接，判據條件如式(1)所示

(1)

式中：假設待入網節點為節點N，最優父節點為節點P，則dN為待入網節點通過M-DAO消息的Data字段攜帶的當前請求的一個時間周期內需傳輸的平均數據包數目，dP為最優父節點的一個時間周期需傳輸的平均數據包數目，di為最優父節點P當前已連接的子節點請求的一個時間周期內需傳輸的平均數據包的數目。q表示最優父節點的隊列長度，do為最優父節點P的一個時間周期內傳輸的平均數據包數目，轉至步驟3。

步驟3 若待入網節點請求的一個時間周期內需傳輸的數據包的平均數目滿足判據條件，則最優父節點建立與待入網節點的連接。更新路由表，并向上轉發M-DAO消息，否則轉至步驟4。

步驟4 若待入網節點請求的一個時間周期內需傳輸的平均數據包數目不滿足判據條件，則最優父節點向待入網節點發送請求拒接消息，待入網節點繼續從備選父節點集中選擇其它節點為最優父節點。轉至步驟5。

步驟5 待入網節點在接收到來自sink節點的DAO -ACK消息后入網。已入網的節點將廣播添加了自身信息的DAO -ACK 消息。

2.3 自適應數據傳輸機制

在擁有多個RPL實例的RPL路由協議中，位于實例邊界的路由節點可以獲取不同RPL實例的DIO消息，加入多個RPL實例。數據傳輸自適應機制的核心思想是：邊界路由節點通過在DIO消息中獲取到的最優父節點的鏈路隊列利用率和網絡深度等信息，根據屬于不同RPL實例的最優父節點的網絡狀態進行自適應的數據傳輸，以均衡數據流量在多個RPL實例的分配。自適應數據傳輸機制的具體操作步驟如下：

步驟1 重新定義DIO消息中的Rank字段，將鏈路隊列利用率Q與網絡深度h進行編碼[10]，(下文式(2)～式(4)中參數的定義請參見文獻[10])。如式(2)所示

RankQU(n)=β(h(n)+1)+(β-1)Q(n)

(2)

邊界路由節點對接收到的DIO消息中的Rank字段解碼，如式(3)、式(4)所示，從而獲取網絡深度以及鏈路隊列利用率等信息

(3)

(4)

步驟2 邊界路由節點對屬于不同RPL實例的DIO消息進行劃分，分別計算不同RPL實例的備選父節點的路由度量，并依據式(5)選出最優的屬于不同的RPL實例的最優備選父節點。式(5)中hp表示備選父節點p的網絡深度，ETX(N,p) 表示待入網節點N與備選父節點p之間的無線鏈路的質量，λ為備選父節點連接的子節點數量，Qp表示MAC子層的鏈路隊列利用率

R=hp+ETX(N,p)+λQp

(5)

如圖2所示，邊界路由節點4的備選父節點集中屬于實例1的備選父節點為節點1及節點2；屬于實例2的備選父節點集為節點9及節點10，轉至步驟3。

步驟3 邊界路由節點從備選父節點集中選擇最優父節點集后，繼續查看最優父節點集合的鏈路隊列利用率，檢查最優父節點集的關聯鏈路中是否有重負載節點。若最優父節點集的關聯鏈路中沒有重負載節點，則邊界路由節點根據網絡深度分配數據傳輸速率[15]，并分別向屬于不同RPL實例的最優父節點發送Pt字段置1以及字段C置0的M-DAO請求消息，否則直接執行步驟4。

步驟4 若當前最優父節點集的關聯鏈路連接有重負載節點，則邊界路由節點向鏈路未連接重負載節點的最優父節點發送字段M值為1和字段C值為0的M-DAO消息，并向鏈路連接有重負載節點的最優父節點發送字段M值為0和字段C值為0的M-DAO消息，否則直接執行步驟5。

步驟5 若當前最優父節點集的關聯鏈路均連接有重負載節點，則邊界路由節點從備選父節點集中重新選擇最優父節點集，然后重復步驟2至步驟4的操作。

2.4 BPSM-ERPL路由協議

BPSM-ERPL路由協議的主要操作[18]如下：

步驟1 待入網節點根據收到的DIO消息的內容，判斷自己是否是邊界路由節點；若不是，則根據目標函數確定最優路徑，選擇最優父節點，然后向最優父節點發送包含自身信息的M-DAO消息。

步驟2 如果待入網節點是邊界路由節點，則由待入網節點選擇最優父節點集。在確定最優父節點集后，檢查最優父節點集的關聯鏈路是否連接有重負載節點。若鏈路未連接重負載節點，則邊界路由節點根據網絡深度分配數據流量，邊界路由節點向最優父節點分別發送包含自己信息的M-DAO消息，否則直接執行步驟3。

步驟3 如果邊界路由節點的最優父節點集的關聯鏈路連接有重負載節點，則邊界路由節點向鏈路未連接重負載節點的最優父節點發送字段M值為1的M-DAO消息；并且向鏈路連接有重負載節點的最優父節點發送字段M值為0的M-DAO消息，否則直接執行步驟4。

步驟4 如果邊界路由節點的最優父節點集的關聯鏈路均連接有重負載節點，邊界路由節點則重新在備選父節點集中選擇最優父節點，然后執行步驟5。

步驟5 最優父節點收到M-DAO消息后，提取該消息攜帶的信息進行判斷；若字段C的值為1，最優父節點須建立與待入網節點的連接，并向sink轉發M-DAO消息；否則，最優父節點根據判據條件式(1)進行判斷；若滿足式(1)，最優父節點建立與待入網節點的連接，并向sink轉發M-DAO消息，否則最優節點向待入網節點發送請求拒絕消息。

步驟6 待入網節點收到來自sink的DAO-ACK消息后便完成了入網。已入網節點繼續廣播添加了自身信息的DIO消息。

BPSM-ERPL路由協議算法流程如圖5所示。

圖5 BPSM-ERPL路由協議算法流程

3 仿真驗證及分析

本文采用網絡仿真軟件OPNET Modeler 14.5對CF-RPL路由協議、TAAM-RPL路由協議和提出的BPSM-ERPL路由協議進行仿真，在相同的網絡場景下對數據傳輸成功率、網絡吞吐量、網絡生存時間性能指標進行定量對比及分析[19]。

3.1 仿真統計量

本文選取了吞吐量、成功率以及網絡生存時間作為驗證新協議性能的仿真統計量。本文所提新協議在原理上能夠更有效、合理地利用網絡帶寬和能量資源，因此對上述3個統計指標有提升作用。

(1)數據傳輸成功率

數據傳輸成功率等于目的節點成功收到的數據包的總比特數與源節點發送的總數據比特數的比值，如式(6)所示

(6)

式中：S為數據傳輸成功率，Dr為被目的節點成功收到的數據包的總比特數，Dt為源節點發送的數據包的總比特數。

(2)網絡吞吐量

網絡吞吐量表示在有數據包發送的仿真時間內，目的節點成功收到的數據包的總比特數，如式(7)所示

(7)

式中：Ts為有數據發送的仿真時間，T表示網絡吞吐量。

3.2 仿真參數設置

網絡場景設置為800 m×800 m的正方形區域，網絡節點數依次設置為40、80、120、160、200以及240。網絡中設置兩個sink節點，網絡中的路由節點位置均固定。節點發射功率設為30 mW，每個路由節點的通信范圍內均設有路由節點，數據分組長度為128 bits，數據發送速率為每秒一個，網絡仿真時間為4000 s，主要仿真參數設置見表1。

表1 主要仿真參數

3.3 數據傳輸成功率

如圖6所示，在不同的網絡規模下，雖然3種路由協議的數據傳輸成功率均呈下降趨勢，但BPSM-ERPL路由協議的數據傳輸成功率高于CF-RPL路由協議和TAAM-ERPL路由協議。主要原因是BPSM-ERPL路由協議首先通過雙向父節點選擇機制，充分考慮了父節點的網絡狀況和數據處理能力，避免了網絡擁塞導致的數據丟包，能夠更有效、合理地利用網絡帶寬資源；同時通過自適應數據傳輸機制，在充分考慮最優父節點鏈路負載狀態的前提下，實現了數據流量在多個DODAG間的均衡分配；有效均衡了網絡負載，降低了網絡擁塞發生概率，從而進一步提升了數據傳輸成功率。

圖6 數據傳輸成功率

3.4 網絡吞吐量

如圖7所示，在不同的網絡規模下，BPSM-ERPL路由協議的網絡吞吐量均高于CF-RPL路由協議以及TAAM-ERPL路由協議，并且隨著網絡規模的擴大，BPSM-ERPL路由協議的性能優勢更加顯著。分析其原因為，網絡吞吐量與數據發送成功率呈正相關，與數據傳輸的平均端到端時延呈負相關。通過圖6可知，BPSM-ERPL路由協議提高了數據發送成功率。其次，由于BPSM-ERPL路由協議能夠有效實現網絡負載均衡，降低網絡擁塞發生的概率，從而能更加合理、有效地利用網絡的帶寬資源。從而其能夠有效降低數據傳輸的排隊時延以及由于丟包導致的數據重傳。也即，可以降低數據傳輸的平均端到端時延。因此，BPSM-ERPL路由協議能夠提高網絡吞吐量。

圖7 網絡吞吐量

3.5 網絡生存時間

網絡生存時間的定義請參見文獻[15]。圖8顯示BPSM-ERPL路由協議能夠有效地延長網絡生存時間。據分析主要原因是BPSM-ERPL協議通過采用DAO消息攜帶咨詢信息和雙向父節點選擇的新機制，有效避免了雷鳴效應，而雷鳴效應的直接后果就是發生雷鳴效應的節點處的網絡資源以及節點能量等被快速消耗；其次，通過采用自適應數據傳輸機制，避免了負載較重的節點被選為最優父節點；并且借助邊界路由節點實現了數據流量在多個RPL實例間的合理分配，調動了整個網絡的資源，使網絡資源的利用更加合理，重負載節點的能量能夠得到保護。因此，BPSM-ERPL路由協議能夠有效延長網絡生存時間。

圖8 網絡生存時間

4 結束語

針對當前RPL相關路由協議存在的雷鳴效應、待入網節點唯一決定父節點選擇以及數據在多個RPL實例間分配不合理問題，提出BPSM-ERPL路由協議。BPSM-ERPL路由協議首先優化了DAO消息，通過M-DAO消息攜帶咨詢信息；其次采用了雙向父節點選擇機制，使父節點根據網絡狀態能夠選擇建立或不建立與待入網節點的連接，從而有效地避免了雷鳴效應，提高了網絡穩定性。最后，BPSM-ERPL路由協議采用了自適應數據傳輸機制，通過邊界路由節點實現了數據信息在RPL實例間的分配，有效實現了網絡負載均衡。理論分析及仿真實驗結果表明，BPSM-ERPL路由協議能夠有效提升網絡性能。在未來的工作中，我們將繼續就如何實現多個DODAG間的通信進行研究。