AODV

按需距离矢量路由协议AODV简介内容1、AODV概述2、RREQ路由请求帧3、RREP路由应答帧4、路由发现和维护5、路由错误控制6、拥塞控制1、AODV概述AODV是为快速移动自组网（MANET）设计的数据包路由协议较适用于有大量节点的无线自主网络按需路由协议，只有当到达某目的节点的路由不存在时才会激活该协议发起路由请求使用节点序列号机制避免环路产生传输层使用的是UDP协议网络各节点使用IP地址统一编址每一个节点维护一个包含到达目的节点路由信息的路由表路由表字段目的节点IP地址目的节点序列号（SequenceNumber）目的节点序列号有效标志位下一跳节点IP地址本节点到达目的节点的跳数前驱节点列表（precursorlist）生存时间（路由失效或删除时间）网络层接口其他的状态和路由标志位路由表每项只记录下一跳路由信息，而不是整条路由信息，简化了路由表的建立和维护源节点和目的节点都维护各自的序列号如何管理序列号是提高路由建立和维护的关键序列号是用来标识路由信息新旧程度（freshness）的源节点发起路由请求RREQ，或者目的节点返回路由应答RREP，都要更新各自的序列号其他节点（中间节点）依据序列号的大小判断路由的新旧AODV路由帧格式主要包括:RREQ–路由请求帧RREP–路由应答帧RERR–路由错误帧HELLO–活跃路由链路监测帧应用层数据发送请求结束使用现有有效路由转发数据包缓存数据，发起路由请求路由是否可用？是否AODV路由请求的发起流程图收到路由控制信息结束检查信息类型更新到目的节点的路由、目的节点前驱列表等信息将受到影响的路径删除（置为无效）更新到源节点的反向路由RREQ消息RERR消息RREP消息本节点是目的节点吗？是否有到达目的节点的路由？发送RREP路由应答帧如果本节点尚没有缓存该RREQ，缓存之并转发本节点是发起节点（源节点）吗？使用新建立的路由发送缓存的数据包单播RREP至路由的下一跳是否一条以上路径被删除？转发RERR到前驱节点是否是否是否否是AODV对路由控制信息的控制流程图2、RREQ路由请求帧帧格式为：RREQ路请求由帧在两个节点之间的路由有效、通信正常的情况下，AODV路由协议不起任何作用只有当源节点S需要向目的节点D发送数据包，但又没有D节点的路由入口时才会发起路由请求，即发送路由广播帧RREQ当RREQ在网络中传播时，中间节点会更新各自到源节点的路由，我们称此路由为反向路由RREQ请求帧中包含源节点以前记录的到目的节点的序列号，但此序列号可能不是最新的（最大的）中间节点如果有到目的节点的路由时，只有该节点记录的目的节点序列号比RREQ中的目的节点序列号更新（更大）时，才认为这条路由是有效的RREQ请求帧的传播B?B?B?B?B?B?B?BA应答帧格式：3、RREP路由应答帧RREP应答帧当RREQ最终到达目的节点时，目的节点通过向该反向路由（即该RREQ传播路线）发送RREP应答帧，从而在该条路径的各个节点建立通向目的节点的前向路由只有在以下情况下节点才会产生RREP:该节点本身就是目的节点该节点为中间节点，但是它有通向目的节点的活跃路径当RREP传播到源节点时，中间节点根据该RREP更新它们各自指向目的节点的路由信息节点只对第一次收到的RREQ发送RREP应答帧，之后到达的RREQ将被忽略RREP路由应答帧的传播BAAAAAAA4、路由发现和维护路由发现过程广播RREQ路由请求帧中间节点更新各自到源节点的路由表如果收到RREQ的节点不是目的节点，并且没有到达目的节点的更新的有效路由，则转发该RREQ中间节点维护指向路由发起节点（源节点）的反向路由目的节点或存在到目的节点有效路由的中间节点产生RREP路由应答帧RREP通过之前建立的反向节点单播至源节点源节点收到RREP应答帧，至此源节点可以向目的节点发送数据包路由发现算法源节点应用层有数据发送请求，并且指向目的节点的路由有效，直接通过该路由发送数据包如果没有到达目的节点的有效路径，则产生RREQ广播帧，RREQ的序列号、ID字段加1，将源节点的IP、序列号，目的节点的IP、序列号等信息添加到该RREQ中，广播至网络中间节点如果中间节点路由表中记录的到目的节点的路由有效，并且记录的目的节点的序列号比RREQ中的目的节点序列号更新（大于或者等于），则该中间节点可以产生路由应答帧。如果该中间节点不产生应答帧，更改RREQ中的目的节点序列号至当前最大，跳数字段加1，然后转发目的节点目的节点的序列号加1产生RREP应答帧（包括源节点的IP、目的节点的IP和更新后的序列号），单播发送至源节点路由发现图示ABDFCGERREQRREQRREQRREQRREQRREQRREQRREQRREQRREPRREPRREPSourceDestination路由维护Hello消息Hello消息帧其实就是TTL=1时的RREP帧。TTL（Time-To-Live)为IP数据包字段，表示该帧的传播跳数。Hello消息帧用于监测活跃路径上相邻节点的链接状况。例如：当活跃路径上某节点ALLOWED_HELLO_LOSS*HELLO_INTERVAL毫秒时间内没有收到该路径上的邻居节点发送来的Hello消息帧或其他任何帧时，该节点就认为与它与邻居节点的链路已断只有当某节点位于某活跃路径之上时，它才能发送Hello消息帧活跃路径节点以HELLO_INTERVAL为周期发送Hello消息在DELETE_PERIOD的时间内没有收到来自邻居节点的Hello消息，则认为该链路已失效发起一次指向该邻居节点的局部修复路由修复超时以后，路由错误信息RERR向源节点和目的节点发送RERR传播过程中，各中间节点删除该失效路径上相应的路由信息路由信息新旧判断AODV依赖网络中每个节点维护自身的序列号源节点在广播路由请求帧RREQ之前要先更新自己的序列号，即将序列号加1目的节点在产生RREP应答帧之前也要将自身的序列号加1每个节点在对各自的序列号加1的时候是将其视为无符号数进行的通过比较来自目的节点路由控制帧中的序列号SN1和本节点维护的目的节点的序列号SN2就可以确定本链路的新旧程度，进而做相应处理。如果SN2-SN10（有符号数相减），说明路由表中维护的信息已过时，应将路由信息更新至路由控制帧中最新的路由信息5、路由错误控制路由错误帧RERR格式：RERR路由错误帧以下情况发生时，则广播RERR路由错误帧：i.一个节点检测到与一个邻居节点的链路断裂（即该邻居节点不可达）ii.节点收到一个数据包，而该节点路由表中没有指向数据包制定的目的地址的有效路由，并且该路由并非处于修复状态iii.节点收到来自邻居节点的RERR路由错误信息帧，该帧可能指示多个目的节点不可达产生或收到RERR后路由更新目的节点序列号-i和ii两种情况下更新路由表中的目的节点序列号（+1），并将更新后的序列号包含在RERR中-第iii种情况下只需复制接收的RERR目的节点序列号到路由表中或者需要转发的RERR中将指向该RERR中目的节点的路由入口设为无效生存时间字段更新为（当前时间+DELETE_PERIOD）生存时间超时以后才可以彻底删除路由入口RERR转发处理建立受到影响的目的节点列表：建立不可达目的节点列表，包括不可达的邻居节点和以该节点为下一跳的目的节点（如果有的话）列出需要接受该RERR信息的下一跳节点列表更新路由信息向列表中的每个节点发送RERR路由错误信息，通知路由上游节点RERR信息的发送方式单播-将RERR信息单播发送给一个接收者重复单播-将RERR信息分别的单播发送给多个接收者广播-将RERR信息同时发送给多个接收者-使用IP地址255.255.255.255进行广播，TTL=1断裂链路处理所有直接使用断裂链路的邻居节点都各自产生一个RERR然后这些节点将RERR向各自的前驱节点发送依此方式继续转发RERR，直至被断裂链路影响的所有节点（包括中间节点和源节点）都收到RERR包重新建立路由源节点在收到RERR路由错误信息后，如果还需要与目的节点通信，它可以再次发起路由请求。再次建立起的路由可能跟原来路由大不相同中间节点在收到发送到目的节点的数据包时，如果发现目的节点的路由入口已失效（如路由计时超时），则该节点可以选择缓存该数据包，然后发起到该目的节点的路由请求RREQ。等重新建立到达目的节点的路由后，在转发此数据包到目的节点。6、拥塞控制可用于AODV的一种拥塞控制方法是：源节点在发送RREQ后，在规定的时间内没有收到来自目的节点的RREP时，它可以选择再次发送RREQ路由请求帧。在尝试了RREQ_RETRIES次之后，如果依然收不到RREP，则在路由表中标记该目的节点不可达，并通知应用层每次重新发送RREQ请求帧时，等待RREP应答帧的时间要在原来时间的基础上乘以2，避免拥塞