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

　　關(guān)鍵詞： ZigBee；樹網(wǎng)絡(luò)；地址；路由；前綴碼

0 引言

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

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

1 ZigBee地址分配限制

　　ZigBee分布式地址分配方案的關(guān)鍵是ZigBee的“協(xié)調(diào)器確定”，ZigBee協(xié)調(diào)器確定有幾個(gè)重要的網(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，并且一次選擇以后保持不變。對(duì)于較大的Lm值，大量子地址未使用的可能性非常大。假設(shè)Cm=4，Rm=2，Lm=14，則深度為1的路由器R能夠分發(fā)到其每2個(gè)子路由器的地址數(shù)是Cskip（1）=16 381。由于路由器R最多能夠有兩個(gè)終端設(shè)備和兩個(gè)子路由器，地址總數(shù)就可以分發(fā)到2+2×16 381=32 764。如果路由器R沒有子路由器，則路由器R分布的大量地址將無法使用，這直接意味著可能將浪費(fèi)掉大約總數(shù)216（65 536，對(duì)于16位地址）的50%的地址。對(duì)于Cm=4，Rm=3，由式（1）[6]計(jì)算可得Lm的最大值為9，這意味著沒有設(shè)備可以存在于深度超過9的地方。

　　另一個(gè)主要問題是尋址方案本質(zhì)上限制了網(wǎng)絡(luò)的深度。假設(shè)Cskip（0）是地址子塊由協(xié)調(diào)器（深度0）分配給每個(gè)路由器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í)也消除了在數(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ì)算如下：在樹中每個(gè)路由器通過一個(gè)唯一的二進(jìn)制數(shù)來標(biāo)識(shí)，如果路由器R有CR個(gè)子節(jié)點(diǎn)，則連接到路由器R的最小數(shù)量位N（CR）為[7]：

　　N（CR）=CR      if CR=0 or CR=1[lg（CR）]  if CR>1（2）

　　樹中每個(gè)節(jié)點(diǎn)的唯一網(wǎng)絡(luò)地址計(jì)算如下：根節(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)號(hào)。其他設(shè)備的地址也是據(jù)此計(jì)算。

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

　　2.2 重組

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

　　2.3 路由算法

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

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

　　算法實(shí)現(xiàn)：當(dāng)節(jié)點(diǎn)X收到一個(gè)數(shù)據(jù)包并將其發(fā)送到目的節(jié)點(diǎn)D時(shí)，首先它會(huì)檢查自己的地址（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)（直接或間接），這時(shí)存在兩種情況：

　　（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的第一個(gè)BX位，再加上N（CX）位來構(gòu)成下一跳設(shè)備的ID。

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

　　2.4 示例

　　用圖1所示的網(wǎng)絡(luò)圖來驗(yàn)證該路由算法是如何決定路由的。假設(shè)設(shè)備E1發(fā)送一個(gè)數(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 成本計(jì)算

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

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

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

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

4 仿真分析

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

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

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

5 總結(jié)

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

參考文獻(xiàn)

　　[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.