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

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

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

1 引 言

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

當(dāng)前，對于LLN網(wǎng)絡(luò)中出現(xiàn)的鏈路故障已開展了一些研究，提出了多種算法[8-11]。但是，現(xiàn)有路由修復(fù)算法主要存在以下不足：一是路由修復(fù)控制開銷冗余，增大了節(jié)點(diǎn)的能耗速率，從而不能達(dá)到高能效的目的；二是路由修復(fù)時延較大，導(dǎo)致數(shù)據(jù)包端到端傳輸時延增大，從而影響數(shù)據(jù)的傳輸；三是鏈路故障修復(fù)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)未能達(dá)到最佳狀態(tài)，主要原因在于對鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)未進(jìn)一步處理。

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

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

LLN網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不同于傳統(tǒng)的無線傳感器網(wǎng)絡(luò)，結(jié)合其自身特點(diǎn)，本文給出如下定義：

定義1 備選父節(jié)點(diǎn)集。在節(jié)點(diǎn)通信范圍內(nèi)且網(wǎng)絡(luò)深度值小于或等于節(jié)點(diǎn)當(dāng)前父節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的集合，被稱之為節(jié)點(diǎn)的備選節(jié)點(diǎn)集，記為P。

定義2 兄弟節(jié)點(diǎn)集。在節(jié)點(diǎn)通信范圍內(nèi)且網(wǎng)絡(luò)深度值與其相同的鄰居節(jié)點(diǎn)的集合，被稱之為節(jié)點(diǎn)的兄弟節(jié)點(diǎn)集，記為B。

定義3 子節(jié)點(diǎn)集。網(wǎng)絡(luò)深度值大于當(dāng)前節(jié)點(diǎn)且在當(dāng)前節(jié)點(diǎn)通信范圍內(nèi)的鄰居節(jié)點(diǎn)的集合，被稱之為當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)集，記為C。子節(jié)點(diǎn)集又包含非親子節(jié)點(diǎn)集和親子節(jié)點(diǎn)集，其中直接與當(dāng)前節(jié)點(diǎn)處于連接狀態(tài)的子節(jié)點(diǎn)集被稱之為親子節(jié)點(diǎn)集；反之，則被稱之為非親子節(jié)點(diǎn)集。

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

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

圖1 EELDR-RPL算法的網(wǎng)絡(luò)模型圖Fig.1 Network model of EELDR-RPL

3 EELDR-RPL算法

針對LLN網(wǎng)絡(luò)中現(xiàn)有路由修復(fù)算法存在控制開銷冗余以及路由修復(fù)時延較大等問題，EELDR-RPL算法在路由修復(fù)的過程中進(jìn)行了如下改進(jìn)：

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

(2)為了使得鏈路故障節(jié)點(diǎn)能夠快速地重新接入網(wǎng)絡(luò)，提出了一種“自適應(yīng)調(diào)整節(jié)點(diǎn)網(wǎng)絡(luò)深度值”機(jī)制，即鏈路故障節(jié)點(diǎn)根據(jù)其鄰居節(jié)點(diǎn)信息自適應(yīng)地調(diào)整自身的網(wǎng)絡(luò)深度值；

(3)為了使得修復(fù)之后的網(wǎng)絡(luò)拓?fù)涓鼉?yōu)，提出了一種“鏈路故障節(jié)點(diǎn)子節(jié)點(diǎn)自適應(yīng)切換”機(jī)制，即鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)通過控制消息獲取到的鏈路故障節(jié)點(diǎn)鄰居節(jié)點(diǎn)信息以及自身鄰居節(jié)點(diǎn)信息進(jìn)行自適應(yīng)地切換當(dāng)前鏈路連接狀態(tài)。

3.1 零額外控制開銷通告鏈路故障及鄰居節(jié)點(diǎn)信息機(jī)制

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

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

當(dāng)檢測到任意節(jié)點(diǎn)與其最優(yōu)父節(jié)點(diǎn)之間的無線鏈路出現(xiàn)故障后，通過廣播N-DIS控制消息重新申請接入到LLN網(wǎng)絡(luò)中。當(dāng)鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)接收到上述N-DIS控制消息后，根據(jù)L字段便可獲知鏈路故障節(jié)點(diǎn)與其最優(yōu)父節(jié)點(diǎn)之間的當(dāng)前無線鏈路連接狀態(tài)。同時，鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)根據(jù)N-DIS控制消息的N字段便可獲知鏈路故障節(jié)點(diǎn)的鄰居節(jié)點(diǎn)信息，從而便于“鏈路故障節(jié)點(diǎn)子節(jié)點(diǎn)自適應(yīng)切換機(jī)制”的實(shí)施和操作。

3.2 自適應(yīng)調(diào)整節(jié)點(diǎn)網(wǎng)絡(luò)深度值機(jī)制

網(wǎng)絡(luò)深度值的大小反映出節(jié)點(diǎn)在網(wǎng)絡(luò)中的大致位置。距離根節(jié)點(diǎn)位置越近，節(jié)點(diǎn)的網(wǎng)絡(luò)深度值相對越小。為了避免路由環(huán)路的產(chǎn)生，子節(jié)點(diǎn)的網(wǎng)絡(luò)深度值必須小于其父節(jié)點(diǎn)的網(wǎng)絡(luò)深度值[6]。

當(dāng)檢測到LLN網(wǎng)絡(luò)中出現(xiàn)鏈路故障節(jié)點(diǎn)時，提出了一種新的網(wǎng)絡(luò)深度值表示方法，即利用小數(shù)表示節(jié)點(diǎn)更新后的網(wǎng)絡(luò)深度值，以便于鏈路故障節(jié)點(diǎn)能夠根據(jù)其緩存的鄰居節(jié)點(diǎn)信息自適應(yīng)的調(diào)整自身的網(wǎng)絡(luò)深度值，從而快速地重新接入網(wǎng)絡(luò)而不受RPL標(biāo)準(zhǔn)的約束。

假設(shè)鏈路故障節(jié)點(diǎn)Q的當(dāng)前網(wǎng)絡(luò)深度值為m，其中m為整數(shù)，那么節(jié)點(diǎn)Q的網(wǎng)絡(luò)深度值Rank將根據(jù)公式(1)進(jìn)行自適應(yīng)地調(diào)整：

(1)

當(dāng)鏈路故障節(jié)點(diǎn)Q的網(wǎng)絡(luò)深度值為m.1時，相對于其他節(jié)點(diǎn)，其網(wǎng)絡(luò)深度值為(m+1)；當(dāng)鏈路故障節(jié)點(diǎn)Q的網(wǎng)絡(luò)深度值為m.2時，相對于其他節(jié)點(diǎn)，其網(wǎng)絡(luò)深度值為(m+2)。那么，鏈路故障節(jié)點(diǎn)Q的網(wǎng)絡(luò)深度值自適應(yīng)調(diào)整策略具體如下：

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

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

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

(4)當(dāng)鏈路故障節(jié)點(diǎn)Q從其緩存中檢測到自身無可建立連接的鄰居節(jié)點(diǎn)時，將其網(wǎng)絡(luò)深度值Rank更新為，同時將N-DIS控制消息中的L字段設(shè)置為1，N字段設(shè)置為00，并廣播N-DIS控制消息將其鏈路故障狀態(tài)通告給其子節(jié)點(diǎn)，等待新一輪網(wǎng)絡(luò)拓?fù)涞闹貥?gòu)。

3.3 鏈路故障節(jié)點(diǎn)子節(jié)點(diǎn)自適應(yīng)切換機(jī)制

為了優(yōu)化鏈路故障修復(fù)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，需要對鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)當(dāng)前連接狀態(tài)進(jìn)行相應(yīng)的調(diào)整。鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)依據(jù)鏈路故障節(jié)點(diǎn)廣播的N-DIS控制消息以及自身鄰居節(jié)點(diǎn)信息進(jìn)行自適應(yīng)地更換與當(dāng)前鏈路故障節(jié)點(diǎn)之間的連接狀態(tài)，以此達(dá)到優(yōu)化鏈路故障修復(fù)之后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的目的。鏈路故障節(jié)點(diǎn)子節(jié)點(diǎn)自適應(yīng)切換機(jī)制的具體實(shí)施過程如下：

(1)當(dāng)鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)監(jiān)聽到鏈路故障節(jié)點(diǎn)發(fā)送的N-DIS控制消息后，檢查N-DIS控制消息中的L字段。如果L字段的值為1，則繼續(xù)檢查N-DIS控制消息中的N字段。

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

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

(4)如果N字段的值為01，表明鏈路故障節(jié)點(diǎn)當(dāng)前僅擁有可直接建立連接的子節(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)將不再與當(dāng)前鏈路故障節(jié)點(diǎn)繼續(xù)維持父子關(guān)系，并從備選父節(jié)點(diǎn)集或是兄弟節(jié)點(diǎn)集中選擇一個合適的節(jié)點(diǎn)建立新的連接狀態(tài)；反之，該鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)則繼續(xù)與當(dāng)前鏈路故障節(jié)點(diǎn)維持父子關(guān)系，并將其當(dāng)前網(wǎng)絡(luò)深度值更新為(m+1.2)。

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

3.4 EELDR-RPL算法操作步驟

EELDR-RPL算法的詳細(xì)操作步驟如下：

Step1 在網(wǎng)絡(luò)拓?fù)涑跏蓟瘎?chuàng)建過程中，每個節(jié)點(diǎn)均存儲鄰居節(jié)點(diǎn)的信息，并周期性地監(jiān)聽其親子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)信息。

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

Step3 鏈路故障節(jié)點(diǎn)選擇其備選父節(jié)點(diǎn)集中最先回復(fù)DIO控制消息的節(jié)點(diǎn)作為新的父節(jié)點(diǎn)，且其子節(jié)點(diǎn)根據(jù)監(jiān)聽鏈路故障節(jié)點(diǎn)組播的N-DIS控制消息決定繼續(xù)與其維持父子關(guān)系。

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

Step5 鏈路故障節(jié)點(diǎn)選擇其兄弟節(jié)點(diǎn)集中最先回復(fù)DIO控制消息的節(jié)點(diǎn)作為新的父節(jié)點(diǎn)，并將其當(dāng)前網(wǎng)絡(luò)深度值加上0.1，且其子節(jié)點(diǎn)根據(jù)監(jiān)聽鏈路故障節(jié)點(diǎn)組播的N-DIS控制消息以及其備選父節(jié)點(diǎn)集是否為空集，從而決定是否繼續(xù)與當(dāng)前鏈路故障節(jié)點(diǎn)繼續(xù)維持父子關(guān)系。

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

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

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

4 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

4.2 仿真結(jié)果分析

4.2.1歸一化控制開銷比較

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

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

4.2.2鏈路故障平均修復(fù)時延比較

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

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

4.2.3根節(jié)點(diǎn)平均吞吐量比較

圖5表明，F(xiàn)RR-RPL、LRR-RPL和EELDR-RPL算法的根節(jié)點(diǎn)平均吞吐量均隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大而逐漸增大，但是EELDR-RPL算法的根節(jié)點(diǎn)平均吞吐量均明顯高于FRR-RPL算法和LRR-RPL算法。通過分析發(fā)現(xiàn)，其主要原因在于：EELDR-RPL算法在路由修復(fù)過程中，鏈路故障節(jié)點(diǎn)根據(jù)其獲知的鄰居節(jié)點(diǎn)信息自適應(yīng)地對自身的網(wǎng)絡(luò)深度值進(jìn)行調(diào)整后，通過少量的控制消息便可較快地重新接入網(wǎng)絡(luò)，能夠有效降低數(shù)據(jù)包端到端平均傳輸時延，而根節(jié)點(diǎn)平均吞吐量與數(shù)據(jù)包端到端平均傳輸時延成反比關(guān)系；EELDR-RPL算法在路由修復(fù)過程中，鏈路故障節(jié)點(diǎn)的子節(jié)點(diǎn)根據(jù)接收到的N-DIS控制消息以及其鄰居節(jié)點(diǎn)信息判斷是否需要維持與當(dāng)前鏈路故障節(jié)點(diǎn)的連接狀態(tài)，優(yōu)化了鏈路故障修復(fù)后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，降低了數(shù)據(jù)包的平均傳輸跳數(shù)，相當(dāng)于降低了數(shù)據(jù)包端到端平均傳輸時延。

圖5 根節(jié)點(diǎn)平均吞吐量比較

5 結(jié)束語

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