ZigBee是基于IEEE802.15.4标准的低功耗个域网协议.根据这个协议规定的技术是一种短距离、低功耗的无线通信技术^[1].由于ZigBee具有低速率、低成本、低功耗等一些特点，近几年在智能家居、智能交通、医疗以及工业自动化等方面都具有广泛应用^[2~3].

虽然ZigBee作为一种低功耗的无线通信技术，但是ZigBee节点是由电池供电的，能量十分有限^[4-6].所以，降低能量消耗成为设计ZigBee路由算法的主要目标之一.ZigBee协议采用Cluster-Tree^[7]和AODVjr^[8]的混合路由算法——ZBR算法^[9]，该算法通过不具有路由功能的节点采用Cluster-Tree算法，而具有路由功能的节点采用AODVjr算法来实现整个网络的通信，但ZBR算法几乎没有通过平衡二者来降低网络能耗.Cluster-Tree算法可以使不具有路由功能的节点通过与各自的父节点通信，最后实现数据的转发，但缺点是效率不高.为了提高效率，ZigBee中允许具有路由功能的节点使用AODVjr算法去发现路由，但是会造成大量的能量消耗.因此，本文提出了一种结合AODVjr和Cluster-Tree优点的分簇路由算法——ACZBR算法，通过分簇的算法平衡二者，以降低AODVjr算法的能耗，从而延长网络生存时间.分簇算法也被认为是比较符合传感器网络特性的高效算法，有关分簇的算法也有不少论述^[10-14].

1 ZigBee协议路由算法 1.1 ZigBee协议简介

ZigBee网络中节点可以分为3种类型：ZigBee协调器节点(ZC)、ZigBee路由器节点(ZR)和ZigBee终端设备节点(ZED).ZC的主要功能是建立和维护整个网络，并且具有存储容量大、计算能力强的特点.ZR主要起路由的作用，能够转发其他节点的数据，可以与其他设备互联.ZED一般作为边缘设备，只能与上一级节点通信.其中ZC和ZR属于全功能设备(FFD)，ZED属于简化功能设备(RFD).FFD可以直接和FFD、RFD通信，RFD只能将信息发送给上一级的FFD或者从上一级的FFD接收信息.每个ZigBee网络中只能有1个ZC，用于管理和控制其他节点加入该网络.

ZigBee网络中的所有节点都有两个地址：1个16位网络地址和一个64位IEEE扩展地址.其中16位网络地址仅在网络内部使用，用于路由机制和数据传输.这个地址是在节点加入网络时由其父节点动态分配的.其具体分配机制如下.

(1) 首先协调器规定3个参数C_m(最大子节点数)、L_m(网络最大深度)、R_m(子节点中最大路由节点数)，计算网络深度为d的偏移量Cskip(d)，具体如式(1)所示.

$ {\rm{Cskip}}\left( \mathit{d} \right){\rm{ = }}\left\{ {\begin{array}{*{20}{c}} {{\rm{1 + }}{\mathit{C}_\mathit{m}}{\rm{(}}{\mathit{L}_\mathit{m}}{\rm{ - }}\mathit{d}{\rm{ - 1)}}}&{{\mathit{R}_\mathit{m}}{\rm{ = 1, }}}\\ {\frac{{{\rm{1 + }}{\mathit{C}_\mathit{m}}{\rm{ - }}{\mathit{R}_\mathit{m}}{\rm{ - }}{\mathit{C}_\mathit{m}}\mathit{R}_\mathit{m}^{{\mathit{L}_\mathit{m}}{\rm{ - }}\mathit{d}{\rm{ - 1}}}}}{{{\rm{1 - }}{\mathit{R}_\mathit{m}}}}}&{{\rm{其他}}{\rm{.}}} \end{array}} \right. $

(1)

(2) ZC将自身地址设置为0，网络深度设置为0.

(3) 假如子节点类型为ZR，则分配的地址如式(2)所示.

$ {\mathit{A}_\mathit{i}}{\rm{ = }}{\mathit{A}_\mathit{p}}{\rm{ + Cskip}}\left( \mathit{d} \right)\left( {\mathit{i}{\rm{ - 1}}} \right){\rm{ + 1, }} $

(2)

其中A_p表示父节点地址，i表示第i个ZR加入该父节点.

(4) 假如子节点类型为ZED，则分配的地址如式(3)所示.

$ {\mathit{A}_\mathit{j}}{\rm{ = }}{\mathit{A}_\mathit{p}}{\rm{ + Cskip}}\left( \mathit{d} \right){\mathit{R}_\mathit{m}}{\rm{ + }}\mathit{j}{\rm{, }} $

(3)

其中A_p表示父节点地址，j表示第j个ZED加入该父节点.

1.2 Cluster-Tree路由算法

Cluster-Tree路由算法的描述如下.当一个网络地址为A，网络深度为d的路由节点(FFD)收到目的地址为D的转发数据包时，路由节点首先要判断目的地址D是否为自身的一个子节点.若地址D满足式(4)，则可以判断D地址节点是A地址节点的子节点，反之，则不是A地址节点的子节点.

$ \mathit{A < D < A}{\rm{ + }}{\rm{Cskip}}\left( {\mathit{d}{\rm{ - 1}}} \right){\rm{.}} $

(4)

判断后采取的数据包转发措施如下：

(1) 目的节点是自身的子节点，则直接把数据包转发给对应的子节点.

(2) 目的节点不是自身子节点，则把该数据包转发给自身的父节点去处理.

1.3 AODVjr路由算法

AODVjr作为一种按需路由协议，只有当ZR接收到数据包，并且节点的路由表没有该数据包的目的地址时，才会进行路由发现过程.一次完整的路由建立由以下3个过程组成.

(1) 路由发现.只有具有路由能力的节点才能发起路由请求分组(RREQ)，当接收到一个数据包，并且数据包的目的地址不在路由表中时，该节点就会创建一个路由请求分组(RREQ)，并使用广播的方式向周围节点进行广播.

(2) 反向路由的建立.当RREQ分组从一个源节点转发到不同的节点时，沿途所经过的节点都要自动建立到源节点的反向路由.当RREQ分组最终到达了目的节点，节点验证RREQ中的目的地址为自身的地址后，目的节点就会产生路由回复分组(RREP)，作为对RREQ分组的应答.

(3) 正向路由的建立.RREP以单播方式转发回源节点，沿着这条路径上的每一个节点都会根据RREP分组建立到目的节点的路由.至此，一次完整的路由建立完毕.源节点与目的节点之间可以开始数据传输.

2 ACZBR路由算法

针对ZBR路由算法没有很好地结合AODVjr与Cluster-Tree优点的问题，文献[15]提出了一种改进的CLZBR算法.CLZBR是把子节点最多的节点做为新簇的簇首.然而，在网络形成阶段子节点数目是不可知的.因此，CLZBR只能在网络完全建立之后才能进行分簇，具有一定的局限性.因此，本文提出了ACZBR路由算法，该算法在网络形成时便可以决定簇的结构.并且，簇内普通节点不转发RREQ，减少了冗余RREQ的产生，从而减少了能量消耗，簇间使用AODVjr算法，使之可以建立比Cluster-Tree算法更短的路由路径，采用这种结合的方式，即保证了效率，又考虑了能量消耗.同时，采用自适应更换簇首的策略，避免了簇首过度消耗能量，从而延长网络生存时间.

2.1 ACZBR算法理论基础

ACZBR算法将ZigBee网络分为很多个逻辑簇，在簇内使用Cluster-Tree算法，在簇间使用AODVjr算法.节点分为3种类型：簇首节点(CH)、网关节点(GW)以及簇普通节点(CM).只有具有路由能力的节点才能形成簇，并成为簇首.终端节点只能成为CM.该算法用Cluster_Info结构体来描述节点的簇信息，其主要包括以下属性：节点剩余能量、节点类型、节点所属簇号、网关信息.其中只有节点类型为GW时，网关信息才有效，网关信息记录了该网关所能通信的簇号.

分簇的目的是为了减少冗余RREQ的产生，而AODVjr算法中具有路由能力的邻居节点收到不存在路由发现表中的RREQ都要进行转发，因此每个路由节点都要转发一次RREQ和接收到很多次RREQ.一个路由节点可能作为许多节点的邻居节点(假设为N)，因此会收到N个RREQ，而这N个RREQ中，最多则有N-1个冗余的RREQ.正是由于邻居节点都需要转发RREQ，所以导致AODVjr浪费了一些能量.ACZBR算法则通过在一跳范围内建立逻辑簇，所有的簇成员同时也是簇首的邻居节点，通过对簇内成员对于转发RREQ的限制，从而减少了冗余RREQ.簇内只有簇首可以以广播的方式转发RREQ，簇内普通节点不具有转发RREQ的能力.同时，为了在簇间能进行RREQ的转发，定义了网关节点(GW)，只有在多个CH的一跳范围内的节点才可以成为GW，GW可以把RREQ转发给CH.通过CH、GW、CM 3种方式对网络节点的逻辑区分，以达到减少RREQ的目的.

ACZBR通过减少冗余RREQ，并综合考虑网络节点剩余能量，以此提高网络能量利用率且延长网络寿命.

节点发送数据包时能量消耗公式^[16-17]为

$ {\mathit{E}_\mathit{T}}\left( \mathit{b} \right){\rm{ = }}\mathit{b}{\mathit{E}_\mathit{\varepsilon }}{\rm{ + }}\mathit{b}{\mathit{\varepsilon }_\mathit{m}}{\mathit{d}^\mathit{\alpha }}{\rm{, }} $

(5)

其中，b表示传输的数据比特数；d表示通信半径；E_e是节点接收或者发送传输数据电路的单位消耗；ε_m是发送传输数据的电路单位消耗；E_T(b)是节点转发b比特数据能耗值.节点接收数据包时能量消耗公式为

$ {\mathit{E}_\mathit{R}}\left( \mathit{b} \right){\rm{ = }}\mathit{b}{\mathit{E}_\mathit{\varepsilon }}{\rm{, }} $

(6)

其中，b与E_e分别表示传输数据的比特数和电路的单位消耗；E_R是节点接收b比特数据的能耗值.

节点剩余能量公式为

$ {\mathit{E}_{{\rm{power}}}}{\rm{ = }}{\mathit{E}_{\rm{0}}}{\rm{ - }}{\mathit{E}_\mathit{T}}\mathit{n}{\rm{ - }}{\mathit{E}_\mathit{R}}\mathit{m}{\rm{, }} $

(7)

其中，E₀表示节点初始能量；n表示节点转发数据的次数；m表示节点接收数据的次数.

现分别分析AODVjr和ACZBR进行一次路由发现过程所消耗的能量.

假设网络中路由节点的数目为N，进行分簇后，CH、GW、CM类型节点的数目分别为N_ch、N_gw、N_cm，其中N=N_ch+N_gw+N_cm.

AODVjr消耗的能量为

$ {\mathit{E}_{{\rm{AODVjr}}}}{\rm{ = }}\left( {\mathit{N}{\rm{ - 1 + }}\mathit{p}} \right){\mathit{E}_{\rm{T}}}{\rm{ + }}\mathit{j}{\mathit{E}_{\rm{R}}}{\rm{, }} $

(8)

ACZBR消耗的能量为

$ {\mathit{E}_{{\rm{ZBRpro}}}}{\rm{ = }}\left( {{\mathit{N}_{{\rm{ch}}}}{\rm{ + }}{\mathit{N}_{{\rm{gw}}}}{\rm{ - 1 + }}\mathit{q}} \right){\mathit{E}_{\rm{T}}}{\rm{ + }}\mathit{k}{\mathit{E}_{\rm{R}}}{\rm{, }} $

(9)

其中，j、k表示接收的数据包数目且j＞k；p，q表示路由回复所经过的节点数且p≤q.

路由建立后，ACZBR比AODVjr所多耗费的能量为：(p-q)E_T，而(E_ACZBR-E_AODVjr)是远大于(p-q)E_T的.所以，ACZBR比AODVjr更节省能量.

当簇内成员过多时，会导致簇首任务过重.而簇内成员过少时，又会影响分簇的效率.因此需要平衡簇内成员的数目.ACZBR以协调器规定的最大子节点数为平衡点，当簇内成员小于最大子节点数时，加大该簇首的权重；反之，则减小该簇首的权重.

簇首权重公式为

$ \mathit{\rho }{\rm{ = }}\mathit{a}{\mathit{E}_{{\rm{power}}}}{\rm{ + }}\mathit{b}\frac{{{\mathit{C}_{\rm{m}}}{\rm{ - }}{\mathit{N}_{\rm{c}}}}}{\mathit{d}}{\rm{ , }} $

(10)

其中，a、b表示平衡系数；d表示节点深度；C_m表示规定的最大子节点数；N_c表示当前簇内成员数.

2.2 自适应簇的建立

ZigBee节点在加入一个网络之前首先要发送信标请求(Beacon Request)，收到此信标请求并且已经加入网络的节点会回复请求节点一个信标回复(Beacon Reply)，此算法把Cluster_Info加入到信标回复帧，用来实现在加入网络时选择合适的簇加入.簇的形成分为以下步骤：

(1) 协调器首先建立网络，形成第一个逻辑簇并成为簇首，并设置自身的Cluster_Info.其中，把节点类型设置为CH.

(2) 路由节点收到信标回复后，根据信标中每个节点的节点类型和节点剩余能量做出以下选择：

①信标中没有簇首节点：则自身成为簇首节点，把节点类型设置为CH.通知父节点设置节点类型为GW，以此保证相邻簇间有网关负责簇间通信.②只有一个簇首节点：加入该簇，把节点类型设置为CM.③有多个簇首节点：选择簇首权重最大的簇加入，把节点类型设置为CM.如果没有网关或者网关节点的网关信息不包含对应的簇首节点，则此节点成为网关，把节点类型设置为GW.

(3) 终端节点收到信标回复后，如果有簇首节点，则加入簇首权重最大的簇，否则加入父节点所在的簇, 并且节点类型设置为CM.

至此，在所有节点加入到网络时，节点也加入到合适的逻辑簇.下面结合图 1详述整个过程.其中，节点加入网络的顺序按字母顺序，即A先加入网络，I最后加入网络.

Step1：协调器ZC建立网络，并成为一个簇首.即步骤(1).

Step2：A、B、C加入ZC簇.设置节点类型为CM.即步骤(2)②.

Step3：D、E自己成为簇首，通知B、C成为网关.设置节点类型为CH.即步骤(2)①.

Step4：F加入ZC或E所在的簇，由于存在网关，设置节点类型为CM.即步骤(2)③.

Step5：I为ZED节点，因此加入父节点所在的簇.即步骤(3).

当网络运行了一段时间后，由于簇内成员都只通过簇首转发数据，造成了簇首能量的过快消耗.为了避免簇首节点过早成为死亡节点，ACZBR算法采用了一种自适应的簇首更换策略.其主要步骤如下：

(1) 当簇首节点剩余能量为初始能量的30%(可以自行定义)以下时，此节点通知簇内成员簇首失效信息，并加入到其他有效簇，把节点类型设置为CM.

(2) 簇内成员收到簇首失效信息后，重新请求邻居簇信息，当收到新的簇信息后，执行簇的形成步骤(2)、(3).

2.3 数据包的传输

ZigBee网络中存在大量路由节点，因此在路由发现的过程中会产生大量RREQ分组冗余.ACZBR算法通过定义一些规则，避免了大量的RREQ分组.定义的规则如下.

(1) 只有簇首节点才能转发RREQ分组.

(2) 网关只转发来自簇首的分组.

(3) 簇成员转发的数据终点不是邻居节点时，必须先转发给簇首节点.

通过以上规则，结合图 2、图 3、图 4，对ACZBR算法的数据帧传输进行详细叙述：

(1) 数据包的终点为此节点，接受该数据包.

(2) 数据包的终点为此节点的邻居节点，转发数据包给邻居节点.

(3) 此节点为簇成员，转发数据包给簇首.

(4) 簇首收到数据包后，首先查看路由表，若有终点路由表，则转发给此终点的下一跳地址，否则执行(5).

(5) 发起路由请求.

(6) 簇成员收到路由请求，则直接丢弃该请求；网关收到路由请求，则转发给所连接的簇首；簇首收到路由请求，若路由终点为自己或者为自己簇内成员，则回复该路由请求，否则转发该路由请求.

(7) 网关收到路由回复，建立路由表，继续回复该路由回复.若回复终点为自己簇内成员或自己时，更新路由表.转发数据包.如图 4所示.

3 仿真分析

为了有效地评价ACZBR算法的性能，本文在OPNET平台下进行了分析验证.通过仿真实验，对数据包的时延、丢包率、死亡节点数目、网络能量消耗与ZBR和CLZBR算法进行了对比.本文仿真参数设置如下：节点个数，49个；协调器位置，中心；网络范围，400 m×400 m；通信半径，40 m；节点初始能量，25J；仿真时间，500 s；数据包发送间隔，5 min.

3.1 ACZBR和CLZBR算法分簇对比

CLZBR算法中规定每个簇内最多只能有两个网关节点，并且每个簇的网络深度为3.这种分簇的思想容易导致网络深度大于3的节点不能加入到任何簇中，对于没有加入到任何簇的节点，数据包的传输只能使用Cluster-Tree算法，图 5表示的是同一节点在不同算法下发送数据包到协调器的时延，由于在CLZBR算法下不能加入到任何簇，而Cluster-Tree算法经过的节点数多于ZBR和ACZBR，使得数据包的平均时延比ZBR和ACZBR都大.

3.2 数据包时延

数据包时延描述的是一个数据包从源节点到目的节点的时间间隔.时延的大小是描述网络性能的重要参数之一.从图 6可以看到ACZBR算法比ZBR算法具有更小的时延，因为新算法采用分簇机制后，有效地减少了冗余RREQ的产生，因此可以更快地建立路由表，从而减少时延.CLZBR由于也采用了分簇的方法，在初期的时延也小于ZBR.但是CLZBR是基于层数的分簇思想，层数的高低与协调器的远近不具有一定的正比关系，并且CLZBR存在着不能加入簇的节点.因此，CLZBR的路径通常不是最短路径，导致后期的时延比ZBR略有增加.

3.3 丢包率

丢包率除了受链路质量的影响外，还受到网络的拥塞程度影响.由于非簇首节点不转发RREQ，降低了网络的拥塞程度，因此CLZBR和ACZBR在路由发现阶段都可以比ZBR具有更小的丢包率.在路由建立之后的数据包发送阶段，由于CLZBR路径所经过的节点数大于ZBR和ACZBR，所以CLZBR在数据包发送阶段的丢包率也略大.具体情况如图 7所示.

3.4 死亡节点数

在一定时间内，网络中死亡节点的数目越少，说明该网络具有更好的稳定性.从图 8的仿真结果可以看出，在相同的仿真时间内，CLZBR和ACZBR比ZBR的死亡节点数都更少.但是CLZBR采用的是固定备用簇首节点的策略，而备用节点在网络中的能量消耗具有不可预测性，可能导致当需要更换簇首时，备用簇首节点的能量也已经很低了，从而使第一个死亡节点发生的时间提前了.而ACZBR采用的是动态的更换簇首策略，只有当簇首能量低于一定阈值时，才根据式(10)选择合适的节点作为簇首，可以更有效地延迟第一个死亡节点出现的时间.

3.5 剩余能量

CLZBR和ACZBR都采用了分簇的思想，减少了大量冗余RREQ的产生，图 9可以看到ZBR在路由发现过程中，消耗了大量能量，而在数据包传输时，CLZBR由于大量节点所经过的跳数大于ZBR和ACZBR，所以，在数据包的传输阶段，CLZBR的能量消耗略有增加.

图 10表示的是当前网络所剩余的总能量，CLZBR虽然在数据包的传输过程中能量略有增加，但是相比较与ZBR还是更节省能量的，而ACZBR所剩余的能量最多，因此可以保证更长的网络生存时间.

4 结束语

ZigBee作为一种短距离、低功耗的无线网络协议，它有着广泛的应用前景.对ZigBee的研究，也可以促进物联网的发展.通过对ZigBee网络层路由协议的分析，本文提出了一种结合了AODVjr与Cluster-Tree优点的ACZBR算法，该算法在不增加时延的条件下，大大减少了RREQ的产生.同时，基于自适应更换簇首的思想，延长了网络生存时间.通过仿真结果可以看到，该算法对延长网络生存时间，减小丢包率等方面比CLZBR和ZBR算法都有提高.