DSR路由协议的改进

苏娇娆

(北京军区总医院 信息科,北京 100700)

DSR路由协议的改进

苏娇娆

(北京军区总医院 信息科,北京 100700)

DSR路由协议是移动Ad Hoc网络常用的按需路由协议之一。由于采用洪泛机制寻找和维护路由表,DSR路由协议能量开销高、分组交付率低。针对此问题,提出局部化路由查询方法,限制路由请求跳数,改进DSR路由协议的路由发现过程,有效地平衡了路由信息存储量、网络拥塞和能量消耗。分析表明,改进的DSR路由协议将路由请求分组控制在一定的网络范围内,减少数据传输时延、降低网络能量开销。仿真结果显示,在选择适当的最大跳数时,改进的DSR路由协议在分组交付率、路由载荷方面均优于传统的DSR路由协议。

Ad Hoc;DSR路由协议;分组交付率;路由载荷

移动Ad Hoc网络是无线自组织网络,无需依赖于网络基础设施,能够迅速展开。各个网络节点相互协作、通过无线链路进行通信、交换信息,实现信息和服务的共享[1]。不同于普通的Mobile IP移动网络,在Mobile IP中移动节点通过基站等有线基础设施的支持来实现移动通信,而移动Ad Hoc网络完全由移动节点构成[2]。这种网络的建立快捷、灵活,不受有线网络的约束,可广泛的应用于灾难救助、偏远地区等无法得到有线网络支持,或某些只是临时需要通信但建立有线通信网络代价过大的环境,具有广阔的发展前景[3]。

由于移动节点的通信范围有限,相距较远的节点需要通过其他节点转发才能通信,因此网络中节点同时也是路由器,负责为其他节点转发数据包。由于节点移动,Ad Hoc网络网络拓扑结构动态变化。移动网络本身具有的通信带宽有限、电池能源有限等特性,使得设计合适的移动Ad Hoc路由协议具有一定的挑战性[4-6]。

移动Ad Hoc网络路由协议按照发现路由的策略可分为表驱动路由和按需路由协议[1]。在表驱动路由协议中,每个节点都有一张完整的路由表,该路由表需要频繁地更新以适应网络动态拓扑结构的变化。其优点在于节点发送数据时时延小,但由于频繁交换的路由信息中有大部分不为当前发送数据所需,因此将浪费大量宝贵的无线带宽。而按需路由协议则是当节点需要发送数据时,根据需要建立相应的路由,因此节点中的路由表并不是反映了整个网络的拓扑,而仅是当前所需的路由。按需路由虽会增加数据分组因等待路由建立产生的时延,但由于协议无需节点周期地交换路由信息,因而节省了有限的无线资源。现在的移动Ad Hoc路由协议大多采用按需路由方式,主要有DSR[7-8],ABR[9-10],AODV[11],LAR[12],CBRP[13],RDMAR[14]和ZRP[15]等。这些按需路由协议分别针对不同的网络应用场景设计,各自具有不同的优缺点,其中最典型的是DSR路由协议[16-17]。

本文分析DSR路由协议在路由寻找和维护过程中使用广播方式存在的资源消耗较大和分组交付率低的缺点,提出局部化路由查询方法,限制路由请求跳数,改进DSR路由协议的路由发现过程,降低网络传输时延、提高分组交付率和降低网络路由载荷。

1 DSR路由协议及其缺陷

1.1 DSR路由协议

DSR路由协议的特点在于使用了源路由的路由机制,在报文的头部携带要经过的路由,路由器按照该路由序列来转发报文。协议包括两部分:路由发现和路由维护。

(1)路由发现。当节点S需要到D的路由时,S广播“路由请求”报文,每个请求报文通过序列号和S标识唯一确定。收到“路由请求”报文的节点,若满足:1)该节点不是目的节点D。2)请求报文头部的源路由序列中不包含该节点。3)该节点没有接收过同样的路由请求报文。4)节点的路由表中没有到目的节点D的路由信息。节点将自己的地址附加到“路由请求”报文头部的路由序列中,并将报文通过洪泛方式转发给所有相邻节点。

若2),3)不满足,节点将删除报文,防止循环处理。若1),2)不满足,节点将发送“路由应答”给S,应答中包含了从S到D的路由,该路由从请求报文中携带的路由序列或节点自身路由表中记录的路由信息中得到。S获得路由后,使用源路由进行数据通信。

(2)路由维护。DSR路由协议支持主动应答和被动应答两种链路状态监测方法,一旦节点在发送数据时发现需要使用的邻接链路断开,其发送“路由出错”报文给这些断开路由的源节点,源节点收到报文后将失效路由从路由表中删除。沿途转发“路由出错”的节点也从自身的路由表中删除包含该断开链路的所有路由。

(3)DSR路由协议评价。1)节点无需周期性的发送报文,节省了电池能源和网络带宽,尤其是当无节点要发送数据时,网络中没有通信开销。2)支持中间节点应答,能使源节点快速获得路由,但会引起过时路由问题。3)每个报文都需要携带完整的路由信息,降低了网络带宽的利用率。

1.2 DSR路由协议存在的不足

DSR路由协议是一个简单高效的移动Ad Hoc网络按需路由协议,但在特定的应用场景下,DSR路由协议存在一些不足,主要体现在:

(1)DSR路由协议使用简单的洪泛方式查找路由,即网络中每个节点在收到路由请求报文后,只要报文不重复且本身不是目的节点或没有到达目的节点的路由信息,该节点就会向相邻节点广播该报文。洪泛路由请求分组使得网络中存在大量的冗余请求数据包,一方面占用了有限的带宽资源,造成节点能量消耗;另一方面洪泛产生大量的信息干扰和碰撞。在目的节点就是源节点的邻居节点或是离源节点较近的节点时,虽只需一步或较少几步就可找到所需路由,但洪泛式的广播会使网络中很多节点甚至全部都参与路由查找,浪费了有限的网络资源,降低了路由查找的效率。

(2)当移动节点在发送数据时发现所使用的邻接链路断开时,发送“路由出错”报文给这些断开路由的源节点。源节点还要重新进行路由发现过程,找到目的节点的新路由后再重发所有或部分数据。

(3)由于链路是单向的,当源节点收到路由出错报文后,转发“路由出错”报文的节点不能通知上游节点路由信息出错,需要重新进行路由发现过程。

(4)DSR的路由维护只是简单的将出错的链路信息发给有关的节点。当数据传送了一部分,并且这一部分数据缓存在这个中间节点中,链路出错的处理方法就造成了很多的浪费。

为克服DSR路由协议的不足,提出局部化路由查询方法,限制路由请求跳数,改进DSR路由协议的路由发现过程,降低网络传输时延、提高分组交付率和降低网络路由载荷。

2 DSR路由协议改进

2.1 平衡关系

DSR路由协议在执行完路由寻找完成后,将发现的路由存储到路由缓存器中。缓冲存储的路径越多,便可尽量避免路由寻找的过程,减少因为路由寻找所带来的网络拥塞问题和节点功耗。但节点路由缓存器中所存储的路径,必然要经过路由寻找过程。在网络节点密集的情况下路由寻找会加重网络的拥塞状况。针对Ad Hoc网络,本文对DSR路由协议进行改进,降低网络中路由请求分组数量,减少网络的能量消耗。

传统DSR路由协议中默认的是对路由请求分组的跳数不加限制,以获得尽可能多的路由存储在路由缓冲器中。但这同时也是对网络资源和能量的浪费,一方面增加节点的功耗,另一方面网络中存在大量路由请求和应答数据包,增加网络负载,引起网络拥塞,最终可能会使大量的数据包丢弃,降低网络中数据分组的交付率,增加分组的传输时延。

在DSR路由协议的实际应用中,对路由寻找过程中的路由请求分组的跳数加以限制可克服上述的缺点。Ad Hoc网络的每一条路由的中间节点数目并不是很多,实验统计表明DSR路由协议中大多数路由的中间节点的数目较小。对路由的跳数设定一个上限阀值,以有效地减少网络中路由请求分组冗余的数量,减轻节点负担和功耗。但这是以减少节点路由缓存器所存储的路径条数为代价的,若将跳数的阀值设置较小,虽可减少路由请求的发送数量和降低节点的功耗,同时也可能使得许多路由请求过程找不到有效的路径。一方面由于缓存的路径比较少,节点会频繁的发起路由请求过程;另一方面由于节点路由寻找的失败,节点会继续发起路由请求过程寻找可用的路由。

对节点路由缓存器中缓冲的路径和网络的拥塞状况、节点的功耗之间做出一个合理的权衡,即这两方面要做一个折中以取得最佳的结果。本文基于以上考虑,提出局部化路由查询方法,限制路由请求跳数,改进DSR路由协议的路由发现过程,有效的平衡了路由信息存储量、网络拥塞和能量消耗。

2.2 DSR路由协议改进

为了平衡节点缓存的路经数、网络拥塞和功耗,对路由寻找进程所发出的路由请求分组的跳数加以限制,使得路由寻找的过程在一个合理的范围内进行。通过路由寻找所获得的路由的长度均不会超过给定的最大跳数阀值max_hop。

改进后的DSR路由协议通过限制路由请求跳数将路由寻找限定在网络局部范围内,减少路由请求消息的发送,减少产生的重复的广播,降低路由请求分组碰撞的发生概率,减少路由的平均跳数,适当提高数据分组的交付率。通过设置不同的max_hop,有效的平衡路由信息存储量、网络拥塞和能量消耗。

3 分析与仿真

3.1 性能分析

相比与传统DSR路由协议,改进后的DSR路由协议在减少数据传输时延、网络开销、路由载荷,提高分组交付率等方面具有明显的优势,更加适合于能量相对受限的AdHoc网络。

(1)数据传输时延。移动AdHoc网络路由协议使用按需操作准备发送数据时,若该数据需一条未知的传输路径,需要调用路由寻找进程寻找到达目的节点的路由,因此必须延迟该分组发送,从而导致分组交付时延的增大。考虑两个方面的时延:1)节点获取到达目的节点的路由所消耗的时间。2)当正在使用的路由中断后发送节点“恢复”路由所消耗的时间。改进后的DSR路由协议对路由寻找的跳数进行了限制,一方面、消除了网络大量的冗余路由请求信息,减少网络通信碰撞,减少时延;另一方面、使得寻找路由更加简洁高效,速度更快,减少路由发现时延。路由中断后的路由恢复同样采用限制跳数的方法,减少路由恢复时延。

(2)节点能量开销。尽管按需路由协议无需周期性地将路由信息传播到整个网络中从而能够降低路由开销,但执行按需路由寻找进程路由时的代价可能较高。当数据发送者发送路由请求分组时,此路由请求分组洪泛到整个网络中,这就有可能干扰网络中的每个节点消耗宝贵的带宽和能量。接收到路由请求分组的每个节点根据其路由存储器中的路由信息给源节点回送一个路由应答分组,进一步转发路由请求分组。改进后的DSR路由协议限制了洪泛的范围,减少大量不必要的冗余数据,有效降低了节点的开销。

3.2 性能仿真

使用网络模拟工具NS2,从分组交付率和路由载荷两个方面对改进的DSR路由协议进行仿真。分组交付率定义为交付到目的节点的数据分组数量与连续比特速率数据源(CBR)源节点产生的数据分组数量之比。路由载荷定义为建立一条传输路径所需要发送的路由分组数量。

(2)仿真结果。1)分组交付率。在max_hop取不同值时的网络中数据分组的交付率如图1所示。从图中可看出,使用10个最大连接时,max_hop取值不同时的DSR协议的分组交付率类似。但增加网络的连接数时,max_hop取值越小,数据分组的交付率越高。因此,在实际应用中,可对路由请求分组的跳数加以适当的限制,以提高分组交付率。

图1 分组交付率比较

2)路由载荷。网络路由载荷如图2所示。无论连接数是多少,在max_hop取最小值5时的路由载荷均为最高。验证了max_hop取值小时可提高数据分组的交付率,但同时也会增加一定的路由开销。

图2 路由载荷比较

仿真结果显示了对DSR协议改进前后的两个重要的特征差异。改进后的DSR协议提高了分组交付率。在网络相对宽松的情况下,如最大连接数为10时,是否对跳数进行限制对DSR协议在分组交付率几乎没有影响。总体上当连接数增大时,对跳数进行限制时的交付率都呈递减趋势。但只要将跳数限制为一个合理的数值,便可适当的增加数据的交付率,同时不至于增加路由开销。

时延和路由开销方面,随着网络连接数的增加,无论是否对路由分组的跳数进行限制,网络的时延和路由开销都呈现递增趋势。但max_hop在取7和10时,路由载荷的增加并不快。因此,max_hop可在7～10之间取值。

4 结束语

由于采用洪泛的方式寻找和维护路由表,DSR路由协议开销较大、易形成网络拥塞、分组交付率低。针对DSR路由协议的缺陷,提出局部化路由查询方法,限制路由请求跳数,改进DSR路由协议的路由发现过程,有效地平衡了路由信息存储量、网络拥塞和能量消耗。分析和仿真结果表明改进的DSR路由协议将路由请求分组控制在一定的网络范围内,具有数据传输时延低、网络能量开销低,分组交付率高、路由载荷低等特点。

[1] Vassileva N,Barcelo-Arroyo F.A survey of routing protocols for energy constrained ad hoc wireless networks[C].Jeju-Island,Korea:Future Generation Communication and Networking(FGCN 2007),2007:522-527.

[2] Do-Hyun Nam,Hong-Ki Min.An efficient Ad-Hoc routing using a hybrid clustering method in a wireless sensor network[C].White Plains,NY:Proceedings of the Third IEEE International Conference on Wireless and Mobile Computing,Networking and Communications,2007:60-65.

[3] Ma Y,Kibria M R,Jamalipour A.Optimized routing framework for intermittently connected mobile Ad Hoc hetworks[C].Beijing:ICC ’08.IEEE International Conference on Communications,2008:3171-3175.

[4] Chiu Chunyuan,Kou Yuliang Kuo,Wu E H K,et al.Bandwidth-constrained routing problem in wireless Ad Hoc networks[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(1):4-14.

[5] Kadri Benamar,Feham Mohammed,M Hamed Abdallah.Weight based DSR for mobile Ad Hoc networks[C].Damascus,Syria:ICTTA 2008.3rd International Conference on Information and Communication Technologies:From Theory to Applications,2008:1-6.

[6] Mohamed Aissani,Messaoud Fenouche,Hadi Sadour,et al.Ant-DSR:cache maintenance based routing protocol for mobile Ad-Hoc networks[C].Mauritius:the Third Advanced International Conference on Telecommunications,2007:35-41.

[7] Broch J,Johnson D B,Maltz D A.The dynamic source routing protocol for mobile ad hoc networks [S].Switzerland:Internet Draft,1998.

[8] Johnson D B,Maltz D A.Mobile computing[M].Boston USA:Kluwer Academic Publishers,1996.

[9] Toh C-K.A ssiciatibity-based routing for ad hoc mobile networks[J].Wireless Personal Communications,1997,4(2):103-109.

[10]Toh C-K.Long-lived Ad Hoc routing based on the concept of associatively[S].Switzerland:Internet Draft,1999.

[11]Perkins C E,Royer E M,Das S R.Ad Hoc on-demand distance vector routing[S].Switzerland:Internet Draft,1999.

[12]Ko Y-B,vaidya N H.Location-aided routing in mobile ad hoc network[C].Dallas,TX:ACM/IEEE International Conference on Mobile Computing and Network,1998:537-545.

[13]Jiang M L,Li J Y,Tay Y C.Cluster based routing protocol (cbrp)[S].Switzerland:Internet Draft,1999.

[14]George A.Relative distance m icro-discovery ad hoc routing protocol[S].Switzerland:Internet Draft,1999.

[15]Hass Z J.The zone routing protocol for ad hoc network[S].Switzerland:Internet Draft,1997.

[16]Tao Yang,Makoto Ikeda,Giuseppe De Marco,et al.Performance behavior of AODV,DSR and DSDV protocols for different radio models in Ad-Hoc sensor networks[C].Xi’an:the 2007 International Conference on Parallel Processing Workshops,2007:51-56.

[17]Ha Duyen Trung,Watit Benjapolakul,Phan Minh Duc.Performance evaluation and comparison of different Ad Hoc routing protocols[J].Computer Communications,2007, 30(11):2478-2496.

An Improvement to DSR Routing Protocol

SU Jiaorao

(Department of Information,Beijing Military General Hospital,Beijing 100700,China)

DSR is one of the most frequently-used on-demand routing protocols in the mobile Ad Hoc networks.DSR protocol is high in energy costs and low in packet delivery fraction because DSR finds and maintains routing table by the flooding mechanism.To this problem,a localized routing discovery method is proposed to control the routing request hops.Also,the routing discovery process is improved so that the storage of the routing information,network jam and energy costs are effectively balanced.The analysis shows that the improved DSR protocol controls the routing request packets to a certain network area.In this way,the data transmission delay and the networks energy costs are reduced.The simulation results show that the improved DSR protocol has the advantages of packet delivery fraction and routing load over the traditional one on choosing the proper maximum hops.

Ad Hoc;dynamic source routing;packet delivery fraction;routing load

2014- 03- 11

苏娇娆(1976—),女,硕士,工程师。研究方向:计算机通信与网络。E-mail:Sjrr881@sohu.com

10.16180/j.cnki.issn1007-7820.2015.04.011

TN915.05

A

1007-7820(2015)04-038-05