工程科学学报，第39卷，第5期：778-785,2017年5月 Chinese Journal of Engineering,Vol.39,No.5:778-785,May 2017 D0L:10.13374/j.issn2095-9389.2017.05.017;htp:/journals..usth.edu.cn 基于按需和贪婪转发的移动自组网路由协议 黄金科四，樊晓光，向新，李帅 空军工程大学航空航天工程学院，西安710038 ☒通信作者，E-mail:86297609@qq.com 摘要移动自组网的动态拓扑特性给路由协议的设计带来了一定的挑战，尤其是在高动态的网络环境中.本文针对该问 题，提出了一种新的基于按需和贪婪转发的路由协议，该协议是在RG模式的基础上提出以下三点改进，即：(1)通过受限的 洪泛机制降低网络在路由发现阶段的控制开销：(2)通过移动预测机制，在被动寻路阶段监视被动路径的状态和在GG阶段 帮助节点选取适当的邻居作为下一跳节点：(3)通过路径请求延迟机制以减少不必要的资源浪费.仿真结果表明：改进的 RGR协议与现有的RGR、AODV、Modified-RGR和Optimized-RGR相比，不仅具有较高的数据包接收成功率，而且平均路由开 销和端到端时延也相对较低. 关键词移动自组织网：路由协议：受限洪泛；移动预测：路由请求延迟；性能分析 分类号TN929.5 Routing protocol for mobile ad hoc networks based on on-demand and greedy forwarding HUANG Jin-ke,FAN Xiao-guang,XIANG Xin,LI Shuai Aeronautics and Astronautics Engineering College,Air Force Engineering University,Xi'an 710038,China Corresponding author,E-mail:86297609@qq.com ABSTRACT The dynamic topology of a mobile ad hoc network poses a real challenge when designing the routing protocol,especially in high-dynamic environments.In this paper,a new routing protocol was proposed that is based on on-demand and greedy forwarding. This protocol proposes three opinions to RGR,i.e.,through scoped flooding to decrease control overhead in route discovery phrase, through mobility prediction to monitor the condition of the reactive path and help nodes choose the proper next-hop in the GGF phrase and through delayed route requests to reduce unnecessary waste of network resources.In contrast to RGR,AODV,Modified-RGR. and Optimized-RGR simulation,the results show the improved RGR not only has a high packet acceptance ratio,but has a low normalized routing overhead and an average end-to-end delay. KEY WORDS mobile ad hoc networks;routing protocol;scoped flooding;mobility prediction;delayed route requests;performance evaluation 移动自组织网络(mobile ad hoc networks, 的路由协议，对确保网络的连通性、时效性以及提高网 MANETs)作为一种自组织、多跳和不依赖地面基础设 络对无线资源的利用率等方面至关重要) 施的无线网络，一直备受业界的关注-】.但是，移动 根据更新机制的不同[3-)，路由协议大致可以分 自组织网络所具有的动态拓扑、无中心、链路易中断和 为主动（表驱动）路由、被动（按需）路由、混合路由和 有限的带宽资源等特性，给移动自组织网络路由协议 地理路由四种路由策略.主动路由需要周期性地广播 的设计带来了一定的挑战，即如何设计一种有效、可靠 路由信息以主动维护路由，路由信息的周期性交换需 收稿日期：2016-09-26 基金项目：陕西省自然科学基础基金资助项目(2009M8001-4)
工程科学学报,第 39 卷,第 5 期:778鄄鄄785,2017 年 5 月 Chinese Journal of Engineering, Vol. 39, No. 5: 778鄄鄄785, May 2017 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2017. 05. 017; http: / / journals. ustb. edu. cn 基于按需和贪婪转发的移动自组网路由协议 黄金科苣 , 樊晓光, 向 新, 李 帅 空军工程大学航空航天工程学院, 西安 710038 苣 通信作者,E鄄mail: 86297609@ qq. com 摘 要 移动自组网的动态拓扑特性给路由协议的设计带来了一定的挑战,尤其是在高动态的网络环境中. 本文针对该问 题,提出了一种新的基于按需和贪婪转发的路由协议,该协议是在 RGR 模式的基础上提出以下三点改进,即:(1)通过受限的 洪泛机制降低网络在路由发现阶段的控制开销;(2)通过移动预测机制,在被动寻路阶段监视被动路径的状态和在 GGF 阶段 帮助节点选取适当的邻居作为下一跳节点;(3)通过路径请求延迟机制以减少不必要的资源浪费. 仿真结果表明:改进的 RGR 协议与现有的 RGR、AODV、Modified鄄鄄RGR 和 Optimized鄄鄄RGR 相比,不仅具有较高的数据包接收成功率,而且平均路由开 销和端到端时延也相对较低. 关键词 移动自组织网; 路由协议; 受限洪泛; 移动预测; 路由请求延迟; 性能分析 分类号 TN929郾 5 Routing protocol for mobile ad hoc networks based on on鄄demand and greedy forwarding HUANG Jin鄄ke 苣 , FAN Xiao鄄guang, XIANG Xin, LI Shuai Aeronautics and Astronautics Engineering College, Air Force Engineering University, Xi爷an 710038, China 苣 Corresponding author, E鄄mail: 86297609@ qq. com ABSTRACT The dynamic topology of a mobile ad hoc network poses a real challenge when designing the routing protocol, especially in high鄄dynamic environments. In this paper, a new routing protocol was proposed that is based on on鄄demand and greedy forwarding. This protocol proposes three opinions to RGR, i. e. , through scoped flooding to decrease control overhead in route discovery phrase, through mobility prediction to monitor the condition of the reactive path and help nodes choose the proper next鄄hop in the GGF phrase and through delayed route requests to reduce unnecessary waste of network resources. In contrast to RGR, AODV, Modified鄄鄄RGR, and Optimized鄄鄄RGR simulation, the results show the improved RGR not only has a high packet acceptance ratio, but has a low normalized routing overhead and an average end鄄to鄄end delay. KEY WORDS mobile ad hoc networks; routing protocol; scoped flooding; mobility prediction; delayed route requests; performance evaluation 收稿日期: 2016鄄鄄09鄄鄄26 基金项目: 陕西省自然科学基础基金资助项目(2009JM8001鄄鄄4) 移 动 自 组 织 网 络 ( mobile ad hoc networks, MANETs)作为一种自组织、多跳和不依赖地面基础设 施的无线网络,一直备受业界的关注[1鄄鄄2] . 但是,移动 自组织网络所具有的动态拓扑、无中心、链路易中断和 有限的带宽资源等特性,给移动自组织网络路由协议 的设计带来了一定的挑战,即如何设计一种有效、可靠 的路由协议,对确保网络的连通性、时效性以及提高网 络对无线资源的利用率等方面至关重要[3] . 根据更新机制的不同[3鄄鄄4] ,路由协议大致可以分 为主动(表驱动)路由、被动(按需)路由、混合路由和 地理路由四种路由策略. 主动路由需要周期性地广播 路由信息以主动维护路由,路由信息的周期性交换需
黄金科等：基于按需和贪婪转发的移动自组网路由协议 ·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·
·780· 工程科学学报，第39卷，第5期 别从路由表和邻居表中获得 在.如果有且可用，节点就会转而使用该被动路径进 if (this is a control packet) 行数据转发.如果有但不可用，节点就会在其邻居表 handle it by control functions RREQs,REPRs,RERRs,... 中查询是否有距离目的节点较近邻的邻居存在.如果 else if this is a data packet) 不存在，该数据包就会被丢弃 if there is a valid reactive route) forward the packet on the route (5)目的节点的作用. else if the packet is from the current node this is a source node)) 数据包可以沿着被动路径或通过GGF转发到达 use RREQ/RREP to find a new path else if the packet is forwarded from a neighbor this is a intermedi- 目的节点.沿着被动路径到达目的节点的或者是源、 ate node)) 目的节点之间有可用的被动路径存在，或者是数据在 switch to GGF 转发时至少存在一次由被动寻路转而使用GGF模式 else drop the packet (neither reactive nor geographic route is a vail- 的情况.无论何种情况，目的节点都会将数据上交给 able) 相关应用. end if else (6)RGR的特点. drop the undnown packet neither a data packet nor a control 1)RGR需要邻居节点的地理位置信息以执行 packet) end if GGF:2)与传统的地理路由协议不同，RGR通过从路 图1伪代码 径请求和路径回复中获得目的节点的位置信息，而不 Fig.1 Pseudo code 需要专门的位置服务机制：3)由于RGR协议专为高动 (4)数据包的处理. 态网络环境而设计，因此相对传统的移动自组织网络， 当节点通过GGF模式收到数据包后，节点就会在 使用RGR协议的网络中时常会发生链路的通断.表1 其路由表中检查是否有通往目的节点的被动路径存 中列出了RGR与被动路由和地理路由的区别. 表1RGR、被动，地理路由的区别 Table 1 Differences between RGR,reactive,and geographic routing 协议 参数 RGR 被动路由 地理路由 位置服务 不需要 不需要 需要 路径请求 需要 需要 不需要 控制消息 路由建立和邻居发现 路由建立和邻居发现 邻居发现 邻居节点的位置 需要 不需要 需要 路径选择的节点属性 源节点和中间转发节点 源节点和中间转发节点 中间转发节点 移动性的典型要求 高移动性 静态和低移动性 高、低移动性 典型应用环境 高动态的移动自组织网络 规模较小的移动自组织网络 节点密度较大的移动自组织网络 1.2采用受限洪泛机制的协议 用I-],LAR则利用AODV或DSR协议将目的节点与 移动距离效应路由(distance routing effect algo- 对应的地理位置信息关联起来，借助源节点通过目的 rithm for mobility,DREAM)是一种采用定向洪泛机制 节点或从已知如何到达目的节点最新路径的中间转发 的路由协议，其规定在数据转发阶段，源节点利用地理 节点发送的路径回复包中得知目的节点的地理位置信 位置信息计算出到目的节点期望区域的角度范围，得 息，LAR协议只需向包含目的节点的区域而不需要向 到一个扇形区域，然后源节点就把分组转发给处于该 整个网络洪泛路径请求包.在路径修复阶段，每个中 扇形区域内的所有一跳邻居节点，邻居节点收到分组 间转发节点都会将自己的位置信息与路径请求包中包 后也将继续采用上述机制洪泛分组，直到分组到达目 含的特定的位置搜索区域进行对比.如果该中间转发 的节点. 节点在此区域中，则继续转发路径请求包，否则将其丢 位置辅助路由(location-aided routing,.LAR)[io协 弃[].如果通往目的节点路径都在搜索区域之外时， 议则充分利用目的节点的地理位置信息来限制数据转 LAR则重新洪泛路径请求包.在LAR协议中，地理位 发过程中分组的洪泛范围，有点类似于DREAM协议. 置信息只用来限制路径请求洪泛的区域，而不决定数 它采用的受限洪泛机制，是减少控制开销最常用的方 据包转发的方式. 法.在AODV和动态源路由(dynamic source routing, 1.3采用移动预测机制的协议 DSR)协议中，目的节点的地理位置信息不能直接使 文献[14-17]中，针对在被动路由中如何利用移
工程科学学报,第 39 卷,第 5 期 别从路由表和邻居表中获得. if (this is a control packet) handle it by control functions (RREQs, REPRs, RERRs,. . . ) else if (this is a data packet) if (there is a valid reactive route) forward the packet on the route else if (the packet is from the current node (this is a source node)) use RREQ/ RREP to find a new path else if (the packet is forwarded from a neighbor (this is a intermedi鄄 ate node)) switch to GGF else drop the packet (neither reactive nor geographic route is a vail鄄 able) end if else drop the undnown packet ( neither a data packet nor a control packet) end if 图 1 伪代码 Fig. 1 Pseudo code (4)数据包的处理. 当节点通过 GGF 模式收到数据包后,节点就会在 其路由表中检查是否有通往目的节点的被动路径存 在. 如果有且可用,节点就会转而使用该被动路径进 行数据转发. 如果有但不可用,节点就会在其邻居表 中查询是否有距离目的节点较近邻的邻居存在. 如果 不存在,该数据包就会被丢弃. (5)目的节点的作用. 数据包可以沿着被动路径或通过 GGF 转发到达 目的节点. 沿着被动路径到达目的节点的或者是源、 目的节点之间有可用的被动路径存在,或者是数据在 转发时至少存在一次由被动寻路转而使用 GGF 模式 的情况. 无论何种情况,目的节点都会将数据上交给 相关应用. (6)RGR 的特点. 1)RGR 需要邻居节点的地理位置信息以执行 GGF;2)与传统的地理路由协议不同,RGR 通过从路 径请求和路径回复中获得目的节点的位置信息,而不 需要专门的位置服务机制;3)由于 RGR 协议专为高动 态网络环境而设计,因此相对传统的移动自组织网络, 使用 RGR 协议的网络中时常会发生链路的通断. 表 1 中列出了 RGR 与被动路由和地理路由的区别. 表 1 RGR、被动、地理路由的区别 Table 1 Differences between RGR, reactive, and geographic routing 参数 协议 RGR 被动路由 地理路由 位置服务 不需要 不需要 需要 路径请求 需要 需要 不需要 控制消息 路由建立和邻居发现 路由建立和邻居发现 邻居发现 邻居节点的位置 需要 不需要 需要 路径选择的节点属性 源节点和中间转发节点 源节点和中间转发节点 中间转发节点 移动性的典型要求 高移动性 静态和低移动性 高、低移动性 典型应用环境 高动态的移动自组织网络 规模较小的移动自组织网络 节点密度较大的移动自组织网络 1郾 2 采用受限洪泛机制的协议 移动距离效应路由 ( distance routing effect algo鄄 rithm for mobility,DREAM) 是一种采用定向洪泛机制 的路由协议,其规定在数据转发阶段,源节点利用地理 位置信息计算出到目的节点期望区域的角度范围,得 到一个扇形区域,然后源节点就把分组转发给处于该 扇形区域内的所有一跳邻居节点,邻居节点收到分组 后也将继续采用上述机制洪泛分组,直到分组到达目 的节点. 位置辅助路由( location鄄aided routing,LAR) [10] 协 议则充分利用目的节点的地理位置信息来限制数据转 发过程中分组的洪泛范围,有点类似于 DREAM 协议. 它采用的受限洪泛机制,是减少控制开销最常用的方 法. 在 AODV 和动态源路由( dynamic source routing, DSR)协议中,目的节点的地理位置信息不能直接使 用[11鄄鄄12] ,LAR 则利用 AODV 或 DSR 协议将目的节点与 对应的地理位置信息关联起来,借助源节点通过目的 节点或从已知如何到达目的节点最新路径的中间转发 节点发送的路径回复包中得知目的节点的地理位置信 息,LAR 协议只需向包含目的节点的区域而不需要向 整个网络洪泛路径请求包. 在路径修复阶段,每个中 间转发节点都会将自己的位置信息与路径请求包中包 含的特定的位置搜索区域进行对比. 如果该中间转发 节点在此区域中,则继续转发路径请求包,否则将其丢 弃[13] . 如果通往目的节点路径都在搜索区域之外时, LAR 则重新洪泛路径请求包. 在 LAR 协议中,地理位 置信息只用来限制路径请求洪泛的区域,而不决定数 据包转发的方式. 1郾 3 采用移动预测机制的协议 文献[14鄄鄄17]中,针对在被动路由中如何利用移 ·780·
黄金科等：基于按需和贪婪转发的移动自组网路由协议 ·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·
·782· 工程科学学报，第39卷，第5期 路径请求和路径回复数据包不仅要携带目的节点的地 节点传输数据，因此没必要立即发送路径错误包.并 理位置信息，而且要捎带上一跳节点的速度、方向和时 且，文献[18]指出当失效路径的前端节点与目的节点 标信息.在路由维护阶段，节点通过周期性广播Hllo 之间的跳数较少时，使用GGF将数据成功传输到目的 包将自身位置、速度、方向和时标信息告知其邻居节 节点的概率很高 点，同时这些信息也将被中间转发节点所记录 在新的被动路径建立之前，中间转发节点将继续 路径发现过程结束后，源节点就将缓存中的数据 向最靠近目的节点的邻居发送数据包.在此规定，失 发送给目的节点.与RGR协议不同，这是传输数据的 效路径前端节点产生的路径错误包将会在经过一段时 当前节点首次估算其与下一跳节点间的距离.假定预 延之后（一般为发送1个Hllo数据包的时间间隔）， 测前time_s时刻，下一跳节点处于位置n处，坐标记为 向相反路径上的节点发送.当路径错误包到达源节点 (X.,Y.):而在c_ime时刻，预测该下一跳节点将移动 时，新的路径修复过程将会被启动.在高动态拓扑环 到位置p处，坐标记为(X。,Y):V和0分别表示下一 境中，该机制将会减少源节点发送的路径请求包的 跳节点的速度和方向信息（参数V和日可以从当前节 总数. 点的路由表中提取出来) 即利用下式，当前节点实时估算其下一跳节点的 3仿真分析 位置 3.1仿真配置 X。=X。+V×cosf×(c_time-time_s), 本文在NS2平台上对改进RGR协议(Improved- Y。=Y.+V×sin6×(c_time-time_s). (1) RGR)的性能进行仿真分析.仿真时，各节点随机分布 利用下式，可以判断出下一跳节点是否在当前节 在300km×300km的网络范围内，且按照random way- 点的通信范围内. point模型移动[]；节点的传播范围均为15km:速度均 D.=√(X。-X)2+(Y。-Y) (2) 匀分布在300~1100ms1之间：仿真时间为30min. 式中，D。是当前节点和下一跳节点之间的实际距离. 仿真中，各节点的仿真模型均相同.在物理层采 X。和Y。是当前节点的位置信息 用自由空间模型，扩频方式为直接序列扩频，并考虑实 如果D小于当前节点的传输范围，则当前节点继 际信道的物理参数；媒体接入控制(media access 续利用被动机制向下一跳节点传输数据.如果D,大 control,MAC)层采用时分多址(time division multiple 于当前节点的传输范围（即在被动模式下，下一跳节 access,TDMA)协议；网络层采用Improved--RGR协议； 点超出节点的通信范围)，当前节点将立即停止利用 应用层采用恒定比特率业务(constant bit rate,CBR)模 该条路径发送数据，转而使用GGF模式转发数据.在 型.所有的网络成员均以相同概率产生新业务，且持 GGF模式下，当前节点通过相同的预测机制获得网络 续时间服从负指数分布，数据包长度满足泊松分布. 的实时拓扑信息.然后，节点将数据传递给距离目的 仿真时的参数设置如表2所示 节点最近的节点 表2仿真参数配置 时间预测机制需要时间同步保障.如果网络中的 Table 2 Simulation parameter settings 节点能够通过GPS或北斗获得准确的导航信息，则不 需要额外的同步机制. 参数名 配置 2.3路径请求延迟机制 信道速率/(Mbits'1) 5 RGR协议中，如果在数据传输时被动路径失效， 数据包大小/kbyte 1024 网络将启动GGF模式继续进行数据转发.并且可以 发射功率/W 125 确保在GGF模式下，将数据传递给距离目的节点最近 接收机灵敏度/dBm -24.67 的节点.而且，失效路径的前端节点将会立即沿着发 物理层特征 直接序列扩频(DSSS) 送数据包的相反路径发送路径错误包直到其到达源节 点，以告知沿途节点该被动路径已经失效.此时，如果 3.2仿真结果及分析 源节点还要继续向同一目的节点（路径失效前与源节 为评估改进RGR协议(Improved-RGR)路由协议 点对应的目的节点)发送数据，则必须启动路径修复 的性能，本文将其与RGR、AODV、改良RGR协议 过程. (Modified-RGR)和优化RGR协议(Optimized--RGR) 采用路径请求延迟机制的RGR协议，主要依赖 从数据包接收成功率、平均路由开销和平均端到端时 GGF模式提升网络的整体性能.在此模式下，当某条 延三个方面进行仿真对比. 路径失效时，即使不存在一条通往目的节点的可用路 图2是五种协议的数据包接收成功率对比图.从 径，每个中间节点均有能力继续使用GGF模式向目的 图中可以看出，Improved-RGR协议的数据包接收成功
工程科学学报,第 39 卷,第 5 期 路径请求和路径回复数据包不仅要携带目的节点的地 理位置信息,而且要捎带上一跳节点的速度、方向和时 标信息. 在路由维护阶段,节点通过周期性广播 Hello 包将自身位置、速度、方向和时标信息告知其邻居节 点,同时这些信息也将被中间转发节点所记录. 路径发现过程结束后,源节点就将缓存中的数据 发送给目的节点. 与 RGR 协议不同,这是传输数据的 当前节点首次估算其与下一跳节点间的距离. 假定预 测前 time_s 时刻,下一跳节点处于位置 n 处,坐标记为 (Xn ,Yn );而在 c_time 时刻,预测该下一跳节点将移动 到位置 p 处,坐标记为(Xp,Yp );V 和 兹 分别表示下一 跳节点的速度和方向信息(参数 V 和 兹 可以从当前节 点的路由表中提取出来). 即利用下式,当前节点实时估算其下一跳节点的 位置. Xp = Xn + V 伊 cos 兹 伊 (c_time - time_s), Yp = Yn + V 伊 sin 兹 伊 (c_time - time_s). (1) 利用下式,可以判断出下一跳节点是否在当前节 点的通信范围内. Dn = (Xo - Xp) 2 + (Yo - Yp) 2 . (2) 式中,Dn 是当前节点和下一跳节点之间的实际距离. Xo 和 Yo 是当前节点的位置信息. 如果 Dn 小于当前节点的传输范围,则当前节点继 续利用被动机制向下一跳节点传输数据. 如果 Dn 大 于当前节点的传输范围(即在被动模式下,下一跳节 点超出节点的通信范围),当前节点将立即停止利用 该条路径发送数据,转而使用 GGF 模式转发数据. 在 GGF 模式下,当前节点通过相同的预测机制获得网络 的实时拓扑信息. 然后,节点将数据传递给距离目的 节点最近的节点. 时间预测机制需要时间同步保障. 如果网络中的 节点能够通过 GPS 或北斗获得准确的导航信息,则不 需要额外的同步机制. 2郾 3 路径请求延迟机制 RGR 协议中,如果在数据传输时被动路径失效, 网络将启动 GGF 模式继续进行数据转发. 并且可以 确保在 GGF 模式下,将数据传递给距离目的节点最近 的节点. 而且,失效路径的前端节点将会立即沿着发 送数据包的相反路径发送路径错误包直到其到达源节 点,以告知沿途节点该被动路径已经失效. 此时,如果 源节点还要继续向同一目的节点(路径失效前与源节 点对应的目的节点) 发送数据,则必须启动路径修复 过程. 采用路径请求延迟机制的 RGR 协议,主要依赖 GGF 模式提升网络的整体性能. 在此模式下,当某条 路径失效时,即使不存在一条通往目的节点的可用路 径,每个中间节点均有能力继续使用 GGF 模式向目的 节点传输数据,因此没必要立即发送路径错误包. 并 且,文献[18]指出当失效路径的前端节点与目的节点 之间的跳数较少时,使用 GGF 将数据成功传输到目的 节点的概率很高. 在新的被动路径建立之前,中间转发节点将继续 向最靠近目的节点的邻居发送数据包. 在此规定,失 效路径前端节点产生的路径错误包将会在经过一段时 延之后(一般为发送 1 个 Hello 数据包的时间间隔), 向相反路径上的节点发送. 当路径错误包到达源节点 时,新的路径修复过程将会被启动. 在高动态拓扑环 境中,该机制将会减少源节点发送的路径请求包的 总数. 3 仿真分析 3郾 1 仿真配置 本文在 NS2 平台上对改进 RGR 协议( Improved鄄鄄 RGR)的性能进行仿真分析. 仿真时,各节点随机分布 在 300 km 伊 300 km 的网络范围内,且按照 random way鄄 point 模型移动[19] ;节点的传播范围均为 15 km;速度均 匀分布在 300 ~ 1100 m·s - 1之间;仿真时间为 30 min. 仿真中,各节点的仿真模型均相同. 在物理层采 用自由空间模型,扩频方式为直接序列扩频,并考虑实 际信 道 的 物 理 参 数; 媒 体 接 入 控 制 ( media access control,MAC) 层采用时分多址( time division multiple access,TDMA)协议;网络层采用 Improved鄄鄄RGR 协议; 应用层采用恒定比特率业务(constant bit rate,CBR)模 型. 所有的网络成员均以相同概率产生新业务,且持 续时间服从负指数分布,数据包长度满足泊松分布. 仿真时的参数设置如表 2 所示. 表 2 仿真参数配置 Table 2 Simulation parameter settings 参数名 配置 信道速率/ (Mbit·s - 1 ) 5 数据包大小/ kbyte 1024 发射功率/ W 125 接收机灵敏度/ dBm - 24郾 67 物理层特征 直接序列扩频(DSSS) 3郾 2 仿真结果及分析 为评估改进 RGR 协议(Improved鄄鄄RGR)路由协议 的性 能, 本 文 将 其 与 RGR、 AODV、 改 良 RGR 协 议 (Modified鄄鄄 RGR) 和优化 RGR 协议(Optimized鄄鄄 RGR) 从数据包接收成功率、平均路由开销和平均端到端时 延三个方面进行仿真对比. 图 2 是五种协议的数据包接收成功率对比图. 从 图中可以看出,Improved鄄鄄RGR 协议的数据包接收成功 ·782·