一種高能效低時延的LLN路由修復算法

鈕 靖,2，于俊洋3，王秋紅

(1.南陽醫學高等?？茖W校，河南 南陽 473061；2.信陽師范學院 計算機與信息技術學院，河南 信陽 464000；3.河南大學 軟件學院，河南 開封 475001)

1 引 言

低功耗有損網絡[1](Low-power and Lossy Network,LLN)是一種由功耗較低的無線傳感器節點組成且節點間無線鏈路不保證可靠性的多跳網絡，主要有點到點、點到多點和多點到點3種通信模式，其中多點到點的通信模式是近年來的研究熱點。傳統的無線多跳網絡路由協議[2-4]因能耗較大不能滿足LLN網絡的應用需求，因此互聯網工程任務組提出了一種全新的基于IPv6的LLN網絡路由協議(IPv6 based Routing Protocol for LLN,RPL)。由于LLN網絡擁有廣泛的應用場景[5-7]以及固有屬性(不穩定性和有損性)，在外部復雜環境的干擾下極易導致鏈路故障的發生，因此，當檢測到LLN網絡中出現鏈路故障后，為了提高通信的可靠性和實時性，通過路由修復算法對網絡拓撲進行修復具有較高的研究價值。

當前，對于LLN網絡中出現的鏈路故障已開展了一些研究，提出了多種算法[8-11]。但是，現有路由修復算法主要存在以下不足：一是路由修復控制開銷冗余，增大了節點的能耗速率，從而不能達到高能效的目的；二是路由修復時延較大，導致數據包端到端傳輸時延增大，從而影響數據的傳輸；三是鏈路故障修復后的網絡拓撲結構未能達到最佳狀態，主要原因在于對鏈路故障節點的子節點未進一步處理。

為了解決上述所存在的不足，本文提出了一種高能效低時延的LLN網絡路由修復算法(Energy Efficient and Low Delay based Repair Routing Protocol for LLN,EELDR-RPL)，并對其性能進行了理論分析和數值驗證。

2 網絡模型

LLN網絡的拓撲結構不同于傳統的無線傳感器網絡，結合其自身特點，本文給出如下定義：

定義1 備選父節點集。在節點通信范圍內且網絡深度值小于或等于節點當前父節點的鄰居節點的集合，被稱之為節點的備選節點集，記為P。

定義2 兄弟節點集。在節點通信范圍內且網絡深度值與其相同的鄰居節點的集合，被稱之為節點的兄弟節點集，記為B。

定義3 子節點集。網絡深度值大于當前節點且在當前節點通信范圍內的鄰居節點的集合，被稱之為當前節點的子節點集，記為C。子節點集又包含非親子節點集和親子節點集，其中直接與當前節點處于連接狀態的子節點集被稱之為親子節點集；反之，則被稱之為非親子節點集。

定義4 鄰居節點集。在節點通信范圍內的所有鄰居節點的集合，被稱之為節點的鄰居節點集，記為N，其中P、B和C均被包含于C中。

EELDR-RPL算法的數學模型標記為G=(V,E)，其中V表示節點集合，E表示無線鏈路集合。網絡中節點的鄰居節點集合表示為Vn={V1,V2,V3},其中,V1={P1,P2,…,Pi}表示為節點的備選父節點集，V2={B1,B2,…,Bi}表示為節點的兄弟節點集，V3={C1,C2,…,Ci}表示為節點的子節點集。EELDR-RPL算法的網絡模型如圖1所示。

圖1 EELDR-RPL算法的網絡模型圖Fig.1 Network model of EELDR-RPL

3 EELDR-RPL算法

針對LLN網絡中現有路由修復算法存在控制開銷冗余以及路由修復時延較大等問題，EELDR-RPL算法在路由修復的過程中進行了如下改進：

(1)為了避免增加額外的控制開銷，提出了一種“零額外控制開銷通告鏈路故障及鄰居節點信息”機制，即對相關控制消息的幀格式稍作修改，使得鏈路故障節點的子節點能夠及時獲知鏈路故障以及鏈路故障節點的鄰居節點情況；

(2)為了使得鏈路故障節點能夠快速地重新接入網絡，提出了一種“自適應調整節點網絡深度值”機制，即鏈路故障節點根據其鄰居節點信息自適應地調整自身的網絡深度值；

(3)為了使得修復之后的網絡拓撲更優，提出了一種“鏈路故障節點子節點自適應切換”機制，即鏈路故障節點的子節點通過控制消息獲取到的鏈路故障節點鄰居節點信息以及自身鄰居節點信息進行自適應地切換當前鏈路連接狀態。

3.1 零額外控制開銷通告鏈路故障及鄰居節點信息機制

為了避免增加額外的控制開銷，設計了一種新的面向目的地有向無循環圖(Destination Oriented Directed Acyclic Graph,DODAG)信息請求消息(New DODAG Information Solicitation,N-DIS)。該控制消息利用DIS控制消息中保留字段，將其第一位設置為無線鏈路故障通告字段L。其值為0時，表明當前節點為申請加入網絡的新節點；其值為1時，表明當前節點與其最優父節點之間的無線鏈路處于故障狀態。同時，將保留字段的第二位和第三位設置為當前節點的鄰居節點信息字段N。當該字段的值為11時，表明當前節點擁有可建立連接的備選父節點；當該字段的值為10時，表明當前節點僅擁有可建立連接的兄弟節點；當該字段的值為01時，表明當前節點僅擁有可建立連接的子節點；當該字段的值為00時，表明當前節點無可建立連接的鄰居節點。N-DIS控制消息的幀格式如圖2所示。

圖2 N-DIS控制消息的幀格式圖Fig.2 Frame format of N-DIS control message

當檢測到任意節點與其最優父節點之間的無線鏈路出現故障后，通過廣播N-DIS控制消息重新申請接入到LLN網絡中。當鏈路故障節點的子節點接收到上述N-DIS控制消息后，根據L字段便可獲知鏈路故障節點與其最優父節點之間的當前無線鏈路連接狀態。同時，鏈路故障節點的子節點根據N-DIS控制消息的N字段便可獲知鏈路故障節點的鄰居節點信息，從而便于“鏈路故障節點子節點自適應切換機制”的實施和操作。

3.2 自適應調整節點網絡深度值機制

網絡深度值的大小反映出節點在網絡中的大致位置。距離根節點位置越近，節點的網絡深度值相對越小。為了避免路由環路的產生，子節點的網絡深度值必須小于其父節點的網絡深度值[6]。

當檢測到LLN網絡中出現鏈路故障節點時，提出了一種新的網絡深度值表示方法，即利用小數表示節點更新后的網絡深度值，以便于鏈路故障節點能夠根據其緩存的鄰居節點信息自適應的調整自身的網絡深度值，從而快速地重新接入網絡而不受RPL標準的約束。

假設鏈路故障節點Q的當前網絡深度值為m，其中m為整數，那么節點Q的網絡深度值Rank將根據公式(1)進行自適應地調整：

(1)

當鏈路故障節點Q的網絡深度值為m.1時，相對于其他節點，其網絡深度值為(m+1)；當鏈路故障節點Q的網絡深度值為m.2時，相對于其他節點，其網絡深度值為(m+2)。那么，鏈路故障節點Q的網絡深度值自適應調整策略具體如下：

(1)當鏈路故障節點Q從其緩存中檢測到自身擁有可建立連接的備選父節點時，其網絡深度值Rank保持不變，同時將N-DIS控制消息中的L字段設置為1，N字段設置為11，并向其備選父節點集組播N-DIS控制消息便可快速地重新申請接入到網絡中；

(2)當鏈路故障節點Q從其緩存中檢測到自身僅擁有可建立連接的兄弟節點時，將其網絡深度值Rank更新為m.1，同時將N-DIS控制消息中的L字段設置為1，N字段設置為10，并向其兄弟節點集組播N-DIS控制消息便可快速地重新申請接入到網絡中；

(3)當鏈路故障節點Q從其緩存中檢測到自身僅擁有可建立連接的子節點時，將其網絡深度值Rank更新為m.2，同時將N-DIS控制消息中的L字段設置為1，N字段設置為01，并向其子節點集組播N-DIS控制消息便可快速地重新接入到網絡中；

(4)當鏈路故障節點Q從其緩存中檢測到自身無可建立連接的鄰居節點時，將其網絡深度值Rank更新為，同時將N-DIS控制消息中的L字段設置為1，N字段設置為00，并廣播N-DIS控制消息將其鏈路故障狀態通告給其子節點，等待新一輪網絡拓撲的重構。

3.3 鏈路故障節點子節點自適應切換機制

為了優化鏈路故障修復后的網絡拓撲結構，需要對鏈路故障節點的子節點當前連接狀態進行相應的調整。鏈路故障節點的子節點依據鏈路故障節點廣播的N-DIS控制消息以及自身鄰居節點信息進行自適應地更換與當前鏈路故障節點之間的連接狀態，以此達到優化鏈路故障修復之后的網絡拓撲結構的目的。鏈路故障節點子節點自適應切換機制的具體實施過程如下：

(1)當鏈路故障節點的子節點監聽到鏈路故障節點發送的N-DIS控制消息后，檢查N-DIS控制消息中的L字段。如果L字段的值為1，則繼續檢查N-DIS控制消息中的N字段。

(2)如果N字段的值為11，表明鏈路故障節點當前擁有可直接建立連接的備選父節點，那么鏈路故障節點的子節點則繼續與其維持父子關系，也即對鏈路故障節點的子節點不作任何處理。

(3)如果N字段的值為10，表明鏈路故障節點當前僅擁有可直接建立連接的兄弟節點，那么鏈路故障節點的子節點檢測自身的備選父節點集是否為空集。如果其備選父節點集不為空集，那么該鏈路故障節點的子節點將不再與當前鏈路故障節點繼續維持父子關系，并從備選父節點集中選取一個節點建立新的連接狀態，反之，該鏈路故障節點的子節點則繼續與當前鏈路故障節點維持父子關系，并將其當前網絡深度值更新為(m+1.1)。

(4)如果N字段的值為01，表明鏈路故障節點當前僅擁有可直接建立連接的子節點，那么鏈路故障節點的子節點檢測自身的備選父節點集或是兄弟節點集是否為空集。如果該鏈路故障節點的備選父節點集或是兄弟節點集不為空集，那么該鏈路故障節點的子節點將不再與當前鏈路故障節點繼續維持父子關系，并從備選父節點集或是兄弟節點集中選擇一個合適的節點建立新的連接狀態；反之，該鏈路故障節點的子節點則繼續與當前鏈路故障節點維持父子關系，并將其當前網絡深度值更新為(m+1.2)。

(5)如果N字段的值為00，表明鏈路故障節點無可建立連接的鄰居節點，那么鏈路故障節點的所有子節點均不再與當前鏈路故障節點維持父子關系，并從鄰居節點集中選擇一個合適的節點建立新的連接狀態。

3.4 EELDR-RPL算法操作步驟

EELDR-RPL算法的詳細操作步驟如下：

Step1 在網絡拓撲初始化創建過程中，每個節點均存儲鄰居節點的信息，并周期性地監聽其親子節點的鄰居節點信息。

Step2 節點周期性地檢測其鏈路是否發生故障，若發生故障則檢測其備選父節點集是否為空集。若其備選父節點集不為空集，則向其備選父節點集組播N-DIS控制消息；反之，則進入Step 4。

Step3 鏈路故障節點選擇其備選父節點集中最先回復DIO控制消息的節點作為新的父節點，且其子節點根據監聽鏈路故障節點組播的N-DIS控制消息決定繼續與其維持父子關系。

Step4 鏈路故障節點檢測其兄弟節點集是否為空集，若其兄弟節點集不為空集，則向其兄弟節點集組播N-DIS控制消息；反之，則進入Step 6。

Step5 鏈路故障節點選擇其兄弟節點集中最先回復DIO控制消息的節點作為新的父節點，并將其當前網絡深度值加上0.1，且其子節點根據監聽鏈路故障節點組播的N-DIS控制消息以及其備選父節點集是否為空集，從而決定是否繼續與當前鏈路故障節點繼續維持父子關系。

Step6 鏈路故障節點檢測其非親子節點集是否為空集，若其非親子節點集不為空集，則向其非親子節點集組播N-DIS控制消息；反之，則進入Step 8。

Step7 鏈路故障節點選擇其非親子節點集中最先回復DIO控制消息的節點作為新的父節點，并將其當前網絡深度值加上0.2，且其子節點根據監聽鏈路故障節點組播的N-DIS控制消息以及其備選父節點集或是兄弟節點集是否為空集，從而決定是否繼續與當前鏈路故障節點維持父子關系。

Step8 鏈路故障節點向其親子節點集中鄰居節點為非空集的子節點組播N-DIS控制消息，且選擇其親子節點集中最先回復DIO消息的節點作為新的父節點，為了避免路由環路的產生，最先回復DIO控制消息的親子節點需要將當前鏈路故障節點從其父節點列表中刪除，且其他子節點根據監聽鏈路故障節點組播的N-DIS消息以及其備選父節點集或是兄弟節點集或是子節點集是否為空集，從而決定是否繼續與當前鏈路故障節點維持父子關系。

4 仿真實驗及結果分析

為了定量驗證EELDR-RPL算法的性能，本文通過OPNET 14.5仿真工具搭建模擬仿真平臺分別實現FRR-RPL[13]、LRR-RPL[15]和EELDR-RPL算法的仿真驗證，并對它們的性能進行定量比較和分析。

4.1 仿真環境及參數設置

在350 m×350 m的正方形區域內分別構建不同網絡規模大小的模擬仿真場景，其中，網絡規模大小分別為30、50、70、90和110，節點的通信半徑為50 m，仿真時間為3 600 s。為了節點獲知更多的鄰居信息以便于鏈路故障修復，節點工作在存儲模式。此外，為了確保網絡場景的穩定性，網絡中所有節點均采用靜態或準靜態模型。HLR-RPL算法在仿真過程中用到的其他主要參數設置如表1所示。

表1 其他主要仿真參數Tab.1 The main simulation parameters

4.2 仿真結果分析

4.2.1歸一化控制開銷比較

圖3表明，隨著網絡規模的變化，EELDR-RPL算法的歸一化控制開銷明顯低于FRR-RPL算法和LRR-RPL算法。通過深入分析，發現其主要原因在于：FRR-RPL算法和LRR-RPL算法在進行路由修復的過程中，均需要從鏈路故障節點處進行大量的信息交互操作之后鏈路故障節點才能夠重新加入到網絡中，這種操作越多，導致控制開銷也就越大；而EELDR-RPL算法在進行路由修復的過程中，僅需要將DIS控制消息的幀格式稍作修改以及對鏈路故障節點及其子節點網絡深度值進行自適應的調整，便可減少在路由恢復過程中的信息交互操作，從而降低了大量控制開銷。

圖3 歸一化控制開銷比較Fig.3 Comparison of the normalized control overhead

4.2.2鏈路故障平均修復時延比較

圖4顯示，隨著網絡規模的擴大，LRR-RPL算法的鏈路故障平均修復時延逐漸增大，而FRR-RPL算法和EELDR-RPL算法的鏈路故障平均修復時延變化不大，但EELDR-RPL算法的鏈路故障平均修復時延均低于LRR-RPL算法和FRR-RPL算法。其主要原因在于：LRR-RPL算法在路由修復過程中，需要先發送控制消息到達根節點，然后接收到根節點的反饋信息后才能實施鏈路反轉操作；FRR-RPL算法在路由修復過程中，鏈路故障節點向其鄰居節點發送控制消息，由鄰居節點依次向上一跳轉發，直至轉發至網絡深度值小于鏈路故障節點的上游節點，然后沿原路返回修改節點網絡深度值，直至鏈路故障節點的網絡深度值修改完成后才完成鏈路故障的修復；而EELDR-RPL算法在路由修復過程中，僅需要鏈路故障節點與其鄰居節點進行少量的信息交互，使得鏈路故障節點能夠快速地重新接入到網絡中，從而有效地避免了FRR-RPL算法和EELDR-RPL算法中的冗余操作。

圖4 鏈路故障平均修復時延比較Fig.4 Comparison of the average link failure repair delay

4.2.3根節點平均吞吐量比較

圖5表明，FRR-RPL、LRR-RPL和EELDR-RPL算法的根節點平均吞吐量均隨著網絡規模的擴大而逐漸增大，但是EELDR-RPL算法的根節點平均吞吐量均明顯高于FRR-RPL算法和LRR-RPL算法。通過分析發現，其主要原因在于：EELDR-RPL算法在路由修復過程中，鏈路故障節點根據其獲知的鄰居節點信息自適應地對自身的網絡深度值進行調整后，通過少量的控制消息便可較快地重新接入網絡，能夠有效降低數據包端到端平均傳輸時延，而根節點平均吞吐量與數據包端到端平均傳輸時延成反比關系；EELDR-RPL算法在路由修復過程中，鏈路故障節點的子節點根據接收到的N-DIS控制消息以及其鄰居節點信息判斷是否需要維持與當前鏈路故障節點的連接狀態，優化了鏈路故障修復后的網絡拓撲結構，降低了數據包的平均傳輸跳數，相當于降低了數據包端到端平均傳輸時延。

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

5 結束語

針對LLN網絡中現有路由修復算法存在控制開銷冗余以及路由修復時延較大等問題，本文提出了EELDR-RPL算法。該算法包含3個創新機制：首先，通過采用零額外控制開銷通告鏈路故障及鄰居節點信息機制，使得鏈路故障節點的子節點能夠及時獲知鏈路故障狀態以及鏈路故障節點的鄰居情況；其次，通過采用自適應調整節點網絡深度值機制，使得鏈路故障節點能夠快速地重新接入網絡；最后，通過采用鏈路故障節點子節點自適應切換機制，使得鏈路故障節點的子節點能夠根據接收到的N-DIS控制消息及自身緩存的鄰居節點情況進行自適應地切換與當前鏈路故障節點的連接狀態，達到優化鏈路故障修復后的網絡拓撲結構的目的。仿真結果表明，相對LLN網絡中現有路由修復算法，EELDR-RPL算法能夠有效地減少網絡控制開銷和降低路由修復時延，并且使得修復之后的網絡拓撲結構能夠達到更優狀態。下一步將對移動匯聚節點場景下的鏈路故障修復策略進行研究。