LLN中基于環(huán)路避免的高效路由修復(fù)算法

姚玉坤, 劉江兵, 李小勇, 任 智

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實驗室, 重慶 400065)

0 引 言

隨著物聯(lián)網(wǎng)技術(shù)[1]的快速發(fā)展,無線傳感器節(jié)點(diǎn)以自組織的方式構(gòu)成的無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSN)被廣泛地應(yīng)用于環(huán)境監(jiān)測[2]、醫(yī)療保健[3]、工業(yè)控制[4]、城市交通[5]和現(xiàn)代化農(nóng)業(yè)[6]等領(lǐng)域。其中,備受人們關(guān)注的低功耗有損網(wǎng)絡(luò)(low power and lossy networks, LLN)[7-8]成為了目前的研究熱點(diǎn)。

LLN具有以下兩方面的特征:一是網(wǎng)絡(luò)中的節(jié)點(diǎn)內(nèi)存大小、處理能力和能量均受到限制;二是網(wǎng)絡(luò)中的鏈路具有不穩(wěn)定性和有損性。因此,國際互聯(lián)網(wǎng)工程任務(wù)組(internet engineering task force, IETF)提出了一種基于IPv6的LLN路由協(xié)議(routing protocol for LLN, RPL)[9-11]。

目前,針對RPL的研究主要集中于網(wǎng)絡(luò)負(fù)載均衡[12-14],以此達(dá)到延長網(wǎng)絡(luò)壽命的目的。然而,對于RPL路由修復(fù)的研究還不夠深入。由于LLN因自身固有的特性以及外部環(huán)境的干擾極易導(dǎo)致網(wǎng)絡(luò)拓?fù)涞牟环€(wěn)定,使得鏈路中斷情況時有發(fā)生,從而嚴(yán)重影響網(wǎng)絡(luò)性能。因此,當(dāng)檢測到LLN中鏈路出現(xiàn)故障后,通過路由修復(fù)算法對網(wǎng)絡(luò)拓?fù)浼右跃S護(hù),這對提高通信的可靠性和實時性以及延長網(wǎng)絡(luò)生命周期顯得極其重要。

1 相關(guān)工作

近年來,在LLN路由修復(fù)方面已經(jīng)開展了一些工作。當(dāng)檢測到網(wǎng)絡(luò)拓?fù)涑霈F(xiàn)故障后,文獻(xiàn)[9]中首先由鏈路中斷節(jié)點(diǎn)廣播網(wǎng)絡(luò)深度值為無窮大的面向目的地的有向無循環(huán)圖(destination oriented directed acyclic graph, DODAG)信息對象(DODAG information object, DIO)消息通告其所有子節(jié)點(diǎn)不再維持連接狀態(tài),然后由鏈路中斷節(jié)點(diǎn)廣播DODAG信息請求(DODAG information solicitation, DIS)消息重新加入到網(wǎng)絡(luò)中。該算法控制開銷和修復(fù)時延均較大,且一旦DIO消息丟失極易產(chǎn)生路由環(huán)路。

當(dāng)鏈路中斷節(jié)點(diǎn)無備選父節(jié)點(diǎn)時,文獻(xiàn)[15]提出了一種基于鏈路反轉(zhuǎn)的RPL路由修復(fù)算法(link-reverse repair routing protocol for LLN, LR-RPL),該算法通過引入時序,并結(jié)合節(jié)點(diǎn)的網(wǎng)絡(luò)深度值共同決定節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置,從而實現(xiàn)鏈路中斷節(jié)點(diǎn)與其子節(jié)點(diǎn)之間的鏈路反轉(zhuǎn)。針對路由環(huán)路的問題,文獻(xiàn)[16]提出了一種基于路由環(huán)路避免的鏈路反轉(zhuǎn)RPL路由修復(fù)(loop-free based link-reverse repair-RPL, LLR-RPL)算法,該算法相比文獻(xiàn)[15]在實施鏈路反轉(zhuǎn)的過程中新增了反轉(zhuǎn)路徑的選擇策略。文獻(xiàn)[17]提出了一種路由環(huán)路避免的RPL路由修復(fù)算法(loop free based repair-RPL, LFR-RPL),該算法通過維持鏈路中斷節(jié)點(diǎn)與其所有子節(jié)點(diǎn)的連接狀態(tài),僅由鏈路中斷節(jié)點(diǎn)廣播DIS消息重新加入網(wǎng)絡(luò),從而避免路由環(huán)路的產(chǎn)生。上述兩種算法的控制開銷和路由修復(fù)時延均較大,且修復(fù)后的網(wǎng)絡(luò)并非最優(yōu)。文獻(xiàn)[18]提出了兩種路由環(huán)路避免的RPL路由修復(fù)方法:一種是基于序列號進(jìn)行路由修復(fù),即鏈路中斷節(jié)點(diǎn)利用本地和全局序列號發(fā)現(xiàn)新的路徑;另一種是ACK(acknowledgement)消息確認(rèn)機(jī)制,鏈路中斷節(jié)點(diǎn)需確保其所有子節(jié)點(diǎn)均接收到鏈路中斷節(jié)點(diǎn)廣播的DIO消息。該機(jī)制修復(fù)時延同樣較大且無法徹底避免路由環(huán)路的產(chǎn)生。

然而,上述針對LLN中現(xiàn)有路由修復(fù)方案存在以下3個方面的不足:①控制開銷較大,不利于網(wǎng)絡(luò)節(jié)能;②路由修復(fù)時延較大,不利于網(wǎng)絡(luò)中數(shù)據(jù)的傳輸,影響網(wǎng)絡(luò)吞吐量;③修復(fù)后的網(wǎng)絡(luò)拓?fù)洳⒎亲顑?yōu),主要在于鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)是否繼續(xù)與之保持連接狀態(tài)還無明確判定機(jī)制。

為了解決上述LLN中現(xiàn)有路由修復(fù)算法存在的不足,本文提出一種LLN中基于環(huán)路避免的高效路由修復(fù)(highly-efficient loop-free based repair-RPL, HLR-RPL)算法,并對其性能進(jìn)行理論分析和驗證。

2 網(wǎng)絡(luò)模型

以圖1所示的網(wǎng)絡(luò)拓?fù)淠Ｐ蛨D為例。其中,根節(jié)點(diǎn)為數(shù)據(jù)匯聚節(jié)點(diǎn),R1～R8為中繼節(jié)點(diǎn),S1～S7葉子節(jié)點(diǎn)。關(guān)于LLN有如下假設(shè):

假設(shè)1根節(jié)點(diǎn)位于網(wǎng)絡(luò)區(qū)域正上方,其余節(jié)點(diǎn)均隨機(jī)部署,且處于靜態(tài)或準(zhǔn)靜態(tài);

假設(shè)2除了根節(jié)點(diǎn)以外,每個節(jié)點(diǎn)的物理構(gòu)造和屬性均相同且能量有限。

圖1 網(wǎng)絡(luò)拓?fù)淠Ｐ蛨DFig.1 Figure of network topology model

為了便于分析,本文給出如下幾個定義:

定義1備選父節(jié)點(diǎn)集:與節(jié)點(diǎn)i的父節(jié)點(diǎn)j的網(wǎng)絡(luò)深度值相同或是網(wǎng)絡(luò)深度值小于節(jié)點(diǎn)j且在節(jié)點(diǎn)i的通信范圍內(nèi)的所有節(jié)點(diǎn)的集合P(i)。

定義2兄弟節(jié)點(diǎn)集:與節(jié)點(diǎn)i的網(wǎng)絡(luò)深度值相同且在節(jié)點(diǎn)i的通信范圍內(nèi)的所有節(jié)點(diǎn)的集合B(i)。

定義3非親子節(jié)點(diǎn)集:比節(jié)點(diǎn)i的網(wǎng)絡(luò)深度值大1且在節(jié)點(diǎn)i的通信范圍內(nèi)的所有節(jié)點(diǎn)的集合C(i)。

在葉子節(jié)點(diǎn)向根節(jié)點(diǎn)進(jìn)行數(shù)據(jù)匯聚傳輸?shù)倪^程中,由于鏈路的有損性和不穩(wěn)定性,容易導(dǎo)致節(jié)點(diǎn)間的鏈路中斷。通常鏈路中斷分為4種:①鏈路中斷節(jié)點(diǎn)擁有可連接的備選父節(jié)點(diǎn);②鏈路中斷節(jié)點(diǎn)無可連接的備選父節(jié)點(diǎn),但擁有可連接的兄弟節(jié)點(diǎn);③鏈路中斷節(jié)點(diǎn)既無可連接的備選父節(jié)點(diǎn)也無可連接的兄弟節(jié)點(diǎn),但擁有可連接的非親子節(jié)點(diǎn);④鏈路中斷節(jié)點(diǎn)既無可連接的備選父節(jié)點(diǎn)也無可連接的兄弟節(jié)點(diǎn),同時又無可連接的非親子節(jié)點(diǎn)。

3 HLR-RPL算法

針對LLN中現(xiàn)有路由修復(fù)方案存在控制開銷冗余、修復(fù)時延較大和路由環(huán)路等問題,HLR-RPL算法進(jìn)行了如下改進(jìn):①提出“取消拆路消息”機(jī)制,即通過采用一種改進(jìn)的DODAG信息請求消息(DIS-amend, DIS-A)使得鏈路中斷通告過程和尋路過程同時進(jìn)行;②提出“減少控制消息回復(fù)”機(jī)制,避免所有接收到鏈路中斷節(jié)點(diǎn)廣播的DIS消息的鄰居節(jié)點(diǎn)均回復(fù)DIO消息;③提出“子節(jié)點(diǎn)切換”機(jī)制,從而達(dá)到優(yōu)化網(wǎng)絡(luò)拓?fù)涞哪康摹?/p>

3.1 取消拆路消息機(jī)制

在取消拆路消息機(jī)制中,取消原有路由修復(fù)方案中鏈路中斷節(jié)點(diǎn)單獨(dú)發(fā)送額外控制消息通告鏈路故障的步驟,通過使用改進(jìn)后的DIS-A消息同時實現(xiàn)鏈路中斷通告過程和路由尋路的過程,即鏈路中斷節(jié)點(diǎn)通過廣播DIS-A消息就可以使得其所有子節(jié)點(diǎn)均獲得其鏈路連接中斷狀態(tài)。DIS-A消息的幀格式如圖2所示,從DIS消息幀格式中的保留(Reserved)字段中取前3 bits設(shè)置為鄰居字段(neighbor field, NF),表示當(dāng)前鏈路中斷節(jié)點(diǎn)是否擁有可連接的備選父節(jié)點(diǎn)、兄弟節(jié)點(diǎn)和非親子節(jié)點(diǎn),并且在DIS消息幀格式中的選項部分添加節(jié)點(diǎn)的網(wǎng)絡(luò)深度值(Rank)字段。此外,DIS-A消息的Type類型與DIS消息不同。

圖2 DIS-A消息幀格式Fig.2 Frame format of the DIS-A message

3.2 減少控制消息回復(fù)機(jī)制

減少控制消息回復(fù)機(jī)制的核心思想為鏈路中斷節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)一旦接收到其廣播的DIS-A消息后,并非每個接收到DIS-A消息的鄰居節(jié)點(diǎn)都需回復(fù)DIO消息,而是根據(jù)接收到的DIS-A消息中的NF和Rank字段決定是否需要回復(fù)DIO消息。僅僅符合作為鏈路中斷節(jié)點(diǎn)父節(jié)點(diǎn)的鄰居節(jié)點(diǎn)才需回復(fù)DIO消息,不符合作為父節(jié)點(diǎn)的鄰居節(jié)點(diǎn)接收到DIS-A消息后,將其丟棄不做任何處理。

假設(shè)鏈路中斷節(jié)點(diǎn)的網(wǎng)絡(luò)深度值為N(N為整數(shù)),那么減少控制消息回復(fù)機(jī)制的具體操作步驟如下。

步驟1鄰居節(jié)點(diǎn)接收到鏈路中斷節(jié)點(diǎn)廣播的DIS-A消息后檢測DIS-A消息的NF字段。若NF字段的第1位為1,則表明鏈路中斷節(jié)點(diǎn)擁有可連接的備選父節(jié)點(diǎn),那么僅網(wǎng)絡(luò)深度值小于N的鄰居節(jié)點(diǎn)回復(fù)DIO消息;若DIS-A消息中NF字段的第1位為0,表明鏈路中斷節(jié)點(diǎn)無可連接的備選父節(jié)點(diǎn),則轉(zhuǎn)至步驟2。

步驟2若鄰居節(jié)點(diǎn)接收到的DIS-A消息中NF字段的第2位為1,則表明鏈路中斷節(jié)點(diǎn)擁有可連接的兄弟節(jié)點(diǎn),那么僅網(wǎng)絡(luò)深度值等于N的鄰居節(jié)點(diǎn)回復(fù)DIO消息;若DIS-A消息中NF字段的第2位為0,表明鏈路中斷節(jié)點(diǎn)無可連接的兄弟節(jié)點(diǎn),則轉(zhuǎn)至步驟3。

步驟3若鄰居節(jié)點(diǎn)接收到的DIS-A消息中NF字段的第3位為1,則表明鏈路中斷節(jié)點(diǎn)擁有可連接的非親子節(jié)點(diǎn),那么僅網(wǎng)絡(luò)深度值為(N-1)的鄰居節(jié)點(diǎn)回復(fù)DIO消息;若DIS-A消息中NF字段的第3位為0,則表明鏈路中斷節(jié)點(diǎn)無可連接的非親子節(jié)點(diǎn),那么無鄰居節(jié)點(diǎn)回復(fù)DIO消息。

3.3 子節(jié)點(diǎn)切換機(jī)制

子節(jié)點(diǎn)切換機(jī)制的核心思想為當(dāng)鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)接收到DIS-A消息后,根據(jù)DIS-A消息幀格式中的NF字段判斷是否與其父節(jié)點(diǎn)繼續(xù)保持連接狀態(tài)。具體操作步驟如下。

步驟1當(dāng)鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)接收到鏈路中斷節(jié)點(diǎn)廣播的DIS-A消息后,檢測DIS-A消息中的NF字段。若NF字段的第1位為1,表明鏈路中斷節(jié)點(diǎn)擁有可連接的備選父節(jié)點(diǎn),那么鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)繼續(xù)與其保持連接狀態(tài);若DIS-A消息中NF字段的第1位為0,則轉(zhuǎn)至步驟2。

步驟2鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)檢測DIS-A消息中NF字段的第2位。若DIS-A消息中的NF字段的第2位為1,表明鏈路中斷節(jié)點(diǎn)擁有可連接的兄弟節(jié)點(diǎn),那么根據(jù)鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)是否擁有可連接的備選父節(jié)點(diǎn)決定是否需要與之繼續(xù)保持連接狀態(tài)。如果鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)擁有可連接的備選父節(jié)點(diǎn),則與其不再保持連接狀態(tài),即從父節(jié)點(diǎn)列表中刪除鏈路中斷節(jié)點(diǎn)的路由信息。反之,則繼續(xù)與其保持連接狀態(tài);若DIS-A消息中FB字段的第2位為0,則轉(zhuǎn)至步驟3。

步驟3鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)檢測DIS-A消息中NF字段的第3位。若DIS-A消息中NF字段的第3位為1,表明鏈路中斷節(jié)點(diǎn)擁有可連接的非親子節(jié)點(diǎn),那么根據(jù)鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)是否擁有可連接的備選父節(jié)點(diǎn)或是可連接的兄弟節(jié)點(diǎn)判斷是否需要與之繼續(xù)保持連接狀態(tài)。如果鏈路中斷節(jié)點(diǎn)的子節(jié)點(diǎn)擁有可連接的備選父節(jié)點(diǎn)或是可連接的兄弟節(jié)點(diǎn),則與其不再保持連接狀態(tài),即從父節(jié)點(diǎn)列表中刪除鏈路中斷節(jié)點(diǎn)的路由信息。反之,則繼續(xù)與其保持連接狀態(tài);若DIS-A消息中NF字段的第3位為0,則轉(zhuǎn)至步驟4。

步驟4DIS-A消息中NF字段的第1位、第2位和第3位均為0,表明鏈路中斷節(jié)點(diǎn)既無可連接的備選父節(jié)點(diǎn)也無可連接的兄弟節(jié)點(diǎn),同時也沒有可連接的非親子節(jié)點(diǎn),那么鏈路中斷節(jié)點(diǎn)的所有子節(jié)點(diǎn)將不再與其保持連接狀態(tài),即從父節(jié)點(diǎn)列表中刪除鏈路中斷節(jié)點(diǎn)的路由信息。

3.4 HLR-RPL算法操作步驟

HLR-RPL算法的具體操作流程如圖3所示。

HLR-RPL算法的操作步驟從網(wǎng)絡(luò)拓?fù)涑跏蓟箝_始,具體實施步驟如下。

步驟1當(dāng)節(jié)點(diǎn)i檢測到與其父節(jié)點(diǎn)j之間的鏈路中斷后,節(jié)點(diǎn)i將節(jié)點(diǎn)j從其父節(jié)點(diǎn)集P(i)中刪除。

步驟2節(jié)點(diǎn)i檢測其父節(jié)點(diǎn)集P(i)是否為空集。若P(i)不為空集,將DIS-A消息中NF字段的第1位設(shè)置為1,并廣播DIS-A消息。僅P(i)中的節(jié)點(diǎn)接收到DIS-A消息后回復(fù)DIO消息,然后節(jié)點(diǎn)i從回復(fù)DIO消息中的節(jié)點(diǎn)選擇一個節(jié)點(diǎn)k1作為父節(jié)點(diǎn),并向其單播一個目的地通告消息(destination advertisement object, DAO),且節(jié)點(diǎn)i的子節(jié)點(diǎn)接收到DIS-A消息后不作任何處理,繼續(xù)與之保持連接狀態(tài);若P(i)為空集,將DIS-A消息中NF字段的第1位設(shè)置為0,并轉(zhuǎn)至步驟3。

圖3 HLR-RPL路由修復(fù)流程圖Fig.3 Flow chart of HLR-RPL routing repair

步驟3節(jié)點(diǎn)i檢測其兄弟節(jié)點(diǎn)集B(i)是否為空集。若B(i)不為空集,將DIS-A消息中NF字段的第2位設(shè)置為1,并廣播DIS-A消息。僅B(i)中的節(jié)點(diǎn)接收到DIS-A消息后回復(fù)DIO消息,然后節(jié)點(diǎn)i從回復(fù)DIO消息中的節(jié)點(diǎn)選擇一個節(jié)點(diǎn)k2作為父節(jié)點(diǎn),并向其單播一個DAO消息,且其子節(jié)點(diǎn)接收到DIS-A消息后根據(jù)有無可連接的備選父節(jié)點(diǎn)決定是否繼續(xù)與之保持連接狀態(tài);若B(i)為空集,將DIS-A消息中NF字段的第2位設(shè)置為0,并轉(zhuǎn)至步驟4。

步驟4節(jié)點(diǎn)i檢測其非親子節(jié)點(diǎn)集C(i)是否為空集。若C(i)不為空集,將DIS-A消息中NF字段的第3位設(shè)置為1,并廣播DIS-A消息。僅C(i)中的節(jié)點(diǎn)接收到DIS-A消息后回復(fù)DIO消息,然后節(jié)點(diǎn)i從回復(fù)DIO消息中的節(jié)點(diǎn)選擇一個節(jié)點(diǎn)k3作為父節(jié)點(diǎn),并向其單播一個DAO消息,且其子節(jié)點(diǎn)接收到DIS-A消息后根據(jù)有無可連接的備選父節(jié)點(diǎn)或兄弟節(jié)點(diǎn)決定是否繼續(xù)保持連接狀態(tài);若C(i)為空集,將DIS-A消息中NF字段的第3位設(shè)置為0,并轉(zhuǎn)至步驟5。

步驟5節(jié)點(diǎn)i廣播DIS-A消息,且將其網(wǎng)絡(luò)深度值更改為無窮大,等待網(wǎng)絡(luò)拓?fù)涞母轮敝寥中迯?fù)過程的到來。同時,節(jié)點(diǎn)i的所有子節(jié)點(diǎn)接收到DIS-A消息后均不再與其保持連接狀態(tài)且重復(fù)節(jié)點(diǎn)i的處理過程。

3.5 HLR-RPL算法性能的理論分析

假設(shè)LLN中有S個中繼節(jié)點(diǎn)因出現(xiàn)故障而導(dǎo)致鏈路中斷,其中擁有可連接備選父節(jié)點(diǎn)的鏈路中斷節(jié)點(diǎn)有m個,無可連接備選父節(jié)點(diǎn)但擁有可連接兄弟節(jié)點(diǎn)的鏈路中斷節(jié)點(diǎn)有n個,既無可連接備選父節(jié)點(diǎn)也無可連接兄弟節(jié)點(diǎn)但擁有可連接的非親子節(jié)點(diǎn)的鏈路中斷節(jié)點(diǎn)有h個。另外,不考慮控制消息出現(xiàn)丟包的情況。

關(guān)于HLR-RPL算法的性能,提出引理1和引理2。

引理1與現(xiàn)有LLN中路由修復(fù)算法相比,HLR-RPL的路由修復(fù)控制開銷低于LFR-RPL。

(mQ+nM+hN)lD

(1)

lA(m+n+n)

(2)

式中,M表示每個鏈路故障節(jié)點(diǎn)擁有的可連接兄弟節(jié)點(diǎn)個數(shù)；N表示每個鏈路故障節(jié)點(diǎn)擁有的可連接子節(jié)點(diǎn)個數(shù)；M和N均大于0。則有

(mQ+2nM+3hN)lR-(nM-2hN)lD

(3)

證畢

引理2與現(xiàn)有LLN中路由修復(fù)算法相比,HLR-RPL的路由修復(fù)時延低于LFR-RPL。

證明設(shè)TH和TL分別表示HLR-RPL和LFR-RPL在相同網(wǎng)絡(luò)拓?fù)淝闆r下的路由修復(fù)時延,一跳范圍內(nèi)每個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)

證畢

4 仿真實驗及結(jié)果分析

本文采用OPNET Modeler 14.5仿真軟件對HLR-RPL算法的性能進(jìn)行仿真驗證,在相同仿真模擬場景下,選取LR-RPL[12]、LLR-RPL[13]和LFR-RPL[14]算法進(jìn)行比較和分析。

4.1 統(tǒng)計量定義

4.1.1 歸一化控制開銷

歸一化控制開銷指在網(wǎng)絡(luò)運(yùn)行時間內(nèi)網(wǎng)絡(luò)中除根節(jié)點(diǎn)外所有節(jié)點(diǎn)發(fā)送和轉(zhuǎn)發(fā)的控制消息比特數(shù)與網(wǎng)絡(luò)中所有節(jié)點(diǎn)發(fā)送和轉(zhuǎn)發(fā)的控制消息和到達(dá)根節(jié)點(diǎn)數(shù)據(jù)包的比特數(shù)的比值,表示為

NC=γC/(γC+γD)

(6)

式中,NC表示為節(jié)點(diǎn)歸一化控制開銷;γC表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)發(fā)送和轉(zhuǎn)發(fā)的控制消息比特數(shù);γD表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)發(fā)送和轉(zhuǎn)發(fā)的控制消息和到達(dá)根節(jié)點(diǎn)的數(shù)據(jù)包的比特數(shù)。

4.1.2 路由修復(fù)平均時延

路由修復(fù)平均時延是指在網(wǎng)絡(luò)運(yùn)行時間內(nèi)當(dāng)檢測到網(wǎng)絡(luò)出現(xiàn)故障后,所有鏈路故障節(jié)點(diǎn)重新加入到網(wǎng)絡(luò)中所耗費(fèi)的平均時間,表示為

(7)

式中,TRi表示網(wǎng)絡(luò)中的鏈路故障節(jié)點(diǎn)i重新加入到網(wǎng)絡(luò)中所耗費(fèi)的時間;n表示在網(wǎng)絡(luò)運(yùn)行時間內(nèi)出現(xiàn)鏈路故障的節(jié)點(diǎn)總數(shù)。

4.1.3 網(wǎng)絡(luò)生存時間

網(wǎng)絡(luò)生存時間是指在網(wǎng)絡(luò)運(yùn)行時間內(nèi)網(wǎng)絡(luò)中能量耗盡節(jié)點(diǎn)的數(shù)量達(dá)到節(jié)點(diǎn)總數(shù)的10%所耗費(fèi)的時間,表示為

TL=Td-T0

(8)

式中,Td表示網(wǎng)絡(luò)中死亡節(jié)點(diǎn)數(shù)量達(dá)到總的節(jié)點(diǎn)數(shù)量10%的時刻;T0表示網(wǎng)絡(luò)開始運(yùn)行的時刻。

4.1.4 路由環(huán)路產(chǎn)生的概率

路由環(huán)路產(chǎn)生的概率是指在網(wǎng)絡(luò)運(yùn)行時間內(nèi),路由修復(fù)過程中出現(xiàn)路由環(huán)路的鏈路故障節(jié)點(diǎn)數(shù)與鏈路故障節(jié)點(diǎn)總數(shù)量的比值,表示為

ρ=NumRL/NumLB

(9)

式中,NumRL表示路由修復(fù)過程中出現(xiàn)路由環(huán)路的鏈路故障節(jié)點(diǎn)數(shù);NumLB表示網(wǎng)絡(luò)中鏈路故障節(jié)點(diǎn)數(shù)量。

4.2 仿真環(huán)境及參數(shù)設(shè)置

在300 m×300 m的模擬仿真區(qū)域內(nèi)根據(jù)節(jié)點(diǎn)數(shù)量不同設(shè)置6個不同仿真場景,場景中的節(jié)點(diǎn)均隨機(jī)分布且位置一旦固定將不再移動。網(wǎng)絡(luò)中除根節(jié)點(diǎn)外,其余節(jié)點(diǎn)的初始能量相同且在仿真過程中不補(bǔ)給能量。由于節(jié)點(diǎn)受限于能量和處理能力,故節(jié)點(diǎn)數(shù)據(jù)傳輸速率不宜過高。同時,考慮鏈路的有損性,應(yīng)設(shè)定鏈路損耗因子。另外,為了便于節(jié)點(diǎn)記錄其鄰居節(jié)點(diǎn)信息,節(jié)點(diǎn)采用存儲模式。為了使結(jié)果更加可靠,在每個場景中分別多次模擬運(yùn)行上述4種路由修復(fù)算法,取平均值作為最終結(jié)果。主要參數(shù)設(shè)置如表1所示。

表1 主要仿真參數(shù)

4.3 仿真結(jié)果分析

4.3.1 歸一化控制開銷

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

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

4.3.2 路由修復(fù)平均時延

如圖5所示,HLR-RPL、LFR-RPL和LR-RPL的路由修復(fù)平均時延隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大變化不大,而LLR-RPL的路由修復(fù)平均時延隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大變化相對較大。且在每個場景中,HLR-RPL的路由修復(fù)平均時延明顯低于其3種算法,至少降低了32.64%,與引理2分析的結(jié)果一致。分析其主要原因在于，HLR-RPL利用DIS-A消息同時實現(xiàn)鏈路中斷通告過程和尋路過程,有效地降低了路由修復(fù)時延;其次,符合作為鏈路中斷節(jié)點(diǎn)父節(jié)點(diǎn)的鄰居節(jié)點(diǎn)一旦接收到DIS-A消息后立即回復(fù)DIO消息即可修復(fù)鏈路故障,對路由修復(fù)時延有降低作用。

圖5 路由修復(fù)平均時延比較Fig.5 Comparison of the average routing repair delay

4.3.3 網(wǎng)絡(luò)生存時間

如圖6所示,與LFR-RPL、LR-RPL和LLR-RPL相比,HLR-RPL算法的網(wǎng)絡(luò)生存時間至少能夠延長9.28%。

圖6 網(wǎng)絡(luò)生存時間比較Fig.6 Comparison of the network survival time

分析其主要原因在于，HLR-RPL通過DIS-A消息同時實現(xiàn)鏈路中斷通告過程和尋路過程,以及減少了不必要回復(fù)DIO消息的鄰居節(jié)點(diǎn)個數(shù),從而降低了節(jié)點(diǎn)的能耗;其次,HLR-RPL通過子節(jié)點(diǎn)切換機(jī)制能夠使得修復(fù)后的網(wǎng)絡(luò)拓?fù)溥_(dá)到最優(yōu)狀態(tài),減少了數(shù)據(jù)分組的傳輸跳數(shù),從而降低了數(shù)據(jù)分組的傳輸能耗。

4.3.4 路由環(huán)路產(chǎn)生的概率

如表2所示,HLR-RPL、LLR-RPL和LFR-RPL在各個場景中的路由環(huán)路產(chǎn)生概率均為0,表明均具有較好的可靠性。分析其主要原因在于，當(dāng)檢測到鏈路出現(xiàn)故障后,HLR-RPL和LFR-RPL中的鏈路中斷節(jié)點(diǎn)選擇其子節(jié)點(diǎn)作為父節(jié)點(diǎn)的概率為0;LLR-RPL中的鏈路故障節(jié)點(diǎn)僅選擇接收到鏈路中斷通告消息的子節(jié)點(diǎn)進(jìn)行鏈路反轉(zhuǎn),從而徹底避免了路由環(huán)路的產(chǎn)生;然而,LR-RPL的路由環(huán)路產(chǎn)生概率隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大逐漸發(fā)生變化,主要原因在于鏈路故障節(jié)點(diǎn)數(shù)量的增加,而一旦當(dāng)鏈路中斷通告消息丟失就會形成路由環(huán)路。

表2 路由環(huán)路產(chǎn)生的概率對比

5 結(jié) 論

由于LLN中現(xiàn)有路由修復(fù)方案存在控制開銷冗余、修復(fù)時延較大和路由環(huán)路等問題,本文提出了HLR-RPL路由算法。為了使路由修復(fù)高效,該算法利用DIS-A消息使得鏈路中斷通告過程和尋路過程同時進(jìn)行;通過減少控制消息回復(fù)機(jī)制,避免所有接收到DIS-A消息的鄰居節(jié)點(diǎn)均回復(fù)DIO消息;通過子節(jié)點(diǎn)切換機(jī)制能夠優(yōu)化網(wǎng)絡(luò)拓?fù)?有利于數(shù)據(jù)的傳輸。理論分析和仿真結(jié)果表明,相對現(xiàn)有路由修復(fù)方案,HLR-RPL能夠有效降低網(wǎng)絡(luò)控制開銷、縮短修復(fù)時延和優(yōu)化網(wǎng)絡(luò)拓?fù)?并且能夠徹底避免路由環(huán)路的產(chǎn)生。在未來工作中,將研究一種適用于動態(tài)的LLN路由修復(fù)算法。

參考文獻(xiàn)：

[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] 姚玉坤,劉江兵,任智,等.集中式網(wǎng)絡(luò)擁塞控制的高效RPL路由協(xié)議[J].系統(tǒng)工程與電子技術(shù),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.