基于鄰居表的ZigBee網絡樹路由改進算法

白樂強，孫晶晶，楊 晰

（沈陽建筑大學 信息與控制工程學院，遼寧 沈陽110168）

0 引 言

ZigBee網絡技術是一種具有短距離、低能耗、復雜度低、數據傳輸量低等特點的無線網絡技術［1］。AODVjr［2，3］算法是針對AODV［4］算法的改進，能夠找到一條較優路徑，但該算法具有很高的控制開銷。樹路由算法［5］適用于存儲能力受限的節點，算法簡單且無需存儲路由表，有效節省了網絡存儲資源，然而該算法往往產生較大的路徑成本。ITRA［6］算法能夠找到一條相對于樹路由算法較優的路徑，但ITRA 算法沒有考慮節點收到數據包后，其鄰居節點到達目的節點是否存在多條樹路由跳數相同的傳輸路徑及在樹路由跳數相同時如何選取最優下一跳轉發節點等因素。針對樹路由算法的改進算法［7］，能夠找到一條較優的路徑，但該算法將所有鄰居節點到達目的節點的樹路由跳數全部計算出來進行比較，選取最小，導致工作量的增大。

針對上述問題，本文在樹路由算法基礎上，提出一種基于鄰居表的ZigBee網絡樹路由改進算法。該算法借助一跳鄰居節點地址信息，對下一跳轉發節點的選擇進行了深入的研究。

1 樹路由算法分析

ZigBee網絡節點設備主要可以分為：協調器、路由設備和終端設備這3種［1］。

1.1 地址分配

ZigBee網絡采用一種分布式地址分配機制，為每個網絡設備分配唯一的網絡地址［8］。其中Cm為最大子節點數，這些子節點最多可擁有Rm個路由節點，Lm為整個網絡的最大深度［1］。Cskip（d）表示網絡深度為d 的父節點為其子節點分配的地址偏移量。網絡深度為d 且地址為Aparent的父節點，它分給它的第n個路由子節點地址An應滿足為

分給它的第m 個終端節點地址Am滿足

路由節點所能分配的地址空間Cskip（d）滿足

1.2 鄰居表

ZigBee協議對鄰居表及鄰居節點進行了規定［1］。若兩節點在一跳范圍之內可以直接進行通信我們就可以將這兩節點稱為鄰居。根據用戶需要，可人為去增添鄰居表中一些基本信息的內容，例如鏈路質量指標 （link quality indicator，LQI）值等。

LQI表示接收數據幀的能量與質量的一個指標。IEEE802.15.4標準將LQI定義為接收幀的強度和／或質量特性表征，該標準將LQI的值限定在0～255范圍內，LQI值越高表明鏈路質量越好，傳輸性能越好，鏈路越可靠［9］。

1.3 樹路由算法

在樹路由算法中，網絡中的節點根據目的節點的網絡地址計算下一跳。當深度為d、地址為A 的節點向目的地址為D 的節點傳送數據時，樹路由算法先判斷目的節點是否為該節點的后代節點。若目的節點D 是節點A 的后代節點，將數據包轉發到相應節點上。判斷目的節點D 為節點A 的后代節點需滿足條件

在滿足式 （4）的前提下，節點A 下一跳節點地址N 為

若目的節點D 不是節點A 的后代節點，則按照樹型結構將數據包轉發給節點A 的父節點［10］。

在ZigBee網絡中，采用樹路由算法根據ZigBee地址分配機制可得到源節點和目的節點最大深度的公共父輩節點，將其網絡深度用MaxDepth 表示。用DstDepth、SrcDepth和HopCount分別表示目的節點、源節點的網絡深度和路由跳數，根據樹路由算法可得路由跳數［11］HopCount

2 改進算法策略

該算法借助鄰居表，進一步減少路由跳數，避免出現網絡中不必要節點浪費的問題，綜合考慮節點LQI值，有效提高網絡性能。算法中將收到數據包的節點記為當前節點。

算法中的符號定義見表1。

表1 算法中的符號定義

鄰居節點選擇策略為：

當前節點利用│D－Aj│從小到大依次計算出Mk的值即 （M1，M2，…，Mk，…，MJ－I）。

依據ZigBee地址分配機制，依次查找 （M1，M2，…，Mk－1，Mk，…，MJ－I）對應的鄰居節點與目的節點最大深度的公共父輩節點，直至查找到鄰居節點與目的節點最大深度的公共父輩節點地址為0即為協調器為止。若Mk對應此鄰居節點，依據ZigBee 地址分配機制的特點，可知（M1，M2，…，Mk－1）對應的鄰居節點與目的節點最大深度的公共父輩節點不為協調器，而 （Mk，…，MJ－I）對應的鄰居節點與目的節點最大深度的公共父輩節點為協調器。依據樹型拓撲結構的特點，可知 （Mk，…，MJ－I）對應的鄰居節點到達目的節點的樹路由跳數分別大于 （M1，M2，…，Mk－1）對應的鄰居節點到達目的節點的樹路由跳數。在 （M1，M2，…，Mk－1）對應的鄰居節點中，構成到達目的節點的樹路由跳數最少的節點集合B，將集合B 的樹路由跳數與按樹型結構所得的樹路由跳數進行比較。在當前節點的鄰居節點中，選擇到達目的節點樹路由跳數最少的節點作為下一跳轉發節點。

改進算法步驟如下：

步驟1 判斷當前節點本身是否為目的節點。

若是則接收數據包，否則轉向步驟2。

步驟2 判斷當前節點的一跳鄰居節點是否存有目的節點。

若存在則直接發送數據包，否則轉向步驟3。

步驟3 按樹型結構，在節點Ai中尋找到達目的節點樹路由跳數最少的一個節點。

步驟3.1 利用式 （4）判斷當前節點的后代節點是否存在目的節點。

若存在則利用式 （5）選擇相應的子節點Ai作為到達目的節點樹路由跳數最少的節點。根據ZigBee地址分配機制找出相應的子節點與目的節點最大深度的公共父輩節點，利用式 （6）計算TRC（Ai，D），轉向步驟4；否則轉向步驟3.2。

步驟3.2 按照樹型結構選擇當前節點的父節點Ai作為到達目的節點樹路由跳數最少的節點。根據ZigBee地址分配機制找出當前節點的父節點與目的節點最大深度的公共父輩節點，利用式 （6）計算TRC（Ai，D），轉向步驟4。

步驟4 在鄰居節點Aj中，利用式 （6）計算TRC（Aj，D），構成min TRC（Aj，D）對應的鄰居節點集合B。

步驟4.1 依次找出與 （M1，M2，…，MJ－I）對應的鄰居節點。

步驟4.2 根據ZigBee地址分配機制找到M1對應的鄰居節點與目的節點最大深度的公共父輩節點，判斷這兩節點最大深度的公共父輩節點是否為協調器。

若M1對應的鄰居節點與目的節點最大深度的公共父輩節點是協調器，利用式 （6）依次計算 （M1，M2，…，MJ－I）對應的鄰居節點到達目的節點的樹路由跳數，直至鄰居表中的節點Aj計算完畢，構成min TRC（Aj，D）對應的鄰居節點集合B，轉向步驟5；否則依次查找 （M2，…，MJ－I）對應的鄰居節點與目的節點最大深度的公共父輩節點，直至判斷出鄰居節點與目的節點最大深度的公共父輩節點為協調器或鄰居表中的節點Aj計算完畢。利用式（6）分別計算所有符合條件的鄰居節點到達目的節點的樹路由跳數，構成min TRC（Aj，D）對應的鄰居節點集合B，轉向步驟5。

步驟5 比較min TRC（Aj，D）與TRC（Ai，D），選取到達目的節點樹路由跳數最少的節點集合。

步驟5.1 當min TRC（Aj，D）＝TRC（Ai，D）時，選取集合C，轉向步驟6。

步驟5.2 當min TRC（Aj，D）＞TRC（Ai，D）時，那么選擇節點Ai作為下一跳轉發節點，將數據包傳送給這一節點。

步驟5.3 當min TRC（Aj，D）＜TRC（Ai，D）時，選取集合B，轉向步驟6。

步驟6 在步驟5得出的節點集合中，選取LQI值大的節點作為下一跳轉發節點，將數據包傳送給這一節點。

該算法按照樹路由跳數最少原則選擇下一跳轉發節點，直至將數據包傳送到目的節點為止。

3 改進算法理論分析

改進算法通過建立鄰居節點選擇策略，在節點的一跳鄰居節點中，選擇到到達目的節點樹路由跳數最少的鄰居節點作為下一跳轉發節點，優化數據傳輸路徑。為驗證改進算法能夠選擇到路由跳數更少的路徑，借助表2中定義的符號分析并比較改進算法、樹路由算法和ITRA 算法在傳送數據時路徑路由跳數的多少。

表2 理論分析中的符號定義

圖1分別為數據包按樹路由算法、ITRA 算法及改進算法從源節點S 到達目的節點D 所經過的路由路徑。在樹路由算法中，數據包從源節點S 到達目的節點D 所經過的樹路由路徑為 （S，Ai（1），Ai（2），Ai（3），...，Ai（t），...，Ai（P），D），其中源節點S 到達目的節點D 的樹路由跳數為P＋1。

根據ZigBee網絡樹型結構的特點可得出式 （7）

在改進算法中，數據包從源節點S 到達目的節點D 所經 過 的 路 徑 為 （S，Ay（1），Ay（2），...，Ay（t），...，Ay（t＋q），D），q為常數且q≥1。此時源節點到達目的節點的路由跳數為t＋q＋1。根據改進算法特性可得出式 （8）

根據式 （7）和式 （8），可推出t＋q≤P。通過不等式定理，可得 （t＋q＋1）≤ （P＋1）即改進算法的路徑優于樹路由算法路由路徑。

在ITRA 算法中，數據包從源節點S 到達目的節點D所 經 過 的 路 徑 為 （S，Ax（1），Ax（2），...，Ax（t），...，Ax（t＋r），D），其中r為常數且r≥1。此時源節點到達目的節點的路由跳數為t＋r＋1。ITRA算法利用min｛│D－Ai│，│D－Aj│｝尋找對應的鄰居節點，將min ｛│D－Ai│，│D－Aj│｝對應的鄰居節點到達目的節點的樹路由跳數與TRC （Ai，D）進行比較，選取兩者之間樹路由跳數較少的鄰居節點作為下一跳轉發節點，該算法在鄰居節點中所選的下一跳轉發節點不一定是到達目的節點樹路由跳數最少的節點。改進算法通過建立鄰居節點選擇策略，在節點的一跳鄰居節點中，能夠選擇到到達目的節點樹路由跳數最少的鄰居節點作為下一跳轉發節點，可得出式 （9）

圖1 ZigBee網絡樹路由算法路由路徑

根據式 （7）和式 （9），可推出t＋q≤t＋r。通過不等式定理，可得 （t＋q＋1）≤ （t＋r＋1）即改進算法的路徑優于ITRA 算法路由路徑。

理論分析結果表明，改進算法能夠尋找到比樹路由算法和ITRA 算法路由跳數更少的路徑。

4 仿真結果與分析

為驗證改進算法的性能，針對數據傳輸平均路由跳數、源節點到目的節點的端到端延時及數據包發送成功率這三方面進行仿真，并與樹路由算法和ITRA 算法進行對比。本文采用MATLAB平臺對改進算法、樹路由算法和ITRA算法進行實驗仿真。實驗仿真參數：選取Cm＝6、Rm＝6、Lm＝4，利用式 （1）～式 （3）搭建一個網絡范圍為100m×100m、節點個數為300、最大傳輸距離為25m 的ZigBee網絡，其中數據包大小為80bytes、數據流類型為CBR、發送數據包的速率為1包／s以及仿真時間設為200s。試驗選取50、100、150、200、250、300ZigBee節點數量規模的網絡場景，實驗中每種場景的仿真數據均是獨立運行100次后求取的平均值。

如圖2所示，隨著網絡節點數目不斷增加，節點傳輸數據所經過的路由跳數逐漸增多，改進算法的路由平均路由跳數少于樹路由算法和ITRA 算法。改進算法考慮鄰居表中節點地址信息，利用鄰居節點選擇策略，在當前節點的鄰居節點中，能夠選取到達目的節點樹路由跳數更少的節點作為下一跳節點，進一步優化數據傳輸路徑。

圖2 平均路由跳數對比

如圖3所示，隨著網絡節點數目不斷增加，改進算法的源節點到目的節點的延時少于樹路由算法和ITRA 算法。源節點到目的節點的端到端延時受源節點到目的節點路由跳數的多少影響，減少算法路由跳數，能夠有效減少端到端的延時。

如圖4所示，隨著網絡節點密度增大，信號干擾程度變強，傳輸路徑路由跳數增多，改進算法中數據包從源節點成功到達目的節點的數目高于樹路由算法和ITRA 算法。數據包發送成功率高與否，主要受信號干擾程度、傳輸路徑路由跳數等因素影響。該算法綜合考慮節點LQI值的因素，選取LQI值大的節點轉發數據，進一步提高數據包送達率。

圖3 端到端延時對比

圖4 數據包送達率對比

5 結束語

本文提出一種基于鄰居表的ZigBee網絡樹路由改進算法。該算法利用鄰居表中節點信息和樹型拓撲結構的特點，選取到達目的節點樹路由跳數最少的鄰居節點作為下一跳轉發節點。當出現多條樹路由跳數相同的路徑時，選取LQI值大的節點作為下一跳轉發節點。理論分析結果表明，該算法路由路徑優于樹路由算法和ITRA 算法。仿真結果表明，該算法有效減少了網絡中路由跳數和數據傳輸延時，提高了網絡數據傳輸可靠性。該算法無需存儲路由表，適用于資源受限的無線傳感器網絡。

［1］ZigBee Alliance.ZigBee specification ［S］.2008.

［2］HE Lingling.An improved Cluster－Tree routing algorithm in ZigBee networks［J］.Chinese Journal of Sensors and Actuators，2010，23 （9）：1303－1307 （in Chinese）.［賀玲玲.ZigBee傳感網絡Cluster－Tree改進路由算法研究 ［J］.傳感技術學報，2010，23 （9）：1303－1307.］

［3］LI Yudong，HUANG Hongguang，XIANG Xixi.Improved ZigBee routing algorithm based on energy balance ［J］.Computer Engineering and Design，2011，32 （2）：397－400 （in Chinese）. ［李予東，黃宏光，向西西.基于能量均衡的Zig－Bee路由算法優化 ［J］.計算機工程與設計，2011，32 （2）：397－400.］

［4］WANG Jun，CHEN Min，Victor CM Leung.Forming priority based and energy balanced ZigBee networks a pricing approach［J］.Telecommun Syst，2013：1281－1292.

［5］PENG Sheqiang，WANG Wei.Cluster－tree routing algorithm optimization ZigBee network ［J］.Digital Technology and Application，2012 （4）：112－113 （in Chinese）. ［彭設強，王為.ZigBee網路中Cluster－Tree路由算法優化 ［J］.數字技術與應用，2012 （4）：112－113.］

［6］QI Jianchao，WEI Zhen.An improved tree－based routing algorithm for ZigBee［J］.Journal of Hefei University of Technology，2010，33 （4）：529－532 （in Chinese）. ［戚劍超，魏臻.ZigBee樹型路由算法的改進 ［J］.合肥工業大學學報 （自然科學版），2010，33 （4）：529－532.］

［7］LI Gang，CHEN Junjie，GE Wentao.An improved Cluster－Tree routing algorithm in ZigBee networks ［J］.Observation and Control Technology，2009，28 （9）：52－55 （in Chinese）.［李剛，陳俊杰，葛文濤.一種改進的ZigBee 網絡Cluster－Tree路由算法 ［J］.測控技術，2009，28 （9）：52－55.］

［8］XU Peicheng，HU Guorong.Improved ZigBee network routing algorithm ［J］.Computer Engineering and Design，2013，34（9）：3019－3023 （in Chinese）.［徐沛成，胡國榮.改進的Zig－Bee網絡路由算法 ［J］.計算機工程與設計，2013，34 （9）：3019－3023.］

［9］LIU Dan，QIAN Zhihong，LIU Ying.Tree routing improvement algorithm in ZigBee network ［J］.Journal of Jilin University （Engineering and Technology Edition），2010，40 （5）：1392－1396 （in Chinese）.［劉丹，錢志鴻，劉影.ZigBee網絡樹路由改進算法 ［J］.吉林大學學報 （工學版），2010，40（5）：1392－1396.］

［10］YAO Yukun，LI Pengxiang，REN Zhi，et al.Borrowed address assignment algorithm for ZigBee network ［J］.Computer applications，2011，31 （8）：2044－2047 （in Chinese）.［姚玉坤，李鵬翔，任智，等.適用于ZigBee網絡的借地址分配算法 ［J］.計算機應用，2011，31 （8）：2044－2047.］

［11］Taehong Kim，Seong Hoon Kim，Yang Jinyoung，et al.Neighbor table based shortcut tree routing in ZigBee wireless networks［J］.IEEE Transactions on Parallel and Distributed Systems，2014，25 （3）：706－716.