王海涛，郑少仁
（解放军理工大学通信工程学院，江苏南京210007）
摘 要：由于Ad hoc网络自身的特殊性，其路由协议的设计与传统固定网络有很大不同。首先说明了Adhoc网络中提供高效路由算法的难点，然后讨论了Ad hoc网络中路由协议设计的几种策略，接着介绍了几种典型的Ad hoc路由协议，最后通过实验分析比较了4种路由协议的性能，并给出了结论。
关键词：网络模拟器；目的序列距离矢量路由；动态源路由；临时按序路由；Ad hoc按需距离矢量路由
0 引 言
无线网络通常可以分为有中心网络和无中心网络，前者需要固定基础设施的支持，移动主机之间的通信通常借助基站来完成，例如蜂窝移动通信系统；后者主要是指移动Ad hoc网络［1－4］，它不需要固定的基础设施，能够快速地自动组网。与有中心网络相比，Ad hoc网络灵活、健壮、投资少，特别适合于作战指挥、抢险救灾以及应付突发事件和执行临时任务的场合。在Ad hoc网络中，每个移动节点兼备路由器和主机两种功能。作为主机，移动节点需要运行面向用户的应用程序；作为路由器，它需要运行相应的路由协议，根据路由策略和路由表参与数据分组转发工作和路由维护工作。考虑到Ad hoc网络中节点是移动的，网络的拓扑结构不断变化，传统的用于因特网的路由协议（如RIP、OSPF等）无法适应Adhoc网络的实际需要［2］，同时由于移动节点的计算能力和存储容量较低并且能源受限，要求路由协议尽量简单，这又增加了Ad hoc网络中路由协议设计的难度。
1 Ad hoc中路由协议的分类
Ad hoc网络的路由协议大致可以分为先验式（Proactive）路由协议、反应式（Reactive）路由协议以及混合式路由协议［2，5］。先验式路由协议又称为表驱动路由协议，在这种路由协议中，每个节点维护一张包含到达其它节点的路由信息的路由表。当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息，收到更新消息的节点将更新自己的路由表，以维护一致的、及时的、准确的路由信息，所以路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文，可以立即获得到达目的节点的路由。因此这种路由协议的时延较小，但是路由协议的开销较大；反应式路由协议，又称为按需路由协议，是一种当需要发送数据时才查找路由的路由算法。在这种路由协议中，节点不需要维护及时准确的路由信息，当向目的节点发送报文时，源节点才在网络中发起路由查找过程，找到相应的路由。与先验式路由协议相比，反应式路由协议的开销较小，但是数据报传送的时延较大。在Ad hoc网络中单纯采用先验式或反应式路由协议都不能完全解决路由问题。在高速动态变化的Ad hoc网络中，使用单纯的先验式路由协议会产生大量的控制报文，并且很多控制报文经常是无用的；如果单独采用反应式路由协议，需要为每个报文查找路由，这也是不合理的（特别是当连续向某个目的节点发送多个报文时）。由此可见，应用结合先验式和反应式路由协议优点的混合式路由协议是一种较好的折衷方案。在局部范围内使用先验式路由协议，维护准确的路由信息，并可缩小路由控制消息传播的范围，当目标节点较远时，通过查找发现路由，这样既可以减少路由协议的开销，时延特性也得到了改善。
2 4种典型的Ad hoc网络路由算法
为了比较和验证Ad hoc网络中的路由协议的性能，采用了NS2网络仿真器［4］进行试验。NS2是由加利福尼亚大学伯克利分校和VINT项目组联合开发的，是一个包含TCL（Tool Command Lan－guage：工具命令语言）语言的受事件驱动的网络仿真器。这个仿真器通过NS的解释程序被调用，解释程序之间的所有相互作用通过一个专门的TCL程序完成。应用NS命令，可定义一个网络拓扑，配置流量源和接收器，收集统计的数据等。NS2最初主要被用来模拟传统有线网络上的TCP协议和其他协议，它并不支持多跳无线移动网络环境，随着相关领域研究的进展，美国的CMU大学对NS2作了相应的扩展，目前，NS2已经可以支持一定范围内和一定条件下的无线多跳移动网络。
2．1 目的序列距离矢量路由协议（DSDV）
DSDV对Bellman－Ford路由算法进行了改进。
在DSDV中，每个移动节点都需要维护一个路由表。路由表表项包括目的节点、跳数和目的地序号，其中目的地序号由目的节点分配，主要用于判别路由是否过时，并可防止路由环路的产生。每个节点周期性必须与邻节点交换路由信息，当然也可以根据路由表的改变来触发路由更新。路由表更新有两种方式：一种是全部更新（Fulldump），即拓扑更新消息中将包括整个路由表，主要应用于网络变化较快的情况；另一种方式是部分更新（Incrementalupdate），更新消息中仅包含变化的路由部分，通常适用于网络变化较慢的情况。在DSDV中只使用序列号最高的路由，如果两个路由具有相同的序列号，那么将选择最优的路由（如跳数最短）。NS实现DSDV路由协议的具体策略如下：一个没有找到路由的分组到达节点后首先被缓存，同时节点发送路由查询消息，直到接收到来自接收端的路由响应消息。当缓存溢出时，新来的分组将被丢弃。分组到达目的节点后将直接由地址解复用器送到相应的端口，而后由端口将分组送到目的代理。
2．2 动态源路由协议（DSR）
DSR是一种基于源路由的按需路由协议，它使用源路由算法而不是逐跳路由的方法。DSR主要包括两个过程：路由发现和路由维护。当节点S向节点D发送数据时，它首先检查缓存是否存在未过期的到目的节点的路由，如果存在，则直接使用可用的路由，否则启动路由发现过程。具体过程如下：源节点S将使用洪泛法发送路由请求消息（RREQ），RREQ包含源和目的节点地址以及唯一的标志号，中间节点转发RREQ，并附上自己的节点标识。当RREQ消息到达目的节点D或任何一个到目的节点路由的中间节点时（此时，RREQ中已记录了从S到D或该中间节点的所经过的节点标识），D或该中间节点将向S发送路由应答消息（RREP），该消息中将包含S到 D的路由信息，并反转S到D的路由供RREP消息使用。此外，中间节点也可以使用路由缓存技术（Routing Cache）来对协议作进一步优化。DSR的优点：①节点仅需要维护与之通信的节点的路由，减少了协议开销；②使用路由缓存技术减少了路由发现的耗费；③一次路由发现过程可能会产生多条到目的点的路由。DSR的缺点：①每个数据报文的头部都需要携带路由信息，数据包的额外开销较大；②路由请求消息采用洪泛方式，相邻节点路由请求消息可能发生传播冲突并可能会产生重复广播；③由于缓存，过期路由会影响路由选择的准确性。NS实现的DSR协议中，采用DSR的节点与其它移动节点有些不同，在DSR节点中，所有分组被送到路由代理，路由信息可通过数据分组进行捎带确认。
2．3 临时按序路由算法（TORA）
TORA是一个基于链路反转方法的自适应的分布式路由算法，主要用于高速动态的多跳无线网络。作为一个由源端发起的按需路由协议，它可以找到从源到一个目的节点的多条路由。TORA的主要特点是：当拓扑发生改变时，控制消息只在拓扑发生改变的局部范围传播。因此，节点只需维护相邻节点的路由信息。协议由3部分构成：路由产生、路由维护和路由删除。初始化时，目的节点的高度（即传播序列号）被置为0。然后由源端广播一个含有目的节点ID的QRY分组，一个高度不为0的节点响应一个UPD分组。收到UPD分组的节点的高度将比产生该UPD分组的节点的高度大1，并且具有较大高度值的节点被规定为上游节点。通过这种方式能够创建一个从源到目的节点的一个有向无环路图（DAG）。当节点移动时，路由需要重建。在路由删除阶段，TORA通过广播一个CLR分组来删除无效的路由。TORA存在的一个问题是当多个节点同时进行选路和删除路由时会产生路由振荡现象。NS中，每个节点为所有可能的目的节点运行一个分离的TORA进程。TORA运行在IMEP（IMEP：InternetMANETEncapsulation Protocol）之上，IMEP主要用来提供路由消息的可靠传送并可以向邻居节点通知链路的改变。
2．4 Ad hoc按需距离矢量路由协议（AODV）
AODV［6］是DSDV算法的改进，但它与DSDV的区别在于它是反应式路由协议。为了找到通往目的节点的路由，源端将广播一个路由请求分组，邻居节点依次向周围节点广播此分组直到该分组被送到一个知道目的节点路由信息中间节点或目的节点本身。一个节点将丢弃重复收到的请求分组，路由请求分组中的序列号用来防止路由环路，并能判断中间节点是否响应了相应的路由请求。当节点转发路由请求分组时，它会将其上游节点的标志ID录入路由表，从而能够构建一条从目的节点到源节点的反向路由。当源端移动时，它会重新发起路由发现算法；如果中间节点移动，那么与其相邻的节点会发现链路失效并向其上游节点发送链路失效消息并一直传到源节点，而后源节点根据情况重新发起路由发现过程。NS中，AODV的实现组合DSR和DSDV协议。它既具有DSR协议的路由发现和路由维护功能，同时又使用了DSDV采用的逐跳路由、序列号和Beacon消息。
3 模拟试验和性能比较
模拟工具采用第2节介绍的NS2网络仿真器，无线仿真开始时，需要定义每个网络功能组件的类型，包括天线的类型、电磁波的传输模式和移动节点使用的Ad hoc路由选择协议等。试验中，网络初始拓扑结构见图1，该模型由3个移动节点（节点0，1和2）构成，并在670 m×670 m的范围内按以下预定的移动模式移动。3个节点初始坐标为：节点0（83，239）、节点1（257，345）、节点2（591，199）。模拟开始运行后，在33 s时节点0以19 m／s速度向目标坐标（89，283）移动，在50 s时节点2以3．37 m／s的速度向目标坐标（369，173）移动，在51 s时节点1开始以14．90 m／s速度向目标坐标（221，80）移动。在节点0和节点2之间建立固定比特率（CBR）业务流，CBR的分组大小为512字节，发送间隔为4 s。并且在127s时，节点0开始向节点2发送CBR数据包，模拟的总时间设为400 s。图2给出了在时间235 s时网络的拓扑结构，此时3个节点已到达各自的目标，并且节 点0正通过节点1向节点2发送CBR数据包。
在试验中，分别使用第3节介绍的4种Ad hoc路由协议在相同的网络环境下进行试验，而后对模拟产生的数据进行分析来比较4种路由协议下CBR应用的性能。试验的具体分析如下。
（1）采用DSDV协议的情况。模拟开始时节点0和节点1由于距离较近可以交换message路由消息，而节点2和其它2个节点距离较远而无法交互路由消息。在时间94 s左右，节点1和节点2开始交换路由消息，并且节点0也可以通过节点1获得节点2的路由信息。在127 s时，节点0开始向节点2发送CBR分组，最初CBR分组由于缓存空间不足或地址解析出错等原因而被节点0丢弃，直到188 s时节点1才收到第一个CBR分组并将其转发给节点2。在此次模拟中，三个节点总共发送了71条路由控制消息，节点0共发送了71个CBR包，并丢弃了15个CBR包。
（2）使用DSR协议。由于DSR是按需路由协议，模拟开始时节点之间不交互路由消息，直到节点0向节点2发送CBR包需要选路时才发送DSR消息。在整个模拟中，3个节点共发送了3条DSR路由控制消息，节点0共发送了68个CBR包，并丢弃了0个CBR包。
（3）采用TORA协议。由于TORA是按需路由协议，并且TORA运行在IMEP之上，因此，模拟开始时节点只发送IMEP消息，直到127 s时节点0才开始发送TORA选路消息。在整个模拟中，3个节点总共发送了1199条IMEP路由消息和1条TORA消息，节点0发送了71个CBR包，其中丢失了0个CBR包。
（4）使用AODV协议。AODV也是按需路由协议，模拟开始时节点不发送路由消息，直到127 s时，节点0开始发送CBR数据包时才发送AODV选路消息。在整个模拟中，3个节点总共发送了4条AODV消息，节点0发送了69个CBR包，其中丢失了0个CBR包。
（5）为了比较在不同网络负载下路由协议运行的情况，以DSDV路由算法为例，将CBR的分组大小改为1024字节，并将CBR流的发送间隔改为0．5s，此时的网络负载将明显增加。将这种网络负载环境下的DSDV协议称为DSDVB，并对其进行相同的试验。从整个模拟过程中可以发现：3个节点总共发送了97条message路由控制消息，而节点0总共发送了426个CBR包，但丢失了97个CBR包。
下面以分组投递率和路由开销为性能指标对以上路由协议进行比较。分组投递率是指接收端收到的分组总数和发送端产生的分组总数之比，它可以反映网络所能支持的最大吞吐量，从而在一定程度上刻画了协议的完整性和正确性。路由开销是指模拟期间传输的路由控制分组的总数，并且对一个需要经过多跳路由传输的分组而言，每一跳传输相当于一次分组传输［7］。路由开销可以用来比较不同路由协议的可扩展性、适应网络拥塞的能力和协议的效率。由测试数据得到的各协议的分组投递率和路由开销见表1。
分组投递率：在相同的移动特性下，反应式路由协议（DSR、TORA以及AODV）的分组投递率高，趋近100％（因为这里网络开销很小，使得分组投递率达到100％）。而DSDV的分组投递率最低，大约为79％。这是因为DSDV为目的节点只维护一个路由，当此路由失效时将没有可以替换的路由。并且发现DSDVB协议的分组投递率低于DSDV，这是因为分组投递率将随网络负载的增加而减少，实际上网络负载对其它路由协议也有类似的影响。
路由协议开销：4种路由协议的开销差别明显，DSR开销最小，TORA开销最大。由于TORA、DSR和AODV都是按需路由协议，它们的开销将随着节点移动性的减小而降低，随着网络负载的增加而增加。DSDV是一个先验式的路由协议，它的开销基本上与节点移动性无关。由于DSR和AODV的特性相似，故它们的性能相似。由于DSR使用缓存技术和混杂接收方式侦听路由请求分组，从而大大降低了路由开销。TORA的开销由恒定的与移动无关的路由开销和可变的与移动相关的路由开销两部分构成，前者是由IMEP邻居发现机制造成的，该机制要求每个节点在每个信号周期至少传送1个HELLO分组，后者是指TORA用来产生和维护路由的路由分组以及IMEP用来确保可靠按序传送的重传和确认分组。因此TORA的路由开销较大，并且当网络负载较大时，路由开销受节点移动性的影响减小。
4 结 论
本文介绍和分析了当前Ad hoc网络采用的几种路由协议，并且通过NS网络仿真器对其中的4种路由算法进行了仿真分析和性能比较。结果表明不同的路由协议都有各自的应用场合和优缺点，设计一种万能的路由协议是不现实的。一种较好的解决思路是采用结合先验式和反应式路由协议的混合式路由，它能在尽量减少分组时延的前提下降低路由协议的开销。例如文献［10］中提出了一种基于分簇结构的分级路由算法，簇内使用先验式路由算法，簇间按需寻找路由，并且根据网络的动态变化可以自适应地调节簇的大小。这种路由算法吸取了2种路由算法的优点，具有较高的效率和较强的适应性，并且作者在文献［8］中给出了相应的模拟结果。由于Ad hoc自身复杂多变的动态特性，路由协议的设计目前仍是一个人们关注的热点问题。一种新的设计思路是采用自适应路由协议，它能够根据不同的网络环境来相应地改变路由算法，但这种方法的计算和维护开销较大，实现比较复杂，目前正处于研究阶段。此外，Ad hoc网络中的QoS路由也是一个研究方向。总之，Ad hoc网络的路由协议是一个比较复杂的问题，真正实现令人满意的路由算法和机制还需要通过长期的探索和研究。
参考文献
［1］ MAGNUSFrodigh，PERJohansson．Wire－less Ad hoc networking－the art of network－ing without a network［J］．EriCSSon Review，2000（4）：248－262．
［2］ PADMINIMisra．Routing protocol for Adhoc mobile wireless network［EB／OL］．http：／／www．cis．ohio－state．edu／～jain／cis788－99／adhoc＿routing／index．html．
［3］ KEVIN Fall，KANNANVaradhan．The nsmanual．The VINT Project［EB／OL］．
http：／／www－mash．cs．berkeley．edu／ns，February，2001．
［4］ Mobile Ad hoc Networks（MANET）［EB／OL］．http：／／www．ietf．org／html．charters／manet－charter．html．2000（5）．
［5］ JOSHB，DAVIDA M，DAVIDBJ．A per－formance comparison of multi－hop wirelessAd hoc network routing protocols［C］．Mo－biCom98，Dallas，USA，October 1998．
［6］ CHARLESEPerkins，ELIZABETHM Roy－er，SAMIR RDas．Ad hoc on－demand dis－tance vector routing［EB／OL］．http：／／www．ietf．org／internet－drafts／draft－ietf－manet－aodv－04．txt，October 1999．
［7］ 英春，史美林．自组网如何路由［J］．计算机世 界，2000，（44期C版）：5－7．
［8］ BRUCEMcDonald，TAIEBFZnati．Scal－able routing strategies for Ad hoc wirelessnetworks［J］．IEEEJournalon Selected Ar－eas in Communications，1999，17（8）：1466－1487．
摘自 重庆邮电学院学报
|