基于鏈路期望壽命的高效路由算法

摘要：隨著物聯(lián)網(wǎng)的不斷發(fā)展，低功耗有損網(wǎng)絡(luò)被廣泛應(yīng)用于各個領(lǐng)域。針對低功耗有損網(wǎng)絡(luò)中移動節(jié)點鏈路頻繁切換導(dǎo)致的較大切換時延問題，提出一種基于鏈路期望壽命的高效路由算法LLE-RPL。該算法在構(gòu)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時，根據(jù)節(jié)點自身屬性與無線鏈路的生存時問選出最優(yōu)父節(jié)點，有效避免了路由判據(jù)單一對網(wǎng)絡(luò)性能造成影響。理論分析和仿真結(jié)果表明，提出的LLE-RPL算法能夠有效地提高網(wǎng)絡(luò)吞吐量，延長網(wǎng)絡(luò)生命周期。

關(guān)鍵詞：低功耗有損網(wǎng)絡(luò);路由算法;生存時間;移動

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）20-0064-02

近年來，隨著物聯(lián)網(wǎng)的迅速發(fā)展，低功耗有損網(wǎng)絡(luò)（LowPower and Lossy Network，LLN）被廣泛應(yīng)用于醫(yī)療保健、軍事指揮以及智慧城市等領(lǐng)域，成為當(dāng)前學(xué)者的研究熱點。LLN是由大量存儲能力、處理能力以及能量受限的無線傳感器節(jié)點組成的網(wǎng)絡(luò)。LLN的鏈路具有不穩(wěn)定性和有損性，存在高丟包率、低帶寬、鏈路不穩(wěn)定等問題，傳統(tǒng)路由算法難以應(yīng)用于LLN。為解決這一問題，國際互聯(lián)網(wǎng)任務(wù)工程組在2012年提出一種基于IPv6的低功耗有損網(wǎng)絡(luò)路由協(xié)議（Routing Protocol f'or LowP㈣er and Lossy Network，RPL）[1-3]。RPL路由協(xié)議有效地滿足了低功耗有損網(wǎng)絡(luò)的要求，但在實際應(yīng)用中仍有一些亟待改進(jìn)的問題，尤其是在節(jié)點移動的環(huán)境中。

目前，國內(nèi)外學(xué)者針對RPL路由協(xié)議的研究取得了大量成果，研究主要集中于網(wǎng)絡(luò)負(fù)載均衡、擁塞控制以及路由修復(fù)等方面。但研究主要是針對LLN中節(jié)點靜態(tài)的環(huán)境，對于LLN節(jié)點移動環(huán)境中的路由技術(shù)研究較少。當(dāng)前，針對LLN節(jié)點移動環(huán)境的研究，在網(wǎng)絡(luò)性能優(yōu)化方面仍需進(jìn)一步提升。文獻(xiàn)[4]提出了一種基于移動節(jié)點位置跟蹤的路由協(xié)議。該協(xié)議是通過設(shè)計一種Corona機(jī)制，將網(wǎng)絡(luò)劃分為以根節(jié)點最大發(fā)射距離為半徑的圓形區(qū)域，節(jié)點根據(jù)自身與根節(jié)點的距離，從而計算節(jié)點的位置坐標(biāo)。該協(xié)議在快速找到替代父節(jié)點作為下一跳方面得到增強，但未有效解決切換延遲和路徑斷開時間較長等問題。文獻(xiàn)[5]通過改進(jìn)RPL協(xié)議中的溪流計時器，使路由協(xié)議支持節(jié)點移動的環(huán)境。該協(xié)議根據(jù)節(jié)點的移動速度來發(fā)送面向目的地的有向無環(huán)圖信息對象消息（DODAG Information Ob-ject，DIO），且在組網(wǎng)過程中采用期望傳輸次數(shù)作為路由度量，從而降低網(wǎng)絡(luò)的控制開銷。該協(xié)議中節(jié)點選擇的父節(jié)點并非最優(yōu)，且路由度量過于單一，容易出現(xiàn)節(jié)點頻繁切換父節(jié)點的問題。

1 RPL路由協(xié)議

RPL路由協(xié)議是針對LLN設(shè)計的距離矢量路由協(xié)議。該協(xié)議通過目標(biāo)函數(shù)和度量集合共同構(gòu)建面向目的地的有向無環(huán)圖DODAG（Destination Oriented Directed Acyclic Graph，DODAG），然后根據(jù)路由度量和約束條件選擇最優(yōu)路徑完成路由過程。RPL定義了三種控制信息，DODAC請求信息DIS（ DODAG Inf'ormati。n SoliCitation），DODAG信息目的廣播對象消息DAO（ Destination Advertisement Object）和DODAG信息對象消息DIO。DIS用于向鄰居節(jié)點請求DODAG信息，DAO用于構(gòu)建上行路由，DIO用于通知有關(guān)DODAG的參數(shù)。

在構(gòu)建DODAG時，Sink節(jié)點向鄰居節(jié)點廣播DIO消息。鄰居節(jié)點根據(jù)接收到的DlO消息決定是否加入DODAG。如果決定加入，將Sink節(jié)點添加到自身的父節(jié)點集中，并返回Sink節(jié)點一個DAO消息。如果決定不加入，則不進(jìn)行任何操作。Sink節(jié)點接收到DAO消息后會更新自己的路由表。該鄰居節(jié)點再廣播更新后的DIO消息到其通信范圍內(nèi)的節(jié)點，接收到DIO消息的節(jié)點決定加入DODAG后返回一個DAO消息，并更新自身路由信息，繼續(xù)廣播。以此類推，節(jié)點通過DIO消息決定是否加入DODAG中。如果一個節(jié)點收到多個DIO消息，會選擇使自己Rank值最小的DlO發(fā)送節(jié)點作為父節(jié)點。如果未收到DIO消息的節(jié)點想加入DODAG，會主動向鄰居節(jié)點發(fā)送DIS消息，當(dāng)鄰居節(jié)點收到DIS消息后會發(fā)送DIO消息進(jìn)行邀請。重復(fù)上述過程，最終通過三種控制信息完成DODAC的構(gòu)建。

2 LLE-RPL路由算法

2.1問題分析

通過對現(xiàn)有移動節(jié)點環(huán)境中的路由算法研究發(fā)現(xiàn)，在構(gòu)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的過程中，節(jié)點選擇最優(yōu)父節(jié)點時忽略了與其備選父節(jié)點之間的鏈路生存時間[6]。當(dāng)無線鏈路生存時間較低的備選父節(jié)點被選為最優(yōu)父節(jié)點時，會導(dǎo)致節(jié)點頻繁地切換父節(jié)點從而引起網(wǎng)絡(luò)震蕩。針對這一問題，本文提出一種基于鏈路期望壽命的高效路由算法LLE-RPL，并對其性能進(jìn)行仿真對比分析。

收稿日期：2020-03-25

基金項目：2019年重慶工商職業(yè)學(xué)院科學(xué)研究項目——面向物聯(lián)網(wǎng)的低功耗有損網(wǎng)絡(luò)路由技術(shù)研究（項目編號：NDYB2019-13）

作者簡介：秦曉琴（1989-），女，講師，工程師，碩士，主要研究方向為無線傳感器網(wǎng)絡(luò)、路由技術(shù)等。

LLE-RPL路由算法中根節(jié)點也被稱之為Sink節(jié)點，主要用于匯聚子節(jié)點上傳的數(shù)據(jù)信息。移動節(jié)點主要用于產(chǎn)生數(shù)據(jù)且將所產(chǎn)生的數(shù)據(jù)向上轉(zhuǎn)發(fā)至Sink節(jié)點。

為了便于分析，在LLE-RPL路由算法中進(jìn)行如下假設(shè)。

（1）網(wǎng)絡(luò)中Sink節(jié)點不具有移動性，其他節(jié)點均可移動。

（2）網(wǎng)絡(luò)中可移動節(jié)點均具有相同的感知覆蓋半徑、物理結(jié)構(gòu)和特性，可感知自身位置信息。

（3）網(wǎng)絡(luò)中可移動節(jié)點間相互獨立，無相互十?dāng)_，速度和方向不會產(chǎn)生突變。

2.2算法設(shè)計

針對節(jié)點移動環(huán)境中LLN現(xiàn)有路由算法所存在的問題，LLE-RPL算法在選擇最優(yōu)父節(jié)點時，考慮了LLN中節(jié)點由于移動特性離開其鄰居節(jié)點通信范圍的時間，即兩者之間無線鏈路生存時間（Link Expiration Time，LET），有效避免子節(jié)點因期望壽命過低引起的頻繁切換，從而最大化延長網(wǎng)絡(luò)的壽命。下面以節(jié)點m為例，其最優(yōu)父節(jié)點選擇的具體操作步驟如下：

步驟1：初始化網(wǎng)絡(luò)后，節(jié)點m將自身的位置信息、移動速度等度量信息添加到DIO控制消息的選項字段中，并且向鄰居節(jié)點廣播該消息;

步驟2：節(jié)點收到鄰居節(jié)點m廣播的DIO控制消息后，獲取消息中攜帶的相關(guān)路由信息，計算兩節(jié)點之間的鏈路生存時間。該節(jié)點選擇生存時間長的鏈路進(jìn)行數(shù)據(jù)傳輸，從而有效降低網(wǎng)絡(luò)延遲，減小路由維護(hù)成本。根據(jù)文獻(xiàn)[6]，LET的計算步驟如下：

（1）假設(shè)當(dāng)前時間為t，節(jié)點m的速度為Vm，位置為Sm，則經(jīng)過時間△t后，節(jié)點m的位置可通過公式（1）得到：

Sm+（t+△t）=Sm（t）+Vm△t

（1）

（2）若是節(jié)點n的速度為Vn，位置為Sn，則m，n兩節(jié)點的相對速度以及相對位置如公式（2）和公式（3）所示：

V（m，n）（t）=Vm（t）-Vn（t）

（2）

S（m，n）（t）=Sm（t）-Sn（t）

（3）

（3）通過公式（2），（3）計算出節(jié)點m，n位置后，則經(jīng)過時間△t后，節(jié)點m，n的相對位置通過公式（4）可知：

D（m，n）（t+△t）=|S（m，n）（t）-V（m，n）（t）△t|

（4）

通過判斷兩點的相對位置D（m，n）（t+△t）是小于節(jié)點m的通信半徑r，從而得出鏈路最大持續(xù)時間LET。

步驟3：節(jié)點n得到其鄰居節(jié)點m的鏈路期望壽命后，通過公式（5）計算自身與鄰居節(jié)點的路由度量值（metric）：

metric=α（ETX（m，n》+（1-α）LET（m，n）

（5）

式中，α為閾值，根據(jù)網(wǎng)絡(luò)場景進(jìn)行設(shè)定。ETX為兩節(jié)點之間的重傳次數(shù)，該值由特定的測試包獲得。路由度量值越大則說明兩節(jié)點之間的傳輸代價越大，反之越小。因此，選擇路由度量值最小的鄰居節(jié)點作為最優(yōu)父節(jié)點。

3仿真分析

本文選用文獻(xiàn)[4]和文獻(xiàn)[5]所提路由算法進(jìn)行對比分析。在300m*300m的仿真區(qū)域內(nèi)，分別構(gòu)建節(jié)點數(shù)為10、30、50、70和90的LLN且節(jié)點隨機(jī)分布，其中根節(jié)點為靜態(tài)節(jié)點，數(shù)量為1。仿真時間為3600s。

如圖1所示，三種算法的網(wǎng)絡(luò)平均壽命隨著LLN網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大而降低，但本文所提算法相較于其他兩種算法較高。其主要原因在于，節(jié)點選擇最優(yōu)父節(jié)點時，綜合考慮了節(jié)點間的期望傳輸次數(shù)和鏈路生存時間，避免了節(jié)點選擇無線鏈路質(zhì)量差和鏈路生存時間短的節(jié)點作為父節(jié)點。

圖2表明，根節(jié)點的吞吐量隨著節(jié)點數(shù)量的增加逐漸加大，而本文所提路由算法相較于其他兩種路由算法，根節(jié)點的吞吐量較高。其主要原因在于：網(wǎng)絡(luò)組網(wǎng)時，節(jié)點根據(jù)無線鏈路的期望壽命進(jìn)行父節(jié)點的選擇，從而使得網(wǎng)絡(luò)能夠最大限度地傳輸數(shù)據(jù)流量。

4結(jié)束語

針對低功耗有損網(wǎng)絡(luò)中移動節(jié)點鏈路頻繁切換導(dǎo)致的較大切換時延問題，提出一種基于鏈路期望壽命的高效路由算法。在構(gòu)建網(wǎng)絡(luò)拓?fù)鋾r，綜合節(jié)點屬性與無線鏈路的生存時間選出最優(yōu)父節(jié)點，使得網(wǎng)絡(luò)平均壽命和根節(jié)點平均吞吐量得到提升。

參考文獻(xiàn)：

[1] Winter T.RFC6550 RPL： routing protocol for low power andlossy networks[S].USA： Internet Engineering Task Force，2012.

[2] THUBERT P.Objective function zero for the routing protocolfor low-power and lossy net works： RFC 6552[S]. Geneva：IETF，2012：1-14.

[3] Liu X， Sheng Z， Yin C. et al. Performance analysis of RoutingProtocol for Low power and Lossy Networks （RPL） in largescale networks[J]. lEEE Intemet of Things Journal，2017，4（6）：2172-2185.

[4]O. Gaddour. A. Koubaa. R. Rangarajan， et al. Co-RPL： RPLrouting for mobile low pmver wireless sensor networks usingCorona mechanismLCl. 2014 9th lEEE International Sympo-sium on Industrial Embedded Systems. Pisa，2014：200-209.

[5] Fotouhi H，Moreira D，Alves Mario. mRPL： Boosting mobilityin the Internet of Things[J]. Ad Hoc Networks. 2015. 26：17-35.

[6]鐘聲.基于分簇的無線光通信網(wǎng)絡(luò)動態(tài)拓?fù)淇刂扑惴ㄑ芯縖D].西安電子科技大學(xué)，2018.

【通聯(lián)編輯：代影】