摘 要：移动Ad hoc是下一代网络(NGN)的重要组成部分，无需固定基础设施的临时网络。重点研究了目前典型的Ad hoc网络的路由协议，设计并实现了在NS-2环境下典型协议的仿真场景和性能分析比较。对Ad hoc路由协议的研究和组网具有参考指导意义。
关键词：Ad hoc网络；仿真；路由协议
移动Ad hoc网络是一种把移动通信和计算机网络结合在一起的网络，它具有分布式、自组织、自配置、自管理等特征，不需要固定基础设施的支持，能够在不能或不便利用现有网络基础设施的情况下提供一种通信支撑平台，从而拓宽了移动通信网络的应用场合，可广泛应用于国防战备、抢险救灾、应对突发事件等无法得到有线网络支持或只是临时需要通信的环境，是下一代网络的重要组成部分。
路由技术担负着为数据分组寻找路由和将其传送到目的地的任务，是移动Ad hoc网络中的一项关键技术，而路由算法和协议则是路由技术的核心内容，直接关系到时延、吞吐率和成功率等网络性能的优劣。移动Ad hoc网络所具有的多跳、动态拓扑、时变信道、资源受限等特点，给路由算法和协议的设计带来很大挑战，传统的有线网和有中心无线网络的路由算法和协议无法在移动Ad hoc网络中直接应用。为此，需要根据移动Ad hoc网络的特点设计专门的路由算法和协议，这是移动Ad hoc网络研究和设计的主要技术难点之一。网络仿真模拟环境NS-2对Ad hoc网络路由协议的研究提供了更为便捷的手段，本文对Ad hoc路由协议进行了分类研究，对典型的路由协议在NS-2环境下仿真实现，并对其性能进行跟踪分析。对Ad hoc路由协议的研究具有参考意义。
1 Ad hoc网络路由协议
路由是把信息从源经过中间网络节点(至少有1个)穿过网络传递到目的节点的行为，中间节点两个基本的动作为确定最佳路径和通过网络传输信息，即选路和传输数据。传输数据相对来说比较简单，而选择路径很复杂。
1.1 Ad hoc路由协议的研究分类
近年来，研究人员提出了上百种路由协议的方案。可以根据不同的原则进行分类研究：
(1)根据接收节点的数量[1]，可分为单播(unicast)：单播通信中目的节点只有一个，实现一对一的通信，单播路由协议是研究得最多的路由协议；组播(multicast，也被称为多播)：一对多的通信，目前有基于树的多播路由协议和基于网格的多播路由协议；广播(broadcast)：所有主机都接收数据。
(2)根据路由发现的策略可以分为先应式(Poractvie)路由，也被称为表驱动(Table-Driven)路由，以及反应式(Reactive)路由，也被称为按需(On-Demand)路由[2]。表驱动路由协议采用周期性的路由分组广播，交换路由信息。每个节点维护一张或多张表格，这些表格包含到达网络中其他所有节点的路由信息。当主机需要和其他主机通信时，可以直接从路由表格中获得相应的路由。当检测到网络拓扑结构发生变化时，节点在网络中发送更新的消息，收到更新消息的节点更新自己的表格，以维护一致的、及时的、准确的路由信息。源节点一旦要发送报文，可以立即得到到达目的地的路由。但是不管有无通信需求，都要进行路由信息交换，它的优点是:当节点需要发送数据分组时，只要去往目的节点的路由存在，所需延时很小，比较适合有实时和QoS要求的网络通信。但为了使路由更新能紧随当前拓扑结构的变化，先应式路由协议需花费较大开销，而且动态变化的拓扑结构可能使路由信息过时，路由协议不易收敛。表驱动路由协议主要有DSDV[3]、FSR[4]、DBF[5]、DTDV[6]、HSR[7]。按需驱动路由协议，也称为被动路由协议。与表驱动路由协议相反，按需路由协议根据发送数据分组的需要按需进行路由发现的过程，主机只查找和维护自己需要使用的路由，而不是到所有主机的路由。所以其内容可能仅仅是整个网络拓扑结构信息的一部分。典型的按需路由协议有DSR、AODV、TORA[8]。
(3)根据网络逻辑视图的不同，可分为平面(Flat)路由与分级(cluster-based)路由。平面路由协议的网络逻辑视图是平面结构，网络结构比较简单，路由协议在平面的逻辑空间里运行，移动节点的地位是平等的，即主机和主机都是平等的。它们所具有的功能完全相同，共同协作完成节点间的通信，每个主机同时还是路由器，负责为其他主机转发报文。平面结构的网络管理比较简单，但路由开销比较大，扩展性较差，支持的用户节点较少，限制了网络的规模；分级路由协议中，网络由多个簇组成。节点分为两种类型:普通节点和簇头节点，处于同一簇的簇头节点和普通节点共同维护所在簇内部的路由信息，簇头节点负责所管辖簇的拓扑信息的压缩和摘要处理，并与其他簇头节点交换处理过后的拓扑信息。
1.2 三种典型的路由协议
1.2.1 目的节点序列距离矢量协议(DSDV)
DSDV是表驱动的平面路由协议，基于Bellman-Ford算法，通过给每个路由设定序列号避免路由环路的产生。在DSDV路由协议中，每个节点都必须存储并维护一张路由表，该路由表记录着目的节点、跳数、下一跳节点和目的节点序列号。其中目的节点序列号由目的节点分配，主要用于判别路由是否过时，并可防止路由环路的产生。每个节点必须周期性地与邻节点交换路由表信息，以维持所有节点都拥有完整的路径信息。当然也可以根据路由表的改变来触发路由更新。DSDV节点维护着整个网络的路由信息，数据需要发送时可以立即传送，使用于一些实时性要求较高的网络环境中。但是在拓扑变化频繁的网络中，DSDV存在一些问题：主要是节点维护路由信息的代价很高，因此不适用于规模大的网络。
1.2.2 动态源路由协议(DSR)[9-10]
DSR是一种按需平面路由协议。每个节点都有路径缓存器，而路径信息则保存在每个封包的缓存标题中。当发送者发送报文时，在数据报文头部携带到目的节点的路由信息，该路由信息由网络中的若干节点地址组成，源节点的数据报文就通过这些节点的中继转发到达目的节点。与基于表驱动方式的路由协议不同的是，在DSR协议中，节点不需要实时维护网络的拓扑信息，因此在节点需要发送数据时，如何能够知道到达目的节点的路由是DSR路由协议需要解决的核心问题。路由发现过程是：源节点广播路由请求分组给其邻居节点，邻居节点收到路由请求分组后，轮流把自己的地址添加到路由请求分组，并转发补充了的路由请求分组。这个过程一直持续到有一个路由请求分组到达目的节点。
若发现自己的地址已经在记录中，就停止广播。每个请求都有一个由源节点所设置的ID号，每个节点都有一个路由缓存，存储最近转发过的路由请求，以便查询接收的是否为同一个请求，这样保证每个节点只转发一次。当路由请求分组到达目的节点时，节点要返回一个路由应答分组，通知节点己收到该路由请求。到达目的节点的路由请求分组包含从源节点到目的节点的路由，目的节点就可以选择利用反向路由来发送路由应答(这里必须是双向链接的)，或者发起另一个新的路由发现过程返回到源节点。从源节点到目的节点可能有很多条路由，一个源节点可能从目的节点那里收到很多个路由应答。DSR协议把这些路由缓存在路由缓存中以备将来所用。DSR协议主机不需要周期性地发送路由发现报文，支持主机睡眠。但是数据收发的每个报文都需要携带完整的路由信息，减低了网络带宽的利用率。
1.2.3 AODV
AODV路由协议是一种按需路由协议，允许节点获得许多路径到达它所需要到达的目的节点，而且不要求节点维护这些路由信息。当网络拓扑结构发生变化时，它能快速收敛，具有断路的自我修复功能，不但计算量小，存储资源消耗小，而且对网络带宽占用也小。通过使用目的节点序列号，协议实现了无环路由，并且避免了无穷计数的问题。为了避免单向链路引起的错误操作，协议引入了一个黑名单，把和自己是单向链路的邻居节点放入黑名单中。
AODV有四种基本的协议帧:RREQ(Route Request)帧、RREP(Route Reply)帧、RERR(Route Error)帧和RREP-ACK帧格式。
当一个节点要传送封包给另一个目的节点时，会先去检查它的路由表。若找不到到达目的节点的路径信息时，便广播RREQ寻找路径，收到RREQ的节点去检查是否是发给自己的，如不是就查看是否有以自己为中继的可达目的节点的路由，如没有，就修改封包内的信息后广播出去。每个RREQ都有一个ID，当节点收到RREQ后可以确认自己是否收到一个ID，如收到过久则丢弃，以确保循环的产生。
2 路由协议的性能分析
衡量Ad hoc网络路由协议的性能一般有定性指标和定量指标两种。
2.1 定性指标
定性指标从整体上描述网络某个方面的性能，如安全性、分布运行性、提供无环路由、是否按需路由等。
MANET路由协议的定性属性包括:
(1)适应动态拓扑：移动Ad hoc网络是一种高度动态的网络，其拓扑不断变化，路由协议的设计要满足拓扑的动态变化。
(2)减少控制开销：移动节点通常靠电池供电，资源有限，协议的设计要节约资源，控制开销要小。
(3)分布式操作:这是一个基本属性，但也应该被规定。
(4)无环路:虽然按照某些定量标准(如性能标准)来说不是必须的，但却可以避免诸如最坏情况现象。
(5)基于需求的操作:在网络中，让路由算法适应基于按需流量模式，而不是假设一种不变的流量分布(在任何时刻在所有节点之间维护路由)，是一种更好的方法。如果可以智能地做到这一点，则可以更加有效地利用网络能源和带宽资源，其代价是增加了路由发现的延时。
(6)先应操作:基于需求操作比较不重要的方面。在某些情况下，基于需求操作增加的延时是不可接受的。如果带宽和能源允许，在这种情况下，就需要先应式的操作。
(7)“睡眠”周期操作:基于能量保存，或其他某种非活动的需要，MANET节点在某段时间内可能会停止发送和/或接收。路由协议应该能适应这种睡眠周期，而不产生非常不利的后果。
(8)路由方式和路由更新方式:不同的路由方式和路由更新方式对协议的影响是巨大的，所有路由协议都必须有路由方式的效率和路由更新方式的效率。
典型协议定性分析如表1所示。
2.2 定量指标
定量指标可以更细致地刻画网络某方面的性能，本文主要对以下几个性能指标进行分析:
(1)数据包成功接收率
数据包成功接收率是应用层信宿接收包数目与信源发送的包数目之比[11]。描述是通过应用层观察到的丢包率，它是路由协议完整性和正确性的指标。
数据包成功接收率=成功接收分组数/发送分组数
(2)端到端平均时延
端到端的平均延迟包含所有可能的延迟时间的总和，如发现路径的缓冲时间、MAC层的重传时间、传送时间等。可以用式(1)计算：
式中，N表示成功传输的分组数，rti表示分组到达目的节点的时间，sti表示分组被发送的时间。
(3)路由开销
路由开销是计算所有路由控制报文(包括路由寻找报文、路由响应报文和路由错误控制报文)的总的字节数与所有报文的字节数之比。对于经过多跳路由传输的分组而言，每经过一跳，就增加一次报文传输。路由开销主要是用来衡量路由协议的效率。
路由开销=路由控制报文字节数/所有报文的字节数
(4)分组数据的丢包率
丢弃的数据包数/发送的数据包数
(5)第一个封包的接收时间参数用来评估路由协议的收敛时间。
3 基于NS-2仿真环境的路由协议性能分析
3.1 NS-2简介和仿真场景建立
NS(Network Simulator)[12]网络仿真器，网络模拟器第二版NS-2(Network Simulator，Version 2)，最初是由美国加州大学伯克利分校(UC Berkeley)开发，目的是为了研究大规模网络和未来网络协议的交互行为。它是一款开放源代码的网络模拟软件，一直以来都在吸收全世界各地研究者的成果，包括CMU大学和SUN等公司的无线网络方面的代码。
仿真实验中，仿真时间设为120 s，所有节点一直处于移动状态，业务代理设置为CBR流，最大的连接数为10条，每秒发出10个封包。在800 m×600 m的范围内，节点数分别设为100、150、200、250、300、400，分别对三种典型路由协议进行仿真。
3.2 仿真结果及分析
对仿真后的trace文件进行分析，AODV结合了DSR和DSDV两个协议的优点，因此一直有较高的数据包投递率，而且较为稳定，但是DSR不适合规模较大的网络。由图1可知，当节点数量增多且不停移动时，DSDV封包的送达比例较低，原因是DSDV的路由表更新不够快，当链路发生变化时，节点不能感知，还使用原来的路由发送数据，导致路由包的丢失。而DSR不适合规模大的网络。
由图2可知，在节点数量较小时，平均传输延迟相当，随着节点数量的增加，DSDV比DSR和AODV大，说明DSDV路由表建立后，随着节点移动和节点数的增加，需要更新路由表次数更频繁，影响包传送的时间。
以图3中可以看出，DSR第一个封包的接收的时间比较早，AODV次之，DSDV最慢。说明DSDV虽然是表驱动的先应式路由协议，但是当节点都在移动时，不见得有可使用的路由协议，等到节点更新路由表时，已经花了一段时间。而DSR协议收敛的速度最快，AODV次之。
作为下一代网络重要的组成部分，Ad hoc网络成为目前的研究热点之一，其关键技术路由协议的研究由于Ad hoc网络拓扑动态变化、资源受限等特点成为具有挑战性的课题。通过上面仿真分析可以看出，按需路由由于是表驱动的路由，也提出了多种按需路由方案。通过分析现有路由综合其优点加以实现，还需要深入的研究。
参考文献
[1] 任智.移动Ad Hoc网络路由算法及协议研究[D].成都：电子科技大学博士学位论文，2005.
[2] ROYER E M， TOH C K. A review of current routing protocols for Ad-hoc mobile wireless networks[J]. IEEE Personal Communications， April， 1999:46-55.
[3] HARLES C， PERKINS E， BHAGWAT Pravin. Highly dynamic destination-sequenced distance-vector routing(DSDV) for mobile computers[A]. ACM SIGCOMM’94[C]， London， Sep， 1994:234-244.
[4] PEI G， GERLA M， CHEN T W. Fisheye state routing: A routing scheme for Ad hoc wireless networks[A]. Proc ICC2000[C]， New Orleans， LA， June， 2000.
[5] AWERBUCH B. Approximate distributed Bellman-Ford algorithms[J]. IEEE Transactions on Communieations， Au， 1994，42:2515-2517.
[6] HAGWAT P B， PERKINS C E. Highly dynamic destination-sequenced distance-vector routing(DTDV) for mobile computers[A]. In Proeeedings of the SIGCOMM’94 Conference on Communieations Architectures[C]， Protocols and Applications， 1994:234-244.
[7] PEI G. A wireless hierarchieal routing Protocol with Group Mobility[A]. IEEE ProeWCNC’99[C]， New Orleans， LA， Sept 1999.
[8] HONG Xiao Yan， XU Kai Xin， GERLA M. Scalable routing protocols for mobile adhoc networks[J]. IEEE Network， July-Aug 2002，16(4):11-21.
[9] JOHNSON D B， MALTZ D A. Dynamic source routing in Ad Hoc wireless networks[J]. Mobile Computing， T Imielinski， H Korth， Eds， Ch 5， Kluwer， 1996:153-81.
[10] JOHNSON D B， MALTZ D A， HU Y C. The dynamic source routing protocol for mobile Ad hoc networks(DSR)[Z]. Draft-ietf-manet-dsr-9.txt， Internet Draft， IETF MANET Working Group， July， 2004.
[11] 欧阳志鹏，沈富可.Ad Hoc网络基于路由协议的拥塞控制[J].计算机工程与设计，2006(8):3102-310.
[12] The ns Manual.http://www.isi.edu/nsnam/ns/ns-documentation.html，2010.