移动Ad hoc网络路由协议及其性能比较 王海涛,郑少仁

(解放军理工大学通信工程学院,江苏南京210007

摘 要:由于A d hoc网络自身的特殊性,其路由协议的设计与传统固定网络有很大不同。首先说明了A d ho c网络中提供高效路由算法的难点,然后讨论了Ad hoc网络中路由协议设计的几种策略,接着介绍了几种典型的A d hoc路由协议,最后通过实验分析比较了4种路由协议的性能,并给出了结论。

关键词:网络模拟器;目的序列距离矢量路由;动态源路由;临时按序路由;Ad hoc按需距离矢量路由

中图分类号:T N915.04 文献标识码:A

Routing Protocols of Ad hoc Network&Theirs Performance Comparisons WANG Hai-tao,ZHENG Shao-ren

(I nstitute of Communication Engineer ing,PL A U ST,N anj ing210007,P.R.China Abstract:Based on A d hoc netw ork's particularity,the routing pro tocols of are different fr om those of tr aditional fix ed netw orks.T his paper firstly ex plains various difficulties in pr oviding hig h efficient r out-ing algor ithms in A d hoc netwo rk.T hen some policies of routing pr otocol desig n in A d hoc netw ork are discussed and sev er al ty pical A d hoc r outing pr otocols are introduced.T he perfor mances of four r outing protocols are analy zed and compar ed and some co nclusions are draw n v ia ex periments in the end.

Key words:N S;DSDV;DSR;T O RA;A ODV 0 引 言

无线网络通常可以分为有中心网络和无中心网络,前者需要固定基础设施的支持,移动主机之间的通信通常借助基站来完成,例如蜂窝移动通信系统;后者主要是指移动Ad hoc网络[1-4],它不需要固定的基础设施,能够快速地自动组网。与有中心网络相比,Ad hoc网络灵活、健壮、投资少,特别适合于作战指挥、抢险救灾以及应付突发事件和执行临时任务的场合。在Ad hoc网络中,每个移动节点兼备路由器和主机两种功能。作为主机,移动节点需要运行面向用户的应用程序;作为路由器,它需要运行相应的路由协议,根据路由策略和路由表参与数据分组转发工作和路由维护工作。考虑到Ad hoc网络中节点是移动的,网络的拓扑结构不断变化,传统的用于因特网的路由协议(如RIP、OSPF等无法适应Ad hoc网络的实际需要[2],同时由于移动节点的计算能力和存储容量较低并且能源受限,要求路由协议尽量简单,这又增加了Ad hoc网络中路由协议设计的难度。

1 Ad hoc中路由协议的分类

Ad hoc网络的路由协议大致可以分为先验式(Proactive路由协议、反应式(Reactive路由协议以

? 73 ?

第14卷,第4期重庆邮电学院学报2002年12月

Vol.14 No.4 J ournal of Chongqing U niversity of Posts and Telecommunications Dec.2002

收稿日期:20020520

作者简介:王海涛(1976-,男,河南焦作人,讲师,现在解放军理工大学攻读博士学位,研究方向为移动网络和宽带网络;郑少仁,教授,博士生导师。

及混合式路由协议[2,5]。先验式路由协议又称为表驱动路由协议,在这种路由协议中,每个节点维护一张包含到达其它节点的路由信息的路由表。当检测到网络拓扑结构发生变化时,节点在网络中发送更新消息,收到更新消息的节点将更新自己的路由表,以维护一致的、及时的、准确的路由信息,所以路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文,可以立即获得到达目的节点的路由。因此这种路由协议的时延较小,但是路由协议的开销较大;反应式路由协议,又称为按需路由协议,是一种当需要发送数据时才查找路由的路由算法。在这种路由协议中,节点不需要维护及时准确的路由信息,当向目的节点发送报文时,源节点才在网络中发起路由查找过程,找到相应的路由。与先验式路由协议相比,反应式路由协议的开销较小,但是数据报传送的时延较大。在Ad hoc网络中单纯采用先验式或反应式路由协议都不能完全解决路由问题。在高速动态变化的Ad hoc网络中,使用单纯的先验式路由协议会产生大量的控制报文,并且很多控制报文经常是无用的;如果单独采用反应式路由协议,需要为每个报文查找路由,这也是不合理的(特别是当连续向某个目的节点发送多个报文时。由此可见,应用结合先验式和反应式路由协议优点的混合式路由协议是一种较好的折衷方案。在局部范围内使用先验式路由协议,维护准确的路由信息,并可缩小路由控制消息传播的范围,当目标节点较远时,通过查找发现路由,这样既可以减少路由协议的开销,时延特性也得到了改善。

2 4种典型的Ad hoc网络路由算法

为了比较和验证Ad hoc网络中的路由协议的性能,采用了NS2网络仿真器[4]进行试验。NS2是由加利福尼亚大学伯克利分校和VINT项目组联合开发的,是一个包含T CL(Tool Com mand Lan-guage:工具命令语言语言的受事件驱动的网络仿真器。这个仿真器通过NS的解释程序被调用,解释程序之间的所有相互作用通过一个专门的T CL程序完成。应用NS命令,可定义一个网络拓扑,配置流量源和接收器,收集统计的数据等。NS2最初主要被用来模拟传统有线网络上的T CP协议和其他协议,它并不支持多跳无线移动网络环境,随着相关领域研究的进展,美国的CMU大学对NS2作了相应的扩展,目前,NS2已经可以支持一定范围内和一定条件下的无线多跳移动网络。

2.1 目的序列距离矢量路由协议(DSDV

DSDV对Bellman-Ford路由算法进行了改进。在DSDV中,每个移动节点都需要维护一个路由表。路由表表项包括目的节点、跳数和目的地序号,其中目的地序号由目的节点分配,主要用于判别路由是否过时,并可防止路由环路的产生。每个节点周期性必须与邻节点交换路由信息,当然也可以根据路由表的改变来触发路由更新。路由表更新有两种方式:一种是全部更新(Full dump,即拓扑更新消息中将包括整个路由表,主要应用于网络变化较快的情况;另一种方式是部分更新(Incremental update,更新消息中仅包含变化的路由部分,通常适用于网络变化较慢的情况。在DSDV中只使用序列号最高的路由,如果两个路由具有相同的序列号,那么将选择最优的路由(如跳数最短。NS实现DS-DV路由协议的具体策略如下:一个没有找到路由的分组到达节点后首先被缓存,同时节点发送路由查询消息,直到接收到来自接收端的路由响应消息。当缓存溢出时,新来的分组将被丢弃。分组到达目的节点后将直接由地址解复用器送到相应的端口,而后由端口将分组送到目的代理。

2.2 动态源路由协议(DSR

DSR是一种基于源路由的按需路由协议,它使用源路由算法而不是逐跳路由的方法。DSR主要包括两个过程:路由发现和路由维护。当节点S向节点D发送数据时,它首先检查缓存是否存在未过期的到目的节点的路由,如果存在,则直接使用可用的路由,否则启动路由发现过程。具体过程如下:源节点S将使用洪泛法发送路由请求消息(RREQ,RREQ 包含源和目的节点地址以及唯一的标志号,中间节点转发RREQ,并附上自己的节点标识。当RREQ 消息到达目的节点D或任何一个到目的节点路由的中间节点时(此时,RREQ中已记录了从S到D 或该中间节点的所经过的节点标识,D或该中间节点将向S发送路由应答消息(RREP,该消息中将包含S到D的路由信息,并反转S到D的路由供

? 74