LLN中基于負載均衡的單路徑路由協議

陳蘇海，黨向盈

(1.徐州工程學院 信電工程學院，江蘇 徐州 221000；2.中國礦業大學 信息與控制學院，江蘇 徐州 221000)

0 引 言

低功耗有損網絡(low power and lossy networks，LLN)[1-5]通過網關或者邊界路由器直接與互聯網進行數據交互，使得LLN擁有較好的互操作性和靈活性。因此，LLN在工業控制、智能家居和醫療保健等領域擁有較好的應用前景。考慮到LLN廣泛的應用場景，國際互聯網工程任務組提出了一種適用于LLN網絡的IPv6路由協議(IPv6 based routing protocol for LLN，RPL)[6,7]。

當前，學術界已對單路徑RPL路由協議展開大量研究。文獻[8]僅將傳輸跳數作為選擇最優父節點的路由度量，而未考慮無線鏈路質量，可能導致網絡中鏈路質量不佳的節點被選作為父節點，從而使數據包的丟包率上升，增大節點的能耗。為了避免將無線鏈路不佳的節點選作父節點，文獻[9]中將數據包的期望傳輸次數作為選擇父節點的判據，卻忽略了節點的剩余能量，極有可能將剩余能量不足的節點選作當前父節點，從而加快了此類節點的能量消耗速率，縮短了網絡生存時間。為了避免將剩余能量不足的節點選作父節點，文獻[10]中將節點的剩余能量作為選擇父節點的路由判據，可能導致無線鏈路質量較差而擁有充足剩余能量的節點被選作為父節點，增加了其子節點丟包重傳的次數，從而降低了網絡吞吐量和增加了節點能耗。為了避免文獻[9]和文獻[10]中存在的問題，文獻[11]中綜合考慮了節點剩余能量和無線鏈路質量。然而，由于文獻[11]未將節點當前緩存占用率考慮在內，一旦遇到突發緊急情況需要傳輸大量數據時，容易產生網絡擁塞，從而嚴重影響數據的傳輸。文獻[12]僅將節點的緩存占用率作為路由度量，而未考慮節點間的無線鏈路質量，從而加劇了節點丟包重傳的能耗。

上述針對單路徑RPL路由協議的研究主要存在以下兩個方面的不足：①在網絡拓撲初始化的過程中，路由度量的選擇過于單一，無法有效地實現網絡負載均衡，從而不能延長網絡壽命；②在選擇最優父節點的過程中，僅僅考慮一跳范圍內的數據傳輸代價而未考慮整條路徑上的數據傳輸代價影響了最優父節點的選擇，導致無法有效地提升網絡各方面的性能。

為了盡可能地解決上述所存在的問題，本文提出了一種基于負載均衡的單路徑LLN路由協議(load balance-based single path routing protocol for LLN，LB-RPL)，并對該協議的具體操作過程進行了詳實的分析以及對該協議的網絡性能進行了模擬仿真對比和驗證。

1 RPL路由構建原理

在創建面向目的地有向無循環圖(destination oriented directed acyclic graph，DODAG)的過程中，RPL路由協議制定了3種常用的控制消息：DODAG信息對象消息(DODAG information object，DIO)、面向目的地有向無循環圖請求消息(DODAG information solicitation，DIS)以及面向目的地有向無循環圖目的地通告消息(destination advertisement object，DAO)。DIO消息的主要功能是為了創建上行路由和維護網絡拓撲的連通性，由sink節點發起；在DODAG構建過程中，DAO消息主要用于回應DIO消息，從而完成下行路由的構建；DIS消息主要用于路由請求，鏈路故障節點或是新節點均可通過廣播DIS消息可以主動請求加入到DODAG中。DODAG構建流程如圖1所示。

圖1 DODAG構建流程

DODAG的構建具體步驟如下：①sink節點向其鄰居節點周期性的廣播DIO消息；②sink節點的鄰居節點A成功接收到sink節點廣播的DIO消息之后，將sink節點作為父節點，并回復包含自身路由前綴信息的DAO消息；③節點A重復sink節點的操作過程，節點B重復節點A的操作過程；④由于節點C在一段時間內未接收到其鄰居節點廣播的DIO消息，于是主動廣播DIS消息；⑤節點B接收到節點C廣播的DIS消息后，向節點C單播一個DIO消息；⑥節點C接收到DIO消息后，向節點B回復一個DAO消息；⑦節點A和節點B轉發該DAO消息直至根節點，至此DODAG構建完成。

2 LB-RPL路由協議

針對LLN中現有單路徑路由協議在網絡拓撲構建過程中考慮的路由度量過于單一，以及在選擇最優父節點時僅依據一跳范圍內的數據傳輸代價而無法有效地均衡節點能耗和延長網絡壽命等問題，LB-RPL路由協議中主要提出了以下3種優化策略：①在備選父節點的選擇過程中，對選擇備選父節點的條件進行限制，從而選出合適的最優父節點；②在路由度量值的計算過程中，綜合考慮多種路由度量，避免單一路由度量對網絡性能所帶來的影響；③在選擇最優父節點的過程中，考慮整條路徑上的數據傳輸代價，最終選擇數據傳輸代價相對較小的備選父節點作為最優父節點。

2.1 備選父節點的選擇

在DODAG的構建過程中，為了降低單一路由度量對最優父節點的選擇所產生的影響，在選擇備選父節點時需滿足以下3個限制條件：第一，節點與其備選父節點之間的無線鏈路質量應高于預設的鏈路質量閾值，從而避免選擇無線鏈路質量較差的節點作為父節點。在本文中，無線鏈路質量低于0.7的節點將不能作為備選父節點；第二，為了使節點的能耗均衡，剩余能量較低的節點(低于能量閾值)不能作為備選父節點。在本文中能量閾值為節點初始能量的20%；第三，備選父節點的緩存占用率應低于預設的網絡擁塞閾值，從而避免選擇高負載的節點作為父節點。在本文中網絡擁塞閾值設定為節點最大緩存的80%。

在網絡拓撲初始化過程中，網絡中每個節點為了獲知彼此之間的內存空間占用情況、剩余能量和鏈路質量，分別將上述3種信息添加到周期性廣播的DIO消息中。因此，節點在選擇備選父節點時，只需依次判斷其鄰居節點的上述3種信息是否滿足要求。若滿足要求，則將該鄰居節點作為備選父節點；反之，則將該DIO消息丟棄。圖2所示為LB-RPL路由協議選擇備選父節點的流程。

圖2 備選父節點的選擇

2.2 路由度量值的計算

在網絡構建過程中，當節點獲知其所有備選父節點信息之后，計算與各個備選父節點之間的路由度量值。在路由度量值的計算過程中，為了有效地避免選擇單一路由度量對網絡性能所產生的不良影響，因此需要將多種路由度量進行有效地融合。下面以網絡中的節點i為例，對多種路由度量有效融合的實際操作步驟如下：

步驟1 根據節點i的當前剩余能量計算其期望壽命，從而有利于避免潛在子節點選擇剩余能量非最佳的備選父節點作為最優父節點。節點當前期望壽命[13]可由如下幾個過程獲取：

(1)統計節點i的數據包發送速率，如式(1)所示。其中，Tgen(i)表示節點i的數據包發送速率，Tj表示其子節點j的數據包發送速率

(1)

(2)計算節點i將在一段時間內所收集的數據包成功發送至其最優父節點k大致所需要發送的平均次數，如式(2)所示。其中，ETX(i,k)表示節點i成功發送單個數據包到達其最優父節點k大致所需要發送的平均次數

Ni=Ti×ETX(i,k)

(2)

(3)計算節點i將在一段時間內所收集的數據包成功發送至其最優父節點k大致所耗費的時間，如式(3)所示。其中，data_rate表示節點i的數據包傳輸速率

(3)

(4)計算節點i將在一段時間內所收集的數據包成功發送至其最優父節點k的能量大致消耗速率，如式(4)所示。其中，Ptx(i)被定義為節點i的數據包發送功率

(4)

(5)最后，依據節點i的當前剩余能量以及能量消耗速率便可計算出其期望壽命，如式(5)所示。其中，Eres(i)表示節點i當前剩余能量

(5)

步驟2 計算節點i的緩存占用率，從而有利于避免節點i的下游節點選擇高負載的備選父節點作為最優父節點

(6)

式中：buffer_occupancyi反映了節點i的緩存空間被占用的情況，buffer_size被定義為節點i的緩存空間大小。

步驟3 在LLN網絡創建過程中，節點i根據所統計子節點發回的DAO消息的個數便可獲得當前處于連接狀態的子節點數量，從而有利于避免節點i的下游節點選擇子節點數量較多的備選父節點作為最優父節點。

步驟4 節點i將其期望壽命、緩存占用率和當前子節點數量相關度量信息添加到DIO消息中，并廣播攜帶上述度量信息的DIO消息。

步驟5 節點i的鄰居節點從接收到的DIO消息中提取出節點i的期望壽命、緩存占用率以及其當前子節點數量后，根據式(7)計算與節點i之間的路由度量值，路由度量值的大小能夠反映出節點的數據傳輸代價，即路由度量值越大，節點的傳輸代價相對越小

(7)

2.3 最優父節點選擇策略

在DODAG的構建過程中，在選擇最優父節點時綜合考慮整條路徑的數據傳輸代價。通過計算整條傳輸路徑上的總度量值大小判斷備選父節點的優先級。總度量值越大，備選父節點的優先級越高，最終選擇優先級最高的備選父節點作為最優父節點。最優父節點選擇策略的具體操作步驟為：

步驟1 當sink節點發起DODAG的構建時，其一跳范圍內的鄰居節點N選擇根節點作為最優父節點，并計算出度量值，且將度量值的大小添加到周期性廣播的DIO消息中。

步驟2 節點M接收到其鄰居節點周期性廣播的DIO消息后，根據備選父節點選擇策略選出備選父節點。

步驟3 節點M根據DIO消息中攜帶的相關信息計算與所有備選父節點之間的度量值，然后根據式(8)計算每條路徑上的總度量值

(8)

式中：Metric(M→N→sink)表示節點M通過其備選父節點N到達sink節點的總度量值，φ表示節點M的網絡深度值。

步驟4 節點M根據計算所得的每條路徑上的總度量值的大小選擇最優父節點，即選擇總度量值最大的備選父節點作為最優父節點。如果計算得到一個節點擁有兩個總度量值相同的備選父節點，則選擇度量值方差較小的備選父節點作為最優父節點。

步驟5 節點M將當前總度量值添加到周期性廣播的DIO消息中，其下游節點接收到該DIO消息后重復節點M的處理過程，直至網絡構建完成。

如圖3所示，節點I有兩個備選父節點D和E，即節點I到sink節點有兩條路徑，分別為I→D→A→sink和I→E→B→sink。而這兩條路徑的總的度量值分別為17和15，根據最優父節點選擇策略，則節點I選擇備選節點D作為最優父節點。

圖3 基于LB-RPL路由協議的網絡拓撲構建

3 實驗及結果分析

使用OPNET14.5仿真工具進行平臺的搭建和仿真，將本文提出的LB-RPL路由協議與RPL-OF0[8]和ETX-RPL[9]路由協議從以下4個方面進行對比和分析，分別為數據包投遞率、網絡生存時間、平均端到端傳輸時延和根節點平均吞吐量。

3.1 仿真環境及參數設置

在300 m×300 m的模擬仿真場景中創建網絡規模大小分別為10、30、50、70、90和110的LLN網絡，且每個場景中的所有節點均隨機放置。除此之外，網絡中每個節點均工作在存儲模式下，且初始能量相同。在網絡創建初期，所有節點均采用靜態模型，即位置一旦被確定將不再進行改變。仿真中用到的其它參數見表1。

表1 主要仿真參數

3.2 統計量定義

(1)數據包投遞率

數據包投遞率(packet delivery ratio，PDR)被定義為從源節點成功傳輸到根節點的數據包數量與源節點發送數據包的比值，計算公式為

(9)

式中：Pi表示成功到達根節點的數據包數量，Dj表示源節點發送的數據包數量。

(2)網絡生存時間

網絡生存時間是指在網絡拓撲初始化之后網絡中出現第一個能量耗盡的節點所耗費的時間，計算公式為

TL=Td-T0

(10)

式中：Td表示網絡中出現第一個能量耗盡節點的時刻，T0表示網絡開始運行的時刻。

(3)平均端到端時延

平均端到端時延被定義為所有從源節點成功傳輸到達根節點的所有數據包的端到端傳輸時延總和與數據包個數的比值，計算公式為

(11)

式中：Ti表示第i個數據包到達根節點的傳輸時延，Dj表示第j個源節點成功傳輸到達根節點的數據包數量。

(4)根節點平均吞吐量

根節點平均吞吐量被定義為在一定時間內根節點成功接收到的總的數據包比特數，計算公式為

(12)

式中：ps表示成功到達根節點的數據包比特數，T表示網絡運行的時間。

3.3 仿真結果分析

3.3.1 數據包投遞率

由圖4可知，3種路由協議的PDR均隨著網絡規模的擴大呈下降趨勢。但是，LB-RPL路由協議的PDR明顯高于RPL-OF0和ETX-RPL路由協議，分析其主要原因有以下兩點：①在DODAG構建的過程中，LB-RPL路由協議在計算度量值的過程中綜合考慮了多種路由判據，譬如鏈路質量、節點緩存占用率和中繼節點當前子節點數量，能夠最大化地實現負載均衡，從而有效地降低了節點因高負載而導致的丟包數量；②LB-RPL路由協議在選擇最優父節點的過程中依據整條路徑的數據傳輸代價，能夠有效地降低數據包從源節點到達sink節點整條路徑上的丟包概率。

圖4 數據包投遞率

3.3.2 網絡生存時間

從圖5中可以發現，隨著網絡規模的擴大，RPL-OF0、ETX-RPL和LB-RPL路由協議的網絡生存時間均逐漸降低，但LB-RPL路由協議的網絡生存時間明顯高于RPL-OF0和ETX-RPL路由協議。分析其主要原因有以下3點：①在選擇備選父節點的過程中，LB-RPL路由協議將節點當前剩余能量和節點當前緩存占用率進行了有效地融合，其中考慮節點當前剩余能量能夠避免將剩余能量不足的節點選作為備選父節點，而考慮節點的緩存占用率，能夠延長高負載節點的能耗；②LB-RPL路由協議在計算度量值的過程中綜合考慮多種路由判據能夠有效地提高數據包的投遞率，從而降低了數據包因丟包而重傳的能耗；③LB-RPL路由協議依據整條路徑的數據傳輸代價進行最優父節點的選擇，能夠有效地降低整條路徑上的節點能耗。

圖5 網絡生存時間

3.3.3 平均端到端時延

圖6表明，LB-RPL路由協議的平均端到端時延在隨著網絡規模的擴大的過程中均低于RPL-OF0和ETX-RPL路由協議。分析其主要原因有以下3點：①在網絡拓撲的組建過程中，LB-RPL路由協議將節點當前緩存占用率有效地考慮到其中，能夠有效地降低重負載節點出現的概率，從而縮短了排隊時延；②LB-RPL路由協議通過結合多種路由判據能夠最大化地實現網絡負載均衡，提高了數據包的投遞率，從而降低了節點因丟包重傳而耗費的時間；③在選擇最優父節點的過程中，LB-RPL路由協議依據整條路徑的數據傳輸代價能夠有效地降低數據整體端到端傳輸時延。

圖6 平均端到端時延

3.3.4 根節點平均吞吐量

由圖7可知，根節點的平均吞吐量隨著網絡規模的擴大均逐漸增大，其中LB-RPL路由協議的根節點平均吞吐量明顯高于RPL-OF0和ETX-RPL路由協議。分析其主要原因在于LB-RPL路由協議在DODAG的構建過程中將多種路由判據有效結合能夠最大化地均衡網絡負載，降低了數據包的丟包率；其次，在計算路由度量值的過程中，LB-RPL路由協議將節點當前緩存占用率考慮其中，從而對數據包的排隊時延有縮減趨勢，以及降低了數據包因緩存而導致丟包重傳的次數，故其根節點平均吞吐量相比較于RPL-OF0和ETX-RPL路由協議有所提高。

圖7 根節點平均吞吐量

4 結束語

本文針對LLN中現有單路徑RPL路由協議在DODAG構建過程中，僅考慮一跳范圍之間的數據傳輸代價而未考慮整條路徑上的傳輸代價，導致不能有效地均衡節點能耗以及延長網絡壽命等問題，提出一種基于負載均衡的單路徑LLN路由協議(LB-RPL)。該協議從3個方面進行了改進：首先，在選擇備選父節點的過程中對無線鏈路質量、節點剩余能量和緩存占用率進行限制；其次，在度量值的計算過程中將多種路由判據有效地結合，旨在避免單一路由判據對網絡性能產生的影響；最后，依據整條路徑上的數據傳輸代價進行最優父節點的選擇。仿真結果表明，LB-RPL路由協議在均衡節點能耗方面有一定的改善，且能夠有效地延長網絡生存時間以及相應地提高數據傳輸的可靠性。在未來的工作中，我們將研究LLN中基于負載均衡的多路徑RPL路由協議。