基于簇父集協作通信的低功耗有損網絡路由算法優化

姚玉坤，劉江兵，李小勇

(移動通信技術重慶市重點實驗室(重慶郵電大學)，重慶400065)

基于簇父集協作通信的低功耗有損網絡路由算法優化

姚玉坤，劉江兵*，李小勇

(移動通信技術重慶市重點實驗室(重慶郵電大學)，重慶400065)

(*通信作者電子郵箱liujb_cqupt@163.com)

針對當前低功耗有損網絡(LLN)中基于簇父集協作通信的路由算法(CRPL)沒有考慮節點剩余能量,存在不能有效地均衡節點能耗和最大化延長網絡壽命的問題，提出一種高效的基于簇父集協作通信的低功耗有損網絡路由(RPL)算法(HE-CRPL)。所提算法采取了三個優化思路:一是同時考慮節點間無線鏈路質量和節點剩余能量進行簇父節點的選擇；二是在簇父節點優先級判定和最優簇父集的選擇過程中把節點間的無線鏈路質量和簇父節點的期望壽命(ELT)相結合；三是在網絡拓撲初始化的過程中通過利用目的地通告對象(DAO)消息攜帶簇父節點優先級列表告知最優簇父集中簇父節點的優先級順序。仿真結果表明，與CRPL算法相比，HE-CRPL算法在延長網絡生存時間、提高數據包投遞成功率和減少數據包重傳次數等方面的性能得到了提升，其中網絡生存時間提高了18.7%，數據包重傳次數降低了15.9%。

低功耗有損網絡；簇父集；協作通信；優先級列表；剩余能量；期望壽命

0 引言

近年來，隨著信息與通信技術和物聯網技術的快速發展，低功耗有損網絡(Low Power and Lossy Network, LLN)在工業控制[1]、醫療保健[2]和環境檢測[3]等領域的應用越來越廣泛; 然而，LLN因為無線傳感器節點的處理能力、內存大小和功率等性能方面的缺陷以及無線通信鏈路質量的不穩定而受到制約。因此，LLN的上述特征給LLN中的路由協議設計帶來極大挑戰[4-5]。

LLN通常用于一些特殊的應用場景，使得無線傳感器節點的電池不易更換因而能量受限，因此在最小化節點能量消耗的同時最大化延長網絡壽命是LLN中路由協議設計的關鍵。已有的路由協議，如移動Ad-Hoc網絡中的按需距離矢量路由協議(Ad-Hoc On-demand Distance Vector, AODV)[6]和動態源路由(Dynamic Source Routing, DSR)[7]因為路由開銷較大而不適用于LLN的應用場景，因此互聯網工程任務組(Internet Engineering Task Force, IETF)的低功耗路由算法工作組(Routing over LLN, ROLL)制定了一種基于IPv6的按需低功耗有損路由協議(Routing Protocol for Low Power and Lossy Networks, RPL)[8]。

隨著工業界和學術界對LLN的深入研究，目前已取得大量研究成果。為了滿足不同應用場景的多樣化需求，ROLL工作組在文獻[9]中提出了適用于LLN中的多種路由度量標準和約束條件，但未對每種路由度量標準和約束條件進行詳細量化。

目前，ROLL工作組規定了兩種目標函數：一種是將跳數作為度量標準的零目標函數(Objective Function Zero, OF0)[10],OF0僅考慮源節點到根節點之間的傳輸跳數加快了無線鏈路質量較差的節點的能耗速率；另一種是將期望傳輸次數(Expected Transmission Count, ETX)作為度量標準的具有遲滯性的最小網絡深度目標函數(Minimum Rank with Hysteresis Objective Function, MRHOF)[11]，MRHOF僅考慮ETX，加快了無線鏈路質量較好的節點的能量消耗速率。

由于基于上述兩種目標函數的RPL路由算法均無法均衡網絡中節點能耗和最大化網絡壽命，文獻[12]在單路徑RPL路由的基礎上提出了一種纏繞多路徑的改進策略。該策略將大量連續數據流按鏈路的路徑權重分發到不同的路徑上傳輸，能夠均衡負載的能耗。但在路徑權重的計算中未考慮節點的剩余能量，不能有效地延長網絡壽命。

文獻[13]提出了一種基于多邊界路由器的負載均衡路由協議。該協議通過網關檢測邊界路由器的流量信息，判斷流量是否過載。當流量過載時，利用網關計算網絡的不均衡度并和切換閾值進行比較決定是否通知邊界路由器啟動負載均衡機制。該協議的缺陷在于當網絡的不均衡度低于切換閾值時，不能達到負載均衡的目的，無法徹底解決網絡擁塞問題。

文獻[14]提出了一種基于節點期望壽命(Expected LifeTime, ELT)的均衡節點能量消耗的RPL路由算法。該算法通過計算網絡拓撲中每個節點的ELT，根據ELT判斷每條路徑上的能量瓶頸節點，通過減少能量瓶頸節點的能耗達到延長網絡壽命的目的。但在減少能量瓶頸節點的能耗過程中，加快了其他節點的能耗，同時子節點頻繁更換父節點會產生網絡震蕩，并不能有效地延長網絡壽命。

文獻[15]提出了一種負載均衡的機會RPL路由算法(Opportunistic Routing Protocol for LLN, ORPL)，該算法在RPL路由協議的基礎上融入機會路由算法，根據中繼節點當前剩余能量和通信情況不斷地調整中繼節點的喚醒間隔。喚醒間隔的大小反映出中繼節點轉發數據包的概率，即喚醒間隔越大，中繼節點轉發數據包的概率越小。通過控制中繼節點的喚醒間隔達到控制節點的能耗的目的。該算法的缺陷在于傳輸數據包時未考慮節點間的無線鏈路質量，導致丟包率上升，從而增加了發送節點的能量開銷。

文獻[16]提出了一種基于簇父集協作通信的RPL路由算法 (Cluster parent set based Routing Protocol for LLN, CRPL)，該算法的核心思想是通過簇父集協作轉發數據包到達根節點。在簇父集協作通信的算法中考慮無線鏈路質量，能夠達到均衡節點能耗和延長網絡壽命的目的。但是在該算法中并未考慮簇父節點的剩余能量，導致簇父集中剩余能量不足但優先級較高的簇父節點的能量過早耗盡，不能有效地均衡節點能耗和延長網絡壽命。

針對上述路由算法的缺陷，本文在CRPL算法的基礎上提出一種高效的基于簇父集協作通信的RPL路由算法(High-Efficient Cluster parent set based Routing Protocol for LLN, HE-CRPL)并進行了仿真驗證。

1 網絡模型及問題描述

1.1 網絡模型

針對由N個無線傳感器節點(中繼節點和葉子節點)和1個根節點(邊界路由器)組成的低功耗有損網絡模型，如圖1所示。

圖1 基于HE-CRPL算法的網絡拓撲模型Fig. 1 Network topology model based on HE-CRPL algorithm

為了便于問題分析，給出以下假設：

1)所有無線傳感器節點均部署在一個正方形監測區域內，根節點位于正方形監測區域正上方。所有無線傳感器節點位置一旦確定，將不再發生移動。

2)網絡拓撲初始化時，所有無線傳感器節點的性能和參數保持一致，即節點的初始能量、傳輸功率、內存大小和數據處理能力等均相同。

3)根節點一直處于工作狀態(時刻保持監聽狀態)，不進入休眠模式。其余所有無線傳感器節點的休眠時間均較短，在通信范圍內都能夠監聽到鄰居節點的工作狀態。

4)根節點的能量可以無限制補充，網絡中其余所有無線傳感器節點的能量均不能補充，由電池提供能量，且中途不更換電池，直至電池能量耗盡。

5)葉子節點只產生數據分組，不轉發其他節點的數據分組。中繼節點既能夠產生數據分組，又可以轉發其他節點的數據分組。

為了便于問題分析，給出以下定義。

定義1 最大簇父集。最大簇父集是指由一個子節點的所有簇父節點組成的集合。如圖1所示，節點H的最大簇父集為節點B、C、D組成的集合{B,C,D}。

定義2 期望壽命因子系數。期望壽命因子系數是指最大簇父集中各個簇父節點的ELT在最大簇父集中所占權重的倒數，用θ表示。

1.2 問題描述

CRPL算法的核心思想是通過計算選出LLN中每個節點(根節點除外)的最優簇父集，通過最優簇父集協作轉發數據包到達根節點，完成數據包的匯聚過程。該算法將節點間的無線鏈路質量作為簇父節點的選擇標準；其次依據簇父節點成功傳輸一個數據包到達根節點的傳輸代價判斷簇父節點的優先級順序；然后依據源節點成功傳輸一個數據包經過簇父集到達根節點的累積傳輸代價選擇最優簇父集；最后通過將最優簇父集中的簇父節點的優先級列表添加到待發送數據包的頭部告知最優簇父集中簇父節點的優先級順序。通過深入研究，作者發現該算法存在以下3個問題：

1)選擇簇父節點時僅依據節點之間的無線鏈路質量，而當剩余能量較低的節點被選擇為簇父節點時，由于沒有考慮簇父節點的剩余能量，會加劇剩余能量不足的簇父節點的能耗速率，無法有效地達到節點能耗均衡的目的，降低了網絡生存時間。

2)簇父節點優先級的高低依據簇父節點成功傳輸一個數據包到達根節點的傳輸代價大小決定，而未考慮源節點成功傳輸一個數據包到達簇父節點的傳輸代價。此外，傳輸代價的計算僅僅考慮了節點間的無線鏈路質量，未考慮簇父節點的ELT，從而影響簇父節點優先級的判定。同樣，在選擇最優簇父集的過程中也因為未考慮簇父節點的ELT而影響最優簇父集的選擇。

3)源節點將優先級列表添加到需發送數據包的頭部，通過數據包的傳輸告知簇父集中簇父節點的優先級順序。由于無線鏈路有損特性，無法確定最優簇父集中所有簇父節點均接收到攜帶有簇父節點優先級列表的數據包，從而無法確保最優簇父集中所有簇父節點都獲知優先級列表。一旦某個簇父節點未成功接收到數據包將會導致源節點在傳輸下一個數據包時，需再次將優先級列表添加到數據包的頭部，從而增大了源節點的能耗。

2 HE-CRPL路由算法的優化機制

本文針對CRPL算法中存在的上述三個問題提出改進算法HE-CRPL，在HE-CRPL算法中提出了四種優化機制，分別是簇父節點選擇機制、簇父節點優先級判定機制、最優簇父集選擇機制和優先級列表攜帶機制。

2.1 簇父節點選擇機制

簇父節點選擇機制涉及一個父節點作為理想的簇父節點應滿足兩個條件：第一，父節點與子節點之間的無線鏈路質量高于設定的鏈路質量閾值；第二，父節點的剩余能量同樣應高于設定的能量閾值。在LLN中構建面向目的地有向無環圖(Destination Oriented Directed Acyclic Graph, DODAG)的過程中，中繼節點將自身的剩余能量信息和無線鏈路質量信息添加到DODAG信息對象(DODAG Information Object, DIO)中。當某一節點接收到鄰居節點廣播的DIO消息后，判斷鄰居節點的網絡深度值(Rank)是否低于自身的Rank值。如果上述條件滿足，該節點則從收到的DIO消息中獲取鄰居節點的無線鏈路質量信息和剩余能量信息，并分別判斷無線鏈路質量和節點剩余能量是否滿足要求。

隨著網絡中節點的能量不斷消耗和網絡拓撲周期性的重建，當某一節點與其全部父節點之間的無線鏈路質量均低于無線鏈路質量閾值時，選取無線鏈路質量相對較高的無線鏈路對應的父節點作為簇父節點。當某一節點的全部父節點的剩余能量均低于能量閾值時，選取剩余能量相對較高的父節點作為簇父節點。具體判斷方法遵循圖2所示的流程。

2.2 簇父節點優先級判定機制

簇父節點優先級判斷機制是指在網絡拓撲初始化過程中，分別計算源節點成功傳輸一個數據包經過其各個簇父節點到達根節點的傳輸代價，傳輸代價值越小，賦予簇父節點的優先級越高。在簇父集中，優先級越高的簇父節點具有優先轉發數據包的特性。簇父節點優先級的具體判定步驟如下：

圖2 簇父節點的選擇流程Fig. 2 Flow chart of cluster parent node selection

步驟1 在網絡拓撲周期性的構建過程中，子節點獲得與簇父節點之間的無線鏈路質量信息和簇父節點剩余能量信息后，計算每個簇父節點的期望壽命ELT[17]。ELT的計算如式(1)，式(1)中各個度量值的物理意義如表1所示。

(1)

其中：Ttotal(j)和ETX(j,CPS(j))的計算如式(2)和式(3)所示:

(2)

(3)

其中：Tgen(j)表示簇父節點j產生的數據包，Ttotal(b)表示簇父節點j收到其子節點b發送的數據包，pjl表示節點j與其簇父節點l之間的無線鏈路質量。

表1 ELT的計算公式中各度量值的物理意義Tab. 1 Physical meaning of each metric in ELT

步驟2 根據式(4)計算簇父節點j的期望壽命ELT(j)在最大簇父集中所占的權重。

(4)

步驟3 根據式(5)計算每一個簇父節點的期望壽命因子系數θ。

θj=1/Kj

(5)

步驟4 根據式(6)分別計算源節點成功傳輸一個數據包經過其各個簇父節點到達根節點的傳輸代價，并根據傳輸代價值的大小判定簇父節點的優先級順序。

(6)

式中:Pi, j∈CPS(i)表示節點i與簇父集CPS(i)中各簇父節點之間的無線鏈路質量，Cj表示簇父節點j成功傳輸一個數據包到達根節點的傳輸代價，Ci→j∈CPS(i)→Root表示節點i成功傳輸一個數據包經過其簇父節點j到達根節點的傳輸代價。根據傳輸代價值Ci→j∈CPS(i)→Root的大小可以判斷簇父集中各個簇父節點的優先級，即Ci→j∈CPS(i)→Root越小，簇父節點優先級越高，Ci→j∈CPS(i)→Root越大，簇父節點優先級越低。

2.3 最優簇父集選擇機制

最優簇父集選擇機制是指簇父節點優先級判定之后，源節點分別計算成功傳輸一個數據包經過其各個簇父集到達根節點的傳輸累積代價，傳輸累積代價最小值對應的簇父集為最優簇父集。端到端傳輸累積代價的計算與簇父節點優先級判定類似，也需要同時考慮節點間的無線鏈路質量和簇父節點的ELT。傳輸累積代價的計算步驟如下：

步驟1 通過簇父節點選擇機制選出合適的簇父節點，將簇父節點劃分為不同的簇父集。例如在圖1中，節點K有三個簇父節點E、H和G，其簇父集組合方式則有7種，分別為{E}、{H}、{G}、{E,H}、{E,G}、{H,G}和{E,H,G}。

步驟2 通過簇父節點優先級判定機制獲知子節點的每個簇父節點的優先級順序。例如在圖1中，假設節點K與其簇父節點E、H和G之間的無線鏈路質量分別為0.8、0.6和0.7，如何計算節點間的無線鏈路質量不在本文考慮范圍內，由數據鏈路層決定。同時假設通過式(1)計算得知節點E、H和G的期望壽命分別為50、25和25，且節點E、H和G成功傳輸一個數據包到達根節點的傳輸代價分別為4、3和2。根據式(6)計算得知節點K分別成功傳輸一個數據包經過簇父節點E、H和G到達根節點的傳輸代價大小為H>G>E，故簇父節點E、H和G的優先級順序為E>G>H。

步驟3 分別計算節點K成功傳輸一個數據包到達其各簇父集的聯合代價和各簇父集成功轉發一個數據包到達根節點的剩余路徑代價。聯合代價的計算如式(7)所示，剩余路徑代價的計算如式(8)所示:

(7)

(8)

步驟4 根據步驟3計算得知的聯合代價ETXCPS(i)和剩余路徑代價RCCPS(i)，由式(9)分別計算節點K成功傳輸一個數據包經過其各個簇父集到達根節點的傳輸累積代價CCPSi,CPS(i)，CCPSi,CPS(i)最小值對應的簇父集為最優簇父集。計算得知節點K成功傳輸一個數據包經過簇父集{E,G}到達根節點的CCPSi,CPS(i)最小，故最優簇父集為{E,G}。

CCPSi,CPS(i)=ETXCPS(i)+RCi,CPS(i)

(9)

2.4 簇父節點優先級列表攜帶機制

簇父節點優先級列表攜帶機制是指在網絡拓撲初始化的過程中，首先依據簇父節點優先級判斷機制獲知子節點的簇父節點優先級順序，然后通過最優簇父集判定機制獲知子節點的最優簇父集后，子節點將其最優簇父集中簇父節點優先級列表添加到目的地通告對象(Destination Advertisement Object, DAO)中，通過回復攜帶優先級列表的DAO消息告知簇父節點在最優簇父集中的優先級順序。簇父節點收到攜帶優先級列表的DAO消息后，檢查優先級列表中是否包含其自身信息。如果包含其自身信息，則提取節點優先級列表并存儲。反之，如果不包含自身信息則丟棄DAO消息。

3 HE-CRPL路由算法的操作步驟

HE-CRPL路由算法的核心思想在于利用簇父節點協作轉發數據包，均衡網絡中節點能耗，同時降低數據包的丟包率，減少數據包的重傳，能夠高效地利用帶寬資源、延長網絡整體壽命和提升數據包的投遞成功率。例如在圖1中，假設節點H的最優簇父集為{B,C,D}，且最優簇父集中簇父節點B、C和D的優先級順序為C>D>B。如圖3所示，最優簇父集{B,C,D}協作通信的步驟如下。

圖3 簇父集協作通信示意圖Fig. 3 Diagram of cluster parent set collaborative communication

步驟1 網絡拓撲初始化完成后，節點H開始傳輸數據包并開啟重傳計時器T1。

步驟2 最優簇父集{B,C,D}中的節點C收到數據包后，先將其緩存，然后判斷在最優簇父集中的優先級順序。節點C檢測到其優先級最高，于是向節點H回復ACK消息，并向上一跳轉發先前緩存的該數據包。本文中不考慮ACK消息發生丟包情況，因為它可以通過復雜的編碼技術恢復.

步驟3 節點D收到數據包后，同樣先緩存該數據包，然后檢測其在最優簇父集中的優先級順序。節點D檢測到優先級順序低于節點C，于是開啟ACK計時器T2，開始監聽節點C是否向節點H回復ACK消息。如果節點D監聽到節點C已回復ACK消息，則丟棄先前緩存的數據包，且停止ACK計時器T2并歸零。如果節點D在ACK計時器T2到期后依舊未監聽到節點C向節點H回復ACK消息，節點D則立刻向節點H回復ACK消息，并向上一跳轉發先前緩存的該數據包。

步驟4 節點B重復節點D的處理過程，開啟ACK計時器T3，開始監聽節點C和D是否向節點H回復ACK消息。如果在ACK計時器T2到期后，節點B未監聽到節點C或D向節點H回復ACK消息，節點B則立刻向節點H回復ACK消息，并向上一跳轉發先前緩存的該數據包.

步驟5 只要節點H收到最優簇父集{B,C,D}中的任意一個簇父節點回復的ACK消息，節點H則取消重傳計時器T1，并向最優簇父集{B,C,D}傳輸下一個數據包。如果節點H在重傳計時器T1到期后依舊未收到其最優簇父集{B,C,D}中任意一個簇父節點回復的ACK消息，則重傳上一個數據包，重置重傳計時器T1，并重復上述所有步驟。

4 仿真實驗及結果分析

本文采用contiki2.7操作系統的COOJA軟件進行仿真平臺搭建，選取RPL算法、ORPL算法和CRPL算法作為參照對象，在相同場景條件下通過仿真對比分析與HE-CRPL算法在不同節點數量的網絡中的網絡生存時間、數據包投遞成功率和數據包重傳次數性能指標上的差異。

4.1 網絡場景及參數設置

為了評估HE-CRPL路由算法的性能相對于RPL算法、ORPL算法和CRPL算法的優越性，在300 m×300 m的正方形區域構建節點數分別為20、40、60、80且節點隨機分布的低功耗有損網絡，其無線信道采用陰影衰落模型。LLN中的節點通常有兩種工作模式：存儲模式和非存儲模式。在仿真過程中節點選擇存儲模式，且每次仿真重復10次，最終取平均值作為仿真結果。具體仿真參數設置如表2所示。

表2 仿真參數設定Tab. 2 Simulation parameters setting

4.2 仿真結果分析

1)網絡生存時間。

網絡生存時間定義為網絡初始化過后出現第一個能量耗盡的節點所耗費的時間，是衡量網絡性能的一項重要指標。從圖4中可以得知隨著網絡中節點數量的增加，4種算法的網絡生存時間均呈下降趨勢。這是因為隨著節點數量的增加，網絡密度增大，導致根節點附近的節點轉發數據包的數量急劇增加，加快了附近節點能量消耗，因而網絡生存時間呈下降趨勢。但是HE-CRPL算法明顯優于其他3種算法，相對于RPL算法和ORPL算法，HE-CRPL算法通過簇父集協作通信降低了發送節點數據包重傳消耗的能量，同時使簇父節點的能耗實現均衡；相對于CRPL算法， HE-CRPL算法選擇簇父節點時考慮了節點的剩余能量，從而不選擇優先級較高但剩余能量不足的節點作為簇父節點。此外，通過DAO消息攜帶簇父節點優先級列表，在數據傳輸過程中能夠有效地避免因丟包重復將優先級列表添加到數據包中，從而降低了發送節點的能量開銷。

圖4 網絡生存時間比較Fig. 4 Comparison of network lifetime

2)數據包投遞成功率。

數據包投遞成功率是指數據包成功到達根節點的個數與網絡中源節點發送數據包總數的比值。從圖5可以得知隨著網絡中節點數量的增加，4種算法的數據包投遞成功率均不斷降低。因為隨著節點數量的增加，網絡密度增大，數據包的傳輸距離相對增大，由于無線鏈路有損特性，導致丟包率增加。但是HE-CRPL算法優于其他3種算法，原因在于相對于RPL算法和ORPL算法，HE-CRPL算法通過簇父集協作通信方式傳輸數據包，降低了數據包因丟包而重傳的概率，從而提高了數據包的投遞成功率；相對于CRPL算法，HE-CRPL算法在判定簇父節點的優先級順序和選擇最優簇父集時綜合考慮了簇父節點的ELT，使得簇父節點的優先級判定更加準確，最優簇父集的選擇更加合理，從而有利于數據包的傳輸；同時ELT的計算過程中考慮了節點中緩存的數據包數量，能夠有效地降低網絡擁塞發生的概率，從而降低了數據包因發生網絡擁塞而產生的丟失率。

圖5 數據包投遞成功率比較Fig. 5 Comparison of packet delivery rate

3)數據包重傳次數。

若中繼節點未成功收到源節點發送的數據包則會導致源節點重傳該數據包。圖6是不同節點數量的網絡對不同路由算法數據包重傳次數影響的仿真結果。從圖中可以得知隨著網絡規模的擴大，4種算法的數據包重傳次數均不斷增加。但HE-CRPL算法優于其他3種算法，相對于RPL算法和ORPL算法，原因在于HE-CRPL算法通過簇父集協作轉發數據包，可以盡可能避免因數據包在某一條鏈路上發生丟包而導致源節點重傳該數據包，能夠最大化提高數據包投遞成功率，從而最大限度地降低了數據包的重傳次數；相對于CRPL 算法，HE-CRPL算法在計算簇父節點的ELT時考慮了節點中數據包的緩存數量，能夠有效地降低數據包因緩存或是網絡擁塞而導致丟包發生的概率，從而降低了數據包重傳次數。

圖6 數據包重傳次數比較Fig. 6 Comparison of the number of data packet retransmission

5 結語

本文針對LLN的相關特點，提出一種高效的基于簇父集協作通信的RPL路由算法(HE-CRPL)。該算法在CRPL算法的基礎上進行優化，通過與現有RPL能量均衡相關算法的有效結合，能夠使網絡中的節點能耗均衡并進一步延長網絡生存時間。HE-CRPL算法在選擇簇父節點時在保證通信質量的前提下同時考慮節點的剩余能量；在簇父節點的優先級判定和最優簇父集的選擇過程中引入節點期望壽命，從而有效地延長網絡壽命；另外，將優先級列表通過DAO消息攜帶，在數據傳輸過程中避免了因丟包而重傳攜帶優先級列表的數據包，從而降低了發送節點的能量開銷。通過實驗仿真結果表明，相對于CRPL算法，HE-CRPL算法能夠有效地實現節點能耗均衡，最大化地延長網絡生存時間和減少數據包重傳次數，其中網絡生存時間提高了18.7%，數據包重傳次數降低了15.9%。

References)

[1] DIAS J, RIBEIRO F, CAMPOS R, et al. Evaluation of an RPL/6LoWPAN/IEEE 802.15.4g solution for smart metering in an industrial environment[C]// Proceedings of the 2016 12th Annual Conference on Wireless On-demand Network Systems and Services. Piscataway, NJ: IEEE, 2016: 1-4.

[2] GARA F, SAAD L B, AYED R B, et al. RPL protocol adapted for healthcare and medical applications[C]// Proceedings of the 2015 International Wireless Communications and Mobile Computing Conference. Piscataway, NJ: IEEE 2015: 690-695.

[3] QUYNH T N, LE-MANH N, NGUYEN K N. Multipath RPL protocols for greenhouse environment monitoring system based on Internet of things[C]// Proceedings of the 2015 12th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology. Piscataway, NJ: IEEE, 2015: 1-6.

[4] HERBERG U, CLAUSEN T. Study of multipoint-to-point and broadcast traffic performance in the “IPv6 routing protocol for low power and lossy networks” [J]. Journal of Ambient Intelligence and Humanized Computing, 2011, 2(4): 293-305.

[5] KO J G, TERZIS A, DAWSON-HAGGERTY S, et al. Connecting low-power and lossy networks to the Internet[J]. Communications Magazine, 2011, 49(4): 96-101.

[6] KHELIFA S, MAAZA Z M. An energy multi-path AODV routing protocol in Ad Hoc mobile networks[C]// Proceedings of the 2010 5th International Symposium on I/V Communications and Mobile Network. Piscataway, NJ: IEEE, 2010: 1-4.

[7] BADAL D, KUSHWAH R S. A energy efficient approach to DSR based routing protocol for Ad Hoc network[J]. International Journal of Computer Applications, 2015, 118(4):14-17.

[8] WINTER T, THUBERT P, BRANDT A, et al. RPL: IPv6 routing protocol for low power and lossy networks: RFC 6550 [S]. Geneva: IETF, 2012:1-157.

[9] VASSEUR J, KIM M, PISTER K, et al. Routing metrics used for path calculation in low-power and lossy networks: RFC 6551 [S]. Geneva: IETF, 2012:1-30.

[10] THUBERT P. Objective function zero for the routing protocol for low-power and lossy networks: RFC 6552 [S]. Geneva: IETF, 2012: 1-14.

[11] GNAWALI O, LEVIS P. The minimum rank with hysteresis objective function: RFC 6719 [S]. Geneva: IETF, 2012:1-14.

[12] 張宗杰, 劉彤, 馬皛源, 等. 無線傳感器網絡RPL路由協議優化[J]. 中國科技論文在線精品論文，2014，7(8)：715-721.(ZHANG Z J, LIU T, MA J Y, et al. Wireless sensor network RPL routing protocol optimization[J]. Highlights of Sciencepaper Online, 2014, 7(8): 715-721.)

[13] 胡婷婷, 秦雅娟, 高德云. IPv6無線傳感網負載均衡路由協議研究[J].計算機技術與發展, 2015,25(7):27-30.(HU T T, QIN Y J, GAO D Y. Research on multi-sink load-balanced routing protocol for IPv6 wireless sensor networks[J]. Computer Technology and Development, 2015, 25(7): 27-30.)

[14] 宋海龍, 張書真. 基于期望壽命與均衡能量消耗的RPL路由協議[J]. 計算機工程,2016,42(1):77-82. (SONG H L, ZHANG S Z. RPL routing protocol based on expected lifetime and balance energy consumption[J]. Computer Engineering, 2016, 42(1): 77-82.)

[15] MICHEL M, DUQUENNOY S, QUOITIN B, et al. Load-balanced data collection through opportunistic routing[C]// Proceedings of the 2015 International Conference on Distributed Computing in Sensor Systems. Piscataway, NJ: IEEE, 2015: 62-70.

[16] ZHAO M, SHWE H Y, CHONG P H J. Cluster-parent based RPL for low-power and lossy networks in building environment[C]// Proceedings of the 2015 12th Annual Consumer Communications and Networking Conference. Piscataway, NJ: IEEE, 2015: 779-784.

[17] IOVA O, THEOLEYRE F, NOEL T. Improving the network lifetime with energy-balancing routing: application to RPL[C]// Proceedings of the 2014 7th Wireless and Mobile Networking Conference. Piscataway, NJ: IEEE, 2014: 1-8.

This work is partially supported by the National Natural Science Foundation of China (61379159), the Foundation and Frontier Research Project of Chongqing (cstc2015jcyjBX008).

YAO Yukun, born in 1964, M. S., professor. Her research interests include network management and application, network coding.

LIU Jiangbing, born in 1989, M. S. candidate. His research interests include routing of wireless networks.

LI Xiaoyong, born in 1992, M. S. candidate. His research interests include wireless network coding.

Optimized routing algorithm based on cooperative communication of cluster parent set for low power and lossy network

YAO Yukun, LIU Jiangbing*, LI Xiaoyong

(KeyLaboratoryofMobileCommunicationTechnology(ChongqingUniversityofPostsandTelecommunications),Chongqing400065,China)

To deal with the problems that the routing algorithm based on Collaborative communication of Cluster Parent (CRPL) for Low Power and Lossy Network (LLN) can’t balance the energy consumption of the node and maximize the extension of the lifetime for network efficiently due to take no account of the residual energy of the node, a high-efficient routing algorithm based on collaborative communications of cluster parent set HE-CRPL was proposed. The proposed algorithm chiefly carried out three optimization schemes. Firstly, the wireless link quality and the residual energy of node could be considered during the cluster parent selection. Secondly, the wireless link quality and the Expected LifeTime (ELT) of cluster parent node were combined while estimating the priority of the cluster parent node and selecting the optimal cluster parent set. Thirdly, the cluster parent nodes were notified the priority list by Destination Advertisement Object (DAO) message during the initialization of the network topology. The simulation results show that, compared with the CRPL algorithm, the performance of the HE-CRPL algorithm is improved obviously in prolonging the network lifetime, increasing the packet delivery success rate and reducing the number of packet retransmissions, and that the lifetime of network prolonging by more than 18.7% and the number of retransmissions decrease by more than 15.9%.

Low power and Lossy Network (LLN); cluster parent set; collaborative communication; priority list; residual energy; Expected LifeTime (ELT)

2016-10-21;

2016-12-13。

國家自然科學基金資助項目(61379159); 重慶市基礎與前沿研究計劃項目(cstc2015jcyjBX0085)。

姚玉坤(1964—)，女，重慶人，教授，主要研究方向：網絡管理與應用、網絡編碼； 劉江兵(1989—)，男，重慶人，碩士研究生，主要研究方向：無線組織網絡路由； 李小勇(1992—)，男，湖北荊州人，碩士研究生，主要研究方向：無線網絡編碼。

1001-9081(2017)05-1300-06

10.11772/j.issn.1001-9081.2017.05.1300

TP393

A