硕士学位论文第三章Ｚｉｇｂｅｅ组网算法的研究与设计旧，当路由信息的分组在传输中丢失时，就很可能导致中问节点对ＲＲＥＱ错误应答，这时ＡＯＤＶ算法将利用节点序列号的大小来避免路由环路问题，而在ＡＯＤＶｊｒ中，不使用节点序列号，仅规定目的节点回复ＲＲＥＰ，这样同样能避免路由环路，同时可以进一步减少丌销。ＡＯＤＶ算法的路由环路的避免如图３．７。源点∽源目的节点嘞源Ｏ点＠Ｓｅｑ＿Ｎｏ．２５Ｓｅｑ＿Ｎｏ．２６Ｓｅｑ＿Ｎｏ．２６Ｓｅｑ＿Ｎｏ．２９Ｓｅｑ＿Ｎｏ．２１０（Ｓｅｑ＿Ｎｏ．２ｌＯ）图３．７避免路由环路如上图：节点１向节点５进行通信，假如路由信息（ＲＲＥＱ）通过节点４传输的时候丢失了，那么４．＞５的链路将中断（图ａ），而源节点ｌ并不知道４．＞５链路发生中断。此时，节点４发起本地链路修复，向节点５发起路由发现过程，节点ｌ将会收到节点４发来的ＲＲＥＱ（通过４．＞６．＞ｌ路径，图ｂ），而节点１原路由表中已经有节点５的信息，那么此时节点ｌ又将沿着１－＞２－＞３－＞４的路径发起ＲＲＥＱ，结果就形成环路４．＞６．＞１．＞２．＞３．＞４。在ＡＯＤＶ算法当中，采用节点序列号方式（图ｃ１，当４－＞５的链路发生中断时，节点４把自身的序列号（－－９）更新为目的节点５的序列号（＝１０），而此时由于节点６的序列号小于节点４的序列号，那么节点４将放弃向节点６广播Ｉ眦Ｑ，这样就能避免路由环路问题。而对于ＡＯＤＶｊｒ算法来说，仅允许目的节点回复ＲＲＥＰ，当源节点到目的节点的链路发生中断时，假如此时还需要路由的话，源节点将修改路由发现路径，及时更新网络拓扑，这样也能有效的避免路由环路，因此不需要节点序列号机制。在ＡＯＤＶｊｒ算法中，节点在转发ＲＲＥＱ之前，会计算将ＲＲＥＱ发送给它的邻节点和本节点之间的链路开销，同样在转发ＲＲＥＰ之前也会计算反向路径中下一跳节点与本节点之间的链路开销，并将这些开销加到各分组中存储的链路开销上。在路由期间，中间节点和目的节点可能多次收到同一个ＲＲＥＱ，这种情况下采用首接为最优的思想，即只响应第一个收到的ＲＲＥＱ，在该请求中记录的路径即为消息传输的路径，ＲＲＥＰ将沿着收到的第一个ＲＲＥＱ中记录的上一级地址发送回去。而在ＡＯＤＶ算法中，由于采用了序列节点号机制，如果两次的ＲＲＥＱ的序列４２硕十学位论文第三章Ｚｉｇｂｅｅ组网算法的研究与设计号相同，那么将丢弃后～个ＲＲＥＱ；如果后一个ＲＲＥＱ的序列号大于先自订的序列号，那么将更新路由，选择序列号大Ｉ拘ＲＲＥＱ。ＡＯＤＶｊｒ算法流程图如图３—８。图３－８ＡＯＤＶｊｒ算法流程图图３－９是ＡＯＤＶｊｒ算法数据传输过程的示例图。图中，节点１向节点１１发送数据，节点５向节点３发送数据，路由发现过程和图３．２中过程一样，不同的是当中间节点（如节点４）有到目的节点的路由，也不回复ＲＲＥＰ，并且路由表中也不存储跳数信息，只存储各节点之间的链路开销（图ａ），然后选择各路径中总成本最小的那条路径作为数据传输路径。由于节点４要同时处理两组ＲＲＥＱ，很可能导致节点４过载，使得路径ｌ的路由总成本小于路径２，也就是说ＲＲＥＱ沿着路径ｌ比路径２要更快到达节点１ｌ，此时将选择路径ｌ作为数据传输的路径（尽管路径２的跳数比路径ｌ小１，并且节点１１会定期发送ＡＣＫ消息以维护路由信息（图”。４３硕十学位论文第三章Ｚｉｇｂｅｅ组网算法的研究与设计（ａ）（ｂ）一一＋反向路径一ＲＲＥＱ’ＲＲＥＰ／，、Ｄａｔａ．７一ｌＡＣＫ图３－９ＡＯＤＶｊｒ算法中数据传送过程示例图从以上分析可以得出：改进的ＡＯＤＶｊｒ算法将使节点避免当节点出现过载的情况下过早的失去作用，当节点想要选择路径时，将考虑路径上的链路开销。在ＡＯＤＶ算法只选择最少跳数的路由，而ＡＯＤＶｉｒ算法中，只选择最快的路由，而忽略其跳数信息。当跳数最少的路径上某个（些）中间节点已经严重过载时，如果继续选择使用该路径进行路由，那么将选择其他链路质量较好的路径，这样就可以避免导致大量数据包的丢失和传输延迟的急剧增加。／／ＡＯＤＶｊｒ算法实现ＲＲＥＱ部分代码：ｖｏｉｄｓｅｎｄ＿ｒｒｅｑ（ＲＲＥＱ幸ｒｅｑｕｅｓｔ）（……ｉｎｓｅｒｔ＿ｒｅｑ＿ｉｄ（ｒｅｑｕｅｓｔ－＞ｓｏｕｒｃｅａｄｄｒ，ｒｅｑｕｅｓｔ－＞ｄｅｓｔ＿ａｄｄｒ，ｒｅｑｕｅｓｔ－＞ｒｅｑ＿ｉｄ）；／／将ｒｅｑｉｄ力ｆｌ入请求表ｕｐｄａｔｅ＿ｒｏｕｔｅ（ｒｅｑｕｅｓｔ－＞ｎｅｘｔｈｏｐ）；ｒｅｑｕｅｓｔ－＞ｓｒｅ＿ａｄｄｒ２ｒｅｑｕｅｓｔ－＞ｓｏｕｒｃｅ＿ａｄｄｒ，ｐｒｅｖａｄｄｒ，ｒｅｑｕｅｓｔ－＞ＬＱＩ，／／更新路由ｓｒｅ＿ｒｏｕｔｅ?＞ｄｅｓｔ＿ａｄｄｒ；ｒｅｑｕｅｓｔ－＞ｒｅｑ＿ｉｄ＝＋＋ｓｒｃ＿ｒｏｕｔｅ－＞ｒｅｑ＿ｉｄ；ｒｅｑｕｅｓｅ－＞ＬＱＩ＝ＭＡＣ＿ＬＱＩ；ｉｆ（ｍａｃｌｎｆｏ．ｓｈｏｒｔＡｄｄｒ．Ｖａｌ—ｒｅｑｕｅｓｔ－＞ｄｅｓｔ＿ａｄｄｒ）（ｓｅｎｄ＿ｒｒｅｐ（ｒｅｑｕｅｓｔ）；ｓｔｒｕｃｔ／／目标节点应答）?ｄｅｓｔ—ｒｏｕｔｅ＝Ｒｏｕｔｅ＿Ｔａｂｌｅ＿Ｅｎｔｒｙｌｏｏｋｕｐｒｏｕｔｅ（ｒｅｑｕｅｓｔ－＞ｄｅｓｔ＿ａｄｄｒ）；ｆｏｒｗａｒｄ＿ｒｒｅｑ（ｒｅｑｕｅｓｔ）；｝）●／／把目的节点地址加进路由表／／转发ＲＲＥＱ）／／ＡＯＤＶｊｒ算法实现Ｉ眦Ｐ部分代码ｖｏｉｄｓｅｎｄ＿ｒｒｅｐ（ＲＲＥＱ?ｒｅｑｕｅｓｔ）’｛硕＋学位论文第三章Ｚｉｇｂｅｅ组网算法的研究与没计ＲＲＥＰ牛ｒｅｐｌｙ＝（ＲＲＥＰ木）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＲＲＥＰ））；ｒｅｐｌｙ．一＞ｔｙｐｅ＝ＡＯＤＶｊｒ＿ＲＲＥＰ；ｒｅｐｌｙ．．＞ｄｅｓｔａｄｄｒ＝ｒｅｑｕｅｓｔ－＞ｄｅｓｔ＿ａｄｄｒ；／／ＲＲＥＰ∥目的节点地址ｒｅｐｌｙ．－＞ＬＱＩ＝ＭＡＣＬＱＩ；ｓｔｒｕｃｔＲｏｕｔｅＴａｂｌｅ＿Ｅ；ｎｔｒｙ木ｄｅｓｔ—ｎｏｕｔｅｌｏｏｋｕｐｒｏｕｔｅ（ｒｅｑｕｅｓｔ－＞ｄｅｓｔ＿ａｄｄｒ）；ｒｅｐｌｙ．?＞ｓｏｕｒｃｅ＿ａｄｄｒ＝ｒｅｑｕｅｓｔ，－＞ｓｏｕｒｃｅｒｅｐｌｙ．．＞ｌｉｒｅ２０ｍｓａｄｄｒ；∥源节点地址ｍａｃＤｅｓｔｌｎｆｏ．ａｄｄｒＭｏｄｅ＝ＭＡＣ—ＤＳＴ＿ＳＨＯＲＴ＿ＡＤＤＲ；ｍａｃＤｅｓｔＩｎｆｏ．ｐａｎｌＤ＝ｍａｃｌｎｆｏ．ｐａｎｌＤ；ｍａｃＤｅｓｔｌｎｆｏ．ｓｈｏｒｔＡｄｄｒ．Ｖａｌ＝ｌｏｏｋｕｐ＿ｒｏｕｔｅ（ｒｅｑｕｅｓｔ－＞ｓｏｕｒｃｅ＿ａｄｄｒ）－＞ｎｅｘｔａｄｄｒ；／／发起节点路径的下一跳…。）在转发ＲＲＥＱ和ＲＲＥＰ时，只需要把下一跳的地址和ＬＱＩ值加进路由表，然后调用网络层相关函数实现即可。３．７Ｚｉｇｂｅｅ路由算法的设计通过上面的研究，在Ｃｌｕｓｔｅｒ－Ｔｒｅｅ算法中，节点之间数据的发送只能按照父子关系进行，印当一个节点收到数据后发现该分组不是给自己的，则只能转发给它的父节点或者子节点，显然这并不一定是最优的路径，因此路由效率较低。另一方面，由于Ｃｌｕｓｔｅｒ－Ｔｒｅｅ算法不需要维护路由表信息，并且无初始延迟，因此控制开销很低。而ＡＯＤＶｊｒ算法具有路径寻优功能，能够获得最佳的路径，但需要路由表信息，并且有初始延迟，因此控制开销相对Ｃｌｕｓｔｅｒ－Ｔｒｅｅ算法来说比较高。为了更进一步提高路由效率，达到低功耗、可靠性高的设计目标，本文采用Ｃｌｕｓｔｅｒ－Ｔｒｅｅ算法和ＡＯＤＶｊｒ算法相结合的ＺＢＲ（ＺｉｇｂｅｅＲｏｕｔｉｎｇ）算法，此算法思想汇聚了两种算法的优点，是两种算法的折衷：既具有ＡＯＤＶｊｒ算法的路由寻优的能力，又具有Ｃｌｕｓｔｅｒ－Ｔｒｅｅ算法的无初始延迟的优点。３．７．１ＺＢＲ算法的设计ＺＢＲ算法设计思想如下：让具有路由功能的节点使用ＡＯＤＶｊｒ算法去发现路由，这样这些节点就可以不按照父子关系而直接发送信息到其通信范围内的其他具有路由功能的节点，而不具有路由功能的节点仍然按照Ｃｌｕｓｔｅｒ－Ｔｒｅｅ路由算法的思想去发送数据分组和控制分组。在ＺＢＲ算法中，把网络中的节点分成三种类型：Ｉ卅、ＲＮ．和ＲＦＤ。其中ｌ埘＋是指具有足够的存储空间和能力去执行４５硕十学位论文第三章Ｚｉｇｂｅｅ组网算法的研究与设计ＡＯＤＶｊｒ路由算法的节点，ＲＮ．是指其存储空间受限，不具有执行ＡＯＤＶｊｒ算法路由算法的能力，只能用Ｃｌｕｓｔｅｒ－Ｔｒｅｅ算法处理。另外Ｃｏｏｒｄｉｎａｔｏｒ的路由算法跟Ｉ州＋相同，而且Ｃｏｏｒｄｉｎａｔｏｒ、ＩⅢ＋和ＲＮ．都是ＦＦＤ，能给其他节点充当路由节点；终端节点（ＲＦＤ）只能充当Ｃｌｕｓｔｅｒ－Ｔｒｅｅ算法的叶子节点（ＬｅａｆＮｏｄｅ），只能把数据交给父节点处理。在ＺＢＲ算法中，当ｌＷ＋节点需要发送分组到网络中的某个节点而又没有通往目的节点的路由时，它会按照ＡＯＤＶｊｒ算法发起路由发现过程，所不同的是在ＡＯＤＶｊｒ算法中，节点都是ＲＮ＋节点，每个节点处理ＲＲＥＱ的过程都一样；而在ＺＢＲ算法中，由于中间节点的类型不同，接收到ＲＲＥＱ时处理的过程也不一样，大致过程如下：１．源节点首先向周围节点广播一个ＲＲＥＱ分组，如果收到ＲＲＥＱ的节点是一个ＲＮ．节点，它就按照Ｃｌｕｓｔｅｒ－Ｔｒｅｅ算法转发此分组；如果收到ＲＲＥＱ的节点是一个ＩⅢ＋，则按照ＡＯＤＶｊｒ算法广播ＲＲＥＱ过程继续广播ＲＲＥＱ，并创建反向路径，当ＲＮ＋节点多次收到ＲＲＥＱ时，同样只响应第一个收到的ＲＲＥＱ，并且假如中间节点有到目的节点的路由，同样也不回复ＲＲＥＰ。２．当ＲＲＥＱ到达目的节点或者目的节点的父节点，此节点就向ＲＲＥＱ的源节点回复一个ＲＲＥＰ分组（ＲＮ．节点也可以回复ＲＲＥＰ分组，但无法记录路由信息１，ＲＲＥＰ应沿着已建立的反向路径向源节点传输，收到ＲＲＥＰ的节点建立到目的节点的正向路径并更新相应的路由信息，然后就可以进行通信。ＺＢＲ算法把节点分为ｌⅢ＋、ＲＮ．和ＲＦＤ，在传输数据时，如果待发送数据的目标节点是自己的邻居节点，直接通信即可；反之，如果不是自己的邻居节点时，三种类型的节点处理数据包各不相同，如图３．１０。ＲＮ．接收到数据包回复ＡＣＫ，将数据交上层处理雪磊裂呈罗列直接发送ＮＮ点的路由？，／’ｌ一““一根据Ｃｌｕｓｔｅｒ－Ｔｒｅｅ路由算法。沿树查找到目的节点的路由将数据包沿着找到的路径传递结束（ａ）ＲＮ．节点数据处理流程图
Zigbee无线组网技术的研究 - 图文
