引言

低功耗有損網(wǎng)絡(luò)路由協(xié)議(RPL)是IETF的ROLL(RoutingOverLowpowerandLossynetworks)工作組，專門針對低功耗有損網(wǎng)絡(luò)LLN(LowpowerandLossynetwork)新提出來的路由協(xié)議。低功耗有損網(wǎng)絡(luò)是由功率、存儲空間、處理能力等資源受限的嵌入式設(shè)備所組成的網(wǎng)絡(luò)。它們可以通過多種鏈路連接，比如IEEE802.15.4、藍(lán)牙、低功率WiFi，甚至低功耗電力線通信(PLC)等等。ROLL將LLN網(wǎng)絡(luò)的應(yīng)用主要劃分為四個領(lǐng)域：城市網(wǎng)絡(luò)(包括智能電網(wǎng)應(yīng)用)、建筑自動化、工業(yè)自動化以及家庭自動化，并且分別制定了針對四個應(yīng)用領(lǐng)域的路由需求。由于LLN的獨特性，傳統(tǒng)的IP路由協(xié)議，比如OSPF、IS-IS、AODV、OLSR，無法滿足其獨特的路由需求，因此ROLL工作組制定了RPL協(xié)議,其協(xié)議標(biāo)準(zhǔn)RFC6550發(fā)布于2012年3月。

本論文首先介紹了RPL的應(yīng)用場景及基本原理，并在路徑選擇策略中加入了對節(jié)點剩余能量的考慮；最后通過仿真驗證了改進(jìn)后的路由協(xié)議的性能。

1RPL協(xié)議工作原理

RPL是一個矢量路由協(xié)議，通過構(gòu)建有向非循環(huán)圖(DAG)來形成拓?fù)浣Y(jié)構(gòu)，加入DAG中的節(jié)點自動形成一條指向根節(jié)點的路徑。RPL主要為數(shù)據(jù)匯聚型的場景設(shè)計，即數(shù)據(jù)流量由葉節(jié)點指向根節(jié)點。當(dāng)然RPL也擴(kuò)展支持多點對點(MP2P)和點對點(P2P)的應(yīng)用場景。

圖1所示為典型的DAG結(jié)構(gòu)。其中的每一個節(jié)點至少有一條指向根節(jié)點的路徑。

圖1DAG結(jié)構(gòu)示意圖

1.1DODAG的形成

DODAG(DestinationOrientedDirectedAcyclicGraph)是面向目的地的有向非循環(huán)圖的簡稱，可以視為物理網(wǎng)絡(luò)上的邏輯路由拓?fù)洹?

RPL中定義了由多種ICMPv6消息來控制拓?fù)涞男纬?。DIO消息用于通告有關(guān)DODAG的參數(shù)，例如DODAGID、目標(biāo)函數(shù)(OF)、DODAG版本號等。其中OF規(guī)定了拓?fù)浣⒓白顑?yōu)父節(jié)點的選擇方式，規(guī)定了節(jié)點級別的計算方法,是路徑選擇的首要參考標(biāo)準(zhǔn)。級別決定了節(jié)點在DODAG中的相對位置，主要用于避免回路。DAO消息是用來建立從根節(jié)點到葉節(jié)點的“向下”的路徑。根據(jù)節(jié)點的存儲能力，RPL協(xié)議中將節(jié)點類型定義為可存儲型和非存儲型，兩者的區(qū)別在于是否存儲有路由表信息。在圖1中，當(dāng)D節(jié)點要和E節(jié)點通信時，如果B節(jié)點和C節(jié)點是非存儲型，那么必須先追溯到根節(jié)點A，查找路由，即路徑為D—C一B—A一B—C一E。若C為可存儲型節(jié)點，則只需追溯到共同的祖先節(jié)點即可找到路由，即路徑為D—C—E。DIS消息用于向鄰居節(jié)點請求DODAG信息。當(dāng)一個孤立的節(jié)點沒有收到任何DIO消息的時候，可通過DIS向周圍節(jié)點請求DODAG信息。收到DIS消息的節(jié)點會反饋DIO消息給DIS源節(jié)點。

如圖1所示，首先A節(jié)點通過DIO消息廣播自己創(chuàng)建的DODAG信息，收到DIO消息的節(jié)點根據(jù)OF來決定是否應(yīng)該加入該DODAG；加入之后然后再向自己周圍的節(jié)點繼續(xù)廣播DIO消息；這樣一層一層地建立拓?fù)浣Y(jié)構(gòu)。當(dāng)節(jié)點加入DODAG之后，就自動創(chuàng)建一條“向上”匯聚到根節(jié)點的路徑?！跋蛳隆钡穆窂絼t由DAO消息完成。

1.2定時器管理

RPL中使用細(xì)流算法［7］來控制DIO消息的發(fā)送。細(xì)流算法是一個適應(yīng)性的機(jī)制，用來限制控制協(xié)議的開銷。與傳統(tǒng)IP網(wǎng)絡(luò)不同，LLN網(wǎng)絡(luò)有著非常有限的資源，必須盡可能的減少控制協(xié)議消息所占的比例，但同時又必須要維護(hù)好網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)網(wǎng)絡(luò)改變時，節(jié)點會以較高的頻率發(fā)送控制包；當(dāng)網(wǎng)絡(luò)趨于穩(wěn)定時，則控制流的速率減少。算法中定義了控制消息發(fā)送間隔參數(shù)I，當(dāng)網(wǎng)絡(luò)很穩(wěn)定時，則I成倍的增加；而網(wǎng)絡(luò)有動蕩時，則發(fā)送間隔迅速降為最小值，高頻率的發(fā)送控制消息以修復(fù)網(wǎng)絡(luò)。

本文借助Contiki系統(tǒng)中的Cooja模擬器，對RPL協(xié)議進(jìn)行了仿真。圖2所示為節(jié)點布局圖，并在圖3中以節(jié)點5為例展示了DIO消息的發(fā)送控制過程。從圖3中可以看到，當(dāng)網(wǎng)絡(luò)剛形成逐步趨于穩(wěn)定的時候,DIO消息發(fā)送間隔成倍增加;圖3中23:00和01：20附近陡峭的轉(zhuǎn)折點表明此時監(jiān)測到節(jié)點5和網(wǎng)絡(luò)存在不一致性，迅速將控制消息發(fā)送間隔調(diào)至最小值以迅速修復(fù)網(wǎng)絡(luò)。

圖2ContikiRPL在Cooja模擬器中的仿真

圖3細(xì)流算法對DIO消息發(fā)送頻率的控制

1.3環(huán)路避免機(jī)制

RPL中規(guī)定，在沿著葉節(jié)點到根節(jié)點的路徑上，節(jié)點級別必須是遞減的［1］，即父節(jié)點的級別必須小于子節(jié)點的級別。當(dāng)節(jié)點在網(wǎng)絡(luò)中位置發(fā)生改變時，必須根據(jù)父節(jié)點重新計算自己的級別。假設(shè)節(jié)點N的最優(yōu)父節(jié)點為P，P的級別為R(P),那么N的級別R(N)計算公式為：

R(N)=R(P)+rank_increase

rank_increase為子節(jié)點和父節(jié)點級別的差值，其算法在OF中有定義。

節(jié)點的級別在環(huán)路避免中有著重要的意義。RPL協(xié)議也通過在包頭上設(shè)定標(biāo)志位來附帶路由控制數(shù)據(jù)，以避免數(shù)據(jù)包被循環(huán)轉(zhuǎn)發(fā)。

2考慮節(jié)點剩余能量的RPL協(xié)議

2.1RPL協(xié)議原始路由方案

目標(biāo)函數(shù)決定了RPL協(xié)議的路徑選擇方式。目前RPL的官方文件中，只明確定義了零目標(biāo)函數(shù)(OF0)［8］,即以跳數(shù)(HC)為最佳路徑選擇的唯一標(biāo)準(zhǔn)，而其他的目標(biāo)函數(shù)則由開發(fā)者根據(jù)需求靈活定義。比如對鏈路可靠性要求較高的應(yīng)用，可將鏈路質(zhì)量作為路由選擇的首要考慮標(biāo)準(zhǔn)；而對能量受限的環(huán)境則可以定義在路徑中盡量避開電池供電節(jié)點。在文檔RFC6551図中，提出了多種可供開發(fā)者參考的路由度量。

在選擇路徑時，若只考慮跳數(shù)因素，必然會導(dǎo)致Sink周邊節(jié)點數(shù)據(jù)壓力過大，從而使關(guān)鍵節(jié)點能量過早消耗而死亡。文獻(xiàn)［10］將網(wǎng)絡(luò)的生命長度定義為第一個節(jié)點死亡的時間。對于能量受限的低功耗有損網(wǎng)絡(luò)，如何平衡能量消耗，延長網(wǎng)絡(luò)整體壽命，是協(xié)議要考慮的重要因素。

2.2優(yōu)化之后的RPL路由方案

目前已有多種針對無線傳感網(wǎng)絡(luò)能量優(yōu)化的路由協(xié)議,比如分級能量路由協(xié)議LEACH和TEEN，以數(shù)據(jù)為中心的能量有效路由協(xié)議DD和SPIN，還有基于地理位置的路由協(xié)議GPSR和GEAR等［11］。但這些協(xié)議都很難實現(xiàn)和RPL協(xié)議的融合。RPL協(xié)議是通過在containermetric中，定義路徑選擇時所考慮的參數(shù)，然后再以一定的方式將所需要考慮的參數(shù)相結(jié)合，從而確定一個合理的路徑選擇方案。

本篇論文中采取的是跳數(shù)(HC)和節(jié)點能量(EN)相結(jié)合的方式。結(jié)合方式有兩種［12］，一種是Lex，一種是Add。Lex是指優(yōu)先考慮跳數(shù)，只有在跳數(shù)相同的情況下，才考慮節(jié)點能量；而Add則是采取兩種參數(shù)綜合考慮的方式，按照一定的比例相結(jié)合，即：

本文對這兩種不同的結(jié)合方式做了仿真對比。

2.3RPL協(xié)議改進(jìn)前后的仿真對比

仿真工具采用的是美國UIUC大學(xué)開發(fā)的針對無線傳感網(wǎng)絡(luò)研究的J-Sim平臺，該平臺基于Java語言，和NS2相比具有內(nèi)存消耗小、仿真速度快、有更好的可擴(kuò)展性等優(yōu)點。本文仿真了傳感網(wǎng)絡(luò)數(shù)據(jù)收集的場景。在100X100的區(qū)域里,規(guī)則的布置有100個節(jié)點，圖4所示是網(wǎng)絡(luò)節(jié)點布局圖和OF0的拓?fù)浣Y(jié)構(gòu)，其中最左上側(cè)的0號節(jié)點為數(shù)據(jù)匯聚節(jié)點，右下側(cè)的49-99和94-98這11個節(jié)點為傳感器數(shù)據(jù)采集節(jié)點。數(shù)據(jù)從右下側(cè)的11個源節(jié)點發(fā)送到左上側(cè)的0號節(jié)點。由于該網(wǎng)絡(luò)具有對稱性，1和10對稱，2和20對稱等，對稱節(jié)點的能量消耗基本一致。本文中重點仿真了具有代表性的1、2、11、12、22這幾個關(guān)鍵節(jié)點的能量消耗情況。

圖4網(wǎng)絡(luò)節(jié)點布局圖和OF0的拓?fù)浣Y(jié)構(gòu)

對于OF0，由于跳數(shù)是路徑選擇的唯一標(biāo)準(zhǔn)，節(jié)點位置固定的網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)也相對保持不變。圖4即為這種情況下的拓?fù)浣Y(jié)構(gòu)。由圖4中可以看到，節(jié)點1和節(jié)點10承載了大部分的數(shù)據(jù)量，幾乎任何從下側(cè)或者右側(cè)源節(jié)點發(fā)過來的數(shù)據(jù)都要經(jīng)過這兩個節(jié)點轉(zhuǎn)發(fā)到Sink節(jié)點。而節(jié)點11，貝貝有來自源節(jié)點99的數(shù)據(jù)由它轉(zhuǎn)發(fā)。

圖5所示是系統(tǒng)節(jié)點能耗圖。其中圖5(a)為OF0方案下部分節(jié)點能量消耗圖。從圖中可以看出，最關(guān)鍵的節(jié)點1和節(jié)點10,能量很快就消耗殆盡。而節(jié)點11，則能耗相對較少。這對節(jié)點位置固定的網(wǎng)絡(luò)是很不利的，會使數(shù)據(jù)量較大的節(jié)點在短期內(nèi)能量迅速消耗完而死亡，而其他非位置關(guān)鍵節(jié)點,則一直被閑置。造成網(wǎng)絡(luò)能耗分布極其不均勻，能量利用率不咼。

接下來可以仿真跳數(shù)和節(jié)點剩余能量相結(jié)合的路徑選擇方式，圖5(b)為跳數(shù)和能量按照2:8的比例加權(quán)所得到的能耗結(jié)果。從圖5(b)可以看出，節(jié)點1、10和11的能耗更為均衡,第一個節(jié)點死亡的時間大為延長。跳數(shù)和節(jié)點剩余能量相結(jié)合的路徑選擇方式，能一定程度上改善以跳數(shù)為唯一度量所造成了能量消耗不均的情況，從而延長關(guān)鍵節(jié)點的生命長度。仿真中也能看到，最佳路徑的拓?fù)鋱D一直處于動態(tài)變化，原先經(jīng)過節(jié)點1和節(jié)點10到達(dá)匯聚節(jié)點的數(shù)據(jù)，有一部分從節(jié)點11分流，從而緩解節(jié)點1和節(jié)點10的壓力。

本文也仿真了跳數(shù)(HC)和節(jié)點能量(EN)按照Lex的結(jié)合方式，即優(yōu)先考慮最小跳數(shù)，當(dāng)跳數(shù)相同的時候再考慮節(jié)點能量，以及在Add結(jié)合方式下按0.8HC+0.2EN和0.2HC+0.8EN的不同比例相結(jié)合的情況對比。最后得出的結(jié)論是，兩種不同的結(jié)合方式對網(wǎng)絡(luò)能耗均衡都有一定程度的改善；而Add的結(jié)合方式能耗更為均衡，且剩余能量所占的比例越高，改善的效果越為顯著。圖6所示是在不同路由策略下，關(guān)鍵節(jié)點能耗的對比情況。

本文描述了RPL協(xié)議的基本原理，并且對原路由協(xié)議的路徑選擇策略進(jìn)行了改進(jìn)，在只考慮跳數(shù)的基礎(chǔ)上，加入節(jié)點剩余能量的考慮，從而平衡了網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)整體壽命。由于RPL是近幾年新提出的協(xié)議，隨著實踐的不斷深入,越來越多的新問題被提出，還有很大的研究空間。RPL協(xié)議在物聯(lián)網(wǎng)領(lǐng)域有著廣闊的應(yīng)用前景，值得廣大學(xué)者進(jìn)一步深入研究。

5致謝

本論文的工作得到了實驗室項目的大力支持。感謝國家自然科學(xué)基金(61271257),北京市自然科學(xué)基金(4122034)和教育部博士點基金(20120005110007)對本文研究工作的支持。

20211118_6196307d10800__無線傳感網(wǎng)絡(luò)中的RPL路由協(xié)議研究