白樂強(qiáng)，孫晶晶，楊 晰

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

0 引 言

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

針對上述問題，本文在樹路由算法基礎(chǔ)上，提出一種基于鄰居表的ZigBee網(wǎng)絡(luò)樹路由改進(jìn)算法。該算法借助一跳鄰居節(jié)點地址信息，對下一跳轉(zhuǎn)發(fā)節(jié)點的選擇進(jìn)行了深入的研究。

1 樹路由算法分析

ZigBee網(wǎng)絡(luò)節(jié)點設(shè)備主要可以分為：協(xié)調(diào)器、路由設(shè)備和終端設(shè)備這3種［1］。

1.1 地址分配

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

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

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

1.2 鄰居表

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

LQI表示接收數(shù)據(jù)幀的能量與質(zhì)量的一個指標(biāo)。IEEE802.15.4標(biāo)準(zhǔn)將LQI定義為接收幀的強(qiáng)度和／或質(zhì)量特性表征，該標(biāo)準(zhǔn)將LQI的值限定在0～255范圍內(nèi)，LQI值越高表明鏈路質(zhì)量越好，傳輸性能越好，鏈路越可靠［9］。

1.3 樹路由算法

在樹路由算法中，網(wǎng)絡(luò)中的節(jié)點根據(jù)目的節(jié)點的網(wǎng)絡(luò)地址計算下一跳。當(dāng)深度為d、地址為A 的節(jié)點向目的地址為D 的節(jié)點傳送數(shù)據(jù)時，樹路由算法先判斷目的節(jié)點是否為該節(jié)點的后代節(jié)點。若目的節(jié)點D 是節(jié)點A 的后代節(jié)點，將數(shù)據(jù)包轉(zhuǎn)發(fā)到相應(yīng)節(jié)點上。判斷目的節(jié)點D 為節(jié)點A 的后代節(jié)點需滿足條件

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

若目的節(jié)點D 不是節(jié)點A 的后代節(jié)點，則按照樹型結(jié)構(gòu)將數(shù)據(jù)包轉(zhuǎn)發(fā)給節(jié)點A 的父節(jié)點［10］。

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

2 改進(jìn)算法策略

該算法借助鄰居表，進(jìn)一步減少路由跳數(shù)，避免出現(xiàn)網(wǎng)絡(luò)中不必要節(jié)點浪費(fèi)的問題，綜合考慮節(jié)點LQI值，有效提高網(wǎng)絡(luò)性能。算法中將收到數(shù)據(jù)包的節(jié)點記為當(dāng)前節(jié)點。

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

表1 算法中的符號定義

鄰居節(jié)點選擇策略為：

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

依據(jù)ZigBee地址分配機(jī)制，依次查找 （M1，M2，…，Mk－1，Mk，…，MJ－I）對應(yīng)的鄰居節(jié)點與目的節(jié)點最大深度的公共父輩節(jié)點，直至查找到鄰居節(jié)點與目的節(jié)點最大深度的公共父輩節(jié)點地址為0即為協(xié)調(diào)器為止。若Mk對應(yīng)此鄰居節(jié)點，依據(jù)ZigBee 地址分配機(jī)制的特點，可知（M1，M2，…，Mk－1）對應(yīng)的鄰居節(jié)點與目的節(jié)點最大深度的公共父輩節(jié)點不為協(xié)調(diào)器，而 （Mk，…，MJ－I）對應(yīng)的鄰居節(jié)點與目的節(jié)點最大深度的公共父輩節(jié)點為協(xié)調(diào)器。依據(jù)樹型拓?fù)浣Y(jié)構(gòu)的特點，可知 （Mk，…，MJ－I）對應(yīng)的鄰居節(jié)點到達(dá)目的節(jié)點的樹路由跳數(shù)分別大于 （M1，M2，…，Mk－1）對應(yīng)的鄰居節(jié)點到達(dá)目的節(jié)點的樹路由跳數(shù)。在 （M1，M2，…，Mk－1）對應(yīng)的鄰居節(jié)點中，構(gòu)成到達(dá)目的節(jié)點的樹路由跳數(shù)最少的節(jié)點集合B，將集合B 的樹路由跳數(shù)與按樹型結(jié)構(gòu)所得的樹路由跳數(shù)進(jìn)行比較。在當(dāng)前節(jié)點的鄰居節(jié)點中，選擇到達(dá)目的節(jié)點樹路由跳數(shù)最少的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點。

改進(jìn)算法步驟如下：

步驟1 判斷當(dāng)前節(jié)點本身是否為目的節(jié)點。

若是則接收數(shù)據(jù)包，否則轉(zhuǎn)向步驟2。

步驟2 判斷當(dāng)前節(jié)點的一跳鄰居節(jié)點是否存有目的節(jié)點。

若存在則直接發(fā)送數(shù)據(jù)包，否則轉(zhuǎn)向步驟3。

步驟3 按樹型結(jié)構(gòu)，在節(jié)點Ai中尋找到達(dá)目的節(jié)點樹路由跳數(shù)最少的一個節(jié)點。

步驟3.1 利用式 （4）判斷當(dāng)前節(jié)點的后代節(jié)點是否存在目的節(jié)點。

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

步驟3.2 按照樹型結(jié)構(gòu)選擇當(dāng)前節(jié)點的父節(jié)點Ai作為到達(dá)目的節(jié)點樹路由跳數(shù)最少的節(jié)點。根據(jù)ZigBee地址分配機(jī)制找出當(dāng)前節(jié)點的父節(jié)點與目的節(jié)點最大深度的公共父輩節(jié)點，利用式 （6）計算TRC（Ai，D），轉(zhuǎn)向步驟4。

步驟4 在鄰居節(jié)點Aj中，利用式 （6）計算TRC（Aj，D），構(gòu)成min TRC（Aj，D）對應(yīng)的鄰居節(jié)點集合B。

步驟4.1 依次找出與 （M1，M2，…，MJ－I）對應(yīng)的鄰居節(jié)點。

步驟4.2 根據(jù)ZigBee地址分配機(jī)制找到M1對應(yīng)的鄰居節(jié)點與目的節(jié)點最大深度的公共父輩節(jié)點，判斷這兩節(jié)點最大深度的公共父輩節(jié)點是否為協(xié)調(diào)器。

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

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

步驟5.1 當(dāng)min TRC（Aj，D）＝TRC（Ai，D）時，選取集合C，轉(zhuǎn)向步驟6。

步驟5.2 當(dāng)min TRC（Aj，D）＞TRC（Ai，D）時，那么選擇節(jié)點Ai作為下一跳轉(zhuǎn)發(fā)節(jié)點，將數(shù)據(jù)包傳送給這一節(jié)點。

步驟5.3 當(dāng)min TRC（Aj，D）＜TRC（Ai，D）時，選取集合B，轉(zhuǎn)向步驟6。

步驟6 在步驟5得出的節(jié)點集合中，選取LQI值大的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點，將數(shù)據(jù)包傳送給這一節(jié)點。

該算法按照樹路由跳數(shù)最少原則選擇下一跳轉(zhuǎn)發(fā)節(jié)點，直至將數(shù)據(jù)包傳送到目的節(jié)點為止。

3 改進(jìn)算法理論分析

改進(jìn)算法通過建立鄰居節(jié)點選擇策略，在節(jié)點的一跳鄰居節(jié)點中，選擇到到達(dá)目的節(jié)點樹路由跳數(shù)最少的鄰居節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點，優(yōu)化數(shù)據(jù)傳輸路徑。為驗證改進(jìn)算法能夠選擇到路由跳數(shù)更少的路徑，借助表2中定義的符號分析并比較改進(jìn)算法、樹路由算法和ITRA 算法在傳送數(shù)據(jù)時路徑路由跳數(shù)的多少。

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

圖1分別為數(shù)據(jù)包按樹路由算法、ITRA 算法及改進(jìn)算法從源節(jié)點S 到達(dá)目的節(jié)點D 所經(jīng)過的路由路徑。在樹路由算法中，數(shù)據(jù)包從源節(jié)點S 到達(dá)目的節(jié)點D 所經(jīng)過的樹路由路徑為 （S，Ai（1），Ai（2），Ai（3），...，Ai（t），...，Ai（P），D），其中源節(jié)點S 到達(dá)目的節(jié)點D 的樹路由跳數(shù)為P＋1。

根據(jù)ZigBee網(wǎng)絡(luò)樹型結(jié)構(gòu)的特點可得出式 （7）

在改進(jìn)算法中，數(shù)據(jù)包從源節(jié)點S 到達(dá)目的節(jié)點D 所經(jīng) 過 的 路 徑 為 （S，Ay（1），Ay（2），...，Ay（t），...，Ay（t＋q），D），q為常數(shù)且q≥1。此時源節(jié)點到達(dá)目的節(jié)點的路由跳數(shù)為t＋q＋1。根據(jù)改進(jìn)算法特性可得出式 （8）

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

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

圖1 ZigBee網(wǎng)絡(luò)樹路由算法路由路徑

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

理論分析結(jié)果表明，改進(jìn)算法能夠?qū)ふ业奖葮渎酚伤惴ê虸TRA 算法路由跳數(shù)更少的路徑。

4 仿真結(jié)果與分析

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

如圖2所示，隨著網(wǎng)絡(luò)節(jié)點數(shù)目不斷增加，節(jié)點傳輸數(shù)據(jù)所經(jīng)過的路由跳數(shù)逐漸增多，改進(jìn)算法的路由平均路由跳數(shù)少于樹路由算法和ITRA 算法。改進(jìn)算法考慮鄰居表中節(jié)點地址信息，利用鄰居節(jié)點選擇策略，在當(dāng)前節(jié)點的鄰居節(jié)點中，能夠選取到達(dá)目的節(jié)點樹路由跳數(shù)更少的節(jié)點作為下一跳節(jié)點，進(jìn)一步優(yōu)化數(shù)據(jù)傳輸路徑。

圖2 平均路由跳數(shù)對比

如圖3所示，隨著網(wǎng)絡(luò)節(jié)點數(shù)目不斷增加，改進(jìn)算法的源節(jié)點到目的節(jié)點的延時少于樹路由算法和ITRA 算法。源節(jié)點到目的節(jié)點的端到端延時受源節(jié)點到目的節(jié)點路由跳數(shù)的多少影響，減少算法路由跳數(shù)，能夠有效減少端到端的延時。

如圖4所示，隨著網(wǎng)絡(luò)節(jié)點密度增大，信號干擾程度變強(qiáng)，傳輸路徑路由跳數(shù)增多，改進(jìn)算法中數(shù)據(jù)包從源節(jié)點成功到達(dá)目的節(jié)點的數(shù)目高于樹路由算法和ITRA 算法。數(shù)據(jù)包發(fā)送成功率高與否，主要受信號干擾程度、傳輸路徑路由跳數(shù)等因素影響。該算法綜合考慮節(jié)點LQI值的因素，選取LQI值大的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，進(jìn)一步提高數(shù)據(jù)包送達(dá)率。

圖3 端到端延時對比

圖4 數(shù)據(jù)包送達(dá)率對比

5 結(jié)束語

本文提出一種基于鄰居表的ZigBee網(wǎng)絡(luò)樹路由改進(jìn)算法。該算法利用鄰居表中節(jié)點信息和樹型拓?fù)浣Y(jié)構(gòu)的特點，選取到達(dá)目的節(jié)點樹路由跳數(shù)最少的鄰居節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點。當(dāng)出現(xiàn)多條樹路由跳數(shù)相同的路徑時，選取LQI值大的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點。理論分析結(jié)果表明，該算法路由路徑優(yōu)于樹路由算法和ITRA 算法。仿真結(jié)果表明，該算法有效減少了網(wǎng)絡(luò)中路由跳數(shù)和數(shù)據(jù)傳輸延時，提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸可靠性。該算法無需存儲路由表，適用于資源受限的無線傳感器網(wǎng)絡(luò)。

［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傳感網(wǎng)絡(luò)Cluster－Tree改進(jìn)路由算法研究 ［J］.傳感技術(shù)學(xué)報，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路由算法優(yōu)化 ［J］.計算機(jī)工程與設(shè)計，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）. ［彭設(shè)強(qiáng)，王為.ZigBee網(wǎng)路中Cluster－Tree路由算法優(yōu)化 ［J］.數(shù)字技術(shù)與應(yīng)用，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ìn) ［J］.合肥工業(yè)大學(xué)學(xué)報 （自然科學(xué)版），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）.［李剛，陳俊杰，葛文濤.一種改進(jìn)的ZigBee 網(wǎng)絡(luò)Cluster－Tree路由算法 ［J］.測控技術(shù)，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）.［徐沛成，胡國榮.改進(jìn)的Zig－Bee網(wǎng)絡(luò)路由算法 ［J］.計算機(jī)工程與設(shè)計，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網(wǎng)絡(luò)樹路由改進(jìn)算法 ［J］.吉林大學(xué)學(xué)報 （工學(xué)版），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網(wǎng)絡(luò)的借地址分配算法 ［J］.計算機(jī)應(yīng)用，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.