改進的ZigBee網狀網絡路由算法研究

劉瀟花，彭 勇

(江南大學物聯網工程學院，江蘇無錫 214122)

1 概述

ZigBee是一種低速率、低功耗、適應性強的短距離無線通信技術，在智能家居、家庭保健以及環境監測等無線通信場合得到了廣泛應用［1-2］。ZigBee網絡節點是依靠電池供電的，由于節點體積小，因此節點能量十分有限。當節點的能量消耗殆盡，容易導致網絡分割，甚至會造成ZigBee網絡癱瘓。所以，提高節點生存率、降低網絡能耗是解決阻礙ZigBee網絡應用發展前景的關鍵［3］。ZigBee主要支持3種網絡拓撲，包括星型拓撲(star)、樹形拓撲(tree)和網狀拓撲(mesh)［4］。其中，網狀網絡是具有“自恢復”能力和高可靠性的網絡，可以為節點提供多條數據傳輸路徑。Mesh網絡拓撲一般采用AODVjr路由算法，AODVjr路由算法是在AODV的基礎上發展而來的，它支持端到端的傳輸［5］。AODVjr算法采用最短路徑傳輸機制，目的節點回復最先達到的RREQ分組建立路由路徑。正是由于這樣的傳輸機制，AODVjr算法的一些節點易于因頻繁參與數據轉發而造成節點死亡。為解決AODVjr算法的這些問題，文獻［6］基于節點角色差異性和節點能量狀態提出一種改進的AODVjr路由算法，文獻［7-8］提出基于能量均衡的改進ZigBee路由算法，文獻［9］基于分層思想提出的網狀網絡路由算法，都在一定程度上降低了節點死亡率和網絡能耗。

本文在深入分析ZigBee網絡路由算法的基礎上，針對現有AODVjr算法節點利用率低、網絡能量消耗大的問題，提出一種改進的 F-AODVjr路由算法。

2 AODVjr路由算法

采用AODVjr路由算法的網狀網絡采用預先地址分配方式，網絡中存在3類節點:中心協調器，路由器和終端節點。協調器和路由器存儲容量大、計算能力強，是全功能設備(Full Function Device，FFD)，可以作為父節點為新加入的子節點分配網絡地址，而終端節點為精簡功能設備(Reduced Function Device，RFD)，只有數據收發功能，作為網絡葉節點。

網絡中，父節點能夠接納子節點的最大數量為Cm，其中，路由器數量最大為Rm，網絡中的最大深度為Lm，可通過式(1)定義深度為d的父節點所擁有的地址空間Cskip(d)［10］:

入網子節點的類型不同，分配給子節點的地址的計算方法也不一樣，如果子節點為第n個加入的路由器節點，父節點分配給子路由器的地址A由式(2)計算，父節點的地址為Ap。若子節點是第n個加入的終端節點，則使用式(3)為其分配網絡地址:

AODVjr路由分為路由發現和路由維護2個過程。在發現路由環節中，存儲路由信息必須通過路由表以及路由發現表來實現。其中，路由表的條目可以保存很長時間，是持續的，而路由發現表條目僅能持續一個路由發現操作的期限。

3 AODVjr路由算法存在的問題

ZigBee網絡中每個節點都維護離自己一跳距離的鄰居節點信息，每個具有路由功能的節點都維護一張路由表，記錄本節點與其他節點已經存在的路徑信息。AODVjr路由算法分組傳輸如圖1所示。

當源節點C向目的節點L傳輸數據時，如果C中存在到L的路由表項，則根據該路由表項轉發數據分組。如果不存在則開啟路由發現，發送RREQ分組搜索目的節點。當開啟路由發現時，C向周圍節點廣播RREQ分組，直到找到目的節點為止。目的節點收到RREQ分組后，選擇最先達到的RREQ分組進行回復建立傳輸路徑，如圖1中的C－A－B－L路徑。此時，算法存在以下問題:(1)在發起RREQ尋址之前，若能利用鄰居表找到目的節點，則可避免開啟路由發現過程，減少能量消耗，但AODVjr算法在尋址前沒有使用鄰居表;(2)AODVjr算法最短路徑的尋址思想使得網絡中的一些節點，如A，B由于頻繁參與轉發數據而使節點能量很快偏低，若繼續使用這些能量偏低節點，容易造成其死亡進而引起網絡能耗增大甚至網絡癱瘓問題。本文為優化AODVjr算法，解決以上影響AODVjr算法性能的2個主要問題，提出改進的FAODVjr路由算法。

圖1 AODVjr算法分組傳輸

4 改進的ZigBee網狀網絡路由算法設計

4.1 鄰居表

由于鄰居表是每個ZigBee節點自動維護的，不需要額外的能量消耗，因此在啟動路由發現之前，如果能根據鄰居表尋址到目的節點，將能降低網絡能量消耗。網絡初始化時每個節點都更新離自己一跳距離的鄰居節點信息，鄰居表存儲內容如表1所示。

路由節點在啟動路由發現過程前，執行下列偽代碼，實現鄰居表搜索目的節點功能。

4.2 路由發現

如果目的節點不在鄰居表傳輸范圍內，則開啟路由發現，發送洪泛到目的節點的RREQ分組。RREQ分組只考慮路徑跳數，雖然能找到最短路徑，但會使某些節點過度使用成為死亡節點。在網絡運行后期，死亡節點無法再轉變為能量充足節點參與路由轉發，其他節點傳輸數據時必須繞過死亡節點，能量消耗巨大。所以，為減少死亡節點數和降低網絡能量消耗，在路由發現時，需解決以下問題:(1)盡量避免低能量節點的使用，降低死亡節點率;(2)改進原算法只將路徑跳數作為路徑代價進行路徑選擇的思想，結合剩余能量、鏈路質量綜合考慮路由成本，達到降低網絡開銷的目的。路由成本最少的路徑為最優路徑，數據傳輸時路由代價較小。

4.2.1 節點死亡率

為降低節點死亡率，改進算法根據剩余能量和能量閾值劃分節點等級，使網絡在運行時能夠判斷哪些節點為能量不足節點，從而在路由時盡量避開這些節點，由能量充足節點充當主要路由角色，以此減少死亡節點數，降低節點死亡率。

改進算法設定一個動態更新的能量閾值Ex(n)，當剩余能量大于Ex(n)時為能量充足節點;當剩余能量小于Ex(n)時為能量偏低節點。能量充足節點可以用于數據傳輸，而能量偏低節點只轉發目的節點在一跳范圍內的數據分組或者接收目的節點為自身的數據分組，在路由過程中盡量避免使用低能量節點。Ex(n)可按式(4)計算:

其中，當n=1時，Ex(1)=ε，Ex(1)為網絡設定的初始能量閾值，ε為特定系數，用來調整初始閾值的設定。Ex(n－1)表示更新之前的能量閾值，σ為一特定系數，作用在于控制能量閾值的減小速度。Ntotal指總節點個數，為常量，n為變量。為中心協調器設置2個內部計數器C1，C2。如果一個節點的剩余能量值低于當前Ex(n)值，則應向協調器發送本節點能量偏低消息，協調器使計數器C1的計數值加1。根據計數器C1的計數值，中心協調器可以算出能量偏低節點與網絡總節點的個數比值q。設定一個閾值Etreshold(0＜Etreshold＜1)，當 q＞Etreshold時，協調器使C2計數值加1，n值即為C2的計數值。這樣n值加1發生改變，使得 Ex(n)值完成一次更新。更新完Ex(n)值，C1置0，C2不變。由式(4)可得Ex(n)值為:

由Ex(n)計算方法可知，在網絡運行初期，能量閾值Ex(n)遞減緩慢，而當n增大，Ex(n)值的遞減幅度越來越小。在網絡運行后期，節點能量普遍不足，FAODVjr算法能量閾值遞減幅度變慢可以使大部分節點都能作為能量充足節點參與路由轉發，避免因參與路由節點過少而引發的網絡擁塞現象，減少因網絡擁塞造成能量的浪費。

4.2.2 路由成本

避開低能量節點使用后的AODVjr算法還需進一步優化。不同的RREQ分組達到目的節點后，使網絡中存在多條可傳輸路徑。本文從這些路徑中，選擇路由成本最低的路徑為最優傳輸路徑，路由成本越低，數據傳輸時路由代價越小。路由成本根據式(5)確定，式(5)綜合考慮了跳數、剩余能量和鏈路質量對路由成本的影響。

F-AODVjr路由算法更全面地考慮了影響路由性能的因素。在網絡運行初期，節點性能相同，FAODVjr路由算法優勢不明顯。網絡運行一段時間后，節點剩余能量、鏈路質量發生變化，改進算法可以選擇一條路由成本最低的路徑，并使數據有更高的發送成功率，從而降低網絡能量消耗。

4.3 算法流程

路由發現過程如圖2所示。

圖2 路由發現過程

算法流程具體如下:

(1)在網絡初始化時，中心協調器為每個網絡節點分配唯一的網絡地址，每個節點初始化自己的鄰居表，中心協調器廣播Ex(1)值。中心協調器根據式(4)計算能量閾值，每當能量閾值發生變化，中心協調器便向各節點重新廣播能量閾值。

(2)源節點查看鄰居表(包括父節點和子節點)，若目的節點在鄰居表中，則直接發送給目的節點;否則轉步驟(3)。

(3)查看目的節點與源節點的鄰居表(包括父節點與子節點)，若存在相同節點，則將數據分組轉發給此相同節點，否則轉步驟(4)。

(4)此時，目的節點必在離源節點兩跳之外。由于RFD節點不具有路由功能，因此如果源節點為FFD節點則直接開啟一個路由發現過程，若不是，則交由父節點開啟路由發現過程，當一個RFD節點收到RREQ分組時就立即丟棄。如果目的節點為RFD節點，則由其父節點轉交。路由發現過程按以下步驟執行:1)RREQ分組達到一個節點，該節點若不是FFD節點則丟棄RREQ分組，如果是FFD節點則轉步驟2)。2)判斷自己是否為目的節點或者為RFD節點的父節點，如果是則回復路由應答(Route Reply，RREP)分組建立路由路徑，否則轉步驟3)。3)查看自己的剩余能量，根據能量閾值判斷是否是低能量節點，若是則丟棄RREQ分組，并向中心協調器發送能量偏低信息，使計數器C1加1，若不是低能量節點轉步驟4)。4)查看自己是否已存在到源節點的路由表項，如果存在則轉步驟5)，如果不存在則轉步驟6)。5)比較路由表和RREQ分組中的路由成本TC。路由成本越小，表明傳輸數據付出的代價越小。如果RREQ分組中的路由成本高于路由表中的路由成本，則丟棄RREQ分組。否則根據式(5)計算并更新兩者的路由成本，繼續廣播RREQ分組。6)建立到源節點的路由表項，并繼續廣播RREQ分組。

(5)中心協調器設置目的節點等待RREQ分組到達的時間常數T［12］，超過設置的時間則停止等待。目的節點收到RREQ分組后選擇路由成本最低的路徑建立路由路徑，回復RREP。

5 算法分析與仿真實驗

5.1 算法分析

改進算法針對節點的能量狀況，根據式(4)不斷動態更新能量閾值，使得不同狀態節點對RREQ分組采取不同的處理方式，從而保護低能量節點。更重要的是，能量閾值的更新速度變慢，使得低能量節點在網絡運行后期轉為能量充足節點重新參與路由，防止了網絡擁塞現象。在路由發現階段，路由成本公式計算簡單，由各節點獨立計算完成。在搜索鄰居表時，假設鄰居節點個數為n，算法遍歷每個鄰居節點，此時，算法時間復雜度為O(n)，算法在多項式時間內完成。

5.2 仿真實驗結果及分析

為評估改進算法的性能，在NS2仿真軟件中對原AODVjr算法、改進的F-AODVjr算法和文獻［6］中的改進的AODVjr算法進行仿真。通過網絡的能量消耗、節點生存率和平均分組成功投遞率進行對比分析。仿真實驗的網絡范圍為300×300，通信半徑為15 m，節點初始能量為10 J，數據流類型為CBR，數據流大小為80 Byte，仿真時間為80 s，數據分組的源節點和目標節點隨機選擇。

表2為3種算法的數據分組成功投遞率仿真對比，數據分組成功投遞率指的是目的節點正確接收到的數據分組個數與源節點發送的全部數據分組個數的比值。用Ps表示源節點發送的分組數目，Pr表示成功接收到的分組數目，數據分組成功投遞率為:

由表2可知，當設置網絡節點個數為50時，3種算法都具有較高的成功投遞率，都在95%以上。隨著節點個數增多，網絡變得復雜，數據在傳輸時發生碰撞幾率增大，所以，3種算法的數據分組成功投遞率都有所下降。節點在傳輸數據時，如果目的節點死亡，數據分組將永遠不可達，而中間節點的死亡，會導致網絡擁塞，阻礙分組投遞。F-AODVjr和改進的AODVjr算法盡量避開了能量不足節點的使用，所以，數據分組成功投遞率大于AODVjr。在此基礎上，F-AODVjr在數據分組傳輸時還考慮了節點的鏈路質量，使節點具有更高的成功投遞率。

表2 數據分組成功投遞率 %

3種算法的剩余能量百分比如圖3所示。

圖3 剩余能量百分比

在網絡初始運行時，網絡節點的剩余能量、鏈路質量相同，3個算法的剩余能量百分比相差不大。隨著網絡運行，開始出現能量偏低節點。AODVjr算法繼續使用能量偏低節點造成其死亡，在網絡運行后期，當大部分節點能量偏低時，低能量節點變為能量充足節點繼續用以傳輸數據。而AODVjr算法由于死亡節點無法再變成充足節點繼續使用，其他節點在傳輸數據時都要繞過這些死亡節點，大量消耗網絡能量，其剩余能量百分比降低幅度增大，而改進的AODVjr算法與F-AODVjr算法卻避免了這一現象的產生，遞減幅度小于 AODVjr算法。雖然改進的AODVjr算法能量不足節點不再用于數據傳輸，但仍參與路由發現，所以，其能量消耗大于F-AODVjr算法。并且網絡運行一段時間后，路徑剩余能量、鏈路質量都發生變化，跳數最少的路徑并不一定最優，FAODVjr算法能找到一條路由成本最低的路徑，所以，F-AODVjr算法的剩余能量百分比始終高于AODVjr算法和改進的AODVjr算法。

3種算法的節點生存率如圖4所示。

圖4 節點生存率

節點生存率為網絡可用節點率。如果一個節點的剩余能量低于初始能量的3%，則被看作是死亡節點。網絡運行結束后，計算生存節點個數。節點生存率計算公式為:

其中，Nable是網絡運行結束后生存節點個數;Ntotal是網絡總節點個數。在網絡運行初期，節點能量充足，節點生存率降低幅度不大。由于F-AODVjr算法盡量避免使用低能量節點參與路由，因此節點死亡數較少，節點生存率始終高于AODVjr算法和改進的AODVjr算法。在網絡運行后期，雖然三者的節點生存率下降幅度都有所增大，但F-AODVjr算法和改進的AODVjr算法的網絡拓撲分割現象不嚴重，所以，節點生存率下降幅度都小于AODVjr算法。

6 結束語

本文針對AODVjr算法存在的問題提出了一種改進的F-AODVjr算法。改進算法在進行發現路由過程前，使用ZigBee節點自身維護的鄰居表尋找目的節點，如果能通過鄰居表找到目的節點，將大大降低網絡能量消耗。如果目的節點不在鄰居表傳輸范圍內，則進行路由發現。在路由發現過程中，改進算法能提高節點生存率、降低網絡能量消耗和增大數據分組成功投遞率。但改進算法的不足之處是沒有考慮網絡節點的移動情況，在路由過程中會因產生對尋址無效的RREQ分組而浪費能量。所以，今后將進一步探討如何減少路由過程中RREQ分組的洪泛并將其投入到實際應用中。

［1］李文仲，段朝玉.ZigBee2006無線網絡與無線定位實戰［M］.北京:北京航空航天大學出版社，2008.

［2］Baronti P，Pillai P，Chook V W C，et al.Wireless Sensor Networks:A Survey on the State of the Art and the 802.15.4 and Zigbee Standards［J］.Computer Communications，2007，30(7):1655-1695.

［3］蔣 挺，趙成林.ZigBee技術及其應用［M］.北京:北京郵電大學出版社，2006.

［4］陳 波.Zigbee路由算法分析及改進［D］.天津:南開大學，2009.

［5］Chakeres I D，Berndt K.AODVjr，AODV Simplified［J］.Mobile Computing and Communication Review，2002，6(3):100-101.

［6］王 芳，柴喬林，班艷麗.一種改進的ZigBee Mesh網絡路由算法［J］.計算機應用，2008，28(11):2788-2794.

［7］李予東，黃宏光，向西西.基于能量均衡的Zigbee路由算法優化［J］.計算機工程與設計，2011，32(2):397-400.

［8］Ran P，Sun M H，Zou Y M.ZigBee Routing Selection Strategy Based on Date Services and Energy Balanced Zigbee Routing［C］//Proceedings of 2006 IEEE Asia Pacific Conference on Services Computing.Washington D.C.，USA:IEEE Computer Society，2006:400-404.

［9］Ha J Y，Park H S，Choi S，et al.Enhanced Hierarchical Routing Protocol for ZigBee Mesh Networks［J］.IEEE Communications Letters，2007，11(12):1028-1030.

［10］張 擎，劉淑美，柴喬林.能量高效的Zigbee網絡改進路由策略［J］.計算機工程，2010，36(7):108-111.

［11］Ashraf U，Abdellatif S，Juanole G.An Interference and Link-quality Aware Routing Metric for Wireless Mesh Network［C］//Proceedings of the 68th Vehicular Technology Conference.［S.l.］:IEEE Press，2008:1-5.

［12］謝 川.Zigbee中改進的Cluster-Tree路由算法［J］.計算機工程，2011，37(7):115-117.