基于分段的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.