基于無線傳感網NB-IoT分簇RPL組播路由算法的研究

高江軍,洪 鋒

(1.池州職業技術學院 電子信息與傳媒系,安徽 池州 247000;2.池州學院 智能感知與計算研究中心,安徽 池州 247000)

路由算法是指用于計算網絡中數據包傳輸路徑的算法。當一個數據包從源節點發送到目標節點時,需要通過一系列的中間節點進行轉發,路由算法就是根據網絡拓撲結構、鏈路狀態、流量負載等信息,計算出數據包傳輸的最佳路徑。

路由算法是網絡協議棧中非常重要的一部分,不同的網絡協議棧可能采用不同的路由算法來實現數據包的傳輸和路由選擇。以基于openFlow/SDN控制器的路由算法[1]為例,該算法利用openFlow的SDN控制平面與數據平面分離,在制定路由策略時考慮全網流量信息和網絡狀態,并以網狀網和胖二叉樹網絡為基礎,制定網絡轉發策略。

RPL(低功耗有損網絡路由協議)是一種可以不依賴定位系統自行組網的無線傳感網路由協議,主要在LLN(低功耗有損網絡)網絡中應用,該網絡中的節點以無源節點為主。節點之間通過RPL協議自行構建由父子節點組成的有向無環圖,根節點通過廣播收集全網節點的數據[2]。但在實際的無線傳感網中,如果只是收集指定區域或者指定節點的信息時,全網發送數據就會造成數據的冗余轉發,對于節點能量有限的無源節點就會減少網絡的生存時間。

加入組播機制后的網絡可以解決傳統RPL路由算法中存在的數據轉發冗余問題,延長網絡的生存時間。隨著無線網絡規模的逐漸擴大,雖然組播技術已經大大減少了節點轉發數據量,但是由于網絡結構是樹形結構,關鍵節點的轉發資源消耗依然很大。傳統的算法設計主要圍繞中小型網絡進行算法改進,當網絡規模不斷擴大后,關鍵轉發節點就會快速消耗殆盡。

目前關于RPL分簇組播路由算法的國內外研究并不多,研究的方向主要有基于位置的路由算法和基于消息報文設計的路由算法。

基于位置的算法主要是通過定位系統將各個節點的地理信息發送給根節點或者關鍵轉發節點,如SenCast算法[3]和HGMR算法[4]。其中,SenCast算法思想主要是在大規模無線傳感網中建立一個強大的基站,根據網絡功能需求和各個節點的路由信息建立最優組播樹,再對該組播樹進行分簇。在轉發數據時,基站首先與各個簇首進行數據交互,簇首再將數據以無狀態的方式發送給各組播接收節點。該算法的優勢是利用強大的基站來維護所有節點的路由信息,承擔了大多的路由計算,但是簇首的能量消耗較大,而且無狀態的組播會因為路由無法固定,容易導致部分數據的轉發路徑復雜甚至丟失。HGMR算法思想首先將網絡劃分成多個子樹,網絡中有一個能量充足的sink節點(根節點),各子樹根據地理哈希算法選取一個簇首,數據的發送從sink節點和簇首開始,再由簇首轉發到各個子樹的接收節點。該算法的優點是大量的路由信息由sink節點和簇首分擔,分散了關鍵轉發節點的能量消耗。但是存在兩個問題,一是sink節點和簇首的位置難以固定,如果距離較遠,可能導致信號接收不到或者不穩定現象;二是簇首的能量消耗較大,沒有較好的輪換機制,很容易導致網絡頻繁重構、數據轉發延遲或者丟失。

基于修改消息報文的組播主要有DODAG(以目的節點為導向的有向無環圖)組播[5]和EBMR組播[6]。其中,DODAG組播是通過修改RPL組網消息中的option選項的內容,在各接收節點消息option選項中增加組播地址并根據RPL算法建立組播樹,每個組播接收節點都有一個父節點和備份父節點。該算法的優點在于當轉發節點失效時,可以通過備份節點完成轉發,增加了網絡傳輸的可靠性。而該算法的缺點是每次發送數據都會經過父節點和備份父節點,這種冗余發送會造成父節點能量多余消耗。EBMR算法前期的研究主要是通過在option選項中增加剩余能量計算機制,并設定節點的能量閾值,建立能量均衡最優轉發節點集合,數據的傳輸選擇能量剩余大于閾值的節點進行轉發。當節點能量小于閾值,從節點集合中更換大于閾值的節點進行轉發。該算法能很好地平衡各關鍵轉發節點的能耗,但在大規模無線傳感網中,由于節點數量較多,組播地址和路由數據也會不斷增大,遠距離的傳輸會加快節點因計算過多導致的能量消耗,網絡生存時間會大幅減少[7]。

1 研究思路

大規模無線傳感網中,已有基于位置和消息報文設計的算法都還存在很多問題,若要有效地提高網絡的生存周期和傳輸效率,應該結合多種協議算法的優缺點,合理優化網絡算法。本研究主要是通過固定節點分簇和最優轉發節點輪換機制來降低大規模網絡節點的存儲壓力和數據轉發冗余率。

1.1 固定節點分簇

大規模無線傳感網的節點數量龐大,僅僅使用RPL組播是不實際的,節點存儲和轉發量過大都會造成節點能量快速消耗殆盡。在網絡密度相同時,將大規模網絡根據覆蓋區域和節點數量分成若干大小相近的簇,網絡的簇首選擇NB-IoT基站模式,簇首按照蜂窩結構排列,所有簇首之間通過NB-IoT協議[8]進行數據通信。各個簇首負責本簇內的節點組播通信,簇內采用RPL組播路由協議,根據前期研究的EBMR算法構建基于能耗均衡的最優轉發集合進行組播分組轉發。

1.2 簇內DODAG的構建

簇內通過構建DODAG完成所有節點的自行組網。簇首先向鄰居節點廣播DIO消息,所有鄰居節點處于監聽狀態,收到DIO消息后根據目標函數和度量值考慮是否加入DODAG,如果鄰居節點符合加入條件則以簇首作為其父節點添加路由,并向父節點回復包含自己rank值(在DODAG中的深度)的DAO消息。加入DODAG的鄰居節點繼續向下定期發送DIO消息,直到所有節點按照上述方法完成注冊和rank值計算,并在rank值與父節點相近的鄰居節點中選擇一個備份父節點,在構建DODAG過程中同時完成環路檢測,確保網絡沒有環路。最后簇首完成所有簇內節點的路由信息更新。

1.3 簇內RPL組播樹構建

在投放無線傳感器之前,所有節點都存儲了組播地址,根據收集數據的不同進行分組。簇首通過構建DODAG已存儲所有組播接收節點的路由信息,組播分組轉發會選擇最優的轉發路線進行轉發。

1.4 簇內最優轉發節點選取

簇首的由于采用NB-IoT基站,可以確保無線信號覆蓋簇內的所有節點,組播分組在組播樹中轉發,會出現rank值小的節點成為關鍵轉發節點,長時間的數據收發,會造成這類節點能量比其他節點更快地消耗,即使有備份節點的輪換,也不會維持太長時間。因此,當部分節點能量耗盡時,很容易觸發DODAG重構,能量耗盡的節點區域則無法采集數據。因此,在節點輪換時,要合理考慮網絡中各節點的能耗均衡,確保節點無意外損害的情況下,可以維持更長的時間。本文研究的RPL-CMRA算法,主要是通過在各節點消息的option中增加能量計算機制和節點輪換能量閾值,讓節點能夠根據閾值進行輪換。由于各節點都可以與簇首建立鄰居關系,可以讓網絡中所有節點都可以參與輪換,最大限度的提高整個簇內網絡節點能耗均衡性能。

2 RPL-CMRA最優轉發節點組播路由算法描述

RPL-CMRA算法思想核心是NB-IoT基站模式和簇內最優節點轉發算法。NB-IoT基站相比前期研究中的RPL節點,具有3個優勢,一是信號覆蓋范圍廣可以達到10km;二是支持海量連接,可以支持10萬個連接,非常適合WSN(無線傳感網)低功耗節點的部署需求;三是低功耗,普通的電池供電可以擁有10年壽命。為了能實現NB-IoT和WSN網絡有效融合,需要在NB-IoT簇首協議棧進行修改和添加移動通信網關硬件模塊,確保能將無線傳感網收集的信息轉發到移動通信網絡中。簇內最優轉發的核心是建立最優轉發節點輪換機制,設定簇內節點總數為n,各組播節點編號為N,rank值為R,組播編號為M,記錄節點剩余能量為E,節點剩余能量上報定時器為T,設計節點輪換閾值為S,用i表示節點序號。

2.1 簇內節點維護信息表設計

簇首組播信息如表1所示。

表1 簇首組播信息表

組播成員信息如表2所示。

表2 組播成員信息表

NB-IoT基站簇首,存儲了本簇內的所有組播組地址和成員信息,RPL協議建立組播樹之后,每當需要收集指定組播組的數據時,簇首會向各個組播成員發送收集數據消息。收到簇首的消息后,各個成員將采集的數據回送給簇首,并將轉發過程中各個節點的剩余能量值Si一并發送給簇首。當在T時間內沒有收到簇首消息時,節點會主動發送自身的能量剩余值給簇首。簇首比較父節點和備份節點的剩余能量閾值,判斷是否存在能量不足的轉發節點,如果存在,將轉發父節點替換成備份節點。如果備份節點能量也不足,則根據能量不足的父節點和備份父節點的數量以及rank值,判斷是否需要重構RPL和組播樹。

轉發節點組播信息如表3所示。

表3 轉發節點組播信息表

在RPL組播簇內,各節點都有可能是本組播樹的成員節點和轉發父節點,同時也可能是其他組播樹的父節點。因為離簇首越近,rank值越小,負責的轉發量也就越大。當這些rank值小的轉發節點能量低于能量剩余閾值時,首先進行備份節點替換,但是往往這些節點也會是其他組播樹的父節點。本研究主要根據能量剩余不足的節點數和對應的rank值判斷是否要重構組播樹,主要依據為相同rank值的節點能量不足占比是否大于指定值,若大于則重構RPL,并對能量不足的節點進行標記,再將它的rank值設置到最大值,促使這些節點暫時不會成為父節點。

2.2 算法實現過程設計

首先,針對DAO消息格式進行改進。節點根據RPL路由算法通過發送組網消息來構建DODAG組播樹,DAO消息中包含有組播編號、組播組地址、剩余能量閾值、父節點地址、備份父節點地址、簇首地址等信息。RPL-CMRA組播消息DAO選項如表4所示。當RPL建立DODAG時,DAO消息攜帶了本節點的編號、剩余能量閾值、所屬組編號以及該節點在DODAG中的類型。RPL組播樹構建完成后,組播消息負責傳送采集信息,并上報剩余能量情況。

表4 RPL-CMRA組播DAO選項

其次,設計PL組播樹重構算法。當DODAG組播構建完成后,組播分組就會根據簇首指令發送數據,并上報節點的剩余能量。當簇首發現同一個子節點的父節點和備份父節點都出現剩余能量不足時(小于閾值),發送通告該子節點下次轉發數據到該父節點時,直接與簇首節點通信。簇首統計所有剩余能量不足節點數量為P。當P達到簇內總節點一半時,將這些節點rank值設置為最大值,并進行RPL重構組播樹。重構RPL組播樹如式(1)-式(3)所示。

(1)

P=crad(F)

(2)

(3)

3 剩余能量閾值設置

RPL-CMRA算法要求簇首根據簇內各節點的剩余能量S確定重構組播樹的時間,S的取值直接決定RPL組播樹的生存時間,根據多次仿真實驗的數據,簇內節點數n、分組長度L、節點射頻傳輸距離r、節點密度ρ直接決定網絡的生存時間。根據這些參數可以計算節點收發一次組播分組的能耗Z,前期已經完成此項研究[9],因此剩余能量閾值可以通過式(4)和式(5)得出:

Z=L(2E+Kr2)

(4)

S=Sc-Zn

(5)

式(4)和式(5)中,Sc表示傳感器節點的初始能量。

在仿真實驗中,通過計算不同節點數和密度的情況,發現節點收發次數等于節點數時,此時的剩余能量值為閾值,剛好可以維持到第二次網絡重構。

結語

針對基于NB-IoT基站模式RPL組播路由算法的研究,發現已有的RPL組播路由算法在大規模無線傳感網中的應用中還存在很多問題。為了能不使用定位系統來降低能耗,利用新型的NB-IoT基站技術,可以充分發揮無源節點高接入和低消耗的優勢。NB-IoT基站替換傳統無線傳感器簇首,可以大幅降低復雜環境的節點安裝問題。另外,通過在簇首完成大量的剩余能量替換和網絡重構計算,可以降低其他節點因計算帶來的能耗,有利于延長網絡生存周期。但該算法還存在其他問題,比如復雜環境下簇首位置的選擇、傳感器信號傳輸等。因此,該算法在后期研究中還需要進一步地改進和完善。