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

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

關鍵詞：低功耗有損網絡;路由算法;生存時間;移動

中圖分類號：TP311 文獻標識碼：A

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

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

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

1 RPL路由協議

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

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

2 LLE-RPL路由算法

2.1問題分析

通過對現有移動節點環境中的路由算法研究發現，在構建網絡拓撲結構的過程中，節點選擇最優父節點時忽略了與其備選父節點之間的鏈路生存時間[6]。當無線鏈路生存時間較低的備選父節點被選為最優父節點時，會導致節點頻繁地切換父節點從而引起網絡震蕩。針對這一問題，本文提出一種基于鏈路期望壽命的高效路由算法LLE-RPL，并對其性能進行仿真對比分析。

收稿日期：2020-03-25

基金項目：2019年重慶工商職業學院科學研究項目——面向物聯網的低功耗有損網絡路由技術研究（項目編號：NDYB2019-13）

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

LLE-RPL路由算法中根節點也被稱之為Sink節點，主要用于匯聚子節點上傳的數據信息。移動節點主要用于產生數據且將所產生的數據向上轉發至Sink節點。

為了便于分析，在LLE-RPL路由算法中進行如下假設。

（1）網絡中Sink節點不具有移動性，其他節點均可移動。

（2）網絡中可移動節點均具有相同的感知覆蓋半徑、物理結構和特性，可感知自身位置信息。

（3）網絡中可移動節點間相互獨立，無相互十擾，速度和方向不會產生突變。

2.2算法設計

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

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

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

（1）假設當前時間為t，節點m的速度為Vm，位置為Sm，則經過時間△t后，節點m的位置可通過公式（1）得到：

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

（1）

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

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

（2）

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

（3）

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

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

（4）

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

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

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

（5）

式中，α為閾值，根據網絡場景進行設定。ETX為兩節點之間的重傳次數，該值由特定的測試包獲得。路由度量值越大則說明兩節點之間的傳輸代價越大，反之越小。因此，選擇路由度量值最小的鄰居節點作為最優父節點。

3仿真分析

本文選用文獻[4]和文獻[5]所提路由算法進行對比分析。在300m*300m的仿真區域內，分別構建節點數為10、30、50、70和90的LLN且節點隨機分布，其中根節點為靜態節點，數量為1。仿真時間為3600s。

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

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

4結束語

針對低功耗有損網絡中移動節點鏈路頻繁切換導致的較大切換時延問題，提出一種基于鏈路期望壽命的高效路由算法。在構建網絡拓撲時，綜合節點屬性與無線鏈路的生存時間選出最優父節點，使得網絡平均壽命和根節點平均吞吐量得到提升。

參考文獻：

[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]鐘聲.基于分簇的無線光通信網絡動態拓撲控制算法研究[D].西安電子科技大學，2018.

【通聯編輯：代影】