概述

GPSR 是一种经典的无线自组织网络或中使用的无状态地理路由协议。它的核心思想非常简单：利用节点的物理位置信息来转发数据包，而不是维护传统的、基于地址的路由表。

  • 无状态：路由器（节点）不需要维护到所有可能目的地的路由表。这大大减少了协议的开销和内存占用，特别适合资源受限的网络（如传感器网络）。
  • 地理路由：每个节点都知道自己的地理位置（例如通过内置 GPS 接收器或其它定位算法），并且假设数据包的最终目的地位置是已知的。节点在转发数据包时，只依赖邻居节点的位置信息和目的地的位置来做决策。

核心工作原理

GPSR 主要使用两种数据包转发模式，并根据网络情况在它们之间智能切换：

  1. 贪婪转发 - 默认模式，在节点密集区域非常高效。
  2. 周边转发 - 恢复模式，当贪婪转发失败时（遇到“空洞”时）使用。

贪婪转发

这是 GPSR 的首选和主要模式。

基本思想

每个中间节点都试图将数据包转发给地理上最接近最终目的地的邻居节点。

工作流程

  1. 当节点 S 有一个要发往目的地 D 的数据包时，它首先会检查自己的邻居表。
  2. 邻居表是通过周期性的信标广播建立的。每个节点都会广播自己的位置，听到广播的节点就知道对方是自己的邻居。
  3. 节点 S 会从所有邻居节点中，选择一个到目的地 D 的欧几里得距离最短的节点作为下一跳。
  4. 数据包被转发给这个“最优”的邻居。
  5. 这个过程在每个中间节点上重复，直到数据包到达目的地。

优点

  • 高效：决策只基于本地信息，计算简单，开销小。
  • 直接：路径趋向于一条接近直线的路径，延迟较低。

缺点:局部最优问题

  • 当节点 X 发现所有邻居到目的地 D 的距离都比自己到 D 的距离更远时，贪婪转发就会失败。这种情况被称为遇到了“空洞”或“空洞问题”。
  • 在上图中，如果 X 的邻居只有 Z，那么 X 到 D 的距离比 Z 到 D 的距离更近，贪婪转发无法选出下一跳。此时，GPSR 会切换到周边转发模式。

示例

如果节点 Ｃ 要传数据给节点 Ｄ，则将数据传输到距离 Ｄ 最近的节点 Ａ，然后 Ａ 将数据传给 Ｄ。

周边转发

周边转发是 GPSR 协议设计中最精妙的部分，它作为一种恢复模式，在贪婪转发失败时被触发。

基本思想

当遇到空洞时，协议会模仿右手定则来绕过空洞/障碍物，就像一个人用手摸着墙走一样。

工作流程

  1. 图论基础：GPSR 将网络拓扑抽象为一个平面图（没有边交叉的图），通常使用相对邻居图或 Gabriel 图来保证图的平面性。

  2. 右手定则：数据包会沿着空洞的边界被转发。具体来说，节点会选择一个“右边”的边，沿着这个方向一直走下去，直到可以重新回到贪婪转发模式。

  3. 模式切换：

    • 进入周边转发：当节点 X（被称为空洞节点）发现贪婪转发失败时，它不会丢弃数据包，而是将数据包封装到周边转发模式。数据包头会记录空洞节点 X 的位置。
    • 执行周边转发：从 X 开始，数据包沿着平面图的边，使用右手定则进行转发。这个路径会绕过网络中的稀疏区域或空洞。
    • 返回贪婪转发：在周边转发的过程中，一旦某个中间节点发现自己到目的地 D 的距离比当初的空洞节点 X 到 D 的距离更近，它就解除周边转发模式，重新切换回高效的贪婪转发模式。

示例

阴影区域是半径为 xD 的圆和节点 x 的圆形信号辐射范围的重叠面。在这个范围内找不到 x 的邻节点。即所有邻节点，都要比节点 x 离目的节点距离更远。这个区域被称为节点 x 的空洞区域（void）。X 节点需要尝试寻求其他的转发路径，绕过空洞区域。

根据右手法则，为了绕过空洞，采用 ｘ→ｗ→ｖ→Ｄ→ｚ→ｙ→ｘ 的顺序转发数据包。

GPSR 协议的关键技术点

  • 信标机制：邻居表的维护依赖于周期性的信标广播。信标间隔是一个重要的权衡参数：间隔太短，开销大；间隔太长，邻居表不准确，可能导致路由失败。

  • 平面化算法：为了保证周边转发能正确工作，必须将真实的网络拓扑（可能包含交叉连接）转换为一个平面图。常用的算法有 GG 和 RNG，它们通过移除一些冗余的边来保证图中没有交叉。

  • 数据包格式：GPSR 数据包头包含：

    • 最终目的地坐标。
    • 发送节点位置（用于计算距离）。
    • 一个标志位，指示当前处于贪婪模式还是周边模式。
    • 在周边模式下，还会记录空洞节点的位置，用于判断何时切回贪婪模式。

优缺点总结

优点

  1. 可扩展性强：由于是无状态的，节点数量增加时，单个节点的存储和计算开销几乎不变。
  2. 开销低：不需要洪泛路由请求，也无需维护复杂的路由表。
  3. 鲁棒性高：对拓扑变化不敏感。节点移动或失效只会影响其直接邻居，路由可以快速通过周边转发进行恢复。
  4. 路径接近最优：在节点密集部署时，贪婪转发能产生接近最短的路径。

缺点

  1. 对位置信息的依赖：必须要有可靠的定位系统（如 GPS），定位误差会直接影响路由性能。
  2. 网络边界问题：在网络的物理边界，周边转发可能会失败，因为右手定则会沿着边界一直走。
  3. 平面化可能失败：在三维网络或某些非理想的二维网络中，可能无法生成完美的平面图，导致周边转发循环。
  4. 空洞问题导致路径过长：虽然周边转发能解决空洞，但绕行的路径可能远长于最优路径。

应用与影响

GPSR 是地理路由领域的里程碑式协议，被广泛引用和研究。它特别适用于：

  • 大规模无线传感器网络（如环境监测）。
  • 车辆自组织网络（VANETs），其中车辆位置信息容易获取。
  • 移动自组织网络（MANETs）中节点移动性较高的场景。