基于三角模算子的RPL協議路由優化算法*

仇英輝，何 霖

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

隨著智能建筑、工業環境監測以及智能電網環境監測控制等技術的不斷推進，對于通信網絡在能量、存儲空間以及處理能力等限制條件下的修復力、互動效率和可持續性要求日益提高。鑒于這一需求，IETF提出了低功耗有損網絡路由協議［1］RPL（Routing Protocol for LLN），并針對城市網絡（包括智能電網）、建筑自動化、工業自動化以及家庭自動化四個領域制定了相應的路由需求［2-5］。

RPL協議是一種基于IPv6路由框架的距離矢量路由協議，擁有獨特的路由創建規則。然而目前國內針對RPL協議的研究還相對較少，大多是應用于無線傳感器網絡的組網功能。文獻［6］基于存儲式的RPL協議，將RPL中的路由表簡化成目的節點集合，并利用布隆過濾器管理這些集合，從而減少了存儲開銷；文獻［7］為解決RPL協議只以跳數為路徑選擇度量而造成的Sink節點壓力多大使其電量過早耗盡，采用了加權融合的方式（W-RPL）綜合考慮跳數和節點能量兩方面因素進行路徑選擇，以延長生命周期，然而文中并未對因素的隸屬度進行定義，且加權融合的權重分配也并未明確；文獻［8］采用簇首競爭機制，借助RPL路由協議中相關參數，通過分簇減少節點到網關的跳數，采用最優父節點優化驅動輪換機制，平衡各節點能耗，達到負載均衡的目的。

為進一步研究適用于LLNs的網絡拓撲構建方式和路由方法，本文提出一種基于三角模算子的RPL協議路由優化算法，綜合考慮能量指標和邏輯距離對網絡構建和路由過程進行優化。

1 RPL協議

RPL協議的拓撲構建主要通過一系列的新型ICMPv6消息來完成，節點之間通過廣播方式交換距離矢量等信息，并基于目標函數構建一個有向無環圖 DODAG（Destination-Oriented Directed Acyclic Graphs），從而有效地防止了路由環路問題，最后節點通過目標函數進行路由度量以選擇最優路徑［1］；且目標函數的設置可以根據網絡需求的不同進行靈活變動，從而構建相應的網絡拓撲［9］。

1.1 DODAG構建過程

RPL中定義了一系列新的ICMPv6消息來控制拓撲結構的形成和交換圖的相關信息，其中包括DODAG信息對象DIO（DODAG InformationObject）；DODAG請求信息DIS（DODAG Information Solicitation）和目的廣播對象DAO（DestinationAdvertisementObject）。

DODAG圖是基于樹的網絡拓撲結構，其構建一般是從匯集節點開始，也稱為邊界路由LBR（LLNBorder Router）；首先LBR向鄰居節點廣播攜帶有關于圖的配置屬性的DIO信息，接受到信息的節點通過DIO信息可以了解周圍節點的配置屬性及其Rank值，并根據約定目標函數決定是否加入該圖，若加入，則LBR節點成為其父節點，節點計算更新其Rank值，同時也向鄰居節點廣播DIO信息，請求更多節點加入該DODAG圖［10］，直至所有節點都加入圖。另外，節點也可主動向鄰居節點發送DIS信息請求圖信息，請求加入DODAG圖。如此重復以上兩個過程，直到所有節點加入到DODAG圖，LBR節點即是DODAG根。

圖1 DODAG構成流程圖

圖1為一典型DODAG的構建簡化流程圖，LBR節點廣播包含其自身配置信息的DIO信息，相鄰的RA節點都在接收到DIO信息后，通過目標函數判定加入到圖中，更新Rank值并向鄰居節點（包括其父節點LBR）廣播其DIO信息，除了含有目標函數、Rank值等基本信息外，還包含有其父節點信息。RB、RC、RD依次以洪泛形式重復上述過程。

1.2 RPL的路由過程

1.2.1 MP2P路由模型

MP2P（Multipoint-To-Point）路由模型是指多點到一點的路由傳輸路徑，在DODAG圖中是“向上”的路徑。其路由過程基于DODAG的父子節點關系建立路徑，各節點均保留其父節點的地址信息，當需要信息傳輸時，每個葉子節點都可通過向自己的父節點發送信息，逐級向上傳送消息直至根節點，從而完成MP2P的信息傳送。

1.2.2 P2MP路由模型

P2MP（Point-To-Multipoint）路由模型是指點到多點的路由傳輸，即指當有來自LLN網外部的信息，需要從父級節點傳送到某一葉子節點的情況。P2MP的實現需要依賴向下路由的構建，其構建過程一般基于上行路徑拓撲構建，節點通過發送DAO消息來聲明目的節點地址用以完成向下路由的建立。在RPL協議中有兩種路由模式：存儲模式和非存儲模式，二者區別在于存儲模式下，每個父節點都存儲有其子DODAG圖的路由表，各子節點都會向其父節點單播發送DAO信息告知其目的地址；而非存儲模式下，由于節點的存儲空間有限，所以DODAG圖中所有中間節點不需要存儲路由表，所有的路由表信息都存儲在DODAG根節點處，所以發送信息的子節點首先需按“向上”路徑將DAO消息傳送到DODAG根節點處進行路由構建［11］。

1.2.3 P2P路由模型

P2P（Point-To-Point）路由模型是指點到點的傳輸，RPL節點產生數據包沿向上的路徑傳輸，并向該路徑上的路由通知目的節點地址，直至找到與目的節點相同的祖先節點，再沿向下的路徑傳輸。當在存儲模式下，源節點只需將數據包傳送到與目的節點共同的祖先節點處，然后根據祖先節點處存儲的路由表信息選擇下一跳到達目的節點即可；而非存儲模式下，只有DODAG根節點為共同的祖先節點，即數據匯集到根節點處進行向下轉發。

1.3 環路避免和環路檢測

傳統網絡中，由于節點信息不同步或是拓撲結構改變，可能會出現暫時的環路現象，為了避免由于環路引起的丟包率突增、信道擁塞問題，所以RPL協議制定了節點“Rank Value”（下文簡稱R值），即上文所提的Rank值用來避免環路出現。RPL的計算規定葉子節點的父節點的R值必須小于其子節點的R值，因此有以下公式計算節點的R值：

式中：RS表示所求子節點的R值；RF表示所求子節點對應父節點的R值；RD表示所求子節點與其對應父節點的R值差。根據以上所得的R值，RPL有兩個規則來避免環路：①最大深度規則，規定圖中任何節點不可以選比自己R值還大的作為父節點；②拒絕貪婪規則，規定不允許圖中任何節點移動到圖中更深位置以增加自己潛在父節點數。

具體來說，檢測環路的方法是在RPL路由信息的頭部設置相關的bit位作為標記以檢測路徑的有效性。比如在上行鏈路中，將bit為設為“upward”，節點收到設置為“upward”的數據包查詢路由信息選擇合適的父節點向上傳輸信息。如果發現數據包是向下傳輸，則出現了臨時的環路，數據包被丟棄并觸發本地修復。

1.4 本地修復和全局修復

當鏈路或節點失效以后RPL協議提供修復功能，包括本地修復和全局修復功能。當環路檢測到了某條鏈路失效，或某節點向上沒有父節點路由時，本地修復會立即被觸發，尋找新的節點替代原路徑或原父節點以保證路徑暢通。而本地修復一旦被觸發，整個網絡最優模式下的拓撲結構以及相關的路由信息就會改變，從而根節點會觸發全局修復機制重建DODAG圖。

1.5 Trickle定時管理算法

由于LLN網絡中資源有限，不能使用在TCP等協議中廣泛使用的“keepalive”，即周期性發送數據來保證路由的更新。因此，在RPL協議中采用了Trickle算法通過實現一致性來控制DIO消息的發送量。一致性是指檢測網絡中是否出現環路或者有新的節點加入或退出，如若沒有則視為網絡穩定，反之則視為網絡不一致。當網絡一致時，Trickle定時器控制節點減少DIO的發送量；當網絡不穩定時，增加DIO的發送盡快解決路由信息不一致問題［12］。

2 基于三角模融合算法的RPL目標函數

2.1 目標量選取

RPL的拓撲構建和路徑選擇主要是根據節點的Rank值，即到根節點的距離來確定的，然而網絡的QoS需要考慮多方面的影響［13］，單純地選擇更近的節點可能造成網絡結構不均衡，局部超負荷等不良影響；為解決這一問題，本文中引入三角模算法將多目標量的影響進行融合，以實現各目標量影響間的優勢均衡、矛盾中和；以影響LLNs最為直接的邏輯距離和節點剩余能量為目標，對其進行定義和隸屬度擬合并作為三角模算法的因子。

2.1.1 邏輯距離

邏輯距離是指信息發送節點發送數據包到達目的節點邏輯上到達的距離，可表達為每一跳的路徑長度和，如式（2）。邏輯距離與節點數據上傳所需能量成正相關性，且優先選擇邏輯距離較小的節點可一定程度上保證多跳網絡各分支的均衡性。

式中：D為邏輯距離，Hopi為第i跳路徑節點。

2.1.2 節點剩余能量

根據RPL協議的原理，在DODAG圖構建初期，每一個節點能量的損耗即為發送或接收DIO信息的能量損耗，因此收發DIO消息的次數間接反映了鄰居節點密集度。此外，從節能和生命周期的角度，選擇剩余能量較多的節點，可以保證網絡負載的均衡，有效延長整個網絡的生命周期，避免因局部網絡崩潰導致網絡重建而消耗多余能量［14］。

2.2 基于三角模算子的目標量融合

2.2.1 目標量隸屬度

根據三角模算子的性質可知參與融合的兩個參數的取值范圍是（0，1）［15］。為實現信息融合，根據RPL路由的邏輯距離值和剩余節點能量的特點，首先對兩個參數分別進行歸一化，其表達式分別如下：

式（4）表示剩余節點能量值的歸一化過程，式中ηE表示剩余節點能量歸一化以后的值，Er表示當前計算的父節點剩余能量值，Eo表示計算的父節點初始能量值。

根據邏輯距離值的特點，選用高斯隸屬度函數計算其可靠性隸屬度，其表達式如下：

式中c、σ為高斯函數期望和標準差，分別決定函數的位置和形狀，本文中取c=0，σ=1。邏輯距離值和選取可能性結果成反比，即邏輯距離值越大被選上的可能性越小，所以為偏小型函數，即c=0；此外歸一化以后邏輯距離值的取值范圍為（0，1），所以σ=1，因此公式（5）變換為：

根據節點剩余能量值得特點，選用反正切函數作為計算其可靠性隸屬度函數，其表達式如下：

其中λ，α的取值可根據需求靈活配置，本文中取λ=20，α=0.5，所得隸屬度函數圖像如圖2所示。當節點剩余能量小于0.1（10%）時，則認為其能量水平不足以作為父節點，給定其隸屬度為0.01；當節點剩余能量大于0.1（10%）小于0.4（40%）時，可以作為父節點，但相對并不適合，因而其隸屬度增加相對緩慢；當節點剩余能量大于0.4（40%）時，則認為節點適合作為父節點，其隸屬度隨剩余能量的增大迅速增加。

2.2.2 三角模算子計算

三角模算法源于模糊數學，其算子表達式為：

其中a,b∈(0,1)，算子滿足以下性質：①同類信息的加強 性 ，即F(a,b)≥max{a,b}，a≥0.5 ，b≥0.5 ，或F(a,b)≤min{a,b}，a≤0.5，b≤0.5；②矛盾信息的調和性，即min{a,b}＜F(a,b)＜ max{a,b}，(a-0.5)和(b-0.5)反號。

圖2 節點剩余能量隸屬度函數

即引入三角模算子后，可以實現在節點選取過程中既可以增強優勢節點被選概率，弱化虛弱節點參與路徑的概率；同時也可以調和備選節點中邏輯距離與節點剩余能量情況可能出現的矛盾性，平衡節點選取標準，如：對于邏輯距離和能量水平都處于良好情況時（隸屬度均大于0.5），該節點被選中概率則會增大，反之亦然；而若邏輯距離和能量水平出現矛盾（其中之一隸屬度高于0.5，另一隸屬度低于0.5）則節點選中概率由兩者的中和值來決定，從而調和參考因素矛盾性。綜上，基于三角模算子的RPL路由優化算法，能夠在保證優先距離優勢節點的同時，兼顧節點能量水平，從而平衡網絡負載，提升網絡整體生命周期，避免局部節點提前死亡造成的網絡故障，即網絡可靠性和有效性得以增強。

3 實驗仿真

本文參考Contiki系統平臺［16］，基于Matlab仿真工具進行了本文算法與RPL協議以及加權融合RPL協議（W-RPL）的對比分析。在100×100的區域內隨機設置100個采集節點，將其按照坐標劃分為2個DODAG，分別將其中處于左下方的節點設置為Sink節點；考慮實際節點的能量情況可能具有差異性，節點初始能量設置為0.75～1.00之間的隨機值。本文具體的仿真參量設置如表1，各取值可根據環境不同靈活配置。

表1 仿真參量設置

此外，為進一步擬合實際系統應用的通信需求，本文在上述配置基礎上增加如下假設：①按照實際的采集需求，設定路由更新周期為每100點數據進行一次路由信息更新；②保證采集數據不缺失，當有節點死亡（能量水平低于5%）時，需要進行更換或充能；③除周期性的Sink節點采集信息外，存在隨機的節點間通信業務。

本文目標量的選取主要以能量有效性和負載均衡性為依據，因此，為驗證算法有效性，采用網絡死亡節點數和網絡平均能量消耗作為統計量進行對比分析。

網絡死亡節點數主要體現了網絡的通信負載均衡性，對于通信量集中的節點便容易提前死亡。本文算法與RPL協議的網絡死亡節點數對比如圖3所示，可見本文算法中首個節點死亡時間的出現比未改進RPL協議延遲416輪，比W-RPL協議延遲257輪；而同一輪內的節點死亡數也明顯減少，相比RPL平均減少57.8%的死亡節點，比W-RPL平均減少40.7%；有效均衡了網絡負載，提升了能量利用效率。

圖3 網絡死亡節點對比圖

從橫向的角度觀察可得出，當網絡的節點死亡率達到同一水平時，本文算法所進行的數據采集輪數遠高于RPL協議。圖4為不同節點死亡比例下的生命周期輪數，由圖可見，在相同死亡率下，本文算法有效提升了網絡的生命周期，當死亡率分別達到15%、30%及45%時，本文算法相對RPL協議可分別提高89.6%，46.7%，24.5%的數據采集輪數，相對WRPL也有所提升，然而當網絡中節點能量都相對較少時，能量參數的權重影響則更為明顯，因此網絡節點死亡數較多時，W-RPL與本文算法差距較小。綜上所述，可見本算法有效提升了網絡的生命周期，延長了節點平均壽命，保證了系統的經濟性和環保性。

圖4 網絡生命周期隨節點死亡數趨勢

本文算法的目標量選取，一方面考慮了節點能量的均衡，另一方面也考慮了節點的邏輯距離，即其通信能量開銷，因此對網絡的平均能量消耗進行統計分析，其結果如圖5所示。前期節點能量還處于相對充裕的階段，本文算法與RPL的能量消耗相差不大；但由于節點初始設置的能量有一定差別，因此W-RPL與本文O-RPL算法均要考慮一部分能量因素，而原始RPL協議則只考慮距離影響，因此相對而言能量消耗較小；而由于本實驗中每96點更新路由的設定，因而在平均能量消耗曲線上體現出較強的波動性；當節點能量水平不均勻時，由于本文算法中節點會優先選擇能量充裕且距離Sink節點邏輯距離較小的節點，其能量消耗相比于RPL逐漸體現出性能優勢；而且三角模算子的引入能夠有效擴大兩個因素間的同向效果，因而相比于WRPL，本文算法整體上的能量消耗要較低，實現了在均衡網絡負載的同時有效減少網絡的能量損耗。

圖5 平均能量消耗對比圖

4 總結

本文根據當前智能監測控制的通信信息傳輸服務需求，結合低功耗有損網絡協議的特點，提出了一種基于三角模算子的RPL協議路由優化算法，在節點接收DIO信息后的父節點選定過程中，通過基于三角模算子的節點剩余能量和邏輯距離指標融合進行了目標函數改進；并通過實驗仿真對算法的優化效果進行驗證分析，結果表明算法有效均衡了網絡負載，延長了網絡生命周期，降低了能量損耗，對于RPL協議的進一步發展和智能監測控制的應用具有重要意義。

［1］WinterT.etal.RFC6550：RPLIPv6RoutingProtocolforLow-Power andLossyNetworks［S］.InternetEngineeringTaskForce，2012.

［2］DohlerM.etal.RFC5548：RoutingRequirementsforUrbanLow-Pow?erandLossyNetworks［S］.InternetEngineeringTaskForce，2009.

［3］Pister K.et al.RFC 5673：Industrial Routing Requirements in Low-Power and Lossy Networks［S］.Internet Engineering Task Force，2009.

［4］Brandt A.et al.RFC5826：Home Automation Routing Require?ments in Low-Power and Lossy Networks［S］.Internet Engineer?ing Task Force，2010.

［5］Martocci J.et al.RFC 5867：Building Automation Routing Re?quirements in Low-Power and Lossy Networks［S］.Internet Engi?neering Task Force，2010.

［6］楊紅，朱紅松，，等.B-RPL：低存儲開銷的RPL路由協議［J］.計算機科學，2015，42（1）：96-100.

［7］胡芹艷，尹長川.無線傳感網絡中的RPL路由協議研究［J］.物聯網技術，2014，1：57-59.

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

［9］朱琳，高德云，，等.無線傳感器網絡的RPL路由協議研究［J］.計算機與技術發展，2008，22（8）：1-4.

［10］Clausen T，Herberg U.et al.A Critical Evaluation of the IPv6 Routing Protocol for Low Power and Lossy Networks（RPL）［J］.Proc IEEE WiMob，2011，11：365-72.

［11］Ancillotti E.et al.The Role of the RPL Routing Protocol for Smart Grid Communications［J］.IEEE Communications Magazine，2013，11：75-83.

［12］Levis P.et al.RFC 6206：The Trickle Algorithm［S］.Internet En?gineering Task Force，2011：3.

［13］于淼，白光偉等.多力驅動的無線傳感網絡QoS路由協議［J］.傳感技術學報，2013，26（11）：1564-1572.

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

［15］劉普寅.吳孟達.模糊理論及其應用［M］.長沙：國防大學科技出版社，1998.

［16］Dunkels A.et al.Contiki-a Lightweight and Flexible Operating System for Tiny Networked Sensors［J］.Proc IEEE LCN，2004，4：455-462.