ZigBee网络Cluster-Tree优化路由算法研究

摘要：通过分析ZigBee协议中Cluster-Tree和AODVjr算法的优缺点，提出一种基于Cluster-Tree+AODVjr的优化路由算法。该算法利用ZigB ee协议中的邻居表，通过定义分区来确定目的节点的范围，从而控制广播RREQ分组的跳数，防止无效的RREQ泛洪。此优化算法能够有效地减小路由跳数，缩短传输时延，减少网络中死亡节点的数量，提高数据传送的成功率。
关键词：ZigBee；路由算法；Cluster-Ttee+AODVjr；邻居表；分组

引言
无线通信和嵌入式微传感器技术的快速发展促进了无线传感器网络的崛起。ZigBee协议基于IEEE 802．15．4无线标准制定，包括应用层、网络层、安全层等，实现了网络的自组织和自维护的功能。在无线传感器网络中，节点的能量是有限的，如果节点在最后因为自身的能量消耗殆尽而死亡，将会对整个网络的传输性能造成很大影响。因此，在实际应用中，根据不同的网络情况来选择最符合应用需求的路由协议，让路由协议根据网络拓扑选择合适的路径，平均分布节点的传输能量，降低网络的功耗是网络层必须要考虑的任务。

1 ZigBee路由算法研究
依据设备的能力，ZigBee网络中的设备可以分为全功能设备(Full Function Device，FFD)和半功能设备(Reduced Function Device，RFD)。FFD能转发其他设备的数据帧，RFD则不能。当FFD加入一个网络时，它可以作为协调器。协调器会周期性地广播数据帧，周围的RFD能够发现并加入网络，形成一个星型拓扑网络。在星型拓扑中，协调器负责控制整个网络，所有终端设备都直接与协调器通信，并且由它维护。
ZigBee网络层还支持树型和网状网络。树型网络采用分级路由的策略在网络中传送数据和控制信息，而网状网络则可以进行点对点的通信。在树型网络中，根节点(协调器节点)和所有的内部节点(路由器节点)是FFD，而RFD只能作为叶子节点(终端节点)。当协调器或路由器加入网络时，它必须被分配唯一的网络地址。
1．1 网络地址分配
ZigBee协议规范使用一个分布式地址方案分配网络地址，它设计为给每个潜在父节点提供一个有限的网络地址子块。当一个设备成功加入网络后，其父节点给该节点自动分配一个唯一的网络地址。
1．2 ZigBee路由算法
网络层支持Cluster-Tree、AODVjr和Cluster-Tree+AODVjr算法(以下简称C+A算法)等多种路由算法，因此ZigBee网络的路由协议兼具树型网络和网状网络的特性。
1．2．1 Cluster-Tree算法
树路由机制是根据网络地址和节点间的父子关系来实现路由的。如果目的地址设备不是该路由器的子孙，则直接将数据帧转发给该路由器的父节点，其父节点将按照同样的步骤进行路由。
1．2．2 AODVjr算法
AODVjr是对AODV算法的一种简化改进，当源节点要寻找到达目的节点的路径时，先向其邻居节点组播RREQ分组。收到该分组的邻居节点若具备路由能力，则建立指向源节点的反向路由回复，同时继续向自己的邻居节点组播该RREQ分组。若不具备路由能力，则通过Cluster-Tree路由算法将该分组交由其子孙节点或父节点进行转发。当目的节点接收到此RREQ分组后，通过单播的方式向源节点回复RREP分组，同时，所有接收到此RREP分组的节点都将更新记录自己的邻居表，路由建立成功。实验证明，AODVjr算法在保持了AODV原始功能的基础上，控制开销比AODV算法更小，因此更节能。
1．2．3 Cluster-Tree+AODVjr算法
在此算法中，网络中的节点被分成了4类：Coordinator、RN+、RN-和RFD。其中RN+具有足够的存储空间和能力来进行AODVjr协议；而RN-则因存储空间受限，不能够进行AODVjr协议。Coordinator、RN+、RN-都具有路由功能，在通信时，如果目的节点不是邻居节点，RN+将会启动AODVjr，主动查找到达目地节点的最佳路径；RN-节点只能通过树路由算法来寻找下一跳的节点。仿真证明，采用Cluster-Tree和AODVjr相结合的路由协议在保证分组递交率的情况下，具有比单独使用其中一种路由协议更低的控制开销和平均时延。

2 优化ZigBee路由算法
2．1 ZigBee路由算法问题
Cluster-Tree算法必须按照簇树型结构地址分配方式来寻址，路由效率低，并且源节点到目的节点的传输路径由于跳数过多，会影响网络时延。
AODVjr算法在路由发现过程中，会产生分组大量泛洪问题。例如，当目的节点是源节点的子节点时，若采用AODVjr向邻居节点发送RREQ分组，则向其父节点以上的节点发送RREQ分组是多余的；若目的节点不是源节点的子节点，则采用AODVjr向其子节点方向发送RREQ分组是多余的。假设网络的最大深度是1，则数据帧可能被转发的最长路径是21，因此当跳数大于21时，就应停止对RREQ分组的继续广播，将其丢弃；假设从源节点到目的节点的最小跳数为M，当RREQ分组被转发的次数大于M时，再继续转发是多余的。由于每一次AODVjr路由都要产生大量的RREQ泛洪，因此会使节点能量消耗严重。
鉴于以上问题，本文提出一种基于C+A算法的优化路由算法，用以解决Cluster-Tree路由的低效率和AODVjr路由的泛洪严重及能量消耗问题。
2．2 优化路由算法思想
在一个传感器网络中，传感节点只能和与它相邻的，并且在它的射频传输范围之内的节点直接通信。树型网络中每个节点的邻居表中都包含有其射频覆盖范围内各个邻居节点的相关信息。在优化路由算法中利用邻居表中记录的有效信息，可以使源节点发送给目的节点的数据帧经过一跳到达。
在AODVjr路由发现过程中，为了避免RREQ分组无选择性的大量泛洪，在优化路由算法中依据不同的情况，添加对RREQ分组广播跳数的限制条件，使大于限制条件的多余路由不能启用。这样能有效地减少RREQ分组泛洪次数，缩小RREQ广播范围，限制RREQ分组传播方向，从而降低网络的能量消耗。
2．3 优化路由算法设计
优化路由算法的具体步骤如下：
①对树型网络进行分区，并设定辅助变量number的初始值为1(number值代表分区次数)。分区原则如下：以协调器为根节点，将根节点的每一个子树看作一个区域，并为其编号。记录每一个区域中的最大地址Amax和最小地址Amin。由树地址分配机制可以得出，在同一区域中的节点地址An均满足Amin≤An≤Amax，即此区域的地址范围是[Amin，Amax]，并且每一个区域的地址范围之间是不相交关系，即一个确定的地址在且仅在一个区域内。
②判断源节点的类型。若为RFD则直接将数据帧转发给其父节点；若为FFD则判断目的节点是否为源节点的子节点。若是，则向下启动AODVjr路由转发数据帧，并将RREQ分组的最大广播跳数限制为|Dd-Ds|(Ds为源节点的网络深度，Dd为目的节点的网络深度)，超出范围则丢弃；若不是，则进行第下一步。
③源节点向邻居节点发送RREQ分组，邻居节点判断自身地址是否与目的地址相等。如果相等，则向上层传递，由其上层对数据帧进行解析，并将RREQ分组的最大广播跳数限制为1，超出范围则丢弃。如果不等，则进行第④步。
④判断目的地址在哪个区域中。若目的节点和源节点在同一区域中，进行第⑥步；若不在同一区域中，则进行第⑤步。
⑤判断源节点的邻居节点中是否有和目的节点在同一区域的节点。如果有，将数据帧转发给该节点，并进行第⑥步；如果没有，则进行第⑦步。
⑥number值加1。将目的节点所在区域看作一个树型网络，将其最小地址节点看作该树的根节点，并按照第①步的分区原则将其进行分区。判断目的节点和当前节点是否在同一区域中。若是，重复第⑥步；若不是，则进行第⑦步。
⑦将数据帧经由树路由转发到第number次分组的根节点，然后启动AODVjr路由，由此根节点将RREQ分组广播至目的节点的相应分组内，寻找目的节点，并将RREQ分组的最大广播跳数限制为|Dd-number+1|，超出范围则丢弃。