WSNs中RPL路由的研究與下行算法的改進*

孫懋珩，倪升武

(同濟大學 電子與信息工程學院，上海 201804)

WSNs中RPL路由的研究與下行算法的改進*

孫懋珩，倪升武

(同濟大學 電子與信息工程學院，上海 201804)

RPL是IETF ROLL工作組針對低功耗有損網絡所提出的IPv6路由協議，而無線傳感網絡屬于低功耗有損網絡之一。通過詳細分析RPL協議中上下行路由的構建過程，發現下行路由構建過程中DAO消息發送數量較多，從而導致能量損耗較大的問題。針對此問題提出了新的算法，并使用Contiki系統的COOJA仿真器對網絡進行仿真。與現有的算法進行比較驗證，改進后的算法使DAO消息數量減少到原來的30%，從而大大降低了能量的消耗。

低功耗有損網絡；無線傳感網；RPL；COOJA

0 引 言

低功耗有損網絡（Low Power and Lossy Networks，LLNs）是目前最重要也最具挑戰性的研究領域之一。它包括無線個域網（Wireless Personal Area Networks，WPANs）、低功耗電力線通信網（Power Line Communication Networks，PLCs）和無線傳感網（Wireless Sensor Networks，WSNs）。LLN是由功率、存儲空間以及處理能力等資源受限的嵌入式設備組成，所以具有低數據率、有限能量以及可能出現的鏈路損壞等特點。

由于LLN的上述特點，路由的設計成為了LLN中最重要的問題之一。IETF ROLL（Routing Over Low Power and Lossy Networks）[1]工作組評估目前已經存在的路由協議（如OSPF、OLSR、AODV等），發現這些路由協議并不適合LLN。因此，該工作組研究制定了RPL（Routing Protocol for Low Power and Lossy Networks）協議，并于2012年3月發布了其協議標準RFC6550[2]。

本文將對RPL協議相關概念做簡要描述，討論其上下行路由的建立過程，并對現有下行路由過程中DAO消息發送數量過多的問題提出改進方案，最后使用Contiki系統中的COOJA仿真工具對新提出的算法進行仿真與分析，以驗證其合理性。

1 RPL路由協議

1.1 網絡拓撲的基本要素

RPL是LLN中基于IPv6的距離矢量路由協議。目標導向的有向無環圖（Destination Oritented Directed Acyclic Graph，DODAG）是RPL中的一個基本元素。它是由根節點根據目標函數（Objective Function，OF）[3]以及一些度量和約束條件[4]構建的。每個DODAG中的節點（根節點除外）會選擇一個父節點作為沿著DODAG向上的默認路由，OF的作用是對特定的度量（如跳數、時延、能量等）和約束條件來尋找最優的路徑。在RPL中，指定以下四個參數來確定和維護一個網絡拓撲圖[5]：

（1）RPL實 例 號（RPLInstanceID）： 由DODAG根節點產生，用來指示RPL實例的標識號。

（2）DODAG ID號（DODAGID）：由DODAG根節點產生，是一個IPv6地址，用來作為當前DODAG的標識符，并唯一標識當前的DODAG。

（3）DODAG版本號（DODAGVersionNumber）：用來指示當前的DODAG版本。當網絡出現更新時，該值會不斷增加，用以動態更新當前網絡的版本。

（4）Rank值：用來指示節點在網絡中的位置。離根節點越遠，該值越大。

內部控制管理體制的不完善，導致高校在招標過程中，缺少必要的監督制度與嚴格的操作過程以及容易受行政干擾，導致采購的物質質量、價格和售后服務都很難得到保證，極易滋生腐敗。另外，高校在物資采購和驗收時，存在一人同時負責這兩項工作的情況，嚴重違反分工控制準則。在設備采購后，高校中出現不把新采購設備計入固定資產項目的情況，導致國有資產流失嚴重。

一個RPL實例包含一個或多個DODAG，每個DODAG有自身的DODAG ID號，即RPL實例號和DODAG ID號唯一確定了一個DODAG。在一個DODAG中，當網絡出現故障或者有新的節點加入DODAG中時，當前的DODAG需要更新，版本號也隨之增加。另外，在一個DODAG中，不同的節點根據自身與根節點的距離具有不同Rank值，節點只能選取比自身Rank值小的節點作為自己的父節點，如圖1所示。

圖1 RPL實例

RPL路由協議支持三種不同的通信模式[6]：點到點通信（Point-to-Point，P2P）、多點到點通信（Multipoint-to-Point，MP2P）和點到多點通信（Point-to-Mutipoint，P2MP）。同時，RPL路由協議可以工作在兩種不同的模式下：存儲模式和非存儲模式。存儲模式中，節點可以存儲路由表和下一跳節點信息；非存儲模式中，只有根節點能夠存儲整個路由表信息。

1.2 RPL上行路由的建立

MP2P即上行路由。該路由的建立需要發送DIO消 息（DODAG Information Object）。DODAG根節點將DIO消息中的Rank值設為1，然后廣播DIO消息給自己的鄰節點。當鄰節點收到DIO消息后，它將判斷是否是第一次接收DIO，如果是，就將發送節點加到自己的父節點列表中，并根據DIO消息中的OF來計算自己的Rank值以及自己到發送節點間的開銷。如果不是第一次接收，那么該節點會將該DIO消息中的Rank值和自己的Rank值進行比較，若小于自己的Rank值，就適當減小自己的Rank值，并將其作為自己的父節點，同時刪除父節點列表中與自己新的Rank值相同的父節點；若大于自己的Rank值，將丟棄此DIO消息。處理完DIO消息后，再將新的DIO消息以多播的形式轉發給自己的鄰節點，直到抵達葉節點為止。

DIO消息處理的偽算法如下：

在MP2P中，存儲模式和非存儲模式的節點都將父節點作為默認的下一跳路由，通過父節點轉發數據到根節點。當一個新的節點想要加入網絡時，它需要等待DIO信息的到來，或者它也可以主動向自己通信范圍內的節點多播DIS消息。收到該DIS消息的節點會單播DIO消息給請求節點，這樣新節點就可以順利加入網絡。DIS消息主要是在穩定環境中使用，如DODAG已經基本形成后，節點由于某種原因想再次獲取圖信息。

1.3 RPL下行路由的建立

P2MP即下行路由。該路由的建立需要發送DAO消 息（Destination Advertisement Object）。DODAG中的節點會觸發它子圖中的節點，向上發送DAO消息。該觸發信息存儲于DIO消息的某個字段中，稱為DAO觸發序列號（DAO Trigger Sequence Number，DTSN）。DAO消息的另一個觸發方式是收到子節點發送的DAO消息，根據該消息中DAOSequence字段來決定是否向上發送DAO消息。在非存儲模式中，如果節點收到的DIO消息中DTSN增加了，那么它也會增加自身的DTSN，然后將更新的DIO轉發給子節點。同時，它會單播一個DAO消息，經過默認父節點到根節點。收到DAO消息的節點不對其做任何處理，沿著DODAG向上轉發。在該模式中，只有根節點存有到下面節點的路由表，所以根節點會根據路由表構建到其余節點的源路由。在存儲模式中，當節點收到更新的DIO消息后啟動定時器。當定時時間到達時，向父節點單播DAO消息。DAO消息中包含節點的地址和頭部，收到DAO消息的節點更新其路由表，將發送DAO的節點作為目的地址的下一跳，并轉發更新后的DAO消息直到根節點。在該模式中，根節點只會存儲到達目的節點的下一跳地址，所有節點都得向父節點發送一條DAO消息來建立根節點到自己的路由。

兩種模式的過程如圖2所示。

存儲模式的偽算法如下：

從文獻[7]中的仿真結果也可以看出，在DIO、DIS和DAO三個消息中，DAO消息的發送是RPL路由開銷的主要因素。DAO消息之所以開銷如此之大，主要有兩個原因：第一，正如上文所分析的那樣，每個節點在收到父節點發來的DIO消息后，都需要向上發送一條DAO消息，因為DAO消息中只攜帶了發送節點的地址；第二，DAO消息比DIO消息發送的數量多得多，因為DAO消息是多跳發送到根節點，而DIO消息僅僅在單跳范圍內廣播，所以DAO消息的量遠遠大于DIO消息的量。

圖2 P2MP中非存儲模式和存儲模式

2 下行路由算法的改進

針對已有的問題，本文對現有的路由算法做了如下兩部分的改進：

第一，當節點收到DIO消息后，判斷自己是否為葉節點。若不是葉節點，處理完DIO消息后不向父節點發送DAO消息，只等待子節點發送DAO消息；如果是葉節點，則向其父節點發送DAO消息，開始建立下行路由。

偽算法如下：

第二，當節點收到子節點發來的DAO消息后，首先解析DAO消息，更新自己的路由表，然后將自己的地址信息添加到DAO消息的選項中，再發送給它的父節點。

改進的算法具有兩個優點：第一，實現了上行路由和下行路由的分開建立；第二，保證網絡中的每個葉節點到根節點的路徑上，每個節點只發送或轉發一次DAO消息，從而大大降低了能量的消耗。

下面將對該機制進行仿真，并與現有的機制作比較，評估其性能。

3 網絡仿真與分析

本文使用Contiki系統中的COOJA模擬器對RPL進行仿真與評估。如圖3所示，假設在區域內放置10個節點，節點8為根節點，節點9和10為葉子節點，其他均為路由節點，每個節點的通信范圍為50 m。

圖3 節點的網絡拓撲

RPL路由協議在網絡中實現的過程，即根節點節點啟動過程、節點收到DIO消息并擴散DIO消息、節點發送DIS請求消息以及節點向父節點發送DAO消息的過程。從圖4的仿真結果中可以看出，DAO消息的發送是由DIO消息所觸發，即沒有DIO消息發送的時候，也沒有DAO消息的發送。但是，DAO消息的數量要遠遠大于DIO和DIS的數量。因為除了節點本身向上發送DAO外，還要轉發子節點發送的DAO消息。

圖4 路由建立過程中不同消息的個數（改進前）

圖5為改進的RPL路由協議中三個控制消息的數量圖。從圖5中可以看出，在本文所提出的算法中，DIO消息和DIS消息沒有顯著的變化，而DAO消息的數量明顯減少，約是改進前的1/3，從而大大減少了下行路由建立過程中能量的損耗。另外，由于改進算法中，下行路由是從葉節點開始建立的，所以路由建立時間要比改進前慢30 s左右，但這并不影響網絡的性能。

圖5 路由建立過程中不同消息的個數（改進后）

4 結 語

本文介紹了RPL路由協議的相關概念以及上下行路由的建立過程，并對現有的下行路由中存在的不足做了適當的改進。同時，使用COOJA對新算法進行了性能仿真。從仿真結果中可以看出，經過改進后，下行路由的建立過程中所需要發送的DAO消息明顯減少，從而大大降低了路由過程中能量的損耗。同時，本文提出的機制實現了上下行路由的分開建立。后續工作可以從定時器的角度出發，可在具有不同Rank值的節點在DAO消息發送的時間設定上做一些算法研究，保證路由順利建立的前提下，減少路由的開銷，同時降低網絡的擁塞。

[1] IETF WG.Routing Over Low Power and Lossy Networks[S]. http://tools.ietf.org/wg/roll.

[2] T. Winter.RPL:Routing Protocol for Low Power and Lossy Networks[S].http://tools.ietf.org/html/rfc6550.

[3] Thubert P.Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks (RPL)[S]. http://tools.ietf.org/html/rfc6552.

[4] Vasseur J.Routing Metrics Used for Path Calculation in Low Power and Lossy Networks[S].http://tools.ietf.org/ html/rfc6551.

[5] Tripathi J,Oliveira JC de,Jean-Philippe V.A Performance Evaluation Study of RPL:Routing Protocol for Low Power and Lossy Networks[C].Information Sciences and Systems (CISS),2010 44th Annual Conference on.IEEE,2010.

[6] Gaddour O,Koubaa A.RPL in A Nutshell:A Survey[J] Computer Networks,2012,56(14):3163-3178.

[7] Accettura N,Grieco LA,Boggia G,et al.Performance Analysis of the RPL Routing Protocol[C].Mechatronics (ICM),2011 IEEE International Conference on.IEEE,2011.

孫懋珩（1957—），男，博士，副教授，主要研究方向為數字圖像處理、嵌入式、傳感網；

倪升武（1990—），男，碩士，主要研究方向為傳感網。

RPL Research and Improvement of Down Routing Algorithms in WSNs

SUN Mao-heng，NI Sheng-wu
(College of Electronic and Information Engineering, Tongji University, Shanghai 201804, China）

RPL is an IPv6 routing protocol proposed by the IETF ROLL Working Group for Low Power and Lossy Networks which contains Wireless sensor networks. This paper analyzes the process of building RPL up and down routing in detail, and finds a problem, a large energy loss during constructing the down routing, because of the large number of DAO messages sending. This paper proposes a new algorithm in terms of this problem and a simulator COOJA of Contiki system will be used to simulate and verify that the proposed algorithm reduces the number of DAO messages to 30% of original, thus greatly reduces energy consumption.

LLN;WSN;RPL;COOJA

TN929.5；TP212.9

：A

：1002-0802(2016)-06-0718-05

10.3969/j.issn.1002-0802.2016.06.013

2016-02-14;

：2016-05-06 Received date:2016-02-14;Revised date:2016-05-06