ZigBee路由算法的研究和改進

劉多多 吳靜

摘 要：ZigBee技術作為一種新興的短距離無線通信技術，具有自組網、低成本和低功耗的優勢。伴隨著物聯網等高新科技的發展，對ZigBee技術的改進成為了關鍵問題。文中首先論述了ZigBee技術的基本協議和網絡配置，之后針對簇樹拓撲結構，分別對Cluster-Tree算法和AODVjr算法進行了重點解析和研究。針對網絡中AODVjr算法路由發現過程中的RREQ分組導致洪泛的缺點，從分簇角度出發，對傳統ZigBee路由算法進行了優化和改進。并通過NS-2模擬仿真實驗，主要從報文發送成功率和端到端時延等方面入手進行對比。實驗結果表明，改進算法能實現網絡負載均衡，使網絡生存時間最大化。

關鍵詞：ZigBee網絡；Cluster-Tree；AODVjr；路由算法；NS-2

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2018）04-00-03

0 引 言

ZigBee技術得益于其距離較短、復雜度較低、能耗較低和成本較低的優勢，不僅適用于無線傳感器網絡領域，在軍事、環境監控、醫療健康、智能家居和工業應用等領域也有著廣泛的應用。

ZigBee協議基于IEEE 802.15.4定義的物理層（PHY）和媒體介質訪問層（MAC）制定，之后ZigBee聯盟在此基礎上對傳輸層（TL）、網絡層（NWK）和應用層（APL）進行了完善[1]。其中，網絡層主要負責網絡的組件、發現新路由及維護已有路由，路由算法是網絡層的核心。

1 ZigBee網絡概述

1.1 ZigBee的網絡拓撲結構

ZigBee網絡通常包括三種網絡拓撲結構：星型拓撲結構、簇樹型拓撲結構和網狀型拓撲結構。其設置可根據不同的實際需求進行變化[2]。常見拓撲結構如圖1所示。

1.2 ZigBee網絡配置

ZigBee聯盟和IEEE 802.15.4對網絡中設備的定義有所區別。根據功能的不同，IEEE 802.15.4將網絡中的設備分為全功能設備（FFD）和精簡功能設備（RFD）[3]。其中，FFD可擔任網絡協調器， 也能用作終端設備，與RFD 或其他FFD通信。而RFD僅支持星型結構，只能與FFD通信。ZigBee聯盟根據設備功能的區別劃分了協調器、路由器和終端設備等。協調器和路由器均為FFD節點，通常網絡最外圍的終端節點由RFD來充當。

1.3 ZigBee網絡地址分配

ZigBee采用分布式尋址方式分配網絡地址[4]。當網絡中的一個節點同意外部節點通過自己加入該網絡時，兩個節點建立父子關系。此后，父節點會為該新入節點分配獨一無二的網絡地址。整個網絡結構的地址分配涉及三個參數：Lm（網絡的最大深度），Cm（每個父節點最多擁有的子節點數量）， Rm（子節點最多可作為路由器節點的個數）[5]。上述3個參數均由協調器決定。

當網絡中的父節點為子節點分配地址時，若d表示父節點的深度，則Cskip（d）地址偏移量可分配地址段的大小為：

首先將協調器深度設為0，則其余節點按照排列順序依次將深度加1。有路由能力的子節點設備分配地址用Cskip（d）表示，依據式（2）進行地址分配，依據式（3）為終端設備進行地址分配：

2 ZigBee路由算法分析

ZigBee網絡層支持樹型（Cluster-Tree），AODVjr和ZBR三種算法 。

2.1 樹型（Cluster-Tree）路由算法

該算法中，當地址為A，深度為d的ZigBee節點收到目的節點地址為D的數據包后，可通過（4）式對該節點的真實性進行驗證，即：

若是，則通過式（5）計算下一跳地址，即：

若不是，則數據包順著樹結構被轉發至父節點。Cluster-Tree算法處理流程如圖2所示。

2.2 AODVjr 路由算法

AODVjr是在AODV基礎上優化路由的發現和維護過程所得[6]。AODVjr和AODV的主要區別如下：

（1）AODVjr路由算法中去掉了AODV路由算法中的目的節點序列號。為了使路由不存在回路，AODVjr路由算法中規定只有目的節點可以進行相應的RREQ分組，即便中間節點有到目的節點的路徑也不可以回復RREQ。

（2）AODVjr路由算法通過目的節點向源節點發送相應連接信息維系路由。若沒有收到目的節點發來的相應信號，則判斷此路徑失效，必要時重新進行路由發現。

（3）AODVjr路由算法中去掉了AODV 中的“先驅節點列表”，以簡化路由表結構。

當源節點中沒有直接到達目的節點的路由時，便會向鄰居節點廣播RREQ包，請求幫忙查詢路徑。當某個節點接收到 RREQ包時，首先會判斷自己是否有到達目的節點的路徑。若有到達的路徑，則會依據路由代價的評估確定是否更新其路由表；若沒有路徑，則接著廣播此RREQ包，同時建立相應的反向路由[7]。AODVjr路由查找模式如圖3所示。

2.3 ZBR算法

ZBR算法既具有Cluster-Tree算法出色的實時性，又保留了AODVjr進行動態路由選擇的優勢，由前兩種算法有機結合而產生[8]。

按照拓撲結構中存儲空間和節點能量的差異，ZBR算法把網絡中的主干節點分為兩類，即RN+節點和RN-節點[9]，且均為全功能節點。RN+節點由于具有高能量和大內存的特點，可以同時運行Cluster-Tree和AODVjr兩種路由算法，而RN-節點只能運行Cluster-Tree一種路由算法[10]。ZBR路由算法處理流程如圖4所示。

3 路由算法的優化策略

Cluster-Tree算法雖然有縮短時延和數據聚合方面的優勢，但也有缺點，即由于非自適應算法的特性，使其在網絡生存時延最大化方面有所不及。而AODVjr算法雖然在路由查找功能方面具有靈活多變的優勢，但因需要維護路由表而產生延遲，且容易產生RREQ廣播風暴。

為此，本文提出了一種簇樹網絡路由策略，即對Cluster-Tree + AODVjr進行優化，該算法融合了上述兩種改進算法的優點。

3.1 簇的建立過程

首先將ZigBee 網絡分成若干簇，通過選定簇首→廣播簇首→建立簇→生成相應調度機制 。

單個簇包括多個節點，根據功能分為3種類型：網關節點、簇成員和簇首。簇建立的規則如下：

（1）將中心節點當作簇首；

（2）充當簇首的節點必須擁有路由能力；

（3）充當簇首的節點網絡深度必須為偶數；

（4）若節點網絡深度為奇數，則屬于其父節點的簇；

（5）終端節點的簇屬于其父節點的簇。

簇首負責在建立路由后進行廣播，建立簇結構，負責對簇成員的數據進行收集，并在融合處理后發送給網關節點。

形成簇之后，判斷網絡深度，若該節點的網絡深度為偶數，則向外廣播RREQ。當一個節點收到RREQ時，便向源節點發送確認信息，發送RREQ的源節點將收到的確認信息與規定的最小信號強度進行比較，若大于該值，則在鄰居表中添加此節點。最后，通過對比鄰居表中周圍節點的數目將節點數最多的節點選作為簇首，同時，將此節點的短地址作為該簇的標簽。

若一個節點被選作簇首節點，則向其周圍節點發送廣播報文，收到廣播報文的節點發送簇加入報文，當簇首發送對應的加入響應后，成功加入到該簇。

3.2 路由過程的建立與維護

當源節點需要給目標節點發送數據時，首先在路由表中查尋目標節點的路徑。若路由存在且有效，則直接發送數據；若路由不存在，則源節點通過泛洪進行路由發現。建立路由后，源節點向周圍節點廣播由其創建的一個路由請求包RREQ。若一個鄰居節點收到RREQ，則通過計算得出目的節點的簇標簽，并將該簇標簽的一個路由接入點加入到其鄰居表中。若一個中間節點收到RREQ，則進行路由成本的比較，若該路由成本較低，則更新路由搜索表信息，并且在到達目的節點之前持續廣播。

當目標節點收到路由請求后，建立反向路徑，并生成一個RREP包，該RREP包中含有最新的各類信息，沿反向路徑送至源節點。當源節點和中間節點收到RREP包后，開始進行目標節點路由的建立和系列號等信息的更新。該路由過程建立完成后，源節點向其簇首發送一個攜帶有路由信息的路由確認包，簇首在收到該確認包后再廣播一個路由更新信息，簇成員收到該信息后，完成節點新建路由信息的共享。

此改進表現出了對分簇思想應用路由算法的巨大優勢，簇頭負責融合數據，減少了數據通信量。同時，分布式算法又可以在拓撲結構得到巨大的施展空間，在大規模網絡場景下有著良好的發揮余地。并且由于簇內節點長時間關閉通信模塊，又達到了網絡時延的效果。

4 實驗結果分析

采用NS-2軟件對改進后的算法和AODVjr進行仿真實驗比較，從發送報文的成功率和平均時延兩個方面進行分析。

報文發送成功率比較如圖5所示，從圖中可以看出，新算法發送報文的成功率與原算法相比有了明顯提升。

兩種算法的平均時延對比如圖6所示。由圖6可知，在源節點數目等同的實驗條件下，隨著節點數目增加，時延呈上升態勢。經分析可知，超過正常范圍數目的源節點增加了網絡擁塞程度，從而增加了成功接收數據包的時間。而在源節點數目相同的情況下，優化后的算法擁有較小時延。

5 結 語

本文在分析ZigBee路由算法的基礎上，提出了一種改進算法。將鄰居列表引入改進后的算法，在數據傳輸過程中，對路由跳數等方面進行了重新考量，同時從基本策略方面對AODVjr進行了改進，考慮到能量的維度，使網絡生存時間得到了有效延長，提升了網絡效率，并通過相關仿真實驗對以上結論進行了驗證。

參考文獻

[1] 唐寅.基于 ZigBee 的傳統路由協議研究與優化 [D]. 武漢：湖北大學，2013.

[2] 耿萌.ZigBee 路由協議研究與分析 [D].鄭州： 中國人民解放軍信息工程大學 ，2006.

[3] 袁安娜.基于 ZigBee 網絡的能量均衡路由算法研究 [D].哈爾濱：哈爾濱理工大學，2014.

[4] 班艷麗，柴喬林，王芳.改進的 ZigBee 網絡路由算法[J].計算機工程與應用，2009，45（5）：95-97.

[5] 凌志浩，周怡頲，鄭麗國.ZigBee無線通信技術及其應用探討[J]. 華東理工大學學報（自然科學版），2006， 32（7）：801-805.

[6] 彭瑜.低功耗、低成本、高可靠性、低復雜度的無線電通信協議——ZigBee[J].自動化儀表，2005，26（5）：1-4.

[7] 鮑鳳卿.基于NS-2的ZigBee網絡節點接入的研究[J].信息技術，2008，11（5）：95-98.

[8] 錢志鴻，朱爽，王雪.基于分簇機制的 ZigBee 混合路由能量優化算法[J].計算機學報，2013， 36（3）：485-493.

[9] 吳非.基于ZigBee技術的無線傳感器網絡路由算法研究[D].北京：北京郵電大學，2015.

[10] 蔣培成，陳鳴，李兵.一種優化ZigBee性能的綜合加權路由算法[J].小微型計算機系統，2013，34（9）：2014-2017.

[11] CHEN S K，WANG P C.Shortcut anycast tree Routing in MANETs[J].IEEE international conference on advanced information networking & applications，2012，11（1）：635-640.

[12] FENG S，WANG M G，Yu Q L，et al.Improved neighbor table-based tree routing strategies in ZigBee wireless networks[C]. International Conference on Information Science & Technology，2015 ： 513-518.

[13] HOU T C，TSAI T J.An Access based clustering protocol for multihop wireless Ad-Hoc networks[J].IEEE joumal on selected areas in communications，2001，19（7）：1201-1210.