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

，将其丢弃；假设从源节点到目的节点的最小跳数为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|，超出范围则丢弃。
目的节点接收到RREQ分组后，将向寻找路由的源节点回复一个RREP分组，其传送路径为路由建立过程的反向路由。所有接收到RREP分组的节点将此路由信息替换并且记录，正向路由从源节点到目标节点建立成功。优化路由算法的流程图如图1所示。

图1 优化路由算法的流程图

具体实现过程举例如下：假设一树型网络，网络参数Cm=4，Lm=4，Rm=3，依据前面的网络地址分配方式给网络中各节点分配相应地址，选定源节点为37，在其射频覆盖范围内的邻居节点是25、36和90。具体网络节点分布图如图2所示。

图2 树型网络节点分布图

首先将树型网络按照自定义的方式进行分区，分区后的网络如图3所示。其中，原树型网络被分为I、II、III、IV4个区域。

图3 第一次分区后的树型网络

树型网络的分区步骤如下：
①当目的节点是41时，直接转发，并将RREQ分组传播跳数限制为|4-3|=1。
②当目的节点是90时，由于90是源节点的邻居节点，直接将数据帧转发，并将RREQ分组传播跳数限制为1。
③当目的节点是8时，由于目的节点和源节点属于同一区域I，则number=number+1，即number=2。并且将区域I继续分区，第二次分区后的树型网络如图4所示。此时，节点8和节点37不属于同一区域，则将数据帧沿树路由转发给第2次分区的根节点，即节点1。然后，由节点1向区域I-1内的节点广播RREQ分组，并限制RREQ分组的跳数为|Dd-number+1|=2。

图4 第二次分区后的树型网络

④当目的节点是72时，由于邻居节点中有和目的节点同区域的节点90，则先将数据帧转发给节点90，然后再由其通过