Zigbee网络基础路由分析与改进

摘要:Zigbee是一种基于IEEE 802.15.4协议标准的新兴的短距离无线通信技术。该文详细介绍了两种适用于ZigBee网络的近距离基础路由协议,分析这两种路由算法并提出相应改进方案或策略。最后提出了一种基于AODVjr的簇树网络路由策略,平衡考虑了报文的端到端延迟和网络生存时间,提高了ZigBee网络的性能。

关键词:路由算法;Cluster-Tree;AODVjr;分簇

中图分类号:TP393文献标识码:A文章编号:1009-3044(2009)33-9242-04

Analysis and Improvement for Basic Zigbee Wireless Networks Route

ZOU Xiao-wu,XU Du,JIANG Yong-ping,ZHOU Yan-can

(School of Information,Guangdong University of Technology,Guangzhou 510009,China)

Abstract: Zigbee is an emerging shortrange wireless network technology, based on IEEE 802.15.4 protocols. In this paper, two short-distance route protocols for Zigbee networks are introduced and analysed in details, the corresponding improved blue print and strategy are proposed.At last, suggest an improved Cluster-Tree routing algorithm based on AODVjr, which equipoise the latency of transport and life span of networks, and raised the efficiency of ZigBee networks.

Key words: routing algorithm; cluster-tree; AODVjr

ZigBee是一种新兴的近距离、低复杂度、低功耗、低数据速率、低成本的无线网络技术,建立在IEEE 802.15.4标准的基础上,在数千个微小的传感器之间相互协调实现通信。但是在ZigBee传感器网络中,由于网络内节点资源有限,数据包的传送通常需要通过多跳通信方式到达目的端。因此,数据包的传送延迟和节点的剩余能量成为了路由设计的重点,如何根据不同的应用需求设计高效率的路由选择算法是实际应用中网络层设计的一个主要任务。

1 ZigBee网络的拓扑结构

IEEE802.15.4/ZigBee网络层支持如图1所示的三种拓扑结构:星型、簇树型和网状型拓扑结构。在星型网络中,整个网络由一个称为zigBee协调器的设备来控制。zigBee协调器负责发起和维护网络正常工作,保持同网络的终端设备来通信。在网状型和簇树型拓扑结构中,zigBee协调器负责启动网络以及选择关键的网络参数,也可以使用zigBee路由其来扩展网络结构。在簇树型网络中,路由其采用分级路由策略来传送控制信息和数据。树型网络可以采用基于信标的方式进行通信。网状型(Mesh)网络中,设备之间使用完全对等的通信方式。Mesh网一般是由若干个FFD连接在一起组成骨干网,每个节点都可以与它的无线通信范围内的其它节点通信,但它们中也有一个会被推荐为ZigBee协调点。

2 两种常见的ZigBee网络路由算法

2.1 Cluster-Tree算法简介

Cluster-Tree(簇树)算法[2]中,节点根据分组目的节点的网络地址计算分组的下一跳.对于地址为A深度为d的ZigBee路由节点,如果下述表达式(1)成立,则具有地址为D的目的设备为子设备,其中Cskip由网络地址分配机制确定。

A

如果确定分组的目的节点是接收节点的一个后代,节点就将分组发送给它的一个子节点,此时如果满足:

D>A+Rm~Cskip (d)(2)

则说明目的节点是它的一个终端子节点,这时下一跳节点地址N为:

N=D (3)

否则, N=A+1+{[D-(A-1)]/ Cskip (d)}~Cskip (d)(4)

如果目的节点不是接收节点的一个后代,则将分组发送给它的父节点。

2.2AODVjr算法简介

AODVjr是一种简化版本的AODV(Ad hoc按需距离矢量路由协议),主要是考虑到ZigBee无线传感器网络的电池能量有限性、应用方便性等因素,而简化了AODV的一些特点。在MESH结构的ZigBee网络中一般使用AODVjr算法来进行路由发现和数据传输。AODVjr舍弃了AODV中的目标序列号和跳数,只能是目标节点来对最先到达的RREQ信号做出响应,而不是像AODV中已知到目的节点路径的中间节点也可以做出响应。这种策略也被称作点到点策略。同时AODVjr取消了HELLO信息的发送,由Destination定期向Source发送KEEP_ALIVE连接信息来维持路由。当Source在一段时间内没有收到Destination发来的KEEP_ALIVE信号时,它认为此条路径失效,必要时重新进行路由发现。此外,AODV中的RERR信号以及前驱列表在AODVjr算法中也无需考虑。这使得ZigBee的路由发现简单且实用、且更加节能高效。图2是使用AODVjr算法时寻找路由的方式,可看到RREQ广播和RREP回复的过程。R5是中心协调器,当终端设备D6要发送数据给R2,D6先把数据发送给具有路由功能的父节点R7,R7查找自身路由表,没有发现到一条到R2的有效路径,于是发起一个路由发现过程,构建并同时洪泛RREQ包。R2选择最先到达的RREQ包的传送路径R7―R6―R2,并返回RREP信息,R7收到R2发来的RREP信号,路由路径建立,R7就会按这条路径来发送缓存的数据。在此期间,R2定期发送KEEP―ALIVE包,用以维护路由信息。

3 算法分析及改进

基于ZigBee协议堆栈的应用通常采用默认路由策略,NWK层一般默认采用AODVjr算法,而Cluster-Tree(簇树)路由算法一般在对时延要求较高的场合才会给予考虑。从参考文献[3]的模拟中可以看出,在大多数情况下采用AODVjr算法的延迟明显长于簇树路由算法,因为AODVjr的路由发现过程产生了额外的延迟。尽管簇树路由算法在缩短时延方面有很好的效果,但它是一个静态的算法而AODVjr中能耗均匀的分布于网络,而能耗在WSN中是一个非常关键的问题,所以将AODVjr作为默认路由是合理的。然而,为了网络能更加实用、高效,针对能耗和时延对原有算法作一些改进是必须做的。

3.1 一种改进的Cluster-Tree算法

为使簇树路由算法在缩短时延方面有更好的效果,应该考虑邻居节点[4]和选择下一跳节点是到目的节点的最短路径的节点。这是基于Greedy算法的想法,因此没有必要去证实最后采用了一条最短的路径。改进的算法主要包括以下三步:

1) 如果目的节点在它的邻居列表中,直接传输到对应的节点。

2) 如果目的节点是它的子节点,选择自身的子节点作为下一跳。

3) 如果不属于以上两种情况之一,那么选择除其子节点外邻居列表中到达目的节点最少跳数的节点作为下一跳。算法如下:

Algorithm 1: 计算最少跳数节点

Input: source node S,destination node D

Output: minHopNode-the minimum hop node address

Begin:

maxComDepth-record the max common ancestor depth,set 0 at first

minHopNode-record the node of maxComDepth,set S’s parent at first

foreach node N in S’s neighbor table

if N is the children node of S continue

for i=1 to Lm

if N and D do not have the common ancestor node at depth i

then i = i-1 break;

end for

if i > maxComDepth then

maxComDepth = i;minHopNode = N

end foreach

End

3.2 改进AODVjr算法的基本策略

对AODVjr算法进行改进时,一般从能量角度考虑,根据节点的剩余能量状态分为充足、不充足及即将耗尽3种等级。路由发现过程中,中间节点在收到路由RREQ报文后,根据节点自身能量等级决定下一步动作。算法如下:①收到RREQ报文后,判断自身能量状态:能量在第1等级时,直接转②;能量在第2等级时,等待一段时间后转②;能量在第3等级时,转③。②判断自身是否为目的节点,若不是,转发RREQ报文;若是,回复RREP报文。③不对RREQ进行响应。

当出现源节点在一段时间后仍没发现有效路由,则重新进行路由尝试,此时路由节点不再进行能量区分以保证路由正常建立。通过上述改进,每个节点根据自身的状况有选择地转发RREQ报文,能阻止在能量不足的节点上建立路由,有效地减少了RREQ报文的广播风暴,可以在总体上提高网络性能。

4 一种基于AODVjr的簇树网络路由策略

通过对上述改进后的算法和改进的策略分析可知:改进的Cluster-Tree结构的优点在于可以增加网络的覆盖范围,在缩短时延和数据聚合方面有较为明显的优势[5]。但其缺点也很明显,这种非自适应算法决定了不可能最大限度延长网络的生存时间。而AODVjr算法具有灵活的路由查找功能,其按需路由提高了协议效率,具有快速适应动态链路环境、较低的处理和内存开销以及支持多播的特点且具有自主学习和发现拓扑的能力,但是因需要维护路由表而有初始延迟且容易产生RREQ广播风暴而耗费能量。为此,提出了融合了上述两种改进算法优点的一种基于AODVjr的簇树网络路由策略,即优化AODVjr+Cluster。

4.1 簇的建立过程

协议在设计的之初将整个ZigBee网络分成多个簇[6],簇的建立过程可分为四个阶段:簇首节点的选择、簇首节点的广播、簇的建立和调度机制的生成。每个簇又由多个节点组成,这些节点按功能又分成3种类型的节点:簇首,簇成员和网关节点。簇首作为簇的中心,负责路由过程建立后向簇内成员广播和簇结构的建立,收集簇成员的数据并在融合处理后发送给网关节点。簇的划分是依据下面的规则的基础建立的:

1) 中心节点是一个簇首;

2) 簇首必须是有路由能力的节点,且网络深度为偶数的节点;

3) 深度为奇数的节点则属于它的父节点的簇;

4) 终端节点的簇属于它的父节点的簇。

簇首建立过程如图3所示。

簇的建立过程是根据节点分布的密集度来划分。簇首的短地址作为该簇的标签。簇的划分是按隔一个深度做一次划分,因为中心节点的深度为0且是一个簇首,所以在深度为偶数的路由节点里面选择一个簇首,簇首的短地址就是这个簇的所有成员的标识。除以中心节点为簇首形成一个簇外,其它的簇首则是根据节点的分布情况来选择的,基于AODVjr的分簇路由根据判断信号强度来确定网络中节点的密集程度。在簇形成的开始阶段,判断网络深度,网络深度为偶数的节点向外广播RREQ,收到RREQ的节点向源节点发送一个确认信息,则发送RREQ的源节点把收到的确认信息按照所规定的最小信号强度来取舍,若大于这个值,则这个节点加入邻居表里,最后根据比较邻居表里周围节点的数目选定节点数最多的节点作为簇首,这个节点的短地址作为这个簇的标签,节点一旦被选定为簇首节点,则向它的周围节点发送簇首广播报文,收到广播报文的节点在自己不是簇首的情况下发送簇加入报文,簇首发送加入响应后,即加入到该簇。簇成员节点维护一个簇首节点列表,簇首节点维护一个网络的所有簇成员列表。

4.2 路由过程的建立与维护

AODVjr+Cluster的路由请求过程类似于Z_AODV的方式。源节点有数据要发送给目标节点时,首先在自己的路由表中查寻到目标节点的路径,若路由存在且有效,则直接发送数据;反之,若路由不存在或路由存在但已标明为无效时,源节点则开启一个泛洪路由发现过程。新路由建立伊始,源节点创建一个路由请求包RREQ,并向其周围节点广播。如果邻居节点收到RREQ,则根据计算簇标签的方法计算出目的节点的簇标签,并在它的邻居表中增加这个簇标签的一个路由接入点,路由查找表中也增加一个目的节点的网络地址的路由接入点;在中间节点收到RREQ时,则与它的路由搜索表中的比较路由成本,如果这个路由成本比较低的话,则更新路由搜索表。之后继续广播,直至到达目的节点为止。

目标节点收到路由请求后,不再广播路由请求,先建立反向路径,并生成一个RREP,RREP中含有最新的各类信息,沿反向路径送至源节点。源节点和中间节点在收到RREP后建立到目标节点的路由,更新系列号等相关信息,源节点建立路由并开始传送数据。这个路由过程一旦建立完毕,源节点向它的簇首发送一个携带有路由信息的路由确认包RNOT(Rote Notify),簇首在收到这个确认包后再广播一个路由更新包RUPT(Route Update),簇成员收到这个信息后,则共享节点新建立的路由信息。

数据传送阶段,簇成员通常只与其簇首通信,数据的转发由簇首负责。基于AODVjr的分簇算法既保证了原有覆盖范围内的数据通信,又在很大程度上节省了能量和缩短了时延。分簇思想具有很明显优点,簇头可以负担数据融合的任务,减少了数据通信量;其拓扑结构有利于分布式算法的应用,适合大规模部署的网络。由于大部分簇内节点在相当长的时间内关闭通信模块,不参加数据转发过程,因此可以延长整个网络的生存时间。

4.3 仿真与结果分析

用NS-2仿真软件[7]进行模拟实验将改进的AODVjr+Cluster算法和改进的AOOVjr进行比较,重点是对比两者在数据传送过程中报文的发送成功率及分组端到端的平均延时。仿真结果证明了前者的高效性。在相同的仿真环境下分别运行AODVjr和优化的AODVjr+Cluster的仿真程序并比较仿真结果,图4是报文发送成功率比较图,从图中可以看出优化的AODVjr+Cluster协议的数据报文发送成功率要明显高于原来的AODVjr协议。

图5是网络中两种协议在相同的节点数量下数据包端到端的平均延时。从图5可以看出,随着源节点数目的增多时延变长。在相同源节点数目的情况下,延时的总体趋势是随着节点数变多而变大,这是由于随着源节点数目的增加会使网络过于拥塞,包成功接收的时间变长,因此会加长时延。而在源节点数目相同的情况下,优化的AODVjr+Cluster算法的时延还是相对较小的。

5 结束语

针对ZigBee网络的基本路由算法,本文在详细分析了其特征基础之上提出了改进的Cluster-Tree算法和改进AODVjr的基本策略,最后提出了一种基于AODVjr的簇树网络路由策略。改进的簇树算法在原Cluster-Tree算法基础上引进了邻居列表,在数据传输过程中,综合考虑了路由跳数;改进AODVjr算法的基本策略,从能量角度考虑,有效延长网络的生存时间;基于AODVjr的簇树网络路由综合了上述两种改进方案的优点,能有效的兼顾端到端延迟和节点剩余能量,较好的改善了网络效率。总之,通过对ZigBee网络路由分析,可以进一步改进其网络性能,从而保证ZigBee网络技术独特的生存空间。

参考文献:

[1] 蒋挺,赵成林.紫蜂技术及其应用[M].北京:北京邮电大学出版社,2006:9-12.

[2] 耿萌.Zigbee路由协议研究与分析[D].河南:信息工程大学,2006.

[3] B. NEFZI and Y. Q. Song. Performance analysis and improvement of zigbee routing protocol[C].In 7th IFAC International Conference on Fieldbuses & Networks in Industrial & Embedded Systems, pages 351C369, France, 2007.

[4] 班艳丽,柴乔林,王琛.基于能量均衡的ZigBee网络树路由算法[J].计算机应用,2008,28(11):2791-2794.

[5] 刘湘雯,侯惠峰,张霞等.基于群树结构的IPv6无线传感器网络的组网及路由协议[J].计算机科学,2007,34(5):28-31.

[6] HOU Ting-chao,Tsai T J.An Access―based Clustering Protocol for Multihop Wireless Ad Hoc Networks[J].IEEE Joumal on Selected Areas in Communications,2001,19(7):1201-1210.

[7] 鲍凤卿.基于Ns2的ZigBee网络节点接入的研究[J].信息技术,2008,11(5):95-98.