Adhoc网络中不相关多路由源端寻路算法

周婧

摘 要 路由方案是Ad hoc网络中一个热点研究领域。其中，按需路由算法由于其有效性在带宽受限的Ad hoc网络中得到比较大的发展。然而大部分的按需路由算法，建立并只使用单条路由，当当前使用的路径的链路断开时，路由算法必须执行一个路由修复过程。本文提出了不相关多路由源端路由算法（DMSR），建立并利用多条最大不相关路由。在本文算法中，中间节点等待一段时间以得到多个路由请求包（RREQ），然后在这个RREQ中，选择相关性最小的多路径，并将这些信息写入一个RREQ中，并将它广播出去。从仿真结果可以看出本文的算法提高了数据包的正确传输率和业务均衡。

关键词 通信保障 综合保障 项目管理

1 引言

Ad hoc网络是没有中心节点的自组网络，在这个网络中，没有固定的路由器，或者无线基站。在Ad hoc网络中，移动节点之间的通信是通过点到点的多跳技术实现的，这就意味着网络拓扑动态的变化，这就产生了许多值得探讨的问题。在Ad hoc网络中，路由技术是至关重要的，在任何业务连接之前，都首先必须完成寻路的过程。

目前，Ad hoc网络中最多的是按需路由。然而，很多已经提出的按需路由协议，如传统的DSR[1]，AODV[2]算法都只为每一个连接建立一条路径，这不仅不能充分利用资源，而且无法有效处理拥塞，链路断开等情况。多路由算法可以解决这些问题。使用多条路径可以提高带宽的有效利用率和传输可靠性以达到一定的QoS保证。

目前，对多路由的研究主要集中在以下两个方面：建立多路由和在这些多路由之间分配业务的策略。

本文提出一种新的不相关多路由源端路由算法（DMSR）。DMSR算法在DSR算法的基础上主要做了以下的改进：在寻路过程中，每个中间节点等待一段时间以接收到多个RREQ，然后在这个RREQ中，选择相关性最小的多路径，并将这些信息写入一个RREQ中，并将它广播出去。DMSR可以找到最大不相关路径，因此可以减小发起路由频率，以减小时延，同时可以提高数据包的正确传输率。

2 Ad hoc中的多路由

在网络拓扑不确定的情况下，寻找到不相关的多路由是比较困难的。DSR协议能够寻找到多条路由，并在主路由断裂的情况下将其他路由作为备份路由。然而，DSR并未将不相关性考虑进来。在本篇文章里提出一种寻找不相关的多路由的方法。

2.1 DSR中的路由发现

在DSR算法中，如果源节点不知道到目的节点的路径，那么源节点将通过洪泛路由请

求消息（RREQ）发起一个路由发现。在RREQ包头中将依次记录下这个RREQ包所经过的节点的地址。当一个节点接收到一个RREQ包，如果这是第一次接收到这个具有相同源节点地址和ID的RREQ包，这个节点经过处理将RREQ广播出去。反之，节点将这个RREQ丢弃。一点RREQ到达目的节点，目的节点将经过RREQ中包含的路径返回一个路由回复消息（RREP）到源节点。当RREP到达源节点，源节点和所有中间节点都会知道一条到达目的结点的路径。

DSR中这种广播RREQ的方式极大的减小了找到不相关的多路径的可能性。也就是说DSR算法最后找到的多条路径的一些节点是相同的。在一些文章的仿真结果中DSR找到完全不相关的多路径的可能性几乎为零。造成这种结果的原因是中间节点将丢弃后收到的相同的RREQ，而这些RREQ中包含着不相关的路径。

2.2 不相关源多路由算法

A.路由发现

DMSR充分利用后来接收到的RREQ包。

当一个中间节点收到第一RREQ包，它不是像DSR那样立刻将自身地址加到这个RREQ上并将这个RREQ广播出去，而是将收到的RREQ储存在高速缓冲存储器中，同时启动一个定时器，在定时器的这段之间内，该节点等待其它相同的RREQ（即具有相同源节点地址和RREQ ID的RREQ）。

当节点收到相同的RREQ，它首先要检查这个RREQ中路径的跳数是大于、小于或者等于之前收到的相同的RREQ的跳数。如果是大于，则节点丢弃该RREQ；如果等于，节点将RREQ记录在cache中；如果小于，节点将删除之前接收到的相同的RREQ，同时将新收到的RREQ记录在高速缓冲存储器中。

为了减小RREQ造成的信令开销，限制一个节点最多记录三条相同的RREQ。为了减小时延，如果已经记录下三条RREQ，就将定时器归零，开始处理高速缓冲存储器中的RREQ。

当定时器到时，开始处理高速缓冲存储器中记录的RREQ：

（1）如果高速缓冲存储器中只有一个RREQ，该节点将自身地址附加在RREQ中的路由纪录中，并将它广播出去；

（2）如果高速缓冲存储器中有不止一个RREQ，节点检查是否存在一个RREQ中只有一条路径。如果存在这样的RREQ，节点首先选择这条路径，然后在其他RREQ中分别选择一条与该路径相干系数最小的路径；如果相干系数一样，则选择首先记录下的那条路径；如果所有的RREQ都包含不止一条路径，则节点首先选择第一个收到的RREQ的第一条路径，其他路径的选择准则见2），然后：

（3）选择完路径，节点将自身地址附加到所选择的路径上，并将这些路径写到原来收到的RREQ中，这些路径的写入顺序是：首先收到的RREQ中选择的路径是第一条路径，第二个收到的RREQ中选择的路径是第二条路径，同样的，从最后收到的RREQ中选择的路径是第三条路径。然后节点将新的RREQ广播出去。

当第一个RREQ到达目的节点，目的节点等待一段时间以接收到更多的RREQ，并从这些RREQ中选择相干最小的多路径。

在DMSR算法中，在一段时间内收到的RREQ中，中间节点选择跳数最小的路径。因此，在目的节点可以得到跳数最小的路径。同时DMSR算法中，优先选择先到达的路径，这同样可以减小时延。

路径中的一条链路可能由于移动、拥塞、包冲突而断裂，因此，修复断裂的路径非常重要。在DMSR算法中，当一个节点不能够将包传送到下一个节点，就认为到下一个节点的链路已经断开，于是发出一个路由错误包（RRER）到这条路径的上游节点。这个RRER包中包含到源节点的路径，以及断开链路的上游、下游节点。一旦收到RRER包，源节点将删除其路由表中所有使用断开路由的表项，而同时源节点使用剩余的路径传送数据包。当所有的路径断开，源节点将重新发起一个路由发现过程。

2.3 DMSR和DSR的比较

图2表示的是DMSR找到的多路径，可以看出这些路径是不相关的。图3表示的是DSR找到的多路径，这些多路径几乎是重叠的。可以看出，DMSR比DSR寻找多路径的效率高得多。

3 仿真结果

3.1 仿真环境

3.3 结果与分析

图4所示的是DMSR与DSR算法的数据包的正确传输率。从图中可以看出，相对于DSR，DMSR提高了性能，尤其是当移动性增加时。当使用多路由时，移动性增加，性能的提高变得明显，这是因为在DSR算法中，每一对业务只使用一条路径，当这条路径失效时，源节点必须重新寻找一条新的路由，在此过程中，会造成包的丢失。但是在DMSR中，源节点可同时使用三条并行路径，因此重新寻路的频率被大大减小，尤其当移动性增大时，因此DMSR能够正确传送更多的数据包。

图5所示的是两种算法的平均端到端时延。可以看到两种算法的时延几乎相同，但是DMSR算法比DSR算法的时延略微大一点。在DMSR中路由发现的频率减小可以减小时延，但是在DMSR的寻路过程中RREQ必须从源节点发送到目的节点以寻找到多条路径，而在DSR中，寻路过程中的任一节点可以使用自己路由表中的信息，不需要一定要将RREQ包发送到目的节点，在这方面，DSR可以减小时延。

图6所示的是两种算法负载均衡的结果。从图中可以看出DMSR的网络CoV性能优于DSR。这是因为DMSR可以将网络业务分摊到多条路径上。而在DSR算法中所选用的路径为源节点与目的结点之间的最短路径，因此会将更多的业务分配到这些路径上。随着休息时间的减少，DMSR和DSR的网络CoV也减小，这表明移动性可以均衡负载。

4 结论

在本篇文章中，提出了一个新的ad hoc中的DMSR算法。DMSR算法在DSR算法的基础上主要做了以下的改进：在寻路过程中，每个中间节点等待一段时间以接收到多个RREQ，然后在这个RREQ中，选择相关性最小的多路径，并将这些信息写入一个RREQ中，并将它广播出去。本文对DMSR的性能进行了研究，结果表明DMSR可以提高数据包的正确传输率和业务均衡性。

参 考 文 献

[1] D. Johnson and D. Maltz， Dynamic source Routing in Ad Hoc wireless networks， in Mobile Computing， T. Imielinski and H. Korth， editors， Kluwer Academic，1996.

[2] C.E. Perkins and E.M. Royer， Ad-hoc On-Demand Distance Vector Routing，Proc. 2nd IEEE Wksp. Mobile Comp. Sys. And Apps.， Feb. 1999， pp.99-100.