改進的無線傳感器網(wǎng)絡(luò)路由算法*

李 莉， 李雪梅， 李秀瀅

(北京電子科技學(xué)院 電子信息工程系，北京 100070)

0 引 言

相對于傳統(tǒng)網(wǎng)絡(luò)和移動網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)[1](wireless sensor networks,WSNs)具有節(jié)點數(shù)據(jù)運算速度和存儲空間有限、傳輸帶寬低，節(jié)點不移動或很少移動、節(jié)點通信能耗高、數(shù)據(jù)處理能耗低、節(jié)點自組網(wǎng)等特點，因此,其組網(wǎng)方式往往備受關(guān)注[2,3]。

目前典型的無線傳感器路由算法主要有簇樹(cluster-tree),無線自組網(wǎng)按需距離矢量(Ad Hoc on-demand distance vector,AODV)、低功耗自適應(yīng)集簇分層(low energy adaptive clustening hierarchy,LEACH)和基于IPV6技術(shù)的低功耗有損無線局域網(wǎng)路由協(xié)議(IPV6 routing protocol for low-power and lossy networks,RPL)。

Cluster-Tree算法屬于典型的平面路由算法[4]，信息轉(zhuǎn)發(fā)僅發(fā)生在父子節(jié)點之間的，采用樹狀拓撲結(jié)構(gòu)的地址分配技術(shù)，節(jié)點發(fā)現(xiàn)速度快，只要進行一次地址計算，便可獲取到節(jié)點的位置,同時，其還具有結(jié)構(gòu)簡單、實現(xiàn)容易等優(yōu)點。但該種路由發(fā)現(xiàn)機制不支持多路徑，若某條路徑上的中間節(jié)點死亡，則整個網(wǎng)絡(luò)將會崩潰。同時，不同支路的節(jié)點間不能直接傳輸，需要借助上層節(jié)點轉(zhuǎn)發(fā)，造成額外的能量消耗。因此，Cluster-Tree路由算法只適用于規(guī)模較小、節(jié)點相對固定的網(wǎng)絡(luò)。AODV算法采用查詢的方式[5]，借助路由請求報文和路由回應(yīng)報文來進行路由發(fā)現(xiàn)，是一種按需建立路由的算法。與Cluster-Tree不同，AODV采用了網(wǎng)狀結(jié)構(gòu)，允許多路徑，因而具有更好的拓展性。但由于其采用洪泛算法，因而節(jié)點的發(fā)現(xiàn)速度慢，能耗較大。此外，AODV對網(wǎng)絡(luò)的服務(wù)質(zhì)量(quality of service,QoS)沒有太多考慮，當(dāng)網(wǎng)絡(luò)的服務(wù)質(zhì)量要求較高時，AODV便不能滿足要求[6]。因此，AODV路由發(fā)現(xiàn)機制只適用于QoS要求較低、網(wǎng)絡(luò)節(jié)點數(shù)較少的網(wǎng)絡(luò)。層次路由算法以LEACH算法為代表[7]，LEACH算法與Cluster-Tree一樣采用樹狀拓撲結(jié)構(gòu)，但一種自分簇的路由算法，簇頭節(jié)點自舉產(chǎn)生，各個節(jié)點在選定好各自的簇頭節(jié)點后，發(fā)送請求入簇消息，加入到對應(yīng)的簇內(nèi)，信息的傳送由普通節(jié)點發(fā)送給簇頭，再由簇頭發(fā)送給基礎(chǔ)節(jié)點，是一種定向、層次式的信息發(fā)送。在該機制下，存在高一級的管理節(jié)點，因此整個網(wǎng)絡(luò)的組織管理能力較強，當(dāng)網(wǎng)絡(luò)發(fā)生變化時，反應(yīng)時間較短。但LEACH算法由于簇頭選擇的隨機性，容易造成各個節(jié)點的能耗不均衡，從而使得整個網(wǎng)絡(luò)的生命周期變短。

RPL算法基于有向無環(huán)圖(destination oriented directed acyclic graph,DODAG)的拓撲概念[8～12]，在有向無環(huán)圖中，每條路徑都是有方向的，目標(biāo)函數(shù)利用度量和約束條件得到最優(yōu)路徑，所要傳遞的數(shù)據(jù)均通過該條最優(yōu)路徑來進行傳遞，數(shù)據(jù)定向地傳遞給該最優(yōu)路徑上箭頭所指的節(jié)點。由于利用有向無環(huán)圖，與樹狀拓撲結(jié)構(gòu)對比，提供了更多的路徑，支持多路徑；與網(wǎng)狀拓撲結(jié)構(gòu)相比，節(jié)點的發(fā)現(xiàn)速度較快，解決了資源浪費問題，此外，相較于其他路由發(fā)現(xiàn)算法，RPL算法可以方便地與IP網(wǎng)絡(luò)互聯(lián)，是一種比較成熟的無線傳感器網(wǎng)絡(luò)路由發(fā)現(xiàn)算法。本文在RPL算法基礎(chǔ)上進行了改進，并實驗驗證了改進算法的有效性。

1 RPL算法

1.1 RPL中DODAG的構(gòu)建過程

RPL算法中DODAG的構(gòu)建過程的核心是通過DAG信息對象(DAG information object,DIO)消息和DAG目標(biāo)訪問對象(DAG access objects,DAO)消息，以及DIS消息發(fā)現(xiàn)路由，同時利用目標(biāo)函數(shù)計算度量值，決定某節(jié)點父節(jié)點的選擇及判斷某節(jié)點是否可以加入對應(yīng)的有向無環(huán)圖。整個DODAG構(gòu)建過程如圖1所示。

圖1 DODAG構(gòu)建過程示意

1.2 RPL的修復(fù)、更新過程

RPL制定了本地修復(fù)和全局修復(fù)這兩種相互補充的修復(fù)技術(shù)來確保網(wǎng)絡(luò)的穩(wěn)定運行。本地修復(fù)的思想是，在發(fā)現(xiàn)一條路徑不可達時，節(jié)點立即尋找一條路徑替代原路徑，而不考慮是否是最優(yōu)的，即盡快找一條“能用的”路徑，先用著再說。全局修復(fù)的重點是在整個網(wǎng)絡(luò)上，為所有的節(jié)點重建DAG，以保證網(wǎng)絡(luò)處于“最優(yōu)狀態(tài)”。

網(wǎng)絡(luò)更新時，PARENT節(jié)點向子節(jié)點發(fā)送一個DIO消息。子節(jié)點在收到消息后，立即對該消息進行處理。處理過程首先取出DIO消息中的PARENT信息，然后與自身已存在的首選PARENT信息進行比對，通過執(zhí)行對比算法得出較為優(yōu)質(zhì)的那個PARENT節(jié)點。最后把對比得出的優(yōu)質(zhì)PARENT節(jié)點更新為默認路由。更新默認路由完成后，子節(jié)點向上發(fā)送DAO消息，更新祖先的向下路由。

2 RPL路由發(fā)現(xiàn)機制的改進與設(shè)計

2.1 能量均衡策略

本文將節(jié)點的剩余能量作為一個參數(shù)加入到最優(yōu)路徑的選擇上，通過均衡節(jié)點能量來延長網(wǎng)絡(luò)生命周期。同時，在選擇父節(jié)點的過程中，若僅僅考慮父節(jié)點的能耗，可能會出現(xiàn)避免父能耗過多而選擇一條更長的路徑的情況，這會導(dǎo)致整個鏈路的能耗實際增大。因此在最優(yōu)路徑的選擇上保留路徑距離參數(shù)，使得算法能選擇整體更優(yōu)的方案。

RPL算法中每一個節(jié)點都包含有三個對象：INSTANCE對象、DAG對象、PARENT對象， INSTANCE對象包含優(yōu)選決策函數(shù)OF，用來決策路由的好壞。本文依據(jù)能量均衡的策略來進行路由的決策。PARENT對象中包含有父節(jié)點的信息，用于描述父節(jié)點的連接特性。DAG對象包含候選節(jié)點的信息。三者間的能量均衡關(guān)系如圖2所示。

圖2 能量均衡策略

優(yōu)選算法根據(jù)度量值進行選擇，確定優(yōu)質(zhì)父節(jié)點。度量值的計算如下

Metric(E,D) =E·We+D·Wd

(1)

式中Metric為度量值，E為節(jié)點剩余能量，D為距離，We,Wd分別為剩余能量和距離的權(quán)重，從而避免了部分節(jié)點長期承擔(dān)轉(zhuǎn)發(fā)任務(wù)而導(dǎo)致能量過度消耗。其中E和D的更新函數(shù)如下：

neighbor_link_callback(rpl_parent_t *p,int status,int numtx)

{new_etx=((uint32_t)recorded_etx*ETX_ALPHA+(uint32_t)packet_etx*(ETX_SCALE-ETX_ALPHA))/ETX_SCALE;

p->link_metric = new_etx;

rpl_mc_eng+=(rank_temp/100);∥發(fā)包能耗和距離有關(guān)}

calculate_rank(rpl_parent_t *p,rpl_rank_t base_rank)

{rank_increase = p->link_metric;

new_rank=base_rank+rank_increase;

rank_temp=rank_increase;

return new_rank;

}

2.2 優(yōu)選算法

優(yōu)先算法對比候選節(jié)點與首選父節(jié)點的度量值大小，度量值較小的節(jié)點認為其在能量與距離的博弈中整體更優(yōu)，選取為優(yōu)質(zhì)父節(jié)點。同時，為了避免節(jié)點過于頻繁改變路由而出現(xiàn)路由風(fēng)暴，需要一個閾值，只有度量差值大于閾值時，優(yōu)選算法才會生效，即

(2)

式中P1為度量值為m1的節(jié)點，P2為度量值為m2的節(jié)點，Pbest為優(yōu)質(zhì)節(jié)點，diff為最小改變差。

優(yōu)選算法的實現(xiàn)如下：函數(shù)有兩個參數(shù)傳入，第一個為首選父節(jié)點，第二個為候選父節(jié)點。返回值為兩者中較為優(yōu)質(zhì)的節(jié)點，該優(yōu)質(zhì)節(jié)點后續(xù)將成為首選節(jié)點。最小度量值間隔diff的引入防止了首選節(jié)點的頻繁改動造成的網(wǎng)絡(luò)不穩(wěn)定。

static rpl_parent_t *best_parent(rpl_parent_t *p1,rpl_parent_t *p2)

{min_diff=PARENT_SWITCH_THRESHOLD;∥最小間隔

p1_metric=(uint32_t)p1->rank*Wd+(uint32_t)p1->eng* We; ∥計算p1度量值

p2_metric=(uint32_t)p2->rank*Wd+(uint32_t)p2->eng* We; ∥計算p2度量值

if(p1==p1->dag->preferred_parent || p2 == p1->dag->preferred_parent) {

if(p1_metric p2_metric -diff) ∥比較節(jié)點

{return dag->preferred_parent; }

}

return(p1_metric

3 實現(xiàn)與測試

為驗證算法的有效性，采用開源平臺Contiki下提供的無線傳感器網(wǎng)絡(luò)仿真工具Cooja進行仿真驗證[13,14]，節(jié)點布置如圖3所示，綠色范圍為節(jié)點可通信范圍，1號節(jié)點為匯聚節(jié)點，其余節(jié)點為傳感節(jié)點。節(jié)點每收到一個dio消息，觸發(fā)一次候選父選擇，回送DAO給首選父節(jié)點，建立二者之間的路由。形成圖4(a)拓撲結(jié)構(gòu)，運行一段時間后，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)如圖4(b)所示，進行了路由的調(diào)整。

圖3 測試方案物理拓撲

圖4 網(wǎng)絡(luò)拓撲

為了獲得剩余能量和距離的合理權(quán)重值，本文在不同節(jié)點數(shù)量和拓撲結(jié)構(gòu)下，測試不同的We與Wd值對網(wǎng)絡(luò)的影響，以網(wǎng)絡(luò)中首個節(jié)點的死亡時間為判斷依據(jù)，對比完整網(wǎng)絡(luò)的存活時間，測試結(jié)果如圖5所示。橫坐標(biāo)表示傳感節(jié)點剩余能量的權(quán)重值We，縱坐標(biāo)表示首個死亡節(jié)點的存活時間，其中橫坐標(biāo)為“無”時的值表示不采用能量均衡策略時的首個死亡節(jié)點的存活時間。

圖5 不同網(wǎng)絡(luò)拓撲結(jié)構(gòu)下的網(wǎng)絡(luò)生存時間

由圖可知在相同網(wǎng)絡(luò)拓撲結(jié)構(gòu)下，能量均衡算法提高了網(wǎng)絡(luò)的平均壽命。另外由于網(wǎng)絡(luò)中傳感節(jié)點所處位置的不同，對于相同節(jié)點數(shù)量的WSNs，節(jié)點所處物理位置的改變也將影響到能量的消耗，以及路由的選擇。因此從圖中可以看出不同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，其首個死亡節(jié)點存活時間對應(yīng)的剩余能量和距離的權(quán)值We，Wd的取值沒有一個統(tǒng)一的最優(yōu)值。圖6為當(dāng)We=0.45，Wd=0.55時，網(wǎng)絡(luò)的生存時間和不采用能量均衡算法時的網(wǎng)絡(luò)生存時間的對比。

圖6 網(wǎng)絡(luò)生存時間

4 結(jié) 論

本文中設(shè)計的RPL路由發(fā)現(xiàn)機制的改進方案通過綜合考慮節(jié)點的剩余能量以及節(jié)點在這個網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的物理位置，均衡了節(jié)點的能量消耗，并通過仿真證明了此方法確實能提高網(wǎng)絡(luò)的平均壽命。由于本文是在仿真的基礎(chǔ)上進行的驗證，并沒有考慮到實際的節(jié)點能量消耗，以及能量消耗與節(jié)點拓撲結(jié)構(gòu)間的關(guān)系，后期將尋求最優(yōu)的節(jié)點剩余能量與距離的權(quán)重值，來獲得最佳的網(wǎng)絡(luò)的平均壽命。