姚玉坤, 劉江兵, 李小勇, 任 智
(重慶郵電大學移動通信技術重慶市重點實驗室, 重慶 400065)
隨著物聯網技術[1]的快速發展,無線傳感器節點以自組織的方式構成的無線傳感器網絡(wireless sensor networks, WSN)被廣泛地應用于環境監測[2]、醫療保健[3]、工業控制[4]、城市交通[5]和現代化農業[6]等領域。其中,備受人們關注的低功耗有損網絡(low power and lossy networks, LLN)[7-8]成為了目前的研究熱點。
LLN具有以下兩方面的特征:一是網絡中的節點內存大小、處理能力和能量均受到限制;二是網絡中的鏈路具有不穩定性和有損性。因此,國際互聯網工程任務組(internet engineering task force, IETF)提出了一種基于IPv6的LLN路由協議(routing protocol for LLN, RPL)[9-11]。
目前,針對RPL的研究主要集中于網絡負載均衡[12-14],以此達到延長網絡壽命的目的。然而,對于RPL路由修復的研究還不夠深入。由于LLN因自身固有的特性以及外部環境的干擾極易導致網絡拓撲的不穩定,使得鏈路中斷情況時有發生,從而嚴重影響網絡性能。因此,當檢測到LLN中鏈路出現故障后,通過路由修復算法對網絡拓撲加以維護,這對提高通信的可靠性和實時性以及延長網絡生命周期顯得極其重要。
近年來,在LLN路由修復方面已經開展了一些工作。當檢測到網絡拓撲出現故障后,文獻[9]中首先由鏈路中斷節點廣播網絡深度值為無窮大的面向目的地的有向無循環圖(destination oriented directed acyclic graph, DODAG)信息對象(DODAG information object, DIO)消息通告其所有子節點不再維持連接狀態,然后由鏈路中斷節點廣播DODAG信息請求(DODAG information solicitation, DIS)消息重新加入到網絡中。該算法控制開銷和修復時延均較大,且一旦DIO消息丟失極易產生路由環路。
當鏈路中斷節點無備選父節點時,文獻[15]提出了一種基于鏈路反轉的RPL路由修復算法(link-reverse repair routing protocol for LLN, LR-RPL),該算法通過引入時序,并結合節點的網絡深度值共同決定節點在網絡中的位置,從而實現鏈路中斷節點與其子節點之間的鏈路反轉。針對路由環路的問題,文獻[16]提出了一種基于路由環路避免的鏈路反轉RPL路由修復(loop-free based link-reverse repair-RPL, LLR-RPL)算法,該算法相比文獻[15]在實施鏈路反轉的過程中新增了反轉路徑的選擇策略。文獻[17]提出了一種路由環路避免的RPL路由修復算法(loop free based repair-RPL, LFR-RPL),該算法通過維持鏈路中斷節點與其所有子節點的連接狀態,僅由鏈路中斷節點廣播DIS消息重新加入網絡,從而避免路由環路的產生。上述兩種算法的控制開銷和路由修復時延均較大,且修復后的網絡并非最優。文獻[18]提出了兩種路由環路避免的RPL路由修復方法:一種是基于序列號進行路由修復,即鏈路中斷節點利用本地和全局序列號發現新的路徑;另一種是ACK(acknowledgement)消息確認機制,鏈路中斷節點需確保其所有子節點均接收到鏈路中斷節點廣播的DIO消息。該機制修復時延同樣較大且無法徹底避免路由環路的產生。
然而,上述針對LLN中現有路由修復方案存在以下3個方面的不足:①控制開銷較大,不利于網絡節能;②路由修復時延較大,不利于網絡中數據的傳輸,影響網絡吞吐量;③修復后的網絡拓撲并非最優,主要在于鏈路中斷節點的子節點是否繼續與之保持連接狀態還無明確判定機制。
為了解決上述LLN中現有路由修復算法存在的不足,本文提出一種LLN中基于環路避免的高效路由修復(highly-efficient loop-free based repair-RPL, HLR-RPL)算法,并對其性能進行理論分析和驗證。
以圖1所示的網絡拓撲模型圖為例。其中,根節點為數據匯聚節點,R1~R8為中繼節點,S1~S7葉子節點。關于LLN有如下假設:
假設1根節點位于網絡區域正上方,其余節點均隨機部署,且處于靜態或準靜態;
假設2除了根節點以外,每個節點的物理構造和屬性均相同且能量有限。

圖1 網絡拓撲模型圖Fig.1 Figure of network topology model
為了便于分析,本文給出如下幾個定義:
定義1備選父節點集:與節點i的父節點j的網絡深度值相同或是網絡深度值小于節點j且在節點i的通信范圍內的所有節點的集合P(i)。
定義2兄弟節點集:與節點i的網絡深度值相同且在節點i的通信范圍內的所有節點的集合B(i)。
定義3非親子節點集:比節點i的網絡深度值大1且在節點i的通信范圍內的所有節點的集合C(i)。
在葉子節點向根節點進行數據匯聚傳輸的過程中,由于鏈路的有損性和不穩定性,容易導致節點間的鏈路中斷。通常鏈路中斷分為4種:①鏈路中斷節點擁有可連接的備選父節點;②鏈路中斷節點無可連接的備選父節點,但擁有可連接的兄弟節點;③鏈路中斷節點既無可連接的備選父節點也無可連接的兄弟節點,但擁有可連接的非親子節點;④鏈路中斷節點既無可連接的備選父節點也無可連接的兄弟節點,同時又無可連接的非親子節點。
針對LLN中現有路由修復方案存在控制開銷冗余、修復時延較大和路由環路等問題,HLR-RPL算法進行了如下改進:①提出“取消拆路消息”機制,即通過采用一種改進的DODAG信息請求消息(DIS-amend, DIS-A)使得鏈路中斷通告過程和尋路過程同時進行;②提出“減少控制消息回復”機制,避免所有接收到鏈路中斷節點廣播的DIS消息的鄰居節點均回復DIO消息;③提出“子節點切換”機制,從而達到優化網絡拓撲的目的。
在取消拆路消息機制中,取消原有路由修復方案中鏈路中斷節點單獨發送額外控制消息通告鏈路故障的步驟,通過使用改進后的DIS-A消息同時實現鏈路中斷通告過程和路由尋路的過程,即鏈路中斷節點通過廣播DIS-A消息就可以使得其所有子節點均獲得其鏈路連接中斷狀態。DIS-A消息的幀格式如圖2所示,從DIS消息幀格式中的保留(Reserved)字段中取前3 bits設置為鄰居字段(neighbor field, NF),表示當前鏈路中斷節點是否擁有可連接的備選父節點、兄弟節點和非親子節點,并且在DIS消息幀格式中的選項部分添加節點的網絡深度值(Rank)字段。此外,DIS-A消息的Type類型與DIS消息不同。

圖2 DIS-A消息幀格式Fig.2 Frame format of the DIS-A message
減少控制消息回復機制的核心思想為鏈路中斷節點的所有鄰居節點一旦接收到其廣播的DIS-A消息后,并非每個接收到DIS-A消息的鄰居節點都需回復DIO消息,而是根據接收到的DIS-A消息中的NF和Rank字段決定是否需要回復DIO消息。僅僅符合作為鏈路中斷節點父節點的鄰居節點才需回復DIO消息,不符合作為父節點的鄰居節點接收到DIS-A消息后,將其丟棄不做任何處理。
假設鏈路中斷節點的網絡深度值為N(N為整數),那么減少控制消息回復機制的具體操作步驟如下。
步驟1鄰居節點接收到鏈路中斷節點廣播的DIS-A消息后檢測DIS-A消息的NF字段。若NF字段的第1位為1,則表明鏈路中斷節點擁有可連接的備選父節點,那么僅網絡深度值小于N的鄰居節點回復DIO消息;若DIS-A消息中NF字段的第1位為0,表明鏈路中斷節點無可連接的備選父節點,則轉至步驟2。
步驟2若鄰居節點接收到的DIS-A消息中NF字段的第2位為1,則表明鏈路中斷節點擁有可連接的兄弟節點,那么僅網絡深度值等于N的鄰居節點回復DIO消息;若DIS-A消息中NF字段的第2位為0,表明鏈路中斷節點無可連接的兄弟節點,則轉至步驟3。
步驟3若鄰居節點接收到的DIS-A消息中NF字段的第3位為1,則表明鏈路中斷節點擁有可連接的非親子節點,那么僅網絡深度值為(N-1)的鄰居節點回復DIO消息;若DIS-A消息中NF字段的第3位為0,則表明鏈路中斷節點無可連接的非親子節點,那么無鄰居節點回復DIO消息。
子節點切換機制的核心思想為當鏈路中斷節點的子節點接收到DIS-A消息后,根據DIS-A消息幀格式中的NF字段判斷是否與其父節點繼續保持連接狀態。具體操作步驟如下。
步驟1當鏈路中斷節點的子節點接收到鏈路中斷節點廣播的DIS-A消息后,檢測DIS-A消息中的NF字段。若NF字段的第1位為1,表明鏈路中斷節點擁有可連接的備選父節點,那么鏈路中斷節點的子節點繼續與其保持連接狀態;若DIS-A消息中NF字段的第1位為0,則轉至步驟2。
步驟2鏈路中斷節點的子節點檢測DIS-A消息中NF字段的第2位。若DIS-A消息中的NF字段的第2位為1,表明鏈路中斷節點擁有可連接的兄弟節點,那么根據鏈路中斷節點的子節點是否擁有可連接的備選父節點決定是否需要與之繼續保持連接狀態。如果鏈路中斷節點的子節點擁有可連接的備選父節點,則與其不再保持連接狀態,即從父節點列表中刪除鏈路中斷節點的路由信息。反之,則繼續與其保持連接狀態;若DIS-A消息中FB字段的第2位為0,則轉至步驟3。
步驟3鏈路中斷節點的子節點檢測DIS-A消息中NF字段的第3位。若DIS-A消息中NF字段的第3位為1,表明鏈路中斷節點擁有可連接的非親子節點,那么根據鏈路中斷節點的子節點是否擁有可連接的備選父節點或是可連接的兄弟節點判斷是否需要與之繼續保持連接狀態。如果鏈路中斷節點的子節點擁有可連接的備選父節點或是可連接的兄弟節點,則與其不再保持連接狀態,即從父節點列表中刪除鏈路中斷節點的路由信息。反之,則繼續與其保持連接狀態;若DIS-A消息中NF字段的第3位為0,則轉至步驟4。
步驟4DIS-A消息中NF字段的第1位、第2位和第3位均為0,表明鏈路中斷節點既無可連接的備選父節點也無可連接的兄弟節點,同時也沒有可連接的非親子節點,那么鏈路中斷節點的所有子節點將不再與其保持連接狀態,即從父節點列表中刪除鏈路中斷節點的路由信息。
HLR-RPL算法的具體操作流程如圖3所示。
HLR-RPL算法的操作步驟從網絡拓撲初始化之后開始,具體實施步驟如下。
步驟1當節點i檢測到與其父節點j之間的鏈路中斷后,節點i將節點j從其父節點集P(i)中刪除。
步驟2節點i檢測其父節點集P(i)是否為空集。若P(i)不為空集,將DIS-A消息中NF字段的第1位設置為1,并廣播DIS-A消息。僅P(i)中的節點接收到DIS-A消息后回復DIO消息,然后節點i從回復DIO消息中的節點選擇一個節點k1作為父節點,并向其單播一個目的地通告消息(destination advertisement object, DAO),且節點i的子節點接收到DIS-A消息后不作任何處理,繼續與之保持連接狀態;若P(i)為空集,將DIS-A消息中NF字段的第1位設置為0,并轉至步驟3。

圖3 HLR-RPL路由修復流程圖Fig.3 Flow chart of HLR-RPL routing repair
步驟3節點i檢測其兄弟節點集B(i)是否為空集。若B(i)不為空集,將DIS-A消息中NF字段的第2位設置為1,并廣播DIS-A消息。僅B(i)中的節點接收到DIS-A消息后回復DIO消息,然后節點i從回復DIO消息中的節點選擇一個節點k2作為父節點,并向其單播一個DAO消息,且其子節點接收到DIS-A消息后根據有無可連接的備選父節點決定是否繼續與之保持連接狀態;若B(i)為空集,將DIS-A消息中NF字段的第2位設置為0,并轉至步驟4。
步驟4節點i檢測其非親子節點集C(i)是否為空集。若C(i)不為空集,將DIS-A消息中NF字段的第3位設置為1,并廣播DIS-A消息。僅C(i)中的節點接收到DIS-A消息后回復DIO消息,然后節點i從回復DIO消息中的節點選擇一個節點k3作為父節點,并向其單播一個DAO消息,且其子節點接收到DIS-A消息后根據有無可連接的備選父節點或兄弟節點決定是否繼續保持連接狀態;若C(i)為空集,將DIS-A消息中NF字段的第3位設置為0,并轉至步驟5。
步驟5節點i廣播DIS-A消息,且將其網絡深度值更改為無窮大,等待網絡拓撲的更新直至全局修復過程的到來。同時,節點i的所有子節點接收到DIS-A消息后均不再與其保持連接狀態且重復節點i的處理過程。
假設LLN中有S個中繼節點因出現故障而導致鏈路中斷,其中擁有可連接備選父節點的鏈路中斷節點有m個,無可連接備選父節點但擁有可連接兄弟節點的鏈路中斷節點有n個,既無可連接備選父節點也無可連接兄弟節點但擁有可連接的非親子節點的鏈路中斷節點有h個。另外,不考慮控制消息出現丟包的情況。
關于HLR-RPL算法的性能,提出引理1和引理2。
引理1與現有LLN中路由修復算法相比,HLR-RPL的路由修復控制開銷低于LFR-RPL。

(mQ+nM+hN)lD
(1)
lA(m+n+n)
(2)
式中,M表示每個鏈路故障節點擁有的可連接兄弟節點個數;N表示每個鏈路故障節點擁有的可連接子節點個數;M和N均大于0。則有
(mQ+2nM+3hN)lR-(nM-2hN)lD
(3)

證畢
引理2與現有LLN中路由修復算法相比,HLR-RPL的路由修復時延低于LFR-RPL。
證明設TH和TL分別表示HLR-RPL和LFR-RPL在相同網絡拓撲情況下的路由修復時延,一跳范圍內每個DIS消息的傳輸時延為t1,每個DIS-A消息的傳輸時延為t2,每個DIO消息的傳輸時延為t3,每個DAO消息的傳輸時延t4,故有
TH=m(t2+t3+t4)+n(t2+t3+t4)+h(t2+t3+t4)=
(m+n+h)(t2+t3+t4)
(4)
TL=m(t1+t3+t4)+n(2t1+2t3+t4)+
h(3t1+3t3+t4)=(m+2n+3h)(t1+t3)+
t4(m+n+h)
(5)

證畢
本文采用OPNET Modeler 14.5仿真軟件對HLR-RPL算法的性能進行仿真驗證,在相同仿真模擬場景下,選取LR-RPL[12]、LLR-RPL[13]和LFR-RPL[14]算法進行比較和分析。
4.1.1 歸一化控制開銷
歸一化控制開銷指在網絡運行時間內網絡中除根節點外所有節點發送和轉發的控制消息比特數與網絡中所有節點發送和轉發的控制消息和到達根節點數據包的比特數的比值,表示為
NC=γC/(γC+γD)
(6)
式中,NC表示為節點歸一化控制開銷;γC表示網絡中所有節點發送和轉發的控制消息比特數;γD表示網絡中所有節點發送和轉發的控制消息和到達根節點的數據包的比特數。
4.1.2 路由修復平均時延
路由修復平均時延是指在網絡運行時間內當檢測到網絡出現故障后,所有鏈路故障節點重新加入到網絡中所耗費的平均時間,表示為
(7)
式中,TRi表示網絡中的鏈路故障節點i重新加入到網絡中所耗費的時間;n表示在網絡運行時間內出現鏈路故障的節點總數。
4.1.3 網絡生存時間
網絡生存時間是指在網絡運行時間內網絡中能量耗盡節點的數量達到節點總數的10%所耗費的時間,表示為
TL=Td-T0
(8)
式中,Td表示網絡中死亡節點數量達到總的節點數量10%的時刻;T0表示網絡開始運行的時刻。
4.1.4 路由環路產生的概率
路由環路產生的概率是指在網絡運行時間內,路由修復過程中出現路由環路的鏈路故障節點數與鏈路故障節點總數量的比值,表示為
ρ=NumRL/NumLB
(9)
式中,NumRL表示路由修復過程中出現路由環路的鏈路故障節點數;NumLB表示網絡中鏈路故障節點數量。
在300 m×300 m的模擬仿真區域內根據節點數量不同設置6個不同仿真場景,場景中的節點均隨機分布且位置一旦固定將不再移動。網絡中除根節點外,其余節點的初始能量相同且在仿真過程中不補給能量。由于節點受限于能量和處理能力,故節點數據傳輸速率不宜過高。同時,考慮鏈路的有損性,應設定鏈路損耗因子。另外,為了便于節點記錄其鄰居節點信息,節點采用存儲模式。為了使結果更加可靠,在每個場景中分別多次模擬運行上述4種路由修復算法,取平均值作為最終結果。主要參數設置如表1所示。

表1 主要仿真參數
4.3.1 歸一化控制開銷
如圖4所示,HLR-RPL的歸一化控制開銷均低于LFR-RPL、LR-RPL和 LLR-RPL,而且隨著網絡規模的擴大,從0.49降低到0.25。HLR-RPL能夠減少歸一化控制開銷的主要原因有以下兩點:首先,通過改進后的DIS-A消息能夠同時實現鏈路中斷通告過程和尋路過程,省去了鏈路中斷通告開銷;其次,通過改進后的DIS-A消息能夠避免所有接收到DIS-A消息的鄰居結點均回復DIO消息,僅符合作為鏈路中斷節點父節點的鄰居節點回復DIO消息,從而有效地降低了控制開銷,與引理1分析的結果一致。而控制開銷的減少降低了可用信道帶寬的占用,從而增加了根節點接收的數據包數量,故控制開銷的減少可以有效地降低歸一化控制開銷。

圖4 歸一化控制開銷比較Fig.4 Comparison of the normalized control overhead
4.3.2 路由修復平均時延
如圖5所示,HLR-RPL、LFR-RPL和LR-RPL的路由修復平均時延隨著網絡規模的擴大變化不大,而LLR-RPL的路由修復平均時延隨著網絡規模的擴大變化相對較大。且在每個場景中,HLR-RPL的路由修復平均時延明顯低于其3種算法,至少降低了32.64%,與引理2分析的結果一致。分析其主要原因在于,HLR-RPL利用DIS-A消息同時實現鏈路中斷通告過程和尋路過程,有效地降低了路由修復時延;其次,符合作為鏈路中斷節點父節點的鄰居節點一旦接收到DIS-A消息后立即回復DIO消息即可修復鏈路故障,對路由修復時延有降低作用。

圖5 路由修復平均時延比較Fig.5 Comparison of the average routing repair delay
4.3.3 網絡生存時間
如圖6所示,與LFR-RPL、LR-RPL和LLR-RPL相比,HLR-RPL算法的網絡生存時間至少能夠延長9.28%。

圖6 網絡生存時間比較Fig.6 Comparison of the network survival time
分析其主要原因在于,HLR-RPL通過DIS-A消息同時實現鏈路中斷通告過程和尋路過程,以及減少了不必要回復DIO消息的鄰居節點個數,從而降低了節點的能耗;其次,HLR-RPL通過子節點切換機制能夠使得修復后的網絡拓撲達到最優狀態,減少了數據分組的傳輸跳數,從而降低了數據分組的傳輸能耗。
4.3.4 路由環路產生的概率
如表2所示,HLR-RPL、LLR-RPL和LFR-RPL在各個場景中的路由環路產生概率均為0,表明均具有較好的可靠性。分析其主要原因在于,當檢測到鏈路出現故障后,HLR-RPL和LFR-RPL中的鏈路中斷節點選擇其子節點作為父節點的概率為0;LLR-RPL中的鏈路故障節點僅選擇接收到鏈路中斷通告消息的子節點進行鏈路反轉,從而徹底避免了路由環路的產生;然而,LR-RPL的路由環路產生概率隨著網絡規模的擴大逐漸發生變化,主要原因在于鏈路故障節點數量的增加,而一旦當鏈路中斷通告消息丟失就會形成路由環路。

表2 路由環路產生的概率對比
由于LLN中現有路由修復方案存在控制開銷冗余、修復時延較大和路由環路等問題,本文提出了HLR-RPL路由算法。為了使路由修復高效,該算法利用DIS-A消息使得鏈路中斷通告過程和尋路過程同時進行;通過減少控制消息回復機制,避免所有接收到DIS-A消息的鄰居節點均回復DIO消息;通過子節點切換機制能夠優化網絡拓撲,有利于數據的傳輸。理論分析和仿真結果表明,相對現有路由修復方案,HLR-RPL能夠有效降低網絡控制開銷、縮短修復時延和優化網絡拓撲,并且能夠徹底避免路由環路的產生。在未來工作中,將研究一種適用于動態的LLN路由修復算法。
參考文獻:
[1] MINOLI D, SOHRABY K, OCCHIOGROSSO B. IoT considerations, requirements, and architectures for smart buildings-energy optimization and next generation building management systems[J].IEEE Internet of Things Journal,2017,4(1):269-283.
[2] VISCONTI P, ORLANDO C, PRIMICERI P. Solar powered WSN for monitoring environment and soil parameters by specific app for mobile devices usable for early flood prediction or water savings[C]∥Proc.of the 16th International Conference on Environment and Electrical Engineering, 2016: 1-6.
[3] ALAIAD A, ZHOU L. Patients’ adoption of WSN-based smart home healthcare systems: an integrated model of facilitators and barriers[J].IEEE Trans.on Professional Communication,2017,60(1): 4-23.
[4] CHENG B, ZHAO S, WANG S, et al. Lightweight mashup middleware for coal mine safety monitoring and control automation[J]. IEEE Trans.on Automation Science and Engineering, 2017, 14(2): 1245-1255.
[5] HU X, YANG L, XIONG W. A novel wireless sensor network frame for urban transportation[J]. IEEE Internet of Things Journal, 2015, 2(6): 586-595.
[6] ABOUZAR P, MICHELSON D G, HAMDI M. RSSI-based distributed self-localization for wireless sensor networks used in precision agriculture[J]. IEEE Trans.on Wireless Communications, 2016, 15(10): 6638-6650.
[7] KIM H S, IM H, LEE M S, et al. A measurement study of TCP over RPL in low-power and lossy networks[J]. Journal of Communications and Networks, 2015, 17(6): 647-655.
[8] PAEK J. Fast and adaptive mesh access control in low-power and lossy networks[J]. IEEE Internet of Things Journal, 2015, 2(5): 435-444.
[9] RFC 6550. RPL: IPv6 routing protocol for low-power and lossy networks[S]. IETF, 2012.
[10] RFC 6552. Objective function zero for the routing protocol for low-power and lossy networks[S].IETF,2012.
[11] RFC 6719. The minimum rank with hysteresis objective function[S]. IETF, 2012.
[12] KIM H S, KIM H, PAEK J, et al. Load balancing under heavy traffic in RPL routing protocol for low power and lossy networks[J]. IEEE Trans.on Mobile Computing, 2017, 16(4): 964-979.
[13] ZHAO M, HO I W H, CHONG P H J. An energy efficient region-based RPL routing protocol for low-power and lossy networks[J].IEEE Internet of Things Journal,2016,3(6):1319-1333.
[14] 姚玉坤,劉江兵,任智,等.集中式網絡擁塞控制的高效RPL路由協議[J].系統工程與電子技術,2017,39(12):2810-2816.
YAO Y K, LIU J B, REN Z, et al. High-efficient centralized network congestion control for RPL routing protocol[J]. Systems Engineering and Electronics, 2017, 39(12):2810-2816.
[15] LA C A, HEUSSE M, GRENOBLE A D. Link reversal and reactive routing in low power and lossy networks[C]∥Proc.of the 24th International Symposium on Personal Indoor and Mobile Radio Communications, 2013: 3386-3390.
[16] AUDEOUD H J, KROL M, HEUSSE M, et al. Low overhead loop-free routing in wireless sensor networks[C]∥Proc.of the 11th International Conference on Wireless and Mobile Computing, Networking and Communications, 2015: 443-451.
[17] GUO J, HAN C, ORLIC P, et al. Loop-free routing in low-power and lossy networks[C]∥Proc.of the 6th International Conference on Sensor Technologies and Applications, 2012: 59-66.
[18] KAMPEN A L, OVSTHUS K, KURE ?. Reconnection strategies in WSN running RPL[C]∥Proc.of the 39 th Conference on Local Computer Networks Workshops, 2014: 602-609.