基于普通節點負載均衡的RPL路由協議*

仇英輝，陳　玲

（華北電力大學電氣與電子工程學院，北京102206）

基于普通節點負載均衡的RPL路由協議*

仇英輝*，陳玲

（華北電力大學電氣與電子工程學院，北京102206）

傳統的RPL路由協議并未涉及到節點負載均衡的問題，容易造成網絡局部負載過重導致部分節點死亡。闡述了RPL路由協議的拓撲構建、路由過程及一些現有的目標函數，定義了鄰居距離和剩余能量級別兩個參考指標，通過劃分能量級別和改變通信半徑兩重負載均衡方法，提出了一種基于普通節點負載均衡的RPL路由協議——OLB-RPL。通過實驗仿真驗證結果證明改進后的協議可以實現網絡中普通節點的負載均衡，并且在減少節點能量消耗的同時延長了整個網絡的生存時間。

低功耗有損網絡；RPL路由協議；剩余能量級別；鄰居距離；負載均衡

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.07.021

在低功耗有損網絡LLNs（Low-power and Lossy Networks）中［1］，路由器往往受到處理能力、存儲能力和能量或電池功率方面的限制。它們之間的連接具有高丟包率、低帶寬和不穩定的特點。而RPL路由協議LLNs（Routing Protocol for LLNs）是IETF提出的針對LLN網絡特點的路由協議［2-3］。

目前，國內外對RPL的研究熱點主要是在路由算法、拓撲控制和協議安全這幾個方面［4-6］。在負載均衡［6-9］方面文獻［6］提出了一種基于RPL的多Sink節點的負載均衡的方法LB-RPL，通過均衡網絡的負載延長了網絡的生存時間，但是文中只針對多Sink節點考慮負載平衡，卻沒有考慮普通傳感節點的過負荷情況，這樣以來容易使普通節點因提前耗盡能量而死亡，造成通信障礙。為進一步研究適用于LLNs的網絡拓撲構建方式和路由方法，并且避免不同傳感節點負載不均衡的情況，本文提出一種基于普通節點負載均衡的RPL路由協議的優化算法——OLB-RPL，綜合考慮能量指標和傳感器鄰居節點集范圍對網絡構建和路由過程進行優化。

1　RPL路由協議

RPL是一個距離矢量路由協議，通過目標函數和度量集合構建一個具有目的地的有向無環圖DODAG（Destination Oriented Directed Acyclic Graph），然后根據路由度量和約束條件選擇最優路徑完成路由過程。RPL路由協議中定義了三種ICMPv6控制消息用來交換圖的相關信息并構建網絡拓撲：DODAG信息對象DIO（DODAG information object），用于通告有關DODAG的參數；DODAG請求信息DIS（DODAG Information Solicitation），用于向鄰居節點請求DODAG信息；目的廣播對象DAO（Destination Advertisement Object），用于構建向上的路由［2，4］。

如圖1所示，是整個DODAG圖的構建。DODAG圖是基于樹的網絡拓撲結構，其構建一般從根節點開始，即邊界路由LBR（LLN Border Router）或sink節點。如圖1所示，LBR節點和普通RPL節點隨機分布在傳感區域內，首先LBR向自己發送功率半徑范圍內的鄰居節點廣播攜帶有關于圖的配置屬性的DIO信息，節點A通過DIO獲取發送節點的配置屬性及其Rank值，決定是否加入圖中。若加入圖中，LBR成為A的父節點，此時A節點根據DIO中的信息計算自己的Rank值，并修改DIO中的信息向周圍的節點廣播DIO數據包，處于A節點發送功率半徑內的節點B收到A發來的DIO后決定加入圖中，計算自己的Rank值，然后向周圍節點發送自己的DIO消息，并回送給A一個DAO消息。以此類推節點C也加入圖中。假設一個節點收到了幾個DIO消息，則選擇使自己Rank值最小的DIO幀的發送節點作為父節點。此時，未收到DIO的節點D也想加入圖中，它主動向自己的鄰居節點A發送DIS信息請求加入DODAG中，A收到DIS后向節點D發送DIO信息邀請D加入圖中，D加入圖中后回送DAO信息。重復上述過程，直到所有節點加入到DODAG圖中，LBR節點即是整個DODAG的根，如圖1所示。

圖1　DODAG的構建

值得注意的是，在非存儲模式下，葉子節點回復的DAO消息需要發送至根節點，在根節點處計算整個網絡的DODAG圖；而存儲模式下，葉子節點將DAO發送至父節點轉發至根節點的過程中，父節點要維護一個記錄到達各個葉子節點路由的下一跳的路由表。

2　目標函數

目標函數OF（Objective Function）定義了路由度量標準和路由限制條件，即定義了怎樣在一個RPL實例中選擇父節點和最優路由。OF具體內容包括：如何獲取更新度量信息；如何計算每個節點的Rank值；如何選出最佳父節點。

路由度量（metric）是計算路徑損失及最短路徑的重要標準，用于評估路徑代價，一般可以累加，OF需要結合路由度量來尋找父節點并計算最佳路徑。IETF發布的RFC6551文檔中，闡述了RPL路由協議中可以使用的幾種度量標準［10］。以下簡單介紹兩種以不同的度量標準為準則的目標函數。

2.1目標函數OF0

目標函數OF0是官方文件RFC6552文檔中明確規定的，它以跳數（HC）為最佳選路標準，是RPL協議中最簡單的目標函數［5-6，11］。

OF0（Object Function Zero）的目標是使節點加入一個連通性足夠好的DODAG中，而不要求路由對某一度量做出特殊的優化［12］。假設P為某節點N的父節點，那么OF0中Rank值計算如下：

OF0在運作的時候會根據自己的路由度量計算出一個Rank的階梯值，然后沿著階梯值計算Rank的增加值Rank_increase，選擇Rank_increase最小的節點作為自己的父節點。但OF0只考慮跳數，在選路的時候選擇了跳數最短的路徑，每一跳的距離卻可能變長，如此以來會降低鏈路的質量。

2.2目標函數MRHOF

目標函數 MRHOF（The Minimum Rank with Hysteresis Objective Function）是一種帶有滯回作用的目標函數。MRHOF的主要目標是當選擇路徑損耗最小的路徑時，避免因為度量的略微變化而引起拓撲的抖動［5-6］。

MRHOF中采用了三種路由度量：跳數（Hop-Count）、時延（Latency）、ETX。ETX表示節點成功發送一個數據包所期望的傳輸次數，ETX的計算方法有很多，ContikiRPL用EWMA函數來計算ETX［13］：

其中ETXnew指包成功被發送或接收前傳輸的總次數，一般a設為0.9。MRHOF的Rank值的計算是給ETX乘了一個因子，此處不再具體贅述。MRHOF的運作是在初次加入圖中，節點選擇Rank值最小的節點作為自己的父節點，當網絡中出現了新的備選父節點不會立馬更換，比較當前父節點與備選父節點所在路徑的開銷，當開銷的差值大于預先設定的門限值，才會改變父節點，選擇新出現的備選父節點。

3　基于普通節點負載均衡的RPL路由協議

RPL網絡一般選擇能量充足存儲能力較強的節點作為Sink節點，目標函數OF0選路時只考慮跳數（HC）的問題，上文所提到的LB-RPL只考慮了多Sink節點間的負載均衡，兩者均未對普通節點進行負載均衡，如此若普通節點負載較多，能耗較大，比如在數據采集網絡中，若該節點正在參與數據采集的過程，一旦能量耗盡死亡，則會出現監測盲點，甚至會導致網絡分裂，部分數據無法傳回Sink節點［14］。為此，本文提出了一種基于普通節點負載均衡的RPL路由協議——OLB-RPL，通過修改目標函數，不僅減小了普通節點的能量消耗，而且延長了整個網絡的生存時間。

3.1參考度量

本文以節點鄰居距離di和節點剩余能量級別REL為依據來計算路徑，以尋找最優傳感器網絡鄰居節點范圍為路由算法來實現RPL網絡中普通節點的負載均衡。

3.1.1節點鄰居距離di

本文定義的節點鄰居距離針對每個節點，指每個節點的鄰居節點集內的節點距該節點的歐式距離。

圖2　節點鄰居距離示意圖

如圖2所示為節點i的鄰居距離示意圖，整個網絡初始時刻每個節點的功率發送范圍半徑為R0，即為節點i的廣播域或通信半徑。由圖中看出周圍有節點1～6處于通信半徑中，那么這些節點的集合即為當前節點i的鄰居節點集，通過測試信號節點i記錄各鄰居節點到該節的距離即節點鄰居距離di：

其中k表示第k個鄰居節點。

3.1.2節點剩余能量級別REL

本文引入剩余能量級別REL，一方面避免了網絡更新過快帶來的抖動，另一方面通過設置每個能級RELi對應的負載數目閾值Fi實現節點的負載均衡，即剩余能量多的RPL節點負載多一些，而剩余能量少的RPL節點負載相對少一些。負載數閾值Fi的值視具體情況而定，會受到節點發送功率、節點密度、剩余能量及鄰居距離等因素的影響。設網絡節點最初能量為E0，設每個節點有m個能量級別，那么每個等級的能量為Eaverage=E0/m，設每個節點i的當前的剩余能量為Ei_cur，則可以得到某時刻網絡中某個節點i的剩余能量級別為［15］：

［Ei_cur/Eaverage］表示大于［Ei_cur/Eaverage］的最小整數。由式（4）得到每個節點的剩余能量級別的取值范圍是［1，m］內的正整數。能量級別m的選取對整個優化協議的性能有重要影響，可依據整個網絡平均節點密度來設置，根據不同網絡對通信質量的要求m可以靈活設置。若m取值較小則不能體現出每個節點剩余能量的差異，根據剩余能量級設定的負載數目不會有明顯改變，負載均衡的效果會很不明顯［15-17］。

3.2基于普通節點負載均衡的目標函數

3.2.1均衡策略

圖3所示為基于普通節點負載均衡的RPL路由協議流程圖，算法如下：

S1進行網絡的初始化，初始半徑為R0，通過測試信號來記錄鄰居節點及各節點鄰居距離di；

S2初始化以后，每個普通節點計算自己的剩余能量級別RELi，并統計自己所攜帶的負載數目fi；

S3判斷當前節點所攜帶的負載數目fi是否大于當前節點剩余能量級別RELi所對應的負載數門限Fi；

S4一旦fi大于門限值Fi則對當前節點的通信半徑Ri調整，減小相應的調整值；

S5若fi小于門限值Fi則當前節點保持通信半徑Ri不變，不必進行接下去的負載均衡機制。

上述算法所述通信半徑調整值Δ為當前鄰居節點集內所有節點的平均節點鄰居距離。當通信半徑變小以后，鄰居節點集中鄰居節點的個數變少，父節點斷開與多出來的負載節點的連接，這些負載節點可以尋找新的剩余能量級別較大的節點作為父節點。若當前節點在當前剩余能量級內所帶負載個數小于相應的負載數目閾值，則節點停留在原來的深度不變，并且不必進行負載均衡機制，等待定時器到下一個時刻更新后再進行條件判斷是否進行負載均衡。

圖3　基于普通節點負載均衡的RPL路由協議流程圖

3.2.2通信半徑調整策略

圖4所示為某時刻對某節點i當前通信半徑Ri調整示意圖。為方便描述，圖4將樹形拓撲暫時畫為星形拓撲，且節點i通信半徑范圍內的節點都是i的葉子節點。某一時刻節點i的通信半徑為Ri，調整后的通信半徑為Ri+1。起初節點i通信半徑范圍覆蓋的子節點有節點1～n，當檢測到節點i的剩余能量級別小于門限值并且i所帶負載數目大于閾值時，計算通信半徑的調節值Δ：

則新的通信半徑為

從新的通信半徑覆蓋范圍看出，只有節點2、4、n位于通信半徑范圍內，故其他節點不能再以當前節點i作為父節點，而需要重新尋找距離較近并且節點剩余能量級別高的節點為父節點。依次類推每個節點都執行這個策略即可實現負載均衡。

圖4　節點通信半徑調整示意圖

4　仿真驗證

本文使用Matlab仿真平臺進行驗證，將本文的OLB-RPL路由協議與RPL路由協議進行了對比分析。為了驗證本文算法的有效性，選取網絡死亡節點數、網絡平均能量消耗以及網絡生存時間為衡量指標進行對比分析。網絡死亡節點數隨著網絡建立后時間延長而增加，增加的快慢程度可反映網絡均衡的性能；平均總能量消耗指平均每輪所有節點消耗的能量的總和；網絡生存時間指網絡中出現第一個節點能量耗盡所用的時間，用輪數表示，為擬合實際通信系統，當剩余能量小于5%時即認為節點失效死亡。

在100×100的區域內隨機設置200個傳感節點，按區域分為兩個DODAG，并手動設置每個DODAG的Sink節點，分別是每個區域內橫縱坐標最小的節點。由于無線傳感器網絡為自組網絡，網絡初始化時每個節點的初始能量均不同，而一般已選的Sink節點是能量比較充足的節點，考慮到以上情況，將Sink節點的初始能量設為1.00，為了可以突出剩余能量級別的差異，將其余普通節點的初始能量設為0.50～1.00之間的隨機值?？筛鶕?設置其他仿真參量。

表1　仿真參量設置

本文的仿真參量的設置可以根據具體情況及網絡大小來靈活配置。仿真中RPL和OLB-RPL的路由更新周期都是96，但由于OLB-RPL是實時更新的，而每一輪能耗過小一般能級不會改變，所以本文仿真中設置每50輪執行一次負載均衡機制進行更新。發送信息能量消耗采用無線通信距離與能量消耗的模型E=δ·d3，δ取值為δ=0.000 1（1/253）。能量級別m的選擇對協議的性能有影響，所以m的取值至關重要，本文根據整個傳感區域節點的平均密度來選取m的值，本文m取值為10，則RPL共有10個級別。

網絡生存時間指網絡中出現第一個節點能量耗盡的時間，而網絡死亡節點數目也可以體現出算法對整個網絡每個節點的負載均衡性能。本文算法OLB-RPL與RPL的網絡死亡節點對比如圖5所示。

圖5　網絡死亡節點對比圖

圖5中數據采集為等間隔采樣，因此采樣輪數反映了網絡生存時間的長短，當出現第一個死亡節點時，輪數越大，網絡生存時間越長圖5記錄了每一輪對應的死亡節點數，由圖知，RPL算法中，第一次出現死亡節點是在第74輪，而在本文的OLB-RPL算法中，第一次出現死亡節點是在第204輪，因此，說明本算法的改進較大程度地提高了網絡的生存時間；此后的數據采集過程中，同樣的數據采集輪數下，采用OLB-RPL算法的網絡死亡節點數也小于采用RPL算法的網絡產生的死亡節點數，而且隨著采集輪數的增加，兩種算法產生的死亡節點數的差值進一步增加，當采集輪數為6 000輪時，差值擴大到80個死亡節點數，說明RPL網絡死亡節點數目的增長速率大于OLB-RPL。由此證明了OLB-RPL確實可以均衡網絡的負載，延長整個網絡的壽命。

圖6所示為網絡平均能量消耗對比圖，網絡初始化時，由于兩種算法采用相同的路由建立過程，因此，初始能耗一致，但此后，本文OLB-RPL算法的仿真中網絡平均每50輪執行一次動態路由選擇，更新網絡路由拓撲，按算法原理，網絡中節點負載數大于其能級對應的數量閾值時，節點將減小自己的負載數目到閾值以下，網絡得到均衡優化，所以圖中出現開始一段驟降的情形；隨著時間的推移，能耗才逐漸緩慢增加；最終，本算法建立起的網絡在死亡節點、重啟節點以及整個網絡之間建立起一種動態平衡，能耗也趨于穩定。較之RPL算法，本文OLB-RPL算法的能耗也有明顯下降，在實現負載均衡的同時也降低了能耗。

圖6　平均能量消耗對比圖

圖7為網絡規模與生存時間關系圖，反映了網絡規模即網絡節點總數與生存時間的關系。為保證較為準確的反映兩者關系，避免偶然性的發生，實驗中，在某一網絡規模下，仿真執行50次就取其對應的生存時間的均值作為參考值，由于采樣間隔一致，網絡生存時間用采樣輪數表示。從圖7可以看出，兩種算法的對應曲線都大致呈遞減趨勢，即兩者都是隨著網絡節點數的增加，網絡生存時間逐漸減小，這是由于節點數增加，導致網絡密度增加，網絡中平均每個節點的負載數目增加而引起的節點能耗增加引起的。但相較于RPL路由算法，本文算法OLB-RPL明顯改善了網絡負載不均衡性，提高了網絡生存時間。

圖7　網絡規模與生存時間的關系

5　結論

本文結合了低功耗有損網絡的特點，提出了一種基于普通節點負載均衡的RPL路由協議OLBRPL，改善了網絡的負載均衡機制，降低網絡能耗。本文提出的算法通過節點能量分級和改變通信半徑兩個負載均衡辦法改進了RPL的目標函數；并通過實驗仿真對算法的有效性進行了驗證分析，實驗數據表明采用本文的算法網絡負載得到有效均衡，網絡的損耗明顯降低，整個網絡的生命周期得以延長，而且由此帶來的跳數增加和網絡抖動可以接受。本改進算法進一步完善了RPL路由協議并在實時監控數據采集等領域的應用具有很重大意義。

［1］ Dohler M，Watteyne T，Winter T，et al.RFC 5548：Routing Requirments for Urban Low-Power and Lossy Networks［S］.Internet Engineering Task Force，2009.

［2］ Winter T，Thubert P，Brandt A，et al.RFC 6550：RPL IPv6 Routing Protocol for Low-Power and Lossy Networks［S］.Internet Engineering Task Force，2012.

［3］ 董立卿.面向LLN的發布訂閱系統仿真研究［D］.北京：北京理工大學，2014.

［4］ 朱琳.無線傳感器網絡RPL路由協議研究與改進［D］.北京：北京交通大學，2013.

［5］ 吳晗.低功耗有損網絡路由協議RPL的實現與改善［D］.北京：北京郵電大學，2015.

［6］ 胡婷婷，秦雅娟，高德云.IPv6無線傳感網負載均衡路由協議研究［J］.計算機技術與發展，2015（7）：27-30.

［7］ 鄭相全，郭偉.自組網中的負載均衡路由協議［J］.計算機科學，2004（11）：40-45.

［8］ Chekka R T；Ting Miao，Ki-Hyung Kim.Implementation of Adaptive Binary Exponential Backoff（ABEB）Algorithm with Dynamical Sizing Buffer for Load-Balanced RPL［C］//Ubiquitous and Future Networks（ICUFN），2014 Sixth International Conf on，2014（l）：562-564，8-11.

［9］ Liu Xinxin，Guo Jianlin，Bhatti G，et al.Load Balanced Routing for Low Power and Lossy Networks［C］//Wireless Communications and Networking Conference（WCNC），2013 IEEE，2013（l）：2238-2243，7-10.

［10］Vasseur J P，Kim M，Pister K，et al.RFC 6551：Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks［S］. Internet Engineering Task Force，2012.

［11］Thubert P.RFC 6552：Objective Fuction Zero for the Routing Pertocal for Low-Power and Lossy Networks［S］.Internet Engineering Task Force，2012.

［12］高筱菲.基于RPL的無線傳感器網絡分簇路由研究與實現［D］.北京：北京交通大學，2014.

［13］Gnawali O，Levis P.The ETX Objective Function for RPL［J］. 2010.

［14］尹安，汪秉文，胡曉婭，等.無線傳感器網絡負載均衡路由協議［J］.華中科技大學學報（自然科學版），2010（1）：88-91.

［15］徐衛，劉端陽，暴占兵.基于剩余能量的可分負載WSN能耗均衡研究［J］.計算機工程，2015（6）：66-70.

［16］馬建樂，楊軍.基于位置和剩余能量的局部集中式LEACH算法研究［J］.傳感技術學報，2013（8）：1147-1151.

［17］張文祥，馬銀花.基于梯度和剩余能量的WSN路由算法研究［J］.傳感技術學報，2009（8）：1182-1185.

仇英輝（1975-），男，河北定州人，副教授，博士，主要研究方向為智能電網和電力系統通信；

陳玲（1992-），女，寧夏銀川人，碩士研究生，主要研究方向為智能電網與電力系統通信，382685891@qq.com。

The RPL Routing Protocal Based on Load Balance of Ordinary Node*

QIU Yinghui*，CHEN Ling
（College of Electrical and Electronic Engineering，North China Electric Power University，Beijing 102206，China）

Traditional RPL routing protocol does not involve the load balance strategies，which is easy to cause local networks over load even leads to the deaths of some nodes.This paper expounds the topological construction and the routing process of RPL routing protocol and some existing Objective Function，then it defines two reference indexes which are the Node Neighbor Distance and Remaining Energy Level.The paper proposes a OLB-RPL routing protocol based on load balance of ordinary node through dividing the energy level and changing the communication radius.At last，we proved that the improved routing protocol achieve the load balancing of the ordinary node through simulation verification，andthenewprotocolreducesthenodeenergyconsumption，andprolongthesurvivalofthewholenetwork.

low-power and lossy networks；RPL routing protocol；remaining energy level；neighbor distance；load balance

TP393.04

A

1004-1699（2016）07-1077-06

項目來源：中央高?；究蒲袠I務費專項資金項目（12MS18）

2016-01-05修改日期：2016-02-18