黄金科等：基于按需和贪婪转发的移动自组网路由协议 ·779· 要消耗大量的带宽资源，因此此类协议适合规模较小 较RGR、按需距离向量(ad-hoc on-demand distance 的网络：被动路由不需要周期性地广播路由信息，只有 vector,AODV)协议、Modified-RGR和Optimized--RGR, 在源、目的节点通信需要且该链路不为源节点所知时 无论是在数据包接收成功率，还是在平均路由开销和 才进行路由发现过程，路由发现会造成一定的时延，因 平均端到端时延方面性能均有一定的提升. 此此类协议也适合规模较小的网络：混和路由协议则 基础理论 是由主动路由和被动路由有机结合组成的协议，即在 1 一定的网络区域内采用主动或被动策略，区域间则采 1.1RGR协议 用被动或主动策略，此类协议主要是针对规模较大、移 RGR是一种兼有基于拓扑和基于位置路由协议 动性较强的网络所设计：地理路由是随着GPS、北斗等 特点的路由协议，它可以有效解决高动态环境下，简单 定位技术的不断发展带来的产物，在网络节点上装备 使用地理路由协议无法满足网络整体性能需求的弊 定位装置，节点可以准确获得自己的地理位置和时标， 端.通常，RGR是将AODV协议和GGF模式相结合， 据此，源节点可将数据“有目的”地向目的节点的方向 即当网络使用的被动路由机制失效时，网络就会使用 上传输，最终到达目的节点. GGF模式进行路由转发：当出现以下两种情况，即：当 在高动态网络环境下，简单的使用被动或地理路 数据包的生存时间(time to live,TTL)减为0或节点使 由已无法满足用户对网络整体性能的需求.因此，文 用GGF模式找不到靠近目的节点的邻居节点时，节点 献[5]提出了一种新的路由模式：即“被动-贪婪-被动 将放弃GGF使用被动方式进行寻路 (reactive-greedy--reactive,RGR)”模式，该模式能够使 RGR协议的创新之处在于：被动方式和贪婪转发 移动自组织网络中的节点很好的适应高动态的场景. 方式都可用来传输数据包.并且，相对于传统的地理 但是由于其控制消息（如路径请求）是在全网进行广 路由协议，RGR协议不需要专门的位置服务机制提供 播，因此协议的控制开销相对会比较高.文献[6]在 目的节点的位置信息，而用被动路由机制替代：相对纯 RGR的基础上，使用受限洪泛和移动预测机制，一定 粹的被动路由协议，RGR协议不需要专门的路由修复 程度上增加了数据包发送的成功率、降低了端到端时 过程进行路径修复而可用贪婪转发机制替代.RGR与 延，但控制开销的降幅则不理想.文献[7]则在RGR 被动路由协议、GGF模式的不同之处主要有以下 的基础上，采用受限洪泛和新路由延迟建立机制，一定 几点： 程度上降低了控制开销，但数据包发送的成功率和端 (1)控制消息. 到端时延这两个指标则不尽如人意.文献「8]提出了 RGR协议中有四类控制消息：路径请求(route 一种改良的RGR(Modified--RGR),该协议是基于RGR request,.RREQ)、路径回复(route responses,RREP)、路 协议在路由建立过程中加入链路稳定性度量.而优化 径错误(route error,RERR)和Hello数据包.RGR协议 的RGR(Optimized-RGR)I]则是在Modified-RGR的 中除了路径请求、路径回复和Hlo数据包中比AODV 基础上，引入了贪婪地理转发(greedy geographic 协议中的多携带了节点的地理位置信息外，控制消息 forwarding,GGF)修复策略.文献[8]和[9]这两种改 的功能和AODV协议中的类似.其中，路径请求数据 进的RGR协议，总体上来讲，都提高了数据发送的成 包中携带了源节点的地理位置信息，路径回复数据包 功率，但却无法保障网络具有较低的控制开销和端到 中携带了目的节点的位置信息，而Hlo数据包中携 端时延 带了邻居节点的位置信息（位置信息则被用于更新中 为提升RGR协议在高动态环境下网络的整体性 间转发节点的节点表) 能，本文在RGR的基础上提出以下三点优化意见. (2)节点表. (1)采用受限的洪泛机制：利用目的节点的速率 RGR中，每个节点需要维护两张“表”：I)路由表， 和运动方向，为中间转发节点提供更为精确的位置信 用于寻找目的节点，其中包括了在路由修复过程中寻 息，从而“有目的”限制控制数据包的洪泛区域，以降 找目的节点所需的特定节点的地址信息；2)邻居表， 低网络在路由发现阶段的控制开销 其中列出了所有的一跳邻居节点及其位置信息. (2)采用移动预测机制：一方面监视在被动寻路 (3)GGF模式的启用. 阶段被动路径的状态：另一方面在GGF阶段帮助节点 当通往目的节点的被动路径失效时，中间转发节 选取适当的邻居节点作为下一跳转发节点 点就会启动GGF模式.即当节点接收到数据包后就 (3)采用路径请求延迟机制：即当已有路径失效 在其路由表中寻找是否有通往目的节点的被动路径. 时，延迟路径错误数据包的发送从而延迟新路由的建 如果有但该被动路径已失效（由于邻居节点的移动等 立，以减少不必要的资源浪费 原因)，RGR就会转用GGF进行转发，其伪代码如图1 仿真结果表明：改进RGR协议(Improved--RGR) 所示.其中，目的节点和邻居节点的位置信息可以分黄金科等: 基于按需和贪婪转发的移动自组网路由协议 要消耗大量的带宽资源,因此此类协议适合规模较小 的网络;被动路由不需要周期性地广播路由信息,只有 在源、目的节点通信需要且该链路不为源节点所知时 才进行路由发现过程,路由发现会造成一定的时延,因 此此类协议也适合规模较小的网络;混和路由协议则 是由主动路由和被动路由有机结合组成的协议,即在 一定的网络区域内采用主动或被动策略,区域间则采 用被动或主动策略,此类协议主要是针对规模较大、移 动性较强的网络所设计;地理路由是随着 GPS、北斗等 定位技术的不断发展带来的产物,在网络节点上装备 定位装置,节点可以准确获得自己的地理位置和时标, 据此,源节点可将数据“有目的冶地向目的节点的方向 上传输,最终到达目的节点. 在高动态网络环境下,简单的使用被动或地理路 由已无法满足用户对网络整体性能的需求. 因此,文 献[5]提出了一种新的路由模式:即“被动鄄鄄贪婪鄄鄄被动 (reactive鄄鄄 greedy鄄鄄reactive,RGR)冶模式,该模式能够使 移动自组织网络中的节点很好的适应高动态的场景. 但是由于其控制消息(如路径请求)是在全网进行广 播,因此协议的控制开销相对会比较高. 文献[6] 在 RGR 的基础上,使用受限洪泛和移动预测机制,一定 程度上增加了数据包发送的成功率、降低了端到端时 延,但控制开销的降幅则不理想. 文献[7] 则在 RGR 的基础上,采用受限洪泛和新路由延迟建立机制,一定 程度上降低了控制开销,但数据包发送的成功率和端 到端时延这两个指标则不尽如人意. 文献[8]提出了 一种改良的 RGR(Modified鄄鄄RGR),该协议是基于 RGR 协议在路由建立过程中加入链路稳定性度量. 而优化 的 RGR(Optimized鄄鄄 RGR) [9] 则是在 Modified鄄鄄 RGR 的 基 础 上, 引 入 了 贪 婪 地 理 转 发 ( greedy geographic forwarding,GGF)修复策略. 文献[8] 和[9] 这两种改 进的 RGR 协议,总体上来讲,都提高了数据发送的成 功率,但却无法保障网络具有较低的控制开销和端到 端时延. 为提升 RGR 协议在高动态环境下网络的整体性 能,本文在 RGR 的基础上提出以下三点优化意见. (1)采用受限的洪泛机制:利用目的节点的速率 和运动方向,为中间转发节点提供更为精确的位置信 息,从而“有目的冶限制控制数据包的洪泛区域,以降 低网络在路由发现阶段的控制开销. (2)采用移动预测机制:一方面监视在被动寻路 阶段被动路径的状态;另一方面在 GGF 阶段帮助节点 选取适当的邻居节点作为下一跳转发节点. (3)采用路径请求延迟机制:即当已有路径失效 时,延迟路径错误数据包的发送从而延迟新路由的建 立,以减少不必要的资源浪费. 仿真结果表明:改进 RGR 协议( Improved鄄鄄 RGR) 较 RGR、 按 需 距 离 向 量 ( ad鄄hoc on鄄demand distance vector,AODV)协议、Modified鄄鄄RGR 和 Optimized鄄鄄RGR, 无论是在数据包接收成功率,还是在平均路由开销和 平均端到端时延方面性能均有一定的提升. 1 基础理论 1郾 1 RGR 协议 RGR 是一种兼有基于拓扑和基于位置路由协议 特点的路由协议,它可以有效解决高动态环境下,简单 使用地理路由协议无法满足网络整体性能需求的弊 端. 通常,RGR 是将 AODV 协议和 GGF 模式相结合, 即当网络使用的被动路由机制失效时,网络就会使用 GGF 模式进行路由转发;当出现以下两种情况,即:当 数据包的生存时间(time to live,TTL)减为 0 或节点使 用 GGF 模式找不到靠近目的节点的邻居节点时,节点 将放弃 GGF 使用被动方式进行寻路. RGR 协议的创新之处在于:被动方式和贪婪转发 方式都可用来传输数据包. 并且,相对于传统的地理 路由协议,RGR 协议不需要专门的位置服务机制提供 目的节点的位置信息,而用被动路由机制替代;相对纯 粹的被动路由协议,RGR 协议不需要专门的路由修复 过程进行路径修复而可用贪婪转发机制替代. RGR 与 被动路 由 协 议、 GGF 模 式 的 不 同 之 处 主 要 有 以 下 几点: (1)控制消息. RGR 协议中有四类控制消息:路径请求 ( route request,RREQ)、路径回复( route responses,RREP)、路 径错误(route error,RERR)和 Hello 数据包. RGR 协议 中除了路径请求、路径回复和 Hello 数据包中比 AODV 协议中的多携带了节点的地理位置信息外,控制消息 的功能和 AODV 协议中的类似. 其中,路径请求数据 包中携带了源节点的地理位置信息,路径回复数据包 中携带了目的节点的位置信息,而 Hello 数据包中携 带了邻居节点的位置信息(位置信息则被用于更新中 间转发节点的节点表). (2)节点表. RGR 中,每个节点需要维护两张“表冶:1)路由表, 用于寻找目的节点,其中包括了在路由修复过程中寻 找目的节点所需的特定节点的地址信息;2) 邻居表, 其中列出了所有的一跳邻居节点及其位置信息. (3)GGF 模式的启用. 当通往目的节点的被动路径失效时,中间转发节 点就会启动 GGF 模式. 即当节点接收到数据包后就 在其路由表中寻找是否有通往目的节点的被动路径. 如果有但该被动路径已失效(由于邻居节点的移动等 原因),RGR 就会转用 GGF 进行转发,其伪代码如图 1 所示. 其中,目的节点和邻居节点的位置信息可以分 ·779·