基于定向的ZigBee网络节能路由算法

刘天琛 谭长庚

(中南大学软件学院 湖南 长沙 410075)

0 引 言

随着物联网技术的发展，ZigBee技术成为解决物联网中的最后100 m问题的关键技术之一。要将ZigBee技术应用到物联网中，使用ZigBee技术的节点能耗问题成为了业界重视的难点。如何降低整个ZigBee网络能耗，以及如何解决个别节点的耗能较快问题，一直是研究的热点[1]。

在如何降低网络能耗方面，有大量的专家致力于此。一个比较明确的研究方向是优化ZigBee网络协议中的路由算法，降低整个ZigBee网络中RREQ路由请求分组的数量。同时，ZigBee协议中的两大路由算法——AODVjr算法与Cluster-Tree算法具有各自的优缺点[2-3]。两种算法如何合理平衡地相互结合，也是研究的重要领域。

为解决以上提到的问题，文献[4]中提出了一种改进的Cluster-Tree算法，部分结合了AODVjr算法，通过计算邻居节点的父节点地址判断目的节点是否是其子孙节点，从而进行转发决策。该方法虽对请求分组数量进行了限制，但控制条件较简单，当节点数量较多时，结果基本与只使用Cluster-Tree算法相同，无法很好解决较低深度节点负担过大的问题。文献[5]中则提出了基于分簇的CLZBR算法，在簇内使用Cluster-Tree算法，簇间使用AODVjr算法，同时计算目的节点的父辈簇节点，在簇首节点进行路由时可直接转发该父辈簇首节点。该算法较好地减少了请求分组数，平衡了两种路由算法，但加重了簇首节点的负担。文献[6]提出DBDR算法，将网络分区域使用定向AODVjr算法，但并未考虑高深度节点使用AODVjr时请求分组数量增长较快的问题。

本文通过研究发现，虽然ZigBee网络层选取AODVjr[7]+Cluster-Tree的混合路由算法，路由过程中路由请求分组冗余问题以及网络整体能耗较高的问题没有得到较好的解决，因此本文将主要尝试解决这方面的问题。

1 ZigBee路由算法

1.1 分布式地址分配机制

在ZigBee网络中，整个网络中的节点都被分配了16位短地址，采用的是一种分布式的地址分配方式[8]。其中协调器节点的地址为0，其余的节点在加入网络时实行地址的分配。分配规则如下所述：

对请求加入ZigBee网络的节点进行地址分配时，首先要确定以下参数：父节点能够接受的最大子节点个数Cm、网络最大深度Lm、新节点加入网络后的父节点的网络深度d、一个非终端的路由节点允许链接其他路由子节点的最大值Rm。确定以上几个参数后，就可以为要加入网络的新节点分配地址。

首先计算新节点相对于父节点的地址偏移量Cskip(d)，具体计算如公式所示：

Cskip(d)=

(1)

偏移量计算完成后，加入网络设备地址的计算取决于该节点的类型。当节点类型为路由节点时，地址计算如公式所示：

Raddr(d)=Paddr+1+(x-1)×Cskip(d)

(2)

式中：Paddr表示父节点地址、x-1表示父节点已有的路由子节点个数。

节点类型为终端节点时，计算如公式所示：

Eaddr(d)=Paddr+Cskip(d)×Rm+n

(3)

式中：n表示当前节点是第几个终端节点。

1.2 路由算法

1.2.1 AODVjr路由算法

作为AODV算法的简化版[7]，AODVjr路由算法减少了路由发现过程中的部分的回复分组，基本过程为：当某个路由节点发起路由发现时，会向周围的邻居节点广播RREQ请求分组。当邻居节点接收到RREQ请求分组后，根据自身节点类型，进行下面的步骤：当节点为终端节点时，若自身为目标节点，则向发送该RREQ分组的上一节点发送RREP回复分组，否则丢弃分组。当节点为路由节点时，若本身是目标节点，则反向发送RREP回复分组，否则将该分组转发至所有邻居节点。网络中接受到RREQ的节点都会重复以上步骤。当中间节点接收到RREP分组后，会将该分组转发至上一个发送对应RREQ分组的节点，直到转发至源节点。通过这样不断地转发请求分组，找到最佳的路由路径，进行数据的传输。

AODVjr算法可以找到目标节点与源节点之间的最佳路径，但在路径发现期间需要大量转发RREQ分组。当网络中的节点较多时，极易形成分组风暴，造成网络拥塞，造成较大的数据传输延迟。同时不断地向邻居节点转发请求分组，会很快地消耗节点存储的电量。当节点的能量耗尽时，会造成部分甚至大面积的网络瘫痪。

1.2.2 Cluster-Tree路由算法

Cluster-Tree路由算法基于分布式地址分布机制，沿树状拓扑进行路由发现。首先根据式(1)计算Cskip(d-1)，然后根据式(4)判断目标节点是不是该节点的子孙节点。

A

(4)

式中：D表示目的节点地址，A表示当前节点地址。

当目的节点满足式(4)时，则当前节点首先根据式(1)计算Cskip(d)，然后根据式(5)计算下一跳节点地址，并将RREQ请求分组转发至该节点。

(5)

式中：NS表示下一跳地址，函数int返回任何数的整数部分，即向下取整。

当目标节点不满足式(4)时，当前节点将RREQ请求分组转发至父节点。父节点接收到RREQ分组后，若自身是目标节点，则向发送该RREQ分组的上一节点发送RREP回复分组，建立反向路由。否则选择下一跳节点。当请求分组被转发至协调器节点时，将直接根据式(5)计算下一跳地址[9]。终端节点则直接将分组转发至父节点。

Cluster-Tree路由算法基于已有的分布式地址分配机制，复杂度低、易于实现。但只依靠树状网络进行路由，会加大深度较小的、具有较多子树的路由节点的负担，一旦这些节点能量耗尽，极易引发网络瘫痪。

大部分ZigBee网络使用的路由算法都是上文提到的两种路由算法的结合[10]。一般根据某些指标进行条件设置，当节点能量等状态满足特定的条件时，灵活地选择路由算法，以此达到网络的最大利用。但是许多方法都无法很好地将两者的优缺点进行结合，使得二者达到一种平衡，同时也不能很好地解决整个ZigBee网络的能耗问题。

2 改进算法描述

本文为了解决上述问题，提出了一种新的路由算法——DZBR算法。该算法基于定向的策略，通过对路由发起过程中转发的RREQ分组进行定向转发，从而达到限制路由发现过程中请求分组数量的目的，以此降低网络能耗。

2.1 区域划分

区域划分工作在进行ZigBee组网时进行。协调器需要维护区域顺序表。区域顺序表是一张环形链表，主要保存各个区域的顺序，以及各个区域中的可分配地址区间。当有路由节点成为协调器节点的子节点时，协调器通过该路由节点与相邻节点的位置关系，计算出其成为新区域节点的位置，插入到区域顺序表中，并将更新后的区域顺序表向全网通报。如图1中区域划分所示。

图1中协调器具有五个子节点，在对其进行地址分配后，建立区域顺序表，顺序为I、II、III、IV、V，如图1中(a)图所示。当新节点要加入ZigBee网络，并确定成为协调器节点的子节点时，可以通过与除协调器节点外的邻居节点进行相关的位置计算，以此确定邻居区域为II、III。此时协调器节点将更新区域顺序表，此时的顺序为I、II、VI、III、IV、V，如图1中(b)图所示。更新后协调器节点向全网广播更新后的区域顺序表，为路由发现时的区域定向做准备工作。

图1 区域划分示意图

2.2 区域内分组转发

每一个具有路由功能的ZigBee节点，都会维护一张路由表与邻居表。当某一节点有路由请求时，首先会遍历路由表，寻找已经存在的路由项进行数据传输。当没有找到对应的路由项，或者已存在的路由项失效时，节点将遍历邻居表，寻找邻居节点中是否存在目的节点。如果邻居表中不存在目的节点，当前结点将发起路由发现。首先判断目标节点是否与源节点处于同一区域。因为在区域顺序表中已经记录了各个区间的可分配地址，所以只需要遍历区域顺序表即可。当目标节点与源节点处于同一区域时，进行区域内分组转发。具体步骤如下：

(1) 源节点深度可以从节点自身信息中获得，故只需要计算目标节点深度。当目标节点地址为0时，返回深度d=0。当目标节点地址不为0时，将初始深度记为d=0，根据式(5)计算下一跳节点的地址，并与目标节点地址比较，如果下一跳地址与目标节点地址相同，则返回d=d+1；否则d++，继续循环计算下一跳节点的下一跳地址。伪代码如算法1所示。

算法1计算节点深度伪代码

输入：节点地址D;

输出：节点深度

1 设置深度获取成功标识GetDeep = false;

2 设置当前深度deep = 0;

3 下一跳节点地址source = 0;

4 while(!GetDeep)

5 {

6 利用式(1)计算Cskip;

7 利用式(5)计算下一跳节点地址nextStep;

8 if(nextStep == D)

9 GetDeep = true;

10 else

11 {

12 source = nextStep;

13 deep ++;

14 }

15 }

16 返回当前深度deep++;

(2) 当获得源节点深度与目标节点深度后，将其与网络深度阈值dm进行比较，以决定采用的路由算法。为避免高深度节点群内路由发现时，采用AODVjr算法会出现需要跨过较多节点寻找目的节点的情况，本算法中建议在高深度不采用AODVjr算法。同时为避免低深度时，采用树状路由发现的路由路径并非最佳路径，并加重父节点或祖辈节点负担的情况，低深度不采用Cluster-Tree路由。为此设置深度阈值dm=xLm(0

(3) 当源节点深度与目的节点深度均小于dm时，则遍历邻居表，挑选节点进行AODVjr路由算法。此时设置新的路由深度阈值dn=yLm(x

(4) 当源节点的深度大于dm，而目标节点深度小于dm时，源节点遍历邻居表，挑选节点进行经过裁剪的AODVjr路由算法。遍历邻居表时，首先判断节点深度。当节点深度大于源节点深度时，忽略该节点，否则计算邻居表中该节点与目的节点的最小公共子树路径长度SND，并与源节点与目的节点的最小公共子树路径长度SSD进行比较。当SND≤SSD时将该邻居节点加入转发RREQ请求分组队列，否则忽略该节点。计算最小公共子树路径长度的伪代码如算法2所示。

算法2计算最小公共子树路径长度伪代码

输入：源节点地址Source，目的节点地址D，源节点深度sourceDeep，目的节点地址DDeep;

输出：最小公共子树路径长度

1 设置获取最小公共子树根节点标识GetCommonNode = false;

2 设置当前深度deep = 0;

3 协调器作为起始公共树节点CommonNode = 0;

4 while(!GetCommonNode)

5 {

6 利用式(1)计算Cskip;

7 利用式(5)计算源节点的下一跳节点sourceNextStep;

8 利用式(5)计算目的节点的下一跳节点DNextStep;

9 if (sourceNextStep != DNextStep)

10 GetCommonNode = true;

11 else

12 {

13 BeginNode = sourceNextStep;

14 deep++;

15 }

16 }

17 返回最小公共子树路径长度SSD= sourceDeep-(deep-1)+ DDeep-(deep-1);

(5) 当目的节点深度大于dm时，而源节点深度小于dm时，源节点遍历邻居表，筛选节点进行AODVjr路由算法。此时同样设置路由深度阈值dn=yLm(x

(6) 当源节点深度与目标节点深度均大于dm时，则采取Cluster-Tree路由算法，将RREQ请求分组转发至父节点。

(7) 中间节点收到RREQ请求分组后，重复以上(1)至(6)步，直到找到目标节点，建立反向路由。

区域内分组转发流程如图2所示。

图2 区域内分组转发流程图

2.3 区域间分组转发

当目标节点与源节点处于不同的区域时，进行跨区域间的分组转发。具体步骤为：

(1) 遍历区域顺序列表获得目的节点所在区域。同时可以获得正向的路由区域顺序列表。然后反向遍历区域顺序列表，获得反向的路由区域顺序列表，与正向路由区域顺序列表进行比较，保留最短路由区域顺序列表。

(2) 遍历邻居表节点，并结合最短路由区域顺序列表，判断邻居节点中是否存在不属于本区域的节点。

(3) 当发现不属于本区域的节点，判断其所属区域是否为下一跳区域，若是则将去加入转发RREQ请求分组队列，否则忽略。

(4) 对于与源节点属于同一区域的邻居节点。首先计算目的节点深度dD，与邻居节点深度di进行比较，当di>dD时忽略该节点。否则计算该邻居节点与目的节点的最小公共子树路径长度SND，然后将源节点与目的节点的最小公共子树路径长度SSD进行比较。当SND≤SSD时，将该邻居节点加入转发RREQ请求分组队列，否则忽略该节点。

(5) 当遍历邻居表发现存在下一跳区域节点时，将遍历转发分组队列中的下一跳区域节点，并转发请求分组。否则遍历整个转发分组队列并依次转发请求分组。

区域内分组转发流程如图3所示。

图3 区域间分组转发流程图

3 仿真分析

为了有效地评价本文提出的算法在降低整个ZigBee网络能耗方面的效果，本文采用了NS3，结合NS3中已实现的IEEE 802.15.4协议层，部分实现ZigBee的网络层，以进行网络层路由算法的仿真。进行仿真前，对一些重要的参数进行设定：父节点能够接受的最大子节点个数Cm= 5、网络最大深度Lm=5、非终端路由节点允许链接其他路由子节点的最大值Rm=3，路由深度阈值dm=1/2Lm、dn=2/3Lm。将本文所提出的算法与文献[5]中提出的CLZBR算法以及文献[6]提出的DBRD算法进行比较。分别在节点数为10～100个的不同场景下进行了仿真实验，仿真时随机分布节点，随机选取源节点与目标节点，记录路由发起过程中产生的数据包个数、成功送达目的节点的包的个数、以及从路由发起到结束网络剩余能量的变化。每个节点数的实验运行20次，对相关数据进行记录后取平均值。每个算法对以下指标进行计算：请求分组成功投递率，网络剩余能量，并进行比较。其他仿真参数如表1所示，其中为了使数据差异明显，将转发能耗进行了适当调高。

表1 部分仿真参数设置

3.1 请求分组成功投递率

请求分组成功投递率衡量的是路由发现过程中的路由开销。通过对进行路由发现时目的节点接收到的RREQ请求分组数与整个路由发起过程中转发的RREQ请求分组数进行比较，衡量算法在路由发现时的路由开销。当请求分组成功投递率越高时，说明了路由算法的可靠性越好，同时说明算法减少了网络中在进行路由发现时转发的RREQ请求分组，降低了分组冗余。具体计算如公式所示：

(6)

图4为三种算法的请求分组成功投递率的比较。当节点较少时，CLZBR算法基本等于树形路由，请求分组数量较少。节点数目增加，网络中请求分组数量也随之增加，请求分组成功投递率因此降低。而DBRD算法未限制高深度节点采用AODVjr算法时请求分组转发大量增加的问题，请求分组成功投递率一直处于偏低的状态。由于本文提出的算法通过定向策略以及不同深度采用不同算法的策略，减少了网内整体的进行路由发现的RREQ分组数量，所以性能相对好于另外两种算法。

图4 请求分组成功投递率

设置并发，使网络中同时存在有3个路由发现过程，运行实验，获得图5中的结果，从图中可以清楚地看出，随着网络负载的增加，请求分组成功投递率都出现了较大的降低，其中DBRD算法下降明显。而CLZBR算法前期较好，后期随着簇的增多，网络内分组显著增多，进行请求时节点能量降低较快，甚至出现能量耗尽，请求分组成功投递率出现明显增多。DZBR算法请求分组成功投递率也出现了下降，但相比另两种算法较优。

图5 提高负载后的请求分组成功投递率

改变网络的拓扑结构，使得网络拓扑中节点不均匀分布，而使某一区间中节点分布较为集中，取消并发，再次实验得到如图6的结果。此时，CLZBR算法在节点数较少的情况下表现较佳，但随着节点数增多，由于节点分布不均匀的问题，网络内频繁地使用AODVjr算法，请求分组数量大幅增加，请求分组成功投递率均下降明显。其中CLZBR算法中，簇与簇之间使用没有限制的AODVjr算法，加大了网络内的请求分组数量，请求分组成功投递率因此降低明显。而由于节点的分布不均，节点深度增加较大，区域数也变多，DBRD算法在多个区域间以及高深度下使用AODVjr算法，网络内的转发分组数量大幅增加，请求分组成功投递率一直较低。DZBR算法由于在深度上的限制，虽然请求分组成功投递率同样偏低，却优于其他两种路由算法。

图6 改变网络拓扑后的请求分组成功投递率

3.2 网络剩余能量百分比

剩余能量百分比能够真正体现算法对整个ZigBee网络能耗控制方面的有效性，剩余能量百分比越高，算法的能耗控制效果越好。剩余能量百分比指的是ZigBee网络中剩余的能量与网络初始能量的比值，具体计算如式(7)所示：

(7)

当仿真结束时，图7为第一次实验时三种算法对应的ZigBee网络剩余能量百分比的比较，可以看出，当节点较少时，CLZBR算法因为采用树形路由，能耗相对较少。随着节点数目增多，CLZBR算法中簇开始增多，采用AODVjr算法的路由簇节点也随之增加，不定向的AODVjr路由消耗了较多的能量，剩余能量百分比有所降低。DBRD算法则因为高深度节点间大量的请求分组转发导致剩余能耗百分比偏低。由于DZBR算法通过定向转发请求分组，减少了网络中的RREQ分组，同时对不同深度节点采用不同路由算法的策略，对能耗进行了平衡，故随着节点数的增多，DZBR算法在网络剩余能量方面表现更好。其他的两次实验结果与之类似，不再一一叙述。

图7 网络剩余能量百分比

4 结 语

本文通过对ZigBee网络层路由算法节能问题的研究，提出了一种新的路由算法，通过对节点进行区域划分，并确定路由过程中的最短区域顺序，以达到在路由过程中对RREQ请求分组进行定向的目的，减少网络中冗余的分组。同时结合节点的深度选择合适的路由算法，当路由节点深度较低时，选择使用AODVjr算法，当节点深度较高时，选择使用Cluster-Tree簇树路由算法，以此避免高深度时大规模转发RREQ请求分组的问题，从而在保证路由算法发现路径较佳的同时，降低整体网络的能耗。该算法平衡了AODVjr算法与Cluster-Tree算法的优缺点，较为有效地降低网络整体能耗，提高了ZigBee网络整体性能。

[1] 钱志鸿,王义君.面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1):215-227.

[2] 谢川.基于ZigBee的AODVjr算法研究[J].计算机工程,2011,37(10):87-89.

[3] 谢川.ZigBee中改进的Cluster-Tree路由算法[J].计算机工程,2011,37(7):115-117.

[4] 徐沛成,胡国荣.改进的ZigBee网络路由算法[J].计算机工程与设计,2013,34(9):3019-3023.

[5] 钱志鸿,朱爽,王雪.基于分簇机制的ZigBee混合路由能量优化算法[J].计算机学报,2013,36(3):485-493.

[6] Mu J.A directional broadcasting algorithm for routing discovery in ZigBee networks[J].EURASIP Journal on Wireless Communications and Networking,2014,2014(1):94.

[7] Chakeres I D,Klein-Berndt L.AODVjr,AODV simplified[J].Acm Sigmobile Mobile Computing & Communications Review,2002,6(3):100-101.

[8] Kim T,Kim S H,Yang J,et al.Neighbor Table Based Shortcut Tree Routing in ZigBee Wireless Networks[J].IEEE Transactions on Parallel & Distributed Systems,2014,25(3):706-716.

[9] 朱旭,牛存良,白晓丽.改进的ZigBee树路由算法[J].计算机工程与应用,2016,52(5):114-118.

[10] Xie H F,Zeng F,Zhang G Q,et al.Simulation Research on Routing Protocols in ZigBee Network[C]//Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation.Atlantis Press,2016.