程克非 陳慈飛 李 棟 吳佳琪

(重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065)

0 引 言

近年來，隨著物聯(lián)網(wǎng)技術(shù)[1]的快速發(fā)展，低功耗有損網(wǎng)絡(luò)可以應(yīng)用在多種場景，包括工業(yè)監(jiān)控[2]、智能電網(wǎng)自動計量基礎(chǔ)設(shè)施(Advanced metering infrastructure,AMI)[3]和無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)[4]，研究低功耗有損網(wǎng)絡(luò)(Low power and lossy networks,LLN)的路由協(xié)議具有重要意義。浮空器上設(shè)備自組網(wǎng)是由具有數(shù)據(jù)采集、處理、傳輸能力的無線設(shè)備組成，其中包括飛控設(shè)備、紅外成像設(shè)備等，其主要特點是低動態(tài)拓撲、多數(shù)據(jù)流量形式、高可靠性、高穩(wěn)定性等。浮空器上設(shè)備自組網(wǎng)受限于有限的資源，屬于低功耗有損網(wǎng)絡(luò)的一種應(yīng)用場景，但是網(wǎng)絡(luò)規(guī)模要小于普通無線傳感器網(wǎng)絡(luò)。

現(xiàn)在，大部分的低功耗有損網(wǎng)絡(luò)的部署都采用基于開放式和標準化的IPv4/IPv6體系結(jié)構(gòu)與互聯(lián)網(wǎng)連接，這種方法使得LLN更具有互操作性、靈活性和多功能性。低功耗有損網(wǎng)絡(luò)中的無線節(jié)點資源有限，并且網(wǎng)絡(luò)中節(jié)點之間的鏈路質(zhì)量不能保持長期穩(wěn)定，這種情況讓路由協(xié)議的研究帶來了很多挑戰(zhàn)。國際互聯(lián)網(wǎng)工程任務(wù)組(The Internet Engineering Task Force，IETF)的低功耗有損網(wǎng)絡(luò)路由(Routing over Low Power and Lossy Networks,ROLL)小組在對比了OLSR[5]、AODV[6]等路由協(xié)議后，于2012年提出了RPL路由協(xié)議[7]，制定了標準RFC6550，以此引入基于IPv6的標準化協(xié)議。

目前，針對RPL路由協(xié)議的擁塞控制[8-9]和構(gòu)建過程[10]等方面已經(jīng)進行了相關(guān)研究。針對近根節(jié)點需要轉(zhuǎn)發(fā)大量的DAO消息導(dǎo)致網(wǎng)絡(luò)發(fā)生擁塞，文獻[11]提出一種改進的DelayDAO定時器機制，以控制DAO的轉(zhuǎn)發(fā)速率，避免擁塞，但是并未減少DAO消息的數(shù)量，同時增加了路由建立過程的收斂時間。文獻[12]提出了一種快速的DODAG形成機制，通過根據(jù)接收到的DIS(DODAG Information Solicitation)消息數(shù)量縮短DIO(DODAG Information Object)消息的傳輸間隔，這樣雖然加快了路由構(gòu)建的速度，但是每個節(jié)點增加了至少一次DIO消息的發(fā)送，產(chǎn)生了控制開銷。文獻[13]通過將上下行路由構(gòu)建過程完全分開，先通過逐跳發(fā)送DIO消息，以此建立上行路由，再由葉子節(jié)點向根節(jié)點逐跳回復(fù)DAO消息，以此建立下行路由。這種方式在一定程度上降低了開銷，但是由于低功耗有損網(wǎng)絡(luò)中鏈路狀態(tài)不穩(wěn)定，控制消息的丟失，就會使得整條路徑上的路由構(gòu)建失敗，這導(dǎo)致收斂時間和控制開銷的增加。

對現(xiàn)有RPL路由協(xié)議分析，低功耗有損網(wǎng)絡(luò)中存儲模式的路由構(gòu)建過程存在著以下的缺點：

1) 在路由構(gòu)建的時候，網(wǎng)絡(luò)是從根節(jié)點周圍逐層進行路由構(gòu)建，節(jié)點最后收到DAO-ACK(Destination Advertisement Object-Acknowledge)消息后，才完成路由構(gòu)建過程，然后向下一跳廣播DIO消息，這將導(dǎo)致整個網(wǎng)絡(luò)的路由構(gòu)建時間過長。當(dāng)節(jié)點收到DIO消息后，都需要立即向最優(yōu)父節(jié)點發(fā)送DAO消息，DIO消息是單跳內(nèi)廣播，而DAO消息經(jīng)過多跳傳輸?shù)礁?jié)點，這就導(dǎo)致網(wǎng)絡(luò)中，尤其是在靠近根節(jié)點的地方，DAO消息的數(shù)量過多，造成網(wǎng)絡(luò)擁塞。

2) 在路由構(gòu)建時，當(dāng)節(jié)點收到DIO消息后，需要立即回復(fù)一個DAO消息來加入DODAG，但是每個節(jié)點可能會有多個父節(jié)點，即短時間內(nèi)會有多個節(jié)點發(fā)送DIO消息，節(jié)點按順序接收DIO消息，當(dāng)節(jié)點選擇第一個DIO消息的發(fā)送者為最優(yōu)父節(jié)點后，若再次收到鏈路狀況更好的DIO消息，則需要進行切換，導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)的不穩(wěn)定，產(chǎn)生不必要的控制開銷。

本文將針對構(gòu)建過程中控制開銷過大及網(wǎng)絡(luò)收斂時間過長的問題，從DODAG的構(gòu)建過程出發(fā)，綜合考慮DAO定時器以及消息聚合等機制，對RPL路由協(xié)議進行改進，通過實驗對改進協(xié)議進行驗證分析。

1 RPL路由協(xié)議原理

RPL路由協(xié)議是距離矢量路由協(xié)議，可以工作在不同的MAC層之上[14]。RPL基于有向無環(huán)圖(Destination Oriented Directed Acyclic Graph,DODAG)的拓撲概念，這是一種典型的樹狀路由，每個節(jié)點都通過目標函數(shù)選擇一個最優(yōu)父節(jié)點，以此構(gòu)建一個有向無環(huán)圖。

如圖1所示，路由的構(gòu)建由根節(jié)點發(fā)起，根節(jié)點上電后，通過Trickle定時器[15]向周圍廣播DIO消息來通告自身的存在，DIO消息中包括實例號、DODAG ID、自身的Rank以及網(wǎng)絡(luò)的配置信息。當(dāng)周圍節(jié)點A收到根節(jié)點的DIO消息后，首先將根節(jié)點加入到自身的父節(jié)點列表中，再通過目標函數(shù)(Object Function,OF)和父節(jié)點的Rank值計算自身的Rank值，并且向根節(jié)點單播回復(fù)一個DAO消息，根節(jié)點收到DAO消息后，添加子節(jié)點信息，并且回復(fù)DAO-ACK消息，節(jié)點A收到DAO-ACK消息后，即完成入網(wǎng)過程。

圖1 路由構(gòu)建過程

節(jié)點A完成路由構(gòu)建后，將計算后的自身Rank值和網(wǎng)絡(luò)配置信息添加至DIO消息中，向周圍廣播。節(jié)點B收到DIO消息后，計算Rank值后，將節(jié)點A添加到父節(jié)點列表，若該節(jié)點為最優(yōu)父節(jié)點，則向節(jié)點A回復(fù)DAO消息，以建立下行路由。節(jié)點A收到該DAO消息后，添加至子節(jié)點列表中，并且將該DAO消息轉(zhuǎn)發(fā)到根節(jié)點。

根節(jié)點收到DAO消息后向節(jié)點B發(fā)送DAO-ACK消息，節(jié)點B收到DAO-ACK消息后，完成入網(wǎng)過程。

當(dāng)新節(jié)點C需要加入到網(wǎng)絡(luò)中時，向周圍節(jié)點周期性廣播DIS消息以請求加入到網(wǎng)絡(luò)中，周圍已經(jīng)加入DODAG的鄰居節(jié)點B收到該DIS消息后，會向節(jié)點C發(fā)送DIO消息，節(jié)點C收到以后，向父節(jié)點發(fā)送DAO消息，最后收到DAO-ACK消息后，完成入網(wǎng)過程。

路由構(gòu)建過程中，目標函數(shù)使用路由度量，如跳數(shù)和期望傳輸次數(shù)ETX，計算節(jié)點的Rank值，Rank值也將作為選擇最優(yōu)父節(jié)點的依據(jù)，節(jié)點通過比較父節(jié)點列表中父節(jié)點的Rank值，選擇最優(yōu)父節(jié)點。

RPL路由協(xié)議的構(gòu)建分為存儲模式和非存儲模式。在存儲模式下，每個節(jié)點收到DAO消息都需要存儲子孫節(jié)點的信息，并且建立路由表后，再將DAO消息轉(zhuǎn)發(fā)給自身的最優(yōu)父節(jié)點。在非存儲模式下，DAO消息直接發(fā)送給DODAG根節(jié)點，中間節(jié)點不存儲DAO消息內(nèi)容，僅將自己的地址添加在DAO消息中，發(fā)送給自己的最優(yōu)父節(jié)點，只有根節(jié)點擁有全網(wǎng)每個節(jié)點的路由信息。

2 RPL路由協(xié)議組網(wǎng)優(yōu)化算法

針對低功耗有損網(wǎng)中RPL路由協(xié)議構(gòu)建的收斂時間過長以及構(gòu)建過程中控制消息過多的問題，本文提出了一種RPL路由協(xié)議的組網(wǎng)優(yōu)化算法，其中包括“跨節(jié)點聚合DAO”和“自適應(yīng)DAO定時器”兩部分，從而有效減少了構(gòu)建過程中的收斂時間和降低構(gòu)建過程中RPL的控制開銷。

2.1 跨節(jié)點聚合DAO

在RPL路由協(xié)議的存儲模式下，DAO數(shù)據(jù)包不是單播到DODAG的根節(jié)點，而是單播給自身的最優(yōu)父節(jié)點，然后最優(yōu)父節(jié)點添加完路由信息后發(fā)送給自身的父節(jié)點，這些DAO數(shù)據(jù)包以逐跳的方式到達DODAG的根節(jié)點，從而建立起RPL路由協(xié)議的下行路由。

“跨節(jié)點聚合DAO”機制在DIO消息中Reserved保留字段引入了DAO-Aggregation字段，在路由構(gòu)建過程中，節(jié)點通過判斷DIO消息中的DAO-Aggregation，以此決定是否需要聚合子節(jié)點DAO消息，以減少DAO消息的發(fā)送數(shù)量。其DIO消息的消息格式如圖2所示。

圖2 DIO消息格式

圖2中的字段Agg是DAO消息聚合標志位，即DAO-Aggregation，占用8 bit保留字段中的1 bit。當(dāng)DAO-Aggregation為1時，則表示節(jié)點需要聚合DAO消息，DAO-Aggregation為0時，節(jié)點立即回復(fù)DAO消息。

為了更好地兼容原有協(xié)議，聚合后的DAO消息采用原協(xié)議中的Target選項，Target選項用于指示沿DODAG可以到達的目的IPv6地址，即表示目標IPv6地址節(jié)點的可到達性。

本文將對聚合機制中的Target選項的包格式進行重新設(shè)計，如圖3所示。

圖3 改進后的Target選項

Option Length為整個Target選項的長度，DAO-PRI為優(yōu)先級標志位，占用2 bit，告知父節(jié)點此消息能否被聚合，Prefix Length為IPv6地址的前綴長度。

對于聚合DAO消息中最大能聚合的地址數(shù)量，本文定義為Targetmax，其計算公式為：

(1)

DAOoverhead=IPv6h+ICMPv6h+DAOh+Tageth

(2)

式中：MTU為網(wǎng)絡(luò)中的最大傳輸單元，由網(wǎng)絡(luò)層而決定。IPv6h、ICMPv6h、DAOh、Targeth為控制消息中的IPv6頭部、ICMPv6頭部、DAO頭部和目標選項的頭部大小。

“跨節(jié)點聚合DAO”機制的算法流程如圖4所示。

圖4 “跨節(jié)點聚合DAO”流程圖

整個DODAG的構(gòu)建由根節(jié)點發(fā)起，將DIO消息中的DAO-Aggregation置為1,向周圍節(jié)點廣播DIO消息，讓鄰居節(jié)點能夠加入到當(dāng)前網(wǎng)絡(luò)中。節(jié)點收到的DIO消息的DAO-Aggregation字段與自身發(fā)出的DIO消息中的DAO-Aggregation字段相反。

步驟一當(dāng)節(jié)點收到DIO消息后，從DIO中獲取DODAG信息，選擇是否加入到網(wǎng)絡(luò)中，若不加入網(wǎng)絡(luò)，則返回繼續(xù)監(jiān)聽。若選擇加入到網(wǎng)絡(luò)中，則添加路由信息，轉(zhuǎn)至步驟二。

步驟二判斷DAO-Aggregation是否為1，若該字段不為1，則添加完路由信息后，立即向自身最優(yōu)父節(jié)點發(fā)送DAO消息，通告自身的目的地信息。若該字段為1，則不立即回復(fù)DAO消息，設(shè)置定時器以聚合DAO消息，轉(zhuǎn)至步驟三。

步驟三設(shè)置完定時器后，將DIO消息中的DAO-Aggregation設(shè)置為0，并且向自身的周圍節(jié)點進行廣播。

步驟四在定時器到期前，若收到子節(jié)點的DAO消息，判斷此時聚合數(shù)量是否已達上限，若未達到上限，則將該DAO消息聚合至自身的DAO消息中。若已達上限，則進行保存第二個DAO消息中，并轉(zhuǎn)至步驟五。

步驟五在定時器到期后，節(jié)點將聚合后的DAO消息發(fā)送給自身的最優(yōu)父節(jié)點。

2.2 自適應(yīng)DAO定時器

DAO定時器決定了等待聚合的時間，起著非常重要的作用。在實際中，如果DAO定時器的時間值設(shè)置得比較小，節(jié)點在收到DAO消息后，將在很短的時間就發(fā)送給自身的父節(jié)點，無法達到聚合的最佳效果，尤其是在位于根節(jié)點附近的節(jié)點，無法降低近根節(jié)點周圍的開銷和緩解網(wǎng)絡(luò)擁塞。而如果DAO定時器的時間設(shè)置得比較大，雖然很大程度上降低了控制開銷，但是整個網(wǎng)絡(luò)中，因為在各個設(shè)置DAO定時器的節(jié)點上會產(chǎn)生較大的延時，導(dǎo)致網(wǎng)絡(luò)構(gòu)建時間加長。因此，傳輸DAO消息的延時時間需要和拓撲信息結(jié)合。與此同時，節(jié)點收到DIO消息后，立即回復(fù)DAO消息，也使得構(gòu)建過程中發(fā)生切換父節(jié)點的次數(shù)增加，增加網(wǎng)絡(luò)的不穩(wěn)定性。

本文提出一種“自適應(yīng)DAO定時器”，節(jié)點在收到DIO消息之前，通過收到的DIS消息，掌握自身的鄰居節(jié)點情況。定義Tdelaydao為DAO定時器的延時時間：

Tdelaydao=TRTT+Tprocess×Nneighbor

(3)

式中：TRTT為節(jié)點與子節(jié)點的單跳往返時延，Tprocess為節(jié)點處理DAO數(shù)據(jù)的平均時間。Nneighbor為節(jié)點的鄰居數(shù)。

在DODAG根節(jié)點廣播DIO消息前，普通節(jié)點都處于未加入DODAG的狀態(tài)，需向周圍周期性廣播DIS消息。普通節(jié)點根據(jù)收到的DIS消息判斷自身周圍鄰居節(jié)點的數(shù)量，并且自定義自身的DAO定時器。

當(dāng)節(jié)點開啟DAO定時器后，等待子節(jié)點的DAO消息的時間內(nèi)，通過比較定時時間內(nèi)收到的DIO消息，以決定最優(yōu)父節(jié)點，增加鏈路的穩(wěn)定性，減少切換父節(jié)點造成的不必要開銷。對于需要聚合DAO消息的節(jié)點而言，DAO定時器將一定程度上增加其組網(wǎng)時間，降低響應(yīng)實時性，但是對整個DODAG的構(gòu)建來說，一次對DODAG的兩層節(jié)點進行路由構(gòu)建取代了原有逐層進行路由構(gòu)建，縮短了整個DODAG的路由構(gòu)建的收斂時間。

3 RPL路由協(xié)議組網(wǎng)優(yōu)化算法實驗

本節(jié)將模擬浮空器上設(shè)備自組網(wǎng)的應(yīng)用場景進行實現(xiàn)和驗證。為了驗證RPL路由協(xié)議的組網(wǎng)優(yōu)化算法的性能，采用基于OpenWRT(嵌入式Linux的發(fā)行版)系統(tǒng)的JS9331低功耗Wi-Fi開發(fā)板，單跳覆蓋范圍為30 m。對比協(xié)議為原始RPL路由協(xié)議、文獻[12]中的RPL路由協(xié)議。

3.1 RPL路由協(xié)議的實現(xiàn)框架

整個協(xié)議的實現(xiàn)包括兩個部分，分別為“路由控制模塊”和“數(shù)據(jù)轉(zhuǎn)發(fā)模塊”，分別位于用戶空間和內(nèi)核空間?！奥酚煽刂颇K”分為DIO、DAO、DAO-ACK、DIS消息的發(fā)送及處理模塊、偵聽模塊、Trickle定時器模塊、目標函數(shù)模塊、路由更新模塊等關(guān)鍵子模塊，“數(shù)據(jù)轉(zhuǎn)發(fā)模塊”分為Pre-routing、Post-routing模塊、虛擬文件模塊等關(guān)鍵子模塊。

系統(tǒng)整體框架如圖5所示?！奥酚煽刂颇K”通過DIO、DAO、DAO-ACK、DIS等控制信息的交互，獲取鏈路信息，產(chǎn)生路由表信息，并將路由表信息通過PROC文件共享至內(nèi)核空間?！皵?shù)據(jù)轉(zhuǎn)發(fā)模塊”采用Netfilter框架，通過hook技術(shù)在掛載點進行嵌入，當(dāng)數(shù)據(jù)包進入到Linux操作系統(tǒng)協(xié)議棧后，依據(jù)“路由控制模塊”的路由信息，對數(shù)據(jù)包進行解析和處理，實現(xiàn)數(shù)據(jù)包的正確尋路、傳輸。

圖5 整體實現(xiàn)框架

3.2 實驗參數(shù)配置

實驗中，為了模擬真實的設(shè)備節(jié)點，實驗節(jié)點間的距離為20 m，根據(jù)不同的節(jié)點數(shù)量設(shè)置6種不同的網(wǎng)絡(luò)拓撲。節(jié)點數(shù)為5、6的DODAG有同樣的網(wǎng)絡(luò)深度，深度為3；節(jié)點數(shù)為7、8的DODAG有同樣的網(wǎng)絡(luò)深度，深度為4；節(jié)點數(shù)為9的DODAG網(wǎng)絡(luò)深度為5。本文實驗環(huán)境的主要具體參數(shù)配置如表1所示。

表1 參數(shù)配置

續(xù)表1

3.3 實驗結(jié)果分析

本文為評估優(yōu)化后的RPL路由協(xié)議的性能，將從路由構(gòu)建時間、控制開銷兩個方面對所提出的RPL路由協(xié)議組網(wǎng)優(yōu)化算法進行驗證。為了保證數(shù)據(jù)的可靠性，每次實驗測試重復(fù)10次，最終取平均值作為最后結(jié)果。下面將對性能指標進行定義。

1) 路由構(gòu)建時間：從根節(jié)點開機后發(fā)起組網(wǎng)至網(wǎng)絡(luò)中全部節(jié)點都收到DAO-ACK消息，加入到DODAG中的時間。

2) 路由構(gòu)建總控制開銷：路由構(gòu)建時間內(nèi)，網(wǎng)絡(luò)中節(jié)點發(fā)送DIO、DAO、DAO-ACK、DIS控制消息的總字節(jié)數(shù)。

如圖6所示，隨著DODAG中節(jié)點的數(shù)量增加，構(gòu)建時間也在增加。其中當(dāng)網(wǎng)絡(luò)深度增加的時候，DODAG的構(gòu)建時間增加幅度要相對高一些。對比圖中，優(yōu)化后的RPL路由協(xié)議，控制開銷降低了至少9.3%。分析其主要原因為：網(wǎng)絡(luò)初始化構(gòu)建時，原始的RPL路由協(xié)議是逐層進行路由構(gòu)建，并進行確認，“跨節(jié)點聚合DAO”機制和“自適應(yīng)DAO定時器”每一次是針對DODAG中兩層的節(jié)點進行入網(wǎng)確認，使得構(gòu)建過程中減少了DAO消息和DAO-ACK消息的交互次數(shù)，從而有效地減少路由構(gòu)建時間。

圖6 路由構(gòu)建時間比較

如圖7所示為構(gòu)建過程中的控制開銷對比圖。隨著網(wǎng)絡(luò)中節(jié)點的數(shù)量增加，控制開銷的數(shù)量也在增加。如圖7(a)所示，本文優(yōu)化后的RPL路由協(xié)議相比于其他協(xié)議，DAO消息的數(shù)量得到了明顯的下降。如圖7(b)所示為路由構(gòu)建的總控制開銷對比，優(yōu)化的RPL路由協(xié)議比現(xiàn)有RPL路由協(xié)議在路由構(gòu)建過程的總控制開銷至少降低了10.6%。

(a) DAO消息數(shù)量

(b) 路由構(gòu)建總控制開銷圖7 路由構(gòu)建控制開銷比較

分析其主要原因：首先，“跨節(jié)點聚合DAO”機制將子節(jié)點的地址聚合成一個DAO消息，有效減少了向根節(jié)點發(fā)送的DAO消息的字節(jié)數(shù)，其次，“自適應(yīng)DAO定時器”減少了DAO消息聚合節(jié)點的父節(jié)點切換次數(shù)，即減少了路由切換時的DAO消息的數(shù)量。最后，組網(wǎng)優(yōu)化算法對聚合后的節(jié)點進行統(tǒng)一確認也降低了DAO-ACK消息的數(shù)量，從而減少了路由構(gòu)建的總控制開銷。

4 結(jié) 語

本文針對RPL路由構(gòu)建過程中收斂時間過長以及控制開銷過多的問題，提出一種RPL路由協(xié)議的組網(wǎng)優(yōu)化算法，其包括了“跨節(jié)點聚合DAO”機制和“自適應(yīng)DAO定時器”兩種新機制。該算法對網(wǎng)絡(luò)中的DAO消息進行有效聚合，并且通過對聚合的DAO消息進行統(tǒng)一的確認。實驗測試表明，RPL路由協(xié)議的組網(wǎng)優(yōu)化算法不僅能夠有效降低控制開銷，并且能縮短路由構(gòu)建過程的收斂時間。在未來的工作中，我們將對父節(jié)點的選擇機制進行研究，進一步增強網(wǎng)絡(luò)的穩(wěn)定性。