一种基于ABR协议的Ad hoc网络路由方案

宋子彧，袁道华，成文龙

1.四川大学计算机学院，四川成都 610065

2.军事经济学院襄樊分院基层财务系，湖北襄樊 441118

一种基于ABR协议的Ad hoc网络路由方案

宋子彧1，2，袁道华1，成文龙1

1.四川大学计算机学院，四川成都 610065

2.军事经济学院襄樊分院基层财务系，湖北襄樊 441118

ABR协议是移动自组网中的一种按需路由协议，采用路径有效时间长短作为选路标准。本文介绍了ABR协议，在其基础上提出了一种保存路由路径的方案，该方案以耗费较小开销为代价，在一定程度上减小数据传输时延。最后，对所提出的方案进行了简要的性能分析。

ABR协议；Ad hoc 网络；路由；稳定性；按需路由

0 引言

近年来，Ad hoc网络一直是国内外研究的热点领域。特别是随着网络时代的发展，由于人们更乐于享受没有拘束的无线网络环境，因此，进一步研究无线移动自组网络从而开发相应的产品，极具现实意义。什么是Ad hoc网络呢？Ad hoc网络是一种分布式无线多跳网络，它是由一组具有路由功能的节点组成且不依靠任何预设的基础设施的网络。该网络中的节点既为路由器又为主机，节点之间相互协作，通过无线链路进行通信、交换信息。然而，自组网中节点的移动性、节点传输范围的有限性等原因，使得节点之间的数据传输不可能简单依靠固定的路由协议，必须设计新的路由协议，所以，路由协议成了自组网研究的一个热点。

1 ABR协议

目前，支持Ad hoc网络的路由协议有很多。其中，ABR（Associativity Based Routing，基于稳定性的协议）协议[1]是一种源点发起的按需路由协议。它的一个重要特点是打破了以“最短路径”作为路由选择的准则，从路由的有效时间来考虑选路，采用路径的稳定性(路径有效时间长短)作为选路的标准。当源节点请求路由时，引起路由发现过程；当已经确定好的路由因源节点、目的节点、中间节点或subnet-bridging MHs[2]（因自身在两个虚拟移动子网间移动而将子网分成更小子网的主机）的移动而改变时，促发路由重建阶段。这就是ABR协议的两个主要的组成阶段。具体过程如下：

1）路由的建立

源节点采用洪泛的方式广播路径查询（BQ）分组，收到BQ分组的节点建立一条到源节点的路由，并在BQ分组中添加自己的ID和“稳定性信息”，然后继续广播BQ分组。中间节点不允许回复路由应答分组。当目的节点收到第一个BQ分组后，等待一段时间，以收到通过其他路径到达的BQ分组的副本，然后选择一个稳定性（associativity[3]）最高的路由，若两条路由的稳定性相同，则选择跳数较少的那条。一旦选定某条路由，目的节点将沿选定的这条路径发送一个路由应答分组。

2）路由重建

当路径的稳定性发生变化，则启动路由重建，首先节点试图从局部进行路由的修复，若不能成功修复，则向上游节点发送RN（route notification）消息。最坏的情况是源节点收到RN消息后，启动一个新的路由建立过程。此外，ABR协议提到，当源节点不再需要路由时，则通过洪泛RD（Route Deletion）分组的方式删除路由，或是超时自动完成路由的删除。

2 提出的方案

在ABR协议中不使用缓存，对已经建立起来的稳定值高的路由采取超时或无用即删除的策略。但是，如果某条稳定值高的路由在一定的时间段内再次或多次被利用，那么重建这条路由也必将产生不小的开销。有没有一种较好的方法能够既降低开销又达到路由重用的目的呢？是否可以考虑通过“牺牲”节点的少许缓存，不将已建立好的稳定值高的路由在使用完后立即删除，而是通过“监视”这条既定路由的稳定指数FOA（figure of associativity），当FOA处于某个数值范围，则保留这条路由；当FOA不在此范围再删除之？基于这样的考虑，提出如下实现步骤：

1）既定路由FOA参量的选定

Ad hoc网络中，链路是由移动节点进行相互通信形成的。判断某条链路是否稳定，归根到底就是判断这条链路上的各个相邻节点之间是否稳定。因此，这里先给出节点间FOA参量的定义。定义FOAx-y表示邻节点y对移动主机x的稳定程度。该数值通过下列方式得到：当移动的节点y刚进入x的范围内，x就为该节点设一个FOAx-y，初始值可以设定为0，该FOA随时间线性增加（如图1）。移动主机x周期性的产生一个hello信息，告知其邻节点自己的存在。当邻节点y收到hello信息并回复后，x就将其为节点y设置的FOAx-y减小，且FOAx-y值减小的数值等于FOAx-y在节点x周期性发送hello信息的周期时间间隔中所增加的数值。也就是说，只要邻节点y还在x的范围内，x为节点y设置的FOAx-y值就会保持在一定数值以内。邻节点y在一段时间内没有回复移动主机x的hello信息，则FOAx-y将逐渐增大。如果邻节点y只是因为阻塞没有及时回复hello信息，则x就在超时较短的时间内再次发送hello信息，收到节点y的回复后，x将FOAx-y设置到警戒值以下。如果y长时间没有回复hello信息，则FOAx-y最终将超过禁用值。接下来，定义既定路由的FOA。设ABCDE为一条已经通过ABR协议选定的路由（如图2），A为源节点，E为目的节点。设定FOAa-b表示B节点对A节点的稳定指数，FOAb-c表示C节点对B节点的稳定指数，依次可得到FOAc-d，FOAd-e，则该路由的FOAa-e取 FOAa-b、FOAb-c、FOAc-d、FOAd-e这4个值中的最大值，即链路采用凸性加权得到既定路由的FOA。

2）获取既定路由FOA的初始值

节点值之间的稳定指数FOA按照上述方式获取后，与ABR协议中的“associativity ticks[2]”一并存储到节点缓存中。路由的发起过程仍然按照ABR协议所述，源节点首先广播BQ分组，寻找一条到目的节点的路径。目的节点DEST在收到第一个BQ分组之后的一个适当的时间内，就知道所有可能的路由和它们的稳定程度。DEST选择稳定性最高且跳数少的路由发送RREP。此时，由于DEST的这个REPLY分组的长度可变，所以，可以在其中附加一帧记录链路的FOA信息。DEST的沿着选定的路由发送RREP，其下一个节点收到RREP后，将其存储的DEST对它的稳定指数FOA记录在RREP的附加帧中，然后转发该RREP。而接下来的节点收到RREP后，都比较前一发送节点对于自己的FOA值与RREP中的FOA值，将FOA值较大的记录到RREP中。依此类推，直到源节点。这样，当源节点收到目的节点的RREP后，就获取了该路由的FOA初始值。当然，这个数值肯定是小于前面提到过的警戒值的。

3）既定路由的删除

源节点到目的节点的路由传送完数据后，路由上的节点并不将该路由删除，而是将这条路由缓存起来备用。当该路由上两个相邻节点不在各自的范围内一段时间后，上游节点（靠近源节点端的节点）对其相邻的下游节点的FOA会超过禁用值。此时，上游节点将这个FOA通过广播BQ分组发送出去，而源节点收到该BQ分组后，发现路由的FOA超过了禁用值，于是广播一个路由删除（RD）分组，通知这条路由上的所有节点删除这个路由。

3 方案性能的定性分析

在ABR协议中加入既定路由稳定指数FOA的判定，能较为有效保存稳定性高的路由。下面对方案的性能进行定性分析：

1）端到端的平均时延

端到端的平均时延定义为单位数据包从源节点发出到目的节点接收的时间差值[4]。时延越小，说明响应速度越快。在本方案与原ABR协议比较，当移动节点的移动速度较快时，由于节点之间稳定值不高，既定路由维持时间短，端到端的平均时延与原ABR协议基本相同。当移动节点移动速度较慢时，由于对既定路由的保存，本方案中数据包传递的时延要小于原ABR协议的数据包传递时延。

2）路由开销

路由开销是指发送的路由分组的总的个数。对于在多跳路径上发送的分组，每发送一次计算为一次发送[5]。该统计量反映路由协议的效率。与原协议相比，本方案多出的开销主要在节点之间稳定指数的获取以及既定路由的各节点对路由的临时保存上。当移动节点分布较密集且移动速度较慢时，由于各节点维持其邻节点的稳定指数个数较多，开销较大，但是，考虑到移动节点移动缓慢时，本方案减少了路由重建的开销，实际开销多少仍需要通过仿真实验后得出结论。而当移动节点分布较为疏散时，本方案造成的开销与原协议大致相等。

4 结论

本文通过研究Ad hoc网络的ABR协议，分析该协议如何采用路径有效时间长短作为选路标准，提出了一种合理保存稳定指数较高路由路径的方案。此方案的提出，是考虑到处于Ad hoc网络的移动节点在实际的网络环境中，并不一定时刻都在迁移。在某些地域范围内，例如小区、办公楼等，移动节点是有可能在一段较长的时间内保持位置稳定的。因此，对于基于ABR协议建立起来的路由路径，可以反复利用。采取本文设计的方案，虽然会增加稳定节点用于缓存路由的控制开销，但是可以减小稳定节点本身和其他节点用于路由重建的开销。另外，让稳定性强的移动节点存储路由，必然会增加这些节点的负载。对于这些节点来说是不公平的。所以，下一步研究的重点是对此方案加入对路由负载的考虑，并采用网络仿真器NS2做相关的仿真试验，希望通过这些工作进一步优化ABR协议，为在现实的Ad hoc网络环境中有效的应用ABR协议做准备。

[1] 于宏毅. 无线移动自组织网[M].北京：人民邮电出版社，2005.

[2] Chai-Keong Toh. Associativtity-Based Routing For Ad-Hoc Mobile Networks[J]. Wireless Personal Communications Journal，1997，4（2）：103-139.

[3] Chai-Keong Toh. Associativtity Based Long-Lived Routing. Special Issue on Mobile Networking & Computing Systems， 1997，4（1）.

[4] 段云飞，周丽琼，杨磊.几种典型Ad hoc路由协议的仿真分析[J].电力系统通信， 2009，30(200)：59-63.

[5] 陈林星，曾曦，曹毅.移动Ad hoc网络[M].北京：电子工业出版社，2006.

TP393

A

1674-6708（2010）18-0138-02

宋子彧，硕士研究生，主要研究方向：计算机网络、分布式并行计算

袁道华，教授，主要研究方向：分布式并行计算、计算机网络、移动计算

成文龙，硕士研究生，主要研究方向：多媒体技术