ZigBee路由算法的研究和改进

刘多多 吴静

摘 要：ZigBee技术作为一种新兴的短距离无线通信技术，具有自组网、低成本和低功耗的优势。伴随着物联网等高新科技的发展，对ZigBee技术的改进成为了关键问题。文中首先论述了ZigBee技术的基本协议和网络配置，之后针对簇树拓扑结构，分别对Cluster-Tree算法和AODVjr算法进行了重点解析和研究。针对网络中AODVjr算法路由发现过程中的RREQ分组导致洪泛的缺点，从分簇角度出发，对传统ZigBee路由算法进行了优化和改进。并通过NS-2模拟仿真实验，主要从报文发送成功率和端到端时延等方面入手进行对比。实验结果表明，改进算法能实现网络负载均衡，使网络生存时间最大化。

关键词：ZigBee网络；Cluster-Tree；AODVjr；路由算法；NS-2

中图分类号：TP391 文献标识码：A 文章编号：2095-1302（2018）04-00-03

0 引 言

ZigBee技术得益于其距离较短、复杂度较低、能耗较低和成本较低的优势，不仅适用于无线传感器网络领域，在军事、环境监控、医疗健康、智能家居和工业应用等领域也有着广泛的应用。

ZigBee协议基于IEEE 802.15.4定义的物理层（PHY）和媒体介质访问层（MAC）制定，之后ZigBee联盟在此基础上对传输层（TL）、网络层（NWK）和应用层（APL）进行了完善[1]。其中，网络层主要负责网络的组件、发现新路由及维护已有路由，路由算法是网络层的核心。

1 ZigBee网络概述

1.1 ZigBee的网絡拓扑结构

ZigBee网络通常包括三种网络拓扑结构：星型拓扑结构、簇树型拓扑结构和网状型拓扑结构。其设置可根据不同的实际需求进行变化[2]。常见拓扑结构如图1所示。

1.2 ZigBee网络配置

ZigBee联盟和IEEE 802.15.4对网络中设备的定义有所区别。根据功能的不同，IEEE 802.15.4将网络中的设备分为全功能设备（FFD）和精简功能设备（RFD）[3]。其中，FFD可担任网络协调器， 也能用作终端设备，与RFD 或其他FFD通信。而RFD仅支持星型结构，只能与FFD通信。ZigBee联盟根据设备功能的区别划分了协调器、路由器和终端设备等。协调器和路由器均为FFD节点，通常网络最外围的终端节点由RFD来充当。

1.3 ZigBee网络地址分配

ZigBee采用分布式寻址方式分配网络地址[4]。当网络中的一个节点同意外部节点通过自己加入该网络时，两个节点建立父子关系。此后，父节点会为该新入节点分配独一无二的网络地址。整个网络结构的地址分配涉及三个参数：Lm（网络的最大深度），Cm（每个父节点最多拥有的子节点数量）， Rm（子节点最多可作为路由器节点的个数）[5]。上述3个参数均由协调器决定。

当网络中的父节点为子节点分配地址时，若d表示父节点的深度，则Cskip（d）地址偏移量可分配地址段的大小为：

首先将协调器深度设为0，则其余节点按照排列顺序依次将深度加1。有路由能力的子节点设备分配地址用Cskip（d）表示，依据式（2）进行地址分配，依据式（3）为终端设备进行地址分配：

2 ZigBee路由算法分析

ZigBee网络层支持树型（Cluster-Tree），AODVjr和ZBR三种算法 。

2.1 树型（Cluster-Tree）路由算法

该算法中，当地址为A，深度为d的ZigBee节点收到目的节点地址为D的数据包后，可通过（4）式对该节点的真实性进行验证，即：

若是，则通过式（5）计算下一跳地址，即：

若不是，则数据包顺着树结构被转发至父节点。Cluster-Tree算法处理流程如图2所示。

2.2 AODVjr 路由算法

AODVjr是在AODV基础上优化路由的发现和维护过程所得[6]。AODVjr和AODV的主要区别如下：

（1）AODVjr路由算法中去掉了AODV路由算法中的目的节点序列号。为了使路由不存在回路，AODVjr路由算法中规定只有目的节点可以进行相应的RREQ分组，即便中间节点有到目的节点的路径也不可以回复RREQ。

（2）AODVjr路由算法通过目的节点向源节点发送相应连接信息维系路由。若没有收到目的节点发来的相应信号，则判断此路径失效，必要时重新进行路由发现。

（3）AODVjr路由算法中去掉了AODV 中的“先驱节点列表”，以简化路由表结构。

当源节点中没有直接到达目的节点的路由时，便会向邻居节点广播RREQ包，请求帮忙查询路径。当某个节点接收到 RREQ包时，首先会判断自己是否有到达目的节点的路径。若有到达的路径，则会依据路由代价的评估确定是否更新其路由表；若没有路径，则接着广播此RREQ包，同时建立相应的反向路由[7]。AODVjr路由查找模式如图3所示。

2.3 ZBR算法

ZBR算法既具有Cluster-Tree算法出色的实时性，又保留了AODVjr进行动态路由选择的优势，由前两种算法有机结合而产生[8]。

按照拓扑结构中存储空间和节点能量的差异，ZBR算法把网络中的主干节点分为两类，即RN+节点和RN-节点[9]，且均为全功能节点。RN+节点由于具有高能量和大内存的特点，可以同时运行Cluster-Tree和AODVjr两种路由算法，而RN-节点只能运行Cluster-Tree一种路由算法[10]。ZBR路由算法处理流程如图4所示。

3 路由算法的优化策略

Cluster-Tree算法虽然有缩短时延和数据聚合方面的优势，但也有缺点，即由于非自适应算法的特性，使其在网络生存时延最大化方面有所不及。而AODVjr算法虽然在路由查找功能方面具有灵活多变的优势，但因需要维护路由表而产生延迟，且容易产生RREQ广播风暴。

为此，本文提出了一种簇树网络路由策略，即对Cluster-Tree + AODVjr进行优化，该算法融合了上述两种改进算法的优点。

3.1 簇的建立过程

首先将ZigBee 网络分成若干簇，通过选定簇首→广播簇首→建立簇→生成相应调度机制 。

单个簇包括多个节点，根据功能分为3种类型：网关节点、簇成员和簇首。簇建立的规则如下：

（1）将中心节点当作簇首；

（2）充当簇首的节点必须拥有路由能力；

（3）充当簇首的节点网络深度必须为偶数；

（4）若节点网络深度为奇数，则属于其父节点的簇；

（5）終端节点的簇属于其父节点的簇。

簇首负责在建立路由后进行广播，建立簇结构，负责对簇成员的数据进行收集，并在融合处理后发送给网关节点。

形成簇之后，判断网络深度，若该节点的网络深度为偶数，则向外广播RREQ。当一个节点收到RREQ时，便向源节点发送确认信息，发送RREQ的源节点将收到的确认信息与规定的最小信号强度进行比较，若大于该值，则在邻居表中添加此节点。最后，通过对比邻居表中周围节点的数目将节点数最多的节点选作为簇首，同时，将此节点的短地址作为该簇的标签。

若一个节点被选作簇首节点，则向其周围节点发送广播报文，收到广播报文的节点发送簇加入报文，当簇首发送对应的加入响应后，成功加入到该簇。

3.2 路由过程的建立与维护

当源节点需要给目标节点发送数据时，首先在路由表中查寻目标节点的路径。若路由存在且有效，则直接发送数据；若路由不存在，则源节点通过泛洪进行路由发现。建立路由后，源节点向周围节点广播由其创建的一个路由请求包RREQ。若一个邻居节点收到RREQ，则通过计算得出目的节点的簇标签，并将该簇标签的一个路由接入点加入到其邻居表中。若一个中间节点收到RREQ，则进行路由成本的比较，若该路由成本较低，则更新路由搜索表信息，并且在到达目的节点之前持续广播。

当目标节点收到路由请求后，建立反向路径，并生成一个RREP包，该RREP包中含有最新的各类信息，沿反向路径送至源节点。当源节点和中间节点收到RREP包后，开始进行目标节点路由的建立和系列号等信息的更新。该路由过程建立完成后，源节点向其簇首发送一个携带有路由信息的路由确认包，簇首在收到该确认包后再广播一个路由更新信息，簇成员收到该信息后，完成节点新建路由信息的共享。

此改进表现出了对分簇思想应用路由算法的巨大优势，簇头负责融合数据，减少了数据通信量。同时，分布式算法又可以在拓扑结构得到巨大的施展空间，在大规模网络场景下有着良好的发挥余地。并且由于簇内节点长时间关闭通信模块，又达到了网络时延的效果。

4 实验结果分析

采用NS-2软件对改进后的算法和AODVjr进行仿真实验比较，从发送报文的成功率和平均时延两个方面进行分析。

报文发送成功率比较如图5所示，从图中可以看出，新算法发送报文的成功率与原算法相比有了明显提升。

两种算法的平均时延对比如图6所示。由图6可知，在源节点数目等同的实验条件下，随着节点数目增加，时延呈上升态势。经分析可知，超过正常范围数目的源节点增加了网络拥塞程度，从而增加了成功接收数据包的时间。而在源节点数目相同的情况下，优化后的算法拥有较小时延。

5 结 语

本文在分析ZigBee路由算法的基础上，提出了一种改进算法。将邻居列表引入改进后的算法，在数据传输过程中，对路由跳数等方面进行了重新考量，同时从基本策略方面对AODVjr进行了改进，考虑到能量的维度，使网络生存时间得到了有效延长，提升了网络效率，并通过相关仿真实验对以上结论进行了验证。

参考文献

[1] 唐寅.基于 ZigBee 的传统路由协议研究与优化 [D]. 武汉：湖北大学，2013.

[2] 耿萌.ZigBee 路由协议研究与分析 [D].郑州： 中国人民解放军信息工程大学 ，2006.

[3] 袁安娜.基于 ZigBee 网络的能量均衡路由算法研究 [D].哈尔滨：哈尔滨理工大学，2014.

[4] 班艳丽，柴乔林，王芳.改进的 ZigBee 网络路由算法[J].计算机工程与应用，2009，45（5）：95-97.

[5] 凌志浩，周怡頲，郑丽国.ZigBee无线通信技术及其应用探讨[J]. 华东理工大学学报（自然科学版），2006， 32（7）：801-805.

[6] 彭瑜.低功耗、低成本、高可靠性、低复杂度的无线电通信协议——ZigBee[J].自动化仪表，2005，26（5）：1-4.

[7] 鲍凤卿.基于NS-2的ZigBee网络节点接入的研究[J].信息技术，2008，11（5）：95-98.

[8] 钱志鸿，朱爽，王雪.基于分簇机制的 ZigBee 混合路由能量优化算法[J].计算机学报，2013， 36（3）：485-493.

[9] 吴非.基于ZigBee技术的无线传感器网络路由算法研究[D].北京：北京邮电大学，2015.

[10] 蒋培成，陈鸣，李兵.一种优化ZigBee性能的综合加权路由算法[J].小微型计算机系统，2013，34（9）：2014-2017.

[11] CHEN S K，WANG P C.Shortcut anycast tree Routing in MANETs[J].IEEE international conference on advanced information networking & applications，2012，11（1）：635-640.

[12] FENG S，WANG M G，Yu Q L，et al.Improved neighbor table-based tree routing strategies in ZigBee wireless networks[C]. International Conference on Information Science & Technology，2015 ： 513-518.

[13] HOU T C，TSAI T J.An Access based clustering protocol for multihop wireless Ad-Hoc networks[J].IEEE joumal on selected areas in communications，2001，19（7）：1201-1210.