基于NS2的Ad Hoc网络路由算法仿真与分析(5)
3．1 算法描述
算法由两个转发数据包的方法组成：贪婪转发，在任何可以使用的时候使用；边缘转发，在贪婪转发不可用的区域使用。
整个的贪婪边缘无状态路由算法，它将在整个网络图上进行的贪婪转发和贪婪转发不可用时的在平面网络图中进行的边缘转发结合起来。所有的节点会文护一个邻节点表，用来存储无线单跳邻节点的地址和位置。该表提供了GPSR进行转发决策所需要的包中所包含状态信息之外的所有状态信息。
GPSR在边缘转发模式下所使用的报头如下表所示。GPSR报头包含一个标志区域来表明该包是在贪婪模式还是在边缘模式下转发。所有产生的数据包初始标记为贪婪模式。包的源节点还在包中加入了目的节点的地理位置。只有包的源节点可以设置目的地址区域，数据包在网络中转发的时候它保持不变。
D 目的节点的地理位置
Lp 进入边缘转发模式的节点的地理位置
Lf 贪婪转发失败的节点位置
e0 包在新的面中遍历时的第一条边
M 数据包转发模式：贪婪转发或边缘转发
表1 GPSR包头
当接收到一个贪婪转发模式的包时，节点查找它的邻节点表，从中找出地理上最接近包目的地址的邻节点。如果该邻节点更接近于目的节点，则节点转发包到此邻节点。当没有邻节点比自身更接近时，节点标记包为边缘转发模式。
GPSR转发边缘模式的包时使用一个简单的平面图遍历。本质上，当一个包在节点x处进入边缘模式，目的节点为D时，GPSR转发该包到平面图上日益接近目的节点的面。这些面被直线xD贯穿。一个平面图有两种类型的面。内部面指的是那些由图的边所构成的密闭的多边形区域。外部面指的是在图的外边界之外的无限大的面。在每种类型的面中，遍历使用右手法则来找到与直线xD交叉的边。遍历移动到相邻的被直线xD贯穿的面。图3.1给出了一个例子。注意在该图中，每个遍历的面被直线xD贯穿，头两个和最后一个面是内部面，第三个是外部面。