第 ４３ ２０１２ 卷 年 第 月 期 ５ 　　 　 ９ 太 原 理 工 大 学 学 报 　 ＪＯＵＲＮＡＬ　ＯＦ　ＴＡＩＹＵＡＮ　ＵＮＩＶＥＲＳＩＴＹ　ＯＦ　ＴＥＣＨＮＯＬＯＧＹ 　 Ｖｏｌ．４３ Ｎｏ．５ 　 Ｓｅｐ．２０１２  文章编号：１００７－９４３２（２０１２）０５－０５８７－０４ 　 贪婪周边无状态路由转发算法 的分析及改进 ＧＰＳＲ 王丽娟ａ，梁海涛ａ，秦建敏ｂ，任新华ｃ 太原理工大学 （ 计算机学院 ａ． 测控技术研究所 ；ｂ． 信息化管理与建设中心 ；ｃ． 太原 ， ０３００２４） 　 摘 要：分 析 了 贪 婪 周 边 无 状 态 路 由 算 法 ＧＰＳＲ（Ｇｒｅｅｄｙ　Ｐｅｒｉｍｅｔｅｒ　Ｓｔａｔｅｌｅｓｓ　Ｒｏｕｔｉｎｇ），并 对 其缺陷进行了改进。利用 ＧＰＳＲＩ（ＧＰＳＲ－ Ｉｍｐｒｏｖｅｄ），并对两 种 算 法 的 传 输 时 延，转 发 跳 数 等 重 要 参 数 进 行 了 比 较；验 证 了 改 进 的 算 法 能更有效地传输数据。该算法降低了传输时延，减少了转发跳数，实现了多路径数据传输， ＧＰＳＲＩ 保证了网络数据传输的可靠性；有效地解决了 算法中出现的空洞（ｖｏｉｄ）问题。 网络模拟平台仿真实现了 算法及改进的算法 ＧＰＳＲ ＧＰＳＲ ＮＳ２ 关键词：贪婪周边无状态路由算法；时延；跳数；空洞 中图分类号：ＴＰ３１２　　　 文献标识码：Ａ ３ 传感器网络系统［１］由 汇聚节点和管理节点 、 　　 节点 。 机部署在监测区域内部或附近 方式构成无线传感器网络 。 按照一定的路由协议或算法 节点进行传输 点处理 通过互联网或卫星通信网络到达管理节点 种节点构成 包括传感器 ， 诸多的传感器节点被随 这些节点通过自组织 ， 传感器节点监测的数据 ， 逐跳地沿着其他传感器 ， 在传输过程中传感数据可能被多个节 ， 然后 ， 数据在经过多跳路由后到达汇聚节点 ， 。 。 ＲＩＰ ＯＳＰＦ 由于无线电射程有限 网络中 转发 态等路由算法 优先算法 移动无 线 传 感 器 网 络 是 哈 佛 大 学 的 在完全由无线设备构成的 ， 从源节点到目的节点的通讯需要多跳节点的 ， 在有线网络中 链路状 可以采用的距离向量 ， ， 和最短路径 例如 路由信息协议 ： （ 不再适用于网络拓扑变化很快的 等 ） 贪 婪 周 边 无 状 态 路 由 算 法 于 年提出来的一种适用于无线数据报网络的基于 ２０００ 该算法使用诸多构成 地理位置的新型路由算法［２］。 无线传感器网络的路由器节点的位置以及数据包的 算法 分 目的地址来决策数据包的转发路径 为两个模式 贪婪转发模式和周边转发模式 ： 。ＧＰＳＲ 。 Ｈ．Ｔ．Ｋｕｎｇ Ｂｒａｄ　Ｋａｒｐ ＧＰＳＲ， 和 。 １　ＧＰＳＲ 算法剖析 １．１　ＧＰＳＲ ＧＰＳＲ 算法基本思想 路由算 法 使 用 贪 婪 转 发 算 法 建 立 路 由 。 。 贪婪转发算法是节点选择邻居节点中距离目的节点 最近的节点作为下一跳路由转发节点 当节点发现 自己到目的节点的距离比自己的邻居节点到目的节 即 无 线 传 感 器 网 络 中 出 现 了 本 地 点的距离都短时 ， 算 最小化问题 法将从贪婪转发模式进入到 边 缘 转 发 模 式 算法中构造平面图 的 方 法 是 删 除 网 络 中 交 叉 的 边 主要 的 平 面 化 算 法 有 也称为空洞 ， 现 象［２］时 。ＧＰＳＲ ， （ｖｏｉｄ） ，ＧＰＳＲ 和 ＧＧ（Ｇａｂｒｉｅｌ　Ｇｒａｐｈ） ＲＮＧ （Ｒｅｌａｔｉｖｅ　Ｎｅｉｇｈｂｏｒｈｏｏｄ　Ｇｒａｐｈ）。 ＲＮＧ［２］的算法定义 如 下 ：ＲＮＧ 间存在 边 的 条 件 是 对 于 任 意 的 一 个 节 点 的距离要小于或等于 最大值 ｖ 用公式表示为 或是 到 到 ｗ ｕ ｗ 中 节 点 之 ｕ，ｖ 到 ｗ，ｕ ｖ 的 距 离 的 。 ： ｗ ≠ｕ，ｖ：ｄ（ｕ，ｖ）≤ ｍａｘ［ｄ（ｕ，ｗ），ｄ（ｖ，ｗ）］． 中的节点 （１） 之间存在 为直径的圆中没有其他节 ｕ，ｖ ：ＧＧ 　　ＧＧ［２］的定义如下 边的条件是在以 点 用公式表示为 ｄ（ｕ，ｖ） 。 ： ｗ ≠ｕ，ｖ：ｄ２（ｕ，ｖ）＜ ［ｄ２（ｕ，ｗ）＋ｄ２（ｖ，ｗ）］． 算法缺陷 （２） １．２　ＧＰＳＲ 的特点 根据 下的缺陷 发送数据包都需要 进 行 平 面 化 ＧＰＳＲ 单路径会使得节点能量容易被耗尽 ： 主 要 有 以 每次 ； 边 缘 转 发 的 路 径 会 我们发现 ， ＧＰＳＲ ， ＊ 　　　 　　　 收稿日期：２０１２－０４－２０ 基金项目： 作者简介： 山西省留学回国资助项目 王丽娟 女 （１９７５－）， （２０１１－０２９）； 山西繁峙人 ， 在读博士 ， 山西省人力资源和社会保障厅留学回国择优科技资助项目 讲师 ， 主要从事计算机网络及网络安全研究 ， ，（Ｔｅｌ）１３９３４６６３６３４ 中国煤炭期刊网 www.chinacaj.net

８８５ 太 原 理 工 大 学 学 报 　　　　　　　　　　　　　　　　　　 第 卷 　 ４３ 很长 并且大多数情况都不是最佳的 ， 。 ２　ＧＰＳＲＩ 算法剖析 ２．１　ＧＰＳＲＩ 基本思想 算法在 ＧＰＳＲ 算法基础上 最 终 ＧＰＳＲＩ 并且针对其 缺 点 进 行 了 改 进 ， 保留了其优 ， 算 法 点 并 增 加 了 路 径 优 化 和 找 寻 节 点 不 改进了贪婪转发 ， 算 法 的 主 要 功 能 分 为 相关多路 径 的 功 能 四个部分 。ＧＰＳＲＩ ＧＰＳＲＩ 所示 ， 如图 ， １ 。 图 网络收敛 １　ＧＰＳＲＩ 功能结构图 ２．１．１　 ， 包 包 时 Ｈｅｌｌｏ 会 更 新 自 己 的 路 由 表 无线 传 感 器 网 络 中 的 每 一 个 节 点 定 期 发 送 包中包含节点的位置信息 当它的一 跳 邻 ， ， Ｈｅｌｌｏ 若 居节点收到 路由表中存在发送 包 节 点 的 信 息 则 只 需 更 新 它 的 位置信息 若路由表不存在 则要将节点的信息插入 ； ， 到路由表 中 若 路 由 表 中 的 信 息 长 时 间 得 不 到 更 则认为此条目对 应 的 节 点 离 开 了 本 节 点 的 传 输 新 ， 此时需要把这个条目删除 范围 节点 ， ， 。 时刻了解周围一跳 的 网 络 拓 扑 使 网 络 处 于 收 敛 状 态 通过此过程 如图 所示 。 。 ， ， 。 ２ 。 图 ２　 网络收敛 贪婪转发 ２．１．２　 。 。 ， 第一次发送数据包时 下 一 跳 节 点 收 到 数 据 包 后 节点收到数据包后 ， 则会把数据包发回上一跳节点 ， 会挑 ， 选路由表中距离目的节点最近的一跳邻居节点作为 下一跳进行转发 也 会 若路由表 从自己的路由表中选择最近的进行转发 为空 上一跳节点收 ， 知道从 距 离 目 的 节 点 最 近 的 邻 居 节 点 到数据包后 ， 不能将数据包转发到目的节点 并 ， 选择剩下的距离目 的 节 点 最 近 的 作 为 下 一 跳 这 个 此时要将数据包发 过程重复进行 直至路由表为空 ， ， 回至上一跳节点 另一种情况是将数据包成功地转 发到 可 以 到 达 目 的 节 点 的 一 跳 邻 居 节 点 了 所示 它会删除此条目 ， 如 图 ， 。 ， 。 贪婪转发算法在本文中的改进策略为 ３ 一个节 ： 图 ３　 贪婪转发 。ＧＰＳＲＩ 点会选择路由表中最接近目的节点的节点为下一跳 由转发 节 点 中的贪婪转发是有 区 别 的 法 点更远 ＧＰＳＲ 不 同 之 处 在 于 改 进 的 算 下一跳节点可以比本节点距离目的节 ， 算 法 中 的 贪 婪 转 发 和 ＧＰＳＲＩ 中 ， 。 路径优化［３］ ２．１．３　 转发过数据包的节点 会监听邻居节点的信息 ， 。 若听到自己刚发出的数据包由下一跳节点转发到了 自己下一次转发数 自己的另外一个邻居节点 ， 据就选取该邻居节点作为下一跳节点转发 这样优 化了路径 使以后的数据包按照优化的 ， 路径发送 缩短了跳数 ， 大大提高传输效率 ， 那么 ， 如图 ， 所示 。 。 ４ 图 ４　 路径优化及多路径实现 ， 在贪婪转发阶段 假设从包的报头信息 ， 点发出的包 是它先前转发过的包还是发送端当前转发的包 在节点 如 ： 如果稍后 可以马上得出 每个节点要监听它周围的节 节点可以鉴别出 ， 例 。 发送一个数据包后 ， 转发了相同的包 则 ， 是捷径 向它的邻居节点 听到另一个邻居 对于这一特定连接 ： 到 Ｉ Ｊ Ｉ Ｋ 。 ，Ｉ Ｋ ２．１．４　 节点不相关多路径 。 ， 若未优化 以后传输数据包时 节点会按照优化的路径进 行传输 则会按照原来找到的路径传输 ， ， 而那些不在传输路径上的节点会监听邻居节点是否 则将 转发数据包 若监听有转发数据包的邻居节点 ， ， 自己路由 表 中 与 这 些 节 点 相 对 应 的 条 目 删 掉 这 样 其路由表中不存 ， 当 传 输 路 径 上 的 节 点 传 输 数 据 在已经使用的节点 对于不在传输路径包含的节点 ， 。 ， 中国煤炭期刊网 www.chinacaj.net

第 期 ５ 　 　　　　　　　　　　　 王丽娟 等 ， 贪婪周边无状态路由转发算法 ： ＧＰＳＲ 的分析及改进 ９８５ 不会将数据转发到已经使用的节点 ， 包时 到 的 路 径 不 会 包 含 已 使 用 过 的 节 点 这样再找 ， 多 次 使 用 就 可 以 找 见 多 条 节 点 不 相 关 的 路 径 ， ， ＧＰＳＲＩ 如图 ７ 算 法 所示 ， 。 ３　ＧＰＳＲＩ 算法详细分析 如图 所示 为 源 节 点 ５ ： 在具体的网络中 为 目 的 节 点 ， ，Ｄ 是这样 传 输 的 ， 的 传 ， 虚 线 圆 为 Ｓ 其中 Ｓ 输半径 ： 图 步骤 ２ ６　 步骤 如图 １： 会收到 包 ，Ｓ Ｃ、Ｆ、Ａ ｌｏ 的信息写入或更新路由表 点会随机移动 若 ： 动到外部 Ｉ 长时间收不到 例如 。 ，Ｓ 已经离开了 １ 图 ８ ５　 所示 ＷＳＮ 的特性 并将 ， 步骤 图中各节点定期发送 ， 发送的数据包 但由于 ， 从 Ｈｅｌ－ Ａ、Ｆ、Ｃ 节 ， 的 传 输 范 围 内 部 移 则可推断 ， 对 应 的 条 每 个 节 点 都 接 收 到 邻 居 节 点 的 信 ， 这样网络中的每个节点都 ， 节 点 根 据 这 一 跳 邻 Ｓ 的位置信息 于 是 删 除 Ｉ 的 传 输 半 径 Ｉ ， Ｓ 一段时间后 。 并更新自己的路由表 ， Ｉ 目 息 知道自己最新的一 跳 邻 居 信 息 居节点信息进行转发 ， ， ６ ２： 步骤 如图 其中 是源 首先会选择距离目 的 节 点 最 近 的 邻 居 择 上一跳 ，Ｓ 又 会 选 转发数据包的时候发现除了 收到 它会发回到 作为下一跳 是 目 的 Ａ，Ａ 但 ， ，Ｄ 当 Ｂ Ｓ Ｂ 。 所示 Ｂ Ｓ Ａ 返回的信息 的其他邻居节点 无其他的邻居 知道通过 ， Ｂ 的 他就会删 除 ， 有除 到同样 会 删 除 路由表中选 择 距 离 择转发数据包的下 一 跳 的节点最近的 照 Ｓ、Ｃ、Ｅ、Ｆ、Ｇ、Ｈ、Ｄ， Ａ Ｄ 。 对 应 的 条 目 对 应 的 条 目 ， Ａ， Ａ 是不能到达目的节点 。 Ｂ ，Ａ 同 理 也会把数据包发回 ， Ｄ 也 发 现 没 收 会 在 剩 余 的 一 个 节 点 选 是 选 择 邻 居 节 点 中 距 离 目 最终会按 之 后 最 近 的 节 点 ，Ｓ Ｃ。 Ｓ，Ｓ 数据包从 ， ， ， Ｓ， 到达目的节点 当数据包发送到 。 时 如图 步骤 ３： 的邻居节点 Ｃ 将自己的下一跳从 Ｆ ７， 在发送之前 变为 Ｃ Ｓ→Ｆ， →Ｅ→Ｆ 改为 缩短了条数 Ｆ， Ｆ ，Ｓ 转发的数据包 Ｃ 这样转发路径由 优化了路径 ， 。 监听到 就会 ， Ｓ→Ｃ 根据此原则 步骤 如图 ４： １１， Ｆ→Ｇ→Ｈ→Ｄ 径上的节点 己路由表中 Ｅ， Ｇ、Ｈ 形成 了 空 洞 Ｇ、Ｈ 当再次运行 ７　 步骤 图 以后发送数据报都会按照 ３ 的 路 径 进 行 数 据 包 转 发 。 在 发 送 数 据 包 听 到 Ｆ，Ｇ Ｓ→ 不 在 此 路 会 删 除 自 ， 对 应 的 路 由 表 条 目 这 样 使 得 ， 其 他 节 点 发 现 不 了 他 们 Ｆ、 ， （ｖｏｉｄ）， 算法时 ＧＰＳＲＩ 的路径进行转发 会按照 ， 虽然是 Ｓ→Ｃ→Ｅ→Ｊ→ 中距离目的 。Ｇ Ｅ Ｄ 可 是 在 刚 才 的 处 理 过 程 中 已 经 将 ， 可以保证查找到的 ， 所以通过这种删除机制 ， Ｋ→Ｄ 最近的邻居节点 其删除 路径是节点不相关的 。 图 ８　 ，ＧＰＳＲＩ 步骤 算 法 成 功 地 找 到 了 ４ 由图 ９ 可 知 和 →Ｇ→Ｈ→Ｄ Ｓ→Ｃ→Ｅ→Ｊ→Ｋ→Ｄ 不相关的路径 并 且 对 路 径 进 行 了 优 化 ， 优化 只可找到 ， 径 由此看见 ， Ｓ→Ｃ→Ｅ→Ｆ→Ｇ→Ｈ→Ｄ 路径优化还可提高找到路径的条数 ， 。 Ｓ→Ｆ 这 两 条 节 点 假 设 没 有 这一条路 。 模拟仿真 ４　 ４．１　ＮＳ２ 介绍 ＮＳ２［４］［５］是一种面向对象的网络仿真器 本质上 ， 中国煤炭期刊网 www.chinacaj.net

０９５ 太 原 理 工 大 学 学 报 　　　　　　　　　　　　　　　　　　 第 卷 　 ４３ ９　 多路径 由 开发而成 。 。 所有的仿真都由离散事件驱 ， ＵＣ　Ｂｅｒｋｅｌｅｙ 可以用于仿真各种不同的 网 。 ＩＰ 图 是一个离散事件模拟器 它本身有一个虚拟时钟 动的 目前 。 ＮＳ２ 与 的比较 ４．２　ＧＰＳＲ ＧＰＳＲＩ 实验结果如图 对两种算法 发 送 ， 从图中我们可以清晰地看到 ， １０，１００ 络中 计 更小的 时 延 １００ 个 无 线 传 感 器 节 点 的 网 个 数 据 包 的 时 延 进 行 统 有 从 （ 得到 ＧＰＳＲＩ ＧＰＳＲ 比 ， 。 我 们 改 变 节 点 数 从 ２００ 了节点不相关的多路径的不同值 中 在 图 改变传输半径 ６０～１１０ ｍ）， 。 １　０００）， １０－ｂ 到 （ 和 ＧＰＳＲＩ 有 效 解 决 了 本 地 最 小 化 问 题 ＧＰＳＲ ＧＰＳＲＩ 的优点 算 法 比 较 的 仿 真 实 验 结 果 显 改进了有效的数据 ： 即 空 洞 问 （ 找 到 节 点 不 从而 有 效 保 证 网 络 传 输 的 可 靠 性 以 ， 示出了改进算法 传输速率 题 相关的多路径 及网络负载的均衡性 降低了传输时 延 和 路 由 转 发 跳 数 ）； ； ； 。 图 １０　ＧＰＳＲ 与 时延比较图 ＧＰＳＲＩ 结束语 ５　 ＧＰＳＲ 笔者 对 进 行 了 简 述 并使用 ， 证实了 ， 进行了详细剖析 ＧＰＳＲＩ 对两种算法进行了比较 有效数据传输速率 少数据传输时延和 路 由 转 发 跳 数 的多路径等方面较 ， ＮＳ２ 对 改 进 后 的 算 法 网络模拟平台 算法在提高 减 、 寻 找 无 相 关 节 点 ＧＰＳＲＩ 、 解决空洞和网络平面化问题 、 ＧＰＳＲ 算法有更佳的表现 。 参考文献： ［１］　 ［２］　Ｋａｒｐ　Ｂ，Ｋｕｎｇ　Ｈ　Ｔ．ＧＰＳＲ：ｇｒｅｅｄｙ　ｐｅｒｉｍｅｔｅｒ　ｓｔａｔｅｌｅｓｓ　ｒｏｕｔｉｎｇ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ［Ｃ］∥Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ａｎｎｕａｌ　ｉｎｔｅｒ－ 无线传感器网络 ． 清华大学出版社 孙利民等编著 ，２００５：４－５． ［Ｍ］． 北京 ： ｎａｔｉｏｎａｌ　ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｍｏｂｉｌｅ　ｃｏｍｐｕｔｉｎｇ　ａｎｄ　ｎｅｔｗｏｒｋｉｎｇ （ＭｏｂｉＣｏｍ　２０００），Ｂｏｓｔｏｎ，ＵＳＡ，Ａｕｇｕｓｔ．３． 等 ［３］　ＬｅｉＳｈｕ，ＹａｎＺｈａｎｇ，Ｌａｕｒｅｎｃｅ　Ｔ， ．Ｙｕ　Ｗａｎｇ．ＴＰＧｆＦ：ｇｅｏｇｒａｐｈｉｃ　ｒｏｕｔｉｎｇ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｍｕｌｔｉｍｅｄｉａ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｃ］∥ Ｓｐｒｉｎｇｅｒ　Ｓｃｉｅｎｃｅ＋Ｂｕｓｉｎｅｓｓ　Ｍｅｄｉａ，ＬＬＣ，２００９． ［４］　Ｔｈｅ　Ｎｅｔｗｏｒｋ　Ｓｉｍｕｌａｔｏｒ－ｎｓ－２［ＥＢ／ＯＬ］，ｈｔｔｐ：∥ ｗｗｗ．ｉｓｉ．ｅｄｕ／ｎｓｎａｍ／ｎｓ／．２００６．１０．２５ ［５］　Ｎｓ２．３４ｉｎｓｔａｌｌａｔｉｏｎ　ｈｅｌｐ　ｉｎ　Ｕｂｕｎｔｕ１０．１０［ＥＢ／ＯＬ］ｈｔｔｐ：ｗｗｗ．ｌｉｎｕｘｑｕｅｓｔｉｏｎ．ｏｒｇ／ｑｕｅｓｔｉｏｎｓ／ｕｂｕｎｔｕ－６３／ｎｓ－２．３４－ｉｎｓｔａｌｌａｔｉｏｎ－ ｈｅｌｐ－ｉｎ－ｕｂｕｎｔｕ－１０－１０－ａ－８６８６６９ Ａｎａｌｙｓｉｓ　ａｎｄ　Ｉｍｐｒｏｖｅｍｅｎｔ　ｏｆ　ｔｈｅ　Ｒｏｕｔｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ＧＰＳＲ ＷＡＮＧ　Ｌｉｊｕａｎ，ＬＩＡＮＧ　Ｈａｉｔａｏ，ＱＩＮ　Ｊｉａｎｍｉｎ，ＲＥＮ　Ｘｉｎｈｕａ （Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ｏｆ　ＴＵＴ； Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｍｅａｓｕｒｅｍｅｎｔ　ａｎｄ　Ｃｏｎｔｒｏｌ　ｏｆ　ＴＵＴ； Ｃｅｎｔｅｒ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｍａｎａｇｅｍｅｎｔ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ＴＵＴ，Ｔａｉｙｕａｎ０３００２４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｅｄ　ａ　ｂｒｉｅｆ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ａｎｄ　ａｎａｌｙｓｉｓ　ｏｆ　ＧＰＳＲ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ａ－ ｃｈｉｅｖｅｄ　ｔｈｅ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ＧＰＳＲＩ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｆｏｒ　ｔｈｅ　ｔｗｏ　ａｌｇｏ－ ｒｉｔｈｍ　ｗｅｒｅ　ｓｉｍｕｌａｔｅｄ　ａｎｄ　ｃｏｍｐａｒｅｄ　ｖｉａ　ＮＳ２ｎｅｔｗｏｒｋ　ｓｉｍｕｌａｔｉｏｎ　ｐｌａｔｆｏｒｍ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ ＧＰＳＲＩ　ａｌｇｏｒｉｔｈｍ　ｂｅｈａｖｅｄ　ｂｅｔｔｅｒ　ｔｈａｎ　ＧＰＳＲ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｔｅｒｍｓ　ｏｆ　ｉｍｐｒｏｖｉｎｇ　ｄａｔａ　ｔｒａｎｓｆｅｒ　ｒａｔｅ， ｓｏｌｖｉｎｇ　ｔｈｅ　ｖｏｉｄ　ｐｒｏｂｌｅｍ，ｒｅｄｕｃｉｎｇ　ｔｒａｎｓｆｅｒ　ｄｅｌａｙ　ａｎｄ　ｈｏｐ　ｃｏｕｎｔ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅ　ｉｍｐｒｏｖｅｄ ＧＰＳＲＩ　ａｌｇｏｒｉｔｈｍ　ｆｏｕｎｄ　ｍｕｌｔｉｐｌｅ　ｎｏｄｅ－ｄｉｓｊｏｉｎｔ　ｐａｔｈｓ　ｗｈｉｌｅ　ｔｈｅ　ＧＰＳＲ　ａｌｇｏｒｉｔｈｍ　ｃｏｕｌｄ　ｎｏｔ． Ｋｅｙ　ｗｏｒｄｓ：ＧＰＳＲ；ｄｅｌａｙ；ｈｏｐ；ｖｏｉｄ 编辑 （ 刘笑达 ： ） 中国煤炭期刊网 www.chinacaj.net