浅谈NS-2对于Ad hoc网络路由协议的作用

　　Ad-Hoc（点对点）模式：ad-hoc模式就和以前的直连双绞线概念一样，是P2P的连接，所以也就无法与其它网络沟通了。一般无线终端设备像PMP、PSP、DMA等用的就是ad-hoc模式。 在家庭无线局域网的组建，我想大家都知道简单的莫过于两台安装有无线网卡的计算机实施无线互联，其中一台计算机连接Internet就可以共享带宽。如下图所示，一个基于Ad-Hoc结构的无线局域网便完成了组建。

　　Ad hoc网络的前身是分组无线网（Packet Radio Network）。对分组无线网的研究源于军事通信的需要，并已经持续了近20年。早在1972年，美国DARPA（Defense Advanced Research Project Agency）就启动了分组无线网（PRNET,Packet Radio NETwork）项目，研究分组无线网在战场环境下数据通信中的应用。项目完成之后，DAPRA又在1993年启动了高残存性自适应网络（SURAN,SURvivable Adaptive Network）项目。研究如何将prnet的成果加以扩展，以支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协议。1994年，DARPA又启动了移动信息系统（GloMo,Globle Mobile Information Systems）项目。在分组无线网已有成果的基础上对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直持续至今。1991年成立的IEEE802.11标准委员会采用了“Ad hoc网络”一词来描述这种特殊的对等式无线移动网络。

　　路由技术担负着为数据分组寻找路由和将其传送到目的地的任务，是移动Ad hoc网络中的一项关键技术，而路由算法和协议则是路由技术的内容，直接关系到时延、吞吐率和成功率等网络性能的优劣。对Ad hoc路由协议的研究具有参考意义。

　　1 Ad hoc网络路由协议

　　路由协议主要运行于路由器上，路由协议是用来确定到达路径的，它包括RIP,IGRP,EIGRP,OSPF。起到一个地图导航，负责找路的作用。它工作在网络层。路由选择协议主要是运行在路由器上的协议，主要用来进行路径选择。

　　路由协议作为TCP/IP协议族中重要成员之一，其选路过程实现的好坏会影响整个Internet网络的效率。按应用范围的不同，路由协议可分为两类：在一个AS（Autonomous System，自治系统，指一个互连网络，就是把整个Internet划分为许多较小的网络单位，这些小的网络有权自主地决定在本系统中应采用何种路由选择协议）内的路由协议称为内部网关协议（interior gateway protocol），AS之间的路由协议称为外部网关协议（exterior gateway protocol）。这里网关是路由器的旧称。现在正在使用的内部网关路由协议有以下几种：RIP-1，RIP-2，IGRP，EIGRP，IS-IS和OSPF。其中前4种路由协议采用的是距离向量算法，IS-IS和OSPF采用的是链路状态算法。对于小型网络，采用基于距离向量算法的路由协议易于配置和管理，且应用较为广泛，但在面对大型网络时，不但其固有的环路问题变得更难解决，所占用的带宽也迅速增长，以至于网络无法承受。因此对于大型网络，采用链路状态算法的IS-IS和OSPF较为有效，并且得到了广泛的应用。IS-IS与OSPF在质量和性能上的差别并不大，但OSPF更适用于IP，较IS-IS更具有活力。IETF始终在致力于OSPF的改进工作，其修改节奏要比IS-IS快得多。这使得OSPF正在成为应用广泛的一种路由协议。现在，不论是传统的路由器设计，还是即将成为标准的MPLS（多协议标记交换），均将OSPF视为必不可少的路由协议。

　　1.1 Ad hoc路由协议的研究分类

　　近年来，研究人员提出了上百种路由协议的方案。可以根据不同的原则进行分类研究：

　　(1)根据接收节点的数量[1]，可分为单播(unicast)：单播通信中目的节点只有一个，实现一对一的通信，单播路由协议是研究得多的路由协议；组播(multicast，也被称为多播)：一对多的通信，目前有基于树的多播路由协议和基于网格的多播路由协议；广播(broadcast)：所有主机都接收数据。

　　(2)根据路由发现的策略可以分为先应式(Poractvie)路由，也被称为表驱动(Table-Driven)路由，以及反应式(Reactive)路由，也被称为按需(On-Demand)路由。所以其内容可能仅仅是整个网络拓扑结构信息的一部分。典型的按需路由协议有DSR、AODV、TORA[8]。

　　(3)根据网络逻辑视图的不同，可分为平面(Flat)路由与分级(cluster-based)路由。平面路由协议的网络逻辑视图是平面结构，网络结构比较简单，路由协议在平面的逻辑空间里运行，移动节点的地位是平等的，即主机和主机都是平等的。节点分为两种类型:普通节点和簇头节点，处于同一簇的簇头节点和普通节点共同维护所在簇内部的路由信息，簇头节点负责所管辖簇的拓扑信息的压缩和摘要处理，并与其他簇头节点交换处理过后的拓扑信息。

　　1.2 三种典型的路由协议

　　1.2.1 目的节点序列距离矢量协议(DSDV)

　　DSDV是表驱动的平面路由协议，基于Bellman-Ford算法，通过给每个路由设定序列号避免路由环路的产生。在DSDV路由协议中，每个节点都必须存储并维护一张路由表，该路由表记录着目的节点、跳数、下一跳节点和目的节点序列号。其中目的节点序列号由目的节点分配，主要用于判别路由是否过时，并可防止路由环路的产生。但是在拓扑变化频繁的网络中，DSDV存在一些问题：主要是节点维护路由信息的代价很高，因此不适用于规模大的网络。

　　1.2.2 动态源路由协议(DSR)[9-10]

　　DSR是一种按需平面路由协议。每个节点都有路径缓存器，而路径信息则保存在每个封包的缓存标题中。当发送者发送报文时，在数据报文头部携带到目的节点的路由信息，该路由信息由网络中的若干节点地址组成，源节点的数据报文就通过这些节点的中继转发到达目的节点。这个过程一直持续到有一个路由请求分组到达目的节点。

　　若发现自己的地址已经在记录中，就停止广播。每个请求都有一个由源节点所设置的ID号，每个节点都有一个路由缓存，存储近转发过的路由请求，以便查询接收的是否为同一个请求，这样保证每个节点只转发。当路由请求分组到达目的节点时，节点要返回一个路由应答分组，通知节点己收到该路由请求。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网络拓扑动态变化、资源受限等特点成为具有挑战性的课题。通过上面仿真分析可以看出，按需路由由于是表驱动的路由，也提出了多种按需路由方案。通过分析现有路由综合其优点加以实现，还需要深入的研究。