无线Mesh网络的AODV协议的研究

康玮辰

（北京工业大学 北京 100124）

无线 Mesh 网[1]（Wireless Mesh Network， WMN）是一种多跳、具有自组织和自愈特点的宽带无线网络结构，即一种高容量、高速率的分布式网络。它旨在探索无线移动通信与IP技术的结合，研究在小型区域范围内允许多个网络同时存在、不同网络自动区分、拓扑结构动态可变、具有多跳和动态路由能力的自组织网络结构形式。无线Mesh网络由Ad Choc网络发展而来但静态于Ad Hoc[2]，相当于Internet的无线版本。

AODV协议作为一种按需路由算法，在无线Mesh网络中有着最为广泛的应用。 但在无线Mesh网中，AODV协议路由表中的节点变为不可达即出现断路时，会重新发起整个路由请求过程。本文在借鉴AODV-BR协议思想的基础上，提出了改进的AODV-BRS协议，该协议维护了除主路由表之外的备用路由表。在发生路由中断时，可以使用备用的路由继续转发数据包，从而降低了网络的时延。

1 AODV路由协议

1.1 路由发现

AODV[3]路由协议分为路由发现和路由维护两个过程。AODV是一种按需路由协议，当源节点需要向目的节点发送数据时，如果路由表中没有目的节点的路由信息，则需要以多播的形式发出RREQ（路由请求）报文。如图1所示，节点S要向节点D发送数据，由于不知晓到节点D的路由，以多播的形式向其下游的临近节点1，2，3发出了RREQ报文，节点1，2，3在收到报文后会建立到S的反向路由，然后将RREQ报文发送给其下游的节点4，5，6。同样的节点4，5，6在接收到RREQ报文后，会建立到发给他们报文的节点1，2，3的反向路由并将RREQ继续向下传递。此时我们假设节点5发送的RREQ最先到达了目的节点D，那么节点D就回沿着之前建立的反向路由将RREP报文发送给节点S，从而建立起由节点S到节点D的路由。节点D只应答第一个或者之后的目的序列号更新的或者跳数更少的RREQ请求，依照此原则节点4，6将不会得到RREP应答。

图1路由发现Fig.1 Route discovery

1.2 路由维护

AODV路由维护过程如图2所示，节点S向目的节点D发送数据，数据发送到节点1后，节点1向节点2转发数据时发现节点2已经不可达。此时如果节点1离目的节点较近，则节点1会发起本地修复，以多播形式发送RREQ报文，建立起从节点1到节点D的路由。在路由建立过程中，节点S发出的数据会暂时保存在节点1中。而如果局部修复失败，那么节点1将会向节点S发送RRER报文，节点S收到报文后从重新以路由发起的方式重新建立到节点D的路由。

图2路由维护Fig.2 Route maintenance

2 改进的AODV算法

2.1 现有的AODV-BR算法

AODV-BR[4]算法在发起路由请求过程中，当源节点需要向目的节点建立路由时，同样的会使用洪范法发送RREQ报文。每个RREQ请求都有一个为一个ID标识，因此节点可以检测并抛弃重复的RREQ请求。一个中间的节点，在接收了一个非重复的RREQ请求后，会记录下之前一跳节点和源节点的信息保存在自己的路由表中。而如果该节点路由表中拥有到目的节点的路由，则会向源节点发送RREP报文，否则将RREQ继续向下游传递，直至到达目的节点后，由目的节点依靠反向路由将RREP报文发送至源节点。在以上过程中，AODV-BR算法与AODV协议保持一致。AODV-BR协议对AODV的改进之处，在于在RREP报文返回至源节点过程中，增加了对非直接相关节点的“意外”收获的RREP报文的处理。

如图3所示，节点S到节点D的路由请求过程中会生成与AODV一致的S→2→5→D的主路由。备用路由的建立是在D回传RREP报文的过程中，由于无线网络环境，节点4，6会“偷听”到这个RREP报文。在原始的AODV协议中，节点4，6是不会对这条报文进行处理的，但在AODV-BR协议中，节点4，6会记录下这条由本身到节点D的路由，放在自己的备用路由表中。以此类推，节点1，3也会在RREP报文回传至节点S过程中，由于收到了来自节点5的RREP报文，在各自的备用路由表中分别添加了下一跳为节点5，目的节点为节点D的备用路由。备用路由的更新原则与主路由的更新原则一致，都是在接收到更新的或者跳数更少的路由信息后，进行更新。

图3 AODV-BR协议Fig.3 AODV-BR protocol

2.2 借鉴AODV-BR改进的AODV-BRS

当AODV-BR在用现有的路由转发数据时，在未到达目的节点前，有中间节点发现了链路中断时，该中间节点会发出一个一跳的广播给该节点所有的邻居节点。在该广播中，除了包含需要转发的数据外，还在广播头中加入了标识信息用以告知邻居节点链路的中断。邻居节点在收到该广播后，会查找自己的备用路由表中是否存在目的节点的路由信息，若存在，则利用备用路由继续完成数据的转发[5]。但在该过程中，存在一个弊端：备用路径并不是在被发现链路中断的节点直接使用，而是这个节点告知后续的节点，由后续一跳范围内的节点启用自己的备用路径。这样做会导致这些邻居如果使用了节点不相交的路径进行数据传输时，会导致导致多个重复数据被传送至目的节点，造成资源的浪费[6]。

改进后的协议AODV-BRS，在某种程度上可以减轻原有协议机制对链路资源浪费造成的影响。在改进后的协议中，在主路由建立过程中，除了为非主路径上的节点建立备用路由，同时也会为主路径上的节点建立备用路由。在发生链路中断时，节点会首先检查备用路由是否存在路径：若存在则直接利用备用路由发送，否则再利用AODV-BR原协议机制发送头部携带有链路中断信息的给周围邻居节点。

在AODV-BRS协议中，需要加入新的RREPS报文，报文格式如图4。

图4 RREPS报文Fig.4 RREPSmessage

报文中，除Backup Route Flag外，其余字段都与原有RREP字段相同。新加入的字段Backup Route Flag，是为了使节点在收到该报文后，将路由信息保存在自己的备用路由中。

非主路径上节点收到RREP判定是否发送RREPS的伪代码：

if（exist route to Destination IPaddress in backup table）{

if（Hop==Hop0&&AddressTo!=Originator IP address）Ignore；

else if（Hop-Hop0==1&&AddressTo!=Originator IP address）

Send RREPS to AddressFrom；

Else if（Hop==Hop0&&AddressTo==Originator IPaddress）

Send RREPS to Originator IP address；

}

Destination IP address和Originator IP address分别代表RREP报文中的对应字段。

Hop0代表备用路由表中到达目的节点的跳数，Hop代表发送RREP给自己的节点到目的节点的跳数。

AddressTo代表RREP所指向的节点地址，AddressFrom代表发送RREP的节点地址。

具体工作过程如图5所示，a在节点D收到来 5的RREQ请求之后，会发送RREP报文，节点4，6在无线传输的有效范围内接收到了这条报文，会建立到节点D的备用路由，这里和原始AODV-BR协议保持一致。节点5在收到这条来自节点D的RREP报文后，会继续将报文传递，这时节点4，6会再次收到来自节点 5的RREP报文，节点4，6根据伪代码中原则不予处理。b接下来节点2接收到了来自节点5的RREP报文，这次在传输范围内的节点4，6又会收到来自节点2发送RREP报文，节点4，6再次根据伪代码原则进行判断，需要向节点2发送RREPS报文，假设节点2先收到来自节点4的RREPS报文，则建立以节点4为下一跳目的节点为节点D的路由放入备用路由表中。c节点1，3同样会收到来自节点2的RREP报文，根据伪代码中原则，节点1，3会向节点S发送RREPS报文，假设节点S先收到了来自节点3的RREPS报文，则将以节点3为下一跳目的节点为节点D的路由存入自己的备用路由表中。

图5 AODV-BRS协议Fig.5 AODV-BRSprotocol

3 结 论

相较原始的AODV-BR协议，在改进后的AODV-BRS协议中，备用路由不仅只在非主路径上建立，主路径上节点的备用路由也会随之建立。改进后的协议可以在链路出现中断时，直接在发现链路中断的节点处利用备用路径将数据转发，取代了之前协议中发现断路节点将数据包转发给全部邻居节点，由邻居使用自己的备用路径将数据转发的机制。这样有效避免了之前协议中，多个重复数据造成的传输路径资源的浪费，进一步降低了无线Mesh网络时延。

[1]王萍，李颖哲．无线Mesh网络基础[M].西安：西安交通大学出版社，2012:1-25．

[2]方旭明．移动AdHoc网络研究与发展现状[J].数据通信，2003（4）:30-33．FANG Xu-ming．Research and development status of mobile Adhoc[J].Data Communication，2003（4）:30-33．

[3]Perkins C，Bekling-Royer E，Das S．Ad Hoc On-demand Distance Vector （AODV） routing protocol[J]．Internet Engineering Task Force（IETF），2003（7）:134-146．

[4]Sung JL，Mario Gerla．AODV-BR:Backup Routing in Ad hoc Networks [C]//Wireless Communications and Networking Confernce，WCNC.IEEE.2000，3:1311-1216．

[5]Hsing Lung Chen，Chein Hsin Lee．Two hops backup routing protocol in mobile ad hoc networks [C]//Parallel and Distributed Systems，2005:600-604．

[6]Junghui Jeon．Fast route recovery scheme for Mobile Ad Hoc Networks [C]//International Conference on Information Networking （ICOIN），2011:419-423．