介绍
哈佛大学的Brad Karp和H. T. Kung在大量的研究分析之后，提出了适合移动自组网的贪婪周边无状态路由协议 (Greedy Perimeter Stateless Routing)，缩写GPSR。论文链接
贪婪周边无状态路由协议主要包括转发数据包的两类方法:贪婪转发和周边转发。贪婪转发是该算法的核心部分。简单来说，贪婪转发方法就是寻找最接近目的位置的一跳邻节点，然后向此节点转发数据包的方法；周边转发方法是在贪婪转发模式的补充，解决在执行贪婪转发失败的区域进行数据分组转发的困境。
GPSR的优势在于，只需要保存一跳邻节点的状态信息，路由开销小；并且随着网络节点数的增加，比距离向量路由（DV）或链路状态路由(LS)有更强的扩展性。即使网络内节点移动频繁，GPSR协议都可以基于一跳邻节点的信息，迅速找到替代路由。
GPSR用信标广播来传播本地位置信息。
信标广播
信标的基本组成
每个节点周期性广播信标数据包，其中主要组成是唯一标识和位置信息。其中位置信息是被编码为两个32位的浮点数，分别表示该节点的横（经度）、纵（纬度）坐标值。信标发送周期默认为B。但是为了减少和邻节点产生信号冲突，信标发送周期随机抖动50%，即信标发送周期将均匀分布在区间[0.5B，1.5B]。接收到信标广播的邻节点，只需要将接收到的标识和位置信息保存到路由表。则路由表保存了节点的一跳邻居节点的信息。路由表的数据会被用来做下一跳路由决策。
而路由表内的路由信息也会被删除。当没有收到邻节点的路由信息的时间间隔超过T，则可以认为此邻居路由节点发送故障或者本节点已经不在此邻居节点的信号辐射范围，则将该邻居节点从路由表里面删除。在GPSR协议中，T=4.5B，即最大信标发送周期的三倍。
信标的局限性
由于节点的移动性，在信标发送周期中，路由表里的位置信息可能不是最新的。这可能是因为：1.老的节点可能离开信号覆盖范围；2.新的节点可能进入信号覆盖范围；3.获取位置的精准度可能会下降等等。
从这些原因来看，节点间的相对移动速率、节点的信号辐射范围决定了路由表是否准确，也代表了信标发送周期是否合适于此网络环境。数据分组转发需要保证一跳范围内的网络拓扑状态是最新的，因为没有任何可用的路由转发策略来处理转发节点不知道一跳或多跳临节点拓扑信息的情况。这是数据包转发的最低标准。
信标优化
在GPSR的实现中，采取了以下办法减少信标开销：
(1) 在节点转发的所有数据包中附带了本地节点的位置信息
(2) 设置所有节点的网络接口运行在混杂模式
使用了以上措施，在信号辐射范围内的所有节点都可以接收到该节点的位置信息。因为位置信息只需要十二字节的开销，所有的数据包都可以携带信标。任何节点发送出一个数据包后，可以将内部信标定时器重新开始。这种优化策略减少了在网络转发数据包区域内的信标流量。
网友评论