LLN中基于移動(dòng)節(jié)點(diǎn)鄰居探測(cè)的高效路由尋路算法

姚玉坤, 何 亮, 任 智, 李維政, 周佳琦

(1.重慶郵電大學(xué)通信與信息工程學(xué)院, 重慶 400065;2.重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室, 重慶 400065)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)是由大量自身內(nèi)存、處理能力、電池能量等資源受限的無線傳感器設(shè)備以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò),不僅能夠滿足特定情況下的網(wǎng)絡(luò)需求而且成本較低。其目的是協(xié)作地采集、感知和處理網(wǎng)絡(luò)覆蓋范圍內(nèi)其他節(jié)點(diǎn)的信息。但傳統(tǒng)的無線自組織網(wǎng)絡(luò)路由協(xié)議如按需平面距離向量路由協(xié)議[1]和最優(yōu)鏈路狀態(tài)路由協(xié)議[2]的能量消耗較大,均不能有效應(yīng)用于低功耗有損網(wǎng)絡(luò)(low power lossy networks,LLN)。為了克服上述問題,國際互聯(lián)網(wǎng)工程任務(wù)組在2012年提出一種基于IPV6的LLN路由協(xié)議(routing protocol for LLN,RPL)[3-5]。

標(biāo)準(zhǔn)RPL是一種支持點(diǎn)到點(diǎn)、點(diǎn)到多點(diǎn)和多點(diǎn)到點(diǎn)的網(wǎng)絡(luò)拓?fù)錇闃湫蔚穆酚蓞f(xié)議。其廣泛應(yīng)用于醫(yī)療護(hù)理[6]、環(huán)境監(jiān)測(cè)[7]和農(nóng)業(yè)領(lǐng)域。然而標(biāo)準(zhǔn)RPL并不適用無線傳感器這種具有移動(dòng)性的場(chǎng)景。

無線傳感器具有移動(dòng)性場(chǎng)景，按不同移速分為3類:一般來說,移動(dòng)速度處于正常人類行走速度即0.5～2 m/s屬于低速場(chǎng)景。移動(dòng)速度處于2～10 m/s屬于中速場(chǎng)景。移動(dòng)速度大于10 m/s屬于高速場(chǎng)景。例如,低速場(chǎng)景下的礦井工人的健康狀況監(jiān)控[8]、中速場(chǎng)景下的無人機(jī)野外信息采集、高速場(chǎng)景下的移動(dòng)車輛間信息交互[9]。在各種不同移速的場(chǎng)景下,移動(dòng)傳感器與其他靜態(tài)傳感器之間的通信鏈路的切換次數(shù)增多,移動(dòng)傳感器的能量消耗增大,丟包率增加。這些問題逐漸成為了近年來的研究熱點(diǎn)[10-12]。但現(xiàn)有國內(nèi)外大多文獻(xiàn)均在低速場(chǎng)景下對(duì)RPL進(jìn)行增強(qiáng)性研究。這些文獻(xiàn)提出的算法均不能很好的適用于中速或高速場(chǎng)景下。

文獻(xiàn)[13]提出一種支持RPL中節(jié)點(diǎn)隨機(jī)遷移的移動(dòng)感知節(jié)能父節(jié)點(diǎn)選擇算法。該算法結(jié)合多種路由度量選擇下一個(gè)父節(jié)點(diǎn)(next parent node,NPN),但在選擇NPN時(shí)并未考慮到節(jié)點(diǎn)剩余能量。文獻(xiàn)[14]提出一種在LLN中靜態(tài)節(jié)點(diǎn)(static node,SN)和移動(dòng)節(jié)點(diǎn)(mobile node,MN)使用多種路由度量來選擇NPN。但該算法端到端時(shí)延較大,影響了協(xié)議的性能。文獻(xiàn)[15]提出一種增強(qiáng)物聯(lián)網(wǎng)移動(dòng)性(boosting mobility in the internet of things,MRPL)的協(xié)議。該協(xié)議通過MN周期性接收控制消息計(jì)算出接收信號(hào)強(qiáng)度指標(biāo)(indicator of received signal strength,RSSI),依靠自身處理移動(dòng)性帶來的問題。但會(huì)消耗大量MN的能量。文獻(xiàn)[16]提出依靠父節(jié)點(diǎn)為MN進(jìn)行移動(dòng)檢測(cè)。MN根據(jù)預(yù)期傳輸數(shù)、RSSI、剩余能量等指標(biāo)選擇新的父節(jié)點(diǎn),但在移動(dòng)速度過快時(shí)仍需依靠MN主動(dòng)廣播面向目的地有向無循環(huán)圖請(qǐng)求消息(destination oriented directed acyclic graph information solicitation，DIS)去尋找NPN。文獻(xiàn)[17]提出一種使用跳數(shù)度量來減少傳遞的控制消息的數(shù)量。MN在選擇父節(jié)點(diǎn)時(shí),還使用跳數(shù)選擇一個(gè)可以與之保持較長時(shí)間連接的父節(jié)點(diǎn),這將增加網(wǎng)絡(luò)的穩(wěn)定性。但當(dāng)有多個(gè)MN連接到同一父節(jié)點(diǎn)時(shí),將加劇父節(jié)點(diǎn)的能量消耗。文獻(xiàn)[18]提出一種物聯(lián)網(wǎng)中的能量和移動(dòng)性感知路由協(xié)議(energy and mobility aware routing for the internet of mobile things,EMA-RPL),其是一種將移動(dòng)性處理過程委托給其父節(jié)點(diǎn)的協(xié)議。減少了MN的能源消耗,并提供了切換父節(jié)點(diǎn)時(shí)的無縫連接。但中速場(chǎng)景下存在尋路不及時(shí)和路由度量單一的問題。文獻(xiàn)[19]提出基于葉子節(jié)點(diǎn)計(jì)數(shù)和RSSI的父節(jié)點(diǎn)預(yù)測(cè)算法。該算法能夠有效均衡網(wǎng)絡(luò)負(fù)載和減少M(fèi)N的能耗,但仍存在路由度量單一的問題。文獻(xiàn)[20]提出一種基于鄰居變異性的跨層移動(dòng)性支持算法,該算法通過MN監(jiān)聽鄰居節(jié)點(diǎn)的RSSI去測(cè)量節(jié)點(diǎn)的可變性鄰域,實(shí)現(xiàn)了MN切換父節(jié)點(diǎn)的無縫連接,但MN能耗較大,縮短了MN的網(wǎng)絡(luò)壽命。

通過對(duì)以上協(xié)議的研究與分析,現(xiàn)有文獻(xiàn)的仿真場(chǎng)景均未考慮到無線傳感器節(jié)點(diǎn)之間存在障礙物的情況,且在中速場(chǎng)景下均存在MN尋路不及時(shí)、能耗較大和路由度量單一等問題。由此,本文提出LLN中基于移動(dòng)節(jié)點(diǎn)鄰居探測(cè)的高效路由尋路算法。該算法通過基于障礙物的信道傳輸模型計(jì)算出安全閾值(safe threshold,ST)和危險(xiǎn)閾值(risk threshold,RT),使得MN可以提前尋路,有效提高了MN的數(shù)據(jù)傳輸成功率。同時(shí)提出基于變異系數(shù)的父本選擇目標(biāo)函數(shù)和基于鄰居節(jié)點(diǎn)的監(jiān)聽預(yù)選機(jī)制,減少了MN切換父節(jié)點(diǎn)的次數(shù)和能量消耗。

1 網(wǎng)絡(luò)模型

如圖1所示,所有無線傳感器節(jié)點(diǎn)部署在一個(gè)云形監(jiān)測(cè)區(qū)域內(nèi)。MN將采集的信息通過父節(jié)點(diǎn)向上傳輸,最終匯聚到根節(jié)點(diǎn)。在LLN網(wǎng)絡(luò)中,部署一個(gè)根節(jié)點(diǎn),多個(gè)SN、MN隨機(jī)移動(dòng),但始終在部署的SN的附近。

圖1 網(wǎng)絡(luò)模型

(1)根節(jié)點(diǎn):根節(jié)點(diǎn)可以被認(rèn)為是中央處理器,處理從各個(gè)節(jié)點(diǎn)發(fā)送回來的數(shù)據(jù)。可以認(rèn)為該節(jié)點(diǎn)的能量可以得到及時(shí)補(bǔ)充。而SN和MN的能量均不能補(bǔ)充,由電池提供能量。

(2)MN:由于MN的隨機(jī)移動(dòng)性且該節(jié)點(diǎn)能量有限,必須在保證數(shù)據(jù)傳輸?shù)耐瑫r(shí),盡可能減少該節(jié)點(diǎn)的能量消耗。因此,在本文的算法中,MN只能是葉子節(jié)點(diǎn)。即不能作為任何類型節(jié)點(diǎn)的父節(jié)點(diǎn)來中繼數(shù)據(jù),只能向上傳輸采集的數(shù)據(jù)。MN作為葉子節(jié)點(diǎn)的另一個(gè)好處是避免MN切換父節(jié)點(diǎn)導(dǎo)致的路由變化,確保路由穩(wěn)定性。

(3)SN:SN的主要任務(wù)是采集和處理周圍可感知對(duì)象的信息,并中繼MN采集的數(shù)據(jù),以上傳到根節(jié)點(diǎn)。因此,有些靜態(tài)節(jié)點(diǎn)SN可能會(huì)成為MN的當(dāng)前父節(jié)點(diǎn)(current parent node,CPN)。

(4)每一個(gè)SN都有一個(gè)RSSI閾值。該閾值等于后文提到的RT。用于判斷MN是否還能正常傳輸數(shù)據(jù)。在網(wǎng)絡(luò)模型中,除根節(jié)點(diǎn)以外的所有無線傳感器節(jié)點(diǎn)具有相同的性能和參數(shù)配置。

2 NDM-RPL算法

在現(xiàn)有文獻(xiàn)對(duì)RPL移動(dòng)性支持研究的基礎(chǔ)上,本文提出了NDM-RPL路由算法,該算法的創(chuàng)新點(diǎn)如下。

(1)提出基于障礙物的鏈路質(zhì)量檢測(cè)機(jī)制。該機(jī)制通過基于障礙物的信道傳輸模型為靜態(tài)節(jié)點(diǎn)SN計(jì)算出安全閾值ST和危險(xiǎn)閾值RT。當(dāng)RSSI值小于ST時(shí),MN便可以提前開始尋路；當(dāng)RSSI小于RT時(shí),MN會(huì)停止發(fā)送數(shù)據(jù)，降低了MN的丟包率。

(2)針對(duì)移動(dòng)節(jié)點(diǎn)提出一種基于變異系數(shù)的父本選擇目標(biāo)函數(shù)。NDM-RPL協(xié)議中MN選擇NPN綜合考慮了備選CPN的網(wǎng)絡(luò)深度、當(dāng)前連接的子節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)剩余能量和與移動(dòng)性相關(guān)的變異系數(shù),能夠有效均衡網(wǎng)絡(luò)負(fù)載和保證移動(dòng)節(jié)點(diǎn)網(wǎng)絡(luò)連接穩(wěn)定性。

(3)提出基于鄰居節(jié)點(diǎn)的監(jiān)聽預(yù)選機(jī)制。MN的鄰居節(jié)點(diǎn)會(huì)監(jiān)聽MN發(fā)向其CPN的數(shù)據(jù)包并測(cè)得RSSI。通過RSSI平均值大小判斷是否遠(yuǎn)離MN。如果靠近,則會(huì)根據(jù)基于變異系數(shù)的父本選擇目標(biāo)函數(shù)計(jì)算出綜合路由度量值(rank值)并向MN或其CPN回復(fù)一個(gè)帶有rank值的DIS消息。解決了備選CPN集冗余的問題,并減少了MN的控制開銷。

2.1 基于障礙物的鏈路質(zhì)量檢測(cè)機(jī)制

為了解決中速場(chǎng)景下MN移動(dòng)速度過快導(dǎo)致切換CPN不及時(shí)和存在障礙物時(shí)信號(hào)衰減增大的問題,本文提出為無線傳感器節(jié)點(diǎn)預(yù)設(shè)兩個(gè)通信閾值,即ST和RT。為了得到合理的通信閾值,必須考慮包接收率與接收信號(hào)強(qiáng)度RSSI的關(guān)系。該算法使用基于障礙物的信道傳輸模型[21]如式(1)所示來計(jì)算得到合理的ST和RT。

(1)

式中：PR為接收信號(hào)強(qiáng)度，即RSSI值;PT為發(fā)射功率。A為1 m處接收信號(hào)強(qiáng)度;n為路徑損耗指數(shù)因子;dw為無障礙物時(shí)通信距離;dm為有障礙物通信距離;S為經(jīng)驗(yàn)指數(shù);C為與頻率、通信距離相關(guān)的指數(shù)。

為了便于計(jì)算ST和RT，定義Dw表示無障礙物時(shí)無線傳感器節(jié)點(diǎn)的最大通信半徑，Dm表示有障礙物時(shí)無線傳感器節(jié)點(diǎn)的最大通信半徑。

假如無線傳感器有無障礙物的最大通信半徑是已知的。為了降低數(shù)據(jù)包丟失的概率，當(dāng)信號(hào)發(fā)射端與信號(hào)接收端之間存在障礙物時(shí)，利用式(1)求出dm=Dm時(shí)的PR作為危險(xiǎn)閾值。同時(shí)令dw=Dm代入式(1)求出PR作為安全閾值。

如圖2所示，假設(shè)lac屬于有障礙物的最大通信距離，lab屬于無障礙物通信距離，且lac=lab。c點(diǎn)處的RSSI即為危險(xiǎn)閾值。b點(diǎn)處的RSSI即為安全閾值ST。b、c兩點(diǎn)處的RSSI值之差即為由障礙物導(dǎo)致的信號(hào)衰減值。有障礙物的信號(hào)衰減比無障礙物的信號(hào)衰減強(qiáng)。由障礙物導(dǎo)致的信號(hào)衰減越強(qiáng)，安全閾值越大,MN便能及時(shí)開始尋找NPN。

圖2 鏈路質(zhì)量區(qū)分示意圖

以圖3為例,在T1時(shí)刻,MN在當(dāng)前父節(jié)點(diǎn)CPN的安全閾值ST內(nèi),意味著MN與CPN之間有很好的鏈路質(zhì)量,可以進(jìn)行可靠通信。在T2時(shí)刻,當(dāng)CPN檢測(cè)到MN處于安全閾值和危險(xiǎn)閾值之間,兩者仍然可以進(jìn)行較為可靠的通信。但MN的移動(dòng)帶來了不確定性,MN可能快要移出CPN的可靠通信范圍。

圖3 MN的鏈路質(zhì)量檢測(cè)

基于障礙物的鏈路質(zhì)量檢測(cè)機(jī)制具體過程如下。

步驟 1CPN通過從MN接收數(shù)據(jù)包測(cè)得RSSI值,每測(cè)得一個(gè)RSSI值就和ST比較大小。若ST>RSSI,則進(jìn)入步驟2。反之,繼續(xù)執(zhí)行步驟1。

步驟 2CPN立即單播給MN一個(gè)Flag為4的DIS消息,讓MN提前開始尋找NPN,然后執(zhí)行步驟3。

步驟 3CPN繼續(xù)從MN接收數(shù)據(jù)包測(cè)得RSSI值每測(cè)得一個(gè)RSSI值就和RT比較大小。若RT>RSSI,執(zhí)行步驟4。若RT

步驟 4CPN立即廣播一次Flag字段為3的DIS控制消息告訴MN停止發(fā)送數(shù)據(jù)包,直到MN建立了與NPN的連接。由于MN已經(jīng)處于危險(xiǎn)閾值之外,為了保證MN能夠接收到該DIS消息,CPN的鄰居節(jié)點(diǎn)在接收到該消息后會(huì)檢查自己鄰居表內(nèi)是否有MN的地址,如果有,則轉(zhuǎn)發(fā)該DIS消息。如果沒有,則丟棄該消息。

2.2 基于變異系數(shù)的父本選擇目標(biāo)函數(shù)

現(xiàn)有大多文獻(xiàn)對(duì)MN選擇NPN時(shí)僅依靠RSSI平均值或方差作為度量，并不能準(zhǔn)確反映MN對(duì)于備選父節(jié)點(diǎn)的通信質(zhì)量,且沒有考慮到SN因?yàn)檫B接過多子節(jié)點(diǎn)而出現(xiàn)網(wǎng)絡(luò)擁塞和能量急劇消耗的情況。NDM-RPL協(xié)議中MN選擇新的NPN綜合考慮了與移動(dòng)性相關(guān)的變異系數(shù)Cv、節(jié)點(diǎn)剩余能量、備選父節(jié)點(diǎn)的網(wǎng)絡(luò)深度和當(dāng)前連接的子節(jié)點(diǎn)數(shù)?；谧儺愊禂?shù)的父本選擇目標(biāo)函數(shù)如下所示:

(2)

式中:rank為綜合路由度量值;α、β、γ為權(quán)重因子且0<α<β<γ<1;M為每個(gè)SN能夠連接的最大子節(jié)點(diǎn)數(shù);H為當(dāng)前節(jié)點(diǎn)傳輸數(shù)據(jù)到根節(jié)點(diǎn)所需的跳數(shù),即網(wǎng)絡(luò)深度;CN為當(dāng)前節(jié)點(diǎn)連接的子節(jié)點(diǎn)數(shù)。

(1)變異系數(shù)：變異系數(shù)Cv是一種結(jié)合了ΔRi的標(biāo)準(zhǔn)差和平均值的性能指標(biāo)，反映了不同SN對(duì)MN的信號(hào)強(qiáng)度變化趨勢(shì)穩(wěn)定性的關(guān)系。Cv越小，表明該SN對(duì)于MN表現(xiàn)出更好的穩(wěn)定性，MN能與之保持更長時(shí)間的連接。一定程度上減少了由于移動(dòng)帶來的頻繁切換父節(jié)點(diǎn)的次數(shù)，也減少了MN的能耗。Cv與ΔRi的計(jì)算由下式得出。

(3)

ΔRi=|RSSIi,t-RSSIi+1,t+1|,i

(4)

式中:ΔRi表示SN在監(jiān)聽預(yù)選階段中連續(xù)時(shí)間[t,t+1]內(nèi)的兩個(gè)RSSI值的差的絕對(duì)值;RSSIi表示第i次測(cè)得的RSSI值。n表示測(cè)得的RSSI總個(gè)數(shù)。

以圖4為例，假設(shè)MN的鄰居節(jié)點(diǎn)a、b、c連續(xù)監(jiān)聽到的6次RSSI絕對(duì)值。節(jié)點(diǎn)a監(jiān)聽的|RSSI|是91，95，92，95，91，94。節(jié)點(diǎn)b監(jiān)聽到的|RSSI|是42，31，41，32，42，31。節(jié)點(diǎn)c監(jiān)聽到的|RSSI|是4，10，18，22，28，37。若按RSSI平均值最大原則選擇NPN，易知節(jié)點(diǎn)c的RSSI平均值最大，但節(jié)點(diǎn)c的RSSI值變化趨勢(shì)很不穩(wěn)定，不適合被預(yù)選為MN的NPN。若按RSSI方差最小原則選擇NPN，易知節(jié)點(diǎn)a的方差最小，但節(jié)點(diǎn)a的RSSI值太小，通信鏈路質(zhì)量較差，也不適合被預(yù)選為MN的NPN。由式(3)和式(4)計(jì)算可得到節(jié)點(diǎn)a、b、c的變異系數(shù)分別為22.32、20.44、60.28?？芍猙的變異系數(shù)最小，所以節(jié)點(diǎn)b更適合作為MN的NPN。求ΔR的標(biāo)準(zhǔn)差而不是直接求RSSI值的標(biāo)準(zhǔn)差的原因是使用ΔR能得到比使用RSSI更小的標(biāo)準(zhǔn)差使其計(jì)算的rank值更小，同時(shí)能正確的反映RSSI值波動(dòng)幅度大小的穩(wěn)定性，在節(jié)點(diǎn)a、b、c的rank值比較中，b才易被選為NPN。

圖4 節(jié)點(diǎn)a、b、c連續(xù)監(jiān)聽到的RSSI

(2)節(jié)點(diǎn)剩余能量:在LLN中,如何均衡能量消耗一直是一個(gè)備受關(guān)注的問題。因?yàn)闊o線傳感器依靠電池運(yùn)行,當(dāng)電量耗盡,設(shè)備就會(huì)停止工作。如果不考慮剩余電量,很可能導(dǎo)致一個(gè)設(shè)備的電量被迅速耗盡。為了克服這個(gè)問題,在選擇父節(jié)點(diǎn)時(shí),考慮節(jié)點(diǎn)的剩余能量是至關(guān)重要的。剩余能量按下式計(jì)算:

Erest=Etotal-Econsume

(5)

式中：Erest為剩余的能量；Etotal為節(jié)點(diǎn)總能量,其是消耗的總能量。這里的Econsume由下式計(jì)算得出[22]:

(6)

式中：V為無線傳感器的供電電壓；Iap、Ilp、Itx、Irx和Ini分別為微控制器處于正常運(yùn)行、低功耗、發(fā)送、接收狀態(tài)和傳感器處于工作狀態(tài)的電流；Tap、Tlp、Ttx、Trx和Tni分別為上述5種狀態(tài)下的運(yùn)行時(shí)間。

(3)備選父節(jié)點(diǎn)的網(wǎng)絡(luò)深度H和當(dāng)前已連接的子節(jié)點(diǎn)數(shù)(CN:MN)在選擇NPN的過程中考慮其備選父節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目能夠有效避免連接子節(jié)點(diǎn)數(shù)過多的節(jié)點(diǎn),一定程度上均衡網(wǎng)絡(luò)中SN的負(fù)載。避免SN因?yàn)檫B接過多子節(jié)點(diǎn)而出現(xiàn)網(wǎng)絡(luò)擁塞和能量急劇消耗的情況。

M減去CN表示當(dāng)前可連接的子節(jié)點(diǎn)數(shù),從式(2)可以看到當(dāng)多個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)深度H相等時(shí),M-CN越大,rank值越小。而當(dāng)多個(gè)節(jié)點(diǎn)的當(dāng)前可連接的子節(jié)點(diǎn)數(shù)相等時(shí),H越小,rank值越小。而rank值越小,越容易被預(yù)選為MN的NPN。

2.3 基于鄰居節(jié)點(diǎn)的監(jiān)聽預(yù)選機(jī)制

為了解決備選父節(jié)點(diǎn)集選取不合理和減少M(fèi)N的能耗,提出一種基于鄰居節(jié)點(diǎn)的監(jiān)聽預(yù)選機(jī)制。在MN處于CPN的ST和RT之間時(shí),MN會(huì)廣播帶有MN_ID的DIS消息。MN_ID的作用是為了區(qū)分整個(gè)網(wǎng)絡(luò)中不同的MN。

由于MN的能量有限,如何合理節(jié)省其能耗是一個(gè)亟待解決的問題。為此,在根節(jié)點(diǎn)廣播DIO消息構(gòu)建網(wǎng)絡(luò)拓?fù)鋾r(shí),每一個(gè)SN都會(huì)通過監(jiān)聽的DIO消息和DIS消息維護(hù)一個(gè)鄰居表,該表存放了鄰居節(jié)點(diǎn)的地址信息。該設(shè)置的目的是當(dāng)MN的周圍存在大量SN時(shí),CPN能夠幫助MN處理一部分?jǐn)?shù)據(jù)以此減少M(fèi)N的能耗。

基于鄰居節(jié)點(diǎn)的監(jiān)聽預(yù)選機(jī)制具體過程如下。

步驟 1當(dāng)MN已經(jīng)處于CPN的安全閾值ST和危險(xiǎn)閾值RT之間時(shí),MN會(huì)收到來自CPN的DIS控制消息。此時(shí),MN會(huì)廣播DIS(MN_ID)控制消息,其鄰居節(jié)點(diǎn)收到該消息后分別設(shè)置一個(gè)包監(jiān)聽定時(shí)器,開始監(jiān)聽MN向CPN發(fā)送的數(shù)據(jù)包,測(cè)得并緩存RSSI值。執(zhí)行步驟2。

步驟 3鄰居節(jié)點(diǎn)依據(jù)式(2)計(jì)算出rank值并查找鄰居表中是否存在該MN的CPN。如果存在,則單播給MN的CPN一個(gè)攜帶rank值的DIS消息。如果不存在,則直接單播給MN。CPN收到多個(gè)該消息后,比較得到最小rank值和該值發(fā)送者的地址,使用DIS控制消息單播給MN。執(zhí)行步驟4。

步驟 4MN收到來自CPN和鄰居節(jié)點(diǎn)DIS控制消息后,比較得到最小rank值,選取rank值最小的節(jié)點(diǎn)作為NPN。MN向NPN單播一個(gè)普通的DIS控制消息申請(qǐng)入網(wǎng)。執(zhí)行步驟5。

步驟 5預(yù)選的NPN收到來自MN的普通DIS控制消息,會(huì)單播一個(gè)普通DIO控制消息給MN,建立與MN的連接。如果此時(shí)的MN還在和CPN進(jìn)行數(shù)據(jù)傳輸,則MN在建立與預(yù)選的NPN的連接之后,再斷開與CPN的連接。以減少數(shù)據(jù)包的丟失。

2.4 控制消息幀格式的修改

為了更好實(shí)現(xiàn)本文提出的協(xié)議并保持與RPL標(biāo)準(zhǔn)協(xié)議的兼容性,同時(shí)節(jié)省MN切換父節(jié)點(diǎn)帶來的控制開銷,在DIS控制消息中修改一些字段,Flag字段占3bit,MN_ID占12 bit,rank占8 bit,如圖5所示。

圖5 修改后的DIS幀格式

對(duì)于DIS消息來說,Flag=0代表它是一個(gè)簡(jiǎn)單的請(qǐng)求入網(wǎng)消息。Flag=1代表SN單播帶有rank值的DIS消息給MN或MN的CPN。Flag=2時(shí)是MN廣播一個(gè)攜帶MN_ID值的DIS消息給它的鄰居節(jié)點(diǎn)。Flag=3時(shí)是CPN通知MN停止發(fā)送數(shù)據(jù)。Flag=4時(shí)是CPN發(fā)送給MN的DIS消息。

NDM-RPL算法流程圖如圖6所示。

圖6 NDM-RPL算法流程圖

3 NDM-RPL算法性能分析

假設(shè)網(wǎng)絡(luò)拓?fù)涑跏蓟?網(wǎng)絡(luò)運(yùn)行一段時(shí)間t后,此時(shí)存在P個(gè)MN需要切換父節(jié)點(diǎn)。對(duì)于第i個(gè)MN來說,t時(shí)刻其鄰居節(jié)點(diǎn)總數(shù)為Qi個(gè)且Qi≥1,平均RSSI大于ST的鄰居節(jié)點(diǎn)總數(shù)為Li個(gè)且Li≥1,其CPN的鄰居節(jié)點(diǎn)總數(shù)為Ki個(gè)。是MN而不是其CPN的鄰居節(jié)點(diǎn)且平均RSSI大于ST的鄰居節(jié)點(diǎn)總數(shù)為Hi,且0≤Hi≤Qi。

3.1 移動(dòng)節(jié)點(diǎn)尋路控制開銷

設(shè)CE、CM和CN分別是EMA-RPL、MRPL和NDM-RPL在t時(shí)刻需要切換CPN的所有移動(dòng)節(jié)點(diǎn)完成切換過程的總控制開銷,DIS、DIO、DAO、DAO-ACK消息的大小分別為lS、lI、lA、lK。故有

(7)

(8)

又有

(9)

因?yàn)閘I比lS大8 byte,且Qi+1>Hi,故CM>CN?？芍狽DM-RPL算法移動(dòng)節(jié)點(diǎn)尋路控制開銷明顯低于MRPL。

3.2 計(jì)算復(fù)雜度分析

EMA-RPL算法中,MN的備選CPN集依據(jù)其CPN的鄰居節(jié)點(diǎn)構(gòu)建,故總的計(jì)算次數(shù)等于所有MN備選CPN集大小之和,其計(jì)算次數(shù)表達(dá)式為

(10)

MRPL算法中,每個(gè)MN依據(jù)自身的鄰居節(jié)點(diǎn)構(gòu)建備選CPN集,故總的計(jì)算次數(shù)為

(11)

本文算法中,每個(gè)MN依據(jù)自己的鄰居節(jié)點(diǎn)構(gòu)建備選CPN集,且平均RSSI大于ST的鄰居節(jié)點(diǎn)才會(huì)加入備選CPN集。故總的計(jì)算次數(shù)表達(dá)式為

(12)

LLN網(wǎng)絡(luò)中,由于CPN為靜態(tài)節(jié)點(diǎn),具有較好的網(wǎng)絡(luò)穩(wěn)定性,其周圍存在的鄰居節(jié)點(diǎn)總數(shù)一般情況下大于等于MN的鄰居節(jié)點(diǎn)總數(shù),故Qi≤Ki,而LiR3。說明本文算法的計(jì)算復(fù)雜度一定低于EMA-RPL和MRPL。

4 仿真驗(yàn)證

本文使用Contiki的IPv6/6loWPAN平臺(tái)開源操作系統(tǒng)進(jìn)行網(wǎng)絡(luò)模型的搭建和仿真。Contiki里有被廣泛使用的RPL開源實(shí)現(xiàn)[23-24]。對(duì)參與移動(dòng)切換過程中的MN和SN的控制開銷、移動(dòng)節(jié)點(diǎn)能耗、網(wǎng)絡(luò)生存時(shí)間、數(shù)據(jù)傳輸成功率4個(gè)方面與MRPL、EMA-RPL進(jìn)行對(duì)比和分析。

4.1 仿真參數(shù)

在350 m×350 m的仿真場(chǎng)景中構(gòu)建網(wǎng)絡(luò)規(guī)模大小為SN(24)和MN(6),移動(dòng)節(jié)點(diǎn)MN隨機(jī)移動(dòng)。為了得到穩(wěn)定的仿真結(jié)果,每次仿真設(shè)置隨機(jī)種子值分別為128、256、528。對(duì)每個(gè)隨機(jī)種子值仿真重復(fù)10次,取平均值作為仿真結(jié)果。在多次仿真過程中,由于MRPL和EMA-RPL算法在節(jié)點(diǎn)移速超過4.5 m/s后,性能表現(xiàn)較差,其仿真結(jié)果參考性較低。為了更好地比較3種算法在不同速度下的性能,故仿真參數(shù)中節(jié)點(diǎn)移動(dòng)速度設(shè)置在2～4.5 m/s。參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

4.2 仿真結(jié)果及性能分析

4.2.1 控制開銷

控制開銷是指MN為尋找NPN發(fā)送或接收的控制消息(DIS,DIO,DAO,DAO-ACK)總比特?cái)?shù)。在圖7中,描繪了MN的移動(dòng)速度變化對(duì)控制開銷的影響。

圖7 控制開銷對(duì)比

隨著MN移動(dòng)速度的增加，MN需要多次使用控制消息切換當(dāng)前連接的CPN。故3種協(xié)議的控制開銷均隨著移動(dòng)速度的增加而上升，但NDM-RPL路由協(xié)議控制開銷明顯低于MRPL和EMA-RPL，而EMA-RPL路由協(xié)議的控制開銷又低于MRPL。NDM-RLP、EMA-RPL和MRPL的平均控制開銷分別為2.79×105bit、3.17×105bit和3.83×105bit。與EMA-RPL和MRPL兩種協(xié)議相比，NDM-RPL的控制開銷分別下降了11.99%和27.15%。這是由于MRPL是通過MN周期性的接收控制消息計(jì)算出RSSI值，同時(shí)負(fù)責(zé)檢測(cè)其移動(dòng)性并尋找NPN，該過程使MN花費(fèi)了較大的控制開銷。EMA-RPL雖然將移動(dòng)性處理過程交付給了MN的CPN來處理，一定程度上降低了MN的控制開銷，但在計(jì)算RSSI值時(shí)仍需MN廣播3次DIS消息。而NDM-RPL在計(jì)算RSSI值時(shí)通過MN的鄰居節(jié)點(diǎn)監(jiān)聽MN發(fā)向PN的數(shù)據(jù)包計(jì)算得到，避免通過發(fā)送控制消息來計(jì)算RSSI值，且修改了用于切換CPN的DIS控制消息幀格式，從而有效降低了MN為移動(dòng)性處理而使用的控制開銷。

4.2.2 移動(dòng)節(jié)點(diǎn)能耗

移動(dòng)節(jié)點(diǎn)能耗是指移動(dòng)節(jié)點(diǎn)MN在仿真時(shí)間內(nèi)消耗的總能量。Pap、Plp、Ptx、Prx和Pni分別為微控制器處于正常運(yùn)行、低功耗、發(fā)送、接收狀態(tài)和傳感器處于工作狀態(tài)的功率：Tap、Tlp、Ttx、Trx和Tni分別為上述5種狀態(tài)的運(yùn)行時(shí)間。故MN總能耗EMN的計(jì)算公式為

(13)

圖8描繪了MN的移動(dòng)速度變化對(duì)移動(dòng)節(jié)點(diǎn)能耗的影響。從仿真結(jié)果可知,隨著MN移動(dòng)速度的增加,3種協(xié)議下的MN均需要頻繁切換CPN,從而導(dǎo)致MN的能耗增加。但在不同移動(dòng)速度下NDM-RPL路由協(xié)議能耗均低于EMA-RPL和MRPL。NDM-RLP、EMA-RPL和MRPL的平均能量消耗為分別為53.67 mJ、58 mJ、61.55 mJ。與EMA-RPL和MRPL兩種協(xié)議相比,NDM-RPL的能量消耗分別下降了7.45%和12.8%。這是由于MRPL將尋找NPN的任務(wù)交給MN自身處理,該過程會(huì)使用發(fā)送和接收大量控制消息。因此,隨著移動(dòng)速度的增加,MN的能量將消耗非?？?。在EMA-RPL中,MN雖然不直接參與移動(dòng)性處理過程,但由于EMA-RPL開始尋找NPN的起始時(shí)間太晚,當(dāng)移動(dòng)速度處于2～4.5 m/s時(shí)容易導(dǎo)致MN不能在離開CPN通信范圍之前建立與NPN的連接,此時(shí)又需要MN主動(dòng)尋找NPN,此過程也會(huì)大量消耗MN的能量。而NDM-RPL通過鏈路質(zhì)量檢測(cè)機(jī)制和監(jiān)聽預(yù)選機(jī)制,使得MN并不直接參與NPN的尋找且能夠及時(shí)預(yù)選出NPN,從而降低了MN的能量消耗。

圖8 移動(dòng)節(jié)點(diǎn)能耗對(duì)比

4.2.3 網(wǎng)絡(luò)生存時(shí)間

網(wǎng)絡(luò)生存時(shí)間是指從仿真開始時(shí)間到出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)(能量低于節(jié)點(diǎn)初始能量的1%)之間的時(shí)間差。圖9描繪了MN的移動(dòng)速度對(duì)網(wǎng)絡(luò)生存時(shí)間的影響。

圖9 網(wǎng)絡(luò)生存時(shí)間對(duì)比

隨著MN移動(dòng)速度的增加,3種協(xié)議下MN的網(wǎng)絡(luò)生存時(shí)間逐漸降低。但相同速度下NDM-RPL網(wǎng)絡(luò)生存時(shí)間明顯高于其他兩種協(xié)議。NDM-RLP、EMA-RPL和MRPL的平均網(wǎng)絡(luò)生存時(shí)間分別為823.31 s、743.67 s、683.33 s。與EMA-RPL和MRPL兩種協(xié)議相比,NDM-RPL的網(wǎng)絡(luò)生存時(shí)間分別延長了10.76%和20.49%。分析其主要原因,在于EMA-RPL和MRPL在MN尋找NPN時(shí)均未考慮節(jié)點(diǎn)剩余能量和沒有限制靜態(tài)節(jié)點(diǎn)SN的可連接子節(jié)點(diǎn)數(shù)。特別是在整個(gè)網(wǎng)絡(luò)拓?fù)渲蠱N數(shù)量較多時(shí),易造成剩余能量較少的靜態(tài)節(jié)點(diǎn)SN過早死亡。NDM-RPL在MN尋找NPN的過程中使用了基于變異系數(shù)的父本選擇目標(biāo)函數(shù),不僅考慮了節(jié)點(diǎn)剩余能量,還限制了每個(gè)SN可連接的最大子節(jié)點(diǎn)數(shù),能夠最大化地均衡網(wǎng)絡(luò)負(fù)載,從而達(dá)到延長網(wǎng)絡(luò)生存時(shí)間的目的。

4.2.4 數(shù)據(jù)傳輸成功率

數(shù)據(jù)傳輸成功率P是指MN發(fā)送的數(shù)據(jù)包N和其CPN接收來自MN的數(shù)據(jù)包個(gè)數(shù)n之比,計(jì)算公式為

(14)

圖10描繪了MN的移動(dòng)速度變化對(duì)數(shù)據(jù)傳輸成功率的影響。從仿真結(jié)果可知,隨著移動(dòng)速度的增加,3種協(xié)議下的MN數(shù)據(jù)傳輸成功率均有所降低。但在移動(dòng)速度為2～4.5 m/s時(shí),NDM-RPL路由協(xié)議的MN數(shù)據(jù)傳輸成功率明顯高于MRPL。在移動(dòng)速度為2.5～4.5 m/s時(shí),NDM-RPL數(shù)據(jù)傳輸成功率明顯高于EMA-RPL。NDM-RLP、EMA-RPL和MRPL的平均數(shù)據(jù)傳輸成功率為分別為97.5%、92.01%、90.83%。與EMA-RPL和MRPL兩種協(xié)議相比,NDM-RPL的平均數(shù)據(jù)傳輸成功率分別提升了5.92%和7.34%。這是由于MRPL不能在切換CPN過程中保證自身與CPN的連接,從而導(dǎo)致了數(shù)據(jù)包丟失的可能。在EMA-RPL中,MN雖然能在切換CPN過程中保證自身與CPN的連接,但在移動(dòng)速度處于2～4.5 m/s時(shí),出現(xiàn)了未找到NPN就與CPN斷開連接的情況,這也會(huì)導(dǎo)致數(shù)據(jù)包的丟失。而NDM-RPL通過鏈路質(zhì)量檢測(cè)機(jī)制能夠及時(shí)讓MN發(fā)起預(yù)選NPN的通知。監(jiān)聽預(yù)選機(jī)制使得MN在移動(dòng)速度較快時(shí),也能尋找通信鏈路質(zhì)量較好且連接穩(wěn)定的靜態(tài)節(jié)點(diǎn)SN作為NPN并實(shí)現(xiàn)切換CPN的無縫連接,有效減少了丟包的數(shù)量。

圖10 數(shù)據(jù)傳輸成功率對(duì)比

5 結(jié)束語

本文針對(duì)當(dāng)前LLN中對(duì)RPL路由協(xié)議在中速場(chǎng)景下的移動(dòng)性研究存在移動(dòng)節(jié)點(diǎn)的CPN切換不及時(shí),備選CPN集冗余和路由度量單一的問題提出NDM-RPL路由協(xié)議。該協(xié)議通過為SN設(shè)置安全閾值ST和危險(xiǎn)閾值RT,以便移動(dòng)節(jié)點(diǎn)提前開始尋路。然后,提出一種監(jiān)聽預(yù)選機(jī)制,通過MN的鄰居節(jié)點(diǎn)監(jiān)聽該MN發(fā)送到CPN的數(shù)據(jù)包得到RSSI值,以此排除冗余的備選CPN,能夠有效降低節(jié)點(diǎn)能耗。最后結(jié)合變異系數(shù)、節(jié)點(diǎn)剩余能量、備選CPN的網(wǎng)絡(luò)深度和當(dāng)前連接的子節(jié)點(diǎn)數(shù)選出NPN。結(jié)合仿真結(jié)果和理論分析可知,NDM-RPL路由協(xié)議性能比較于EMA-RPL和MRPL均有顯著提升。