周边转发

如图一所示，阴影区域是半径为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)是常见的、满足以上条件的平面图。