基于节点转移的ZigBee网络路由改进算法

李跃 黄希玲 贾海瑞

摘 要：ZigBee网络的一个主要的目标就是降低网络的耗能，以延长网络的使用时间。但ZigBee协议中的网络结构和路由算法并没有完整的讨论能量消耗问题。该文提出一种改进的分布式路由算法，该算法尽可能通过电源供电路由节点转发数据，最终减少电池供电路由节点的能量消耗来延长网络的生存时间。仿真结果表明，该算法只需少量的通讯开销就可以明显地减少电池供电路由节点的耗能。

关键词：ZigBee协议 能耗有效 路由 算法

中图分类号：TP393 文献标识码：A 文章编号：1674-098X（2015）02（b）-0013-03

Improved Algorithm of ZigBee Network Based on Node-Transporting

Li Yue1 Huang xiling1 Jia Hairui2

（1.City College of Southwest University of Science and Technology，Mianyang，621010，China；2.Sichuan airport consciousness Technology Co. Ltd.Chengdu，610000，China）

Abstract：One of the primary goals of ZigBee is low power consumption and therefore long-living networks.Current network formation and routing protocols described in the ZigBee specification do not completely discuss power consumption issues.Distributed routing algorithm to reduce power consumption of battery-powered devices by routing the communication through mains-powered devices is proposed.The proposed algorithm works in tree topologies supported by ZigBee and requires only minor modifications to the current specification. The simulation results showed that the algorithm is able to reduce the power consumption of battery-powered devices significantly with minimal communication overhead.

Key Words：ZigBee Standard； Energy Efficient； Routing；Algorithm

ZigBee技术是一种低成本、低功耗、低速率的基于IEEE 802.15.4无线标准有关组网、安全和应用软件方面的短距离双向无线通信技术，该技术主要针对低速率无线传感器网络和控制网络而设计，能够满足小型化，低成本设备（如智能家居，工业控制和传感器网络等）的无线网络要求，广泛地应用于工业、建筑等无线通信应用场合[1]。

ZigBee协议中的网络结构和路由算法并没有完整的讨论节点能量消耗问题[2]。文献[3]讨论了通过引入邻居表，在选择路由的时候考虑节点的剩余能量，尽量避开剩余能量较低的节点。文献[4]分析了ZigBee传感器网络协议栈不同层的能量效率。文献[5]提出了根据数据包的到达率，采用动态的信标间隔来增加节点的休眠时间以节约能量。文献[6]提出了一种使用跨层费用计算函数构造树路由的算法，该函数综合考虑了剩余能量，信道质量和路由跳数。同样在文献[7]中提出在ZigBee网络的路由发现阶段，采用构造的函数来选择能量满足的路径，延迟受限制的路径。

但现有的文献资料对在ZigBee无线网络中电源供电设备和电池供电设备共存的情况没有深入的研究，而有关大量ZigBee无线传感器网络的应用设计中，不同电源类型的设备可以共存，例如，智能家居、楼宇自动化以及工业控制等[1]，在这些应用中部分节点能够使用外接持续电源。网络中电池供电的节点设备和电源供电的节点设备可以共存，电源供电的节点设备能够降低维修的费用，而电池供电的节点设备使用在不容易布线或布线代价较高的位置。该文深入研究了ZigBee网络的组网技术及其路由算法，结合电源供电设备和电池供电设备的特点，构建了相应的算法模型，提出了一种基于ZigBee树型网络的电源感知路由算法（Power-Aware Routing Algorithm， PARA）。PARA算法基于簇树型网络拓扑，用来减少ZigBee网络中电池供电节点的能量消耗，延长网络运行时间。

1 算法模型构建与分析

由ZigBee网络的树路由算法可知，路由完全依赖父节点和子节点的关系。这样在ZigBee网络中就存在以下几个问题：（1）即使目的节点在转发节点的一跳通信范围内，数据包也必须沿树拓扑传送到目的节点，而无法直接发送到目的节点[3]。（2）某些实用的网络拓扑中，持续电源设备与电池供电设备共存，如果采用现有的树路由算法，所有的路由都是单一的，这样网络中某些电池供电节点会过早耗尽电池的能量，缩短网络的使用时间。

分析图1构建的ZigBee簇树混合电源节点网络模型，图中C是网络的协调器节点，标号R1～R13的节点是FFD节点，RFD节点略去，电源供电的路由节点用实线表示，电池供电的路由节点用虚线表示。当路由节点R6与路由节点R3、R5通信时，其路由分别是R6 -R2-C-R3，R6 -R2-C-R1-R4-R5。以上路由中，需要电池供电结点R1、R2和R4转发数据，使得电池供电节点消耗能量增加，网络容易因个别电池供电节点能量的耗尽而中断。

2 电源感知路由算法

2.1 算法思想

电源感知路由算法思想是尽可能的通过持续电源节点转发数据，减少电池供电节点的数据转发量。树型网络拓扑中，两节点间只有一条路由通路，树型网络形成后，就没有可选择的路由来减少电池供电设备的数据转发量[2]。一个可行的方案是依据流量的动态分布改变树型网络的拓扑结构，通过持续电源节点转发数据，减少电池供电节点的数据转发量，降低网络中电池供电路由节点的总负载。

例如将图1中节点R6与节点R2的连接断开，而将节点R6连接到节点R7，将节点R5与R4断开并与结点R6建立连接。网络拓扑结构改变后，节点R6与节点R3和节点R5的路由均不通过电池供电的路由节点，这样就减少了电池供电节点的数据转发量。

当网络中有新节点加入或原有节点离开时，协调器会检测到网络结构的改变，此时启动路由改进算法重构网络，使得路由算法能够动态适应网络的变化。恰当地更改网络拓扑结构可整体降低电池供电节点的数据转发量。此外，不同路径上流量的变化也会引起网络拓扑结构的改变。

2.2 算法初始条件计算

ZigBee树型拓扑中，要实现上述算法，路由节点需要获取以下信息：（1）节点转发的数据流量；（2）已知网络中数据转发时的路由；（3）路由中包含的电池供电节点；（4）路由节点可连接的其他路由节点信息。由ZigBee树型网络结构的特征可知，一个路由节点只需要极少的流量就可获得这些信息[3] [4]。当数据经过某路由节点转发时，该路由节点能够检测到数据的源节点和目的结点，以及该结点转发数据的比重。获取节点设备的电源类型需要额外的信息，算法中通过搜集每个节点的信息，协调器记录电池供电节点的信息，其它节点访问协调器获取所需信息。数据转发的路由在树型网络中可由具有路由能力的节点直接计算获得。通过（1）式计算网络中电池供电路由节点的总负载[5]，其中TotalLoad是电池节点的总负载，P是路由中电池供电节点的数目，n为网络中的总路由数，T是该条路由转发数据量的比重。

（1）

为获取可连接的邻居节点的信息，该文中引入了邻居表[8]，如果某路由节点在另一路由节点的直接通信范围内，则两节点互为邻居节点，网络中只针对FFD节点储存邻居节点信息，每个FFD节点通过邻居列表记录下该节点与其他节点的邻接关系。邻居表中记录如图2所示，在邻居表中ADDR是邻居节点地址，DType是邻居节点电源类型。

2.3 重构网络拓扑结构算法流程

当网络中有新的节点加入或有节点离开时，网络重构会发生，用（1）式计算所有可重构的新拓扑网络中的电池供电节点总负载，若总负载最小的网络结构，也即最好的网络拓扑结构，其总负载小于当前网络的总负载时，算法更改网络拓扑，否则维持原有网络拓扑。一个路由节点依据电池供电节点的总负载量来决定其父节点，需要改变网络拓扑时，该路由节点就断开与原父节点的连接，并与新的父节点建立连接，新父节点的路径深度要求不大于原父节点的路径深度，避免该节点的子节点无法获得足够的网络地址，网络重构选择新父节点的具体算法如下。

（1）初始化网络中的电池供电设备总负载为load。

（2）依次取得网络中具有路由能力的节点Cn。

（3）依次取得节点Cn的邻居节点An，若无邻居节点时转向第（2）步。

（4）如果节点An的深度小于节点Cn的网络深度，算法继续，否则转到第（3）步。

（5）使用（1）式计算当节点Cn连接到父节点An时网络中电池供电节点的总负载newload，如果新找到网络拓扑中电池供电节点的总负载小于已发现的网络拓扑负载时，将load值更改为newload，并且记录节点An和节点Cn。

（6）转到第（2），继续查找使得网络中电池供电节点的总负载最小的节点对An和Cn，直到分析完网络中所有具有路由能力的节点。

（7）将节点Cn连接到节点An，父节点An给节点Cn分配新地址Rn，选择父节点的过程结束。

由ZigBee树型网络的地址分配机制可知，当路由节点的父节点改变后，该节点的地址及其所有子节点的地址都需要重新分配。重构网络时，改变父节点的重构子树的根节点将原有地址和新分配的地址发送给各后代节点，每个后代节点利用该信息计算其父节点、子节点或自身的地址。重构子树的节点更改地址后，按ZigBee网络中独立节点方式加入网络拓扑中。通过以下算法可修改网络结构改变后重构子树中节点的地址，具体流程如下。

（1）初始化函数参数，R是子树根节点原地址，R是子树根节点新地址，D是后代节点原地址，函数返回结果是后代节点新地址Dn

（2）若节点D是子树根节点R的后代节点

（3）将D赋值为R，A赋值为R。

（4）递归查找地址A，使其指向节点D

（5）递归计算节点D在新网络拓扑中地址

更改设备地址算法的伪代码如下：

UpdateAddress（R，R，D）

{if（ R< D&& D< （R+ C（depth-1）））

{D=R；A=R；

While（A！= D）

{skip=C（depth）；skip=C（depth）；

index=

A=A+1+index*skip

D=D+1+index*skip }}}

return Dn

网络中节点的地址改变后，网络中其余的节点应该获取改变地址节点的信息，以便能够正确的发送数据包。同时修改协调器中存储的节点信息，使修改后的节点地址与电源类型一致，以便能够正确的计算网络中电池供电节点的总负载。当某个网络拓扑中数据流量稳定时，网络重构会生成一个新的稳定的网络拓扑，新的网络拓扑中会尽可能避免使用电池供电节点转发数据，当发现网络中电池供电节点的总负载减少时，即有更好的网络拓扑时，网络继续进行重构。因为路由节点会不断地检测转发的数据包，并且做相应的记录，因此该算法也能处理网络流量动态改变的情况，当网络中总流量或部分路由中的流量发生变化时，新的网络拓扑重构会进行以适应新的网络流量状态。

3 仿真结果分析

算法仿真分别在使用了PSAR算法和未使用PSAR算法两种情况下进行。仿真中所有变量保持不变，改变以下变量来测量算法的运行效果。这些变量是电池供电节点的数据转发总量，网络规模和电池供电节点占网络总节点数的比例。表示算法效率的变量是网络中电池供电节点总负载的耗能减少百分率（Reduction），定义见（2）式。

（2）

改进算法通过仿真实验和传统树路由算法进行了比较，主要比较优化前后两种网络拓扑中电池供电节点转发数据的总负载。仿真结果证明了使用改进算法重构的网络中能使电池供电节点的总负载平均减少50%以上，证明了改进算法的有效性。

仿真工具采用Omnet++，网络覆盖面积为400×400，网络中路由节点数分别为40和100个，网络中的节点都是具有路由能力的FFD节点，网络协调器参数初始化Cm =5，Rm=5，Lm=5，网络中电池供电节点比例的值依次是10，30，…，90%。仿真实验结果如图3和图4所示。

图3记录了仿真网络中分别为40和100时，网络中电池供电节点的总负载随电池供电节点占网络节点比例的变化。分析可知，当采用改进后的PARA算法，可使电池供电节点的总负载较原网络拓扑平均减少近50%，同时网络中随着电池供电节点比例以及节点密度的增大，PARA算法对网络拓扑重构后电池供电节点总负载的影响也相应减小。说明该算法更适用于电源供电节点占一定比例的网络。

实验结果同时分析了PARA算法的网络路由代价，即控制信息数据量占实际数据量的比重。算法费用主要来自记录或询问设备的电源类型，请求潜在父节点的连接，重构子树节点的地址更改，网络重构后通知其它节点重构子树节点的新地址。由图4 可知，控制信息的数据量比率低于0.6%，算法对网络流量的影响小，算法的稳定性较好。网络规模在40和100时，控制报文的比率相差不大，说明网络规模对该比率并无显著的影响，这是因为当网络规模增大时，控制信息的数据量与网络的总数据量在同比增加。

4 结语

该文在深入研究了ZigBee网络的组网技术及其路由算法的基础上，结合电源供电设备和电池供电设备的特点，提出了一种基于ZigBee树型网络的电源感知路由算法（PARA），并分析了改进算法的性能。由仿真评估可知PARA算法比树路由算法（DAAM）有效的减少了网络中电池供电节点的数据转发量，算法只需少量的通讯开销就可以明显地减少电池供电路由节点的耗能，延长了网络的生存时间。但该算法仅适应于持续电源节点占一定比例的网络，且网络中需含有完全由持续电源节点组成的路径，该算法研究为特定应用环境中网络节点的布置提供了理论基础。

参考文献

[1] IEEE Std.802.15.4，Wireless Medium Access Control（MAC） and Physical Layer（PHY）Specification for Low-Rate Wireless Personal Area network， October 1，2003.

[2] ZigBee Standards Organization.（2006）.ZigBee specification.

[3] Shah，p.，Shaikh，T.，Ghan，l，Shilaskar，S.Power mana- gement using ZigBee wireless sencor network.Emerging trends in engineering and technology，2008.First International Conference on2008：242-245.

[4] Egan，D.The emergence of ZigBee in building automation and industrial control[J].Computering and Control Engineering Journal，2005，16（2），14-19.

[5] Chen，M.Yang，L.T.Kwon，T. Zhou，L.&Jo，M.Itinerary planning for energy efficient agent communications in wireless sensor networks[J].Vehicular Technology，IEEE Transactions on，2011，60（7）：3290-3299.

[6] I.Hwang，J.Baek.Wireless Access Monitoring and Control System based on Digital Door Lock，IEEE Trans[J].Consumer Electron，2007，53（4）.

[7] 薛艳亮，胡建萍，王江柱.基于分布式编址机制的ZigBee组网技术研究[J].杭州电子科技大学学报，2008，28（2）：33-36.

[8] 戚剑超，魏臻.ZigBee树型路由算法的改进[J].合肥工业大学学报，2010，33（4）：529-532.