基于邻居表的能量均衡ZigBee树路由改进算法

白乐强，王玉涛，孙晶晶

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

0 引 言

根据在网络中功能的不同，可以将ZigBee［1］节点分为全功能设备和精简功能设备两种类型［2］。协调器与路由器为FFD 设备，终端节点为RFD 设备。根据网络结构的不同，ZigBee一般分为树路由和AODVjr（Ad－hoc on－demand distance vector junior）两种路由算法。树路由是ZigBee协议中定义的最基本的路由方式，该算法只依靠相关节点的父、子节点进行路径选择，相对简单、无需维护路由表，节省网络的存储资源［3］，但该算法往往产生较大路径成本。Cluster－Tree［4］与AODVjr相结合的改进算法［5］能选出路由跳数较少的路径，有效减少网络总体能量消耗，但该算法只将路由跳数作为节点路由代价的评判标准，没有考虑节点剩余能量。基于能量感知与能量均衡的路由算法［6］根据节点的剩余能量，选择路径损耗小、能量消耗低的节点作为下一跳转发节点，有效降低了网络总体能耗，但该算法没有考虑所选路径的跳数问题。

针对源节点到目的节点的路由跳数多以及节点能量负载不均衡问题，提出一种基于邻居表的能量均衡ZigBee网络树路由改进算法 （EBZTR）。

1 ZigBee网络树路由算法

1.1 ZigBee网络地址分配机制

ZigBee网络采用分布式地址分配机制，为每个网络设备分配唯一的网络地址。其中Cm为最大子节点数，Rm为子节点中最大路由节点数，Lm为网络最大深度［1］，Cskip（d）表示网络深度为d 的路由节点所能分配的地址偏移量，如式 （1）所示

若父节点地址为Aparent，那么分给它的第n个路由子节点地址An应满足式 （2）

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

1.2 ZigBee网络树路由寻址方式

树路由算法完全依赖树型结构转发数据。若一个网络地址为An、网络深度为d 的FFD 节点向目的地址为D 的节点发送数据包，树路由算法先判断目的节点是否为该节点的后代节点。若目的节点D 是节点An的后代节点，将数据包转发到相应节点上［7］。

判断目的节点D 为节点An后代节点的充要条件是

An＜D ＜An＋Cskip（d－1） （4）

在满足式 （4）的前提下，节点An会根据式 （5）计算下一跳节点地址N

若目的节点D 不满足式 （4），则将数据包转发给节点An的父节点。

在ZigBee树路由算法中，根据地址分配机制可得到源节点和目的节点最大深度的公共父辈节点，用LCA（S，D）表示。S、D 分别代表源节点、目的节点，用level（u）表示节点u的深度，用R（u）表示节点u 到目的节点的树路由跳数。那么源节点到目的节点的树路由跳数［8］如式 （6）所示

2 邻居表

设网络中每个设备类型为FFD 的节点都会存储一个相应的邻居表，当前节点A 共有P个邻居节点，Ap表示节点A 的第p 个邻居节点地址且1≤p≤P，则节点A 的邻居表信息结构如图1所示。

图1 邻居表信息结构

（1）NodeTypeAp：NodeTypeAp为节点Ap的节点设备类型，NodeTypeAp＝0 表示节点设备类型为RFD，Node－TypeAp＝1表示节点设备类型为FFD。

（2）NpowerAp：NpowerAp为节点Ap剩余能量。

（3）CountAp：CountAp为节点Ap作为路由节点的次数。

（4）RoutingCostAp：RoutingCostAp为节点Ap路由 代价，路由代价越大表示节点转发数据包的损耗越大。

若节点Ap的节点类型为RFD 时，由于RFD 节点不具有路由功能，则此时RoutingCostAp的值为无限大；否则RoutingCostAp（q）计 算 如 式 （7）［9］所 示，其 中 节 点Ap（q）为NodeTypeAp＝1对应的节点，节点A 共有Q 个此类邻居节点且Q≤P、1≤q≤Q，RoutingCostAp（q）为 节 点Ap（q）路由代价

式中：CountAp（q）——节 点Ap（q）作 为 路 由 节 点 次 数；SunsAp（q）——节点Ap（q）具有的子孙节点个数；DepthAp（q）——节点Ap（q）网络深度；NpowerAp（q）——节点Ap（q）剩余能量。

3 EBZTR算法设计

算法综合考虑节点剩余能量，在节点类型为FFD 的当前节点的邻居节点中，选取剩余能量充足且到目的节点树路由跳数最少的邻居节点作为下一跳转发节点，避免利用剩余能量偏低的节点转发数据包。该算法通过设定节点能量阈值，将网络中的节点分为剩余能量充足区的节点集合和剩余能量偏低区的节点集合。其中算法中的能量阀值用Cwarning表示，Cwarning的计算如式 （8）所示

式 （8）中 的Ap（q（k））为 当 前 节 点A 的 第k 个 满 足TRC（Ap（q），D）≤TRC（A，D）－1对应的邻居节点地址，其中节点A 共有K 个此类邻居节点，TRC（A，D）为节点A 到达目的节点D 的树路由跳数，TRC（Ap（q），D）为节点Ap（q）到达目的节点D 的树路由跳数；NpowerAp（q（k））为节点Ap（q（k））剩余能量；RoutingCostAp（q（k））为节点Ap（q（k））路由代价。

处于剩余能量充足区的节点集合：该节点集合中所有节点的剩余能量值均大于Cwarning，参与下一跳转发节点的选择过程。

处于剩余能量偏低区的节点集合：该节点集合中所有节点的剩余能量值均小于Cwarning，不参与下一跳转发节点的选择过程。

EBZTR 算法中相关参数的定义，见表1。

EBZTR 算法在选取下一跳转发节点过程中，当存在多个剩余能量充足且到达目的节点树路由跳数最少的邻居节点时，选取节点转发优先级最大的邻居节点作为下一跳转发 节 点，其 中 用ForwardingLevelAp（q（k（t（w））））表 示 节 点Ap（q（k（t（w））））的转发 优 先 级。ForwardingLevelAp（q（k（t（w））））的 计算如式 （9）所示

表1 EBZTR 算法相关参数定义

RoutingCostAp（q（k（t（w））））表 示 节 点Ap（q（k（t（w））））的 路 由 代价。根 据 式 （9）可 知：TRC（Ap（q（k（t（w）））），D）值 越 小 则ForwardingLevelAp（q（k（t（w））））值 越 大；RoutingCostAp（q（k（t（w））））的值越大则ForwardingLevelAp（q（k（t（w））））值越小。

通过计算集合F中所有节点到达目的节点的树路由跳数及TRC（A，D），构成满足TRC（Ap（q），D）≤TRC （A，D）－1对应的邻居节点集合G，根据树形拓扑结构的特点，所选的路由路径一定存在。节点A 确认节点集合G 中所有邻居节点的剩余能量值，根据节点集合G 中所有邻居节点的剩余能量值计算Cwarning值的大小，判断集合G 中节点的能量状态。构成满足剩余能量充足区的节点集合H，在节点集合H 中，构成到达目的节点树路由跳数最少的节点集合L，利用式 （9）计算节点集合L 中所有节点的转发优先级，选取转发优先级最大的节点作为下一跳转发节点，其中节点A 转发一次数据包，其CountA值加1。

EBZTR 算法具体步骤如下：

步骤1 判断节点A 是否为目的节点。

若是则算法结束；否则转向步骤2。

步骤2 判断节点A 设备类型是否为RFD。

若是则发送数据包给父节点Aparent，算法结束；否则转向步骤3。

步骤3 判断节点A 的一跳邻居节点是否存在目的节点。

若存在则发送数据包给该邻居节点，算法结束；否则转向步骤4。

步骤4 在节点集合E 中，构成NodeTypeAp＝1对应的节点集合F。

步骤5 利用式 （6）分别计算节点集合F中邻居节点的TRC（Ap（q），D）及TRC（A，D），构成TRC（Ap（q），D）≤TRC（A，D）－1对应的邻居节点集合G。

步骤6 在节点集合G 中，计算Cwarning值，根据Cwarning值构成满足剩余能量充足的节点集合H。

步骤7 在 节 点 集 合H 中，构 成min TRC（Ap（q（k（t））），D）对应的节点集合L。

步骤8 在节点集合L 中，利用式 （9）计算节点Ap（q（k（t（w））））的ForwardingLevelAp（q（k（t（w）））），发 送 数 据 包 给ForwardingLevelAp（q（k（t（w））））最大的节点，算法结束。

重复上述步骤，直至数据包到达目的节点为止。

4 EBZTR算法理论分析

为证明EBZTR 算法的可行性，对EBZTR 算法的时间复杂度与利用该算法选取的路径进行分析。

性质1 EBZTR 算法的时间复杂度为O（P），其中P为当前节点的邻居节点个数。

证明：算法开始，第一步与第二步，每一步均计算1次。第三步判断P个邻居节点是否为目的节点，计算P次。第四步判断P个邻居节点是否为FFD 节点，计算P次。第五步计算集合F中每个节点到目的节点树路由跳数，每个节点最多计算Lm次，有Q 个节点，共计算Lm×Q 次。第六步判断集合G 中K 个节点的能量状态，计算K 次。第七步找出集合H 中T 个节点到达目的节点树路由跳数最少的节点，计算T 次。第八步计算集合L中W 个节点的转发优先级，计算W 次。其中P≥Q≥K≥T≥W，所以EBZTR算法的计算次数为1＋1＋P＋P＋Lm×Q＋K＋T＋W＜ （7＋Lm）×P，即EBZTR算法的时间复杂度为O （P）。

性质2 EBZTR 算法选取的路径是初级通路。

证明：为了证明EBZTR 算法具有该性质，只需证明数据包在传递过程中到目的节点的树路由跳数不断减少。把当前节点与前一跳节点的关系分成父子关系与非父子关系两种。设ti表示第i 个转发节点与前一跳节点具有父子关系，称为树节点，ni表示第i 个转发节点与前一跳节点具有非父子关系，称为非树节点。

按照树路由算法，路径可表示为 （S，t1，t2，ti，…tj，D），路由跳数为j＋1，j≥i≥0。随着数据传递，路由跳数逐跳减少，如式 （10）所示

利用EBZTR 算法会出现4种情况：

（1）树节点到树节点

根据式 （10），R（ti）＜R（ti－1）。

（2）树节点到非树节点

根据EBZTR 算法的描述，R（ni）＜R（ti），R（ti）＜R（ti－1），所以R（ni）＜R（ti－1）。

（3）非树节点到树节点

若ti＋1是ni的父节点，level（ti＋1）＝level（ni）－1；

若ti＋1是ni的子节点，level（ti＋1）＝level（ni）＋1 且level（LCA（ti＋1，D））＝level（LCA（ni，D））＋1。

所以R（ti＋1）＝level（ti＋1）＋level（D）－2×level（LCA（ti＋1，D））＜R（ni）。

（4）非树节点到非树节点

根据以上3种情况，R（ni＋1）＜R（ti＋1）＜R（ni）。

所以，EBZTR 算法找到的路径中任何一个转发节点到目的节点的树路由跳数都小于上一跳节点到目的节点的树路由跳数，数据包传递过程中到目的节点的树路由跳数不断减少。所以EBZTR 算法选取的路径没有重复节点，是一条初级通路。

5 仿真结果与分析

为验证EBZTR 算法的性能，采用MATLAB平台针对网络整体能耗、死亡节点个数以及数据包发送成功率三方面进行实验仿真，并与树路由算法、文献 ［5］中的算法和文献 ［6］中的改进算法进行对比。实验仿真参数：Cm＝6、Rm＝6、Lm＝4，利用式 （1）、式 （2）和式 （3）搭建一个网络范围为200m×200 m、节点个数为100、最大传输距离为40m 的ZigBee网络，节点的初始能量设置为1000J，判定节点死亡能量为50J，数据包长度为80bytes、数据流类型为CBR、发送数据包的速率为50包／s以及仿真时间设为300s，其中ZigBee网络节点的初始能量和判定节点是否死亡的能量是根据现有大多数ZigBee路由算法的取值选取的。实验中每种场景的仿真数据均是独立运行100次后求取的平均值。

如图2所示，随着时间的不断推移，网络总体能量消耗逐渐增多，EBZTR 算法总体能量消耗少于树路由算法、文献 ［5］中的算法以及文献 ［6］中的改进算法。网络中节点能量消耗＝节点初始能量－节点剩余能量［10］。由于EBZTR 算法在路径选择过程中综合考虑剩余能量与路径成本，尽量选择具有能量充足、路径成本低的路径进行传输数据，从而节省了网络的整体能耗。

图2 网络总体能量消耗

如图3所示，EBZTR 算法出现死亡节点的个数少于树路由算法、文献 ［5］以及文献 ［6］中的改进算法。初始阶段，网络中没有出现节点死亡的现象，随着时间的不断推移，死亡节点个数不断增多。由于EBZTR 算法避免利用剩余能量偏低的节点转发数据包，能有效均衡网络的负载，从而延长网络的整体寿命。

图3 网络死亡节点个数

如图4所示，随着时间的不断推移，EBZTR 算法中的数据包从源节点成功到达目的节点的比例高于树路由算法、文献 ［5］中的算法以及文献 ［6］中的改进算法。网络中死亡节点数目的大小直接影响数据包发送成功率的高低，网络中死亡节点数目越多，丢失数据包的现象就越多。EBZTR 算法借助一跳邻居表，综合考虑节点剩余能量与路由代价，有效减少网络死亡节点个数，进而达到数据包发送成功率提高的目的。

图4 数据包发送成功率

6 结束语

针对现有能量均衡ZigBee网络树路由改进算法的不足，提出一种基于邻居表的能量均衡ZigBee网络树路由改进算法。该算法借助一跳邻居表，选取能量充足且到达目的节点树路由跳数最少的节点集合，当存在多个邻居节点能量充足且到达目的节点树路由跳数相同时，选取转发优先级最大的节点作为下一跳转发节点。理论分析结果表明，该算法具有较低的时间复杂度，可以找到一条初级通路。仿真结果表明，该算法有效减少网络整体能量消耗，避开剩余能量偏低的节点转发数据包，推迟死亡节点出现的时间，延长ZigBee网络使用寿命。

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

［2］WANG Xiaowei，ZHAO Xinhui.Design of low energy consumption routing protocol based on AODV in ZigBee network［J］.Computer Measurement＆Control，2013，21 （2）：461－463 （in Chinese）.［王小伟，赵新辉.基于AODV 协议的Zig－Bee网络低能耗按需多路由设计 ［J］.计算机测量与控制，2013，21 （2）：461－463.］

［3］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.］

［4］Huang Yu－Kai，Pang Ai－Chun.Distributed throughput optimization for ZigBee cluster－tree networks［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23 （3）：513－520.

［5］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.］

［6］HE Xuewen，WANG Qiang，ZHANG Zhenli.Research of ZigBee network tree routing algorithm based on energy awareness and energy balance ［J］.Industry and Mine Automation，2013，39 （10）：44－47 （in Chinese）. ［何学文，王强，张振利.基于能量感知与能量均衡的ZigBee网络树路由算法研究［J］.工矿自动化，2013，39 （10）：44－47.］

［7］GUO Xiangyong，LIU Hongli.Design of building energy consumption monitoring system based on ZigBee technology ［J］.Computer Measurement ＆Control，2011，19 （3）：551－553 （in Chinese）.［郭湘勇，刘宏立.基于ZigBee技术的建筑能耗监测系统设计［J］.计算机测量与控制，2011，19 （3）：551－553.］

［8］Taehong Kim，Seong Hoon Kim，Jinyoung Yang，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.

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

［10］Mostafa KA Al－Harbawi，Mohd Fadlee A Rasid，Nor Kamariah Noordin.Utilizing neighbours－table to improve tree routing ［J］.Wireless Personal Communications，2012，65：469－488.