雷　斌　穆春喜

(西安工业大学电子信息工程学院　西安　710021)



ZigBee网络路由算法的分析与优化*

雷斌穆春喜

(西安工业大学电子信息工程学院西安710021)

摘要论文结合某研究所高海拔地区冻土地温采集项目,通过对ZigBee网络路由算法的分析,针对其网络中传统的路由算法耗能较高,个别节点由于负载较大而导致能量过早消耗殆尽的问题,提出了一种改进的适用于ZigBee网络的路由算法。改进的算法结合了树路由和AODVjr路由协议,对RREQ的传输范围和大致方向进行控制,同时利用邻居表进行路由查找,避开剩余能量不足节点。最后通过仿真工具分析比较优化前后的路由算法,结果表明,改进后的算法有效地降低了网络的整体能耗,提高了节点的生命周期和收发数据的可靠性。

关键词ZigBee网络; 路由算法; 优化; 仿真

Analysis and Optimization of Routing Algorithm for Zigbee Network

LEI BinMU Chunxi

(College of Electronic and Information Engineering, Xi’an Technological University, Xi’an710021)

AbstractConsidering the high cost of the traditional routing algorithm and a problem of individual nodes have a high pay-load in ZigBee network, an improved routing algorithm is proposed which applied to the ZigBee network. The improved algorithm combines the cluster-tree and AODVjr two kind of routing protocols, which control the broadcast scope and direction of the rout request(RREQ) packet, at the same time, the neighbor tables are used to loopup route and let routers possessed a dormant method, finally, the low residual energy nodes are avoided. Using simulation tool simulate the improvement routing algorithm, the routing algorithm is compared with the original routing algorithm, the results show that the improved algorithm effectively reduces the overall energy consumption of network, prolong the nodes lifetime and improved the reliability of send-receive data.

Key WordsZigBee network, routing algorithm, optimization, simulation

Class NumberTP393.1

1引言

ZigBee是一种短距离、低功耗、低速率、低成本的无线通信技术,底层采用的是IEEE.802.15.4标准规范的物理层与MAC层,ZigBee联盟在此基础上定义了网络层与应用层,这四个层就组成了ZigBee协议。其主要应用于自动控制与远程控制领域,可以嵌入到各种设备中。

ZigBee网络中根据节点的职能不同,可以将节点划分为Coordinator(协调器),Router(路由器)和End-Device(终端设备)三种类型。ZigBee网络是由一个协调器和多个路由器以及多个终端设备组成的,其中协调器负责组建网络,路由器负责路由与转发数据,终端设备负责数据的收发。终端设备不需要维护网络结构,它可以休眠和唤醒,因此可以是一个电池供电设备。ZigBee规范路由设备不支持休眠机制,一直处于活动的状态。在ZigBee中节点一般是采用电池供电,节点能量是有限的。因此实现路由节点的节能是ZigBee实际应用中必须考虑的一个问题[1]。

2ZigBee网络地址分配机制

ZigBee设备有两种类型的地址,一种是通常由制造商设置的全球唯一的64位物理地址,即MAC地址,另一种是在组建网络时由父节点分配的16位网络地址,网络地址的分配机制如下。

假设一个父节点最多可以容纳Cm个子设备,其中所能容纳的路由设备数最多为Rm个,网络的最大深度为Lm,则对于深度为d的父节点为其子节点分配的地址空间偏移量Cskip(d)可以通过式(1)得到。

(1)

子节点的类型不同为子节点分配地址的计算方式也不同。若子节点为第n个加入的路由器节点,则父节点为其分配的网络地址Ac可以通过式(2)得到,Ap为其父节点的短地址。

Ac=Ap+1+Cskip(d)(n-1)

(2)

若子节点为第n个加入的终端节点,则父节点为其分配的网络地址Ac可以通过式(3)得到。

Ac=Ap+Cskip(d)Rm+n, 1≤n≤Cm-Rmm

(3)

3ZigBee路由算法分析

ZigBee协议常用的路由算法有以下几种:Cluster-Tree(树簇路由协议)、AODVjr(按需路由协议)以及两种算法的结合使用[2]。

3.1树路由算法

树路由是按照树结构寻找路径的。在树簇拓扑中,具有转发功能的路由节点可以充当父节点,终端节点只能充当叶子节点。若某一终端节点需要发送数据到其它节点,直接将数据包发送给其父亲节点,父节点通过判别式(4)来确认目的地址是否是其子节点。其中Ap为父节点的短地址,d为其深度,D为目的节点网络地址。

Ap

(4)

若目的节点网络地址满足式(4)则目的地址在父节点的地址空间内,即目的节点是其后代节点,下一跳如何寻址在此分为两种情况:

1) 若目的节点是自己的子终端节点,则直接将数据发送给子节点,收到数据的子节点先判断目的地址是不是自己,不是则丢弃,如果是自己将收到的数据交由应用层进行处理。

2) 若目的节点不是自己的子节点,那么下一跳的地址根据式(5)计算得出:

(5)

若D不满足式(4),则将数据包向上转发给其父节点,若目的地址是其父节点则处理数据,否则的话收到数据的父路由按照如上同样的方式寻址,直到找到目的地址。

整个寻址过程如图1所示。

图1　树簇路由流程

树簇路由是静态路由,不需要存储路由表,减少了维护路由的成本,节省地址空间,但也存在如下的局限性:

1) 树路由是依据树状父子结构寻址的,这就增加了路径的跳数,数据延时较大。

2) 树底层的节点转发数据的跳数更多,压力较大。

3) 若某一路由节点死亡,那么它的后代节点将无法正常地发送数据。

3.2Mesh路由算法

ZigBee的Mesh网络中中一般采用AODVjr(一种按需路由算法)路由算法或者Cluster-Tree+AODVjr来维护路由和转发数据的,AODVjr是AODV(Ad hoc on-demand distance vector routing)路由算法的简化版。

3.2.1AODV路由协议

AODV路由协议本质上是DSR(Dynamic Source Routing)和DSDV(Destination-Sequenced Distance-Vector Routing)两种路由思想基础上的改进。

DSR是一种按需路由协议,即节点仅在需要发送数据时才进行路由发现,然后按照数据分组头部携带的路由信息转发分组,并采用了源路由的路由机制。

DSDV协议是在Bellman-Ford算法的基础上,结合RIP(Routing Information Protocol)完成设计的。但是并没有说明具体的算法,但对其他的路由协议的产生也有一定的影响。AODV协议就借鉴了DSDV序列号的思想。

AODV使用了RREQ(RouteRequest)、RREP(RouteReply)、RRER(RouteError)三种消息作为控制分组。

当某一节点需要转发分组时就会向所有的邻居节点广播一个RREQ,该分组中包含源地址和目的节点地址等信息。邻居节点收到RREQ分组后,如果自己的路由表中保存着源节点和目的节点的信息,就丢弃该分组,否则的话在路由发现表中创建表项记录RREQ中的信息。

3.2.2AODVjr路由协议

AODVjr是简化了的AODV的一种协议,它是按时间最短原则来寻找最优路径的。路由节点需要发送数据时,先查看路由表是否有到达目的节点的路径,有则直接发送过去,若无则使用RREQ包去查找路由,若源节点可以收到目的节点的RREP,则存在到达目的节点的最优路径,数据包可以按此路径传输数据包。在AODVjr协议中,AODVjr优化掉了AODV协议的目的节点序列号,只有目的节点对最早到来的RREQ进行RREP,之后到来的RREQ不予回复,中间的节点也不对RREQ进行回复。同时,AODVjr取消了节点的先驱列表,简化了路由表,降低了复杂度。并且AODVjr路由算法通过目的节点对源节点周期性的发送KEEP-ALIVE来维护路径,取代了AODV算法中的HELLO消息机制[4]。如图2所示是广播RREQ和RREP回复的过程。

图2　广播RREQ和RREP回复过程

AODVjr是按照最短路径来查找路由的,并且在AODV的基础上做出了很大的优化,算得上是一种比较好的路由策略,但仍旧存在着一些问题。比如:当目的节点是源节点的后代节点时,那么源节点向它的非后代节点洪泛的RREQ便是多余的;同理若目的节点是它的非后裔节点时,那么它向后裔节点洪泛的RREQ便是多余的分组,降低了寻址的效率,消耗了节点的能量。

3.2.3路由控制分组

1) RREQ控制分组

路由请求命令帧的结构如图3所示。网络层荷载中命令帧标识符为0x01,标识这是一个路由请求,目的地址为网络短地址,命令选择域的0~6位保留,第7位表示路由维护,第7为若为1表示需要进行路由维护,为0则表示不需要路由维护。路由请求ID为源设备产生的序列号。路由开销表示路由请求的链路中累积的成本,用一个字节表示。

命令帧标识符命令选择路由请求ID目的地址路由开销字节:11121网络层载荷

图3RREQ控制分组

2) RREP控制分组

当目的节点收到源节点发送过来的RREQ时,会沿着此链路反向回复一条RREP分组给源地址。RREP控制分组如图4所示。RREP控制分组的命令帧标识符为0x02。

命令帧标识符命令选择路由请求ID源地址目的地址路由开销字节:111221网络层载荷

图4RREP控制分组

3) RRER控制分组

当维护路由失败时,源节点会发送RRER控制分组给邻居节点,通知失效的节点。路由错误命令帧的结构如表1所示。RRER的命令帧标识符为0x30。错误代码有以下几种:无效路由0x00;树状链路失败0x01;非树状链路失败0x02;低电池电压0x03;无路由能力0x04;0x05-0xFF保留[5]。

表1　RRER控制分组

4路由优化策略

通过上面的分析比较可知,以上两种路由方法有各自的优缺点,针对其缺点本文采用了以下改进的方案。

4.1限制最大跳数

从树形拓扑可以看出,如果采用树寻址的算法,其最大跳数可能是网络深度的2倍即2Lmax。但实际上从源节点到目的节点的跳数是小于2Lmax,所以可以通过限制最大跳数来提高路由效率。当目的节点是源节点的后裔节点时,最大跳数可由式(6)得到,dSrc为源节点的深度,dDes为目的节点深度。

dmax=|dSrc-dDes|

(6)

当目的节点不是源节点的后裔节点时,则最大跳数为它们的共同父节点到源节点和目的节点的跳数之和,共同的父节点深度为dF,则通过式(7)可得到最大跳数[7]。

dmax=dSrc+dDes-2dF

(7)

4.2邻居表的使用

因为ZigBee网络路由器存在着邻居表,邻居表中包含有该设备一跳之内的所有节点的长短地址、RSSI等信息。所以可以使用邻居表进行路由,并且对其进行改进不会增加额外的开销。可以使用下面的函数来获取邻居表项:

NLME_GetRequest(ZNwkAttributes_t NIBAttribute,uint16 Index,void*Value)

其中参数NIBAttribute支持的属性有网络容量nwkCapabilityInfo,邻居表nwkNeighborTable,邻居表数目nwkNumNeighborTableEntries,Index用于表的索引,Value指向存储属性值的地址。节点在收到路由请求时可以查看邻居表中是否存在有目的节点,若存在可以单点直接发送到目的节点,完成路由任务。

4.3采用最小能量剩余优化路由

在ZigBee中,距离协调器越近的路由节点转发的数据量可能越大,也需要充足的能量来维持中继的功能,否则能量不充足会导致数据帧的丢失和网络的瘫痪,因此需要检测节点的能量值,来判断是否使用该节点转发数据包。假设节点的初始能量值为E0,剩余最小能量值为Emin,如式(8)所示

(8)

其中,t为设备工作时间,α为一特定系数,作用在于减缓Emin值减缓的速度,d表示节点的网络深度。可以看出最小能量值与时间、节点网络深度成反比。在改进的算法中设置变量energy表示该节点的剩余能量,当energy

4.4添加路由器休眠方法

TI的ZigBee协议栈没有路由器的休眠机制,只有终端节点的休眠机制,而路由器在ZigBee网络中担任着非常重要的数据转发任务,所以必须保证路由器的电源充足。

ZigBee节点有五种不同的运行模式(供电模式),分别是主动模式、空闲模式、PM1、PM2和PM3。主动模式是一般模式,而PM3具有最低的功耗,稳压器的数字内核关闭,所有的振荡器都不运行,复位或外部中断时系统将转到主动模式。所以在节点采集完数据后,通过初始化睡眠定时器开启路由器的PM3模式,进入超低功耗休眠模式,每隔一段时间去唤醒检测是否有网络,若有网络则进入运行模式否则再次进入休眠模式。

初始化休眠定时器和设置PM3模式的部分代码如下:

初始化休眠定时器:

void InitSleepTimer(void)

{

ST2 = 0X00;

ST1 = 0X0F;

ST0 = 0X0F;

EA = 1; //开中断

STIE = 1; //睡眠定时器中断使能

STIF = 0; //睡眠定时器中断标志

}

设置PM3模式:

void SysPowerMode(uchar mode)

{

if(mode < 4)

{

SLEEPCMD |= mode;//设置系统睡眠模式

PCON = 0x01; //进入睡眠模式 ,通过

//中断唤醒

}

else

PCON = 0x00; //通过中断唤醒系统

}

4.5路由具体实现方法

根据以上的方案,综合后具体的实现方案如图5所示。

1) 源节点发起路由请求时,各路由节点先初始化邻居表项,收到RREQ的节点查看目的节点是否是自己,如果是则处理数据并进行路由回复[9];

2) 否则,判断是否为FFD,不是FFD丢弃RREQ;

3) 否则,检查自身的能量值是否小于最小能量值,若小于,则丢弃RREQ;

4) 否则,根据式(7)查看跳数是否小于dmax,若不小于,则丢弃RREQ;

5) 否则,查看邻居表中是否存有目的节点,有则发送给邻居节点RREQ,目的邻居节点的能量不论剩余多少都回复RREP包;

6) 否则,利用式(4)判断目的节点是否为后代节点,不是则将请求包转发给自己的父节点;

7) 否则,利用式(5)寻址,若目的节点是其子节点则直接回复RREP包;

8) 否则,发送给子路由设备从3)开始寻址,直到找到目的节点。源节点收到RREP后,会按照路由发现的路径进行数据的传输。

图5　路由具体实现方法

5算法分析

本文在传统算法AODVjr的基础之上,结合树簇算法,通过限制跳数减少了路由延时。利用邻居表增加寻址效率,并考虑了剩余能量并在网络运行期间周期性更新,减小了由于节点能量不足死亡造成瘫痪的概率,有效地减少了网络开销,保证了数据的可靠传输和网络的稳定性[10]。

6仿真并分析结果

仿真实验中通过比较改进算法与ZigBee中使用的AODVjr算法,主要是比较两者的网络总耗能和平均跳数。仿真工具为Matlab R2012b。

6.1节点与平均跳数关系仿真

设置网络深度为5,每一层的节点数为20,其中路由器数为6。如图6所示是最后仿真的关系图。从图中可以明显地看出,随着网络节点数目的增加,平均跳数有明显的差异。在节点数目较少的时候,由于由于原始算法不需要计算最大跳数,而改进的算法需要计算最大跳数,所以改进后的算法跳数有些许增加。但是当节点增加到某个数目时,改进的算法显示出比传统算法减少的趋势。所以网络节点越多,越能体现出改进算法的优越性。

图6　节点与平均跳数

6.2时间与剩余能量关系仿真

设置网络节点数为80,α设置为0.5,网络运行时间为20min,设置网络深度为5,每一层的节点数为20,其中路由器数为6。时间与剩余能量的关系图,如图7所示。从图中可以明显地看出,由于改进后的算法通过邻居表来获取路由,并控制路由请求的方向,有效地节省了能量,提高了效率,所以改进的算法相比原始算法,能量消耗速度更缓慢。

图7　时间与剩余能量

7结语

ZigBee网络是近年一种新兴的无线传感器网络,具有广阔的应用场景和发展空间,作为一种低功耗技术,其路由算法必然会向着节能稳定的方向发展。所以研究并改进目前路由协议中的不足,对网络的稳定性和数据的可靠性有着不言而喻的积极意义。

本文通过控制RREQ数据包的转发方向,限制其最大跳数并利用邻居表增加了路由寻址效率。为减少死亡节点数目,防止网络分割,有效地利用了最小剩余能量对中继节点进行调整,使网络耗能均衡。最后通过仿真改进前后的效果,结果表明,该算法能够有效地减少网络开销,减缓耗能保证了数据传输的有效性。

参 考 文 献著录规则 中的责任者采用姓前名后的著录形式。欧美著者的名可缩写,姓大写,姓和缩写的名之间不可用“.”隔开,而是用空格。如用中译名,可以只著录其姓。如原文中作者为“P．S．昂温”则在本刊要求中应写成“昂温 P S”,Albert Einstein Seny应写成EINSTEIN A S。 的责任者之间用“,”分隔。不超过3个时,全部照录。超过3个时,只著录前3个责任者,其后加“,等”,外文用“,et al”,“et al”不必用斜体。

[1] 王芳,柴乔林,班艳丽.改进的ZigBee网络路由算法[J].计算机工程与应用,2008,28(11):300-303.

WANG Fang, CHAI Qiaolin, BAN Yanli. Improved Routing Algorithm for ZigBee network[J]. Computer Engineering and Application,2008,28(11):300-303.

[2] Chakeres I D, Klein-Bemdt. AODVjr, AODV simplified[J]. Mobile Computing and Communication Review,2002,6(3):100-101.

[3] 李晖,常全成,郭长顺.Mesh网络下AODV、DSR和ZigBee路由的比较分析[J].通信技术,2010,10(9):100-102.

LI Hui, CHANG Quancheng, GUO Changshun. Analysis and Comparison Study of AODV, DSR and ZigBee Routing Protocols in Mesh Topology[J]. Communications Technology,2010,10(9):100-102.

[4] 耿萌.ZigBee路由协议研究[D].郑州:解放军信息工程大学,2006,12(3):58-60.

GENG Meng. Research for ZigBee routing protocol[D]. Zhengzhou: The PLA Information Engineering University,2006,12(3):58-60.

[5] 杜焕军,张维勇,刘国田.ZigBee网络的路由协议研究[J].合肥工业大学学报(自然科学版),2008,46(1):1618-1619.

DU Huanjun, ZHANG Weiyong, LIU Guotian. Study of the routing protocol in ZigBee networks[J]. Journal of Hefel University of Technology,2008,46(1):1618-1619.

[6] 向庆,王建明.ZigBee协议网络层的研究与实现[J].电子技术应用,2006,20(1):129-132.

XIANG Qing, WANG Jianming. Research and implementation of ZigBee protocol in the network layer[J]. The application of electronic and technology,2006,20(1):129-132.

[7] Kleinberg J. Authoritative gources in a hyperlinked environment[C]//Proceedings of the 9th ACM—SIAM Symposium on Discrete Alsorithms. San Francisco, USA, Jan 25—27 1998. USA, SIAM, Philadelphia,1998:668-677.

[8] 郭瑞星,王庆生.ZigBee路由算法的研究与改进[J].电脑开发与应用,2011,32(3):125-128.

GUO Ruixing, WANG Qingsheng. Research and Improvement on the Routing Algorithm in ZigBee Networks[J]. Computer Development and Application,2011,32(3):125-128.

[9] Flake G W, Lawrence S, Giles C L, et al. Self organization of theweb and identification of connnunities[J]. IEEE Computer,2002,35(3):66-71.

[10] Imafuji N, Kitsuregawa M. Effects of maximum flow algorithm on identifying web community[C]//Proceeding of the Forth international Workshop on Web Information and Data Management, United states, Nov 8 2002. United States: Association for computing Machinery,2002:43-48.

一.总要求

为了帮助向本刊投稿的作者按规范著录参考文献,现将常见类型文献的著录格式作如下要求。

本刊要求双语参考文献,所有的中文参考文献均需附英文译文,示例如下:

示例1:

[1] 焦李成,杜海峰,等．免疫优化计算、学习与识别[M].北京:科学出版社,2006．

JIAO Licheng, DU Haifeng, et al Immune optimization calculation 、Learning and Recognition [M]. Beijing: Science Pres,2006．

[2] 李诗灵,陈宁,赵学彧．基于粒子群算法的城市轨道交通接运公交规划[J]．武汉理工大学学报(交通工程与科学版)2010,34(4)780-783．

LI Shiling, CHEN Ning, ZHAO Xueyu． Planning of Feder Bus to the Urban Rail Transit Based on Particle Swarm Optimization[J]． Journal of Wuhan University of Technology(Transportation Science & Enginering),2010,34(4):780-783．

示例2:马克思,恩格斯．示例2:YELLAND R L, JONES S C, EASTON K S, et al．

二.图书和期刊的著录格式

◆普通图书(原著):

[序号]著者．书名[M]．版本(第1版不著录)．出版地:出版者,出版年:引文页码．

[3]余敏．出版集团研究[M]．北京:中国书籍出版社,2001:179-193．

[4]中国社会科学院语言研究所词典编辑室．现代汉语词典[M]．修订本．北京:商务印书馆,1996:258-260．

[5]CRAWFPRD GORMAN M． Future libries: dreams, madnes, &reality[M]． Chicago: America Library Asociation,1995．

◆普通图书(译著):

[序号]著者．书名[M]．译者,译．版本．出版地:出版者,出版年:引文页码．

[6]AGRAWAL G P． 非线性光纤光学[M]．胡国绛,黄超,译．天津:天津大学出版社,1992:179-193．

[7]霍斯尼 R K． 谷物科学与工艺学原理[M]．李庆龙,译．2版．北京:中国食品出版社,1989:15-20．

◆期刊(有卷)

[序号]著者.题名[J]．刊名,出版年份,卷(期)引文页码．

[8]蒋超,张沛,张永军,等．基于SRLG不相关的共享通路保护算法[J]．光通信技术,2007,31(7):4-6．

[9]DIANOV E M, BUFETOV I A, BUBNOV M M, et al． Thre-cascaded 1407nm Raman laserbased on phosphorusdoped silica fiver[J]． OPTICS LETTERS,2000,26(6):402-404．

◆期刊(无卷)

[序号]著者.题名[J]．刊名,出版年份(期):引文页码．

[10]周可,冯丹,王芳,等．网络磁盘阵列流水调度研究[J]．计算机学报,2005(3):319-325．

[11]VLATK V, MARTIN B P． Basic of quantum compwtation[J]． Proces in Quantum Electronics,1998(22):1-39．

三.电子文献的著录格式

◆电子文献:

[序号]主要责任者．题名:其他题名信息[文献类型标志/文献载体标志]．出版地:出版者,出版年(更新或修改日期)[引用日期]．获取和访问路径．

[12]Online Computer Library Center, Inc． History of OCLC[EB/OL]．[2000-01-08]．htp://www．oclc．org．

[11]萧钰．出版业信息化迈入快车道[EB/OL]．(2001-12-19)[2002-04-15]．htp:∥www．creader．com/news/200112190019．htm．

四.学位论文与论文集的著录格式

◆学位论文:

[序号]著者．题名[D]．出版地:出版者,出版年:引文页码．

[13]孙玉文．汉语变调构词研究[D]．北京:北京大学文学院,2000．

◆论文集:

[序号]著者．题名[C]//著者．专题名:其他题名．出版地:出版者,出版年:引文页码．

[14]白书龙．植物开花研究[C]//李承森．植物科学进展．北京:高等教育出版社,1998:146-163．

[15]AZIEM M M A, ISMAIEL H M． Quantitative and qualitative Evaluations of Image Enhancement Techniques[C]//Procedings of the 46th IEEE International Midwest Symposium on Circuits and Systems,2003:664-669．

中图分类号TP393.1

DOI:10.3969/j.issn.1672-9722.2016.03.026

作者简介:雷斌,男,副教授,研究方向:无线传感器网络、信息安全与网络对抗技术、虚拟现实技术、嵌入式系统等。穆春喜,男,硕士研究生,研究方向:无线传感器网络。

收稿日期:2015年9月9日,修回日期:2015年10月23日