ZigBee中Cluster-Tree路由算法改进研究

邹国霞，李 燕

（桂林航天工业高等专科学校，桂林 541004）

0 引言

无线传感器网络是由大量无处不在的，具有通信与计算能力的微小传感器节点密集布设在监控区域而组成的自组织网络，在工业控制、工业无线定位、家庭网络、汽车自动化、楼宇自动化、消费电子、医疗设备等多个领域具有广阔的应用前景和较高的应用价值。ZigBee是IEEE 802.15.4标准基础上的无限个域网的短距离无线通信技术，它拥有低成本、低功耗、低复杂度、网络容量大、可靠性高等方面的优势[1~3]。

在ZigBee网络中，Cluster-tree路由算法为目的地址提供了简单但可靠的路由[4~6]。该算法采用了网络地址分配机制，节点根据目的节点的网络地址来计算下一跳节点。虽然该算法具有简单并且不需要存储路由表等优点，但也存在一些缺点,比如即使目的节点就在发送节点附近，数据包也必须沿Cluster-tree拓扑传送到目的节点，而不能直接发送到目的节点。为此，靠近根部的节点可能会因为业务量过大而过早耗尽电池能量。针对这些情况，本文对Cluster-tree路由算法进行了改进，引入路由表，使局部路由最优化,从而减少了网络的总体能量消耗，延长了网络的寿命。

1 ZigBee Cluster-tree路由算法

IEEE 802.15.4定义了2种物理设备，全功能设备（Full Function Device,FFD）和精简功能设备（Reduced Function Device,RFD）[7,8]。FFD可以担任网络协调器、路由器和终端设备，能与RFD和其他FFD进行通讯。RFD只能作为终端设备，只需要较少的资源和存储空间，成本比FFD低很多。在ZigBee网络中，定义了三种逻辑设备类型：ZigBee协调器（简称ZC）、ZigBee路由器、ZigBee终端设备。

1.1 ZigBee地址分配机制

加入ZigBee网络的节点通过IEEE 802.15.4 MAC层提供的关联过程组成一颗逻辑Clustertree，当网络中的节点允许一个新节点通过它加入网络时，它们之间就形成了父子关系，每个进入网络的节点都会得到父节点为其分配的一个在该网络中唯一的网络地址。规定每个父节点最多可以连接Cm个子节点, 这些子节点中最多可以有Rm个路由节点，网络的最大深度为Lm。Cskip(d)是网络深度为d的父节点为其子节点分配的地址之间的偏移量。Cskip(d)的计算表达式为(1)式

设置ZC的网络地址为0 ，其网络深度Depth0 =0。假设父节点k的深度为d，地址为Ap。如果新加入的节点是RFD ，并且该节点是其父节点的第n个RFD节点，则父节点为该节点分配网络地址:

如果新加入的节点是FFD，并且该节点是其父节点的第k个FFD节点。则父节点为该节点分配网络地址:

ZigBee网络路由基于上面的分布式网络地址分配机制构建，支持Cluster-Tree路由算法、AODVjr路由算法及两者混合模式的路由算法。

1.2 Cluster-tree路由算法

在该算法中，节点根据目的节点的网络地址来计算分组的下一跳，假设地址为A，深度为d的ZigBee路由节点收到目的节点地址为D的数据帧，路由节点首先通过(4)式

判断该目的节点是否是它的后代节点。

如果目的节点是其后裔节点,则下一跳节点地址为(5)式。

否则，如果目的节点不是其后裔节点，则下一跳节点为该节点的父节点。

2 问题的提出

ZigBeeCluster-tree路由算法按Cluster-tree型结构分层遍历，算法简单且查找目的节点的速度快，但是这种路由选择不可能是最佳路由，而且ZC节点需要转发大量的数据，必须储备充足的能量，但是就目前的技术，电池的使用时间是有限制的，为此容易造成网络分割，缩短网络寿命。

假设有如图1所示的网络，如果采用原始的Cluster-Tree路由算法，rfd[12]发送数据给rfd[14]，需要4跳才能到达；rfd[12]发送数据给rfd[17]，需要5跳才能到达。且都需要ZC进行转发，消耗了大量的ZC能量。如果考虑在无线信号覆盖范围内，信号可以直接从源地发送到目的地，则rfd[12]发送数据给rfd[14]，需要2跳就能到达；rfd[12]发送数据给rfd[17]，需要2跳就能到达。

针对以上的问题，需要将邻居表应用到Cluster-Tree路由算法中，减少Cluster-Tree路由算法的路由跳数和节约整体能量。

图1 ZigBee网络拓扑结构图

3 改进算法设计

3.1 邻居表定义

如果两节点在一跳范围内可以直接通信,我们就说这两个节点是邻居。当一个ZigBee节点想要加入网络时，它会以广播的形式将请求连接的信息传给其一跳通信范围内的其他节点；收到请求连接信息的其它存在于已知网络中的节点会给要求加入网络的节点传回一个信息；最后要求加入网络的节点根据收到的信息选择一个合适的父节点，再回传一个加入信息并正式加入该网络。

在节点加入ZigBee网络时，相互传送信息的过程中可以得知一跳范围内节点的一些基本信息，并将这些信息存放在邻居表里。设计的邻居表结点NbNode如图2所示。

图2 邻居表结点结构体

NbNode有三个域:

AddNb：邻居节点地址。

Type：邻居节点设备类型, 如果为FFD设备，既可以作为路由器也可以作为终端设备；如果为RFD设备，不具有路由功能，只进行数据的收发。

Depth：邻居节点的深度。

3.2 改进算法描述

算法分3步，具体方法如下：

1）搜索目的子节点

图3 改进Cluster-Tree路由算法流程图

当一个节点接收到一个数据帧时，首先根据式(4)检查目的地址D是否是它的一个后代节点,如果 D 是后代节点,沿着Cluster-tree型结构将该数据帧转发到相应的子节点,如果D不是后代节点,转向步骤(2) 。

2）搜索邻居表

如果D与邻居表表项中的AddNb相等，则直接发送给邻居节点；如果D与邻居表表项中的AddNb不相等，则看Type类型，只有当Type=“FFD”时，再利用式(4)检查目的地址D是否是该邻居节点的一个后代节点,如果D是其后代节点,将该数据帧转发到该邻居节点,如果D不是其后代节点,转向步骤(3) 。

3）搜索下一条子节点

如果A < D < A + Cskip(d-1)，则下一跳地址为

4）搜索祖先节点

不满足(1)-(3)条件时，将数据帧发送给当前节点的父节点。

5）重复(1)-(4)步骤

具体流程如图3所示。

4 算法的仿真和分析

仿真工具采用OMNET++4.1。网络覆盖面积为500*500m，网络节点数目为30，网络延迟为0，误码率为0，参照图1网络拓扑，设置Cm=6，Rm=4，Lm=4。为了简化，ZC初始能量为30000J,，其他节点能量初始为20000J。仿真时间为60S。

通过仿真实验，对改进算法和传统Cluster-tree路由算法进行比较，重点比较了节点能耗和平均跳数。

4.1 节点能耗比较

图4中红色表示ZC节点，其他的为FFD节点，横坐标为时间，单位为秒，纵坐标为能量，单位为J。从图中可以看出，改进Cluster-Tree路由算法中，ZC节点变化比较缓慢，仿真时间结束时剩余能量比Cluster-Tree路由算法多很多。其他的FFD节点，只有蓝色和绿色代表的FFD节点能耗比原Cluster-Tree路由算法快，其它的FFD节点能耗都有所减少。

图4 Cluster-Tree路由算法改进前后节点能耗变化趋势对比图

从整体上看，改进的Cluster-Tree路由算法整体能耗要小于原Cluster-Tree路由算法。

4.2 节点跳数比较

图5 Cluster-Tree路由算法改进前后节点跳数变化趋势对比图

图5中线段的端点处表示此时RFD发送的信息已经到达目的地，横坐标表示时间，单位为S，纵坐标为跳数。从图中可以看出，图5(b)6跳个数约为15，图5(a)6跳个数约为20；图5(b)2跳个数约为16，图5(a)2跳个数约为15；图5(b)3跳个数为28，图5(a)3跳个数为11；图5(b)4跳个数约为18，图5(a)4跳个数约为29；图5(b)5跳个数约为36，图5(a)5跳个数约为39。

从整体上看，改进的Cluster-Tree路由算法节点跳数要小于原Cluster-Tree路由算法。

综合(1)(2)比较分析证实：改进的Cluster-Tree路由算法在减少路由跳数得同时节约了整体能量。

5 结论

针对Cluster-Tree路由算法存在的一跳节点可能需要多跳到达问题，将邻居表引入进Cluster-Tree路由算法中，经仿真实验证明，改进的Cluster-Tree路由算法可以根据邻居表有效的优化路由，同时降低网络整体能量消耗，特别是ZC的能量消耗，最终提高网络的效率，延长网络的存活时间。

[1] 贺玲玲.Z igBee传感网络Cluster-T ree改进路由算法研究[J].传感技术学报,2010,23(9):1303-1307.

[2] ZigBee Alliance.ZigBee specification 2008[ DB/OL].[2008.01.27]. http://www.zigbee.org .

[3] Suzuki,N.;Mitani,T.;Shinohara,N..Study and Development of a microwave power receiving system for ZigBee device[J].Asia-P acific Microwave ConferenceProceedings,APMC2010:45-48.

[4] Khan,S.A.;Khan,F.A..Performance analysis of a ZigBee beacon enabled cluster-tree network[J].Third International Conference on Electrical Engineering,ICEE 2009:1-6.

[5] Dilum Bandara,H.;Jayasumana,A.P..An enhanced top-down cluster and cluster-tree formation algorithm for Wireless Sensor Networks[J].International Conference on Industrial and Information Systems,ICIIS 2007:565-570.

[6] 班艳丽,柴乔林,王芳.改进的ZigBee 网络路由算法[J].计算机工程与应用, 2009,45(5):95-97,116.

[7] 朱向庆,王建明.Z igBee协议网络层的研究与实现[J].电子技术应用,2006,32(1):137-140.

[8] 孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社, 2005.