改进的ZigBee网络路由算法

徐沛成，胡国荣

（中国科学院微电子研究所，北京100029）

0 引 言

ZigBee通信技术的MAC层和PHY层基于IEEE802.15.4标准协议，ZigBee联盟在此基础上定义了ZigBee的NWK层和APL层，使其构成一套完整的标准协议。ZigBee技术在传感器网络中的应用已日益受到重视，低成本、低功耗、低数据传输速率、低复杂度等优点满足了小型、低成本的固定、便携或移动设备无线联网的要求［1］。ZigBee协议的 NWK层［2］负责建立和管理网络，其核心问题是路由算法，路由算法直接关系到网络中节点转发的跳数、网络的时间延迟以及网络能量的消耗［3］。

1 ZigBee网络概述

1.1 网络结构

ZigBee网络层主要支持3种网络拓扑结构：星形（star），网状 （mesh）以及属性 （cluster－tree）结构［4］。根据IEEE802.15.4标准协议可以将设备分成2种类型：FFD和RFD，其中FFD是指全功能节点设备，能够组织建立网络，也有能力管理其它节点的加入与离开网络，而RFD是指精简功能节点设备，不能组建网络，只能选择已有的网络加入，也没有管理其它节点的功能。ZigBee网络中的协调器 （coordinator）和路由器 （router，可分 为 RN＋、RN－）必须都是FFD，RN＋具有路由功能，RN－没有路由功能，而终端节点设备 （end device，ED）则可以是RFD也可以是 FFD［5］。

1.2 地址分配机制

ZigBee网络地址分配采用分布式地址分配机制［6］，即为每个潜在的父节点提供有限的地址块，再由父节点把地址分配给子节点。ZigBee网络中的协调器决定网络中允许的最大设备数，参数Rm决定父节点设备的子节点中的路由器的数目，其余设备为终端节点，不具有路由能力。每个设备都有相关深度，用Lm表示，指示其与协调器传输数据帧所需要的最少跳数。每个父节点可以拥有的最大子节点数目用Cm表示。Zigbee网络中的协调器的Lm为0，地址为0X0000，其子节点的Lm为1，协调器决定网络的最大深度。对于深度为d，地址为Af的父节点为它的有路由器能力的子节点分配的网络地址块如式 （1）。若设备的Cskip（d）为0，则表示该设备没有路由能力接受子节点，只能作为终端节点，若大于0，则表示该设备可以接受子节点设备，并根据其路由能力给子节点分配地址。父节点为它的第一个有路由能力的子节点比自己大1，为每个有路由能力的子节点设备分配的地址用Cskip（d）分离，如式 （2）所示，为终端节点设备分配地址如式 （3）所示

2 ZigBee网络的路由算法

2.1 Cluster－tree树型路由算法［7－8］

Cluster－tree算法采用树型分层路由，地址为Ar、深度为d的路由节点收到目的地址为D的帧，若目的地址为自己则直接接收，否则用式 （4）判断目的地址是否是其子节点，若是子节点，则转发给合适的子节点，若不是，则转发给自己的父节点

Cluster－tree算法简单，帧总是沿着树型路径转发，由于没有路由功能，不需要存储路由表，节省了存储空间，节点造价低。但是该算法属于静态路由，不适合移动场合，并且由于帧的转发总是沿着树型路径，导致越靠近协调器的节点的转发任务越重，消耗也越大，而且容易造成路径拥堵。

2.2 AODVjr路由算法

AODVjr协议［9－11］是 AODV协议的简化，AODVjr协议考虑到了无线节点的有限移动性，并且最大限度的降低了节点能耗。在AODVjr协议中取消了AODV协议的HELLO消息、路由错误信息、问询序列号等措施，但保留了按需路由的特性。由于AODVjr协议的能耗远远小于AODV协议，所以在无线传感网络中越来越多地使用AODVjr协议。

3 路由算法问题分析

如图1所示的树型网络可以分为3个区域，分别标记为区域1，区域2，区域3。根据Cluster－tree算法，帧的传输总是沿着树型路径，因此若区域3中的E节点想要发送帧给区域1中的 D节点，其发送路径为 E－F－G－H－A－C－D，需要6跳来完成，但是从图中可以看出，E节点与D节点距离很近，E节点完全可以直接把帧发送给D节点，即ED，只需1跳。所以这种按树型路径转发的路由算法虽然简单，但是不仅增加了转发次数也造成了时间上的延迟以及能量消耗的浪费［12］。

图1 区域间相邻节点路由分析

AODVjr路由算法比AODV更简单有效，但是其发送的RREQ容易引起广播风暴，从而增加网络能量消耗。如图1所示，若区域3中的节点G想要发送数据给区域2中的节点B，它们之间有3跳的距离，但是在使用AODVjr路由算法寻找路径时，RREQ在大于3跳时仍会被转发，造成能量的不必要消耗，并且RREQ没有方向选择，容易形成广播风暴。

4 ZigBee路由算法的改进

4.1 Cluster－tree算法的改进

改进算法为Cluster－tree算法加入邻居表，邻居表是节点周围一跳范围内的节点列表，是节点加入网络的时候在通过发送广播帧得到的回复消息的基础上建立的，能够一跳把消息发送到周围目的节点。在邻居表中可以为每个节点建立一个记录条目，记录包括节点在网络中的地址，节点的设备类型等信息，当周围节点信息发生变化时对邻居表进行更新。

改进后的Cluster－tree路由算法：

（1）子节点查找。当节点收到一个数据帧时，先检查目的地址D是否是自己，若是，则直接接收，若不是，则利用式 （4）判断该目的地址是否是自己的子节点，若是，则转发给相应的子节点，若不是，转向 （2）。

（2）邻居节点查找。若目的地址D存在于邻居表中，则直接发送给相应的邻居节点，若不在，则使用式 （5）选择邻居节点Ak中到达D最近的节点Ac为

其中Ak，k＝0，1…m为邻居表中邻居节点的地址。若Ac节点为RFD则转向 （3），若为FFD则使用式 （4）进行判断D是否是Ac子节点，即

若目的地址D是Ac的子节点，将数据帧转发给Ac，若目的地址D不是Ac的子节点，转向 （3）。

（3）父节点查找。若目的地址D不是Ac的子节点，计算出Ac的父节点Ar，判断是否是D，若不是，则根据式（4）判断是否是Ar的子节点。若是其子节点则将数据帧转发给Ac，否则将数据发给自己的父节点。

具体流程图如图2所示。

图2 改进的Cluster－tree算法流程

4.2 ADOVjr路由算法的改进

为了对RREQ的发送方向进行选择，可以在RREQ的分组中增加标志位flag，若flag为0则表示子节点可以转发而父节点不必转发，若flag为1则表示父节点可以转发而子节点不必转发，从而对RREQ的发送方向进行选择，具体过程如下：

（1）当网络中的一个节点收到RREQ时，先判断自己是否是其目的地址，若是，则直接回复，若不是，则转向（2）。

（2）Ls为源节点的深度，若当前跳数大于Lm＋Ls时，应丢弃该RREQ，否则转向 （3）。

（3）判断flag的值进行方向选择，若flag＝0，则转向（4），若flag＝1，则转向 （6）。

（4）判断当前节点是否是前一跳的父节点，若是，则丢弃该RREQ，若不是，则转向 （5）。

（5）判断目的节点是否是当前节点的子节点，若是，继续转发，若不是，修改flag位为1，转向 （8）。

（6）判断当前节点是否是前一跳的子节点，若是，丢弃该RREQ，若不是，则转向 （7）。

（7）判断目的节点是否是当前节点的子节点，若不是，继续转发，若是，修改flag位为0，转向 （8）。

（8）转发RREQ，当到达目的节点时，目的节点需回复RREP。

中间节点处理RREQ的过程如图3所示。

图3 中间节点处理RREQ的过程

4.3 两种路由算法的结合与改进

ZigBee网络中的节点可以分为：Coordinator、RN＋、RN－、RFD［13］，其中前三者都是全功能节点，Coordinator、RN＋能够建立和管理网络，具有路由功能，使用AODVjr路由算法，RN－节点没有路由功能，使用Cluster－tree路由算法沿树型路径转发数据，RFD只能作为终端节点。

当RN－节点收到数据帧时使用改进的Cluster－tree路由算法进行转发，减少数据帧在网络中的转发跳数以及网络时间延迟。当Coordinator和RN＋节点收到数据帧时，因为具有路由能力，所以优先查找路由表条目是否包含目的节点地址，若有，则直接发送，若不包括，则不立即使用AODVjr路由算法而是先使用改进的Cluster－tree算法，若成功，则转发数据帧，若失败则启用改进的AODVjr路由算法。这样可以充分利用树型网络结构特点，减少时间上的延迟以及路由发现过程中能量消耗。

5 仿真与结果分析

为了模拟真实环境，采用NS2仿真软件，通过修改代码与仿真参数观察仿真结果。实验采用独立多次仿真，然后取其平均值，以减小误差。实验的网络结构为协调器位于中心位置，网络中的其它节点随机分布在协调器周围。其它参数如下：网络结构大小：150m×150m，有效数据源：CBR，数据帧传输距离：10m，实验中的数据帧大小为80Byte，另外Lm，Rm，Cm分别为6，4，5。

在图4中对原Cluster－Tree算法和改进的Cluster－Tree算法在网络中运行所需要的平均跳数进行了对比，从图中可以看出，随着选取的节点数目不断增加，两种算法所需要的跳数都在增加，但是改进的Cluster－Tree算法所需要的跳数要少于原Cluster－Tree算法，并且随着节点数的增加，跳数减少的更加明显。在图5中对原Cluster－Tree算法和改进的Cluster－Tree算法在网络中的平均时间延迟进行了对比，从图中可以看出，随着选取的节点数不断增加，两种算法的时间延迟都在增加，但是改进后的Cluster－Tree算法的延迟要小于原Cluster－Tree算法，并且这种趋势也随着节点数的增加变的增加明显。综合平均跳数与平均时间延迟来看，在这两种对比中改进的Cluster－Tree算法都优于原Cluster－Tree算法，其所需要的跳数更少，时间延迟更小，从而能量消耗也会减少，提高了网络的整体性能。

在图6中对AODVjr路由算法，AODVjr＋Cluster＋Tree算法和改进的AODVjr＋改进的Cluster＋Tree算法在网络中的平均跳数进行了对比，从图中可以看出AODVjr路由算法所需要的平均跳数最多，因为其在路由表没有相关条目时需要进行路由发现从而建立发送路径，而采用AODVjr＋Cluster－Tree算法的平均跳数要小于AODVjr算法，因为邻居表的存在，使得其可以很快的做出转发，而不必进行路由发现，改进的AODVjr算法＋改进的Cluster＋Tree算法因为能够有效的利用邻居表和选择RREQ的转发方向，所以平均跳数最少。在图7中对AODVjr路由算法，AODVjr＋Cluster＋Tree算法和改进的AODVjr＋改进的Cluster＋Tree算法在网络中的平均时间延迟进行了对比，时间延迟和转发跳数有一定的关系，AODVjr算法所需要的时间最多，AODVjr＋Cluster－Tree算法次之，而改进的AODVjr算法＋改进的Cluster＋Tree算法所需时间最少。综合平均跳数与平均时间延迟来看，改进的AODVjr算法＋改进的Cluster＋Tree算法最优，也即该算法在网络中的路由效率最高。

6 结束语

本文对ZigBee网络的两种现有算法Cluster＋Tree算法和AODVjr算法都进行了改进优化，并对这两种算法进行了综合利用，提出了改进算法。在原Cluster＋Tree算法中加入邻居表，建立一跳范围内的链路信息，在原AODVjr算法中加入标志位flag控制RREQ的转发方向。对两种路由算法综合利用后的改进路由策略为RN－节点直接使用改进后的Cluster＋Tree算法，而RN＋节点则先使用改进后的Cluster＋Tree算法，若失败在启用改进后的AODVjr算法。通过仿真实验结果可以看出，这种改进的算法在转发跳数和网络时间延迟等方面都要优于原来的算法，能够有效提高ZigBee网络的总体性能。

［1］GAO Lipeng，ZHU Meidong，YANG Dan.Simulation and implement of weighted centroid localization algorithm based on ZigBee ［J］.Chinese Journal of Sensors and Actuators，2010，23 （1）149－150 （in Chinese）. ［郜丽鹏，朱梅冬，杨丹，基于ZigBee的加权质心定位算法的仿真与实现 ［J］.传感技术学报，2010，23 （1）149－150.］

［2］LIU Lijun，TONG Lili，ZigBee network layer routing algorithm analysis ［J］.Compu－ter and Information Technology，2008 （1）：70－72 （in Chinese）.［刘丽钧，童丽丽.ZigBee技术网络层的路由算法分析 ［J］.计算机与信息技术，2008（1）：70－72.］

［3］GUO Ruixing，WANG Qingsheng，Research and Improvement on the Routing Algorithm in ZigBee Networks ［J］.Computer Development ＆ Applications，2011，24 （5）32－33 （in Chinese）. ［郭瑞星，王庆生.ZigBee路由算法的研究与改进［J］.电脑开发与应用，2011，24 （5）32－33.］

［4］WANG Chen，CHAI Qiaolin，WANG Fang.Energy balanced protocol research based on tree structure ZigBee ［J］.Computer Engineering and Design，2009，30 （15）：3534－3586 （in Chinese）.［王琛，柴乔林，王芳.基于树形结构的ZigBee能量均衡协议研究 ［J］.计算机工程与设计，2009，30（15）：3534－3586.］

［5］XIE Chuan.Research of AODVjr algorithm based on ZigBee［J］.Computer Engineering，2011，37 （10）87－88 （in Chinese）.［谢川.基于ZigBee的AODVjr算法研究 ［J］.计算机工程，2011，37 （10）87－88.］

［6］ZigBee.Alliance.ZigBee.specification.2008 ［DB／OL］.［2013－01－10］.http：／／www.zigbee.org.

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

［8］Dilum Bandara H M N，AnuraP Jayas－umana.An enhanced top－down cluster and cluster tree formation algorithm for wireless sensor networks ［C］／／International Conference on InduS－trial and Information Systems，2007：565－570.

［9］ZHAGN Qing，LIU Shumei，CHAI Qiaolin.Energy efficient improved routing strategy for ZigBee network ［J］.Computer Engineering，2010，36 （7）：108－109 （in Chinese）. ［张擎，刘淑美，柴乔林.能量高效的ZigBee网络改进路由策略 ［J］.计算机工程，2010，36 （7）：108－109.］

［10］ZOU Xiaowu，XU Du，JIANG Yongping，et al.Analysis and improvement for basic Zigbee wireless networks route［J］.Computer Knowledge and Technology，2009，5 （33）：9242－9243 （in Chinese）.［邹小武，徐杜，蒋永平，等.Zigbee网络基础路由分析与改进 ［J］.电脑知识与技术，2009，5 （33）：9242－9243.］

［11］WANG Fang，CHAI Qiaolin，BAN Yanli.Improved routing algorithm for ZigBee mesh networks ［J］.Computer Applications，2008，28 （11）：112－113 （in Chinese）. ［王芳，柴乔林，班艳丽.一种改进的ZigBee mesh网络路由算法 ［J］.计算机应用，2008，28 （11）：2788－2789.］

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

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