基于負載均衡的高能效LLN路由協議

黃 欣 趙志剛

1(廣西農業職業技術學院網絡信息中心 廣西 南寧 530007)2(廣西大學計算機與電子信息學院 廣西 南寧 530004)

0 引 言

低功耗有損網絡LLN[1]通常是由幾十、幾百甚至成千上萬個嵌入式網絡設備所組成的網絡，在智能電網[2]、工業控制[3]和物聯網[4]等領域具有廣闊地應用前景。在電氣電子工程師協會IEEE、國際互聯網工程任務組IETF以及Zigbee等標準化組織的支持下，物聯網系統現已擁有多種應用于大規模部署的協議和標準。其中，IETF提出的一種基于IPv6的LLN路由協議RPL(IPv6-based Routing Protocol for LLN)[5]成為了當下的研究熱點。

然而，由于LLN的網絡結構呈樹形且LLN中的嵌入式設備通常是由能量受限的無線傳感器節點組成，從而極易因負載不均衡導致能量瓶頸節點的出現，一旦未對能量瓶頸節點及時處理，將會對網絡各方面性能產生嚴重影響。因此，在LLN中如何有效地解決能量瓶頸節點的問題，以及最大化地均衡節點能耗具有極其重要的研究價值。

1 相關工作

目前，針對LLN的負載均衡方面已經取得了大量的研究成果。文獻[6]在組網的過程中將緩存占用率作為選擇最優父節點的路由度量，雖然能夠提高網絡吞吐量，但是由于未考慮節點的剩余能量，從而無法有效均衡節點能耗。為了避免選擇重負載節點作為最優父節點，文獻[7]同樣參考了緩存占用率。此外，當網絡擁塞出現時，通過對溪流計時器(Trickle timer)[8]重置策略的改進，使得網絡擁塞節點的子節點以一定概率進行切換，但是其同樣未考慮節點剩余能量以及未考慮節點因負載較重而出現能量瓶頸狀態的情況。文獻[9]在組網的過程中考慮了多種路由度量，其中包括節點剩余能量，但同樣未考慮高負載場景下能量瓶頸節點出現的情況以及對其提出相關解決方法。文獻[10]中將節點剩余能量作為構建路由的判據，能夠有效減輕剩余能量不足節點的負載。但是，一旦剩余能量充足但鏈路質量較差的節點被選作為最優父節點時，將會使此類節點的能耗速率加快。為了彌補文獻[10]中的缺陷，文獻[11]在組網時結合了期望傳輸次數和節點剩余能量，可以有效避免剩余能量相對充足但無線鏈路質量相對較差的節點被選作為最優父節點。為了延長網絡生存時間，文獻[12]中通對節點所需傳輸的數據流量按比例分配進行多路徑傳輸，旨在使網絡中瓶頸節點的能耗均衡，其不足在于增添了額外控制開銷且未考慮如何處理網絡中出現剩余能量不足節點的情況。文獻[13]提出了一種機會RPL路由算法ORPL(Opportunistic Routing Protocol for LLN)。該算法根據節點當前剩余能量和通信忙閑程度對其休眠間隔進行一定調整，但是該算法會導致剩余能量充足的節點擁有大量的子節點，從而加快了其能耗速率。文獻[14]提出了一種基于期望壽命與能量消耗的RPL路由協議ELT-BE-RPL(Expected Life Time Balance Energy based Routing Protocol for LLN)，該協議將節點期望壽命作為路由度量，在選擇最優父節點時采用最大最小原則，從而最小化每條路徑上的剩余能量最小節點的能耗速率。

綜上所述，現有研究并未對網絡中的能量瓶頸節點進行考慮，也并未對此種情況進行處理。因此，為了盡量避免網絡中出現的能量瓶頸節點對網絡性能造成嚴重影響，本文提出了一種基于負載均衡的高能效RPL路由協議LBEE-RPL。

2 網絡模型

如圖1所示，LLN是由大量無線傳感器節點所組成且呈樹形結構。其中，節點共包括3種類型：根節點、能量瓶頸節點和普通節點。根節點主要功能是進行數據的匯聚，通常其能量不受限制；能量瓶頸節點的主要特征在于其剩余能量不足，即將處于能量耗盡的狀態；普通節點的主要功能在于數據的收集和轉發，初始能量有限且自始自終均不能補充。此外，本文研究的對象均處于靜態，即節點的位置一旦被確定，將不再改變其所處的位置。

圖1 LLN網絡模型圖

為了便于闡述，本文給出以下幾個定義：

定義1能量閾值：網絡中節點(除根節點外)的剩余能量與自身初始能量的比值為0.2時，此節點當前剩余能量被稱為能量閾值。

定義2期望壽命閾值：網絡中節點的當前期望壽命與節點初始期望壽命的比值為10%時，此節點當前期望壽命被稱之為期望壽命閾值。

定義3期望壽命安全閾值：網絡中節點的當前期望壽命與節點初始期望壽命的比值為30%時，此節點當前期望壽命被稱之為期望壽命安全閾值。

定義4能量瓶頸節點：當節點的期望壽命第一次低于期望壽命閾值或是節點的剩余能量低于能量閾值時，此節點為能量瓶頸節點；如果節點的期望壽命并非第一次低于期望壽命閾值，則只有當此節點的剩余能量低于能量閾值時，此節點才被稱之為能量瓶頸節點。

定義5死亡節點：當網絡中節點的剩余能量低于節點初始化時能量的1%時，此節點被稱之為死亡節點。

3 改進的路由協議

本文提出的路由協議進行了如下改進：

(1) 提出一種Trickle timer重置改進策略，即一旦當網絡中的節點處于能量瓶頸狀態時，通過對Trickle timer的重置策略進行改進，從而將能量瓶頸節點的能量狀態盡快通告給其子節點和鄰居節點。

(2) 提出一種能量瓶頸節點的子節點切換機制，即能量瓶頸節點采用集中式的方式決定其子節點的切換，旨在降低能量瓶頸節點的能耗，從而延長網絡生存時間。

3.1 Trickle timer重置改進策略

在RPL標準[5]中，面向目的地的有向無循環圖DODAG(Destination Oriented Directed Acyclic Graph)信息對象消息DIO(DODAG Information Object)主要用于上行路由的構建和網絡拓撲的維護，其發送由Trickle timer[8]控制。而在現有DIO控制消息的發送策略中，僅當網絡拓撲結構發生重大變化時Trickle timer才會被重置，否則DIO控制消息的發送周期將會成倍遞增。因此，當檢測到網絡中節點處于能量瓶頸狀態時，由于Trickle timer控制發送DIO控制消息的時間間隔較大，將會延遲節點能量瓶頸狀態的通告，從而加快了能量瓶頸節點的死亡速率。

當網絡中的節點第一次處于能量瓶頸狀態不是因其剩余能量不足所導致時，若對能量瓶頸節點的子節點進行部分切換，能量瓶頸節點的當前期望壽命將會高于期望壽命閾值，則當前能量瓶頸節點便能夠快速地解除能量瓶頸狀態。但是，隨著時間的推移，該節點可能再次出現期望壽命低于期望壽命閾值的情況。如果一旦上述情況發生就對Trickle timer進行重置，將會增加大量額外控制開銷。因此，當檢測到網絡中的節點處于能量瓶頸狀態時，應當判斷該節點處于能量瓶頸狀態是由于節點負載較重所導致還是由于節點當前剩余能量過低所導致。如果節點處于能量瓶頸狀態是因為當前剩余能量過低所導致，那么Trickle timer至始至終僅需被重置一次；如果節點處于能量瓶頸狀態是因為節點負載較重所導致，那么Trickle timer的重置需要考慮多種情況。首先，判斷該能量瓶頸節點是否是首次出現能量瓶頸狀態。如果是，則立即對Trickle timer進行重置；否則，只有當該能量瓶頸節點的剩余能量低于能量閾值時Trickle timer才被重置。Trickle timer的重置改進策略的具體實施過程如圖2所示。

圖2 Trickle timer重置改進流程圖

Trickle timer重置改進策略的具體實施步驟如下：

步驟1當網絡拓撲初始化構建開始時，每個節點用C(n)統計自身出現能量瓶頸狀態的次數，并將其值初始化設置為0。

步驟2網絡拓撲初始化構建結束后，每當節點檢測到自身處于能量瓶頸狀態時，便將統計量C(n)自增1。

步驟3節點根據自身C(n)的值判定是否第一次處于能量瓶頸狀態。如果C(n)=1，則表明當前節點是第一次處于能量瓶頸狀態，則進入步驟4；否則，進入步驟7。

步驟4該能量瓶頸節點立刻重置Trickle timer，及時通過廣播DIO控制消息將其能量瓶頸狀態通告給其子節點和鄰居節點。

步驟5能量瓶頸節點的子節點接收到上述DIO控制消息后，按照下一小節中的能量瓶頸節點子節點切換機制對能量瓶頸節點子節點的數據傳輸路徑進行更換；能量瓶頸節點的鄰居節點接收到上述DIO控制消息后，記錄下能量瓶頸節點的能量狀態。

步驟6對能量瓶頸節點的子節點進行處理后，判斷該節點的剩余能量是否小于預設的能量閾值。如果該節點的剩余能量小于預設的能量閾值，則結束；反之，則返回至步驟2。

步驟7判斷該節點剩余能量是否小于預設的能量閾值。如果該節點剩余能量小于預設的能量閾值，則立刻重置Trickle timer；反之，則解除當前節點的能量瓶頸狀態，并返回至步驟2。

3.2 能量瓶頸節點的子節點切換機制

為了更好地使能量瓶頸節點的子節點獲知該能量瓶頸節點的能量瓶頸狀態信息以及不增加額外的控制開銷，利用DIO控制消息中的保留字段中的第1 bit，將其設置為節點能量瓶頸狀態字段，用S表示。當該字段的值為1時，表明當前節點處于能量瓶頸狀態；當該字段的值為0時，則表明當前節點處于能量充足狀態。

網絡中的節點通過周期性廣播的DIO控制消息將自身備選父節點的剩余能量狀態信息共享給父節點，利用DIO控制消息的保留字段中的第2 bit，將其設置為節點備選父節點的能量瓶頸狀態字段，用B表示。當該字段的值為1時，則表明節點的備選父節點處于能量瓶頸狀態；當該字段的值為0，則表明節點的備選父節點處于能量充足狀態。因此，能量瓶頸節點通過接收到其子節點周期性廣播的DIO控制消息便能獲知它所有子節點的備選父節點的剩余能量狀態信息。但是，在能量瓶頸節點的子節點切換過程中，其子節點可能同時切換到另外一個節點，發生“羊群效應”，從而增大了該節點出現能量瓶頸狀態的概率，且極有可能導致網絡出現震蕩現象。為了避免能量瓶頸節點的子節點在切換的過程中出現“羊群效應”，因而制定了一種完善的能量瓶頸節點的子節點切換機制，其具體實施過程如下：

步驟1當檢測到LLN網絡中出現能量瓶頸節點時，判斷該節點是否是首次出現能量瓶頸狀態。如果非首次出現，則進入步驟8；反之，則進入步驟2。

步驟2判斷該能量瓶頸節點出現能量瓶頸狀態的原因。如果能量瓶頸節點的能量瓶頸狀態不是因為節點當前剩余能量低于節點能量閾值所引起，則進入步驟5；反之，則進入步驟3。

步驟3只要該能量瓶頸節點子節點的備選父節點的剩余能量高于能量安全閾值，該能量瓶頸節點就將這類子節點添加到子節點切換列表中，并將子節點切換列表添加到DIO控制消息的選項字段中，同時將DIO控制消息中的EBS字段的值設置為1，通過廣播該DIO控制消息通告給其子節點。

步驟4能量瓶頸節點的子節點接收到上述DIO控制消息后，首先檢查DIO控制消息中的S字段，如果該字段的值為0，則表明子節點當前父節點處于能量充足狀態，并按照常規的路由判據決定是否需要切換當前父節點；如果該字段的值為1，表明節點當前父節點處于能量瓶頸狀態，于是該節點從接收到的能量瓶頸節點廣播的DIO控制消息的選項字段中提取出子節點切換列表，并查看其中是否包含自身信息。如果包含其自身信息，則在內存中將當前父節點標記為能量瓶頸狀態，并從其父節點列表中刪除當前能量瓶頸節點的信息，同時從父節點列表中選取一個備選父節點作為新的父節點，并將原父節點的瓶頸狀態信息通過DIO控制消息通告給新的父節點；反之，若不包含其自身信息，則繼續與能量瓶頸節點保持連狀態。

步驟5能量瓶頸節點將可切換的子節點按照節點發包率的大小由高到低排序，依次計算排除掉需切換的子節點后的能量瓶頸節點新的期望壽命，直至能量瓶頸節點新的期望壽命高于期望壽命安全閾值，達到解除能量瓶頸狀態的目的為止，并將排除掉的子節點添加到子節點切換列表中。若切換掉所有可切換的子節點后，能量瓶頸節點的期望壽命依舊低于期望壽命安全閾值，那么只有切換掉滿足切換條件的當前所有子節點。

步驟6能量瓶頸節點將其子節點切換列表添加到DIO控制消息的選項字段中，同時將DIO控制消息中的S字段的值設置為1，通過廣播該DIO控制消息通告給其子節點。

步驟7能量瓶頸節點的子節點接收到上述DIO控制消息后，重復步驟4。

步驟8判斷該節點出現能量瓶頸狀態的原因。如果該節點出現能量瓶頸狀態是因為節點當前期望壽命小于節點期望壽命閾值，為了避免增加額外的控制開銷以及避免網絡拓撲結構頻繁的發生變化，因此將對其不作任何處理，直到其剩余能量低于能量閾值時，返回至步驟3；如果能量瓶頸節點出現能量瓶頸狀態是因為節點當前剩余能量低于節點能量閾值所引起，則直接返回至步驟3。

在瓶頸節點的子節點切換策略執行過程中，如果已切換的子節點的當前父節點因后續出現能量瓶頸狀態而再度切回到先前能量瓶頸狀態節點，那么會導致先前能量瓶頸節點再度快速地出現能量瓶頸狀態。因此，每個因為先前父節點處于能量瓶頸狀態而切換的子節點均需記錄先前父節點的能量瓶頸狀態信息，并將其通過DIO控制消息共享給當前父節點。

4 仿真實驗及結果分析

采用Contiki 2.7仿真軟件對本文方法各方面網絡性能進行模擬仿真驗證，并選取ORPL[13]和ELT-BE-RPL[14]在相同仿真模擬場景下進行比較分析，主要對比分析了網絡生存時間、節點死亡率和根節點平均吞吐量三個方面的性能。

4.1 仿真環境及參數設置

在500 m×500 m的仿真區域內根據節點數量不同設置6種不同的模擬仿真場景，網絡規模大小分別為30、50、70、90、110和130，仿真周期為4 800 s，每個場景中節點隨機分布且位置固定，除根節點外，其余所有節點的能量均受限，初始能量為10 J，且在仿真過程中不補給能量。節點的發包速率介于1 pkt/s到4 pkt/s之間，且每個數據包的大小均為1 500 B。節點的最大發射功率為50 MW，發送單位比特數據的能耗為65 nJ/bit。

4.2 仿真結果分析

圖3為網絡生存時間的對比。網絡生存時間是指網絡中首次出現死亡節點所耗費的時間。從圖3中可以發現，隨著網絡規模的不斷擴大，與ORPL和ELT-BE-RPL相比，本文方法的網絡生存時間至少能夠提升10.53%。其主要原因有以下兩點：(1) 當檢測網絡中出現能量瓶頸節點時，通過對Trickle timer重置策略進行改進，能夠及時將節點能量瓶頸狀態通告給其子節點，從而迅速地對能量瓶頸節點的子節點進行處理；(2) 能量瓶頸節點的子節點切換機制能夠使得能量瓶頸節點的負載減輕，有效地降低能量瓶頸節點的能耗速率，從而延長了能量瓶頸節點的生存時間。

圖3 網絡生存時間比較

圖4所示為節點死亡率的對比。節點死亡率是指在網絡運行時間內網絡中的死亡節點數與網絡中總的節點數的比值。從圖4中可以發現，隨著網絡中節點數量的增多，本文方法的節點死亡率均低于ORPL和ELT-BE-RPL，且至少降低了18.59%。其主要原因在于當檢測到LLN中出現能量瓶頸節點后，通過對Trickle timer重置策略的改進，能夠及時地將能量瓶頸節點的能量瓶頸狀態通知給其子節點，進而快速地對能量瓶頸節點子節點進行切換，降低了能量瓶頸節點的能耗速率，從而延長了能量瓶頸節點的生存時間，有效地減少了死亡節點的數量。

圖4 節點死亡率比較

圖5所示為根節點平均吞吐量的對比。根節點平均吞吐量是指根節點在單位時間內平均收到的數據流量。可以發現，3種方法的根節點平均吞吐量均隨著網絡規模的擴大而逐漸張增大。但是本文方法在每種場景中的根節點平均吞吐量均明顯高于ORPL和ELT-BE-RPL，至少提高了8.76%。通過分析發現其主要原因在于當LLN中檢測出能量瓶頸節點后，能夠對能量瓶頸節點的子節點進行快速的處理，有效地延長了網絡生存時間和降低了節點死亡率，從而提高了根節點的平均吞吐量。

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

5 結 語

由于LLN中現有負載均衡路由算法未對檢測出的能量瓶頸節點及時進行處理，進而嚴重影響網絡各方面性能，因此本文提出了改進的路由協議。該協議通過對Trickle timer重置策略的改進，及時將能量瓶頸節點的能量瓶頸狀態通告給其子節點，并進一步快速地對能量瓶頸節點的子節點進行處理，降低了能量瓶頸節點的能耗速率，從而能夠有效地延長能量瓶頸節點的生存時間。理論分析和仿真結果表明，相比較于現有路由算法，本文方法能夠有效延長網絡生存時間、降低節點死亡率和提升根節點平均吞吐量。在接下來的研究中，將重點對動態網絡場景下的能量瓶頸節點進行研究。