基于邻居表的ZigBee网络树路由改进算法

白乐强，孙晶晶，杨 晰

（沈阳建筑大学 信息与控制工程学院，辽宁 沈阳110168）

0 引 言

ZigBee网络技术是一种具有短距离、低能耗、复杂度低、数据传输量低等特点的无线网络技术［1］。AODVjr［2，3］算法是针对AODV［4］算法的改进，能够找到一条较优路径，但该算法具有很高的控制开销。树路由算法［5］适用于存储能力受限的节点，算法简单且无需存储路由表，有效节省了网络存储资源，然而该算法往往产生较大的路径成本。ITRA［6］算法能够找到一条相对于树路由算法较优的路径，但ITRA 算法没有考虑节点收到数据包后，其邻居节点到达目的节点是否存在多条树路由跳数相同的传输路径及在树路由跳数相同时如何选取最优下一跳转发节点等因素。针对树路由算法的改进算法［7］，能够找到一条较优的路径，但该算法将所有邻居节点到达目的节点的树路由跳数全部计算出来进行比较，选取最小，导致工作量的增大。

针对上述问题，本文在树路由算法基础上，提出一种基于邻居表的ZigBee网络树路由改进算法。该算法借助一跳邻居节点地址信息，对下一跳转发节点的选择进行了深入的研究。

1 树路由算法分析

ZigBee网络节点设备主要可以分为：协调器、路由设备和终端设备这3种［1］。

1.1 地址分配

ZigBee网络采用一种分布式地址分配机制，为每个网络设备分配唯一的网络地址［8］。其中Cm为最大子节点数，这些子节点最多可拥有Rm个路由节点，Lm为整个网络的最大深度［1］。Cskip（d）表示网络深度为d 的父节点为其子节点分配的地址偏移量。网络深度为d 且地址为Aparent的父节点，它分给它的第n个路由子节点地址An应满足为

分给它的第m 个终端节点地址Am满足

路由节点所能分配的地址空间Cskip（d）满足

1.2 邻居表

ZigBee协议对邻居表及邻居节点进行了规定［1］。若两节点在一跳范围之内可以直接进行通信我们就可以将这两节点称为邻居。根据用户需要，可人为去增添邻居表中一些基本信息的内容，例如链路质量指标 （link quality indicator，LQI）值等。

LQI表示接收数据帧的能量与质量的一个指标。IEEE802.15.4标准将LQI定义为接收帧的强度和／或质量特性表征，该标准将LQI的值限定在0～255范围内，LQI值越高表明链路质量越好，传输性能越好，链路越可靠［9］。

1.3 树路由算法

在树路由算法中，网络中的节点根据目的节点的网络地址计算下一跳。当深度为d、地址为A 的节点向目的地址为D 的节点传送数据时，树路由算法先判断目的节点是否为该节点的后代节点。若目的节点D 是节点A 的后代节点，将数据包转发到相应节点上。判断目的节点D 为节点A 的后代节点需满足条件

在满足式 （4）的前提下，节点A 下一跳节点地址N 为

若目的节点D 不是节点A 的后代节点，则按照树型结构将数据包转发给节点A 的父节点［10］。

在ZigBee网络中，采用树路由算法根据ZigBee地址分配机制可得到源节点和目的节点最大深度的公共父辈节点，将其网络深度用MaxDepth 表示。用DstDepth、SrcDepth和HopCount分别表示目的节点、源节点的网络深度和路由跳数，根据树路由算法可得路由跳数［11］HopCount

2 改进算法策略

该算法借助邻居表，进一步减少路由跳数，避免出现网络中不必要节点浪费的问题，综合考虑节点LQI值，有效提高网络性能。算法中将收到数据包的节点记为当前节点。

算法中的符号定义见表1。

表1 算法中的符号定义

邻居节点选择策略为：

当前节点利用│D－Aj│从小到大依次计算出Mk的值即 （M1，M2，…，Mk，…，MJ－I）。

依据ZigBee地址分配机制，依次查找 （M1，M2，…，Mk－1，Mk，…，MJ－I）对应的邻居节点与目的节点最大深度的公共父辈节点，直至查找到邻居节点与目的节点最大深度的公共父辈节点地址为0即为协调器为止。若Mk对应此邻居节点，依据ZigBee 地址分配机制的特点，可知（M1，M2，…，Mk－1）对应的邻居节点与目的节点最大深度的公共父辈节点不为协调器，而 （Mk，…，MJ－I）对应的邻居节点与目的节点最大深度的公共父辈节点为协调器。依据树型拓扑结构的特点，可知 （Mk，…，MJ－I）对应的邻居节点到达目的节点的树路由跳数分别大于 （M1，M2，…，Mk－1）对应的邻居节点到达目的节点的树路由跳数。在 （M1，M2，…，Mk－1）对应的邻居节点中，构成到达目的节点的树路由跳数最少的节点集合B，将集合B 的树路由跳数与按树型结构所得的树路由跳数进行比较。在当前节点的邻居节点中，选择到达目的节点树路由跳数最少的节点作为下一跳转发节点。

改进算法步骤如下：

步骤1 判断当前节点本身是否为目的节点。

若是则接收数据包，否则转向步骤2。

步骤2 判断当前节点的一跳邻居节点是否存有目的节点。

若存在则直接发送数据包，否则转向步骤3。

步骤3 按树型结构，在节点Ai中寻找到达目的节点树路由跳数最少的一个节点。

步骤3.1 利用式 （4）判断当前节点的后代节点是否存在目的节点。

若存在则利用式 （5）选择相应的子节点Ai作为到达目的节点树路由跳数最少的节点。根据ZigBee地址分配机制找出相应的子节点与目的节点最大深度的公共父辈节点，利用式 （6）计算TRC（Ai，D），转向步骤4；否则转向步骤3.2。

步骤3.2 按照树型结构选择当前节点的父节点Ai作为到达目的节点树路由跳数最少的节点。根据ZigBee地址分配机制找出当前节点的父节点与目的节点最大深度的公共父辈节点，利用式 （6）计算TRC（Ai，D），转向步骤4。

步骤4 在邻居节点Aj中，利用式 （6）计算TRC（Aj，D），构成min TRC（Aj，D）对应的邻居节点集合B。

步骤4.1 依次找出与 （M1，M2，…，MJ－I）对应的邻居节点。

步骤4.2 根据ZigBee地址分配机制找到M1对应的邻居节点与目的节点最大深度的公共父辈节点，判断这两节点最大深度的公共父辈节点是否为协调器。

若M1对应的邻居节点与目的节点最大深度的公共父辈节点是协调器，利用式 （6）依次计算 （M1，M2，…，MJ－I）对应的邻居节点到达目的节点的树路由跳数，直至邻居表中的节点Aj计算完毕，构成min TRC（Aj，D）对应的邻居节点集合B，转向步骤5；否则依次查找 （M2，…，MJ－I）对应的邻居节点与目的节点最大深度的公共父辈节点，直至判断出邻居节点与目的节点最大深度的公共父辈节点为协调器或邻居表中的节点Aj计算完毕。利用式（6）分别计算所有符合条件的邻居节点到达目的节点的树路由跳数，构成min TRC（Aj，D）对应的邻居节点集合B，转向步骤5。

步骤5 比较min TRC（Aj，D）与TRC（Ai，D），选取到达目的节点树路由跳数最少的节点集合。

步骤5.1 当min TRC（Aj，D）＝TRC（Ai，D）时，选取集合C，转向步骤6。

步骤5.2 当min TRC（Aj，D）＞TRC（Ai，D）时，那么选择节点Ai作为下一跳转发节点，将数据包传送给这一节点。

步骤5.3 当min TRC（Aj，D）＜TRC（Ai，D）时，选取集合B，转向步骤6。

步骤6 在步骤5得出的节点集合中，选取LQI值大的节点作为下一跳转发节点，将数据包传送给这一节点。

该算法按照树路由跳数最少原则选择下一跳转发节点，直至将数据包传送到目的节点为止。

3 改进算法理论分析

改进算法通过建立邻居节点选择策略，在节点的一跳邻居节点中，选择到到达目的节点树路由跳数最少的邻居节点作为下一跳转发节点，优化数据传输路径。为验证改进算法能够选择到路由跳数更少的路径，借助表2中定义的符号分析并比较改进算法、树路由算法和ITRA 算法在传送数据时路径路由跳数的多少。

表2 理论分析中的符号定义

图1分别为数据包按树路由算法、ITRA 算法及改进算法从源节点S 到达目的节点D 所经过的路由路径。在树路由算法中，数据包从源节点S 到达目的节点D 所经过的树路由路径为 （S，Ai（1），Ai（2），Ai（3），...，Ai（t），...，Ai（P），D），其中源节点S 到达目的节点D 的树路由跳数为P＋1。

根据ZigBee网络树型结构的特点可得出式 （7）

在改进算法中，数据包从源节点S 到达目的节点D 所经 过 的 路 径 为 （S，Ay（1），Ay（2），...，Ay（t），...，Ay（t＋q），D），q为常数且q≥1。此时源节点到达目的节点的路由跳数为t＋q＋1。根据改进算法特性可得出式 （8）

根据式 （7）和式 （8），可推出t＋q≤P。通过不等式定理，可得 （t＋q＋1）≤ （P＋1）即改进算法的路径优于树路由算法路由路径。

在ITRA 算法中，数据包从源节点S 到达目的节点D所 经 过 的 路 径 为 （S，Ax（1），Ax（2），...，Ax（t），...，Ax（t＋r），D），其中r为常数且r≥1。此时源节点到达目的节点的路由跳数为t＋r＋1。ITRA算法利用min｛│D－Ai│，│D－Aj│｝寻找对应的邻居节点，将min ｛│D－Ai│，│D－Aj│｝对应的邻居节点到达目的节点的树路由跳数与TRC （Ai，D）进行比较，选取两者之间树路由跳数较少的邻居节点作为下一跳转发节点，该算法在邻居节点中所选的下一跳转发节点不一定是到达目的节点树路由跳数最少的节点。改进算法通过建立邻居节点选择策略，在节点的一跳邻居节点中，能够选择到到达目的节点树路由跳数最少的邻居节点作为下一跳转发节点，可得出式 （9）

图1 ZigBee网络树路由算法路由路径

根据式 （7）和式 （9），可推出t＋q≤t＋r。通过不等式定理，可得 （t＋q＋1）≤ （t＋r＋1）即改进算法的路径优于ITRA 算法路由路径。

理论分析结果表明，改进算法能够寻找到比树路由算法和ITRA 算法路由跳数更少的路径。

4 仿真结果与分析

为验证改进算法的性能，针对数据传输平均路由跳数、源节点到目的节点的端到端延时及数据包发送成功率这三方面进行仿真，并与树路由算法和ITRA 算法进行对比。本文采用MATLAB平台对改进算法、树路由算法和ITRA算法进行实验仿真。实验仿真参数：选取Cm＝6、Rm＝6、Lm＝4，利用式 （1）～式 （3）搭建一个网络范围为100m×100m、节点个数为300、最大传输距离为25m 的ZigBee网络，其中数据包大小为80bytes、数据流类型为CBR、发送数据包的速率为1包／s以及仿真时间设为200s。试验选取50、100、150、200、250、300ZigBee节点数量规模的网络场景，实验中每种场景的仿真数据均是独立运行100次后求取的平均值。

如图2所示，随着网络节点数目不断增加，节点传输数据所经过的路由跳数逐渐增多，改进算法的路由平均路由跳数少于树路由算法和ITRA 算法。改进算法考虑邻居表中节点地址信息，利用邻居节点选择策略，在当前节点的邻居节点中，能够选取到达目的节点树路由跳数更少的节点作为下一跳节点，进一步优化数据传输路径。

图2 平均路由跳数对比

如图3所示，随着网络节点数目不断增加，改进算法的源节点到目的节点的延时少于树路由算法和ITRA 算法。源节点到目的节点的端到端延时受源节点到目的节点路由跳数的多少影响，减少算法路由跳数，能够有效减少端到端的延时。

如图4所示，随着网络节点密度增大，信号干扰程度变强，传输路径路由跳数增多，改进算法中数据包从源节点成功到达目的节点的数目高于树路由算法和ITRA 算法。数据包发送成功率高与否，主要受信号干扰程度、传输路径路由跳数等因素影响。该算法综合考虑节点LQI值的因素，选取LQI值大的节点转发数据，进一步提高数据包送达率。

图3 端到端延时对比

图4 数据包送达率对比

5 结束语

本文提出一种基于邻居表的ZigBee网络树路由改进算法。该算法利用邻居表中节点信息和树型拓扑结构的特点，选取到达目的节点树路由跳数最少的邻居节点作为下一跳转发节点。当出现多条树路由跳数相同的路径时，选取LQI值大的节点作为下一跳转发节点。理论分析结果表明，该算法路由路径优于树路由算法和ITRA 算法。仿真结果表明，该算法有效减少了网络中路由跳数和数据传输延时，提高了网络数据传输可靠性。该算法无需存储路由表，适用于资源受限的无线传感器网络。

［1］ZigBee Alliance.ZigBee specification ［S］.2008.

［2］HE Lingling.An improved Cluster－Tree routing algorithm in ZigBee networks［J］.Chinese Journal of Sensors and Actuators，2010，23 （9）：1303－1307 （in Chinese）.［贺玲玲.ZigBee传感网络Cluster－Tree改进路由算法研究 ［J］.传感技术学报，2010，23 （9）：1303－1307.］

［3］LI Yudong，HUANG Hongguang，XIANG Xixi.Improved ZigBee routing algorithm based on energy balance ［J］.Computer Engineering and Design，2011，32 （2）：397－400 （in Chinese）. ［李予东，黄宏光，向西西.基于能量均衡的Zig－Bee路由算法优化 ［J］.计算机工程与设计，2011，32 （2）：397－400.］

［4］WANG Jun，CHEN Min，Victor CM Leung.Forming priority based and energy balanced ZigBee networks a pricing approach［J］.Telecommun Syst，2013：1281－1292.

［5］PENG Sheqiang，WANG Wei.Cluster－tree routing algorithm optimization ZigBee network ［J］.Digital Technology and Application，2012 （4）：112－113 （in Chinese）. ［彭设强，王为.ZigBee网路中Cluster－Tree路由算法优化 ［J］.数字技术与应用，2012 （4）：112－113.］

［6］QI Jianchao，WEI Zhen.An improved tree－based routing algorithm for ZigBee［J］.Journal of Hefei University of Technology，2010，33 （4）：529－532 （in Chinese）. ［戚剑超，魏臻.ZigBee树型路由算法的改进 ［J］.合肥工业大学学报 （自然科学版），2010，33 （4）：529－532.］

［7］LI Gang，CHEN Junjie，GE Wentao.An improved Cluster－Tree routing algorithm in ZigBee networks ［J］.Observation and Control Technology，2009，28 （9）：52－55 （in Chinese）.［李刚，陈俊杰，葛文涛.一种改进的ZigBee 网络Cluster－Tree路由算法 ［J］.测控技术，2009，28 （9）：52－55.］

［8］XU Peicheng，HU Guorong.Improved ZigBee network routing algorithm ［J］.Computer Engineering and Design，2013，34（9）：3019－3023 （in Chinese）.［徐沛成，胡国荣.改进的Zig－Bee网络路由算法 ［J］.计算机工程与设计，2013，34 （9）：3019－3023.］

［9］LIU Dan，QIAN Zhihong，LIU Ying.Tree routing improvement algorithm in ZigBee network ［J］.Journal of Jilin University （Engineering and Technology Edition），2010，40 （5）：1392－1396 （in Chinese）.［刘丹，钱志鸿，刘影.ZigBee网络树路由改进算法 ［J］.吉林大学学报 （工学版），2010，40（5）：1392－1396.］

［10］YAO Yukun，LI Pengxiang，REN Zhi，et al.Borrowed address assignment algorithm for ZigBee network ［J］.Computer applications，2011，31 （8）：2044－2047 （in Chinese）.［姚玉坤，李鹏翔，任智，等.适用于ZigBee网络的借地址分配算法 ［J］.计算机应用，2011，31 （8）：2044－2047.］

［11］Taehong Kim，Seong Hoon Kim，Yang Jinyoung，et al.Neighbor table based shortcut tree routing in ZigBee wireless networks［J］.IEEE Transactions on Parallel and Distributed Systems，2014，25 （3）：706－716.