基于位置预测的Ad hoc网络路由协议研究
2.3.2 按需驱动路由协议
按需路由协议又叫被动路由协议，与表驱动路由协议（主动路由协议）相反，按需路由协议认为Ad Hoc网络是一个动态拓扑结构的自组织网络环境，不需要维护更新整个网络的路由信息。它只有在没有到达目的节点路由信息的时“按需”进行路由发现。它的优点是不需要周期性在网络中广播路由信息，维护更新路由表，节省大量的网络资源（如带宽、电源等）。缺点是发送数据分组一般需要等待因路由发现所引起的延时。按需路由协议通常由路由发现和维护两个过程组成。当源节点没有去往目的节点的路由时，触发路由发现过程。一旦路由上某一节点被移除时，将启动路由维护过程。
按需路由协议仅仅维护活动的路由信息从而大大减少表驱动路由协议中路由开销。也就是说仅仅需要决定和维护那些有数据要传输到特殊的目的节点的路由，不需要维护整张路由表。路由发现是在网络中以洪泛的方式发送一个路由请求数据包，当节点收到路由请求数据包，首先检查自己是否是目的节点或是否有到达目的节点的路由，如果是目的节点或有到目的节点的路由时，它将沿着逆向路径给源节点发送一个路由应答包，或者通过将携带有路由的回答包洪泛给源节点，否则，它将发送到下一节点。因此按需路由协议的路由发现的开销随O（N+M）增长，而对于双向链路是随O（2N）增长。为了更好地实现网络的整体性能，研究人员从不同的角度提出很多按需路由协议。下面介绍几种典型的按需路由协议。
（1）DSR(Dynamic Source Routing) [29]
DSR协议是最早采用按需路由思想的路由协议，它包括路由发现和维护两个过程。它的主要特点是借鉴了IEEE802.5协议用于在网桥互连的多个令牌环网中节点寻找路由的源路由机制进行分组转发，可以避免出现路由环路。DSR的优点是在移动节点的缓存中存贮多条路由，源节点首先在缓存中查找是否有有效的合适的路由可用，如果存在有就不用进行路由发现直接使用，否则启动路由发现机制。这种优点在拓扑结构变化不大的网络情况下相当有利的。另外DSR协议不需要周期性发送HELLO消息，节点可以进入睡眠状态以节省能量。其缺点是每个数据分组都携带完整的路径信息，增加数据分组的大小，造成很大的路由开销。只适合中小型网络。
（2）AODV(Ad hoc On demand Distance Vector) [30]
AODV协议是在DSDV协议的基础上使用按需机制改进而来的一种路由协议。它不像DSDV那样需要维护所有的路由信息。
源节点寻找路由时，向它们的邻节点广播一个路由请求数据包。如果收到路由数据请求包的节点已经处理过这个包，它就丢掉它，否则检查其是否知道到目的节点的路由或者它本身就是目的节点，如果是则用最新的信息来响应，否则继
- 14 -
工程硕士学位论文
续向其邻节点广播。AODV协议通过使用序列号来实现无环路由。为了实现逆向路由应答包，节点向其下一级邻节点转发路由请求数据包时，同时记录其上一级节点。在动态的Ad Hoc网络中如果中间节点移动，造成链路断开，就会给其上游节点发送一个链路断开信息，一直到源节点，如果需要源节点就重新启动路由发现机制。如果源节点移动，那么它将直接重新启动到目的节点的路由发现。
在AODV协议中仅携带目的地址，并不携带完整的路由信息，大大降低了路由开销。在AODV中路由回答包中也仅携带目的IP地址和序列号，并不携带路由中每个移动节点的地址。动态拓扑结构对AODV路由协议影响不大。然而路由的建立和链路断裂再次启动的路由发现都会耗费很大的延迟，特别是网络网络规模的增加会引入额外的延迟和消耗更多的带宽。
（3）TORA(Temporally-Ordered Routing Algorithm) [31]
TORA协议是基于有向无环图（Directed Acyclic Graphic，DAG）算法的一种按需路由协议。它由路由发现、路由维护和路由消除三个过程组成。TORA的路由发现与其他按需路由协议基本一样，首先在网中广播路由请求数据分组，只有在路由应答中应用了DAG算法。其主要思想是：给每个移动节点设定一个相对于源节点“度量值”，其中目的节点的“度量值”最低，从源节点到目的节点形成一条或多条的有向路径，形成一个从源节点到目的节点的有向无环图。通过路由更新分组在回到源节点的过程中形成。在Ad Hoc网络拓扑结构发生变化时，TORA协议采用DAG算法重新构造变化的有向无环图，迅速重新生成路由。
TORA的优点是在Ad Hoc网络拓扑结构发生变化时，减少邻节点到远处的控制消息；另外支持多播功能。TORA的缺点是会产生临时无效路由。
2.3.3 混合路由协议
混合路由协议是一类新的协议，是结合了主动路由协议和被动路由协议的优缺点，即在小范围内使用主动路由协议，维护准确的路由信息，可以减少路由控制消息传播产生的延时。当目标节点较远时，通过被动路由协议查找发现路由，这样既可以减少路由协议的开销，也减少了报文传送时延。
（1）CGSR ( Clustered Gateway Switch Routing，簇头网关交换路由) [32] CGSR是一种分级结构的路由协议。通过簇首管理算法任意选择部分合适的移动节点作为簇首，构成骨干网络，然后以簇首为单位对网络进行簇的划分，簇首负责簇内节点的路由管理与相互之间通信，簇间通过簇首进行通信。簇首并不是永远不变的，在一定的网络环境下簇首与簇内成员可以相互转化。CGSR协议中每个移动节都维护两张路由表和一张簇成员表。
- 15 -
基于位置预测的Ad hoc网络路由协议研究
图2.3 CGSR路由协议的路由机制
如图2.3所示，当源节点S进行路由发现时，首先将路由报文交给簇首A，A首先找自身簇成员列表，若目的节点D不在簇内，则通过网关节点C转发到下一个簇首B，直至报文转交给目的节点D。若目的节点N与源节点S在同一簇内，则直接由簇首A转发，但S不能直接转发报文至N，即使在直接通信范围之内。
该协议采用了分层的路由查找机制，路由的查找通过簇首节点和网关节点来完成，绝大多数数据报文只在簇首间进行转发，在大规模的网络中避免了大量路由查找报文的泛洪，一定程度上降低了查找报文的开销，并具有良好的可扩展性。缺点是增加了算法复杂度和簇首的维护开销，实用于较大规模的Ad Hoc网络。
（2）ABR（Associativity-Based Routing，基于联合稳定度的路由协议）[33] ABR是一个基于节点及相应链路在时间和空间上的稳定程度的路由选择协议。根据路由稳定的时间和路由信号的强度作为路由选择的度量。网络中每个移动节点周期性向其邻接点广播一个信标，每收到一次信标报文，相应的节点稳定度就增加一，稳定度越高，表明拓扑结构变化越小，相应的路由越稳定。一旦拓扑结构发生变化链路中断，联合稳定度会重新设置。
ABR选择的路由具有较高的路由持久性和传输质量，提高了数据的成功传输率，并降低了路由破裂和重构的次数，减少了路由开销。它的另一个优点是采用了局部查找机制，减少了路由查找的开销和路由重构时间。协议的缺点是周期性发送信标报文和计算路由稳定度会带来一些额外路由开销，带宽利用率下降和电源使用寿命缩短。
2.3.4 实现机制比较
为了对以上几种目前研究最多的典型Ad Hoc路由协议进一步的研究，我们给出它们的实现机制比较，见表2-1。
鉴于Ad Hoc网络路由协议要求路由开销低和电源能耗小，复杂度高的路由协议将对网络整体性能带来较大影响，因此，时间复杂度和通信复杂度是路由协
- 16 -
工程硕士学位论文
议评价的两个重要指标。时间复杂度是指执行一次路由协议操作所需要运行的步数，通信复杂度是指执行路由协议操作所需要传送的信息数。
在表2-3中由于按需驱动路由协议由路由发现和路由维护组成，其时间复杂度和通信复杂度是不同的（如DSR存在缓存路由，路由维护时间复杂度为0），另外，应答报文是按己建立的路由进行反向传输，不需要全网洪泛，通信复杂度应小于O(2N)。为方便比较，表中指的都是路由建立过程的复杂度。
表2.3 典型Ad hoc路由协议实现机制比较
时间复杂度 通信复杂度 逻辑结构 驱动方式 路由测度
DSDV O（d） O（N） 平面 表驱动 最短最新路径
DSR O（2d）
AODV O（2d）
TORA O（2d）
WRP O（h） O（N） 平面 表驱动 最短路径
CGSR O（d） O（N） 分级 表驱动 最短路径
ABR O（2d） O（2N） 平面 按需 联合最稳最短路径
路由断裂与
维护
重新查找路由表
路由缓存
无
缓存路由或重建 有
无 源节点重建
链路翻转路由修复 无
重新查找路由表 无
重新查找路由表 无
无 局部修复
O（2N） O（2N） O（2N） 平面 按需 最短路径
平面 按需 最短最新路径
平面 按需 最短路径
2.4 本章小结
本章从理想的Ad Hoc网络路由协议需要具有的特点着手，对路由协议按路由协议建立时间、算法类型、拓扑结构和协议的功能进行分类研究，比较其性能，最后对几种典型的路由协议进行详细的分析研究。通过分析研究，目前Ad Hoc路由协议基于不同的出发点和机制，尚无比较完善的各方面性能都比较优越的路由协议，都存在或多或少的问题。
- 17 -
基于位置预测的Ad hoc网络路由协议研究
第3章 Ad Hoc路由协议的OMNeT++仿真与性能分析
OMNeT++[34]是Objective Modular Network TestBed in C++的英文缩写，它是开源的基于组件的模块化的开放性网络仿真平台，是近年来在科学研究和工业领域里逐渐流行的一种优秀的网络仿真平台。OMNeT++作为离散事件仿真器，具备强大完善的图形界面接口和可嵌入式仿真内核，同NS2，OPNET和JavaSim等仿真平台相比，OMNeT++可运行于多个操作系统平台，可以简便定义网络拓扑结构和环境参数的设置，具备编程、调试和跟踪支持等功能。OMNeT++主要用于通信网络和分布式系统的仿真，目前最高版本为OMNeT4.0。本章首先简要介绍了OMNeT++仿真的一些基本原理[35]和仿真流程，然后用OMNeT++对四种常见Ad Hoc路由协议在不同负载下的性能变化进行仿真分析，得出相应的结论。
3.1 OMNeT++仿真的基本原理
OMNeT++主要由六个部分组成：仿真内核库（simulation kernel library，简称Sim），网络描述语言编译器（network description compiler，nedc），图形化的网络编辑器（graphical network description editor，GNED），仿真程序的图形化用户接口——Tkenv，仿真程序的命令行用户接口——Cmdenv，图形化的输出工具——Plove和Scalar。 Sim是仿真内核和类库，用户编写的仿真程序要同Sim连接，Sim在OMNeT++中占据最为核心重要的地位。
OMNeT++通过NED语言可以对大量的组件（如通道等）、简单和复合模块的类型进行描述，当然模型中较为简单的网络拓扑结构可以使用GNED，但复杂网络的拓扑描述还应该用NED源文件方式书写。
OMNeT++通过一个已定义的接口程序，实现用户接口和仿真内核的交互，很好地实现仿真程序的人机交互，无需改变仿真内核，就可以实现不同类型的用户接口。同样无需更改模型文件，仿真模型可在不同接口下运行。用户可以在强大图形化用户接口下测试和调试仿真程序，并最后可在简单快速的用户接口中运行，而且该接口支持批处理。同时，OMNeT++允许模型内部机制对用户可视化，也允许用户启动和终止仿真，并更改模型内部的变量。OMNeT++中的图形化接口是一个用户工具，可方便用户了解模型内部的运行机制。
目前OMNeT++支持两种用户接口，即Tkenv和Cmdenv。Tkenv是一个简便易用的图形窗口化的用户接口，支持跟踪，具有调试和执行仿真的功能，用户可以在Tkenv接口下对仿真进行测试和调试。它在执行仿真过程中的任意时刻都能够提供详细的状态信息。Tkenv的主要特征有：各模块的文本输出有其独立的窗
- 18 -