改进的ZigBee网状网络路由算法研究

刘潇花，彭 勇

(江南大学物联网工程学院，江苏无锡 214122)

1 概述

ZigBee是一种低速率、低功耗、适应性强的短距离无线通信技术，在智能家居、家庭保健以及环境监测等无线通信场合得到了广泛应用［1-2］。ZigBee网络节点是依靠电池供电的，由于节点体积小，因此节点能量十分有限。当节点的能量消耗殆尽，容易导致网络分割，甚至会造成ZigBee网络瘫痪。所以，提高节点生存率、降低网络能耗是解决阻碍ZigBee网络应用发展前景的关键［3］。ZigBee主要支持3种网络拓扑，包括星型拓扑(star)、树形拓扑(tree)和网状拓扑(mesh)［4］。其中，网状网络是具有“自恢复”能力和高可靠性的网络，可以为节点提供多条数据传输路径。Mesh网络拓扑一般采用AODVjr路由算法，AODVjr路由算法是在AODV的基础上发展而来的，它支持端到端的传输［5］。AODVjr算法采用最短路径传输机制，目的节点回复最先达到的RREQ分组建立路由路径。正是由于这样的传输机制，AODVjr算法的一些节点易于因频繁参与数据转发而造成节点死亡。为解决AODVjr算法的这些问题，文献［6］基于节点角色差异性和节点能量状态提出一种改进的AODVjr路由算法，文献［7-8］提出基于能量均衡的改进ZigBee路由算法，文献［9］基于分层思想提出的网状网络路由算法，都在一定程度上降低了节点死亡率和网络能耗。

本文在深入分析ZigBee网络路由算法的基础上，针对现有AODVjr算法节点利用率低、网络能量消耗大的问题，提出一种改进的 F-AODVjr路由算法。

2 AODVjr路由算法

采用AODVjr路由算法的网状网络采用预先地址分配方式，网络中存在3类节点:中心协调器，路由器和终端节点。协调器和路由器存储容量大、计算能力强，是全功能设备(Full Function Device，FFD)，可以作为父节点为新加入的子节点分配网络地址，而终端节点为精简功能设备(Reduced Function Device，RFD)，只有数据收发功能，作为网络叶节点。

网络中，父节点能够接纳子节点的最大数量为Cm，其中，路由器数量最大为Rm，网络中的最大深度为Lm，可通过式(1)定义深度为d的父节点所拥有的地址空间Cskip(d)［10］:

入网子节点的类型不同，分配给子节点的地址的计算方法也不一样，如果子节点为第n个加入的路由器节点，父节点分配给子路由器的地址A由式(2)计算，父节点的地址为Ap。若子节点是第n个加入的终端节点，则使用式(3)为其分配网络地址:

AODVjr路由分为路由发现和路由维护2个过程。在发现路由环节中，存储路由信息必须通过路由表以及路由发现表来实现。其中，路由表的条目可以保存很长时间，是持续的，而路由发现表条目仅能持续一个路由发现操作的期限。

3 AODVjr路由算法存在的问题

ZigBee网络中每个节点都维护离自己一跳距离的邻居节点信息，每个具有路由功能的节点都维护一张路由表，记录本节点与其他节点已经存在的路径信息。AODVjr路由算法分组传输如图1所示。

当源节点C向目的节点L传输数据时，如果C中存在到L的路由表项，则根据该路由表项转发数据分组。如果不存在则开启路由发现，发送RREQ分组搜索目的节点。当开启路由发现时，C向周围节点广播RREQ分组，直到找到目的节点为止。目的节点收到RREQ分组后，选择最先达到的RREQ分组进行回复建立传输路径，如图1中的C－A－B－L路径。此时，算法存在以下问题:(1)在发起RREQ寻址之前，若能利用邻居表找到目的节点，则可避免开启路由发现过程，减少能量消耗，但AODVjr算法在寻址前没有使用邻居表;(2)AODVjr算法最短路径的寻址思想使得网络中的一些节点，如A，B由于频繁参与转发数据而使节点能量很快偏低，若继续使用这些能量偏低节点，容易造成其死亡进而引起网络能耗增大甚至网络瘫痪问题。本文为优化AODVjr算法，解决以上影响AODVjr算法性能的2个主要问题，提出改进的FAODVjr路由算法。

图1 AODVjr算法分组传输

4 改进的ZigBee网状网络路由算法设计

4.1 邻居表

由于邻居表是每个ZigBee节点自动维护的，不需要额外的能量消耗，因此在启动路由发现之前，如果能根据邻居表寻址到目的节点，将能降低网络能量消耗。网络初始化时每个节点都更新离自己一跳距离的邻居节点信息，邻居表存储内容如表1所示。

路由节点在启动路由发现过程前，执行下列伪代码，实现邻居表搜索目的节点功能。

4.2 路由发现

如果目的节点不在邻居表传输范围内，则开启路由发现，发送洪泛到目的节点的RREQ分组。RREQ分组只考虑路径跳数，虽然能找到最短路径，但会使某些节点过度使用成为死亡节点。在网络运行后期，死亡节点无法再转变为能量充足节点参与路由转发，其他节点传输数据时必须绕过死亡节点，能量消耗巨大。所以，为减少死亡节点数和降低网络能量消耗，在路由发现时，需解决以下问题:(1)尽量避免低能量节点的使用，降低死亡节点率;(2)改进原算法只将路径跳数作为路径代价进行路径选择的思想，结合剩余能量、链路质量综合考虑路由成本，达到降低网络开销的目的。路由成本最少的路径为最优路径，数据传输时路由代价较小。

4.2.1 节点死亡率

为降低节点死亡率，改进算法根据剩余能量和能量阈值划分节点等级，使网络在运行时能够判断哪些节点为能量不足节点，从而在路由时尽量避开这些节点，由能量充足节点充当主要路由角色，以此减少死亡节点数，降低节点死亡率。

改进算法设定一个动态更新的能量阈值Ex(n)，当剩余能量大于Ex(n)时为能量充足节点;当剩余能量小于Ex(n)时为能量偏低节点。能量充足节点可以用于数据传输，而能量偏低节点只转发目的节点在一跳范围内的数据分组或者接收目的节点为自身的数据分组，在路由过程中尽量避免使用低能量节点。Ex(n)可按式(4)计算:

其中，当n=1时，Ex(1)=ε，Ex(1)为网络设定的初始能量阈值，ε为特定系数，用来调整初始阈值的设定。Ex(n－1)表示更新之前的能量阈值，σ为一特定系数，作用在于控制能量阈值的减小速度。Ntotal指总节点个数，为常量，n为变量。为中心协调器设置2个内部计数器C1，C2。如果一个节点的剩余能量值低于当前Ex(n)值，则应向协调器发送本节点能量偏低消息，协调器使计数器C1的计数值加1。根据计数器C1的计数值，中心协调器可以算出能量偏低节点与网络总节点的个数比值q。设定一个阈值Etreshold(0＜Etreshold＜1)，当 q＞Etreshold时，协调器使C2计数值加1，n值即为C2的计数值。这样n值加1发生改变，使得 Ex(n)值完成一次更新。更新完Ex(n)值，C1置0，C2不变。由式(4)可得Ex(n)值为:

由Ex(n)计算方法可知，在网络运行初期，能量阈值Ex(n)递减缓慢，而当n增大，Ex(n)值的递减幅度越来越小。在网络运行后期，节点能量普遍不足，FAODVjr算法能量阈值递减幅度变慢可以使大部分节点都能作为能量充足节点参与路由转发，避免因参与路由节点过少而引发的网络拥塞现象，减少因网络拥塞造成能量的浪费。

4.2.2 路由成本

避开低能量节点使用后的AODVjr算法还需进一步优化。不同的RREQ分组达到目的节点后，使网络中存在多条可传输路径。本文从这些路径中，选择路由成本最低的路径为最优传输路径，路由成本越低，数据传输时路由代价越小。路由成本根据式(5)确定，式(5)综合考虑了跳数、剩余能量和链路质量对路由成本的影响。

F-AODVjr路由算法更全面地考虑了影响路由性能的因素。在网络运行初期，节点性能相同，FAODVjr路由算法优势不明显。网络运行一段时间后，节点剩余能量、链路质量发生变化，改进算法可以选择一条路由成本最低的路径，并使数据有更高的发送成功率，从而降低网络能量消耗。

4.3 算法流程

路由发现过程如图2所示。

图2 路由发现过程

算法流程具体如下:

(1)在网络初始化时，中心协调器为每个网络节点分配唯一的网络地址，每个节点初始化自己的邻居表，中心协调器广播Ex(1)值。中心协调器根据式(4)计算能量阈值，每当能量阈值发生变化，中心协调器便向各节点重新广播能量阈值。

(2)源节点查看邻居表(包括父节点和子节点)，若目的节点在邻居表中，则直接发送给目的节点;否则转步骤(3)。

(3)查看目的节点与源节点的邻居表(包括父节点与子节点)，若存在相同节点，则将数据分组转发给此相同节点，否则转步骤(4)。

(4)此时，目的节点必在离源节点两跳之外。由于RFD节点不具有路由功能，因此如果源节点为FFD节点则直接开启一个路由发现过程，若不是，则交由父节点开启路由发现过程，当一个RFD节点收到RREQ分组时就立即丢弃。如果目的节点为RFD节点，则由其父节点转交。路由发现过程按以下步骤执行:1)RREQ分组达到一个节点，该节点若不是FFD节点则丢弃RREQ分组，如果是FFD节点则转步骤2)。2)判断自己是否为目的节点或者为RFD节点的父节点，如果是则回复路由应答(Route Reply，RREP)分组建立路由路径，否则转步骤3)。3)查看自己的剩余能量，根据能量阈值判断是否是低能量节点，若是则丢弃RREQ分组，并向中心协调器发送能量偏低信息，使计数器C1加1，若不是低能量节点转步骤4)。4)查看自己是否已存在到源节点的路由表项，如果存在则转步骤5)，如果不存在则转步骤6)。5)比较路由表和RREQ分组中的路由成本TC。路由成本越小，表明传输数据付出的代价越小。如果RREQ分组中的路由成本高于路由表中的路由成本，则丢弃RREQ分组。否则根据式(5)计算并更新两者的路由成本，继续广播RREQ分组。6)建立到源节点的路由表项，并继续广播RREQ分组。

(5)中心协调器设置目的节点等待RREQ分组到达的时间常数T［12］，超过设置的时间则停止等待。目的节点收到RREQ分组后选择路由成本最低的路径建立路由路径，回复RREP。

5 算法分析与仿真实验

5.1 算法分析

改进算法针对节点的能量状况，根据式(4)不断动态更新能量阈值，使得不同状态节点对RREQ分组采取不同的处理方式，从而保护低能量节点。更重要的是，能量阈值的更新速度变慢，使得低能量节点在网络运行后期转为能量充足节点重新参与路由，防止了网络拥塞现象。在路由发现阶段，路由成本公式计算简单，由各节点独立计算完成。在搜索邻居表时，假设邻居节点个数为n，算法遍历每个邻居节点，此时，算法时间复杂度为O(n)，算法在多项式时间内完成。

5.2 仿真实验结果及分析

为评估改进算法的性能，在NS2仿真软件中对原AODVjr算法、改进的F-AODVjr算法和文献［6］中的改进的AODVjr算法进行仿真。通过网络的能量消耗、节点生存率和平均分组成功投递率进行对比分析。仿真实验的网络范围为300×300，通信半径为15 m，节点初始能量为10 J，数据流类型为CBR，数据流大小为80 Byte，仿真时间为80 s，数据分组的源节点和目标节点随机选择。

表2为3种算法的数据分组成功投递率仿真对比，数据分组成功投递率指的是目的节点正确接收到的数据分组个数与源节点发送的全部数据分组个数的比值。用Ps表示源节点发送的分组数目，Pr表示成功接收到的分组数目，数据分组成功投递率为:

由表2可知，当设置网络节点个数为50时，3种算法都具有较高的成功投递率，都在95%以上。随着节点个数增多，网络变得复杂，数据在传输时发生碰撞几率增大，所以，3种算法的数据分组成功投递率都有所下降。节点在传输数据时，如果目的节点死亡，数据分组将永远不可达，而中间节点的死亡，会导致网络拥塞，阻碍分组投递。F-AODVjr和改进的AODVjr算法尽量避开了能量不足节点的使用，所以，数据分组成功投递率大于AODVjr。在此基础上，F-AODVjr在数据分组传输时还考虑了节点的链路质量，使节点具有更高的成功投递率。

表2 数据分组成功投递率 %

3种算法的剩余能量百分比如图3所示。

图3 剩余能量百分比

在网络初始运行时，网络节点的剩余能量、链路质量相同，3个算法的剩余能量百分比相差不大。随着网络运行，开始出现能量偏低节点。AODVjr算法继续使用能量偏低节点造成其死亡，在网络运行后期，当大部分节点能量偏低时，低能量节点变为能量充足节点继续用以传输数据。而AODVjr算法由于死亡节点无法再变成充足节点继续使用，其他节点在传输数据时都要绕过这些死亡节点，大量消耗网络能量，其剩余能量百分比降低幅度增大，而改进的AODVjr算法与F-AODVjr算法却避免了这一现象的产生，递减幅度小于 AODVjr算法。虽然改进的AODVjr算法能量不足节点不再用于数据传输，但仍参与路由发现，所以，其能量消耗大于F-AODVjr算法。并且网络运行一段时间后，路径剩余能量、链路质量都发生变化，跳数最少的路径并不一定最优，FAODVjr算法能找到一条路由成本最低的路径，所以，F-AODVjr算法的剩余能量百分比始终高于AODVjr算法和改进的AODVjr算法。

3种算法的节点生存率如图4所示。

图4 节点生存率

节点生存率为网络可用节点率。如果一个节点的剩余能量低于初始能量的3%，则被看作是死亡节点。网络运行结束后，计算生存节点个数。节点生存率计算公式为:

其中，Nable是网络运行结束后生存节点个数;Ntotal是网络总节点个数。在网络运行初期，节点能量充足，节点生存率降低幅度不大。由于F-AODVjr算法尽量避免使用低能量节点参与路由，因此节点死亡数较少，节点生存率始终高于AODVjr算法和改进的AODVjr算法。在网络运行后期，虽然三者的节点生存率下降幅度都有所增大，但F-AODVjr算法和改进的AODVjr算法的网络拓扑分割现象不严重，所以，节点生存率下降幅度都小于AODVjr算法。

6 结束语

本文针对AODVjr算法存在的问题提出了一种改进的F-AODVjr算法。改进算法在进行发现路由过程前，使用ZigBee节点自身维护的邻居表寻找目的节点，如果能通过邻居表找到目的节点，将大大降低网络能量消耗。如果目的节点不在邻居表传输范围内，则进行路由发现。在路由发现过程中，改进算法能提高节点生存率、降低网络能量消耗和增大数据分组成功投递率。但改进算法的不足之处是没有考虑网络节点的移动情况，在路由过程中会因产生对寻址无效的RREQ分组而浪费能量。所以，今后将进一步探讨如何减少路由过程中RREQ分组的洪泛并将其投入到实际应用中。

［1］李文仲，段朝玉.ZigBee2006无线网络与无线定位实战［M］.北京:北京航空航天大学出版社，2008.

［2］Baronti P，Pillai P，Chook V W C，et al.Wireless Sensor Networks:A Survey on the State of the Art and the 802.15.4 and Zigbee Standards［J］.Computer Communications，2007，30(7):1655-1695.

［3］蒋 挺，赵成林.ZigBee技术及其应用［M］.北京:北京邮电大学出版社，2006.

［4］陈 波.Zigbee路由算法分析及改进［D］.天津:南开大学，2009.

［5］Chakeres I D，Berndt K.AODVjr，AODV Simplified［J］.Mobile Computing and Communication Review，2002，6(3):100-101.

［6］王 芳，柴乔林，班艳丽.一种改进的ZigBee Mesh网络路由算法［J］.计算机应用，2008，28(11):2788-2794.

［7］李予东，黄宏光，向西西.基于能量均衡的Zigbee路由算法优化［J］.计算机工程与设计，2011，32(2):397-400.

［8］Ran P，Sun M H，Zou Y M.ZigBee Routing Selection Strategy Based on Date Services and Energy Balanced Zigbee Routing［C］//Proceedings of 2006 IEEE Asia Pacific Conference on Services Computing.Washington D.C.，USA:IEEE Computer Society，2006:400-404.

［9］Ha J Y，Park H S，Choi S，et al.Enhanced Hierarchical Routing Protocol for ZigBee Mesh Networks［J］.IEEE Communications Letters，2007，11(12):1028-1030.

［10］张 擎，刘淑美，柴乔林.能量高效的Zigbee网络改进路由策略［J］.计算机工程，2010，36(7):108-111.

［11］Ashraf U，Abdellatif S，Juanole G.An Interference and Link-quality Aware Routing Metric for Wireless Mesh Network［C］//Proceedings of the 68th Vehicular Technology Conference.［S.l.］:IEEE Press，2008:1-5.

［12］谢 川.Zigbee中改进的Cluster-Tree路由算法［J］.计算机工程，2011，37(7):115-117.