基于竞争转发的Adhoc网络路由算法

刘钢　郭晗

摘要：移动Ad hoc网络是通过无线通信技术，结合相邻节点转发从而能够实现群组内各个節点的通信。是若干带有无线接收和发射装置的移动终端所组成的具有多跳能力的临时自治系统。GPSR是一种比较典型且健壮的地理路由协议，但是当遇到有较多的分组同时传递给同一个目的节点的情况时，由其周边转发模式产生的较多跳数的路由，会成为一个难以解决的问题，本文由此提出了一个改进优化的路由算法——EGPSR路由算法。

关键词：Ad hoc；路由协议；竞争转发；自组织

1、引言

在以往的研究过程中，典型的基于地理位置信息的路由协议有LAR[1]协议、GPSR[2]协议和TB协议等，这类协议具有更好的可扩展性和对无线网络更好的适应性。

本文针对车载Ad hoc网络所具有的特点提出了一种新的基于竞争转发方式的路由算法，算法核心思路是通过特定的竞争转发策略来确定合适的下一跳节点。数据包会沿着最终选定的序列进行路由操作，并在岔路口区域进行确定下一个岔路口的计算，从而减少数据包中携带完整岔路口序列信息的数据量，提高了工作效率。

2、车载Ad hoc路由算法研究进展

GPSR是采用贪婪转发策略和面遍历算法的路由协议，它的缺点是性能在节点分布不均衡时恶化。

已经比较成熟的确定路由的算法，主要有两种，一种是基于已经选定的结点的路由选择，是找出一系列数据包转发过程中必须经过的地理位置，并在选定结点之间，使用特定的转发策略进行数据包转发。另一种是空间感知路由算法，是利用空间地理信息计算得到一个数据包转发的确定路径。

此外，还有一些利用实际环境因素进行路由选择的算法。其中基于街路和通信量信息感知路由算法是利用地理位置信息和道路交通信息确定选定点路径。而基于位置的路由协议是以道路交叉点岔路口为选定点，基于网络拓扑与车辆交通信息的路由协议。数据包摆渡是一种是控制移动节点的移动以辅助节点转发。

3、EGPRS路由算法

根据已有的研究可知，包括移动Ad hoc网络在内的很多无线网络的拓扑结构都具有一定的易变性，某些时刻某些节点对之间已经建立的通路会中断，同时，较多的路由跳数会增加特定路由上传输分组丢失的可能性，并能够增加分组的传输时间延迟，从而降低网络的性能。仅从路由跳数的角度来考虑，可以看出GPSR协议选择的路由并不是最佳路由。

基于以上原因，本文借助某些路由节点上存储的少量路由状态信息提出了一种增强的策略和与之相对应的路由算法。新的路由算法能够在一定程度上减少GPSR协议在周边转发模式中由于绕道产生的跳数。当多个分组传到相同的目的节点时，新的路由算法能够在传递完第一个分组后，以最快的速度确定一条较短的路由，以便在进行后续分组的信息传递时经过尽量少的跳数。所以节点能够确定某一分组曾经是否转发过，并且能从分组的头部包含的信息确定分组到达当前发送节点所经过的跳数。

3.1 竞争转发策略

所有数据包中持有节点广播的数据包都会给它的直接邻接节点，这个数据包头部包含持有节点的位置信息、当前交叉节点的位置信息和数据包的编号。竞争节点接收数据包并临时存储数据包到本地缓存区，并且每个参与竞争的节点根据本节点、上一跳节点以及当前交叉节点、前一岔路口的位置，为每个数据包设置一个计时器。若计时器超时，当前节点的数据包会以广播方式转发出去。在这个过程中，地理位置越靠近当前交叉节点，其计时器超时的数值就会越小，满足这个条件的时候，当前节点会把本地缓存中的相应数据包删除。

3.2 EGPSR算法的路由发现

EGPSR算法采用与GPSR算法相类似的思路为信息序列的第一个分组找到路由，然后构成无线网络的节点会遵循下列路由算法进行信息传递的分组，算法如下：

if节点m正在持有分组数据包p then

if 节点m是源节点 then

节点m所经历的跳数为0

else

节点m的跳数为分组数据包p的跳数加1，同时把p的跳数改为与m的跳数一致。

if 节点m不是目的节点d then

m向前移动到m的下一个节点

if 节点 m 监听到一个属于邻接节点n

把这个相同的节点p进行发送，m的跳数加1

m的下一跳指向n

当相同连接的数据包通过m发送数据时，m重新路由操作

在与GPSR算法相比较时，改进的EGPSR算法有以下优点：

a）一定程度的减少了路由的跳数；

b）任意一个节点在一跳传输范围内，有明确的下一跳信息；

c）进行适当的优化后，第二个分组以及后续分组的路由是收敛的；

d）在一定程度上降低了路由的复杂度；

4、结束语

本文研究了以往的路由算法，并提出EGPSR算法，通过增加路由探测的方法达到了优化信息传递路径的目的。通过实验可以看出EGPSR算法在协议资源的开销方面比GPSR算法大，但在分组丢失率、分组传输时延以及网络吞吐量等方面都要好于GPSR算法，从而得知EGPSR算法改善了以往路由算法的网络性能。（作者单位：1.吉林建筑大学；2.长春工业大学）

参考文献：

[1]MarioGerla，Kennmg，RajiveBagrodia.TCpperformanceinwirolessmulti一hopnetworks.ProeeedingSoftheSecondIEEEWbrkshoPon MobileComPutersystemsandAPPlieations.NewOrleans，Louisiana：1999.41一5

[2]K.CHuang，K.C.Chen.Interferene analysis of nonPersistentCSMAwithhiddentenninalsinmultieellwirelessdatanebork.ProeeedingsoftheIEEEPIMRC.Toronto，Canada：1995，2.907 91