ZigBee網絡的路由算法分析

王惠清，周 雷，王 靜/Wang Huiqing，Zhou Lei，Wang Jing

（1．瀘州醫學院現代教育技術中心 瀘州646000；2.中南大學信息科學與工程學院 長沙410083）

1 引言

ZigBee網絡是一種近距離的無線傳感網絡，具有低數據量、低能耗、靈活組網的特點，在局域區域中使用廣泛。ZigBee 是建立在IEEE 802.15.4 標準的基礎上，在數千個微小的傳感器之間相互協調實現通信[1]。2003年12月，IEEE 正式發布了該技術物理層和媒體接入層（MAC）所采用的標準協議，即IEEE 802.15.4 協議標準，作為ZigBee 技術的網絡層和媒體接入層的標準協議。2004年12月，ZigBee聯盟在IEEE 802.15.4 定義的物理層和MAC的基礎上，定義了網絡層和應用層，正式發布了基于IEEE 802.15.4的ZigBee 標準協議[2]。本文在分析ZigBee網絡配置、組網和網絡拓撲結構的基礎上，對比常用的幾種ZigBee網絡路由算法，并且利用Matlab 軟件對其網絡性能進行仿真實驗。

2 ZigBee網絡拓撲結構

ZigBee網絡層支持3 種拓撲結構： 星型拓撲、樹型拓撲和網狀型拓撲[3]。其拓撲結構如圖1所示。星型拓撲網絡主要為一個節點與多個節點的通信設計； 樹型拓撲網絡采用基于信標的方式進行通信，使用分級路由策略來傳送控制信息和數據；網狀型拓撲網絡是一種骨干網，由若干個FFD 節點連接在一起組成。在網狀型拓撲結構中，網絡節點之間進行通信需要預先設定一個節點作為整個ZigBee網絡的協調點。

圖1 ZigBee網絡拓撲結構

3 ZigBee網絡組網

ZigBee網絡的組網分為以下幾個步驟。

①初始化ZigBee網絡環境并將網絡設備節點加入到ZigBee網絡，網絡初始化的主要工作是確定ZigBee的節點協調點。

②為了避免節點干擾，需要對信道進行掃描，以準確獲取節點信息。

③對網絡的節點ID 進行設置，獲取合適的信道后，協調器選取一個標識符作為網絡標識符（PAN ID），PAN ID 在信道中必須唯一，且不能為廣播地址，這樣就實現了ZigBee 網狀網絡的初始化。

④最后將選取的設備節點加入ZigBee網絡中，主要有兩種節點加入情況：一種情況是有新的節點需要加入網絡；另一種情況是已失效的節點重新喚醒，申請加入網絡。第一種需要原來保存的路由信息向父節點發起申請； 第二種則需要FFD網絡節點向協調器發出連接請求，協調器根據實際網絡情況決定是否允許其連接，建立連接后，才能實現數據的收發。

ZigBee網絡組網時，節點網絡地址的獲得基于樹型地址分配機制[4]，其主要步驟為：ZigBee網絡中選定的協調器需要建立一個新的網絡，首先利用樹形分配算法給網絡分配地址0，網絡深度Depth0，新節點i 加入網絡并且與節點k 連接，這里，節點k 稱為節點i的父節點。節點k 本身的網絡地址為Ak，網絡深度為Depthi=Depthk+1。ZigBee網絡自身的協調器節點深度定義為0，作為根節點，且它的子節點深度定義為1。父節點k 為子節點i 分配網絡地址的關系為

若新增加的子節點為FFD 設備，并且為路由節點，則給它分配網絡地址

4 ZigBee 路由算法

ZigBee網絡層支持Tree、AODV 和EHRP 等多種路由協議，ZigBee網絡進行路由選擇主要有以下幾個步驟。

①ZigBee網絡源節點以廣播的方式發送路由請求報文。

②目的節點在網絡報文中接收到請求報文后，發送響應回答報文。

③路由路徑上的網絡節點對收到的響應回答報文進行計算和分析，得到所有路由路徑的跳數和數據時延。

④將計算和分析后的最優路徑信息記錄到此路徑網絡節點的路由表中。

考慮到ZigBee網絡低能耗和簡單配置等各項特點，對ZigBee網絡中的典型路由算法，如Tree算法、AODV算法[5]、EHPR算法、Cluster-Tree+AODVjr算法等進行對比分析，在此基礎上對這些算法進行改進和完善，使其適應不同的網絡環境。

4.1 Tree 路由算法

Tree 型路由機制主要包括樹形地址的分配和樹形地址的路由選擇，其Tree 型路由算法的核心就是尋找網絡中源節點到目的節點之間的路由路徑。例如，設某路由節點向目的地址為D的節點發送報文，其中，A 為路由節點的網絡地址，d 為網絡深度，判斷目的節點位置的表達式為

若當前節點是目的節點的祖先節點，則當前節點的下一跳地址為

Tree 路由算法的優點主要是通過簡單的路由計算便可獲得節點的數據傳輸路徑，且需要的路由開銷小，節點功耗低以及網絡節點維護簡單；缺點主要是層次低的節點會成為祖先節點，其作為數據傳輸的路由路徑的可能性大，隨著網絡規模逐漸增大，拓撲結構樹中根節點附近的路由數據負載會越來越嚴重，進而造成網絡擁塞和延遲，最終導致網絡的整體性能降低。

4.2 AODV 路由算法

DSDV 協議是一個基于傳統的BellmanFord 路由機制的表驅動算法，被認為是最早的無線自組網絡路由協議。DSDV 在傳統Distance-Vector算法的基礎上采用了序列號機制，用于區分路由的新舊程度，防止Distance-Vector算法可能產生的路由環路。DSDV 采用時間驅動和事件驅動技術控制路由表的傳送，即每個移動節點在本地都保留一張路由表，包括所有有效目的節點、路由跳數、目的節點路由序列號等信息，目的節點路由序列號用于區別有效和過期的路由信息，以避免環路的產生[6]。

AODV 路由協議在DSDV 協議的跳路由、序列號、定期廣播機制的基礎上，加入了DSR 按需路由發現和維護機制。AODV 路由算法在此基礎上有所改進，主要是引入路由表，在網絡節點的路由表中保存路由信息，減少網絡中廣播的次數。AODV算法作為無線傳感網絡中的經典算法，運用十分廣泛，算法復雜度高，消耗的網絡資源多。針對這種情況，對其路由算法進行改進，涉及以下幾個方面：簡化了路由表的項目，刪除了路由跳數和節點的先驅節點項；簡化了路由路徑的查詢過程，只授權網絡的目的節點對請求數據幀發送響應；改進了路由維持的機制，若源節點在時鐘定時器內無法接收到目的節點的確認幀，路由算法重新對路徑進行計算，規劃新的路由路徑； 改進了路由環路形成的條件，基于AODV 路由算法所需開銷小，對其運用最優化的原理，使用節點序列號對路由更新情況進行區分，而且目的節點僅響應RREQ 報文分組。故改進后的AODV 路由算法開銷更小、路由路徑更短。

4.3 EHRP 路由算法

EHRP 路由算法是在Tree 路由算法的基礎上進行改進，以適應動態變化的網絡環境。Tree 路由算法的路由選擇只適用于父節點與子節點的路由選擇，而EHRP 路由算法在此基礎上增加了路由尋址功能，并在網絡節點中增加了一個路由鄰接表，路由選擇過程中EHRP 路由算法先按照Tree 路由算法計算路由開銷S1，然后在鄰接路由表中計算源節點到目的節點的路由開銷S2，最后判斷S1和S2+1的大小，將分組發送到開銷較小的路由節點上，后續的節點類似，直到到達目的節點。EHPR算法的路由開銷小，選擇最短路徑進行數據報轉發。

5 算法比較及仿真

算法的對比分析采用Matlab 軟件模擬仿真，其過程為：首先組建一個仿真ZigBee網絡，在ZigBee組網實驗中，選取70 個網絡節點，從分布在網絡中的70 個節點中，選取出一個ZigBee網絡的協調節點，同時，還需要選擇40 個路由器節點用來轉發分組，30 個連接到網絡中的設備節點，用來實現設備的連通性，其節點分布情況如圖2所示。組網過程中，運用Tree 型路由拓撲結構分配節點地址，其ZigBee網絡組網結果如圖3所示。

圖2 ZigBee網絡節點分布情況

圖3 ZigBee網絡節點組網結果

對比分析相同的源節點和目的節點的路由選擇算法，對網絡中的節點分別采用Tree 路由算法、EHRP 路由算法和AODV 路由算法，然后計算路由路徑長度。由圖4 可知，Tree 路由算法路徑最長，EHRP 路由算法次之，AODV 路由算法路徑最短。通過對3 種路由算法的對比分析可知，Tree 路由算法路徑的建立可通過計算網絡節點的地址得到；EHRP 路徑的建立則需要建立鄰接表，然后對節點路徑進行計算和比較，最后獲得最優路徑；AODV 路由算法路徑的建立，首先需要建立路由表，即自適應路由，通過目的節點的反饋信息建立路由路徑，最后獲得最短路徑。

圖4 3 種路由算法的路由路徑

綜合分析可知，從節點能量消耗和存儲使用角度來看，Tree 路由算法節點能量耗費最少，EHRP 路由算法的存儲空間消耗較少，AODV 路由算法的性能最佳。然而在實際的網絡環境中，需要依據節點的能量消耗、時延和負載均衡等各項性能指標選擇最佳的路由算法。一般而言，ZigBee網絡依據設備節點和直接連接的路由節點進行通信的情況以及當路由節點因能量消耗無法進行主動路由的情況，均采用“Cluster-Tree +AODV”混合的路由算法，可以使網絡的性能達到最優。

6 結束語

本文主要介紹了ZigBee網絡的體系結構和組網過程，對ZigBee網絡常用的幾種路由算法進行了分析，重點對Tree算法、EHPR算法和AODV算法的路由開銷、功耗進行對比分析。最后，對ZigBee網絡中的源節點和目的節點分別運用Tree 路由算法、EHRP 路由算法和AODV 路由算法進行模擬仿真，計算路由路徑。

實驗結果顯示，根據具體的節點能量消耗、數據傳輸時延和數據負載等各項網絡性能指標選擇合適的路由算法，才能使網絡性能達到最佳。因此，隨著無線傳感網絡的發展，ZigBee 技術被廣泛應用于各個領域的生產生活中，如智能電網、智能家居等。

[1]ZigBee specification[EB/OL].http://www.zigbee.org.

[2]劉麗鈞，童麗麗.ZigBee 技術網絡層的路由算法分析[J].計算機與信息技術，2008，（1）.

[3]ZigBee Alliance.ZigBee architecture overview[EB/OL].http://www.zigbee.org/ en/events/documents，2005.

[4]JAE Y H，SUNGHYUN C，WOOK H K.EHRP:enhanced hierarchical routing protocol for ZigBee mesh networks[J].IEEECommunications Letters，2007.

[5]杜煥軍，張維勇.ZigBee網絡的路由協議研究[J].合肥工業大學學報，2008，31（10）： 1618-1621.

[6]趙新偉,鄭洪飛.Ad hoc網絡路由協議分析與仿真[J].計算機安全，2011，（7）.