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

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

1 引言

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

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

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

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

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

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

本文的主要貢獻如下。

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

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

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

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

2 網絡模型

2.1 模型與定義

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

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

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

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

2.2 剩余地址空間

本文在研究中發(fā)現，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；然后，向鄰居節(jié)點廣播組網消息。

2) 地址請求

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

3) 地址分配

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

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

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

3.2 計算復雜度

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

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

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

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

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

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

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

3.4 樹路由協議的改進

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

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

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

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

3) 判斷：

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

然后，將數據分組轉發(fā)給下一跳節(jié)點。

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

4 性能分析

4.1 理論分析

1) 地址分配成功率

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

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

2) 控制開銷

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

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

3) 地址分配平均耗時

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

4.2 仿真分析

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

4.2.1 仿真設置

使用Windows XP平臺上的OPNET仿真軟件[11]對上述地址分配算法進行仿真。在半徑為200m的圓形區(qū)域設置具有不同節(jié)點密度的5個仿真場景，N個靜止節(jié)點在該區(qū)域中隨機均勻分布，N∈{100，200，300，400，500}；每個場景的中心位置有 1個協調器，路由節(jié)點和終端節(jié)點的數量比例為6：4；節(jié)點的MAC層和物理層采用IEEE802.15.4a標準[12]，節(jié)點通信范圍統一設為35m；考慮節(jié)點總數和路由、終端節(jié)點比例，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節(jié)點場景），分析其原因主要在于 SOSAA算法通過擴展地址使更多的節(jié)點得到地址，而且不影響節(jié)點原有的地址分配機會。SLAR由于縮小了網絡深度，對地址分配成功率造成了明顯影響。

圖3 地址分配成功率比較

2) 控制開銷

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

圖4 控制開銷比較

3) 地址分配平均耗時

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

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

4) 路由節(jié)點比例的影響

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

圖6 路由節(jié)點比例對SOSAA性能的影響

5) 網絡深度的影響

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

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

5 結束語

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

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