一種高效低時延的RPL 跨層優(yōu)化機制

姚玉坤，朱克蘭，楊 迪，趙子軍

（1.重慶郵電大學通信與信息工程學院，重慶 400065；2.重慶郵電大學移動通信技術重點實驗室，重慶 400065）

0 概述

隨著智能電網(wǎng)［1］、智能建筑［2］、智能家居［3］以及環(huán)境監(jiān)測［4］等領域的快速發(fā)展，無線傳感器網(wǎng)絡（WSN）［5-7］得到研究人員的廣泛關注。針對鏈路質量不穩(wěn)定、網(wǎng)絡節(jié)點能量及處理能力受限的低功耗有損網(wǎng)絡（LLN），互聯(lián)網(wǎng)任務工作組（IETF）中的低功耗網(wǎng)絡工作組（ROLL）提出一種針對LLN 的路由協(xié)議（RPL）［8-9］。目前，ROLL 工作組制定了2 種路由度量，一種為當前節(jié)點距離根節(jié)點的邏輯位置，稱為網(wǎng)絡深度［10］，另一種為期望傳輸次數(shù)（ETX）［11］，待入網(wǎng)節(jié)點依據(jù)這2 種路由度量標準選擇父節(jié)點。

RPL 是一種網(wǎng)絡拓撲呈樹形的路由協(xié)議，網(wǎng)絡中的所有節(jié)點均支持多點到點通信、點到多點通信和點到點通信3 種數(shù)據(jù)通信模式。文獻［12］針對RPL 路由協(xié)議負載不均衡導致能量失衡的問題，提出一種負載均衡的多路徑機制，待入網(wǎng)節(jié)點通過新定義路由度量選擇最優(yōu)多父節(jié)點，新的路由度量綜合考慮節(jié)點剩余能量［13］、鏈路質量、緩存區(qū)占用率［14］以及子節(jié)點數(shù)目等多種因素。同時，文獻［12］依據(jù)期望壽命［15］、緩存區(qū)占用率、網(wǎng)絡深度以及子節(jié)點數(shù)目等因素定義路徑權重，依據(jù)路徑權重進行多路徑數(shù)據(jù)傳輸。文獻［16］提出基于多父節(jié)點的RPL 路由協(xié)議，通過啟發(fā)式的貪婪算法實現(xiàn)網(wǎng)絡中每個節(jié)點的生存時間最大化，同時，通過數(shù)據(jù)的多路徑轉發(fā)實現(xiàn)網(wǎng)絡負載均衡。但是，文獻［12，16］在最優(yōu)父節(jié)點選擇時均未考慮備選父節(jié)點的上行鏈路節(jié)點網(wǎng)絡狀態(tài)。

文獻［17］提出一種考慮父節(jié)點及子節(jié)點網(wǎng)絡狀態(tài)的目標函數(shù)（CAOF），并設計新的基于CAOF 的路由度量，稱為上下文感知路由度量（CARF）。CARF綜合考慮整條鏈路的隊列利用率以及剩余能量，待入網(wǎng)節(jié)點依據(jù)CARF 選擇最優(yōu)父節(jié)點，從而減緩高負載網(wǎng)絡場景中負載不均衡問題。但是，文獻［17］對于如何在控制消息中添加相關信息并未給出具體方案。文獻［18］提出一種提前預測的基于多種路由度量的父節(jié)點選擇機制，其中備選父節(jié)點與待入網(wǎng)節(jié)點均參與最優(yōu)父節(jié)點選擇過程。待入網(wǎng)節(jié)點依據(jù)多種路由度量標準選擇最優(yōu)備選父節(jié)點，最優(yōu)備選父節(jié)點根據(jù)自身隊列利用情況決定是否接受待入網(wǎng)節(jié)點為子節(jié)點。但是，該機制由于提前預測導致網(wǎng)絡控制開銷提升，且在進行最優(yōu)父節(jié)點選擇時存在路由度量較為單一的問題。文獻［19］通過實驗指出在當前Contiki RPL 開源系統(tǒng)以下行流量為主的網(wǎng)絡場景中，存在ETX 路由度量更新不及時的問題，并針對該問題提出改進方案。文獻［20］在文獻［19］的基礎上進行優(yōu)化，在最優(yōu)父節(jié)點選擇時融合網(wǎng)絡深度、期望傳輸次數(shù)和隊列利用率等多種路由度量，同時通過Trickle Timer［21］定時器進行快速重置，及時通告網(wǎng)絡擁塞情況。但是，上述方案僅考慮網(wǎng)絡負載均衡問題，并未解決數(shù)據(jù)傳輸時存在的繞路問題。

本文通過改進的最優(yōu)父節(jié)點選擇機制以及橫向路由建立機制，對當前RPL 路由協(xié)議進行優(yōu)化，提出一種高效低時延的RPL 跨層優(yōu)化機制CL-ORPL。

1 網(wǎng)絡拓撲構建及問題描述

1.1 網(wǎng)絡拓撲構建流程

在LLN中構建面向目的地的有向無環(huán)圖（DODAG）時，需要DODAG信息（DIO）、DAO（DestinationAdvertisement Object）以及目的地通告對象確認消息（DAO-ACK）3 種控制消息。RPL 路由算法構建網(wǎng)絡拓撲的控制消息交互過程如圖1 所示。根節(jié)點廣播DIO 消息發(fā)起組網(wǎng)，通信范圍內的待入網(wǎng)節(jié)點在收到DIO 消息后，若選擇加入該DODAG 中，則將根節(jié)點的信息添加到父節(jié)點列表中，并向根節(jié)點單播回復攜帶自身信息的DAO消息。根節(jié)點對每個接收到的DAO 消息均單播回復DAO-ACK 消息，待入網(wǎng)節(jié)點接收到DAO-ACK 消息后完成入網(wǎng)。節(jié)點入網(wǎng)后將繼續(xù)廣播發(fā)送添加自身相關信息的DIO 消息，重復上述過程，直至網(wǎng)絡拓撲組建完成。

圖1 節(jié)點入網(wǎng)的消息交互過程Fig.1 Message interaction process of the nodes entering the network

RPL 路由協(xié)議的組網(wǎng)流程偽代碼如下：

算法1RPL 路由協(xié)議組網(wǎng)算法

1.2 問題描述

當前針對RPL 路由協(xié)議的研究存在以下問題：

1）路由度量不完善。當前RPL 路由協(xié)議的研究中最優(yōu)父節(jié)點選擇機制未考慮備選父節(jié)點處的網(wǎng)絡連接情況，易造成網(wǎng)絡拓撲不均衡。

2）不合理的基于隊列利用率的路由度量。在當前基于隊列利用率的路由度量中，僅考慮備選父節(jié)點的隊列利用率，若所選最優(yōu)備選父節(jié)點處的整條鏈路中部分節(jié)點的隊列利用率較高，此時節(jié)點選擇該備選父節(jié)點為最優(yōu)父節(jié)點將加重鏈路負載。

3）數(shù)據(jù)傳輸存在繞路問題。在數(shù)據(jù)傳輸時，當節(jié)點發(fā)送數(shù)據(jù)包時的目的節(jié)點不是自身時，需向最優(yōu)父節(jié)點轉發(fā)數(shù)據(jù)，直至到達公共源節(jié)點，由公共源節(jié)點依據(jù)路由表發(fā)送數(shù)據(jù)。如圖2 所示，當節(jié)點A向節(jié)點E 發(fā)送數(shù)據(jù)時，完整的數(shù)據(jù)傳輸路徑應如圖中帶箭頭的虛線所示，即A →C →R →C →E，但若此時節(jié)點E 在節(jié)點A 的通信范圍內，就不需要經(jīng)過多次轉發(fā)。當網(wǎng)絡規(guī)模較大時，RPL 路由協(xié)議中的數(shù)據(jù)傳輸繞路問題將更加顯著。

圖2 數(shù)據(jù)轉發(fā)過程示意圖Fig.2 Schematic diagram of data forwarding process

2 CL-ORPL 機制

本文提出一種高效的CL-ORPL 機制，其主要包括最優(yōu)父節(jié)點選擇機制和橫向路由建立機制2 個部分。

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

最優(yōu)父節(jié)點選擇機制的基本思想是綜合考慮節(jié)點與父節(jié)點間的鏈路質量和網(wǎng)絡深度，本文以跳數(shù)指代節(jié)點網(wǎng)絡深度、鏈路隊列利用率以及子節(jié)點數(shù)目等多種路由度量，從而使得在選擇最優(yōu)父節(jié)點時更全面地考慮多個備選父節(jié)點及其鏈路的網(wǎng)絡狀態(tài)，有效實現(xiàn)網(wǎng)絡負載均衡。最優(yōu)父節(jié)點選擇機制的具體步驟如下：

步驟1節(jié)點根據(jù)當前的負載情況計算隊列利用率，避免負載較重的節(jié)點被選作最優(yōu)父節(jié)點。節(jié)點隊列利用率的計算公式如下：

其中，Boccupancy(n)指節(jié)點n當前隊列所占數(shù)據(jù)量，Bmax_size(n)指節(jié)點n的隊列空間大小。

用ETX(n，m) 表示n與m2 個節(jié)點間的鏈路質量，其計算公式如下：

其中，Dtotal(n→m)為節(jié)點n發(fā)送的總數(shù)據(jù)量，Dsuccess(n→m)為節(jié)點m成功接收的數(shù)據(jù)量。

步驟2為了不增加額外的控制開銷，通過DIO消息中的Rank字段攜帶網(wǎng)絡深度以及鏈路隊列利用率［13］，如下：

節(jié)點在廣播DIO 消息前需將自身的隊列利用率與最優(yōu)父節(jié)點隊列利用率進行對比，若自身隊列利用率較高，則將自身隊列利用率與網(wǎng)絡深度進行編碼；否則，將最優(yōu)父節(jié)點的隊列利用率與網(wǎng)絡深度進行編碼。

步驟3節(jié)點依據(jù)接收到的DAO 消息計算子節(jié)點數(shù)目，并將該信息加入待廣播發(fā)送的DIO 消息中。

步驟4待入網(wǎng)節(jié)點在接收到來自備選父節(jié)點的DIO 消息后，得到不同備選父節(jié)點的網(wǎng)絡情況，即網(wǎng)絡深度、期望傳輸次數(shù)、鏈路隊列利用率以及子節(jié)點數(shù)目等信息。通過對改進的Rank 字段解碼可以得到網(wǎng)絡深度以及鏈路隊列利用率的信息，解碼過程如式（4）、式（5）所示：

步驟5待入網(wǎng)節(jié)點依據(jù)式（6）分別計算所有備選父節(jié)點的綜合路由度量值，選擇具有最小路由度量值的節(jié)點為最優(yōu)父節(jié)點。

其中，hp為備選父節(jié)點p的網(wǎng)絡深度，ETX(n，p)為待入網(wǎng)節(jié)點n與備選父節(jié)點p之間的無線鏈路質量，λ為備選父節(jié)點的已連接子節(jié)點數(shù)目，Q()p為鏈路隊列利用率。

2.2 橫向路由建立

橫向路由建立策略包括攜帶上一跳節(jié)點信息的DAO-ACK 消息機制以及跨層旁聽DAO-ACK 消息機制2 個方面，其能夠有效縮短數(shù)據(jù)傳輸路徑，降低數(shù)據(jù)傳輸?shù)钠骄说蕉藭r延。

2.2.1 攜帶上一跳節(jié)點信息的DAO-ACK 消息機制

攜帶上一跳節(jié)點信息的DAO-ACK 消息機制的基本思路為：用DAO-ACK 消息的源地址字段攜帶上一跳節(jié)點地址，節(jié)點將DAO-ACK 消息的源地址字段內容，從原來保持不變的根節(jié)點網(wǎng)絡地址調整為當前節(jié)點的上一跳節(jié)點網(wǎng)絡地址。圖3 所示為改進的攜帶上一跳節(jié)點信息的DAO-ACK 消息具體幀格式。

圖3 攜帶上一跳節(jié)點信息的DAO-ACK 消息Fig.3 DAO-ACK message with information of last hop node

攜帶上一跳節(jié)點信息的DAO-ACK 消息機制的具體操作步驟如下：

步驟1節(jié)點的MAC 層在收到DAO-ACK 幀后，無論自己是否為目的地，均將幀中的內容（即DAO-ACK 消息）取出上傳至網(wǎng)絡層，并且將幀頭的源MAC 地址也取出上傳至網(wǎng)絡層。

步驟2節(jié)點的網(wǎng)絡層在接收到來自MAC 層傳輸?shù)脑碝AC 地址后，通過查詢所建立的“網(wǎng)絡地址-MAC 地址”映射表，獲取源MAC 地址對應的網(wǎng)絡地址，即上一跳節(jié)點地址，并將該地址放入接收到的DAO-ACK 消息的“Previous Hop Address”字段，即原“Source Address”字段。

步驟3用DAO-ACK 消息的目的地址查詢路由表獲取通往目的地的下一跳節(jié)點網(wǎng)絡地址。接著，通過查詢“網(wǎng)絡地址-MAC 地址”映射表，獲取下一跳節(jié)點的MAC 地址。最后，將DAO-ACK 消息和下一跳節(jié)點的MAC 地址下傳至MAC 層。

2.2.2 跨層旁聽DAO-ACK 消息機制

跨層旁聽DAO-ACK 消息機制的基本思路為：當網(wǎng)絡中其他節(jié)點的MAC 層接收到DAO-ACK 幀時，均將該DAO-ACK 幀的內容取出并上傳至網(wǎng)絡層，網(wǎng)絡層讀取相關內容，建立其到鄰居節(jié)點父節(jié)點的兩跳路由，從而避免數(shù)據(jù)傳輸繞路問題。

跨層旁聽DAO-ACK 消息機制的操作步驟如下：

步驟1節(jié)點依據(jù)發(fā)送到網(wǎng)絡層的信息的幀頭源MAC 地址，根據(jù)“網(wǎng)絡地址-MAC 地址”映射表獲取網(wǎng)絡地址，建立鄰居節(jié)點路由表，即一跳路由表。

步驟2節(jié)點讀取幀中的“Previous Hop Address”字段值，根據(jù)“網(wǎng)絡地址-MAC 地址”映射表獲取網(wǎng)絡地址，建立通過該節(jié)點和可到達節(jié)點的路由表，即兩跳路由表。在圖3 中，由于建立了橫向路由表，CL-ORPL機制中當節(jié)點A 向節(jié)點E 傳輸數(shù)據(jù)時，數(shù)據(jù)傳輸路徑如帶箭頭實線所示，即A →E。

2.3 CL-ORPL 機制組網(wǎng)流程

CL-ORPL 機制的組網(wǎng)流程如圖4 所示，具體步驟如下：

1）待入網(wǎng)節(jié)點依據(jù)式（6）依次計算每個備選父節(jié)點的綜合路由度量值。

2）待入網(wǎng)節(jié)點選擇綜合路由度量值最小的備選父節(jié)點為最優(yōu)父節(jié)點，并向最優(yōu)父節(jié)點單播發(fā)送DAO 消息請求入網(wǎng)。最優(yōu)父節(jié)點接收到DAO 消息后更新路由表，并繼續(xù)向自身的最優(yōu)父節(jié)點轉發(fā)，直至根節(jié)點接收DAO 消息。

3）根節(jié)點依據(jù)DAO 消息建立路由表并單播回復DAO-ACK 消息。

4）節(jié)點在轉發(fā)的過程中，不斷更新DAO-ACK消息中的“Previous Hop Address”字段并繼續(xù)依據(jù)自身的路由表發(fā)送DAO-ACK 消息。

5）若在MAC 層接收到目的地址不是自身的DAO-ACK 幀，仍將幀的內容傳輸至網(wǎng)絡層，并依據(jù)幀頭源MAC 地址以及Previous Hop Address 建立一跳鄰居路由以及通過鄰居可到達的兩跳路由。

6）待入網(wǎng)節(jié)點在接收到DAO-ACK 消息后入網(wǎng)。

圖4 CL-ORPL 機制組網(wǎng)流程Fig.4 The networking procedure of CL-ORPL mechanism

2.4 CL-ORPL 機制理論分析

CL-ORPL 機制能有效降低數(shù)據(jù)傳輸?shù)钠骄说蕉藭r延并提高數(shù)據(jù)傳輸成功率，理論分析具體如下：

1）CL-ORPL 機制能有效降低數(shù)據(jù)傳輸?shù)钠骄说蕉藭r延。

假設數(shù)據(jù)在網(wǎng)絡中傳輸?shù)亩说蕉藭r延為發(fā)送時延Tsend、傳播時延Ttra、處理時延Tpro以及排隊時延Tqueue之和，則總時延T為：

設TQU?RPL與TCL?ORPL分別為QU-RPL 與CL-ORPL的數(shù)據(jù)傳輸端到端時延，m與n分別為QU-RPL 與CL-ORPL 的數(shù)據(jù)平均發(fā)送次數(shù)，則有：

當網(wǎng)絡規(guī)模較大時，由于數(shù)據(jù)傳輸時橫向路由信息的建立，解決了數(shù)據(jù)包在網(wǎng)絡中通過上下行路徑傳輸導致的繞路問題，則有TQU-RPL遠大于TCL-ORPL，因此，CL-ORPL 機制能有效降低數(shù)據(jù)傳輸?shù)亩说蕉藭r延。

2）CL-ORPL 機制能有效提高數(shù)據(jù)傳輸成功率。

假設CL-ORPL 機制與QU-RPL 路由協(xié)議的數(shù)據(jù)傳輸成功率均為α，則CL-ORPL 機制與QU-RPL路由協(xié)議的平均數(shù)據(jù)傳輸成功率分別為nα與mα，由于CL-ORPL 機制通過橫向路由建立機制緩解了數(shù)據(jù)傳輸?shù)睦@路問題，因此其數(shù)據(jù)平均發(fā)送次數(shù)小于QU-RPL 路由協(xié)議，n＜m，則有nα＞mα，即CL-ORPL機制能有效提高數(shù)據(jù)傳輸成功率。

3 仿真驗證及分析

本文采用OPNET14.5 仿真軟件，在相同的網(wǎng)絡場景下對所提CL-ORPL 機制、QU-RPL 路由協(xié)議以及RPL 路由協(xié)議的網(wǎng)絡性能進行對比與分析。實驗中的具體參數(shù)設置如表1 所示。

表1 仿真參數(shù)設置Table 1 Simulation parameters setting

3.1 平均端到端時延

如圖5 所示，CL-ORPL 機制的數(shù)據(jù)傳輸平均端到端時延小于其他路由協(xié)議，主要原因為：CL-ORPL機制通過跨層旁聽攜帶上一跳節(jié)點信息的DAO-ACK消息，建立橫向路由，中間節(jié)點轉發(fā)次數(shù)的減少能夠有效降低平均端到端時延，此外，CL-ORPL 機制在選擇最優(yōu)父節(jié)點時綜合考慮鏈路隊列利用率以及連接的子節(jié)點數(shù)目，從而有效降低了部分路由節(jié)點處的負載以及數(shù)據(jù)傳輸時的排隊時延。

圖5 平均端到端時延變化情況Fig.5 Variation of average end-to-end delay

3.2 數(shù)據(jù)傳輸成功率

如圖6 所示，CL-ORPL 機制能夠提高數(shù)據(jù)傳輸?shù)某晒β?，主要原因在于?shù)據(jù)傳輸成功率與數(shù)據(jù)的轉發(fā)次數(shù)相關，CL-ORPL 機制通過橫向路由的建立減少了數(shù)據(jù)轉發(fā)次數(shù)，同時，隨著網(wǎng)絡規(guī)模的擴大，RPL 路由協(xié)議與QU-RPL 路由協(xié)議的繞路問題將更加嚴重，因此，CL-ORPL 機制提高數(shù)據(jù)傳輸成功率的效果更為顯著。

圖6 數(shù)據(jù)傳輸成功率變化情況Fig.6 Variation of success rate of data transmission

3.3 網(wǎng)絡生存時間

網(wǎng)絡生存時間指出現(xiàn)第一個節(jié)點的能量降至節(jié)點初始能量10%時的網(wǎng)絡運行時間。從圖7 可以看出，CL-ORPL 機制能夠有效延長網(wǎng)絡生存時間，主要原因在于：1）CL-ORPL 機制通過最優(yōu)父節(jié)點選擇機制實現(xiàn)網(wǎng)絡負載均衡，避免了網(wǎng)絡拓撲不均衡導致的部分節(jié)點需轉發(fā)數(shù)據(jù)量較大的問題，有效降低了部分路由節(jié)點的能耗；2）通過跨層旁聽攜帶上一跳節(jié)點信息的DAO-ACK 消息機制大幅減少了數(shù)據(jù)轉發(fā)次數(shù)，進一步降低了路由節(jié)點的處理能耗。

圖7 網(wǎng)絡生存時間變化情況Fig.7 Variation of network lifetime

4 結束語

針對當前RPL 路由協(xié)議中存在的網(wǎng)絡負載不均衡、數(shù)據(jù)傳輸繞路等問題，本文提出一種改進的CL-ORPL 機制。該機制通過綜合網(wǎng)絡深度、鏈路隊列利用率、期望傳輸次數(shù)以及子節(jié)點數(shù)目等多種路由度量，實現(xiàn)網(wǎng)絡負載均衡，同時利用跨層旁聽攜帶上一跳節(jié)點信息的DAO-ACK 消息建立橫向路由，以緩解數(shù)據(jù)傳輸時的繞路問題。OPNET 仿真軟件上的實驗結果表明，CL-ORPL 機制能夠有效降低數(shù)據(jù)傳輸?shù)钠骄说蕉藭r延，提高數(shù)據(jù)傳輸成功率并延長網(wǎng)絡生存時間。下一步將對RPL 路由協(xié)議中的橫向路由進行維護并繼續(xù)優(yōu)化數(shù)據(jù)傳輸過程。