喻先强，叶建芳

（东华大学信息科学与技术学院，上海201620）

资源受限设备的ZigBee树路由协议改进算法研究

喻先强，叶建芳

（东华大学信息科学与技术学院，上海201620）

ZigBee提供的自由表树路由算法与IEEE802.15.4标准的资源受限设备寻址方案，只适用于有限大小的对称树网络。本文提出了一种高效的路由算法和一个基于前缀码的灵活的、可变长度的寻址方案。该方案消除了路由表，并且不限制网络的规模，允许设备拥有任意数的子节点；利用简单的数学与/或逻辑等式来决定路由，并可以适用几乎所有类型的树状网络。理论分析和仿真结果表明，这种灵活的机制大大降低了成本开销。

ZigBee；树网络；地址；路由；前缀码

0 引言

ZigBee提供了资源受限的、简单的、轻量级的自由表树路由算法。ZigBee网络的路由协议基本上是树路由（用于树型拓扑结构）和按需距离矢量（AODV）路由（用于网状拓扑结构）的组合。在参考文献[1]中，提出一种基于移动IP的路由算法，该地址借用方案可以应用到增长超过16跳的网络，并通过地址借用克服地址耗尽的问题。参考文献[2]提出一种针对不对称网路的扩展ZigBee树路由算法，该算法利用对应网络深度的地址数来分配地址。在参考文献[3]中，提出一种统一的多路通道路由方案，该方案应用于树状网络，使网络能够在动态空间中使用，并克服由多通道且不增加任何额外开销的路由表引起的中断问题。在参考文献[4]中，提出基于ZigBee无线网络邻居表的捷径树路由算法，该算法延伸了ZigBee树路由，但网络深度的问题仍然存在且只适用于对称树网络。路由协议的性能评价是ZigBee网络研究的核心问题，这些路由协议用于处理无线网络的低宽带、高错误率、能源和内存受限等问题。在参考文献[5]中，通过对这些协议的分析研究可以发现，在IEEE802.15.4/ZigBee中对路由算法改进的研究相对缺乏。

本文针对ZigBee无线网络的地址分配限制、网络规模、成本开销等问题，提出了一种基于前缀码的可变长度的编址方案与路由改进算法。该算法利用前缀码的性能，不使用任何路由表，而仅使用数学与/或逻辑等式来决定路由。理论分析和仿真结果表明，该方案大大降低了成本开销，同时该路由算法可用于对称以及非对称的大型网络，且对ZigBee网络直径没有任何限制。

1 ZigBee地址分配限制

ZigBee分布式地址分配方案的关键是ZigBee的“协调器确定”，ZigBee协调器确定有几个重要的网络参数：Cm，Rm和Lm（Cm为协调器数量，Rm为路由器数量，Lm为网络深度），但如何确定这些参数仍然没有有效方法。不当的Cm和Rm参数可能导致网络地址的浪费，原因是所有路由器使用相同的Cm和Rm，并且一次选择以后保持不变。对于较大的Lm值，大量子地址未使用的可能性非常大。假设Cm=4，Rm=2，Lm=14，则深度为1的路由器R能够分发到其每2个子路由器的地址数是Cskip（1）=16 381。由于路由器R最多能够有两个终端设备和两个子路由器，地址总数就可以分发到2+2×16 381=32 764。如果路由器R没有子路由器，则路由器R分布的大量地址将无法使用，这直接意味着可能将浪费掉大约总数216（65 536，对于16位地址）的50%的地址。对于Cm=4，Rm=3，由式（1）[6]计算可得Lm的最大值为9，这意味着没有设备可以存在于深度超过9的地方。

另一个主要问题是寻址方案本质上限制了网络的深度。假设Cskip（0）是地址子块由协调器（深度0）分配给每个路由器Rm的分布式地址，分配到所有路由器总的地址数是RmCskip（0），则所有可能的地址是RmCskip（0）、终端协调器设备Em（Em=Cm-Rm）的数目和本身地址的总和。例如，如果Cm=8，Rm=4，最大可能的深度只有Lm=7。

2 改进方案

ZigBee设备要求更低的成本和功耗，则带来的结果是相应的资源受到限制。因此，提出的路由算法必须能够在资源受限设备上有效地运行。本文提出的改进路由算法消除了路由表，它只需要非常小的内存来运行，同时也消除了在数据包中放置路由信息的开销。该路由算法是基于前缀码的寻址方案，解决了ZigBee网络地址分配限制和由于重组带来的成本开销等问题。

2.1 网络地址分配

该改进方案可以智能地分配网络地址到相应设备，且到达目标设备的路由能够仅从目的地址就可以确定。如图1所示的树图，地址计算如下：在树中每个路由器通过一个唯一的二进制数来标识，如果路由器R有CR个子节点，则连接到路由器R的最小数量位N（CR）为[7]：

树中每个节点的唯一网络地址计算如下：根节点（协调器）的地址总是1，其他设备D的地址AD通过连接其父节点的地址ID来获得。例如，图1中路由器R8的地址是AR8=101101。这里，1011是R7的地址，01是连接R7到R8的标号。其他设备的地址也是据此计算。

图1 网络地址分配

该方案具有以下重要特性：地址始终是唯一的；叶节点的地址绝不会是另一个叶节点的前缀；具有相同父节点的节点有共同的前缀；每个节点的地址使用其父节点地址作为前缀。本文提出的路由算法正是利用最后一个最为重要的特性避免了路由表的使用。

2.2 重组

该方案的一个问题在于比特位数可能要根据设备随时加入或离开网络而改变。例如图2（a），由式（1）可知比特数N（CR）要求标记连接链路的路由器R的子节点数为2，如果另一设备X连接到R，N（CR）就变成2。因此，每个输出链路连接到R就必须重新标记为2位。这意味着路由器R所有现有子节点的地址必须重新计算，如图2（b），此过程称为重组。重组将增加成本开销，但本文将证明（分析仿真结果）因该方案引起的额外成本开销是相当低的。

图2 网络地址重组

2.3 路由算法

本节介绍如何利用基于前缀码的方法寻找到达目标设备的路由。符号说明如下：Ai：设备i的网络地址；Bi：Ai的位数；Ci：路由器i的子节点数；IDi：设备i的本地地址（除根节点）。前缀码的特性就是每个节点的父节点作为它的前缀。假设节点的顺序为：V→W→X→Y→Z，则节点Z的地址AZ为如下形式：

由上式可知，如果一个节点X的地址AX是另一个节点Y地址AY的前缀，那么节点Y一定是节点X的子节点。换言之，X必须是Y的父节点，所以如果X得到一个数据包发往Y，就可以使用此特性来决定路由。如图3所示是改进路由算法的流程图。

图3 改进路由算法

算法实现：当节点X收到一个数据包并将其发送到目的节点D时，首先它会检查自己的地址（AX）是否是目标地址（AD）的前缀，如果不是，即目的节点D不是节点X的子节点，在这种情况下，X除了将信息反馈给其父节点以外什么都不做；否则（即X的地址为目的节点地址的前缀），目的节点一定是X的子节点（直接或间接），这时存在两种情况：

（1）目的节点D是节点X的直接子节点：目的地址（BD）的比特位数正好等于（图4（a））自己的地址（BX）比特位数和代表其子节点[N（CX）]的比特位数的总和。这表明目的地址是节点X地址（AX）和子节点ID的连接组合，如图4（a）所示。

（2）否则，如图4（b）所示，目的节点D不是节点X的直接子节点。

这两种情况下，下一跳设备ID都可以用以下方法获得：从目的地址AD的MSB开始，忽略地址AD的第一个BX位，再加上N（CX）位来构成下一跳设备的ID。

图4 决定父节点X和子节点D的关系

由以上分析可知，该算法只使用了数学与/或逻辑运算，从而消除了路由表。

2.4 示例

用图1所示的网络图来验证该路由算法是如何决定路由的。假设设备E1发送一个数据包到设备E11。由于E1的地址110000不是10100的前缀，所以它只是将数据包转发到其父节点R5。R5和R4像E1一样执行类似的步骤并且最终把数据包转发到地址为1的协调器C，C的地址1是10100的前缀。因为CC=2，所以C从 AE11=10100中BC=1位后的N（CC）=1位提取并得到0。C通过标记为0的链路转发其数据包，并将该数据转发给地址为10的路由器R1，然后R1和R3执行完全相同的方式将数据包最终发送到目标设备E11。

3 成本计算

本节将计算由于“重组”过程而带来的成本开销。ZigBee网络主要是静态的，一旦设备加入网络，它们很难改变或离开网络[8]。“重组”必然会带来额外的开销，但随后的分析表明平均每个节点对重组的影响是很小的。

重组只是发生在有设备加入或者离开网络时导致子节点的数量从2n到2n+1或者从2n+1到2n（n=1，2，3，…）改变时，在前一种情况下，未来的（2n+1-2n）次，和后一种情况下，未来的（2n-2n-1）次，都不会有重组发生。假设路由器拥有2n个子节点，则平均有（n-1）种重组情况会发生。例如，若路由器拥有8（即23）个子节点，重组会发生两次。表1给出路由器子节点数和该路由器上发生重组数之间的关系。

表1 路由器子节点数对重组发生数的影响

计算所有路由器发生的“重组”总数。考虑以下参数：D：特定时间下的设备总数；R：路由器数；C：终端设备数，C=D-R。每个路由器拥有平均D/R的子节点数，则每个路由器需要的重组数是log2（D/R）-1，发生重组的总数为N=（log2（D/R）-1）R，得到N与R的关系如图5所示[9]。

图5 路由器数量对重组数量的影响（理论分析）

由图5可见，对于少量（＜10）路由器，成本开销大约在3%～10%（对于250个设备），对于大量的设备，成本开销也很小。图5给评估路由器数量带来的最小成本开销提供了依据。此外只有路由器的子节点才受到重组过程的影响，并且对于静态的无线网络，一旦网络建立，几乎就不会有成本开销了。每个重组过程的地址更新数量很小，所以整体预期开销很低。

4 仿真分析

该仿真实验采取了150，200和250不同数量的设备。对于每一种情况，路由器的数量1~70不等，进行了超过200次的实验，得到平均结果。图6展示了路由器数量对重组数的影响。仿真结果接近由式N=（log2（D/ R）-1）R计算所得结果，符合预期。从图中的数字部分可以看出，重组发生的概率很小（250个设备），最大达到总实验数的23%。

图6 路由器数量对重组数的影响（仿真结果）

从图6中可以看出路由器数量和平均节点数对每个重组的影响，它表明即使重组发生，节点数量对于重组的影响也是很小的。观察发现大约只有6~10个节点受到重组过程的影响，这一数字在大部分情况下是可以接受的。一般来说，路由器数量相对较少时，由于重组带来的成本开销可以忽略不计。此外，它对于内存的要求是有限的。

图7展示了路由器数量对参与重组节点数量的影响。它表明，虽然重组发生，但只有极少数节点受此过程的限制。因此，在实际应用中由于重组过程带来的成本开销也是可以忽略不计的。

图7 路由器数量对参与重组节点数量的影响

5 总结

本文提出一种新的路由改进算法和针对IEEE802. 15.4树网络的寻址方案。每个设备被智能地分配一个唯一的二进制地址，以便只通过目的地址就可以决定路由。本文提出的改进路由算法不需要每个路由器来对路由表进行维护，仍然可以将数据包转发到正确的目的地址。本文研究还表明，该路由算法大大降低了成本开销。

[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]吴英杰.基于能量优化的ZigBee网络路由算法仿真研究[D].武汉：武汉理工大学，2011.

[9]崔东旭.面向无线传感器网络的ZigBee路由协议研究与改进[D].北京：北京林业大学，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-），女，硕士，副教授，主要研究方向：无线系统射频与微波电路及超宽带无线通信及关键技术的研究。