第 24 卷 第 3 期 2007 年 3 月 计 算 机 应 用 研 究 Application Research of Computers Vol. 24, No. 3 March 2007 AODV 的 本 地 修 复 算 法 * 肖百龙, 郭 伟, 刘 军, 祝思路 ( 电 子科 技大 学 通信 与信 息工 程学 院 通 信抗 干扰 技术 国家 级重 点实 验室 , 四川 成 都 610054) 摘 要: 提 出了 一种 新的 路由 本地 修复 算法 , 将 修复 尽量 限 制在 断 链 的 局 部 范 围内 , 减 少 了 修 复时 间 和 降 低 路 由维 护的开 销, 且不用 考虑 失效 链路 在整 个路 由 上 的 相 对 位置 , 均 可 对 其 进 行修 复 , 提 高 了 处 理失 效 链 路 的 能 力, 有利 于提 高网 络的 可扩 展性 。仿真 表明 , 这 种新 的路 由本 地修 复算 法明 显地提 高了 网络 多方 面的 性能 。 关键 词: 自 组织 分组 无线 网络 ; 路由 协议 ; 自组 织分 组无 线网 络按 需距离 矢量 路由 ; 本地 修复 ; 下两 跳 中图 分类 号: TP311 文 章编 号: 1001- 3695( 2007) 03- 0231- 03 文 献标 志码: A Local Recovery Mechanism in AODV XIAO Bai-long, GUO Wei, LIU Jun, ZHU Si-lu ( National Laboratory of Anti-interference Communication Technology, School of Communications & Information Engineering, University of Elec- tronic Science & Technology of China, Chengdu Shichuan 610054, China) Abstract: A new idea about local recovery of route that limited the repair near the broken links was proposed to decrease the reaction time of route breakage and the overhead of route maintenance. Furthermore, the approach can repair failure links without taking into account of their relative position on the whole path. It improves the ability of dealing with failure links and scala-bility properties of Ad hoc networks. Simulations show that the local recovery mechanism results in substantial perfor- mance improvement. Key words: Ad hoc network; routing protocols; AODV; local recovery; next-to-next hop 移动自组织网( Mobile Ad hoc Networks, MANET) 是由一组 带有无线收发装置的移动节点 组成的 无需基 站支持 的多跳 的 临时性自治系统。MANET 主要用于满足应急通信和军用 移动 通信需求, 如战场上部队 快速部 署和推 进、地 震或水 灾后的 营 救等。由于节点的无线通信覆盖范围有限, 两个无法直接通信 的移动节点需要借助于其他 节点进 行分组 转发, 即经 过多跳, 这是 MANET 与其他移动网络的最根本区别。 由于节点的随机移动, MANET 的拓扑随时都在发生变化, 无中心的动态变化的拓扑给设 计自适 应的分 布式路 由协议 带 来了很大的困难。路由技术是实现 Ad hoc 网 络的一项关 键技 术, MANET 的路由协议可分 为表驱 动和 按需 两大 类。表驱 动 路由协议 [ 1] 又被称 为主 动式 路由 协 议, 网络 中 的节 点通 过 周 期性的交互路由信息更新到其他所有节点的路由, 而不管是否 需要该路由进行通信。典型 的表驱动路 由协议有 OLSR( Opti- mized Link State Routing Protocol) [ 1] 、WRP( Wireless Routing Protocol) [ 2] 和 TBRPF( Topology Dissemination Based on Reverse- Path Forwarding) [ 3] 。按需 路 由 协议 [ 4] 又称 为 反 应 式 路 由 协 议, 在节点需要进行通信 时才建 立路由, 且仅 在通信 过程中 才 维护路由。 典型 的 反 应式 路 由 协议 有 AODV( Ad hoc On-de- mand Distance Vector Routing) [ 5] 、DSR( Dynamic Source Rou- ting) [ 6] 和 TORA ( Temporally-Ordered Routing Algorithms) [ 7] 。 反应式路由协议更能适应 Ad hoc 网 络的 动态 拓扑、带 宽受 限 和能源约束等特点, 通常 分为路 由发现 和路由 维护两 个阶段。 目前, 对于 Ad hoc 网络路由协议的研究正逐步深入, 但主要 集 中于路由发现阶段, 而关于路由维护的研究 却较少。C. Gui 等 人 [ 8] 提出了一种自修复和优 化路由 算法( SHORT) , 在 SHORT 算法中, 路由的所有相邻节 点均在 监视这 条路由, 当 有更好 的 子路由时就优化它。然而, 路由优化会影响网络的性能和能量 消耗, 当负荷较 重 时影 响更 加 严重。 Genping Liu 等人 [ 9] 提 出 了一种路由本 地修 复算 法( PATCH) , 用较 少的 开销 实现 了 对 链路的快速修复, 但是这种算法只能用于源路由协议。本文将 基于 AODV 提出一种 改 进的 路由 本 地修 复算 法, 将 修复 尽 量 限制在失效链路的附近, 从 而缩短 了修复 的时间, 减 少了控 制 的开销, 而且其控制开销与时延均与网络的规模无关。 1 AODV 协议及其本地修复算法 AODV 是最有代表性的按需路由协议之一, 它有三种类 型 的控制分组: 路由请求( RREQ) 、路由应答( RREP) 和路由错 误 ( RERR) 。当源节点 需要 发送 数据 而又 没有 到达目 的节 点 的 有效路由时, 启动路由发现 过程, 在收 到路由 应答后 则开始 向 对应目的节点发送数据。在数据传输过程中, 如果有效路由发 生链路中断, 断链的上游节点可能会选择在本地修复链路。为 收 稿日期 : 2006- 01- 09; 修 返日期 : 2006- 03- 12 基 金项 目: 国 家自 然科学 基金 资助项 目( 60472052) ; 战术 通信抗 干扰 技术国 防科 技重点 实验室 基金资 助项 目( 51434020105ZS04) 作 者简介 : 肖百龙 ( 1973- ) , 男, 湖南 湘潭人 , 讲师, 博士 研究 生, 主要研 究方 向为自 组织 网络 路 由协 议 ; 郭伟 ( 1964- ) , 男 , 教授 , 博 导, 主 要研 究 方向为 移动通 信网 、扩 频通 信、信号与 信息 处理; 刘军 ( 1973- ) , 男, 博士 研究 生, 主 要 研究 方 向为 自 组织 网 络 MAC 技 术、资 源 管理 、移动 性 管 理; 祝 思路( 1982- ) , 男 , 硕 士研 究生, 主 要研究 方向为 自组 织网络 路由 协议. 

·232· 计 算 机 应 用 研 究 2007 年 了修复链路, 节点增加关 于目的 节点的 序列号, 然后 广播关 于 目的节点的 RREQ。发 起修 复的 节点等 待路 由发 现周 期来 获 得响应的 RREP, 在 本地修 复过 程中 数据 分 组应 该进 行 缓存。 如果路由发现周期结束仍然没有收到关 于目的 节点的 RREP, 则发送关于该目的的 RERR; 另一方面, 如果节点在路由发现期 间收到一个或多个 RREP, 它就更新关于该目的的路由表项。 在 AODV 中, 序列号 的管 理 对于 避免 路 由环 路是 非 常 关 键的。在修复链路时, 发起修复的节点增加关于目的节点的序 列号, 然后广播关于目的的 RREQ。多跳路由 的失效通常 是由 于节点的相对运动或故障导致 的单条 和相邻 的两条 链路断 裂 而引起的, 可以假设两条 不相邻 的链路 是相互 独立的, 也就 是 说, 当单条和相邻的两条 链路断 裂时, 路径上 的其余 部分仍 然 是有效的。路径上靠近目的的 节点可 能仍有 到达目 的的有 效 路由, 但是这些节点 的 路由 表项 中 保存 的目 的 序列 号却 过 时 了, 从而不能对收到的 RREQ 进行应答。通常只有目的节点才 能作出应答, 所以 RREQ 的广播范围必须覆盖目的节点。这种 路由本地修复算法仍需要大范围的泛洪, 这会导致大的控制开 销和长的时延。在现有算法中, 只有当节点比较靠近目的时才 发起路由修复。 2 AODV 本地修复的改进 2. 1 改进的本地修复算法 在原始的 AODV 算法中, RREQ 和 RREP 只保存下一 跳和 前一跳节点的 IP 地址, 节 点中的 路由表 项也 只有 下一 跳节 点 地址。如图 1 所示, 当节点 A 发送数 据分组( 当节 点 A 是源 节 点时) 或者转发数据分组 ( 当节点 A 是中间 节点 时) 到 达目 的 节点 D 时, 节点 A 检查 路由 表。如 果没 有找 到 目的 为节 点 D 的路由表项或者 路由表 项已 经过 期, 则发 送目 的为 节点 D 的 RREQ 消息。如果到节点 D 的路由 表项的 下一跳 节点 B 失 效 或者节点 B 移出节点 A 的通信 范围时, 节 点 A 到 节点 D 的 路 径失效。若节点 A 到节点 D 的距离 比较近, 则发起本 地修复, 广播目的为节点 D 的 RREQ 消 息, RREQ 消息 途 经 节点 E, F 最后到达节 点 D, 然 后由节点 D 发送 RREP 消息, 沿反向路 由 传送到节点 A。这样, 就重新建立了从节点 A 途经节点 E, F 到 节点 D 的路由。 在改进的修复 算法 中, 用 断链 附 近的 节点 替 换失 效 的 节 点, 而路径上的其他节点可以 保留。RREQ 和 RREP 分组还 保 存下两跳和前两跳节点 的 IP 地址, 节点 的路 由表 项中 也增 加 了下两跳节点地址。下两跳节 点是指 在该路 径上的 下一跳 节 点的下一跳; 前两跳节点则是在该路径上的前一跳节点的前一 跳。 如图 1 中的节点 C 是节点 A 的下两跳节点, 而节点 A 是节 点 C 的前两跳节点。 如图 2 所示, 节点 A 发送数据分组或者转发数据分组到节 点 D 时, 节点 A 检查路由表, 如果没有找到目的 为节点 D 的路 由表项或者路由表项已经过期, 则发送目的为节点 D 的 RREQ 消息。当到节点 D 的路由表项的下一跳节 点 B 失效或者 节点 B 运动出节点 A 的通信范围时, 节点 A 到节点 D 的路 径失效, 由节点 A 进行 本 地 修复。 节点 A 并 不直 接 发 送目 的 为 D 的 RREQ 消息, 而是查找节点 A 的目的为 D 的路由表项中的下两 跳节点 C, 如果路由表 项中 下两 跳节 点 C 地 址存 在, 则节 点 A 发送目的为节点 C 的路由修复请求分组 Repair_RREQ。当 Re- pair_RREQ 经过节点 E 到达节点 C, 并且节点 C 到节 点 D 的路 由有效, 则从节点 C 发送路由修复应答分组 Repair_RREP, 经反 向路由通过节点 D 将 Repair_RREP 消息发 送回节点 A。这样, 就重新建立了一条从节点 A 途经节点 E, C 到节点 D 的路由。 如果路由表项中节点 A 的 下一跳 节点 B 和 下两跳 节点 C 同时失效, 则节点 A 发送目的 为节点 D 的 RREQ 消息, 下面的 步骤就与原始的 AODV 本地修复相同了。 从上面 的论述 可以看 出, 由 于节点 C 通常比 节点 D 距 离 节点 A 更近, 所以当节点 A 只有 下一跳 节点失 效时, 修复的 范 围将限制在 A 与 C 之间, 所 以网 络上 传播 的控 制分 组数 量 要 少一些, 寻路时间也短一些。 S 失效 B E A RREPRREQ C F D S C 失效 D A B E Repair_RREQ Repair_RREP 图 1 原 始的 AODV 算法 图 2 改 进的 AODV 算法 2. 2 路由表的改动 路由表中目的节点的 IP 地址域保存所要到达的目的节 点 的 IP 地址, 每个表项都具有不同的目的节点地址, 以此作为 区 别和查找网络路由的关键 字。 目的节 点的序 列号保 存该表 项 的当前目的序列号, 只有在整个移动自组织网中没有对应的比 其更大的目的序列号时才 表示这 条路由 信息是 最新的。下 一 跳节点 IP 地址域保存到达目的节点路径上的下一跳节点的 地 址, 作为转发数据时生 成 IP 分 组的 报头 信息。改 进算 法中 的 路由表项增加了下两跳节 点 IP 地 址域, 保存 到达 目的 节点 路 径上的下两跳节点的地址。当下一跳链路无效时, 若下两跳节 点有效, 则发送本地修复的 路由请 求分组, 目 的地址 就是下 两 跳节点的 IP 地址。 2. 3 RREQ、RREP、RERR 分组的改动以及新增分组 为了使路由本地修复时能 在路由 表中获 得下两 跳节点 的 地址, RREQ、RREP、RERR 分组中分别添加了前两跳节 点的 IP 地址字段, 其他字段均 无变动。另 外, 为 了进行 路由的 本地 修 复, 新增加了本地修复 的路 由请 求分组 Repair_RREQ、路由 应 答分组 Repair_RREP、NOTICE 分组。节点进行本地 修复时, 路 由请求是以下两跳节点( 图 2 中的节点 C) 为目的节点, 但还应 该携带修复的路由的真实目的( 图 2 中的节 点 D) 的信 息。于 是, Repair_RREQ 分组在 RREQ 分 组基础 上添 加了 以下 字段: 真实目的节点的 IP 地址和序列号; Repair_RREP 分组 在 RREP 分组基础上添加了以下字 段: 真实目 的节点 的 IP 地址 和序 列 号, 下两跳节点到达真实目的节点的跳数。 本地修复时, 发起修复的节点( 图 2 中的节点 A) 先将到 节 点 D 的路由设为 无 效, 并 且 将 D 的 目 的 序列 号 加 一, 再 广 播 Repair_RREQ 分组。但是由于 Repair_RREQ 不能到达节点 D, 从而 使得 A 到 C 之间 的 节点 的真 实 目的 节 点的 序列 号 更 新 了, 但 C 与 D 之间的 节点 却没 有得到 更新, 在 以后 的路 由中, 将可能形成环路, 或者 D 发 出的 路由 分组 将由 于序 列号 低 而 无法更新其他节点。为此, 协议增 加了 NOTICE 分组。当节 点 C 收到 Repair_RREQ 分组时, 产生一个 NOTICE 分组并存入 D 

第 3 期 肖 百龙等 : AODV 的 本地 修复 算法 ·332· 的新序列号, 并且将这个分组沿着 C 到 D 的路径发 送, 路 径上 的节点收到此分 组后则 更新 自己 到 D 的新 序列 号, 最后 到 达 D, 使得 D 也能更新自 己的 序列 号, 从而 避免 了以 上问 题。由 于 NOTICE 分组很小, 故增 加的 协议开 销很 少。NOTICE 分 组 格式如表 1 所示。 表 1 NOTICE 分组 格式 type ( 8 bits ) de st ( 32 bits) de stSeq ( 8 bits ) nextHo p ( 32 bits) 其中, type 为分 组 类型; dest 为 需 要通 知 的 目的 节 点; destSeq 为需要通知的目的节点的新序列号; nextHop 为下一跳, 接收方 用于判断该分组是否正确发送。 2. 4 改进的本地修复算法的工作流程 由 于 在 RREQ、RREP 中 添 加 了 前 两 跳 节 点 字 段, 每 个 RREQ、RREP 发送之前 都要 将前 一跳地 址放 入 分组 的前 两 跳 节点字段中。这样下一个节点将知道它的前两跳节点, 由此更 新自 己 到 源 ( 或 者 到 目 的 ) 的 反 向 路 由 ( 或 正 向 路 由) 。 在 RREQ 的 广 播 过 程 中, 节 点 在 收 到 有 效 的 RREQ 之 后, 要 将 RREQ 中的前两跳节点 字段 的值 更新到 该节 点到 源节 点的 反 向路由的下两 跳字 段; 同 样 地, 当 节 点收 到 RREP 之 后, 要 将 RREP 中的前两跳节点 字段 更新 到该 节点 到达 目的 节点 的 正 向路由的下两跳字段。由此则在路由表中增加了下两跳。 增加下两跳的作用主要 是为了 进行路 由的本 地修 复。在 改进的 AODV 协议中, 如图 2 所示, 当 B 失效时, A 先将到 D 的 路由设为无效, 检查目的为 D 的路由表项, 若下两跳 C 存 在且 有效, 则将其目的序 列 号加 一, 以 C 为 目 的节 点 广 播 Repair_ RREQ 分组, 其 TTL 值可以设为 2( 或 3) 。除 C 之外 的节点 都 不对 Repair_RREQ 进行应答。当节点 C 收到 Repair_RREQ 分 组时, 产生一个 Repair_RREP 分 组, 同 时还 产 生 一个 NOTICE 分组并存入 D 的新序列 号, 并 且将这 个分组 沿着 C 到 D 的 路 径传送。此路径上的节点收到 NOTICE 分组时, 则更新其 路由 表项 中 D 的新 序列 号, 最后 到达 D, D 也 更新 自己 的序 列号。 当节点 A 收到 Repair_RREP 时, 则 更新 其到 D 的路 由。若 下 两跳不存在, 或者存在但无效, 则节点 A 向 D 发送 RREQ, 从而 回到原始 AODV 协议的本地修复过程。 3 仿真及分析 3. 1 仿真环境和性能评估参数 本仿真实验是为了比较改进的 AODV 路 由协议 和原始 的 AODV 路由协议的 性能, 采 用网 络仿 真软 件 OPNET 8. 1。120 个节点在 1 500 m×2 000 m的 区域内 随机移 动, 采用 Random Way-Point 移动模型 [ 10] 。节点在所规定 的网络范围 内, 随机 选 择一个目的位置, 然后以速度 V 向目的位置运动, 到达该点后, 暂停一个等待时间( T_pause, 设 为 30 s) , 再 向下 一个 目的 位 置移动, 如此反复。为了考查网络在不同的拓扑变化情形下协 议的 性 能, 仿 真 取 了 四 个 场 景, 速 度 V 分 别 设 为 5、10、15、 20 m/ s。选择 30 个节点产 生数据 流, 流持 续、空闲 的时 间分 别 服从均值为 30 s, 5 s 的指 数分布, 每秒 产生八 个数 据分 组, 每 个数据分组为 128 Bytes, 向 随机 选 择的 一个 目 的发 送。节 点 传输 距 离 为 300 m, MAC 层 使 用 802. 11 协 议, 仿 真 时 间 为 600 s。收集的仿真参 数 [ 11] 包括数据成 功接收率、平均端 到端 时延以及协议开 销, 其 中协 议开 销 分别 按字 节 数和 分组 数 计 95 90 85 80 75 70 65 5 0.24 0.22 0.2 0.18 0.16 0.14 0.12 0.1 5 算。协议开销是指网络中传输的 控制分组的 字节( 分组) 数 与 所有分组的字节( 分组) 数的比值。 3. 2 仿真结果及性能分析 图 3 给出了在 不同 节点 运 动速 度 下的 数据 成 功 接收 率。 很明显, 在所有的移动场景下, 改 进后的 AODV 协议 性能均 优 于原始的协议。另外, 随着 速度的 增加, 改进的 协议性 能比 原 始协议下降得慢一些, 这显示它能更好地适应拓扑快速多变的 环境。因为改进的修复算法将操作限制在断链的局部范围内, 从而不用考虑断链在整条路 径上的 相对位 置, 均可进 行修复, 提高了处理失效链路的能力, 故因没有找到路由而丢弃的数据 分组和缓存内的数据分组更少, 从而明显地提高了数据成功接 收率。 图 4 给出了协议改 进前后 的平均 端到端 时延, 可以 看出, 协议改进之后, 平均端 到端时 延也下 降了。由分 析可知, 由 于 改进的路由修复 算法 限 制了 修复 的 范围, 修 复 所需 的时 间 更 短, 缓存的数 据就能更快 地发送出去, 从而降 低了时延; 另外, 正常接收到的分 组时 延很 小( 毫 秒级) , 而由 于改 进后 的协 议 成功接收的数据分组更多, 这些多接收到的分组是在路由修复 之后收到的, 时延比较大, 对平均值的影响大, 从而实际的性能 改善其实更好一些。 改进前 AODV 改进后 AODV 改进前 AODV 改进后 AODV 0.220.210.20.190.180.170.160.150.140.130.12 10 15 20 5 10 15 20 图 4 平均 端到 端时延 节点运动速度渊m/s冤 节点运动速度渊m/s冤 图 3 数 据成 功接收 率 图 5, 图 6 显示了改进前后协议 的控制开销。由 于改进 的 协议增加了控制分组的长度和新的分组, 但通过限制修复的范 围却可以减少控 制分 组 的数 量, 这 两个 因素 都 会影 响控 制 开 销。当节点移动较慢时( 5 m/ s) , 断链 较少发 生, 路由 很少 需 要修复, 但因为控制分组字段的增加使得改进后的协议字节开 销增加了, 不过此时的分组 开销却 降低了, 即 减少了 控制分 组 的数量。随着节点运动速度 的增加, 链路 更加频 繁地断 开, 修 复的次数相应增加了, 改进的修复算法就更能发挥其优越性。 改进前 AODV 改进后 AODV 10 15 节点运动速度渊m/s冤 图 5 协 议比 特开销 0.48 0.46 0.44 0.420.4 0.38 0.360.34 0.320.3 5 20 改进前 AODV 改进后 AODV 20 15 10 节点运动速度渊m/s冤 图 6 协 议分 组开销 4 结束语 本文对 AODV 路 由 协 议 的 本地 修 复 算 法 做 了 很 大 的 改 动, 提出了新的路由本 地修复 算法。在原 始路由 协议中, 本 地 修复的意义就在于将修复限定在出错的节点和目的节点之间, 而尽量不涉及源节点, 且只有当失效链路离目的节点较近时才 对路由进行修复, 否则通知源节点重新路由。 ( 下转 第 237 页 ) 

第 3 期 王红 剑等: 一 种基 于 DNMAI 架构 的网 络拓 扑发 现方 法 ·732· ( 3) 由于绘图 程序 模 块生 成的 是 BMP 格式 的图 形 文件, 体积较大, 不利于在网络传输, 在程序最 后引入了 CxImage 库, 该库能将输出结果保存为 增强图 元文件 的格式。这 种文件 特 别适合于存储网络拓扑这种体积巨大而画面简单的图形, 如存 储一个398 ×1 280的拓扑 图大 约只 需十 几 KB, 能够 快速 方 便 地回显与放缩。 6 拓扑发现程序的测试实例 6. 1 测试环境选择与部署 测试环境选择了实验室内的网络测试平台, 该平台包括了 若干支持 SNMP 的路由器、交换 机和主 机设备, 可 根据 要求 组 建不同的网络拓扑结构。为方便测试, 网内所有支持 SNMP 的 设备, 设置了统一的 Community 名和密码。运行在网络测 试平 台上的 DNMAI 客户端参数设置界面如图 5 所示。 6. 2 测试结果 在测试时, 分别采用了对不同拓扑结构的网络进行拓扑发 现, 以及对同一拓扑结构的不同探测起点发起拓扑探测等多种 方案。结果证明, 本文提 出的方 法能准 确、高 效地发 现网络 拓 扑结构, 绘制出完整的拓 扑图形, 能较 好地满 足实际 网络管 理 的需求。部分探测结果如图 6 所示。 图5 DNMAI 测试参数设置界面 图 6 测试网络拓扑图 7 结束语 网络拓扑发现是随网络大 规模应 用和普 及而兴 起的一 项 研究课题。本文在对现有的网 络拓扑 发现算 法存在 的不足 进 行了分析之后, 提出了一种新型的基于 DNMAI 的实现方法, 既 注重具体实现的性能要求, 又考 虑了拓 扑信息 的扩展 和复用, 应用简便且易实现。由于 在实际 网络中 可能 存在 对 SNMP 的 管理权限限制, 此类网络 并不完 全适用 于本文 所提出 的方法。 下一步的 工 作 就 是 实 现 将 该 方 法 与 DNMAI 中 已 有 的 基 于 UDP 的拓扑探测模 块 [ 3] 相 结合, 以 适应 更广 泛 的网 络应 用 需 求。 参考文献: [ 1] ALVIN J. Administrative model for version 2 of SNMP( SNMPv2 ) [ DB/ OL] . [ 1993- 04 ] . http: / / www. ietf. org / rfc. html. [ 2] POSTEL J. Internet control message protocol[ DB/ OL] . [ 1981 - 09] . http: / / www. ietf. org / rfc. html. [ 3] 朱畅华 , 裴昌幸 , 李 建东 , 等 . 分 布式 网 络 测 量 与分 析 基 础 架构 研 究与实 现[ J] . 北京邮 电大 学学报 , 2004 , 27( Z1) : 25- 31 . [ 4] LIN Hwa-Chun, LAI Hsin-Liang, LAI Shou-Chuan. Automatic link layer topology discovery of IP networks: ICC’99: proceedings of IEEE International Conference on Communications Vancouver[ C] . [ S. l. ] : [ s. n. ] , 1999: 1034-1038 . [ 5] BRUCE L, DAVID O, THOMAS G. Topology discovery for large e- thernet networks: proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communica- tions[ C] . San Diego: [ s. n. ] , 2001: 237- 248 . [ 6] 赵欣, 晏 蒲柳, 郭成 城, 等. 基于 Web 技术 的 网络 拓 扑图 生 成方 法 研究[ J] . 武 汉大学 学报 : 理 学版, 2002( 5 ) : 631- 634. ( 上 接第 233 页) 而改进之 后的 算法 则完 全诠释 了局 部的 意义, 发起修复的节点向其下两跳节点发起修复过程, 把修复限定在 了失效链路的附近, 范围更小, 处理时间更短, 从而也无需考虑 失效链路在整个路由上的相 对位置, 均 可进行 修复, 提高了 处 理失效链路的能力。此外, 改进的本地修复算法的控制开销和 时延都与网 络的 规 模无 关。当网 络 规模 越 大, 路由 的跳 数 越 多, 改进的路由本地修复 算法就 越有其 优越性, 从而 有利于 提 高移动 Ad hoc 网的可扩展性 [ 12] 。 参考文献: [ 1] LAUSEN T, P JACQUET. Optimized link state routing protocol n. ] , 2003. [ 6] DAVID B J, DAVID A M, HU Y C. The dynamic source routing pro- tocol for mobile Ad hoc networks ( DSR) , IETF Internet Draft, draft- ietf-manet-dsr- 09. txt[ R] . [ S. l. ] : [ s. n. ] . [ 7] PARK V, CORSON M. A highly adaptive distributed routing algo- rithm for mobile wireless networks [ C] . Kobe: IEEE INFOCOM, 1997: 1403-1405. [ 8] GUI C, MoHAPATRA P. SHORT: Self-healing and optimizing rou- ting techniques for mobile ad hoc networks: Proceedings of the 4 th ACM International Symposium on Mobile Ad hoc Networking and Computing, Annapolis[ C] . [ S. l. ] : [ s. n] , 2003: 279- 290. ( OLSR) , IETF RFC 3626[ R] . [ S. l. ] : [ s. n. ] , 2003. [ 9] LIU G P, WONG K J, et al. PATCH: A novel local recovery mecha- [ 2] MURTHY S, GARCIA-LUNES, ACEVES J. An efficient routing pro- nism for mobile Ad hoc networks: proceedings of the IEEE Vehicular tocol for wireless networks[ J] . ACM Balzer M obile Networks and Technology Conference[ C] . [ S. l. ] : IEEE VTC, 2003: 2995- 2999 . Applications Journal, Special Issue on Routing Communications [ 10] BROCH J, MALTZ D A, JOHNSON D, et al. A performance compari- Networks, 1996, 1( 2 ) : 183 -197. son of multi-hop wireless Ad hoc network routing protocols, Dallas: [ 3] OGGIER R, TEMPLIN F, LEWIS M. Topology dissemination based Proceedings of MOBICOM[ C] . [ S. l. ] : [ s. n. ] , 1998: 85- 97 . on reverse-path forwarding ( TBRPF) , IETF RFC 3684[ R] . [ S. l. ] : [ 11] CORSON S, MACKER J. Mobile Ad hoc Networking ( MANET) : [ s. n. ] , 2004. routing protocol performance issues and evaluation considerations, [ 4] 臧婉 瑜, 于勐, 谢立 , 等. 按需 式 Ad hoc 移 动网 络路由 协议的 研究 IETF RFC 2501[ R] . [ S. l. ] : [ s. n. ] , 1999. 进展 [ J] . 计 算机 学报, 2002, 25( 10) : 1009-1017. [ 12] HONG Xiaoyan, XU Kaixin, GERLA Mario. Scalable routing protocol [ 5] PERKINS C, BELDING-ROYER E, Das S. Ad hoc on-demand dis- for mobile Ad hoc networks[ J] . IEEE Network, 2002, 16( 4) : 11- tance vector ( AODV) routing, IETF RFC 3561 [ S] . [ S. l. ] : [ s. 21.