ZigBee网络路由算法研究与优化①

黄 静,陈 兰

(浙江理工大学 信息学院,杭州 310018)

近些年来,物联网行业发展越来越迅速,人们越来越离不开物联网.ZigBee技术是物联网的核心技术之一[1],它具有能耗小、成本小、复杂度低等优点,对于资源匮乏、注重绿色发展的当今社会来说,它的研究价值非常高.虽然ZigBee网络已经有低功耗低成本的优点了,但是研究发现,ZigBee网络在能耗方面的减少还具有很大空间,为了减少ZigBee网络的能耗,大量的专家学者进行了研究.Ha和Pack等人[2]提出网络路由分层协议,利用分层策略找到最短路径,降低能耗.李志明[3]等人则引入了差分算法对最小生命周期求解,使路由节点选择生命周期最长的簇进行通信.王飞[4]则通过 GA-PSO 算法通过对簇类节点优化而找到最优路径.Li和Meng[5]等人提出对RREQ分组的泛洪进行控制,从而降低能耗.高霞、徐海峰[6,7]等则提出将没有工作的节点进行休眠来减少网络的能耗.通过以上的这些研究,给本文研究提供了理论基础.而本文则结合传统ZBR路由算法进行改进,并对改进的ZBR算法进行验证,旨在为当前的无线网路由优化提供另外的一种借鉴.

1 ZigBee路由机制

当前ZigBee协议采用的是按需距离矢量路由(AODVjr)和树形网络结构路由(Cluster-tree)混合作为自身的路由算法,其主要作用是发现和维护路由.ZigBee网络中的节点既可以当作中继节点,也可以直接通过所连接的传感器采来监控和采集数据.

1.1 ZigBee地址分配

ZigBee网络中的节点都拥有两个地址,一个是64位的MAC地址,它是节点唯一的标识,由制造商或者被安装的时候设置,另一个是16位的,类似于IP地址,是节点加入网络的时候,由路由器分配的.仅在网络内部使用,只负责数据间的传输[8].网络地址分配时会涉及3个参数,这3个参数由协调器决定.

为了便于理解,图1为ZigBee网络树状结构图.

图1 ZigBee网络树状结构图

由图中参数可知节点可连接的终端节点最大数量为Cm−Rm.其中,网络深度是指该节点到协调器的最短跳数;终端节点是指没有路由功能的节点.若父节点网络深度为d,那么该节点为子节点分配地址的偏移量为Cskip(d).

只有当Cskip(d)＞0时才允许子节点接入网络[9].首先预设协调器的深度为0,假定父节点地址为Ap,加入此节点第一个拥有路由能力的子节点地址为Ap+1,协调器为第i个有路由能力子节点分配的地址如式(2)所示;为第k个终端节点分配的地址如式(3)所示.

根据节点分配的方式,我们可以通过式(4)来判断目的节点是否为当前节点的后代节点[9].

假定当前节点的地址是A,深度是d,若地址为D的目的节点地址满足式(4),则目的节点是当前节点的后代节点,那么当前节点的下一跳地址D根据式(5)确定.

若目的节点地址D不满足于式(4),则当前节点会讲数据传给自己的父节点,即下一跳为当前节点父节点.

1.2 ZigBee路由算法

目前ZigBee支持3种算法,分别是cluster-tree、AODVjr和ZBR.在cluster-tree算法中,当地址为A,深度为d的节点收到数据后会根据式(4)判断下一跳,若满足,则下一跳的地址可以经过式(5)得到;若不满足,下一跳为其父节点.Cluster-tree 算法的优点是可以一定程度上减少缩短端到端的延迟,但是由于他的非自适应算法的特点,使得它无法动态进行路由的选择,使该算法在网络时延的最大化方面还有所不足.AODVjr算法的一次路由建立过程分成3步:路由发现、反向路由建立和正向路由建立.该算法的优点是,相对于有线网络的路由协议而言,它不需要周期性的路由信息广播,节省了一定的网络资源.缺陷在于它的路由发现过程只有在有需求的时候才会进行,那样就会增加数据传输到目的地址的时间,并且在路由发现的过程中也容易引起RREQ风暴.

目前常用的ZBR算法是由cluster-tree和AODVjr两种算法结合产生的,图2为ZBR算法处理流程图.

首先利用cluster-tree路由算法将ZigBee网络构建好,有助于分组信息有方向的传输,然后通过AODVjr路由算法来寻找最佳路径,以减少时间延迟和能量消耗,结合了两种算法的优点,但依旧没有很好地解决路由发现时的问题,当AODVjr路由算法在进行路由发现这个过程时,所有节点都会参加RREQ分组转发,大量无用的RREQ分组容易造成RREQ泛洪,并且距离协调器愈近的点,转发分组次数就会愈多,能量的耗费也就愈快,以致节点失效,造成传感器网络瘫痪.

图2 ZBR算法处理流程图

2 改进的ZigBee路由算法

2.1 改进路由算法的解决方案

光具有波粒二象性,也就是具有波动性和粒子性,研究通过计算机数字图像处理手段,把一些光学现象清晰地展示出来,便于观察和研究,在实验结果中显示的光流扰动现象恰好像一些颗粒状的东西在做漂流运动,与光的粒子性和波动性是吻合的.为了改善ZBR算法在路由发起过程中的缺点,本文提出了一种分层能量的控制方法,从限制RREQ控制分组的范围着手,并考虑能量的消耗,对混合路由算法进行改进,主要从以下几个方面来解决问题.

(1)将ZigBee网络分成若干个簇

通常一个簇拥有多个节点,依据功能分为网关节点、簇头、簇成员和备用节点4种类型.由于在ZigBee网络中节点地址分配严格按照分布式地址分配机制进行,因此我们引入路由深度作为划分簇和选择簇头节点的标准,当ZigBee网络由协调器建立起来后,其自身首先成为第一个簇的簇头,第一个簇建立完毕后,然后计算路由器的深度,第一个簇的网关节点会将深度为偶且连接的子节点最多的的节点选为下一个簇的簇头,最后将深度为奇的节点和终端节点均划分到其父节点所在的簇中,以此类推,直到所有的节点都划分完毕.

(2)定义能量阈值

簇划分完毕后,将每一个处在该ZigBee网络中的节点都添加一个能量阈值,剩余能量低于该值的节点将会休眠,若该节点为簇头节点,那么网络则会启用备用节点,各逻辑簇仅有一个簇头,若簇头未失效,则备用节点与簇成员相同;若簇首能耗过大而超过预设阈值,则由备用节点替代簇首[9].在定义节点阈值的同时,我们距离主协调器或者簇头越近的节点,转发分组包数量越庞大,能量消耗的越快,因此我们需要对协调器附近的节点进行一些保护,即负载均衡策略,距离协调器越近深度越小的节点,阈值越高;距离协调器越远深度越大的的点,阈值越低.从而使ZigBee网络的使用寿命增长.在实际应用中,随时间长度的增加,节点的能耗必然也会增加,考虑到这一特性,那么随时间长度增加,能量阈值降低.根据以上参数的相关性,定义能量阈值的公式如下:

其中,节点的初始能量设为P;节点i的深度设为di;节点的阈值设为Ei;t为运行的时间;α为权因子,用来调节阈值的实际大小;(di+1)是为了避免分母为0的情况的出现.由(6)式可知,当t→无穷大时,Ei→0;随着时间t的增大,一些休眠的节点会被唤醒;在网络启动工作后,网络中节点的能量普遍很低.当有路由请求时,若节点的能量power＜E时,就会产生中断,并发送报警信息给源节点,并将该报警信息扩散至其临近的节点,使它们的路由表中这一项失效,然后这些节点再依次广播下去[10].

(3)传播范围计算

对RREQ传播的范围进行限制,使超过范围的节点丢弃不必要的RREQ分组,从而节约在路由发现过程中节点的能耗.假设源节点地址为S,深度为ds[10],目的节点地址为D,深度为dD,RREQ请求包最大传输范围为Lm,其中dD和Lm未知,其他已知.在路由请求发送过程中,首先判断源节点和目的节点的关系,若为父子节点,则请求的最大传播范围等于两节点深度之差的绝对值,即Lm=|ds−dD|;若不存在父子关系,则分组包的最大传播范围等于它们分别与该父节点进行深度差计算并叠加后的值:

其中,dF共同的父节点网络深度,其定义为当源节点是父辈节点时,dF=ds,则Lm=dD−ds;当目的点是父辈节点时,dF=dD,则Lm=ds−dD.dF可通过式(4)、式(5)计算得到:由ZigBee网络地址分配机制可得上式.式中,A和d分别表示为转发路由节点的网络地址和深度.该路由节点地址若在式(4)范围内,则表示目的节点为其子节点,那么下一跳的地址可通过式(5)得到;反之,则目的节点不为转发路由节点的子节点,那么下一跳的地址为该节点的父节点.由于在最中心的协调器为所有节点的父辈节点,dF为0,我们默认地址A也为0,并假设从协调器到目的节点开始寻址,便可计算出下一跳的地址,并判断源节点是否为它的后代节点,若是dF+1,循环往复,知道源节点不是它的后代节点为止,便可得到dF值,dF计算流程如图3所示.

图3 dF 计算流程图

同理设dD为0,通过式(4)、式(5)计算下一跳地址,每计算一次dD加1,循环往复,知道其等于目的节点地址时结束.并通过求得的dF和dD可以得到RREQ的最大传输范围Lm=ds+dD−2dF,dD计算流程如图4所示.

(4)路径规划

ZigBee网络中的节点收到RREQ分组包后经由式(3)来决定其父节点是否转发RREQ分组包,为了降低整个网络的能耗,我们通过式(3)判断节点转发分组的大致参考方向,并通过节点的能量阈值,深度和能传播的最大范围来找出最优路径.在此过程中,为了便于判断源节点和目的节点之间的父子关系,我们在分组包中添加一个标志项r.

图4 d D 计算流程图

r=0时,当前节点的父节点需丢弃RREQ消息分组包(存在父子关系).

r=1时,当前节点的子节点需丢去RREQ消息分组包(不存在父子关系).

2.2 路由发现过程

第1步:当源节点S发起到目的节点D的路由发现,在此过程中当前节点P从源节点接收到RREQ消息分组包,首先判断该节点是否为目的节点D,如果是的话,则不考虑自身剩余能量的情况下回复RREQ消息分组包,若不是则进入下一步.

第2步:判断当前节点P自身剩余能量大小和该节点能量阈值,若小于,则丢弃RREQ分组包;若大于,则进行下一步.

第3步:判断当前节点P深度,若为奇数,则丢弃RREQ分组包,使用cluster-tree算法沿树路由方式发送数据分组;若为偶数,则进行下一步.

第4步:深度为偶数且通过对比邻居表中周围节点的数目,不为簇头的节点,则丢弃RREQ分组包,沿树路由方式发送数据分组;若为簇头,则进行下一步.

第5步:通过查找标志位R来判断源节点和目的节点之间是否存在父子关系,当R=0时存在父子关系,那么若当前节点为源节点的父节点时,则丢弃RREQ分组包;如果不是,再判断当前节点是否为目的节点的父节点,若是,则进入下一步;如果不是,便令R=1进入循环;当r=1时源节点目的节点间不存在父子关系,若当前节点为源节点的子节点,则丢弃RREQ分组;若不是,再判断当前节点是否为目的节点的父节点,若是,进入下一步;若不是,令R=0进入循环.

第6步:判断由式(4)、式(5)、式(7)计算出的RREQ分组包最大传输范围Lm,如果当前节点接收到分组包中目的节点跳数hops大于Lm,则丢弃RREQ分组包结束;若小于,则进入下一步.

第7步:当前节点转发RREQ分组包,并更新自身剩余能量.

改进的路由算法工作流程如图5所示.

图5 改进的ZBR算法工作流程图

3 实验结果分析

本文的仿真使用的是NS-2仿真平台,该仿真平台自带 IEEE802.15.4 定义的媒体接入层与物理层的协议模块,仿真的时候只需编写网络层算法的协议模块.将仿真出来的结果使用AWK进行数据处理分析后绘图,然后使用Excel进行图表绘制.本文将ZBR算法和改进后的ZBR算法分别在节点数为10～100个不同的场景下进行仿真比较,数据取运行50次的平均值,仿真时随机分布节点,随机并发8个数据流,平均速度为0.5 packets/s,其他的仿真参数设置如表1所示.

表1 仿真参数设置

仿真实验后,我们从平均时间延迟、剩余能量和分组投递率3个方面进行分析.网络平均延迟比较如图6 所示,分簇机制减少了通信量,由簇头进行数据融合,减少了时间延迟.由图可以看出改进后的算法时间相对于改进前的发算法延迟减少了12.4%.

图6 网络平均延迟对比图

剩余能量对比图比较如图7所示.剩余能量百分比时网络中剩余能量和网络中初始能量的比值,它可以有效衡量算法的能量使用情况,剩余能量百分比越高,节能效果越好[11].

图7 剩余能量百分比对比图

由图7可以看出,改进后的算法剩余能量比高于改进钱的算法,随着节点的增加,剩余能量百分比降低,并且随着时间越久,下降越平缓,这也符合实际情况,由于减少了不必要的RREQ分组的转发,使得网络整体能量消耗降低.

分组投递率是检测网络传输性能的关键指标,它能反映出网络的稳定与可靠程度,分组投递率是接收的数据分组和发送数据分组数量的比值,它和网络性能成正比,图8为改进前后算法的分组投递率比较.

图8 分组投递率对比图

由图8可知,丢弃了多余的RREQ分组后的算法,分组投递率变高了.

4 结束语

本文在分析 ZigBee 路由算法的基础上,提出了一种改进了的ZBR算法即分层能量控制算法.改进后的算法通过控制节点能量阈值、限制RREQ分组的传播范围、限制网络深度入手以丢弃不必要的RREQ分组,从而达到减少网络的能耗.并通过NS2仿真实验,从端到端的延迟、剩余能量、分组投递率3方面和未改进的算法进行比较,实验结果表明改进后的算法能在保证网络传输稳定的同时降低端到端的延迟和能量的消耗,使得网络负载均衡,网络生存时间最大化.