高負載場景下基于負載均衡的LLN路由協議

秦 峰，曾 浩，2，林開東

1.重慶郵電大學 通信與信息工程學院，重慶400065

2.重慶郵電大學 電工理論與新技術實驗室，重慶400065

1 引言

低功耗有損網絡（Low-power and Lossy Networks，LLN）[1-2]被認為是一種特殊的無線傳感器網絡，在物聯網[3-4]等領域中具有廣泛的應用前景。LLN 通常由大量的嵌入式設備組成，然而組成LLN 的這些嵌入式設備往往受到一定的限制，譬如能量供應不足，存儲空間較小和處理能力較弱。因此，鑒于LLN 的廣泛應用前景和其特有的性質，設計出一種適用于LLN 的路由協議顯得尤為重要。

2008 年，國際互聯網任務工程組制定了一種基于IPv6 的低功耗有損網絡路由協議（Routing Protocol for Low-power and Lossy network，RPL）[5]。RPL是一種基于距離矢量的先驗式路由協議，由根節點發起并逐級完成整個面向目的地的有向無環圖（Destination Oriented Directed Acyclic Graph，DODAG）的構建。此外，DODAG中的每個嵌入式設備均需要定期廣播DODAG 信息對象消息（DODAG Information Object，DIO），該消息主要用于維護網絡拓撲結構的穩定性，且該消息的發送周期間隔由溪流計時器[6]控制。

目前，學術界對RPL 已展開了大量研究工作。文獻[7]在構建DODAG時將傳輸跳數作為路由度量，能夠在一定程度上提高數據傳輸的實時性，但忽略了數據傳輸的可靠性。文獻[8]在構建DODAG 時將期望傳輸次數作為路由度量，能夠對數據傳輸的可靠性有一定提升，卻忽略了數據傳輸的實時性。尤其是在高負載場景下，依據文獻[7]和[8]中的路由度量所構建的DODAG均無法較好地實現網絡負載均衡，將會對網絡各方面的性能造成嚴重的影響。

為了減少在構建DODAG 時僅考慮節點一跳范圍內的期望傳輸次數所產生的能量瓶頸節點的數量，文獻[9]在構建DODAG 的過程中考慮了當前節點至根節點整條傳輸路徑上的期望傳輸次數，在一定程度上能夠減少能量瓶頸節點產生的數量，但效果不是很顯著。文獻[10]在構建DODAG 的過程中，綜合考慮了當前節點至根節點整條路徑上的期望傳輸次數和節點轉發數據包的概率，即根據當前節點至根節點整條路徑的數據傳輸代價進行最優父節點的選擇。此種方式雖然能夠在整體上降低數據的傳輸代價，卻未考慮負載不均衡對網絡性能所產生的負面影響。文獻[11]在單路徑RPL協議的基礎上，提出了一種多路徑RPL協議。該協議為了降低網絡中能量瓶頸節點的能耗速率，節點在傳輸數據時根據每條路徑中能量瓶頸節點的期望壽命進行數據流量的分配，并實現數據的分流傳輸。該協議能夠在一定程度對網絡整體壽命進行延長，但忽略了數據傳輸的可靠性。文獻[12]在構建DODAG的過程中綜合考慮了節點的期望傳輸次數和節點剩余能量，在保證數據傳輸可靠性的前提下，能夠避免剩余能量不足的節點被選作為最優父節點。

當檢測到節點發生網絡擁塞時，文獻[13-14]均通過周期性廣播的DIO 控制消息將網絡擁塞狀態通告給網絡中的其他節點，并進一步對當前網絡擁塞進行處理。然而，當網絡拓撲結構相對穩定時，DIO 控制消息的發送周期間隔相對較大，故通過周期性廣播的DIO控制消息無法快速地將節點的網絡擁塞狀態通告給網絡中的其他節點，從而影響當前網絡擁塞的處理。文獻[15]針對文獻[13-14]中存在的問題，通過對溪流計時器的重置便可快速的將節點當前的網絡擁塞狀態通告給網絡中的其他節點。然而，多次的將溪流計時器重置將會增加大量不必要的控制開銷，且對數據的傳輸也會產生一定的影響。

2 網絡模型和問題描述

2.1 網絡模型

如圖1 所示為HSLB-RPL 協議的網絡拓撲模型圖。其中，sink 節點也被稱之為根節點，主要用于對下游節點向上游節點傳輸的數據流量進行匯聚；R1～R8為中繼節點，主要用于轉發所有葉子節點所產生的數據流量；S1～S7為葉子節點，主要用于產生數據流量，并向上游節點傳輸所產生的數據流量。

圖1 HSLB-RPL協議網絡模型

關于HSLB-RPL協議的網絡模型有如下假設：

（1）網絡中所有節點的物理構造、屬性和性質均相同，其中根節點除外。

（2）為了盡可能保證網絡的穩定性，網絡中所有節點均工作于靜態模式下。

（3）雖然節點的存儲空間受限，但網絡中每個節點均有足夠的隊列空間對路由表項進行緩存。

（4）網絡中每個節點既可作為消息的發布者，也可作為消息的接收者。

2.2 問題描述

通過深入研究發現，在高負載場景下已有RPL協議存在以下幾個問題：

（1）在DODAG 的構建過程中，節點在選擇最優父節點時通常僅考慮與其備選父節點之間的期望傳輸次數，而未考慮其備選父節點與其備選父節點的上一跳節點之間的期望傳輸次數，使得擁有期望傳輸次數較大的父節點的節點被其鄰居節點選作為最優父節點的概率增大，從而導致節點所選擇的最優父節點并非最優。

（2）當檢測到網絡中某些節點的負載較重時，并未對此類節點的DIO 控制消息的廣播周期間隔進行一定調整，從而導致此類節點的負載極有可能持續加重，且加快了此類節點的能耗速率，并對數據的傳輸造成了一定的影響。

（3）在數據傳輸過程中，當檢測到網絡中節點出現網絡擁塞時，利用周期性廣播的DIO控制消息無法及時的將當前網絡擁塞節點的網絡擁塞狀態通告給其鄰居節點。此外，重置溪流計時器雖然能夠盡快的將當前網絡擁塞節點的網絡擁塞狀態通告給其鄰居節點，但會增加大量不必要的控制開銷，且對數據的傳輸也會造成一定的影響。

為了解決上述問題，本文提出了一種高負載場景下基于負載均衡的LLN 路由協議（HSLB-RPL）。該協議包含3 種改進策略：（1）最優父節點選擇策略。為了避免擁有期望傳輸次數較大的父節點的備選父節點被其鄰居節點選作為最優父節點，綜合考慮當前備選節點和其父節點的期望傳輸次數。（2）溪流計時器調整策略。當檢測到節點負載較重時，為了降低其被鄰居節點選作為最優父節點的概率，對其DIO控制消息的發送時間間隔進行一定調整。（3）網絡擁塞狀態通告策略。當檢測到節點發生網絡擁塞時，設計一種網絡擁塞通告消息（NCN），及時將當前網絡擁塞狀態通告給其鄰居節點。

3 HSLB-RPL協議

3.1 最優父節點選擇策略

在DODAG 構建過程中，節點在選擇最優父節點時，通常會依據不同的路由度量對最優父節點進行確定，譬如傳輸跳數、節點剩余能量、期望傳輸次數和節點緩存占用率等。其中，傳輸跳數能夠大致反映數據傳輸的實時性；期望傳輸次數能夠大致反映數據傳輸的可靠性。為了兼顧數據傳輸的可靠性和實時性，本文將結合傳輸跳數和期望傳輸次數兩種路由度量。

此外，最優父節點選擇策略的核心之處在于，節點在選擇最優父節點時，不僅需要考慮與當前一跳范圍內的備選父節點之間的期望傳輸次數，而且還需要考慮其備選父節點與其備選父節點上一跳節點之間的期望傳輸次數，降低期望傳輸次數較高的備選父節點被選作為最優父節點的概率，從而達到均衡網絡負載的目的。以節點k 為例，其當前擁有兩個備選父節點m 和n ，那么，節點k 在選擇最優父節點時的具體實施步驟如下：

步驟1 節點k 的備選父節點m 和n 分別計算各自的期望傳輸次數。期望傳輸次數為節點間無線鏈路質量的倒數，表示節點成功傳輸一個數據包到達其父節點需要傳輸的平均次數，其計算如公式（1）所示：

步驟2 節點m 和n 分別將各自的期望傳輸次數與各自的傳輸跳數進行匯聚處理[15]，并通過周期性廣播的DIO控制消息中的RANK字段攜帶匯聚處理后的結果，并將匯聚后的結果通告給節點k。期望傳輸次數與傳輸跳數匯聚處理如公式（3）所示：

步驟3 節點k 接收到節點m 和n 廣播的DIO控制消息后，分別解析出節點m 和n 的傳輸跳數和期望傳輸次數。期望傳輸次數與傳輸跳數解析處理如公式（3）和公式（4）所示：

步驟4 節點k 解析出節點m 和n 的期望傳輸次數后，判斷是否需要對與節點m 和n 之間的期望傳輸次數進行調整，其調整如公式（5）所示：

步驟5 節點k 分別計算與節點m 和n 之間的路由度量值，并選擇路由度量值較小的節點作為最優父節點。路由度量值的計算如公式（6）所示：

3.2 溪流計時器調整策略

在RPL協議中，DIO控制消息的發送間隔由溪流計時器控制，可通過調整溪流計時器實現對DIO控制消息進行周期性的發送。當檢測到網絡出現不一致（網絡結構發生較大變化）時，溪流計時器通常會被重置，從而使得節點更快的適應網絡的變化；而當網絡拓撲結構較為穩定時，DIO 控制消息的發送時間間隔將會逐漸增大，從而避免不必要的控制開銷。因此，為了降低負載較重節點被其鄰居節點選作為最優父節點的概率，對溪流計時器發送DIO控制消息的策略進行一定改進，即根據節點的負載狀態適當延長DIO 控制消息的發送間隔。溪流計時器調整策略實施具體流程，如圖2所示。

圖2 溪流計時器調整策略

溪流計時器中用到的主要參數如下：

（1）Imin：發送DIO控制消息的最小時間間隔長度。

（2）Imax：發送DIO控制消息的最大時間間隔長度。

（3）k：冗余常量。

（4）I ：當前DIO控制消息發送的時間間隔長度。

（5）t：時間值，介于[I/2,I]之間。

（6）c：冗余計數器。

那么，溪流計時器調整策略的具體實施步驟如下：

步驟1 網絡初始化時，將I 設置為介于[Imin,Imax]之間的任意一個值，并開始第一個時隙。

步驟2 將冗余計數器c 的值初始化為0，t 設置為介于[I/2,I]之間的任意一個值，該時隙終止于I 處。

步驟3 Trickle定時器每接收到一個“一致性”傳輸，則將冗余計數器c 的值自增1。

步驟4 在時刻t 時，Trickle定時器檢查冗余計數器c 的值是否小于冗余常量k。如果c ＜k，再判斷當前節點的隊列利用率是否超過預設的閾值，所預設的閾值大小為0.6。如果當前節點的隊列利用率超過預設的閾值，Trickle 定時器將會延長DIO 控制消息的發送間隔，則將其發送間隔增大1 倍；反之，則當前節點可以向其鄰居節點廣播DIO 控制消息。如果c ＞k ，則當前節點被禁止向其鄰居節點廣播DIO控制消息。

步驟5 當時隙I 結束后，將I 的值增大到原來的兩倍，并重復步驟2。如果加倍后的I 大于Imax，則將I 的取值設置為Imax。

步驟6 一旦接收到“不一致”傳輸時，Trickle定時器立刻被重置，即將c 的值重新歸位于0，并將時間間隔I設置為Imin并重復步驟3，直至網絡運行時間結束。

3.3 網絡擁塞狀態通告策略

通常，當檢測到網絡中的節點處于網絡擁塞狀態時，需要網絡擁塞節點將當前的網絡擁塞狀態通告給其子節點，以便其子節點對當前的網絡擁塞進行一定處理，譬如對當前數據的傳輸路徑進行更換或是調整當前數據包的傳輸速率。在RPL協議中，通用方式是利用周期性廣播的DIO控制消息攜帶節點當前網絡擁塞狀態，并將節點當前網絡擁塞狀態通告給其子節點。然而，此種方式并不能及時的將節點當前網絡擁塞狀態通告給其子節點和鄰居節點；此外，通過重置溪流計時器雖然能夠快速地對節點當前網絡擁塞狀態進行通告，但是，此操作會導致DIO控制消息的發送間隔變小，從而增加了大量不必要的控制開銷，且會對數據的傳輸造成一定的影響。

為了盡量減少不必要的控制開銷，并且能夠及時地將節點當前網絡擁塞狀態通告給其子節點和鄰居節點，設計了一種新的網絡擁塞通告控制消息（NCN）。NCN控制消息的幀格式與DIO控制消息的幀格式區別不大，除了消息的類型不同之外，在NCN 控制消息中新增了網絡擁塞狀態（NC）字段。為了避免增加NCN 控制消息的大小，利用其保留字段中的1 bit 設置為NC 字段。當該字段的值為1 時，表明當前節點處于網絡擁塞狀態；反之，當前節點處于正常狀態。因此，當節點檢測其當前處于網絡擁塞狀態時，無需對溪流計時器進行重置，僅需向其子節點組播NCN 控制消息便可及時地實現網絡擁塞狀態通告的目的。

4 性能評估

為了驗證HSLB-RPL協議的性能，本文采用Contiki 2.7操作系統中的Cooja 仿真器對文獻[8]、文獻[10]所提協議以及本文所提協議進行模擬仿真，并對它們以下三種性能指標分別進行對比和分析。

（1）網絡平均壽命：以網絡中最先死亡的節點的生存時間作為網絡平均壽命，其中死亡節點是指當前剩余能量僅為初始能量的1%的節點。

（2）根節點平均吞吐量：根節點平均吞吐量表示為在單位時間內網絡中成功傳輸的數據包的數量，是衡量LLN網絡性能的一項重要指標。

（3）歸一化控制開銷：歸一化控制開銷是指在網絡運行時間內，網絡中所有節點傳輸的控制消息比特數與網絡中所有節點傳輸的控制消息比特數和根節點接收的數據包比特數的比值。

4.1 仿真環境

在200 m×200 m 的仿真區域構建節點數為21 且節點隨機分布的LLN 網絡，其中根節點的數量為1，普通節點的數量為20。此外，根節點的初始能量不受限制，而普通節點的初始能量將會受到一定限制。本文所提協議與其他兩種對比協議采用相同的網絡模型，且為了網絡模型的穩定性，其中所有節點均工作于靜態模式。模擬仿真過程中用到的主要仿真參數如表1所示。

表1 仿真參數設置

4.2 性能分析

4.2.1 網絡平均壽命

如圖3表明，隨著節點數據包傳輸速率增加，HSLBRPL 協議的網絡平均壽命均比文獻[8]和文獻[10]協議高，且至少提升了23.57%。分析其原因主要體現在以下三點：（1）HSLB-RPL 協議中，在構建DODAG 時，綜合考慮了當前節點與其備選父節點之間的期望傳輸次數以及其備選父節點與其備選父節點上一跳節點之間的期望傳輸次數，能夠避免期望傳輸次數較大的備選父節點被選作為最優父節點，從而降低了節點因數據包重傳所耗費的能量。（2）在數據傳輸過程中，當檢測到節點負載較重時，對其DIO控制消息的發送時間間隔進行調整，能夠降低此類重負載節點被其鄰居節點選作為最優父節點的概率，從而避免了此類重負載節點的能耗速率持續增加。（3）當節點發生網絡擁塞時，設計了一種網絡擁塞通告消息（NCN），能夠避免重置溪流計時器所產生大量不必要控制開銷，同時還能夠將節點當前網絡擁塞狀態及時地通告給其子節點和鄰居節點，從而加快了當前網絡擁塞的緩解，降低了網絡擁塞節點的能耗。

圖3 網絡平均壽命比較

4.2.2 根節點平均吞吐量

從圖4 中發現，隨著節點數據包傳輸速率的增加，HSLB-RPL 協議的根節點平均吞吐量均比文獻[8]和文獻[10]協議高，且至少提升了14.52%。通過分析發現其主要原因在于：HSLB-RPL 協議中，在構建DODAG 時，綜合考慮了當前節點與其備選父節點之間的期望傳輸次數以及其備選父節點與其備選父節點上一跳節點之間的期望傳輸次數，能夠避免期望傳輸次數較大的備選父節點被選作為最優父節點，從而有效地降低了數據包的重傳次數；當檢測到網絡中節點發生網絡擁塞時，設計了一種網絡擁塞通告消息（NCN），能夠避免重置溪流計時器產生大量不必要控制消息，同時能夠及時地將節點當前網絡擁塞狀態通告給其子節點和鄰居節點，從而有效地避免了重置溪流計時器對數據傳輸的影響。

圖4 根節點平均吞吐量比較

4.2.3 歸一化控制開銷

如圖5顯示，隨著節點數據包傳輸速率的增加，HSLBRPL 協議的歸一化控制開銷均比文獻[8]和文獻[10]協議低，且至少降低了12.87%。分析其原因主要有以下兩點：（1）HSLB-RPL協議中，在構建DODAG時，綜合考慮了當前節點與其備選父節點之間的期望傳輸次數以及其備選父節點與其備選父節點上一跳節點之間的期望傳輸次數，能夠避免期望傳輸次數較大的備選父節點被選作為最優父節點，從而有效地降低了數據包的重傳次數。（2）HSLB-RPL協議中，當檢測到網絡中節點發生網絡擁塞時，設計了一種網絡擁塞通告消息（NCN），能夠避免重置溪流計時器所產生大量不必要控制消息，同時還能夠及時地將當前網絡擁塞狀態通告給其子節點和鄰居節點，從而有效地降低了當前網絡擁塞狀態通告的控制開銷，并減少了數據傳輸帶寬的占用。

圖4 歸一化控制開銷比較

5 結論

本文提出了一種高負載場景下基于負載均衡的LLN路由協議（HSLB-RPL）。HSLB-RPL協議包含三種策略：（1）最優父節點選擇策略，在組網的過程中，聯合節點傳輸跳數和期望傳輸次數兩種路由度量；（2）溪流計時器調整策略，在數據傳輸過程中，對重負載節點的DIO 控制消息的發送周期進行一定調整；（3）網絡擁塞狀態通告策略，當檢測到網絡發生擁塞時，通過NCN控制消息及時地將當前網絡擁塞狀態進行通告。仿真結果表明，HSLB-RPL協議能夠有效地改善網絡各方面的性能。在今后的工作中，基于動態網絡場景下的負載均衡將是研究的重點。