喻先強，葉建芳

（東華大學信息科學與技術學院，上海201620）

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

喻先強，葉建芳

（東華大學信息科學與技術學院，上海201620）

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

ZigBee；樹網絡；地址；路由；前綴碼

0 引言

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

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

1 ZigBee地址分配限制

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

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

2 改進方案

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

2.1 網絡地址分配

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

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

圖1 網絡地址分配

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

2.2 重組

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

圖2 網絡地址重組

2.3 路由算法

本節(jié)介紹如何利用基于前綴碼的方法尋找到達目標設備的路由。符號說明如下：Ai：設備i的網絡地址；Bi：Ai的位數；Ci：路由器i的子節(jié)點數；IDi：設備i的本地地址（除根節(jié)點）。前綴碼的特性就是每個節(jié)點的父節(jié)點作為它的前綴。假設節(jié)點的順序為：V→W→X→Y→Z，則節(jié)點Z的地址AZ為如下形式：

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

圖3 改進路由算法

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

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

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

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

圖4 決定父節(jié)點X和子節(jié)點D的關系

由以上分析可知，該算法只使用了數學與/或邏輯運算，從而消除了路由表。

2.4 示例

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

3 成本計算

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

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

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

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

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

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

4 仿真分析

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

圖6 路由器數量對重組數的影響（仿真結果）

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

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

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

5 總結

本文提出一種新的路由改進算法和針對IEEE802. 15.4樹網絡的尋址方案。每個設備被智能地分配一個唯一的二進制地址，以便只通過目的地址就可以決定路由。本文提出的改進路由算法不需要每個路由器來對路由表進行維護，仍然可以將數據包轉發(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路由算法研究與應用[D].濟南：山東大學，2009.

[7]郭昌飛.基于ZigBee的無線傳感器組網技術研究與應用[D].北京：北京信息科技大學，2010.

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

[9]崔東旭.面向無線傳感器網絡的ZigBee路由協(xié)議研究與改進[D].北京：北京林業(yè)大學，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）

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

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