降低路由开销的ZigBee路由算法研究

摘要：ZigBee技术是为无线传感器网络技术设计的一项新兴的低成本、低功耗的短距离无线通信技术。在分析ZigBee路由机制的基础上，针对控制分组的传输范围和转发方向提出降低路由开销的改进方案，并与原算法进行仿真分析。

关键词：ZigBee；路由算法；路由开销

中图分类号：TP393文献标识码：A 文章编号：1009-3044(2008)06-10000-00

Research on ZigBee Routing Algorithm with Reduced Routing Overhead

GUO Zhuang－hui, HU Ke, WANG Lei

(Institute of Electronic & Communication Engineering, Tongji University, Shanghai 200092，China)

Abstract: ZigBee technology is a low-cost, low power consumption, short-distance wireless communication technology, which is newly designed for wireless sensor networks. Based on the analysis of routing process, the author proposes improved routing strategies focus on restricting the transmission range and direction of control packets to reduce the routing overhead, and make simulation and analysis with original routing algorithm.

Key words: ZigBee; routing algorithm; routing overhead

1 引言

ZigBee技术是一种新兴的针对于无线传感器网络的短距离无线通信技术。它依据IEEE802.15.4标准，在数千个微小的传感器之间相互协调，以接力的方式通过无线电波将数据从一个传感器传到另一个传感器，由于这些传感器只需要很少的能量，所以具有非常高的通信效率。与蓝牙和Wi-Fi相比，ZigBee具有数据传输速率低、功耗低、成本低，复杂度低、时延短、网络容量大、工作频段灵活等特点，其技术特性决定它将是无线传感器网络最具潜力的选择，具有广阔的应用前景[1]。

为了达到低成本、低功耗、可靠性高等设计目标，ZigBee网络中采用了Cluster-Tree + AODVjr路由算法，结合了Cluster-Tree算法和AODVjr算法各自的优点。Cluster-Tree（簇-树）是一种由协调器展开生成的树型网络拓扑结构，适合于节点静止或者移动较少的场合，属于静态路由，不需要存储路由表。AODVjr (AODV Junior)[2]是对按需距离矢量路由(Ad-hoc On-Demand Distance Vector Routing, AODV)[3,4]算法的改进，充分考虑了降低成本、节能、使用的方便性等因素，简化了AODV的一些特点，但是仍然保持AODV的原始功能。

路由开销是衡量路由算法性能的一个非常重要的指标，它是传递数据分组时使用的控制分组总和，较大的路由开销将会给网络的运行带来负面影响。由于控制分组相对于数据分组是一种资源的浪费，因此在保证网络的分组递交率和平均时延性能不受影响的前提下，尽量减少无用的控制分组，降低路由算法的路由开销，对于网络的优化和减负具有重要的意义。

2 ZigBee路由算法分析

在ZigBee网络中，节点使用Cluster-Tree算法按照父子关系选择路径，即当一个节点接收到数据分组后如果发现该数据分组不是给自己的，则只能转发给它的父节点或者子节点，不存在路由发现过程，然而由Cluster-Tree建立的路由不一定是最优的路径，会造成分组传输时延增加，而且容易造成网络中通信流量分配不均衡。为了提高路由效率，ZigBee中允许具有路由功能的节点使用AODVjr算法去发现路由，即具有路由功能的节点可以不按照父子关系而直接发送信息到其通信范围内的其它具有路由功能的节点，寻找通往目的节点的最优路径；而不具有路由功能的节点仍然使用Cluster-Tree路由发送数据分组和控制分组。由于AODVjr的使用，降低了分组传输时延，提高了分组递交率。

2.1 网络地址的分配机制[5]

假定每个父节点最多可以连接Cm个子节点，这些子节点中最多可以有Rm个路由节点，网络的最大深度为Lm，用Cskip(d)表示网络深度为d的父节点为其子节点分配的地址间的偏移量，它的值可按如下公式计算：

对于地址为A深度为d的ZigBee路由器，如果地址为D的目的节点满足下面的不等式，那么D是它的一个子节点：

若目的节点 是当前节点 的后代，那么从 到 的下一跳节点地址 可以表示为：

2.2 路由建立过程

路由的建立过程分为以下两大步骤：

第一步，广播RREQ分组，建立反向路由：

节点创建并向周围节点广播一个RREQ分组，如果收到RREQ的节点是一个RN-节点，它就按照Cluster-Tree路由转发此分组；如果收到RREQ的节点是一个RN+节点，则在路由表中建立一个指向RREQ源节点的反向路由，并继续广播此RREQ分组。

第二步，回复RREP分组，建立正向路由：

经过一系列广播后，一旦RREQ到达目的节点（RN+）或者目的节点（RN-和RFD）的父节点，此节点就向RREQ的源节点回复一个RREP分组，RREP将沿着已建立的反向路由向源节点传输，每个收到RREP的节点建立到目的节点的正向路由并更新相应的路由信息。

图1给出了一个路由建立的例子。

3 降低路由开销的改进算法研究

由于Cluster-Tree算法的使用，ZigBee路由相比AODVjr具有较少的路由开销，但是我们分析ZigBee的路由机制，发现在寻找路径的过程中仍然会产生很多多余的控制分组，这些控制分组虽然也参与路由发现，但对于最终找到一条最优路径并没有什么帮助。如果我们能够在路由发现过程中适当地限制这些控制分组的产生或转发，将能够显著地降低网络的路由开销。能否准确地找到这部分控制分组是非常关键的，因为如果抑制了一些可能找到最优路径的控制分组的产生或转发，将会降低路由协议的性能（如分组递交率、平均端到端时延等）。

针对第3节对ZigBee路由算法的分析，我们从两个角度分析降低路由开销的策略：

（1）限制RREQ分组的传输范围

ZigBee路由中，RN+节点在选择路径时会向周围节点广播路由请求分组RREQ，网络中的其它节点帮助转发RREQ以便找到一条通往目的节点的最优路径。这样随着网络业务量的增加，节点需要处理的控制分组也会大量增加。路径的长度直接影响着网络的各项性能，ZigBee在Cluster-Tree算法中加人AODVjr的一个主要原因就是为了寻找相比Cluster-Tree更优的路径，如果找到的路径比按照Cluster-Tree算法选择的路径长，便没有了实际的意义，而且较长的路径往往会对网络的平均端到端时延和寿命等产生负面影响。因此，如果我们能够事先确定RREQ分组的传输范围，使之不超过节点按照Cluster-Tree算法找到的路径长度，那么就能够丢弃一些超出传输范围的控制分组，达到降低路由开销的目的。

（2）限制RREQ分组的转发方向

由第3节路由建立过程中RREQ分组的广播机制可知，RN+节点收到RREQ分组后如果发现自己不是路由的目的节点，便向周围所有的邻节点转发此RREQ，事实上这样做存在着很大一部分浪费，而且随着转发跳数的增加，此种无益的开销增加得更大。究其原因主要有两点：其一，并不是所有的邻节点都有可能帮助其找到到达目的节点的最优路径，有些邻节点几乎不可能找到通往目的节点的路径，而有些邻节点只会使路由选择走很大弯路；其二，在大多数路由算法的路由发现过程中，数据可以传输的范围通常限制在网络直径的范围之内，超过传输范围的RREQ会被节点丢弃，因此存在一些邻节点由于距离目的节点太远而不可能将RREQ分组转发过去。从上述分析可知，如果我们在每个节点转发RREQ分组前，加入一个路由方向判断机制，如果此节点是对路由发现无益的节点，令它丢弃分组不再转发，那么可以节省很大一部分路由开销。随着网络深度的增加，这种节省会更加明显。

4 改进算法的实施方案

4.1 限制RREQ分组的传输范围

根据上一节的分析，我们可以在源节点广播RREQ分组前根据目的节点的地址来设置分组传输的最大范围，当传输的路径超过此范围时，节点自动丢弃收到的这个分组。

从树型结构可以很容易地看出，如果仅使用Cluster-Tree算法选择路由，可能存在的最长路径应是网络最大深度的2倍，即2Lm，可以规定RREQ的最大传输范围为2Lm，这样当RREQ的传输范围到达2Lm时，节点便自动丢弃收到的RREQ。

为了进一步合理地缩小传输范围，尽量降低路由开销，我们利用ZigBee网络的Cluster-Tree参数Cm、Rm、Lm和目的节点的网络地址D0来确定RREQ的最大传输范围l。发起RREQ的源节点地址为 深度为d，均为已知量，目的节点的深度为d0，为未知量。下面详细阐述求解 的过程。

首先判断目的节点与源节点的位置关系。如果目的节点是源节点的后代或源节点是目的节点的后代，那么RREQ到达目的节点后所发现的路径长度应不大于目的节点与源节点的深度之差，即l=│d0-d│；如果目的节点和源节点均不是对方的后代，那么所发现的路径长度应不大于目的节点与源节点相对于最高深度公共父节点的深度之和，设最高深度公共父节点的深度为dc，则l=d+d0-2dc。作为特例，当它们的公共父节点只有协调器节点时，dc=0，此时l=d+d0。

事实上，目的节点是源节点的后代或者源节点是目的节点的后代也是一种特殊情况，此时dc=d或dc=d0，我们可以统一用=d+d0-2dc来求。然而由于源节点发送分组时只知道目的节点的地址D0不知道其深度d0，也不知道它与目的节点的最大深度父节点的深度dc，我们无法直接得到l。

易知0≤dc≤d，我们可以沿树型结构从协调器节点向地址为 的源节点发送分组，循环利用本文2.1节式3求出下一跳地址N，此时dc将从0开始依次增加至d-1，在每一个中间节点处利用式2判断目的节点是否是当前节点的后代：当它是深度为dc的节点的后代而不是深度为dc+1的节点的后代时，则dc即为源节点和目的节点的最大深度父节点的深度。

求dc的算法流程如图2。

在求得dc之后，我们从协调器节点开始沿着树型结构，利用循环过程直至求得的下一跳地址 等于目的节点地址D0，统计出的循环次数便是从协调器节点到目的节点的跳数，即深度d0,进而求得RREQ的最大传输范围l=d+d0-2dc。其计算流程如下图3。

计算出l后，源节点在广播RREQ分组前可以将RREQ的传输范围设为l，当传输路径到达l时自动丢弃RREQ，这样就进一步缩小了RREQ的传输范围，减少了不必要控制分组的转发，达到降低路由开销的效果。

4.2 限制RREQ分组的转发方向

从前面的介绍可以得知，ZigBee网络中所有节点在收到分组后都可以利用本文2.1中的式2判断分组想要到达的目的节点是否是自己的一个后代。如果节点确定了RREQ分组的目的节点是自己的一个后代，那么此时如果仍然让其父节点为其转发RREQ，此RREQ找到通往目的节点的最优路径的可能性是非常小的，甚至有可能无法到达目的节点；反之，如果节点确定了RREQ分组的目的节点不是自己的一个后代，却仍然将RREQ发送给它所有的子节点，这些子节点再转发RREQ已没有太大的意义。我们可以使用式2判断RREQ目的节点的大致方向，从而限制其向与目的节点相反的方向传输，达到节省路由开销的目的。

具体做法如下：

在路由请求分组RREQ中增加一个标志位flag，用来记录RREQ的目的节点与本节点的关系：flag=1，目的节点是本节点的后代；flag=0，目的节点不是本节点的后代。设目的节点为D，在路由发现过程中存在两个中间节点A和B，A向B转发分组。我们的算法是：

（1）A在转发RREQ分组前，执行下列伪码：

if (D是A的一个后代)

flag = 1;

else

flag = 0;

（2）B收到A转发的RREQ分组后，执行下列伪码：

if (flag = = 1)

{

if (B是A的父节点)

丢弃RREQ；

else

处理RREQ；

}

else

{

if(B是A的一个子节点)

丢弃RREQ；

else

处理RREQ；

}

综合上述两种改进策略，我们将其应用在ZigBee原始路由算法中，基于降低路由开销的改进算法流程如下图4所示：

5 仿真结果及性能分析

本文采用NS2软件对改进算法和原算法的性能进行仿真，仿真采用下图5所示的网络拓扑。

仿真参数见表1。

表1 降低路由开销改进算法的仿真参数

从仿真结果可以看出，ZBR改进算法的路由开销始终远远小于原始ZBR算法的路由开销。这是因为：一，ZBR改进算法在源节点广播RREQ分组前利用树型结构和Cluster-Tree算法限制了RREQ的最大传输范围，丢弃了一部分超出范围的不必要的控制分组；二，在每个中间节点转发之前，都进行当前节点与目的节点关系的判断，以便指示下一跳节点该如何处理。路由开销得到了很好的改善，那么改进后网络的分组递交率、平均跳数和平均端到端时延性能会不会由于改进算法的引用导致明显的下降呢？图7分别给出了仿真的结果。

从图7(a)中可以看出，随着CBR数据流个数的增加，ZBR改进算法与ZBR算法的分组递交率相差不大，仍然维持在99.6%左右，说明改进方案并没有影响数据包的发送效率。从图7(b)(c)可以看出，随着CBR数据流个数的增加，ZBR改进算法的平均跳数、平均端到端时延始终与原始ZBR算法保持一致，ZBR改进算法的平均跳数和平均端到端时延并没有明显高于ZBR，这说明改进算法对RREQ分组范围和方向的限制策略是合理的，丢弃的分组基本为没有意义的冗余分组，改进算法的使用并没有使节点选择更长的路径，没有增加发送分组的时延。

综合以上分析可以得出下述结论：

降低路由开销的ZigBee路由改进算法通过限定RREQ分组的最大传输范围和约束RREQ分组在每个中间节点的转发方向，使节点在路由发现时丢弃了一部分无益的控制分组，从而在保证网络分组递交率、平均跳数和平均端到端时延性能的同时，达到了降低路由开销的目的。

6 结语

本文在分析ZigBee路由算法和路由机制的基础上，针对降低网络的路由开销这一目标探讨了改进方案，并在NS-2仿真平台中进行了验证和对比分析。

改进方案从两个角度考虑：通过设置路由请求分组RREQ的最大传输范围，丢弃超出此范围的无益控制分组，通过限定每一个中间节点转发分组的方向，丢弃对路由发现无益的反方向控制分组。经过上述方案对算法的改进，明显减少了路由开销，同时从仿真结果可以看出，分组递交率、平均跳数、平均端到端时延等性能没有受到较大影响。这是由于本方案丢弃的分组均为对节点发现最优路径无关紧要的节点，准确地找出这些节点是方案可靠性的

关键。

7 致谢

本文研究得到了国家自然科学基金重点项目（70531020）资助，在此谨表谢意。

参考文献：

[1]郦亮. IEEE802.15.4 标准及其应用.电子设计应用，2003.

[2]Ian D.Chakeres, Luke Klein-Berndt. AODVjr, AODV simplified. Mobile Computing and Communications Review, 2002, 6(3):100-101

[3]Charles E. Perkins, Ad hoc On Demand Distance Vector Routing，Mobile Computing Systems and Applications, 1999.

[4]Masayuki Tauchi, Ad-Hoc Routing Protocol Avoiding Route Breaks Based on AODV， System Sciences, 2005.

[5]蒋挺，赵成林.紫蜂技术及其应用.北京：北京邮电大学出版社，2006.

收稿日期：2008-01-12

基金项目：国家自然科学基金重点项目（70531020）

作者简介：郭壮辉，同济大学电子与信息工程学院硕士研究生，研究方向为智能自动化；胡柯，同济大学电子与信息工程学院硕士研究生，研究方向为智能自动化；汪镭，江苏无锡人，同济大学控制科学与工程系教授，博士生导师，从事智能自动化系统研究。

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”