GPSR协议详解（1）——简介
GPSR协议详解（2）——贪婪转发
周边转发
如图一所示，阴影区域是半径为xD的圆和节点x的圆形信号辐射范围的重叠面。在这个范围内找不到x的邻节点。即所有邻节点，都要比节点x离目的节点距离更远。这个区域被称为节点x的空洞区域(void)。x节点需要尝试寻求其它的转发路径，绕过空洞区域。
在GPSR协议中，当贪婪转发遇到路由空洞的时候，进入周边转发模式绕过路由空洞。在Brad Karp和H. T. Kung的论文中，周边转发模式有两个关键工具：右手定则和构造平面拓扑图
右手定则
右手定则如图二所示：当数据包从节点y到达节点x的时候，采用以节点x为轴心，将(x，y)按照顺时针旋转，到达的第一条边则是下一次转发所要经过的路径。如图所示，转发顺序应该是y→x→z→y。而为了绕过图一中出现的空洞区域，釆用x→w→v→D→z→y→x的顺序转发数据分组。这种由右手定则构成的路径，称为周边(perimeter)。
当转发数据包遇到路由空洞的时候，记录当时的状态（位置），使用右手定则来走出路由空洞。这需要一种无交叉启发式搜索算法，使右手定则在互相相交的图中，找到一个包含路由空洞的周边(perimeter)。这个启发式搜索有以下责任：1.简化拓扑图，使周边转发更快走出路由空洞; 2.不能造成网络分区。 如果出现网络分区，算法将不会找到跨越此分区的路由。所以引入构造平面图的这个工具。
构造平面图
平面图就是没有任何两条边相交的图。假设节点的信号范围为半径为r的圆，而节点m在节点n的信号范围内，即距离d(n，m)≤r，则称存在边(n，m)在节点n和m之间。（PS：我们忽略节点的高度差异，假定所有节点都在同一平面）。
要构造复合我们的应用要求的平面图，需要达到以下要求：
(1) 删除不属于平面图的边，构造一个没有交叉边的网络拓扑图
(2) 平面图算法必须能够以分布式运行在每个节点上，而且只需要用到与节点有关的本地拓扑信息作为算法的输入
(3) 将图中多余的边删除，到平面图构造完成的过程中，不能使图断开，导致网络拓扑分割。
相对邻域图RNG(Relative Neighborhood Graph)和加布里埃尔图GG (Gabriel Graph)是常见的、满足以上条件的平面图。
1. RNG平面图
RNG平面图的定义
若顶点U，V和任意其它顶点W之间的距离，全都大于或等于顶点u和v之间的距离d(u，v)，则在顶点U和V之间存在RNG边(u，v)。用方程式表示如下:
下图形象地说明了RNG平面图的定义。以节点u和节点v各自形成一个半径为d(u，v)的圆形，半月形阴影区域则是这两个圆的重叠部分。若(u，v)是RNG中的边，则在节点U和V之间的阴影半月形区域内，不能包含有任何证明节点w。
RNG的算法
对于每个节点u，有完整的邻节点列表N，用以下伪代码去除非RNG连接：
2. GG平面图
GG平面图的定义
如果节点u和节点v之间，直径为uv的圆内，不存在其它顶点W，则节点u和节点v存在GG边(u，v)。用方程式表示如下:
下图形象地说明了RNG平面图的定义，节点u和节点v之间形成一个直径为d(u，v)的圆形，节点u和节点v都在圆上，即是圆形阴影区域。若(u，v)是GG中的边，则在节点U和V之间的圆形阴影区域，不能包含有任何证明节点w。
GG平面图的算法
直径为uv的圆形阴影的圆心也是uv的中点。对于每个节点u，有完整的邻节点列表N，用以下伪代码去除非GG连接：
从两者的定义可以看出，RNG是GG的子集，差别在GG只是在节点间较小的圆形阴影区域内搜寻证明节点。如下图所示，左图是无线网络的完整拓扑图；200个节点被随机部署在2000*2000米的区域，无线电范围为250米；中间表示整个拓扑图的GG子图;右图表示整个拓扑图的RNG子图。
