基于分段的ZigBee網絡按需可擴展地址分配算法

任智，李鵬翔，姚玉坤，黃勇

（重慶郵電大學 通信與信息工程學院 移動通信技術重慶市重點實驗室，重慶 400065）

1 引言

采用 ZigBee標準[1]的無線傳感器網絡[2,3]（簡稱“ZigBee網絡”）近來得到較多關注。ZigBee網絡在組網過程中會為每個節點分配一個 16bit的網絡地址，以用于之后的通信。分布式地址分配機制（DAAM, distributed address assignment mechanism）[1]是ZigBee網絡中一種重要的節點地址分配機制，它使用網絡協調器和路由節點的最大子節點數Cm、最大子路由節點數Rm和網絡最大深度Lm這3個參數計算并分配節點地址，通過在分配與被分配地址的節點之間建立“父-子”關系，使地址與位置相關聯，從而為樹路由（tree routing）協議[1,4]的運行提供條件。因為實現簡便且能使地址與位置關聯，DAAM目前得到較廣泛的研究和應用。

由于DAAM預設了參數Cm和Rm，因此當向某個路由節點申請地址的路由節點數大于Rm，或終端節點數大于Cm-Rm時，節點分配不到地址，稱之為“寬度不足”（insufficient breadth）問題，得不到地址的節點因無法入網而成為孤節點（orphan node）[5]，如圖1中的節點A。由于網絡部署通常難以直接固定所有節點位置，因此寬度不足問題發生的可能性不能忽略。

圖1 寬度不足問題（Cm=5,Rm=3,Lm=2）

對于寬度不足問題，目前已有一些研究。文獻[5]探討了節點因預設參數限制而成為孤節點的成因，提出了改變孤節點潛在父節點、重構局部網絡拓撲的解決方法，能夠減少因寬度不足產生的孤節點，但在通信和運行時間等方面會產生明顯的額外開銷。文獻[6]對寬度不足問題提出的解決方法是無地址的節點以有地址的相鄰路由節點為代理，向協調器申請地址，協調器將 DAAM 定義的地址空間之外的地址分配給該節點，這種方法的主要問題是會產生額外通信開銷及部分節點無法使用樹路由。文獻[7]和文獻[8]提出了借地址的思路，子地址空間不足的路由節點向有剩余地址的路由節點借地址進行分配，這種方式同樣存在額外通信開銷和破壞樹路由的問題。文獻[9]介紹了一種通過地址重配置來減少孤節點的方法，在重配置過程中使用了DAAM未用到的地址，但重配置使控制開銷增加且其擴展操作是一次性的。文獻[10]針對寬度不足問題提出了一種通過增大深度參數減小地址偏移量，從而使路由節點的子節點地址空間增大的方案 SLAR（single level address reorganization）；當深度為d的路由節點子地址不夠時，啟動地址重配置過程，使用Cskip(d+1)取代Cskip(d)作為地址偏移量分配地址給子節點，Cskip(d)由式(1)計算：

這種“以深度換寬度”的方法雖能增大路由節點的子節點地址空間，但減小了網絡深度，且地址重配置操作使控制開銷和耗時增加。

為解決現有方案存在的上述增加額外通信開銷、破壞樹路由的問題，本文提出一種基于分段的按需可擴展地址分配算法，對路由節點的子節點地址空間進行分段式按需擴展，為更多節點分配地址，既保持“地址-位置”關系又無需任何額外的通信開銷，并且通過改進樹路由協議使其適應所有地址。

本文的主要貢獻如下。

1) 提出一種基于分段的按需可擴展地址分配新算法，在需要時逐段擴展可用地址空間，增加路由節點能夠連接的子節點數。

2) 改進DAAM中的節點地址計算公式，引入段地址和段偏移量，使其適用于新算法，并保持原有的“地址-位置”關系。

3) 改進現有的ZigBee網絡樹路由協議，使其與新算法分配的節點地址兼容。

本文后面部分組織如下：第2節介紹網絡模型，第3節詳述提出的地址分配新算法和樹路由協議的改進方法，第4節對新算法的性能進行理論和仿真分析，第5節總結全文。

2 網絡模型

2.1 模型與定義

ZigBee網絡的數學模型為：G=(V，E)，其中，V表示所有節點的集合，V={t}∪Vr∪Ve，t表示網絡協調器，Vr表示所有路由節點的集合，Ve表示所有終端節點的集合；E表示所有對稱無線通信鏈路的集合。

為便于研究，在本文中做如下定義。

定義1 地址空間（address space）：指具有一定位數的地址集合。

定義2 分段（segmentation）：指將一個地址空間分為多個容量更小的地址空間。

2.2 剩余地址空間

本文在研究中發現，DAAM定義的地址空間上限很少達到65 535(216-1)，這意味著絕大多數情況下有剩余地址空間可供利用。下面推導 DAAM 用完16bit地址空間的概率。

根據DAAM的原理，有SDAAM={1,Am}，其中，SDAAM和Am分別表示DAAM定義的地址空間和分配的最大地址。Am可用式(2)計算：

1) 當Rm=1時，有：

欲使Am=65 535，須CmLm=65 535；通過因式分解可知65 535為4個素數的乘積：65 535=3×5×17×257；因此，滿足條件的CmLm組合個數為：

2) 當Rm＞1時，有：

結合條件Rm＞1、Cm≥Rm和Lm≥1進行遍歷搜索，得到滿足條件的CmRmLm組合個數為3，即（4 369, 2,4）、（13 107, 4, 2）、（21 845, 2, 2）。

綜上，DAAM 用完 16bit地址空間的方式有16+3=19種；由于Lm∈{1, 65 535}，Cm∈{1, 65 535}，因此總的地址分配方式數大于65 5352，則DAAM用完地址空間的概率P＜19/65 5352(≈4.42×10-9)，近似地，P≈0。

3 基于分段的按需可擴展地址分配算法

根據按需利用剩余地址空間的思路，提出一種基于分段的按需可擴展地址分配 (SOSAA, segmentation-based on-demand scalable address assignment)算法，用DAAM定義的地址空間作為單位，對 16bit地址空間進行按需的分段式擴展（如圖 2所示），改善寬度不足問題。

圖2 地址空間分段式擴展

3.1 SOSAA算法操作

SOSAA算法操作包括初始化、地址請求和地址分配3個階段，具體如下。

1) 初始化

網絡協調器將自己的地址設為 0，并確定參數Cm、Rm和Lm；然后，向鄰居節點廣播組網消息。

2) 地址請求

如果一個無地址的節點收到鄰居廣播的組網消息，它將鄰居地址存入鄰居表；然后，從鄰居表中選擇一個信號最強的節點，向其發送地址請求消息；如果收到無地址分配的消息，則依次向鄰居表中的其他節點發送地址請求，直至發往所有鄰居。

3) 地址分配

如果地址為Ap的路由節點收到其他節點的地址請求，用式(6)為該申請節點分配地址Ar。

其中，AS為段地址，等于進行地址擴展操作的次數，初始值為 0；n為同一段地址空間內已分配的同類節點數。如果無剩余地址，該路由節點將AS加1，重新計算Ar；若Ar小于65 536，則將其分配給申請節點，否則，因地址位數大于16，向申請節點發送無地址分配消息。

SOSAA算法進行地址分配的效果可從圖1中看出，該圖中的節點A使用DAAM無法獲得地址，但運行 SOSAA 算法則能獲得地址 28(1×20+7+1×0+1=28)。

3.2 計算復雜度

關于SOSAA算法的計算復雜度，有如下引理。

引理1 SOSAA算法具有與DAAM相同的計算復雜度。

證明 考慮時間、存儲和通信3個方面的復雜度。

SOSAA算法的運行時間主要受網絡深度Lm和節點的最大鄰居節點數Nm影響，為O(Lm+Nm)；而DAAM的時間復雜度同樣如此，也為O(Lm+Nm)。DAAM 占用節點存儲空間最多的部分是鄰居節點的信息，因此它的存儲復雜度由最大鄰居節點數決定，為O(Nm)；SOSAA算法只比DAAM多存儲了一個長度固定的段地址值，此值占用空間相對很小，對存儲復雜度沒有影響，因此它的存儲復雜度同樣為O(Nm)。DAAM算法的通信操作主要包括網絡協調器和路由節點的組網消息廣播和節點的地址申請與回復，因此它的通信復雜度由路由節點的數量和度決定，為O(NRmLm-1)，其中，N為路由節點的度；而SOSAA算法沒有增加任何通信操作，因此其通信復雜度同樣為O(NRmLm-1)。由上述內容可得：SOSAA算法與DAAM具有相同的計算復雜度。證畢。

3.3 SOSAA算法的適用范圍與不足

SOSAA算法可用于任何使用DAAM的ZigBee網絡。當子節點數量適用于DAAM時，DAAM和SOSAA算法均可應用且地址分配的效果相同；而通常情況下子節點數有可能超出 DAAM 的限制，此時 SOSAA算法能夠分配更多地址，效果優于DAAM。在任何規模的 ZigBee網絡中，都可以用SOSAA算法代替DAAM，為更多節點分配地址并且保持“地址－位置”關系。SOSAA算法的不足之處在于：16bit地址總空間的限制對分段后留給子節點擴充用的地址空間有一定程度的制約，當DAAM定義的地址空間較大時，地址空間分段式擴展的次數會降低，能夠多分配的地址數也會相應減少；但只要16bit地址空間沒被DAAM用完，就能多分配地址，前文已推導出用完的概率約等于0。

另一方面，由于受到 ZigBee標準的限制，節點根本地址的最大值為65 535；當節點數小于該值時，SOSAA算法能夠有效擴充節點所用地址空間；而當節點數大于該值時，由于根本地址數量已不能滿足要求，因此需要在根本地址的擴充上再想辦法，比如為節點地址擴充附加比特數等，這涉及到改變 ZigBee標準對節點地址比特數的定義，將在下一步工作中深入研究此問題。

3.4 樹路由協議的改進

為消除SOSAA算法對樹路由的影響，本文改進了樹路由協議中判斷數據傳遞方向和計算下一跳節點的機制。改進后的樹路由協議主要步驟如下。

1) 地址為A深度為d的路由節點收到目的地址為D的數據分組時，先計算基準地址D'：

2) 用式(7)判斷D是否是子孫節點：

若式(8)成立，則執行步驟3）；否則，將數據分組發給本節點的父節點，結束。

3) 判斷：

若式(8)成立，下一跳節點地址N=D；否則：

然后，將數據分組轉發給下一跳節點。

如上所述，改進后的樹路由協議能夠適用于SOSAA算法分配的所有地址。

4 性能分析

4.1 理論分析

1) 地址分配成功率

地址分配成功率用于評價地址分配算法的有效性。定義地址分配成功率S為

其中，N為節點總數，NS表示獲得地址的節點數。因為SOSAA算法能夠通過按需的地址擴展為原來得不到地址的節點分配地址，所以會使NS增大，則S隨之增大。

2) 控制開銷

控制開銷指地址分配算法在運行過程中用于傳送控制分組的開銷，與算法效率負相關。為消除控制分組長度不同的影響，在本文中用地址分配算法運行結束時節點發出的所有控制分組的比特數BC來表示控制開銷。

其中，i為大于0的整數，Li表示第i個控制分組的長度。由于SOSAA算法能夠為原來得不到地址的節點分配地址，這部分節點獲得地址后不再觸發地址請求分組及其答復分組，因此與DAAM相比，i減小，相應地BC減小。

3) 地址分配平均耗時

地址分配平均耗時表征算法分配地址的快慢程度。定義地址分配平均耗時ta為其中，ts表示分配地址消耗的全部時間，Na表示獲得地址的節點總數。與DAAM相比，SOSAA算法能夠為更多的節點分配地址，Na增大；減少了節點因得不到地址而多次申請的操作，使ts減小，所以ta減小。

4.2 仿真分析

取 DAAM 和 SLAR[10]作為比較對象，通過仿真比較分析它們和SOSAA算法在地址分配方面的性能。選擇SLAR的原因在于它能夠增大路由節點的地址空間且未破壞樹路由。

4.2.1 仿真設置

使用Windows XP平臺上的OPNET仿真軟件[11]對上述地址分配算法進行仿真。在半徑為200m的圓形區域設置具有不同節點密度的5個仿真場景，N個靜止節點在該區域中隨機均勻分布，N∈{100，200，300，400，500}；每個場景的中心位置有 1個協調器，路由節點和終端節點的數量比例為6：4；節點的MAC層和物理層采用IEEE802.15.4a標準[12]，節點通信范圍統一設為35m；考慮節點總數和路由、終端節點比例，Cm、Rm和Lm的缺省值分別設為5、3和8。每個仿真實驗做4次，結果取平均值。隨機種子值分別取128、130、132和134。

4.2.2 仿真結果及分析

1) 地址分配成功率

從圖3可看出，SOSAA算法在5個場景中的地址分配成功率均明顯大于DAAM和SLAR，它們的均值分別為88%、65%和30%，最小的差距也有 20%（300節點場景），分析其原因主要在于 SOSAA算法通過擴展地址使更多的節點得到地址，而且不影響節點原有的地址分配機會。SLAR由于縮小了網絡深度，對地址分配成功率造成了明顯影響。

圖3 地址分配成功率比較

2) 控制開銷

圖4顯示了SOSAA算法的控制開銷(均值為552 700.8bit)在各場景中均不大于另外2種算法，這驗證了前面的理論分析。此外，由于深度減小而丟失地址的節點會再次發送地址請求消息，也使開銷上升。隨著節點數的增加，SOSAA算法的優勢從0（100節點）上升到28.6%（500節點），也從側面說明了無地址節點的增加使 DAAM 和SLAR的開銷增加較明顯，尤其是SLAR，上升速率最大，說明重配置過程在節點多時會明顯增加開銷。

圖4 控制開銷比較

3) 地址分配平均耗時

圖5表明SOSAA算法的地址分配平均耗時（均值為0.12s）在總體上少于DAAM（均值為0.14s）和SLAR（均值為0.60s）。分析其原因在于DAAM中無地址的節點會向相鄰的所有路由節點申請地址，引起耗時增加；SLAR在第一次分配地址之后會再次運行地址分配過程，使分配耗時增加；從圖中數據來看，SLAR地址重配置過程加上之后的無地址節點的地址請求過程，使地址分配平均耗時成倍增加。100個節點的場景中由于節點總數和無地址的節點數都較少，因此SOSAA算法的優越性尚未充分體現，平均耗時比 DAAM 稍高，但仍比SLAR低約60%。

圖5 地址分配平均耗時比較

4) 路由節點比例的影響

選擇500個節點的場景，改變路由節點比例，得到如圖6所示的結果。從圖中可看出，隨著路由節點比例的增加，SOSAA算法的地址分配成功率從4.2%開始上升，在比例為0.8時獲得最大值91%，地址分配平均耗時從0.393開始下降，在比例為 0.6時取得最小值 0.042s，說明路由節點比例的增加總體上對 SOSAA的節點地址分配性能有利，這為網絡部署時路由節點比例的選取提供了一個參考。

圖6 路由節點比例對SOSAA性能的影響

5) 網絡深度的影響

選擇 500個節點的場景，取Cm=5，Rm=3，Lm∈{2，3，4，5，6，7，8，9}，考察 SOSAA算法的性能得到如圖7所示結果。由圖7可知，SOSAA算法的地址分配成功率和平均耗時在Lm=8時取得最優值，說明網絡最大深度和地址分配性能不是正相關關系。分析其原因在于：在寬度一定的情況下，深度小時因深度不足而無法得到地址的節點會增多；而深度大時，在地址總量65 535的限制下，因DAAM占用的地址空間增大而會導致可擴展的地址空間減少，這也驗證了3.3節的分析。

圖7 網絡深度對SOSAA性能的影響

5 結束語

本文提出了一種基于分段的按需可擴展地址分配算法——SOSAA算法，當路由節點的子節點地址空間不足時對其進行分段式擴展，從而為更多的節點分配地址，并且避免了額外通信開銷和對樹路由的影響。理論分析和仿真結果顯示，與DAAM和它的一種改進方案(SLAR)相比，SOSAA算法在地址分配成功率、控制開銷和地址分配平均耗時等方面的性能表現整體更優。在未來工作中，將深入研究根本地址的擴充問題和寬、深度不足問題的合成解決方案。

[1] ZigBee Alliance, ZigBee Specification Document 053474r17[S].2007.

[2] AKYILDIZ I F, SU W L, SANKARASUBRAMANIAM Y,et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002,40(8): 102-114.

[3] 黃瓊, 張宏科, 郜帥等. 基于 IPv6的無線傳感器網絡應用設計[J].重慶郵電學院學報(自然科學版), 2006, 18(5): 621-624.HUANG Q, ZHANG H K, GAO S,et al. Application design of wireless sensor network based on IPv6[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2006,18(5): 621-624.

[4] HARBAWI M A, RASID M F A, NOORDIN N K. Improved tree routing (ImpTR) protocol for ZigBee network[J]. International Journal of Computer Science and Network Security, 2009, 9(10):146-152.

[5] PAN M S, TSAI C H, TSENG Y C. The orphan problem in ZigBee wireless networks[J]. IEEE Transactions on Mobile Computing, 2009,8(11):1573-1584.

[6] YEN L H, TSAI W T. The room shortage problem of tree-based Zig-Bee/IEEE 802.15.4 wireless networks[J]. Computer Communications,2010, 33(4):454-462.

[7] GIRI D, ROY U K. Address borrowing in wireless personal area network[A]. 2009 IEEE International Advance Computing Conference(IACC 2009)[C]. Patiala, India, 2009.181-186.

[8] FANG M Q, WAN J, XU X H. A preemptive distributed address assignment mechanism for wireless sensor networks[A]. Proceedings of the 4th International Conference on Wireless Communications,Networking and Mobile Computing (WICOM’ 08)[C]. Dalian, China,2008.1-5.

[9] LI Y R, SHI H B, TANG B Y. Address assignment and routing protocol for large-scale uneven wireless sensor networks[A]. 2009 International Symposium on Computer Network and Multimedia Technology[C]. Wuhan, China, 2009.1-4.

[10] GIRI D, ROY U K. Single level address reorganization in wireless personal area network[A]. 2009 International Conference on Com-

[14] ZigBee Alliance. ZigBee Specification[S]. 2008.

[15] 張潔穎.基于ZigBee網絡的定位跟蹤研究與實現[D]. 上海：同濟大學, 2007.ZHANG J Y. The Research and Implementation of Localization and Tracking in the ZigBee Network[D]. Shanghai: Tongji University,2007.

[16] GON?ALO G, HELENA S. Indoor location system using ZigBee technology[A]. Third International Conference on Sensor Technologies and Applications[C]. 2009. 152-157.