基于ZigBee无线网络的Cluster-Tree路由算法研究*

赵　博，吴　静

(1.西南科技大学 信息工程学院，四川 绵阳 621010；2.特殊环境机器人技术四川省重点实验室，四川 绵阳 621010)

基于ZigBee无线网络的Cluster-Tree路由算法研究*

赵博1，2，吴静1，2

(1.西南科技大学 信息工程学院，四川 绵阳 621010；2.特殊环境机器人技术四川省重点实验室，四川 绵阳 621010)

针对ZigBee无线网络中Cluster-Tree算法只依靠父子关系路由且ZigBee技术传输带宽的限制，致使网络中负载较重的链路不能及时传递信息，而造成网络拥塞、丢包和较低的吞吐量问题，提出了一种改进算法 Z-DMHCTR。该算法针对负载超过一定限度的节点，除了按照原等级树算法路由之外，结合引入的邻居列表信息，寻找节点不与原路径相交的路径同时进行信息传输，从而提高网络带宽利用率，达到提升网络的吞吐量的目的。仿真实验主要从网络吞吐量、端到端数据传输延时等方面入手进行对比。结果表明，改进算法能够有效地提高网络吞吐量，并降低了传输数据的延时。

ZigBee网络；Cluster-Tree算法；Z-DMHCTR算法；邻居列表

0　引言

无线传感器网络技术(Wireless Sensor Network，WSN)是物联网的关键技术，是全球未来四大技术产业之一［1］。而 ZigBee技术因其低成本、低功耗、低复杂度、高可靠性等特点，在工业自动化、农业、交通运输、智能家居、医疗等领域都得到广泛应用［2］。ZigBee网络拓扑结构主要有星型(Star)、树形(Tree)和网状(Mesh)3种网络结构［3］。其中ZigBee树型拓扑结构因扩展方便覆盖范围广，且Cluster-Tree算法仅依靠父子关系路由，不需要进行路由发现和路由列表维护，因而很大程度上降低了网络泛洪压力，节省了网络带宽，降低了开销和能耗，所以被广泛的应用到低功耗、低成本的无线传感器网络中［4］。

然而，当所构建的网络中要采集大量信息时，承担较大业务量的底层节点往往因依据 Cluster-Tree算法进行路由不能及时传输信息，而造成丢包和传输延时。同时信息量传输大的路径上，节点能耗快，因而容易导致网络分割。比如煤矿开采［5］等环境复杂多变的情况下，采集节点平时需要传输的数据比较少。但当出现突发事件时，需要紧急传输大量详细信息。此时网络中容易出现拥塞、丢包等问题，不利于控制中心的处理。如何降低网络拥塞，提升网络吞吐量是目前面临的重要问题。

目前对ZigBee树型拓扑结构的改进算法中，如参考文献［6-9］中提到的HCTR算法、ENTR算法、一种改进的Cluster-Tree算法和SATR算法，往往是通过结合引入的邻居列表,从距离上优化路由的下一跳，而并未考虑其所选下一跳是否发生拥塞，或是否在发生拥塞的路径上，以及当节点发生拥塞后如何处理的问题。因此本文提出Z-DMHCTR算法，不仅使一跳范围内的传输可以直接通过邻居列表送达，而且对于缓存区剩余容量小于一定数值的节点，可利用其邻居列表寻找额外的路径进行传输。在额外路径的选取中，首先要考虑转发节点的缓冲区大小；然后通过选中的节点转发数据时，要避免选用发生拥塞的节点所在的源传输路径上的节点进行转发，以此降低再次发生拥塞的可能性，提升网络吞吐量。

1　ZigBee无线网络Cluster-tree路由机制

ZigBee无线网络中根据设备功能不同分为两类：可用来充当协调器和路由器的全功能设备FFD和仅用来充当终端叶子节点的精简功能设备RFD。在ZigBee网络中，每个节点都具有 64位的 IEEE扩展地址作为其唯一的标识。此外，还会获得由其父节点动态分配的16位网络地址［10］。以下分别介绍ZigBee网络层地址分配机制和等级树路由过程。

1.1ZigBee网络地址分配

ZigBee网络地址分配涉及到 3个重要参数：Lm(网络的最大深度)、Cm(父节点最多可拥有的子节点的个数)、Rm(子节点中最多可为路由节点的个数)。以上参数由协调器设定。网络中父节点为子节点进行地址分配时，地址偏移量 Cskip(d)可由式(1)计算得出，其中 d为父节点深度［10］。

根据子节点类型不同，地址分配分别依据式(2)和式(3)进行。

其中Ap为深度为d的父节点地址。

1.2Cluster-tree路由算法实现过程

Cluster-tree路由算法依靠父子关系进行。根据以上ZigBee网络地址分配公式，当节点收到目的地址为D的数据包后，可依照式(4)判断 D是否为自己的后代节点。若是则按照式(5)进一步计算下一跳地址，否则向上发给父节点［10］。

其中A为深度为d的节点的地址。

2　改进算法设计

通过引入邻居列表，使空间相近的节点可以直接送达，从而不仅可以降低传输延时，还可以节省能量。同时在该邻居列表中添加邻居节点的剩余缓冲区大小和邻居节点拥塞示警位，以便在传输过程中降低发生拥塞的可能性。如果当节点检测到自身缓冲区达到某预定值，则发起寻找到目的节点的额外的与自身传输路径不相交的路径进行信息的传输，从而避免再次发生拥塞，提高网络吞吐量。

2.1拥塞示警机制

首先在邻居列表中设置了剩余缓冲区大小(Buffer size)和拥塞警示位(Congestion alarm)。其中，剩余缓冲区大小由节点缓存队列的剩余值表示，并根据节点收发数据情况进行动态更新。当节点缓冲区大小高于特定值时，拥塞警示位置0，节点按照正常方式进行路由；否则，拥塞警示位置1，节点会寻找额外路径进行转发，同时尽量避开已发生拥塞的节点。邻居列表的更新是通过对收到的数据包的包头进行分析进行的。

2.2Z-DMHCTR算法

改进算法的目的是能够使 ZigBee等级树路由算法更好地处理大量或高速率数据的传输问题。因此当节点发生拥塞时，可通过寻找额外的节点不相交的路径同时进行信息传输，从而提高网络的带宽利用率，增加网络吞的吐量。寻找节点不相交路径是为了降低再次发生拥塞的可能性，因为所选中下一跳节点可能与发生拥塞的节点具有相同的公共传输节点。

2.2.1算法描述

假设网络中所有信息都传输至汇聚节点 sink(协调器或簇首节点)，在ZigBee树型拓扑结构中，依据上节描述，Z-DMHCTR算法中每个路由节点维护一个邻居列表。当网络中传输数据量较低时，仅结合邻居列表进行判断一跳范围内的直接传输，否则按照原路由方式进行。若当某一节点缓冲队列的剩余大小等于邻居节点个数时拥塞示警位置1，则发起寻找额外的节点不相交路径的过程。发生拥塞的节点对邻居列表中非父节点进行筛选，将数据包转发至拥塞警示位为0且剩余缓冲区大的节点处。作为转发的中间节点，则需要依靠树型路径信息，从邻居列表中挑选出不与上发送节点相交的传输路径进行数据传输。对于挑选出的节点，再进一步判断缓存区大小，从而挑选出适合的节点进行转发。

2.2.2树型路径信息

为了降低发生拥塞的可能性，通过引入ZigBee树型拓扑结构中父子关系路径信息，来挑选节点不相交的路径进行信息传输。其中父子关系路径信息指的是依据ZigBee网络地址所计算出的当前子节点为其父节点的第几个子节点。例如给定一个地址为Ai的节点，其深度为di∈［1，Lm］，则在ZigBee树型网络中从节点Ai到sink节点的父子关系路径信息可以定义为一个集合ZTPi= (C1，C2，…，Cdi)，其中 Ck(1≤k≤di)取整，表示位于 k-1层的父节点的第Ck个子节点。Ck可通过式(6)计算。

当Ck取0时表明路径已经终止。根据节点类型不同，集合 ZTPi分为以下两种类型：

转发节点通过式(6)计算出父子关系路径信息的集合，然后同发送节点的集合中元素进行对比，从而可以判断其公共节点所在的位置和深度。避免在依据等级树路由方式路由时，采用相同节点转发数据。

2.2.3Z-DMHCTR算法实现

在源节点s向sink节点发送数据包的过程中：

(1)发送节点（可能为源节点，也可能为中间节点）检测到自身拥塞标志位γ=1后将相关信息封装至分组头部后，发起额外路径寻找过程。

(2)通过查询邻居列表筛选出非父节点到一个结合中，对集合中节点的拥塞警示位进行判断，若集合中节点均发生拥塞，则跳转至步骤(5)执行，否则继续执行；

(3)优先挑选邻居列表中，剩余缓冲区较大的节点进行转发；

(4)中间节点收到数据包并获取分组头信息后，若发现分组中拥塞标志位置1，则将自身的路径信息集合与发送节点的路径信息进行对比。设变量l、i。l表示当前节点的集合中最后一个不为0的元素，i表示两集合中最先出现不同的元素为第i个元素：

①若i=1，则相同节点为sink节点，执行步骤(5)；

②若i=l，则两节点共父，跳转至步骤(2)执行；

②若1＜i＜l，则该中间节点同源节点在深度 i-1处有公共父节点，执行步骤(5)；

(5)仍按等级树路由方式路由至下一跳节点；

(6)传输过程中节点按照步骤(1)～(4)执行，直至信息传输到sink节点。

算法具体传输过程举例如下：因算法所挑选的路径的数目会受到协调器子节点数目和发送节点邻居节点数目的影响，所以建立如下环形网络。其中(Lm，Cm，Rm)= (3，4，4)，协调器位于圆心，其余不同深度i的子节点部署在半径为iR的同心圆上，如图1所示。

其中 s为源节点，d为汇聚节点。根据式(1)结合所设定的参数可计算出深度为 0，1，2时地址块 Cskip分别为21，5，1。然后结合式(2)计算出各节点地址。TR为所设定的节点的通信范围，确保一个节点在其通信范围内除父节点外，至少存在两个邻居节点，以增加找到额外路径的几率。比如源节点 s，其邻居节点为 i，f，g。正常情况下数据包的传输路径为s→f→a→d，结合式(6)计算所得的等级树路径信息记为ZTPs=(1，1，1)。即s为其父节点f的第一个子节点，f为其父节点a的第一个子节点，依次类推。如果当源节点s拥塞标志位置1后，节点s依据其邻居列表寻找额外的路径。当选择节点g为其下一跳并转发数据包后，节点g通过将自身的树路径信息集合 ZTPg=(1，1，2)，与源节点 s的进行对比，可知其第一个不同元素出现的位置为集合中第3个元素，则可判断两节点s和g共父节点。所以节点g从其邻居列表中挑选非父的节点k为其下一跳。当k收到数据包后同样将 ZTPk=(2，1，1)与 ZTPs进行对比，其第一个不相同的元素位于第一位，由此可知节点k同节点s只有在sink节点处才相交。因此节点k可按照等级树路由方式进行路由，由此寻找到的第二条路径为s→g→k→p→b→d。同样如果 s选择的下一跳节点为 i，由同样的过程可以得出另一条传输路径为s→i→h→j→c→d。如此可以在避免二次发生拥塞的情况下，将数据传输至 sink节点，从而降低丢包率，提升网络吞吐量。

图1　传输路径示意图

3　Z-DMHCTR路由协议性能仿真与分析

3.1仿真环境

仿真基于NS2平台，重点将传输过程中，ZDMHCTR算法在网络平均吞吐量、分组递交率和端到端的平均传输延时与 Cluster-Tree算法进行比较分析。仿真结果证明了改进算法是有效的。

本实验利用IEEE802.15.4的PHY层和MAC层来实现网络层的仿真，网络覆盖区域大小为150 m×150 m，网络布局依照同心圆建立。协调器节点位于网络中心，同心圆半径为节点所在深度倍的R。所有仿真数据通过对网络独立运行20次取平均值所得。仿真过程中通过 Trace文件对实验数据追踪记录，并通过 gawk工具对其进行提取和处理，最后通过 gnuplot工具绘制二维图形并对结果进行分析。具体仿真环境的参数如表1所示。

3.2仿真结果与分析

实验过程中通过将节点缓冲队列设置的较小，并且采用Pareto分布流量产生器，从而使节点缓冲队列长时间处于拥塞状态。仿真结果如图2所示。

图2所示的分组递交率是通过式(8)计算所得，其中仅包括发生在路由层的传输包。

表1　仿真参数及取值

图2　分组投递率

从图中可以看出改进后算法的分组递交率优于改进前算法。尤其在网络运行至80 s时，改进前后算法的分组头地率有最大差值，此时改进前后算法的分组投递率分别为9.742%、11.932%,改进后算法提高了2.19%。

图3中平均吞吐量指的是单位时间内成功传输的数据量，可由式(9)计算。

其中 N为成功传送的分组数，Psize为一个封包的大小，tstart和 tend分别为仿真模拟的开始和结束时间。

图3　平均吞吐量

虽然随着网络的运行，改进前后算法的吞吐量均呈下降趋势，在50 s～80 s间改进后算法平均吞吐量明显高于改进前算法，从表2中可以看出在70 s处两者出现最大差值2 760。说明改进后算法通过多条路径传输确实改善了网络吞吐量。

表2　改进前后算法在不同时刻网络平均吞吐量

图4为发送节点数目增加时，网络整体的平均吞吐量变化情况。

图4　全网平均吞吐量

Z-DMHCTR算法所挑选的路径数目会受到邻居节点等的影响，而且大量传输包发送至汇聚节点容易发生碰撞而导致丢包，因此增加发送节点个数进行仿真。可以看到，改进前后算法网络整体吞吐量增长情况均变缓，但Z-DMHCTR算法通过寻找额外的传输路径与原算法相比仍提升了网络的吞吐量。

图5所示的平均端到端延时是通过式(10)计算所得：

其中 N为成功传送的分组数，tr(i)为分组传输至目的节点的时间，ts(i)为分组被发送的时刻。虽然改进后算法通过非父子关系路径传输数据时可能使传输条数增多而增加部分延时，但同时也降低了数据包在节点处缓存而引发的延时。从实验结果可以看出，虽然延时相差非常小，但改进算法因为所选路径不为最短所造成的网络延时并未影响网络整体性能。

图5　平均端到端延时

4　结束语

目前，ZigBee技术依然是最适合传感器网络接入端的短距离无线通信技术。而其树型拓扑结构也因为支持节能操作和轻量级路由并且已扩展而得到了广泛应用。但因Cluster-tree路由特点和 ZigBee技术本身传输带宽限制，使其对突发大量数据的传输或图像传输等一些高数据速率应用的处理存在问题。本文针对上情况提出改进的Z-DMHCTR算法，使网络中节点发生拥塞前能够寻找额外路径传输数据，从而不仅可以提升网络吞吐量，降低丢包率，还可以均衡网络负载，避免部分节点因过度使用而死亡造成网络分割，从而提升了网络整体的性能。

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

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

［3］马海潮.ZigBee网络可扩展性及分簇路由协议研究［D］.西安：西安电子科技大学，2014.

［4］赫晓萌.基于ZigBee的无线粮情检测系统中路由协议的研究［D］.北京：北京邮电大学，2009.

［5］刘国梅，谢晓广，白首华.基于煤矿安全监测的 ZigBee路由协议改进［J］.工业安全与环保，2015，41(1)：99-102.

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

［7］Feng Shuo，Wang Mingan，Yu Qilin，et al.Improved neighbor table-based tree routing strategies in ZigBee［C］.Information Science and Technology(ICIST)5th International Conference，2015：513-518.

［8］班艳丽，柴乔林，王芳.改进的ZigBee网络路由算法［J］.计算机工程与应用，2009，45(5)：95-97.

［9］Chen Shyr-Kuen，Wang Pi-Chung.Shortcut anycast tree routing in MANETs［C］.Advanced Information Networking and Applications(AINA)26th International Conference，2012：635-640.

［10］钱志鸿，朱爽，王雪.基于分簇机制的 ZigBee混合路由能量优化算法［J］.计算机学报，2013，36(3)：485-493.

Research on Cluster-Tree algorithm based on ZigBee wireless network

Zhao Bo1，2，Wu Jing1，2
(1.School of Information Engineering，Southwest University of Science and Technology，Mianyang 621010，China；2.Robot Technology Used for Special Environment Key Laboratory of Sichuan Province，Mianyang 621010，China)

For Cluster-tree algorithm only relays on parent-child relationship to rout in ZigBee wireless network and the limited bandwidth of ZigBee technology will result in that the heavily loaded link can′t timely transmit information and so prone to network congestion,packet loss and lower network throughput problem，this paper proposes an optimization algorithm,the Z-DMHCTR algorithm,which combines with neighbor list among the nodes to find a node disjoint paths with the original path to transmit information，thereby improving network bandwidth utilization and increasing the network throughput.Through the simulation,this paper compares the difference of improved algorithm and the original algorithm in the network throughput,end data transmission delay and other aspects of difference.The result shows that the improved algorithm effectively improves the network throughput,and reduces the time delay of data transmission simultaneously.

ZigBee network；Cluster-Tree algorithm；Z-DMHCTR algorithm；neighbor list

TP393

A

10.16157/j.issn.0258-7998.2016.04.032

四川省 2014年科技计划项目（2014JY0215）

2015-12-23)

赵博(1989－)，女，硕士研究生，主要研究方向：ZigBee技术、物联网。

吴静(1963－)，女，副教授，硕士研究生导师，主要研究方向：无线传感器网络、通信技术、三网融合、物联网。

中文引用格式：赵博，吴静.基于ZigBee无线网络的Cluster-Tree路由算法研究［J］.电子技术应用，2016，42(4)：116-119，123.

英文引用格式：Zhao Bo，Wu Jing.Research on Cluster-Tree algorithm based on ZigBee wireless network［J］.Application of Electronic Technique，2016，42(4)：116-119，123.