舒红

(重庆邮电大学 重庆市移动通信重点实验室，重庆 400065)

ZigBee网络自剪裁路由算法

舒红

(重庆邮电大学 重庆市移动通信重点实验室，重庆 400065)

ZigBee网络中的AODVjr算法通过全网广播路由请求RREQ消息而获得分组发送的最短路径，但节点大量广播RREQ消息增加了网络控制开销，导致网络节点耗能剧增，同时网络堵塞的可能性也大大提升。针对AODVjr算法存在的网络节点耗能剧增问题，在AODVjr算法基础上，结合节点邻居表，提出筛选RREQ消息转发节点，从而限制RREQ消息转发次数的路由算法ZigBee树节点自剪裁转发算法(ZigBee On-tree Self-pruning Rebroadcast Algorithm，ZOSR)和ZigBee转发节点选择算法(ZigBee On-tree Forwarding Node Selection Algorithm，ZOFNS)。仿真结果表明，算法能有效降低网络节点的转发次数，从而降低网络整体功耗，延长网络工作时间。

ZigBee；自剪裁；AODVjr；RREQ；路由

0 引言

ZigBee网络是近几年出现的一种新兴网络技术，因其低功耗、低成本、低复杂度、短时延、大网络容量及高节点集成度等特点，被广泛应用于短距离低速率的数据传输场景中。然而由于ZigBee网络中节点的能量资源有限，故ZigBee网络路由算法必须以能量有效性为首要的设计要素。经典AODVjr算法通过全网广播RREQ消息而获得发送数据的最短路径，节点因大量广播RREQ消息，而耗能迅速，同时网络堵塞的可能性也大大增加［1］。

如何优化ZigBee路由算法、降低网络能量消耗一直是各国学者研究关注的热点［2－5］。文献［2］提出通过控制RREQ消息洪泛范围，以降低网络整体功耗。文献［3］提出利用分层拓扑信息来减少AODVjr算法中的路由开销，该算法为了平衡网络能耗，将节点剩余能量作为路由度量。文献［4］提出定向转发RREQ消息，该算法能有效减少冗余RREQ消息的转发，从而减少节点功耗。文献［5］提出Mesh拓扑混合路由优化算法，该算法在邻居表基础上，控制RREQ消息的转发范围和转发方向，并在选择路径时避开剩余能量较少的节点。上述算法在一定程度上限制RREQ消息的转发次数，降低了网络能量消耗，但都以节点已知其他节点位置信息为前提，而这在实际中很难实现。

针对ZigBee网络路由算法存在问题，在AODVjr算法基础上，结合节点邻居表，提出通过筛选RREQ消息的转发节点，能有效减少RREQ消息的转发次数，从而有效降低网络整体功耗的路由算法。

1 ZigBee网络

1.1 地址分配方式

ZigBee网络节点类型分为协调器节点(ZigBee Coordinator，ZC)、路由器节点(ZigBee Router，ZR)和终端节点(ZigBee End Device，ZED)3种。每一个无线个域网(WPAN)中仅仅包含一个ZC节点，它负责初始化网络和管理网络结构［6］。

ZigBee网络有2种地址分配方式，即分布式地址分配机制(Distributed Address Assignment Mechanism，DAAM)和随机地址分配机制(Stochastic Address Assignment Mechanism，SAAM)［7］。树型网络拓扑中节点默认采用DAAM获得唯一的16 bit网络地址。ZC节点首先进行参数设置:Cm是网络中任一父节点最大子节点数目;Lm是网络最大深度; Rm是网络中任一父节点最大路由子节点数目。则网络深度为d的父节点为其子节点分配网络地址时，通过式(1)计算地址偏移量Cskip(d)［8］。网络中，只有Cskip(d)＞0的节点才具有为其子节点分配网络地址，供其加入网络的能力。

ZigBee网络组网时，优先让ZR节点加入网络，这样能减少ZR节点向周围节点广播拓扑变化产生的广播开销。具体的地址分配机制［9］如下:

①ZC节点先将自身的网络地址和网络深度分别设置为0;

②对于网络深度为d，网络地址为A的父节点，其第n个ZC子节点对应的网络地址如式(2)所示;

③其第m个ZED子节点对应的网络地址如式(3)所示:

由上可知，ZigBee网络中任意节点可根据DAAM计算得到自身树邻居节点(即父节点和子节点)的地址。

1.2 AODVjr路由算法

ZigBee网络中基于路由请求的路由算法AODVjr是在AODV算法基础上做出的改进［10］。AODVjr算法中一旦节点有路由需求，节点则会以洪泛方式向邻居节点广播RREQ消息，中间节点会向邻居节点转发接收到的RREQ消息。目的节点一旦接收到RREQ消息，将沿RREQ消息的反向转发路径发送路由回复(Route Reply，RREP)消息，直到源节点接收到RREP消息后，路由建立完成。通过AODVjr算法可以得到源节点与目的节点之间的最短路径，但此算法在寻路过程中需转发大量RREQ消息，这就增加了全网的路由控制开销，导致网络节点因大量转发RREQ消息而能量消耗过快，造成网络分割。所以，如何降低AODVjr算法中RREQ消息的转发次数，从而降低网络控制开销和节点能量消耗一直是各国学者研究的重点。

2 自剪裁广播算法

2.1 假设与定义

为了更好地描述算法，在表1中给出如下定义，这里的A代表的是任意节点或节点集合。

表1 符号定义

由于ZigBee网络的资源限制，进行如下假设:

①任意节点之间的距离和具体位置不可知;

②任意节点的发送功率固定且相同;

③网络拓扑不一定是以ZC节点为圆心的圆，但节点间邻居关系是对称的:若节点i是节点j的邻居节点，则节点j也是节点i的邻居节点;

④使用分布式地址分配机制DAAM，任意节点在没有信息交换的的前提下，可获得父节点和子节点地址;

⑤任意节点维护一跳邻居表，任意邻居表记录由邻居网络地址和子节点数量组成。

2.2 ZigBee树节点自剪裁转发算法

通常Ad hoc网络的自剪裁广播算法中，节点v接收到RREQ消息后不会直接转发，而会先判断是否需要转发RREQ消息［12］。若节点v的所有邻居节点都已经接收到节点u转发的RREQ消息，即N(v)－N(u)=φ，那么节点v就没必要转发RREQ消息了。这就需要节点获悉两跳邻居表信息，而这对于能量和带宽有限的ZigBee网络来说是不可能实现的，所以，提出ZigBee树节点自剪裁算法ZOSR。ZOSR算法步骤如下:

①一旦有路由请求，源节点就会向邻居节点广播RREQ消息;

②若中间节点v首次接收到RREQ消息则将RREQ消息缓存，并启动定时器;

③节点v根据DAAM地址分配方式计算TN(v)，令TC(v)=TN(v);

④节点v接收到节点u发送的相同RREQ消息，则节点v根据DAAM地址分配方式计算TN(u)，并计算TC(v)=TC(v)－TN(u);

⑤若TC(v)=φ，节点v丢弃该RREQ消息，并停止计时器;

⑥重复步骤④和步骤⑤，直到定时器超时;

⑦若定时器超时，则转发缓存中的RREQ消息;

⑧RREQ消息到达目的节点之前，重复步骤②～⑦;

⑨目的节点接收到RREQ消息后，沿RREQ反向路径回复RREP消息;

⑩源节点接收到RREP消息后建立到目的节点之间的路由。

2.3 ZigBee转发节点选择算法

为了进一步减少RREQ消息的转发次数，在ZOSR算法基础上提出一种ZigBee转发节点选择算法ZOFNS，此算法根据一定准则，进一步地在未被覆盖的树邻居节点中挑选最优的转发节点进行RREQ消息的转发。ZOFNS算法具体步骤如下:

①一旦节点v有路由需求，则向邻居节点广播RREQ消息，并初始化转发节点集合，令F(v)=φ;

②利用式(4)分别计算节点v的备选转发节点集S(v)和覆盖节点集C(v);

③节点v若接收到节点u转发的RREQ消息，则根据式(5)更新节点v的备选转发节点集合覆盖节点集;

④根据N(v)中节点网络地址对节点进行排序;

⑤对于节点v的任意邻居节点w，若w∈S(v)，则令节点w的状态为“初始”状态，反之，则令w状态为“已转发”状态;

⑥初始化当前深度值，令CurrentLevel=Lm;

⑦对于处于当前深度，且为“初始状态”的任意节点x，若x没有子节点或所有子节点深度均为CurrentLevel+1，则将x的状态更新为“不转发”，反之将x的状态更新为“转发”;

⑧对于任意深度为CurrentLevel+1，状态不为“已转发”，且父节点x深度不为CurrentLevel的节点y，若节点y的状态为“不转发”且节点x的父节点深度为CurrentLevel－1，则将节点x的状态设置为“转发”。否则，将节点y的状态设置为“转发”;

⑨更新当前深度值，令CurrentLevel=CurrentLevel－1;

⑩重复步骤⑦～⑨，直到CurrentLevel=0;

⑪仅状态为“转发”的节点转发RREQ消息。

3 仿真分析

为了有效地评价ZOSR算法和ZOFNS算法的性能，采用MATLAB软件来进行仿真。将ZOSR算法和ZOFNS算法与ZigBee经典路由算法AODVjr分别在节点数目为20～100个的不同场景下进行了仿真比较:包括转发节点数目和网络转发次数等指标。

仿真时网络节点静止且随机分布，并假定仿真是在MAC层和物理层都不会有数据包丢失的理想状态下进行的，取5次仿真的平均值为最终结果，其他仿真参数如表2所示。

表2 仿真参数设置

当仿真节点数目为90时，AODVjr、ZOSR和ZOFNS 3种算法的转发节点分布图分别如图1(a)、(b)、(c)所示，图中实心节点为RREQ消息的转发节点，空心节点为无需转发RREQ消息的节点。

图1 ZOFNS算法转发节点分布图

由仿真结果可得出AODVjr、ZOSR和ZOFNS算法的转发节点数分别为100、26和20，且算法均能覆盖全部网络节点。这说明ZOSR、ZOFNS算法能有效减少网络中转发节点数目，这是因为ZOSR算法中节点接收到RREQ消息后不会直接转发，而是等待一段时间，根据所有树邻居节点是否已接收到RREQ消息来决定当前节点是否转发RREQ消息。而ZOFNS算法在ZOSR算法基础上，将一跳树邻居关系推广到两跳，即若当前节点的所有邻居节点的树邻居节点全部已经接收到RREQ消息，则当前节点无需转发RREQ消息。

3.1 转发节点数

随着节点数从20增加到90(间隔设置为10)，3种算法的转发节点数目都呈正比例增长，如图2所示。其中，AODVjr算法的转发节点数目与网络节点总数大致相等，因为AODVjr算法中一旦节点接收到RREQ消息，会向邻居节点广播RREQ消息，则网络中所有节点都会转发RREQ消息;而ZOSR算法和ZOFNS算法中，随着节点总数的增加，节点密度随之增加(因为仿真区域固定)，从而当前节点的邻居节点数目增加，能有效减少覆盖全网所需的转发节点数目。所以，随着节点数目增加，ZOSR和ZOFNS算法中转发节点数目涨幅远远小于AODVjr算法，且ZOFNS算法在一定程度上优于ZOFNS算法。

3.2 转发次数

随着网络节点总数的增加，3种算法中网络总转发次数增加，如图3所示。

图3 各算法转发次数比较

其中，AODVjr算法的任意节点一旦接收到RREQ消息后，会将RREQ消息直接转发，所以随着节点数量增加，网络总转发次数增长较快;然而，ZOSR算法中，虽然网络节点数量增加，但转发节点数目涨幅不大，所以网络总转发次数随着网络节点总数增加而缓慢增长;由于ZOFNS算法改进思想类似于ZOSR算法，且转发节点的数目更少，所以ZOFNS算法随节点总数增加，网络总转发次数增长趋势类似于ZOSR算法，但较ZOSR算法更优。

4 结束语

在经典ZigBee路由算法AODVjr基础上，提出了ZigBee树邻居节点自剪裁转发算法ZOSR、ZigBee转发节点选择算法ZOFNS。仿真结果显示，ZOSR和ZOFNS算法均能有效减少网络转发节点数目，从而减少网络中RREQ消息的总转发次数，最终减少网络路由开销，降低网络能量消耗。同时，由转发次数曲线可知，网络规模越大，ZOSR和ZOFNS算法较AODVjr算法优势越明显。然而，由于ZOSR和ZOFNS算法在选择转发节点时会等待随机时间，ZOSR和ZOFNS算法的全网覆盖时间必然会增加。所以，今后的工作将主要集中于优化ZOSR和ZOFNS算法网络覆盖时间问题上。

［1］周武斌．ZigBee无线组网技术的研究[D]．长沙:中南大学，2009:38－39．

［2］Lin Z，Meng M Q H，Liang H．ARoute Discovery Method Based on Limited Flooding in Zigbee Networks［C］∥Automation and Logistics，2008．ICAL 2008．IEEE International Conference on．IEEE，2008:3039－3044．

［3］Ren Z，Tian L，Cao J，et al．AnEfficient Hybrid Routing Algorithm for Zigbee Networks［C］∥Instrumentation＆Measurement，Sensor Network and Automation(IMSNA)，2012 International Symposium on．IEEE，2012，2:415－418．

［4］Mu J．ADirectional Broadcasting Algorithm for Routing Discovery in ZigBee Networks[J]．EURASIP Journal on Wireless Communications and Networking，2014，2014 (1):1－9．

［5］Shan C，Zhang W，Li X．Hybrid Routing Algorithm Optimization for ZigBee Mesh Network［C］∥Computer Applications and Communications(SCAC)，2014 IEEE Symposium on:142－146．

［6］穆嘉松，刘开华，史伟光．ZigBee网络中基于节点移动性的路由选择策略[J]．天津大学学报，2012，45(4): 301－308．

［7］杜娟，贾海瑞，李众立．基于逻辑区域的ZigBee网络地址分配算法[J]．传感器与微系统，2014，33(1): 126－129．

［8］钱志鸿，朱爽，王雪．基于分簇机制的ZigBee混合路由能量优化算法[J]．计算机学报，2013，36(3): 485－493．

［9］任智，李鹏翔，姚玉坤，等．基于分段的ZigBee网络按需可扩展地址分配算法[J]．通信学报，2012，33 (5):131－137．

［10］罗华．基于ZigBee的无线传感器网络路由算法研究[D]．长沙:中南大学，2010:42－46．

［11］谢川．基于ZigBee的AODVjr算法研究[J]．Computer Engineering，2011，37(10):87－89．

［12］Kim T，Kim S H，Yang J，et al．Neighbor Table Based Shortcut Tree Routing in ZigBee Wireless Networks[J]．IEEE Transactions on Parallel and Distributed Systems，2014:25(3):706－716．

Self-pruning Routing Algorithm in ZigBee Network

SHU Hong
(Chongqing Key Lab of Mobile Communications Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China)

Although the AODVjr algorithm can obtain the shortest path of packet through broadcasting route request RREQ message to the whole ZigBee network，a large amount of RREQ messages increase the network control overhead，the energy consumption of network nodes，and the possibility of network congestion．Considering the dramatic increase of network nodes'energy consumption in AODVjr algorithm，based on AODVjr and combined with nodes'neighbor table，two algorithms called ZigBee On-tree Self-pruning Rebroadcast Algorithm(ZOSR)and ZigBee On-tree Forwarding Node Selection Algorithm(ZOFNS)are proposed，which limit the number of RREQ messages by screening the forwarding nodes that broadcast RREQ messages．Simulation results show that the algorithms effectively reduce the forwarding number of network nodes，thereby reduce the whole network power consumption and expand the network lifetime．

ZigBee;self-pruning;AODVjr;RREQ;routing

TP393

A

1003－3114(2015)05－41－5

10.3969/j.issn.1003－3114.2015.05.11

舒红．ZigBee网络自剪裁路由算法［J］．无线电通信技术，2015，41(5):41－45．

2015－05－11

长江学者和创新团队发展计划(IRT1299);重庆市科委项目(CSTC2012jjA40044，cstc2013yykfA40010);重庆市科委重点实验室专项经费

舒红(1991—)，女，硕士研究生，主要研究方向:移动通信和无线传感网络。