2019-03-02 | UNLOCK

GPSR:贪婪转发与周边转发

这是之前学习《无线传感网络》这门课做的期末大作业,GPSR是”greedy perimeter stateless routing”的缩写。

这是一种无状态的路由转发协议,巧妙地借助“贪婪转发”和“周边转发”有效地降低了每个物理节点的存储信息量,非常具有实用意义。

除此之外,它还能快速地应对现实中外界条件、节点能耗等多种因素造成的频繁变化的节点分布。

因此,特别重温一下,作为一次分享。

0. 摘要

随着路由节点的增加以及拓扑结构变化率的增大,传统的路由转发协议算法效率低、鲁棒性差。贪婪周界无状态路由协议(GPSR)只使用拓扑结构中的临近信息节点进行“贪婪转发”决策。当数据包进入“路由空洞”的时候,算法会先构造GG平面图或者RNG平面图,然后采用“周边转发”绕过此区域。此过程中,算法会自动切换“贪婪转发”和“周边转发”这两种模式。在频繁变化或者节点数量多的拓扑结构中,并且每个节点存储的信息量少,GPSR可以较低的成本快速地响应变化,查询正确的路由路径。

关键词:GPSR, 贪婪转发, 周边转发, 路由空洞, 平面图

1. 研究背景及意义

1.1 研究背景与动机

当下的一些路由具有节点多、拓扑结构变化快的特点,例如:Ad-hoc网络(无基础设施,支持军事用户、灾后救援人员以及临时协作)、传感器网络(由小型传感器组成,节点资源匮乏)、“屋顶”网络(非移动,但是密集遍布大都市区域,节点数量数十万)。

传统的路由算法的节点成本和消息成本过高,造成在高移动性和密集节点拓扑结构中的的低适应性。因此,需要一种新的节点成本低、鲁棒性高的路由算法。

1.2 研究意义

论文提出的GPSR算法合理利用地理信息来实现高稳健性。在网络节点数量不断增加的情况下提高稳健性和迁移率,降低路由协议消息发送成本,各个路由节点消息传递成功率以及使得每个节点存储最少的信息量。

2. 国内外研究现状

论文中提出的DV和LS算法,要求将整个网络拓扑结构的映射到所有的路由节点。在DV算法的描述中,每个路由节点都记录了最新周期中到所有网络目的地的距离;在LS算法的描述中,每个路由节点都会接受到链路改变的相关信息状态。

当拓扑结构变化率增大,或者路由区域中的路由节点的数量增多,DV算法和LS算法的复杂度就会增加,同时增加的还有每个节点的信息量储备和节点之间沟通成本。

虽然“缓存”技术可以减少节点负载,但是当节点数目过多或者拓扑结构变化率过大的时候,现有算法仍然不能保证较高的鲁棒性以及较低的节点开销。

3. 研究内容

3.1 主要挑战及创新点

为了让节点存储最少的信息量,并且能够快速响应拓扑结构的变化。需要使用贪心法的思想,让每一步都是最优解,这个转发过程就是“贪心转发”。

但是有些时候无法满足“贪心转发”的条件,此时的情况就是“路由空洞”。解决“路由空洞”的重要技术是“右手法则”,这个转发过程就是“周边转发”。而在周边转发之前需要将图处理成平面图,有GG和RNG两种平面图供选择。

在转发过程中,根据节点条件,切换“贪心转发”模式和“周边转发”模式,直到到达最终的目的节点。

3.2 相关技术介绍

GPSR算法的实现过程中,需要配合“信标算法”来确定邻居节点的位置信息。

“信标算法”中,每个节点周期性的以广播方式传送一个信标,信标包括节点自身的位置信息,位置信息被编码成两个4字节的浮点数值,用于标记节点的x坐标和y坐标。数据格式是(IP, (x, y))

为了避免邻居节点发送的信标产生冲突,用B表示信标间的时间间隔,节点发送信标的时间统一分布在[0.5B, 1.5B]之间。设节点保留位置信息的最长时间为T,在超过T时间间隔后仍然没有收到邻居节点发送的信标,就认为邻居节点失效或超出覆盖范围,删除对应的位置信息。

借助这些地理信息,GPSR算法的可以避免探测包的盲目洪泛,从而进行有效的路由转发,并且针对节点变动进行有效的路由维护。甚至实现基于无状态的分布式的非端到端的数据转发。

3.3 贪婪转发

贪婪转发的过程是指:

  1. 数据包由源节点标记要发送数据包的目标节点或目标区域位置;
  2. 每一个中间的转发节点都知道它的邻居节点的位置,转发节点在选择数据包的下一跳节点时使用贪婪转发策略,即选择地理位置最接近目标节点的节点作为下一跳节点;
  3. 以此类推,每一次转发都会更加接近目标节点,直至到达目标节点。

贪婪转发的原理就是利用“贪心”思想,让每个节点选择当前的最优选择(在满足条件的情况下),直到算法结束。

如下图所示,根据贪婪转发的原则,节点x的下一跳节点就是节点y。毫无疑问,贪婪转发只需要保证节点的一条邻居信息即可

3.3 贪婪转发困境·路由空洞

路由空洞是指当前节点比所有其他一跳邻居节点更接近目的节点,此时,根据贪婪转发的规则,当前节点不会转发数据给一跳的邻居节点。如果存在这种网络拓扑结构,那么就称之为“路由空洞”。

如下图所示,void区域就是没有满足“贪婪转发”条件的区域。因为节点x的覆盖范围与以直线xD为半径的圆的交叉区域没有邻居节点。

3.4 周边转发

针对上述的“路由空洞”问题,算法会将模式(Mode)从贪婪转发切换到周边转发,进而绕过“路由空洞”。

“周边转发”是根据“右手法则”来判断下一跳转节点:连接当前节点和目的结点形成直线,右手握住此线逆时针旋转,到达的第一条边(边代表其上的两个点可以互达)就是下一跳的方向。

3.5 周边转发困境

虽然周边转发可以绕过“路由空洞”,但在一些情况下,单纯地进行周边转发可能会陷入死循环,最终只能回到当前节点,无法抵达目的节点。

这里举一个例子进行介绍。下图是一个由X、W、U、Z以及目的节点D构成的图,节点之间的连线代表着两端节点是相邻的(可以互相达到)。假设现在从节点X开始出发。

从X节点开始,根据“右手法则”依次抵达U节点、Z节点和W节点。此时,对W节点再次使用“右手法则”,算法又重新跳回了U节点。最后,对U节点使用“右手法则”,跳回了开始节点X。

显而易见,此时的周边转发陷入困境。这主要是由于这张图不是一个“平面图”的原因。需要删除一些边,从而使其变成GG或者RNG平面图,才能走出此困境。

3.6 RNG平面图和GG平面图

RNG平面图的定义是:若顶点U,V和任意其它顶点W之间的距离,全都大于或等于顶点u和v之间的距离d(u,v),则在顶点U和V之间存在RNG边(u,v)。用方程式表示如下:

如下图所示,若(u,v)是RNG中的边,则在节点U和V之间的阴影半月形区域内,不能包含有任何证明节点w。此时,由于d(u, v) > max(d(u,w), d(w,v)),为了构建RNG平面图,必须把边(u, v) 舍去

关于RNG平面实现的伪代码如下。其中,N是对于任意节点u来说的邻接节点列表,v是集合N中的任一节点。

GG平面图的定义是:如果节点u和节点v之间,直径为uv的圆内,不存在其它顶点W,则节点u和节点v存在GG边(u,v)。用方程式表示如下:

如下图所示,若(u,v)是GG中的边,则在节点U和V之间的圆形阴影区域,不能包含有任何证明节点w。

关于GG平面实现的伪代码如下。其中,N是对于任意节点u来说的邻接节点列表,v是集合N中的任一节点。

对于GG和RNG两种平面图,RNG平面图是GG平面图的子集。它们之间的直接关系可以用下图表示出来:

3.7 周边转发困境·RNG平面图解决

构造上述的RNG平面图或者GG平面图就可以解决“周边转发”无法到达目的节点的困境。这里以构造RNG平面图为例,还是使用之前的图形。为了方便讲述,规定边xu长度为12,边xw长度为11,边uw长度为10。

根据RNG的定义,D(U, X) > MAX(D(W, U), D(X, W)),所以移除UX边。此时,“周边转发”不再会陷入困境。

4. 性能评估

论文为了测试算法的性能,使用了Carnegie Mellon(卡梅隆)大学的测试数据。在畅通平面上,无线仿真模型节点进行运动。节点会在指定区域内随机选择一个目标,然后在指定范围内随机选择一个速度,以此速度到达目标并且停留一段时间。这个过程模拟了拓扑结构的高迁移率以及其中的节点。

下图显示了不同的B(时间间隔)的情况下,GPSR传递成功的数据包。将从B=3s降低到B=1.5S并没有带来很大成功率提高,成功率也保持在97%以上。

下图比较了DSR算法和GPSR算法的节点消耗,GPSR的节点消耗远远低于DSR的节点消耗,并且随着时间推移,GPSR节点的消耗也更加稳定。

因此,GPSR算法达到了设计的初衷:在迁移率高的拓扑结构中,能够保持较高的鲁棒性,并且每个节点的资源消耗都得到了改善。论文中还分节点状态、路径长度等维度进行了比较,也只是说明GPSR算法的优势。主要的性能测试还是上述的传包成功率和节点消耗,其它测试这里不再冗赘。

5. 阅读心得

在本次论文的学习过程中,掌握了“贪婪转发”、“周边转发”、“RNG和GG平面图”,最重要的是理解了在GPSR算法中是如何调度进行状态转化(贪婪=>周边 / 周边=>贪婪),以及如何解决“路由空洞”和“周边转发困境”。除了算法的核心部分,也触类旁空地了解了“信标算法”的实现机制以及冲突解决方法。

就我个人来看,GPSR算法和论文中提及的传统算法相比,已经实现了最小化节点的保存数据(节省节点资源),并且能够利用状态切换合理应对可变性高的拓扑结构。

美中不足的是“信标机制”会带来额外的开销,但是相比于每个节点保存所有节点的信息,信标机制的这点开销完全可以忽略。

6. 参考

在阅读论文的过程中,我查找了大量的中文和英文资料,非常有助于理解这篇论文所讲述的GPSR算法。特此系统记录一下相关资料。

  1. 论文:GPSR: Greedy Perimeter Stateless Routing for Wireless Networks
  2. Youtube Videos(印度英语)
  3. 百度文库讲义(从43页开始): https://wenku.baidu.com/view/c23bcb7bc950ad02de80d4d8d15abe23482f039d.html

请针对 Disqus 开启代理