改進的無線傳感器網絡路由算法*

李 莉， 李雪梅， 李秀瀅

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

0 引 言

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

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

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

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

1 RPL算法

1.1 RPL中DODAG的構建過程

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

圖1 DODAG構建過程示意

1.2 RPL的修復、更新過程

RPL制定了本地修復和全局修復這兩種相互補充的修復技術來確保網絡的穩定運行。本地修復的思想是，在發現一條路徑不可達時，節點立即尋找一條路徑替代原路徑，而不考慮是否是最優的，即盡快找一條“能用的”路徑，先用著再說。全局修復的重點是在整個網絡上，為所有的節點重建DAG，以保證網絡處于“最優狀態”。

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

2 RPL路由發現機制的改進與設計

2.1 能量均衡策略

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

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

圖2 能量均衡策略

優選算法根據度量值進行選擇，確定優質父節點。度量值的計算如下

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

(1)

式中Metric為度量值，E為節點剩余能量，D為距離，We,Wd分別為剩余能量和距離的權重，從而避免了部分節點長期承擔轉發任務而導致能量過度消耗。其中E和D的更新函數如下：

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);∥發包能耗和距離有關}

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 優選算法

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

(2)

式中P1為度量值為m1的節點，P2為度量值為m2的節點，Pbest為優質節點，diff為最小改變差。

優選算法的實現如下：函數有兩個參數傳入，第一個為首選父節點，第二個為候選父節點。返回值為兩者中較為優質的節點，該優質節點后續將成為首選節點。最小度量值間隔diff的引入防止了首選節點的頻繁改動造成的網絡不穩定。

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) ∥比較節點

{return dag->preferred_parent; }

}

return(p1_metric

3 實現與測試

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

圖3 測試方案物理拓撲

圖4 網絡拓撲

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

圖5 不同網絡拓撲結構下的網絡生存時間

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

圖6 網絡生存時間

4 結 論

本文中設計的RPL路由發現機制的改進方案通過綜合考慮節點的剩余能量以及節點在這個網絡拓撲結構中的物理位置，均衡了節點的能量消耗，并通過仿真證明了此方法確實能提高網絡的平均壽命。由于本文是在仿真的基礎上進行的驗證，并沒有考慮到實際的節點能量消耗，以及能量消耗與節點拓撲結構間的關系，后期將尋求最優的節點剩余能量與距離的權重值，來獲得最佳的網絡的平均壽命。