NS2.35中AODV协议及其实现简介

AODV路由协议及其在NS2中实现过程简介尚硕2013.05.091.上一阶段工作总结...........................................................................22.AODV路由协议概述........................................................................32.1概述.................................................................................................................................................................32.2AODV协议运行方式.....................................................................................................................................32.3AODV协议的特点.........................................................................................................................................53.NS2中AODV协议实现过程............................................................53.1处理数据分组的流程..................................................................................................................................63.2处理协议分组流程.......................................................................................................................................81.上一阶段工作总结第一阶段：4月10日~4月23日：看AODV源码，研究路由度量ETX添加思路AODV源码程序49页，OLSR等协议更多，在看底层协议的时候用了较多的时间。在研究添加思路的时候，比如探测帧问题，我们就尝试过多种解决方案：一种是在原有的hello包基础上添加探测功能，但是这样可能会改变原来程序的功能，使源程序出现问题；第二种方法是在aodv协议中增加新的探测数据包，但是需要添加相应的定时器，使程序较为复杂，而且添加成功后的协议覆盖了原有的AODV协议；第三种方法，即最后采用的方法是添加一种新的协议AODVETX。第二阶段：4月24日~4月28日：编写并修改代码在参考相应的ETX资料的基础上，编写并修改自己的程序。第三阶段：4月29日~5月04日：添加程序并调试，实现了ETX功能在添加程序的时候，小组成员采用两种不同方案：一种正常的修改makefile文件的思路，较为常用；另一种为采用autotool工具，自动生成makefile文件。该种方法采用makefile.am文件，比上种方案高一个层次。该种方法只需建立一个文件夹，并在该文件夹中自动生成协议及实现仿真，不需要修改其他系统文件，对系统影响较小。该方法使用与大型程序，实现较为复杂。第四阶段：5月05日~5月09日：整理汇报稿，研究添加路由度量ETT现阶段面临的主要问题为：实现ETT度量中如何获得系统带宽。2.AODV路由协议概述2.1概述AODV(Adhocon-demanddistancevectorrouting，按需平面距离向量路由协议)是一种源驱动路由协议，AODV支持组播功能，支持QoS，可以使用IP地址，实现通Intenet连接，但是不支持单向信道。AODV实质上就是DSR和DSDV的综合，借用了DSR中路由发现和路由维护的基础程序，以及DSDV的逐跳路由、目的节点序列号和路由维护阶段的周期更新机制，以DSDV为基础，结合DSR中的按需路由思想并加以改进。与DSDR保存完整的路由表不同的是，AODV通过建立基于按需路由来减少路由广播的次数；与DSR相比，AODV的源路由并不需要包括在每一个数据分组中，这样会降低路由协议的开销。AODV是一个纯粹的按需路由系统，那些不在路径内的节点不保存路由信息，也不参与路由表的交换。AODV操作无环路，避免了通常Bellman-ford算法（DSDV采用的基本算法）的无穷计数问题的同时，还提供了很快的收敛速度。AODV的路由表中每个项都使用了目的序列号。目的序列号是目的节点创建，并在发给发起节点的路由信息中使用的。使用目的序列号可以避免环路的发生。2.2AODV协议运行方式AODV路由协议的运行方式主要分为路由发现过程、反向路由建立过程、正向路由建立过程、路由表管理、路由维护过程。AODV使用3种消息作为控制信息:RouteRequest(RREQ)，RouteReply(RREP)和RouteError(RERR)，下面的内容会逐步涉及这三种消息。2.2.1路由发现过程当一个节点需要给网络中的其他节点传送信息时，如果没有到达目标节点的路由，则必须先以多播的形式发出RREQ(路由请求)报文。RREQ报文中记录着发起节点和目标节点的网络层地址，邻近节点收到RREQ，首先判断目标节点是否为自己。如果是，则向发起节点发送RREP(路由回应)；如果不是，则首先在路由表中查找是否有到达目标节点的路由，如果有，则向源节点单播RREP，否则继续转发RREQ进行查找。2.2.2反向路由的建立在RREQ分组中包含了两个序列号：源节点序列号和源节点所知道的最新的目的序列号。源节点序列号用于维持到源的反向路由的特性，目的序列号表明了到目的地的最新路由。当RREQ分组从一个源节点转发到不同的目的地时，沿途所经过的节点都要自动建立到源节点的反向路由。节点通过记录收到第一个RREQ分组的邻居地址来建立反向路由，当RREQ分组到达了目的节点，目的节点就会产生RREP分组，并利用建立的反向路由来转发RREP。2.2.3正向路由的建立RREQ分组最终将到达一个节点，该节点可能就是目的节点，或者这个节点有到达目的节点的路由。如果这个中间节点有到达目的的路由项，它就会比较路由项里的目的序列号和RREQ分组里的目的序列号的大小来判断自己已有的路由是否需要更新。如果RREQ分组里的目的序列号比路由项中的序列号大，则这个中间节点不能使用己有的路由来响应这个RREQ分组，只能是继续广播这个RREQ分组。中间节点只有在路由项中的目的序列号不小于RREQ中的目的序列号时，才能直接对收到的RREQ分组做出响应。如果节点有到目的地的最新路由，而且这个RREQ还没有被处理过，这个节点将会沿着建立的反向路由返回RREP分组。在RREP转发回源节点的过程中，沿着这条路径上的每一个节点都将建立到目的节点的同向路由，也就是记录下RREP是从哪一个邻居节点来的地址，然后更新有关源和目的路由的定时器信息以及记录下RREP中目的节点的最新序列号。对于那些建立了反向路由，但RREP分组并没有经过的节点，它们中建立的反向路由将会在一定时间后自动变为无效。收到RREP分组的节点将会对到某一个源节点的第一个RREP分组进行转发，对于其后收到的到同一个源的RREP分组，只有当后到的RREP分组中包含了更高的目的序列号或虽然有相同的目的序列号但所经过的跳数较少时，节点才一会重新更新路由信息，以及把这个RREP分组转发出去。这种方法有效地抑制了向源节点转发的RREP分组数，而且确保了最新及最快的路由信息。源节点将在收到第一个RREP分组后，就开始向目的节点发送数据分组。如果以后源节点了解到的更新的路由，它就会更新自己的路由信息。2.2.4路由表的管理移动节点为每一个相关的目的节点维护了一个路由表。每一个路由表包含以下一些信息:目的地址、下一跳地址、跳数、目的序列号及路由项的生存时间。路由表在每一次被用来传送一个分组时，它的生存时间都要重新开始计算，也就是用当前时间加上Active-Route-Timeout。如果一个移动节点被提供了到达某一个目的节点的新路由，那么它就会把这个新路由的目的序列号与自己路由表中己有的目的序列号做比较，并将目的序列号大的作为到达目的节点的路由表。如果目的序列号相同，则采用到目的节点所经过的节点数(跳数)最少的那个路由。2.2.5路由维护过程在网络资源充分的情况下，AODV协议可以通过定期广播hello报文来维护路由，一旦发现某一个链路断开，节点就发送ERROR报文通知那些因链路断开而不可达的节点删除相应的记录或者对已存在的路由进行修复。2.3AODV协议的特点AODV是一种距离矢量路由协议，采用的算法克服了以前提出的一些算法的缺点，具有如下优点:(1)基于传统的距离向量路由机制，思路简单、易懂。(2)支持中间节点应答，能使源节点快速获得路由，有效减少了广播数，但存在过时路由问题。(3)节点只存储需要的路由，减少了内存的需求和不必要的复制。(4)快速响应活跃路径上断链。(5)通过使用目的序列号来避免路由环路，解决了传统的基于距离向量路由协议存在的无限计数问题。(6)具有网络的可扩充性。(7)需要周期性地广播分组，需要消耗一定的电池能源和网络带宽。与DSDV以及其他持续存储更新路由信息的算法相比，AODV需要相对较长的路由建立时延，不过AODV采取了以下的一些措施来加以改善:(a)到某个目的节点的路由可以由知道路由的中间节点进行响应。(b)链路失效能够被立即报告，这样路由可重新建立。(c)不活跃的路由在一定时间后会被删除。3.Ns2中AODV协议实现过程Ns2中AODV协议的实现与以下文件有关，具体内容见附件AODV.docx：AODV.H、AODV.CC、AODV_LOGS.CC、AODV_PACKET.H、AODV_RQUEUE.H、AODV_RQUEUE.CC、AODV_RTABLE.H、AODV_RTABLE.CC其中aodv.cc是实现aodv功能的主要文件，阅读aodv程序需要从AODV::recv(Packet*p,Handler*)程序入手，分析分组类型，对不同类型的数据包进行分析。3.1处理数据分组的流程AODV::recv(Packet*p,Handler*)本节点产生的数据包，添加IP头收到的不是广播分组，解析分组本节点是中间节点，通过TTL（生存时间）判断是否丢包收到本节点发送的包，说明有路由环路，丢包直接转发判断是否为协议分组，是则调用AODV(P)函数处理协议分组处理数据分组VoidAODV::recv(Packet*p,Handler*)//判断是否是aodv包，是则调用函数recvAODV(p)if(ch-ptype()==PT_AODV){recvAODV(p);//本节点产生的数据包，添加IP头if((ih-saddr()==index)&&(ch-num_forwards()==0))AddtheIPHeader//收到本节点发送的包，说明有路由环路，丢包elseif(ih-saddr()==index)drop(p,DROP_RTR_ROUTE_LOOP);//本节点是中间节点else{//TTL是分组最多能转发的次数if(--ih-ttl_==0)drop(p,DROP_RTR_TTL);//收到的不是广播分组，解析分组if((u_int32_t)ih-daddr()!=IP_BROADCAST)rt_resolve(p);//转发elseforward((aodv_rt