武汉工程大学 毕业设计（论文）
之前必须先解除本身的所有子节点和自己的关联。
图3.4 一个节点加入当前网络和脱离当前网络的过程
3.2 ZigBee路由协议分析
设计无线网络的路由算法首要目标就是充分高效的利用现有的网络带宽并在此基础上尽可能的提高网络数据传输的服务质量(QOS)，而 ZigBee 网络相比与其它无线网络来说有其自身的特点。比如 ZigBee 网络中传输数据的速率一般较低，而且节点的能量有限，这就要求ZigBee 路由算法能够有效的利用节点能量来进行数据传输，此外由于节点功能和存储空间有限，节点无法通过获得整个网络的信息后来进行路由选择，只能获取到局部的网络信息，所以 ZigBee 路由算法需要在知道局部网络信息的基础上来选择最优的路由来进行数据传输。在ZigBee 网络中，节点按功能分为协调器、路由器和终端节点。这些节点在网络中充当不同的角色，如终端节点就无法充当路由器的角色，只能进行简单的数据收发工作，所以传统的无线传感器网络所应用的路由协议无法应用与 ZigBee 网络中。
ZigBee 路由协议是指 ZigBee 规范中定义的与路由相关的算法和功能部分，针对不同的ZigBee 网络拓扑结构有与之相适应的路由算法。为了实现低成本、可靠性高、低能耗等设计目标，应用最广泛的 ZigBee 网状网络中采用了树路由(Cluster-Tree)和无线自组织按需距离矢量(Ad-hoc On-Demand Distance Vector Routing，AODV)相结合的混合路由算法，结合了树路由算法和 AODV算法各自的优点。这里的 AODV算法与无线自组织网络中广泛应用的 AODV算法不完全一样，而是对传统 AODV 算法的改进算法，后面部分章节对这种路由算法我们称之为 AODVjr(AODV Junior)。
3.3. Cluster-Tree路由算法
在树型结构网络中，每个父节点都必须是全功能设备节点，精简功能设备节点只能作为父节点的子节点，节点按照父子关系使用树路由算法选择路径，当一个节点收到数据分组后发现目的节点并不是自己，就只能将该数据分组转发给它的子节点或者父节
- 12 -
武汉工程大学 毕业设计（论文）
点。在介绍树路
由算法之前，有必要先介绍 ZigBee 网络的地址分配机制，因为树路由算法的原理就来源于网络地址的分配机制。
3.3.1Cluster-Tree路由算法机制
在树路由算法中，路由通常分为上行路由或下行路由，如果目的节点是自己的后代，则为下行路由，否则就是上行路由。收到分组的节点是根据分组的目的地址来判断分组的下一跳的。假设一个 ZigBee 路由节点的网络地址是 A，网络深度为 d，且此节点接收到一个目的地址为 D 的分组，如果下面的不等式成立，则目的节点就是此节点的一个后代节点：
（3.1）
如果分组的目的节点就是此节点的一个后代节点，那么该分组就将被此节点转发给它的一个子节点，此时若下式成立：
（3.2）
则目的节点是接收节点的一个终端子节点，此时下一跳节点的地址 N 为：
（3.3）
否则
如果目的节点并不是接收节点的一个后代节点，则该分组将被转发给它的父节点，树路由算法相对简单，不需要存储路由表，属于静态路由，树路由算法只需根据简单的计算就能确定下一跳的节点地址，而且不需要为了建立维护路由所增加的额外的开销，但是对于每一个传输的分组都要经过这样的计算确定下一跳的地址，传输效率明显低下，所以为了提高传输效率，在 ZigBee 网络中具有路由功能的节点使用 AODVjr 去建立路由，也就是具有路由功能的节点可以按照建立好的路由将分组直接传输给下一跳节点，而不具有路由功能的节点就仍然按照树路由算法去计算下一跳节点地址然后转发分组和为了建立与维护路由而发送的控制分组。
3.4 AODvj算法
3.4.1 AODV算法原理
当前的zigBee网状网络采用Ad Hoc中按需矢量路由算法AoDv,AODV算法是由Nokia研究中心的CharlesE.PerkinS和加利福尼亚大学SantaBarbara的Eliz的ethM.Belding-Royer以及eineinnati大学的samirR.Das等共同开发,是在传统的按需
- 13 -
武汉工程大学 毕业设计（论文）
路由算法DSR和DSDV上发展而来的,采用动态路由发现!维护机制和目的序列,以DsDV为基础,结合DsR中的按需路由思想并加以改进。
在AODV算法中,有三种控制分组:路由请求(RREQ)、路由应答(RREP)和路由错误(RRER),Hello消息是特殊的RRER分组。当源节点需要与其他节点通信但路由表中没有到该节点的路由时,它就通过向所有的邻居节点广播一个RREQ分组,各邻居节点采用泛洪(Flood)的方式在网络中传播RREQ。当中间其他节点收到这个RREQ时,首先判断是否收到过具有相同源节点和目的节点的RREQ,如果是,则丢弃;如果不是,就利用RREQ创建一个表项,但先不分配有效序列号,只用于记录一个临时的到达源节点的反向路径,目的是使RREP分组能够返回源节点,并且中间节点每转发一次RREQ就将跳数(Hop)加1。如果
中间节点含有到目的节点的路由,就按RREQ经过的路径反向发送RREP给源节点,否则继续广播该RREQ\当目的节点收到RREQ时,同样建立反向路由,然后目的节点也沿着RREQ经过的路径给源节点发送RREP,收到RREP的节点建立到目的节点的正向路径,这样源节点就可以根据收到的RREP信息获得到目的节点的路由并利用该路由向目的节点发送数据\当源节点移动时,它会重新发起路由发现算法;如果中间节点移动时,那么与其相邻的节点会发现链路失效并向其上游节点发送RRER并一直传到源节点,而后源节点根据情况重新发起路由发现过程。下图是AODV算法数据传输过程的一个示例图。
图中节点1向节点H发数据,但本身没有到达n节点的路由,并假设中间所有节点都没有到达11节点的路由。此时节点1广播RREQ(图a),中间节点收到这个RREQ后将继续广播此RREQ分组并建立反向路径,并且在各自的路由表中添加源节点地址、下一跳节点地址和跳数信息(图b/c/d),直到此RREQ分组到达目的节点11,收到RREQ后,目的节点n将沿着反向路径向源节点回复RREP,并所有在反向路径上的节点的路由表中添加目的节点地址、下一跳节点地址和跳数信息。在路径选择时,通过路由表中的跳数大小来选择跳数最少的那条路径,如在图中,节点3、6、9中路由表保存的信息有几种可能,这种情况下对这几种信息中的跳数进行比较并选择跳数最少的那条信息,即图中的(1,6,3),这样就确定了路径,此时节点1就可以把数据沿着刚刁-确定的路径发给节点11。
- 14 -
武汉工程大学 毕业设计（论文）
假如中间节点(比如节点6)有到节点11的路由信息,那么节点6将直接回复RREP给源节点,并把节点11的信息附加到路由表中\假如在数据传输当中,发生了路径中断，如下图。
图中,6->9链路中断(图a),则节点6产生RRER消息一直传递给节点1告知路由不可达到(图b),这时候节点1将重新发起路由过程,找一条新的路径发送数据(图c):
其路由维护过程为:节点通过MAC层会周期性的广播Hello消息来判断链路的状态,如果该节点连续3次没有收到Hello消息,则认为链路已经断开,这种情况下,链路的上游节点将删除该链路的路由信息并发送一个RERR,通知相邻节点和相应的上游节点删除所有因链路断开而导致目的节点不可达的路由信息。每个节点都保留了一个先驱列表(PrecursorList)来帮助完成RRER的功能,这个列表保存了把自己作为当前不可达节点的下一跳的相邻节点。如果源节点想重建到目的节点的路由,则会发送一个带有大于先前序列号(SequeniNtlmber)的目的地序列号的RREQ\另外,与活动路由无关的节点移动或者断路时,并不影响源节点到目的节点的路由。
3.4.2改进AoDv的AODvjr路由算法
在AODVjr算法中,继续采用AoDv算法的路由发现一般机制,主要是对AODV算法以下问题的一些改进： 1) 简化路由发现过程
- 15 -
武汉工程大学 毕业设计（论文）
在AODVjr算法中,只允许目的节点回复RREP,即使中间节点有到目的节点的路由时,也不回复RREP,从而减少了控制开销。
下图是两种算法路由发现过程比较图。源节点1和目的节点5进行通信,假如中间节点3有节点5的路由信息,那么对于AODV算法来说,节点3将直接回复RREP,而对于AODvjr算法来说,只有目的节点才能回复RREP,因此即使节点3包含节点5的路由信息也不能回复RREP,从而简化了路由发现过程,也在一定程度上减少了控制开销。
2) 路由维护
AODVjr算法采用端对端(源节点泪的节点)策略,删除了Hell\消息、RRER和节点序列号机制\如果数据传输是单向的,那么目的节点会周期性的向源节点发出确认连接消息(ACK)来维护其反向路径,源节点将根据这个ACK消息判断链路是否发生中断。当源节点在一定时间内没有收到ACK消息,就认为链路发生中断,此时将放弃原来的路径并重新寻找另外一跳路径完成通信。如果数据传输是双向的,就不需要额外的附加消息了,直接根据收到的数据来判断。这样不仅可以提高算法的效率(特别是在网络负载!带宽不足的情况下),并且很大程度上节省了控制开销。而AODV算法会定期发送Hello消息来检测本地链路的连接状态,当发生链路中断时,将产生一个RRER通知所有受影响的源节点,虽然这样做能够及时发现路由变化并进行维护,保证活动路径上邻节点之间连通的有效性,但实际上这是用增加算法的维护开销来换取时延的降低,必然引起了大量的控制开销。下图是两种算法路由维护比较。
- 16 -