Ad hoc网络TORA和DSR路由协议的分析比较

郑创明 张升华

(中国电子科技集团公司第七研究所 广州510310)

摘 要: T ORA和DSR路由协议是Ad hoc网络中具有成果性的两种后应式路由协议。分别对两种路由协议的建立、维护方面进行了分析对比,并给出了两种协议的优缺点。最后通过仿真从路由分组开销、路由建立时间和发送数据分组信息几个方面进行分析论证。

关键词: TORA DSR 路由协议 Ad hoc网络

在Ad hoc网络的路由协议中普遍认可的代表性成果有DSR[1]、TORA[2]、DSDV[3]、WRP[4]、AODV[5]、和ZRP[6]等。源头性的创新性研究主要集中在2001年以前,后续的成果多为这些协议的改进,目前路由协议的研究仍然是Ad Hoc网络成果最集中的部分。这些路由协议根据不同的角度进行分类,从路由发现策略的角度可分为先应式的路由协议(主动路由)和后应式的路由协议(按需路由)两种类型。DSR和T ORA是MANET工作组提出的比较具有成果性的后应式路由协议,本文通过深入研究DSR和T ORA的实现方法,对DSR和TORA 的性能进行分析比较,并通过仿真进行论证。

1 动态源路由协议(DSR)

动态源路由协议DSR(Dynamic Source Rout ing)最重要的一个特点是利用了源路由[1]。也就是说,发送包的源节点知道到达目的地的完整路径,即路径所经过的节点地址有序列表。这些路径存于路由缓存器中,数据分组的包头携带该源路由。这种源路由的方法避免了数据分组经过的中间节点不停更新路由的需要,而且允许节点在转发或无意中收到数据分组时,将最新的路由信息存于它的路由缓存器中以备将来所需。协议的所有操作都是基于按需求的,允许数据分组动态的根据需要对当前路径的变化做出反应。DSR协议包含两个重要的机制:路由搜索和路由维护。

1.1 路由搜索机制

当在MANET中的一个节点要发送数据分组给一个目的节点时,路由搜索程序向网络广播路由请求RREQ(Route Request)包(该包会记录下经过的节点地址有序列表),每个接到RREQ包的节点又重广播它(但丢弃收到的重复的路由搜索包)。RREQ包格式如图1所示。

分组类型分组ID其他控制信息源地址目的地址经过的节点列表信息

图1 RREQ数据分组格式

当目的节点或路由缓存中存在通向目的地的路径的中间节点收到RREQ时,发送一个路由应答包RACK(Route Acknow ledge),把RREQ包中的路由发回给源节点。由于无线链路存在不对称性,因此RACK包不能简单的按RREQ来时的路径发回源节点,若该节点的路由缓存器内已存在回源节点的路由,则RREQ可经这条路径回源节点;否则,要启动路由搜索程序,为了避免相互寻找对方,造成路由搜索循环,在此路由搜索报文中必须附带想要发送到源节点路由应答包RACK。源节点收到RACK 包后将此路径加入其路由缓存器中。RACK格式如图2。

分组类型分组ID其他控制信息源地址目的地址路径节点列表

图2 RACK数据分组格式

1.2 路由维护机制

只有当路由在使用时,才对它进行维护。即当路径上某个节点发现数据分组无法发送到下一跳节点,从自己路由缓存中找出路由,并向源节点发送一个路由出错包(RERR),使源节点将自己的路由缓

收稿日期:2005 01 22

存中的路径删除。若还有数据分组要发送而又没有找到目的节点的有效路由信息,则源节点要重新启动路由搜索程序来获得新的路径。为了防止节点在相应路由搜索时,由于同时发送路由应答包RACK 引起大规模的争夺信道冲突,在发送RACK 前先要延时:

delay=H (h-1+r)(1)

其中,h:节点到目的节点的距离,即RACK 的跳距;r:随机浮点数;H:较小的时延常数。

另外,为了节约控制开销,通过对路由搜索请求包RREQ 设置TTL 限制搜索范围。先在1跳范围内搜索,失败后再以2的倍数增大TT L 。

2 临时按序路由算法(TORA)

T ORA(Tem porally Ordered Routing Algorithm)协议是一种按需路由协议[2],分为路由建立、路由维护和路由消除三个过程。过程中用到三种分组格式:路由请求分组QRY 、路由更新分组UPD 、路由擦除分组CLR 。每个节点i 都分配一个五元素的状态变量HEIGHT =(tau[i],oid[i],r[i],delta[i],i),其中前三个变量(tau[i],oid[i],r [i])定义为参考水平,(delta[i],i)定义为节点i 的高度。tau[i]为时间标签,oid[i]引起节点i 参考水平改变的节点ID,r [i]为反射状态标志,delta[i]节点i 在链路中的序号,i 为网络中节点i 的ID,目的节点j 用ZERO=(0,0,0,0,j)表示,NULL=(-,-,-,-,k)表示节点k 不在传输链路中,网络初始化时所有节点的状态为NU LL 。2.1

路由建立

图3 T ORA 路由建立过程

当源节点A 需要建立路由时,它首先发送一个路由请求分组QRY(图3a),第一次收到QRY 分组的节点设定RRi=1并广播QRY 分组,如果收到重复的QRY 分组立即销毁(图3b)。当目的节点j 收到QRY 分组时,首先设定自己的H j =ZERO,然后销毁QRY 分组并产生一个包含源节点信息和自己H j 信息的U PD 分组。对于RR i =1的节点i 首次收到UPD 分组时,根据T ORA 路由建立算法[2]修改H i 、NH i 和LS i,k ,然后广播UPD 。当源节点收到UPD 分组时,建立算法并修改H i 、NH i 和LS i,k ,销毁UPD 分组,整个路由建立(图3c)。从图中可以看出,节点的高度从源到目的分别为:3 2 1 0,因此该协议成为临时按序的路由协议。2.2

路由维护

图4 T ORA 路由更新过程

维护路由只发生在H i (i N )不等于NULL 的节点之间。在时间为1时,节点C 检测到它的下游链路C 、D 之间的无线链路断开后首先修改自己的Hc=(1,C,0,0,C),产生一个包含Hc 信息的UPD 分组并在网络中广播;节点B 收到U PD 分组后,修改HB=(1,C,0,-1,B)并广播UPD 。当节点A 收到UPD 后,由于还存在通过节点F 到达目的节点的下游链路,所以直接销毁UPD 分组。2.3

路由消除

图5 T ORA 路由消除过程

假如在时刻2节点A 和节点B 之间的无线链路断开(图5a),节点B 重新定义一个新的参考水平并设定H B =(2,B,0,0,B),产生一个UPD 分组并广播该分组(图5b),节点C 收到UPD 分组后,由于节点C 此时没有任何下游链路,且收到的U PD 分组内容的参考水平为(2,B,0),所以设定H C 中的反射标志为1,设定H C =(2,B,1,0,C)(图5c),并修改UPD 分组内容,广播该分组。当节点B 收到节点C 发来的UPD 分组,根据路由准则设定H B =(-,-,