無線傳感網(wǎng)絡(luò)中的RPL路由協(xié)議研究
掃描二維碼
隨時(shí)隨地手機(jī)看文章
引言
低功耗有損網(wǎng)絡(luò)路由協(xié)議(RPL)是IETF的ROLL(RoutingOverLowpowerandLossynetworks)工作組,專門針對(duì)低功耗有損網(wǎng)絡(luò)LLN(LowpowerandLossynetwork)新提出來的路由協(xié)議。低功耗有損網(wǎng)絡(luò)是由功率、存儲(chǔ)空間、處理能力等資源受限的嵌入式設(shè)備所組成的網(wǎng)絡(luò)。它們可以通過多種鏈路連接,比如IEEE802.15.4、藍(lán)牙、低功率WiFi,甚至低功耗電力線通信(PLC)等等。ROLL將LLN網(wǎng)絡(luò)的應(yīng)用主要?jiǎng)澐譃樗膫€(gè)領(lǐng)域:城市網(wǎng)絡(luò)(包括智能電網(wǎng)應(yīng)用)、建筑自動(dòng)化、工業(yè)自動(dòng)化以及家庭自動(dòng)化,并且分別制定了針對(duì)四個(gè)應(yīng)用領(lǐng)域的路由需求。由于LLN的獨(dú)特性,傳統(tǒng)的IP路由協(xié)議,比如OSPF、IS-IS、AODV、OLSR,無法滿足其獨(dú)特的路由需求,因此ROLL工作組制定了RPL協(xié)議,其協(xié)議標(biāo)準(zhǔn)RFC6550發(fā)布于2012年3月。
本論文首先介紹了RPL的應(yīng)用場景及基本原理,并在路徑選擇策略中加入了對(duì)節(jié)點(diǎn)剩余能量的考慮;最后通過仿真驗(yàn)證了改進(jìn)后的路由協(xié)議的性能。
1RPL協(xié)議工作原理
RPL是一個(gè)矢量路由協(xié)議,通過構(gòu)建有向非循環(huán)圖(DAG)來形成拓?fù)浣Y(jié)構(gòu),加入DAG中的節(jié)點(diǎn)自動(dòng)形成一條指向根節(jié)點(diǎn)的路徑。RPL主要為數(shù)據(jù)匯聚型的場景設(shè)計(jì),即數(shù)據(jù)流量由葉節(jié)點(diǎn)指向根節(jié)點(diǎn)。當(dāng)然RPL也擴(kuò)展支持多點(diǎn)對(duì)點(diǎn)(MP2P)和點(diǎn)對(duì)點(diǎn)(P2P)的應(yīng)用場景。
圖1所示為典型的DAG結(jié)構(gòu)。其中的每一個(gè)節(jié)點(diǎn)至少有一條指向根節(jié)點(diǎn)的路徑。
圖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版本號(hào)等。其中OF規(guī)定了拓?fù)浣⒓白顑?yōu)父節(jié)點(diǎn)的選擇方式,規(guī)定了節(jié)點(diǎn)級(jí)別的計(jì)算方法,是路徑選擇的首要參考標(biāo)準(zhǔn)。級(jí)別決定了節(jié)點(diǎn)在DODAG中的相對(duì)位置,主要用于避免回路。DAO消息是用來建立從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的“向下”的路徑。根據(jù)節(jié)點(diǎn)的存儲(chǔ)能力,RPL協(xié)議中將節(jié)點(diǎn)類型定義為可存儲(chǔ)型和非存儲(chǔ)型,兩者的區(qū)別在于是否存儲(chǔ)有路由表信息。在圖1中,當(dāng)D節(jié)點(diǎn)要和E節(jié)點(diǎn)通信時(shí),如果B節(jié)點(diǎn)和C節(jié)點(diǎn)是非存儲(chǔ)型,那么必須先追溯到根節(jié)點(diǎn)A,查找路由,即路徑為D—C一B—A一B—C一E。若C為可存儲(chǔ)型節(jié)點(diǎn),則只需追溯到共同的祖先節(jié)點(diǎn)即可找到路由,即路徑為D—C—E。DIS消息用于向鄰居節(jié)點(diǎn)請(qǐng)求DODAG信息。當(dāng)一個(gè)孤立的節(jié)點(diǎn)沒有收到任何DIO消息的時(shí)候,可通過DIS向周圍節(jié)點(diǎn)請(qǐng)求DODAG信息。收到DIS消息的節(jié)點(diǎn)會(huì)反饋DIO消息給DIS源節(jié)點(diǎn)。
如圖1所示,首先A節(jié)點(diǎn)通過DIO消息廣播自己創(chuàng)建的DODAG信息,收到DIO消息的節(jié)點(diǎn)根據(jù)OF來決定是否應(yīng)該加入該DODAG;加入之后然后再向自己周圍的節(jié)點(diǎn)繼續(xù)廣播DIO消息;這樣一層一層地建立拓?fù)浣Y(jié)構(gòu)。當(dāng)節(jié)點(diǎn)加入DODAG之后,就自動(dòng)創(chuàng)建一條“向上”匯聚到根節(jié)點(diǎn)的路徑。“向下”的路徑則由DAO消息完成。
1.2定時(shí)器管理
RPL中使用細(xì)流算法[7]來控制DIO消息的發(fā)送。細(xì)流算法是一個(gè)適應(yīng)性的機(jī)制,用來限制控制協(xié)議的開銷。與傳統(tǒng)IP網(wǎng)絡(luò)不同,LLN網(wǎng)絡(luò)有著非常有限的資源,必須盡可能的減少控制協(xié)議消息所占的比例,但同時(shí)又必須要維護(hù)好網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)網(wǎng)絡(luò)改變時(shí),節(jié)點(diǎn)會(huì)以較高的頻率發(fā)送控制包;當(dāng)網(wǎng)絡(luò)趨于穩(wěn)定時(shí),則控制流的速率減少。算法中定義了控制消息發(fā)送間隔參數(shù)I,當(dāng)網(wǎng)絡(luò)很穩(wěn)定時(shí),則I成倍的增加;而網(wǎng)絡(luò)有動(dòng)蕩時(shí),則發(fā)送間隔迅速降為最小值,高頻率的發(fā)送控制消息以修復(fù)網(wǎng)絡(luò)。
本文借助Contiki系統(tǒng)中的Cooja模擬器,對(duì)RPL協(xié)議進(jìn)行了仿真。圖2所示為節(jié)點(diǎn)布局圖,并在圖3中以節(jié)點(diǎn)5為例展示了DIO消息的發(fā)送控制過程。從圖3中可以看到,當(dāng)網(wǎng)絡(luò)剛形成逐步趨于穩(wěn)定的時(shí)候,DIO消息發(fā)送間隔成倍增加;圖3中23:00和01:20附近陡峭的轉(zhuǎn)折點(diǎn)表明此時(shí)監(jiān)測到節(jié)點(diǎn)5和網(wǎng)絡(luò)存在不一致性,迅速將控制消息發(fā)送間隔調(diào)至最小值以迅速修復(fù)網(wǎng)絡(luò)。
圖2ContikiRPL在Cooja模擬器中的仿真
圖3細(xì)流算法對(duì)DIO消息發(fā)送頻率的控制
1.3環(huán)路避免機(jī)制
RPL中規(guī)定,在沿著葉節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上,節(jié)點(diǎn)級(jí)別必須是遞減的[1],即父節(jié)點(diǎn)的級(jí)別必須小于子節(jié)點(diǎn)的級(jí)別。當(dāng)節(jié)點(diǎn)在網(wǎng)絡(luò)中位置發(fā)生改變時(shí),必須根據(jù)父節(jié)點(diǎn)重新計(jì)算自己的級(jí)別。假設(shè)節(jié)點(diǎn)N的最優(yōu)父節(jié)點(diǎn)為P,P的級(jí)別為R(P),那么N的級(jí)別R(N)計(jì)算公式為:
R(N)=R(P)+rank_increase
rank_increase為子節(jié)點(diǎn)和父節(jié)點(diǎn)級(jí)別的差值,其算法在OF中有定義。
節(jié)點(diǎn)的級(jí)別在環(huán)路避免中有著重要的意義。RPL協(xié)議也通過在包頭上設(shè)定標(biāo)志位來附帶路由控制數(shù)據(jù),以避免數(shù)據(jù)包被循環(huán)轉(zhuǎn)發(fā)。
2考慮節(jié)點(diǎn)剩余能量的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ù)需求靈活定義。比如對(duì)鏈路可靠性要求較高的應(yīng)用,可將鏈路質(zhì)量作為路由選擇的首要考慮標(biāo)準(zhǔn);而對(duì)能量受限的環(huán)境則可以定義在路徑中盡量避開電池供電節(jié)點(diǎn)。在文檔RFC6551図中,提出了多種可供開發(fā)者參考的路由度量。
在選擇路徑時(shí),若只考慮跳數(shù)因素,必然會(huì)導(dǎo)致Sink周邊節(jié)點(diǎn)數(shù)據(jù)壓力過大,從而使關(guān)鍵節(jié)點(diǎn)能量過早消耗而死亡。文獻(xiàn)[10]將網(wǎng)絡(luò)的生命長度定義為第一個(gè)節(jié)點(diǎn)死亡的時(shí)間。對(duì)于能量受限的低功耗有損網(wǎng)絡(luò),如何平衡能量消耗,延長網(wǎng)絡(luò)整體壽命,是協(xié)議要考慮的重要因素。
2.2優(yōu)化之后的RPL路由方案
目前已有多種針對(duì)無線傳感網(wǎng)絡(luò)能量優(yōu)化的路由協(xié)議,比如分級(jí)能量路由協(xié)議LEACH和TEEN,以數(shù)據(jù)為中心的能量有效路由協(xié)議DD和SPIN,還有基于地理位置的路由協(xié)議GPSR和GEAR等[11]。但這些協(xié)議都很難實(shí)現(xiàn)和RPL協(xié)議的融合。RPL協(xié)議是通過在containermetric中,定義路徑選擇時(shí)所考慮的參數(shù),然后再以一定的方式將所需要考慮的參數(shù)相結(jié)合,從而確定一個(gè)合理的路徑選擇方案。
本篇論文中采取的是跳數(shù)(HC)和節(jié)點(diǎn)能量(EN)相結(jié)合的方式。結(jié)合方式有兩種[12],一種是Lex,一種是Add。Lex是指優(yōu)先考慮跳數(shù),只有在跳數(shù)相同的情況下,才考慮節(jié)點(diǎn)能量;而Add則是采取兩種參數(shù)綜合考慮的方式,按照一定的比例相結(jié)合,即:
本文對(duì)這兩種不同的結(jié)合方式做了仿真對(duì)比。
2.3RPL協(xié)議改進(jìn)前后的仿真對(duì)比
仿真工具采用的是美國UIUC大學(xué)開發(fā)的針對(duì)無線傳感網(wǎng)絡(luò)研究的J-Sim平臺(tái),該平臺(tái)基于Java語言,和NS2相比具有內(nèi)存消耗小、仿真速度快、有更好的可擴(kuò)展性等優(yōu)點(diǎn)。本文仿真了傳感網(wǎng)絡(luò)數(shù)據(jù)收集的場景。在100X100的區(qū)域里,規(guī)則的布置有100個(gè)節(jié)點(diǎn),圖4所示是網(wǎng)絡(luò)節(jié)點(diǎn)布局圖和OF0的拓?fù)浣Y(jié)構(gòu),其中最左上側(cè)的0號(hào)節(jié)點(diǎn)為數(shù)據(jù)匯聚節(jié)點(diǎn),右下側(cè)的49-99和94-98這11個(gè)節(jié)點(diǎn)為傳感器數(shù)據(jù)采集節(jié)點(diǎn)。數(shù)據(jù)從右下側(cè)的11個(gè)源節(jié)點(diǎn)發(fā)送到左上側(cè)的0號(hào)節(jié)點(diǎn)。由于該網(wǎng)絡(luò)具有對(duì)稱性,1和10對(duì)稱,2和20對(duì)稱等,對(duì)稱節(jié)點(diǎn)的能量消耗基本一致。本文中重點(diǎn)仿真了具有代表性的1、2、11、12、22這幾個(gè)關(guān)鍵節(jié)點(diǎn)的能量消耗情況。
圖4網(wǎng)絡(luò)節(jié)點(diǎn)布局圖和OF0的拓?fù)浣Y(jié)構(gòu)
對(duì)于OF0,由于跳數(shù)是路徑選擇的唯一標(biāo)準(zhǔn),節(jié)點(diǎn)位置固定的網(wǎng)絡(luò),其拓?fù)浣Y(jié)構(gòu)也相對(duì)保持不變。圖4即為這種情況下的拓?fù)浣Y(jié)構(gòu)。由圖4中可以看到,節(jié)點(diǎn)1和節(jié)點(diǎn)10承載了大部分的數(shù)據(jù)量,幾乎任何從下側(cè)或者右側(cè)源節(jié)點(diǎn)發(fā)過來的數(shù)據(jù)都要經(jīng)過這兩個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)到Sink節(jié)點(diǎn)。而節(jié)點(diǎn)11,貝貝有來自源節(jié)點(diǎn)99的數(shù)據(jù)由它轉(zhuǎn)發(fā)。
圖5所示是系統(tǒng)節(jié)點(diǎn)能耗圖。其中圖5(a)為OF0方案下部分節(jié)點(diǎn)能量消耗圖。從圖中可以看出,最關(guān)鍵的節(jié)點(diǎn)1和節(jié)點(diǎn)10,能量很快就消耗殆盡。而節(jié)點(diǎn)11,則能耗相對(duì)較少。這對(duì)節(jié)點(diǎn)位置固定的網(wǎng)絡(luò)是很不利的,會(huì)使數(shù)據(jù)量較大的節(jié)點(diǎn)在短期內(nèi)能量迅速消耗完而死亡,而其他非位置關(guān)鍵節(jié)點(diǎn),則一直被閑置。造成網(wǎng)絡(luò)能耗分布極其不均勻,能量利用率不咼。
接下來可以仿真跳數(shù)和節(jié)點(diǎn)剩余能量相結(jié)合的路徑選擇方式,圖5(b)為跳數(shù)和能量按照2:8的比例加權(quán)所得到的能耗結(jié)果。從圖5(b)可以看出,節(jié)點(diǎn)1、10和11的能耗更為均衡,第一個(gè)節(jié)點(diǎn)死亡的時(shí)間大為延長。跳數(shù)和節(jié)點(diǎn)剩余能量相結(jié)合的路徑選擇方式,能一定程度上改善以跳數(shù)為唯一度量所造成了能量消耗不均的情況,從而延長關(guān)鍵節(jié)點(diǎn)的生命長度。仿真中也能看到,最佳路徑的拓?fù)鋱D一直處于動(dòng)態(tài)變化,原先經(jīng)過節(jié)點(diǎn)1和節(jié)點(diǎn)10到達(dá)匯聚節(jié)點(diǎn)的數(shù)據(jù),有一部分從節(jié)點(diǎn)11分流,從而緩解節(jié)點(diǎn)1和節(jié)點(diǎn)10的壓力。
本文也仿真了跳數(shù)(HC)和節(jié)點(diǎn)能量(EN)按照Lex的結(jié)合方式,即優(yōu)先考慮最小跳數(shù),當(dāng)跳數(shù)相同的時(shí)候再考慮節(jié)點(diǎn)能量,以及在Add結(jié)合方式下按0.8HC+0.2EN和0.2HC+0.8EN的不同比例相結(jié)合的情況對(duì)比。最后得出的結(jié)論是,兩種不同的結(jié)合方式對(duì)網(wǎng)絡(luò)能耗均衡都有一定程度的改善;而Add的結(jié)合方式能耗更為均衡,且剩余能量所占的比例越高,改善的效果越為顯著。圖6所示是在不同路由策略下,關(guān)鍵節(jié)點(diǎn)能耗的對(duì)比情況。
本文描述了RPL協(xié)議的基本原理,并且對(duì)原路由協(xié)議的路徑選擇策略進(jìn)行了改進(jìn),在只考慮跳數(shù)的基礎(chǔ)上,加入節(jié)點(diǎn)剩余能量的考慮,從而平衡了網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)整體壽命。由于RPL是近幾年新提出的協(xié)議,隨著實(shí)踐的不斷深入,越來越多的新問題被提出,還有很大的研究空間。RPL協(xié)議在物聯(lián)網(wǎng)領(lǐng)域有著廣闊的應(yīng)用前景,值得廣大學(xué)者進(jìn)一步深入研究。
5致謝
本論文的工作得到了實(shí)驗(yàn)室項(xiàng)目的大力支持。感謝國家自然科學(xué)基金(61271257),北京市自然科學(xué)基金(4122034)和教育部博士點(diǎn)基金(20120005110007)對(duì)本文研究工作的支持。
20211118_6196307d10800__無線傳感網(wǎng)絡(luò)中的RPL路由協(xié)議研究