資源受限設(shè)備的ZigBee樹路由協(xié)議改進(jìn)算法研究

喻先強(qiáng)，葉建芳

（東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海201620）

資源受限設(shè)備的ZigBee樹路由協(xié)議改進(jìn)算法研究

喻先強(qiáng)，葉建芳

（東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海201620）

ZigBee提供的自由表樹路由算法與IEEE802.15.4標(biāo)準(zhǔn)的資源受限設(shè)備尋址方案，只適用于有限大小的對稱樹網(wǎng)絡(luò)。本文提出了一種高效的路由算法和一個基于前綴碼的靈活的、可變長度的尋址方案。該方案消除了路由表，并且不限制網(wǎng)絡(luò)的規(guī)模，允許設(shè)備擁有任意數(shù)的子節(jié)點(diǎn)；利用簡單的數(shù)學(xué)與/或邏輯等式來決定路由，并可以適用幾乎所有類型的樹狀網(wǎng)絡(luò)。理論分析和仿真結(jié)果表明，這種靈活的機(jī)制大大降低了成本開銷。

ZigBee；樹網(wǎng)絡(luò)；地址；路由；前綴碼

0 引言

ZigBee提供了資源受限的、簡單的、輕量級的自由表樹路由算法。ZigBee網(wǎng)絡(luò)的路由協(xié)議基本上是樹路由（用于樹型拓?fù)浣Y(jié)構(gòu)）和按需距離矢量（AODV）路由（用于網(wǎng)狀拓?fù)浣Y(jié)構(gòu)）的組合。在參考文獻(xiàn)[1]中，提出一種基于移動IP的路由算法，該地址借用方案可以應(yīng)用到增長超過16跳的網(wǎng)絡(luò)，并通過地址借用克服地址耗盡的問題。參考文獻(xiàn)[2]提出一種針對不對稱網(wǎng)路的擴(kuò)展ZigBee樹路由算法，該算法利用對應(yīng)網(wǎng)絡(luò)深度的地址數(shù)來分配地址。在參考文獻(xiàn)[3]中，提出一種統(tǒng)一的多路通道路由方案，該方案應(yīng)用于樹狀網(wǎng)絡(luò)，使網(wǎng)絡(luò)能夠在動態(tài)空間中使用，并克服由多通道且不增加任何額外開銷的路由表引起的中斷問題。在參考文獻(xiàn)[4]中，提出基于ZigBee無線網(wǎng)絡(luò)鄰居表的捷徑樹路由算法，該算法延伸了ZigBee樹路由，但網(wǎng)絡(luò)深度的問題仍然存在且只適用于對稱樹網(wǎng)絡(luò)。路由協(xié)議的性能評價是ZigBee網(wǎng)絡(luò)研究的核心問題，這些路由協(xié)議用于處理無線網(wǎng)絡(luò)的低寬帶、高錯誤率、能源和內(nèi)存受限等問題。在參考文獻(xiàn)[5]中，通過對這些協(xié)議的分析研究可以發(fā)現(xiàn)，在IEEE802.15.4/ZigBee中對路由算法改進(jìn)的研究相對缺乏。

本文針對ZigBee無線網(wǎng)絡(luò)的地址分配限制、網(wǎng)絡(luò)規(guī)模、成本開銷等問題，提出了一種基于前綴碼的可變長度的編址方案與路由改進(jìn)算法。該算法利用前綴碼的性能，不使用任何路由表，而僅使用數(shù)學(xué)與/或邏輯等式來決定路由。理論分析和仿真結(jié)果表明，該方案大大降低了成本開銷，同時該路由算法可用于對稱以及非對稱的大型網(wǎng)絡(luò)，且對ZigBee網(wǎng)絡(luò)直徑?jīng)]有任何限制。

1 ZigBee地址分配限制

ZigBee分布式地址分配方案的關(guān)鍵是ZigBee的“協(xié)調(diào)器確定”，ZigBee協(xié)調(diào)器確定有幾個重要的網(wǎng)絡(luò)參數(shù)：Cm，Rm和Lm（Cm為協(xié)調(diào)器數(shù)量，Rm為路由器數(shù)量，Lm為網(wǎng)絡(luò)深度），但如何確定這些參數(shù)仍然沒有有效方法。不當(dāng)?shù)腃m和Rm參數(shù)可能導(dǎo)致網(wǎng)絡(luò)地址的浪費(fèi)，原因是所有路由器使用相同的Cm和Rm，并且一次選擇以后保持不變。對于較大的Lm值，大量子地址未使用的可能性非常大。假設(shè)Cm=4，Rm=2，Lm=14，則深度為1的路由器R能夠分發(fā)到其每2個子路由器的地址數(shù)是Cskip（1）=16 381。由于路由器R最多能夠有兩個終端設(shè)備和兩個子路由器，地址總數(shù)就可以分發(fā)到2+2×16 381=32 764。如果路由器R沒有子路由器，則路由器R分布的大量地址將無法使用，這直接意味著可能將浪費(fèi)掉大約總數(shù)216（65 536，對于16位地址）的50%的地址。對于Cm=4，Rm=3，由式（1）[6]計算可得Lm的最大值為9，這意味著沒有設(shè)備可以存在于深度超過9的地方。

另一個主要問題是尋址方案本質(zhì)上限制了網(wǎng)絡(luò)的深度。假設(shè)Cskip（0）是地址子塊由協(xié)調(diào)器（深度0）分配給每個路由器Rm的分布式地址，分配到所有路由器總的地址數(shù)是RmCskip（0），則所有可能的地址是RmCskip（0）、終端協(xié)調(diào)器設(shè)備Em（Em=Cm-Rm）的數(shù)目和本身地址的總和。例如，如果Cm=8，Rm=4，最大可能的深度只有Lm=7。

2 改進(jìn)方案

ZigBee設(shè)備要求更低的成本和功耗，則帶來的結(jié)果是相應(yīng)的資源受到限制。因此，提出的路由算法必須能夠在資源受限設(shè)備上有效地運(yùn)行。本文提出的改進(jìn)路由算法消除了路由表，它只需要非常小的內(nèi)存來運(yùn)行，同時也消除了在數(shù)據(jù)包中放置路由信息的開銷。該路由算法是基于前綴碼的尋址方案，解決了ZigBee網(wǎng)絡(luò)地址分配限制和由于重組帶來的成本開銷等問題。

2.1 網(wǎng)絡(luò)地址分配

該改進(jìn)方案可以智能地分配網(wǎng)絡(luò)地址到相應(yīng)設(shè)備，且到達(dá)目標(biāo)設(shè)備的路由能夠僅從目的地址就可以確定。如圖1所示的樹圖，地址計算如下：在樹中每個路由器通過一個唯一的二進(jìn)制數(shù)來標(biāo)識，如果路由器R有CR個子節(jié)點(diǎn)，則連接到路由器R的最小數(shù)量位N（CR）為[7]：

樹中每個節(jié)點(diǎn)的唯一網(wǎng)絡(luò)地址計算如下：根節(jié)點(diǎn)（協(xié)調(diào)器）的地址總是1，其他設(shè)備D的地址AD通過連接其父節(jié)點(diǎn)的地址ID來獲得。例如，圖1中路由器R8的地址是AR8=101101。這里，1011是R7的地址，01是連接R7到R8的標(biāo)號。其他設(shè)備的地址也是據(jù)此計算。

圖1 網(wǎng)絡(luò)地址分配

該方案具有以下重要特性：地址始終是唯一的；葉節(jié)點(diǎn)的地址絕不會是另一個葉節(jié)點(diǎn)的前綴；具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)有共同的前綴；每個節(jié)點(diǎn)的地址使用其父節(jié)點(diǎn)地址作為前綴。本文提出的路由算法正是利用最后一個最為重要的特性避免了路由表的使用。

2.2 重組

該方案的一個問題在于比特位數(shù)可能要根據(jù)設(shè)備隨時加入或離開網(wǎng)絡(luò)而改變。例如圖2（a），由式（1）可知比特數(shù)N（CR）要求標(biāo)記連接鏈路的路由器R的子節(jié)點(diǎn)數(shù)為2，如果另一設(shè)備X連接到R，N（CR）就變成2。因此，每個輸出鏈路連接到R就必須重新標(biāo)記為2位。這意味著路由器R所有現(xiàn)有子節(jié)點(diǎn)的地址必須重新計算，如圖2（b），此過程稱為重組。重組將增加成本開銷，但本文將證明（分析仿真結(jié)果）因該方案引起的額外成本開銷是相當(dāng)?shù)偷摹?/p>

圖2 網(wǎng)絡(luò)地址重組

2.3 路由算法

本節(jié)介紹如何利用基于前綴碼的方法尋找到達(dá)目標(biāo)設(shè)備的路由。符號說明如下：Ai：設(shè)備i的網(wǎng)絡(luò)地址；Bi：Ai的位數(shù)；Ci：路由器i的子節(jié)點(diǎn)數(shù)；IDi：設(shè)備i的本地地址（除根節(jié)點(diǎn)）。前綴碼的特性就是每個節(jié)點(diǎn)的父節(jié)點(diǎn)作為它的前綴。假設(shè)節(jié)點(diǎn)的順序?yàn)椋篤→W→X→Y→Z，則節(jié)點(diǎn)Z的地址AZ為如下形式：

由上式可知，如果一個節(jié)點(diǎn)X的地址AX是另一個節(jié)點(diǎn)Y地址AY的前綴，那么節(jié)點(diǎn)Y一定是節(jié)點(diǎn)X的子節(jié)點(diǎn)。換言之，X必須是Y的父節(jié)點(diǎn)，所以如果X得到一個數(shù)據(jù)包發(fā)往Y，就可以使用此特性來決定路由。如圖3所示是改進(jìn)路由算法的流程圖。

圖3 改進(jìn)路由算法

算法實(shí)現(xiàn)：當(dāng)節(jié)點(diǎn)X收到一個數(shù)據(jù)包并將其發(fā)送到目的節(jié)點(diǎn)D時，首先它會檢查自己的地址（AX）是否是目標(biāo)地址（AD）的前綴，如果不是，即目的節(jié)點(diǎn)D不是節(jié)點(diǎn)X的子節(jié)點(diǎn)，在這種情況下，X除了將信息反饋給其父節(jié)點(diǎn)以外什么都不做；否則（即X的地址為目的節(jié)點(diǎn)地址的前綴），目的節(jié)點(diǎn)一定是X的子節(jié)點(diǎn)（直接或間接），這時存在兩種情況：

（1）目的節(jié)點(diǎn)D是節(jié)點(diǎn)X的直接子節(jié)點(diǎn)：目的地址（BD）的比特位數(shù)正好等于（圖4（a））自己的地址（BX）比特位數(shù)和代表其子節(jié)點(diǎn)[N（CX）]的比特位數(shù)的總和。這表明目的地址是節(jié)點(diǎn)X地址（AX）和子節(jié)點(diǎn)ID的連接組合，如圖4（a）所示。

（2）否則，如圖4（b）所示，目的節(jié)點(diǎn)D不是節(jié)點(diǎn)X的直接子節(jié)點(diǎn)。

這兩種情況下，下一跳設(shè)備ID都可以用以下方法獲得：從目的地址AD的MSB開始，忽略地址AD的第一個BX位，再加上N（CX）位來構(gòu)成下一跳設(shè)備的ID。

圖4 決定父節(jié)點(diǎn)X和子節(jié)點(diǎn)D的關(guān)系

由以上分析可知，該算法只使用了數(shù)學(xué)與/或邏輯運(yùn)算，從而消除了路由表。

2.4 示例

用圖1所示的網(wǎng)絡(luò)圖來驗(yàn)證該路由算法是如何決定路由的。假設(shè)設(shè)備E1發(fā)送一個數(shù)據(jù)包到設(shè)備E11。由于E1的地址110000不是10100的前綴，所以它只是將數(shù)據(jù)包轉(zhuǎn)發(fā)到其父節(jié)點(diǎn)R5。R5和R4像E1一樣執(zhí)行類似的步驟并且最終把數(shù)據(jù)包轉(zhuǎn)發(fā)到地址為1的協(xié)調(diào)器C，C的地址1是10100的前綴。因?yàn)镃C=2，所以C從 AE11=10100中BC=1位后的N（CC）=1位提取并得到0。C通過標(biāo)記為0的鏈路轉(zhuǎn)發(fā)其數(shù)據(jù)包，并將該數(shù)據(jù)轉(zhuǎn)發(fā)給地址為10的路由器R1，然后R1和R3執(zhí)行完全相同的方式將數(shù)據(jù)包最終發(fā)送到目標(biāo)設(shè)備E11。

3 成本計算

本節(jié)將計算由于“重組”過程而帶來的成本開銷。ZigBee網(wǎng)絡(luò)主要是靜態(tài)的，一旦設(shè)備加入網(wǎng)絡(luò)，它們很難改變或離開網(wǎng)絡(luò)[8]。“重組”必然會帶來額外的開銷，但隨后的分析表明平均每個節(jié)點(diǎn)對重組的影響是很小的。

重組只是發(fā)生在有設(shè)備加入或者離開網(wǎng)絡(luò)時導(dǎo)致子節(jié)點(diǎn)的數(shù)量從2n到2n+1或者從2n+1到2n（n=1，2，3，…）改變時，在前一種情況下，未來的（2n+1-2n）次，和后一種情況下，未來的（2n-2n-1）次，都不會有重組發(fā)生。假設(shè)路由器擁有2n個子節(jié)點(diǎn)，則平均有（n-1）種重組情況會發(fā)生。例如，若路由器擁有8（即23）個子節(jié)點(diǎn)，重組會發(fā)生兩次。表1給出路由器子節(jié)點(diǎn)數(shù)和該路由器上發(fā)生重組數(shù)之間的關(guān)系。

表1 路由器子節(jié)點(diǎn)數(shù)對重組發(fā)生數(shù)的影響

計算所有路由器發(fā)生的“重組”總數(shù)。考慮以下參數(shù)：D：特定時間下的設(shè)備總數(shù)；R：路由器數(shù)；C：終端設(shè)備數(shù)，C=D-R。每個路由器擁有平均D/R的子節(jié)點(diǎn)數(shù)，則每個路由器需要的重組數(shù)是log2（D/R）-1，發(fā)生重組的總數(shù)為N=（log2（D/R）-1）R，得到N與R的關(guān)系如圖5所示[9]。

圖5 路由器數(shù)量對重組數(shù)量的影響（理論分析）

由圖5可見，對于少量（＜10）路由器，成本開銷大約在3%～10%（對于250個設(shè)備），對于大量的設(shè)備，成本開銷也很小。圖5給評估路由器數(shù)量帶來的最小成本開銷提供了依據(jù)。此外只有路由器的子節(jié)點(diǎn)才受到重組過程的影響，并且對于靜態(tài)的無線網(wǎng)絡(luò)，一旦網(wǎng)絡(luò)建立，幾乎就不會有成本開銷了。每個重組過程的地址更新數(shù)量很小，所以整體預(yù)期開銷很低。

4 仿真分析

該仿真實(shí)驗(yàn)采取了150，200和250不同數(shù)量的設(shè)備。對于每一種情況，路由器的數(shù)量1~70不等，進(jìn)行了超過200次的實(shí)驗(yàn)，得到平均結(jié)果。圖6展示了路由器數(shù)量對重組數(shù)的影響。仿真結(jié)果接近由式N=（log2（D/ R）-1）R計算所得結(jié)果，符合預(yù)期。從圖中的數(shù)字部分可以看出，重組發(fā)生的概率很小（250個設(shè)備），最大達(dá)到總實(shí)驗(yàn)數(shù)的23%。

圖6 路由器數(shù)量對重組數(shù)的影響（仿真結(jié)果）

從圖6中可以看出路由器數(shù)量和平均節(jié)點(diǎn)數(shù)對每個重組的影響，它表明即使重組發(fā)生，節(jié)點(diǎn)數(shù)量對于重組的影響也是很小的。觀察發(fā)現(xiàn)大約只有6~10個節(jié)點(diǎn)受到重組過程的影響，這一數(shù)字在大部分情況下是可以接受的。一般來說，路由器數(shù)量相對較少時，由于重組帶來的成本開銷可以忽略不計。此外，它對于內(nèi)存的要求是有限的。

圖7展示了路由器數(shù)量對參與重組節(jié)點(diǎn)數(shù)量的影響。它表明，雖然重組發(fā)生，但只有極少數(shù)節(jié)點(diǎn)受此過程的限制。因此，在實(shí)際應(yīng)用中由于重組過程帶來的成本開銷也是可以忽略不計的。

圖7 路由器數(shù)量對參與重組節(jié)點(diǎn)數(shù)量的影響

5 總結(jié)

本文提出一種新的路由改進(jìn)算法和針對IEEE802. 15.4樹網(wǎng)絡(luò)的尋址方案。每個設(shè)備被智能地分配一個唯一的二進(jìn)制地址，以便只通過目的地址就可以決定路由。本文提出的改進(jìn)路由算法不需要每個路由器來對路由表進(jìn)行維護(hù)，仍然可以將數(shù)據(jù)包轉(zhuǎn)發(fā)到正確的目的地址。本文研究還表明，該路由算法大大降低了成本開銷。

[1]GIRI D，ROY U K.Address borrowing in wireless personal area network[C].Proc of IEEE International Advanced Computing Conference（IACC），Patiala，India，2009：1074-1079.

[2]GIRI D，ROY U K.Single level address reorganization in wireless personal area network[C].4th International Conference on Computers&Devices for Communication（CODEC），CalcuttaUniversity，India，2009：1-4.

[3]GIRI D，ROY U K.Multi channel personal area network（MCPAN）formation and routing[C].International Conference on Industrial Engineering Science and Applications（IESA），2014：49-61.

[4]KIM T，KIM S H，Yang Jinyong，et al.Neighbor table based shortcut tree routing in ZigBee wireless networks[J]. Parallel and Distributed Systems，IEEE Transactions on，2014，25（3）：706-716.

[5]ROYER E，TOH C-K.A review of current routing protocols for Ad-Hoc mobile wireless networks[J].IEEE Personal Communications Magazine，1999，6（2）：46-55.

[6]王琛.ZigBee路由算法研究與應(yīng)用[D].濟(jì)南：山東大學(xué)，2009.

[7]郭昌飛.基于ZigBee的無線傳感器組網(wǎng)技術(shù)研究與應(yīng)用[D].北京：北京信息科技大學(xué)，2010.

[8]吳英杰.基于能量優(yōu)化的ZigBee網(wǎng)絡(luò)路由算法仿真研究[D].武漢：武漢理工大學(xué)，2011.

[9]崔東旭.面向無線傳感器網(wǎng)絡(luò)的ZigBee路由協(xié)議研究與改進(jìn)[D].北京：北京林業(yè)大學(xué)，2011.

Research of ZigBee tree routing protocol im proved algorithm for resource-constrained devices

Yu Xianqiang，Ye Jianfang
（College of Information Science and Technology，Donghua University，Shanghai 201620，China）

ZigBee provided a table-free tree routing algorithm together with an addressing scheme for resource constrained IEEE 802.15.4 devices，which is applicable for symmetric limited-sized tree networks only.This paper presented an efficient routing algorithm and a flexible，variable-length addressing scheme based on prefix code.The scheme eliminates routing tables and does not limit network size and also allows devices to have arbitrary number of children.It leverages simple mathematical and/or logical equations to take routing decisions and can be applied for almost all types of tree networks.Analysis and simulation results show that this flexible mechanism reduces overhead.

ZigBee；tree networks；address；routing；prefix-code

TN915.04

A

1674-7720（2015）13-0065-04

2015-03-02）

喻先強(qiáng)（1990-），男，碩士研究生，主要研究方向：無線通信與射頻技術(shù)。

葉建芳（1964-），女，碩士，副教授，主要研究方向：無線系統(tǒng)射頻與微波電路及超寬帶無線通信及關(guān)鍵技術(shù)的研究。