黄金科等：基于按需和贪婪转发的移动自组网路由协议 ·781· 动预测机制提出了很多方法.但是大部分方法都是在 点的位置信息)，则该中间转发节点便用自身与目的 已知的路径中，找出一条最为稳定的路径作为最佳路 节点之间的距离值替换路径请求中携带的距离值0并 径.文献「141中，提出了利用节点间的链路生存时间 重新广播.如果从路径请求数据包中提取的距离值非 (link expiration time,LET)来优化路由协议.该策略通 0,则该中间转发节点便将自身与目的节点之间的距离 过在控制数据包中携带节点的位置信息，估算出任意 值与路径请求包中携带的距离值进行比较，当该距离 两节点间的ET,然后将其添加到路径请求数据包中. 值小于路径请求中原先携带的距离值时，路径请求包 接着，中间转发节点将路径请求数据包广播给其所有 中的距离值就会被该距离值（最新计算的出的距离 的一跳邻居节点.当目的节点收到此路径请求数据包 值)替换，并随路径请求包一起被重新广播.否则，中 后，就可以掌握所有链路的生存时间.通过找出源节 间转发节点将会丢弃该路径请求数据包.该过程将会 点到目的节点的各条路径上的最小链路生存时间，目 一直被继续，直到路径请求数据包抵达目的节点 的节点就可以得知该路径的生存时间(route expiration 当网络中没有节点知道目的节点的地理位置信息 time,RET),这样源节点就可以找出一条最为稳定的 时，改进RGR协议(Improved-RGR)就会采用和RGR 链路传输数据. 协议同样的机制.当源节点使用不精确的地理位置信 移动预测路由(mobility prediction routing protocol, 息进行寻路时，该受限的洪泛机制也会失败.此时源 MPRP)协议[是在数据传输阶段预测链路状态的，该节点将会在经过一段不必要的时间浪费后重新广播路 协议将节点的位置信息封装在传输的数据包中.在数径请求数据包. 据传输阶段，中间转发节点可以从转发给它的数据包2.2移动预测机制 中提取出前端节点的位置信息.通过比较连续两次从 根据RGR协议，源、目的节点间存在被动路径时， 收到数据包中提取出的位置信息，当前节点可以判断 数据包就可被传输到目的节点.在数据传输阶段，中 出该链路的剩余持续时间和排除一些不必要的中间转 间转发节点通过是否收到Hlo数据包来判断下一跳 发节点（如两节点间距离足以传输数据不必经过中间 节点的状态.如果中间转发节点连续3次收不到下一 节点转发，此时该中继转发节点的角色将会被距离当 跳节点的Ho数据包时，则认为该链路断开.此后， 前节点两跳范围内的其他可达节点替代（即被处于当 数据将会通过GGF模式进行转发.Hello数据包每秒 前节点通信覆盖范围内的节点替代)).这种预测机制广播一次，因此在这种机制下当链路断开，被发现时的 简单且不需要复杂的计算和封包格式.但是，该协议 延迟为2~3s.因此一旦链路断开，中间转发节点不能 必须在按需协议的基础上增加一个用于存储预测信息 立即发现该链路已经断开.在此阶段，中间转发节点 的预测表，并增加一个新的路径生存(route expired, 依就认为该链路可用并利用被动模式进行数据传输. EXP)数据包将此链路的状态反馈给当前节点的前端 因此，这些数据包就会丢失，并且也不会因此后采用的 节点.本文在RGR协议中增加具备同样能力的机制 GGF模式而被恢复. 来取代该新信息包的作用. 但是可以通过重新配置链路断开的标准，如当中 2改进的RGR协议 间转发节点收不到1次Helo数据包即认为该链路断 开，来减少数据包的丢失.这种机制虽然会缩短链路 2.1受限洪泛机制 断开的发现时间，但必将导致更多路径错误包的发送， 为减少路径请求数据包的发送数量，以降低路由 进而会干扰在无线链路中其他节点广播的Helo数据 开销和避免网络拥塞，在此将提出一种受限的洪泛 包，造成冲突.如果降低H®llo数据包发送的频率，当 机制. 网络中的节点较多时，单位时间内网络必将会产生大 首先假定：网络中不仅源节点，其他节点也可掌握 量的Helo数据包，这将增加协议的控制开销. 目的节点的位置信息.当网络首次进行路由发现时， 为解决这个问题，本文提出的移动预测机制将在 源节点将其与目的节点之间的距离值设为0并将其封 发送数据包（周期性Hlo包的一部分）之前利用下一 装在路径请求数据包中.然后，源节点将向其所有一 跳节点的一个有时间标签的速度矢量，来计算当前节 跳邻居广播该路径请求数据包.当邻居节点接收到该 点和下一跳节点之间的距离.当下一跳节点超出当前 数据包后，首先检查该数据包中是否有关于目的节点 发送节点的通信范围时，可立即意识到该链路无法使 的地理位置信息.如果没有，则该邻居继续广播接收 用进而使用GGF模式进行转发，避免造成数据包的 到的路径请求数据包：否则，该邻居（中间转发节点） 丢失 将计算其与目的节点之间的距离并将该距离值与路径 在该预测机制中，除路径请求、路径回复和Helo 请求数据包中的距离值进行比较.如果从路径请求数 数据包需要携带更多信息外，其他控制消息的功能和 据包中提取的距离值为0（即前端节点不知道目的节 广播机制与RGR协议中的类似.即在路由发现阶段，黄金科等: 基于按需和贪婪转发的移动自组网路由协议 动预测机制提出了很多方法. 但是大部分方法都是在 已知的路径中,找出一条最为稳定的路径作为最佳路 径. 文献[14]中,提出了利用节点间的链路生存时间 (link expiration time,LET)来优化路由协议. 该策略通 过在控制数据包中携带节点的位置信息,估算出任意 两节点间的 LET,然后将其添加到路径请求数据包中. 接着,中间转发节点将路径请求数据包广播给其所有 的一跳邻居节点. 当目的节点收到此路径请求数据包 后,就可以掌握所有链路的生存时间. 通过找出源节 点到目的节点的各条路径上的最小链路生存时间,目 的节点就可以得知该路径的生存时间( route expiration time,RET),这样源节点就可以找出一条最为稳定的 链路传输数据. 移动预测路由(mobility prediction routing protocol, MPRP)协议[15]是在数据传输阶段预测链路状态的,该 协议将节点的位置信息封装在传输的数据包中. 在数 据传输阶段,中间转发节点可以从转发给它的数据包 中提取出前端节点的位置信息. 通过比较连续两次从 收到数据包中提取出的位置信息,当前节点可以判断 出该链路的剩余持续时间和排除一些不必要的中间转 发节点(如两节点间距离足以传输数据不必经过中间 节点转发,此时该中继转发节点的角色将会被距离当 前节点两跳范围内的其他可达节点替代(即被处于当 前节点通信覆盖范围内的节点替代)). 这种预测机制 简单且不需要复杂的计算和封包格式. 但是,该协议 必须在按需协议的基础上增加一个用于存储预测信息 的预测表,并增加一个新的路径生存( route expired, REXP)数据包将此链路的状态反馈给当前节点的前端 节点. 本文在 RGR 协议中增加具备同样能力的机制 来取代该新信息包的作用. 2 改进的 RGR 协议 2郾 1 受限洪泛机制 为减少路径请求数据包的发送数量,以降低路由 开销和避免网络拥塞,在此将提出一种受限的洪泛 机制. 首先假定:网络中不仅源节点,其他节点也可掌握 目的节点的位置信息. 当网络首次进行路由发现时, 源节点将其与目的节点之间的距离值设为 0 并将其封 装在路径请求数据包中. 然后,源节点将向其所有一 跳邻居广播该路径请求数据包. 当邻居节点接收到该 数据包后,首先检查该数据包中是否有关于目的节点 的地理位置信息. 如果没有,则该邻居继续广播接收 到的路径请求数据包;否则,该邻居(中间转发节点) 将计算其与目的节点之间的距离并将该距离值与路径 请求数据包中的距离值进行比较. 如果从路径请求数 据包中提取的距离值为 0(即前端节点不知道目的节 点的位置信息),则该中间转发节点便用自身与目的 节点之间的距离值替换路径请求中携带的距离值 0 并 重新广播. 如果从路径请求数据包中提取的距离值非 0,则该中间转发节点便将自身与目的节点之间的距离 值与路径请求包中携带的距离值进行比较,当该距离 值小于路径请求中原先携带的距离值时,路径请求包 中的距离值就会被该距离值( 最新计算的出的距离 值)替换,并随路径请求包一起被重新广播. 否则,中 间转发节点将会丢弃该路径请求数据包. 该过程将会 一直被继续,直到路径请求数据包抵达目的节点. 当网络中没有节点知道目的节点的地理位置信息 时,改进 RGR 协议( Improved鄄鄄 RGR)就会采用和 RGR 协议同样的机制. 当源节点使用不精确的地理位置信 息进行寻路时,该受限的洪泛机制也会失败. 此时源 节点将会在经过一段不必要的时间浪费后重新广播路 径请求数据包. 2郾 2 移动预测机制 根据 RGR 协议,源、目的节点间存在被动路径时, 数据包就可被传输到目的节点. 在数据传输阶段,中 间转发节点通过是否收到 Hello 数据包来判断下一跳 节点的状态. 如果中间转发节点连续 3 次收不到下一 跳节点的 Hello 数据包时,则认为该链路断开. 此后, 数据将会通过 GGF 模式进行转发. Hello 数据包每秒 广播一次,因此在这种机制下当链路断开,被发现时的 延迟为 2 ~ 3 s. 因此一旦链路断开,中间转发节点不能 立即发现该链路已经断开. 在此阶段,中间转发节点 依就认为该链路可用并利用被动模式进行数据传输. 因此,这些数据包就会丢失,并且也不会因此后采用的 GGF 模式而被恢复. 但是可以通过重新配置链路断开的标准,如当中 间转发节点收不到 1 次 Hello 数据包即认为该链路断 开,来减少数据包的丢失. 这种机制虽然会缩短链路 断开的发现时间,但必将导致更多路径错误包的发送, 进而会干扰在无线链路中其他节点广播的 Hello 数据 包,造成冲突. 如果降低 Hello 数据包发送的频率,当 网络中的节点较多时,单位时间内网络必将会产生大 量的 Hello 数据包,这将增加协议的控制开销. 为解决这个问题,本文提出的移动预测机制将在 发送数据包(周期性 Hello 包的一部分)之前利用下一 跳节点的一个有时间标签的速度矢量,来计算当前节 点和下一跳节点之间的距离. 当下一跳节点超出当前 发送节点的通信范围时,可立即意识到该链路无法使 用进而使用 GGF 模式进行转发,避免造成数据包的 丢失. 在该预测机制中,除路径请求、路径回复和 Hello 数据包需要携带更多信息外,其他控制消息的功能和 广播机制与 RGR 协议中的类似. 即在路由发现阶段, ·781·