基于AODV的无线Mesh网络路由协议优化设计

摘 要 无线Mesh网络（WMN）融合了WLAN和Ad hoc网络的优势，具有高速、多跳和自组织的特点，广泛用于会场、医院和车站等场合.由于其开放性和无线链路，导致路由协议效率不高.针对Ad hoc单跳路由的缺陷，从WMN的体系结构入手，提出了设计原则和方法，并在AODV的基础上，通过修改数据包的格式，优化设计了相应的网络协议，并给出了相应的路由算法，然后选择时延和负载两个核心指标，在OPNET平台上进行了仿真实现，结果表明，15个节点组成的WMN和4个节点的网络相比，其关键指标值优势明显，说明这种算法更加适合于规模较大的网络.

关键词 无线Mesh网络；路由协议；AODV；数据包；OPNET

中图分类号 TP393 文献标识码 A 文章编号 1000-2537（2015）03-0085-06

无线Mesh网络（Wireless Mesh Network-WMN）是一种基于IP协议的无线宽带接入技术，它融合了WLAN和Ad hoc两者的优势，支持多点对多点的网状通信模式，具有自动组网、自动修复、多跳级联和节点自我管理等智能优势以及移动性、宽带宽和无线定位的特点，是一种高速率、大容量和宽覆盖范围的网络，是解决最后1km无线宽带接入瓶颈问题的理想方案.任意无线设备节点在接入此网络后，既能发送和接收信号，又具备路由转发功能，即充当路由器，能同时与一个或多个对等节点直接通信.其最大好处在于：如果邻近的AP由于流量过大而导致拥塞，数据可以自动重新路由到一个通信流量较小的相邻节点传输，直到送达最终目的地，即多跳访问.因而被广泛应用于会场、医院、机场、学校和小区等各种场合[1-2].

WMN最初源于军事领域，应用在战场上的移动网络需要极高的数据速率、极低的被检出概率和防外来干扰的能力.随着802.11局域网技术的深入研究，无线Mesh技术逐步成为业界和研究的焦点，并沿不同的分支演进.其路由技术的核心主要是两个方面[3]，路由协议和路由算法.路由判据、路由容错、负载均衡、多径路由、跨层信息交互、QoS、多信道等都是路由设计要考虑的因素.

文献[4]以动态源路由协议DSR为基础，提出了一种新的安全增强的多径DSR路由协议SE-DSR，通过多径路由发现机制为协议提供负载均衡和路由容错能力，采用双向路径信任评估和单向证书链验证为协议提供安全保障，通过牺牲存储缩短了网络延时.文献[5]利用蚁群算法求解跨域跨层跨节点的QoS自适应体系架构模型，设计了双层规划模型的蚁群优化路由算法.文献[6]提出了多信道无线Mesh网络路由度量CLIDH概念，设计了跨层多信道路由协议CMAODV，提高了网络资源利用率.文献[7]通过分布式免干扰的链路调度机制，根据带宽要求为链路分配时槽数，保证带宽链路流，增加了通信连接成功概率.文献[8]提出了面向吞吐量效率的机会主义路由算法，通过引入传输时间因素，在转发节点数量与链路稳定度之间取得平衡，提高了网络性能.文献[9]分析了在路由算法设计时，链路质量、期望传输次数、每一跳的往返时间等相关参数对网络性能的影响，提出了基于加权累计期望传输次数的路由度数指标，较好地解决了信道相互影响的问题.

无线Mesh网络兼容现有任何IEEE802.11的无线网络通信协议，并且在802.11s，802.15，802.16d/e，802.20等标准中对Mesh组网技术作了一定的规范.学术界已经取得了一定的研究成果，并有相关产品投入市场，但作为一种新型网络架构，国际上尚未形成非常成熟的标准.我国参与IEEE802标准开发的很少，影响了它的迅速推广，还有许多问题值得进一步探索，特别是路由算法的设计还有很大的研究空间，成为其推广应用的瓶颈.

1 无线Mesh网络体系结构

WMN包括无线骨干网和无线移动接入两部分，前者由无线 Mesh 路由器组成，节点位置相对固定，提供无线回程功能，移动性较少，而无线移动接入部分则是由用户节点连接接入点 AP和无线用户终端节点组成.近端用户节点可以直接关联接入点，而距离骨干网节点较远的用户，可以通过其他用户节点中继后连入WMN，用户节点通过自组织、自配置互联.其体系结构如图1所示.

无线Mesh网络的节点通常包括3类：客户端（移动终端）节点，路由节点和网关节点，它是一个可靠而冗余的无线网络.当一个节点发生故障，其他节点可以通过一个或者多个中间节点互相连接后通讯，节点的接入和撤出都容易实现.

2 无线Mesh网络路由协议设计的原则与方法

无线Mesh网络是WLAN和Ad hoc自组织网络技术的结合，其路由算法可以通过继承并进行改造而实现[10-11].

2.1 无线Mesh网络的路由协议类型

无线Mesh网络路由协议主要分为4类[12]：（1）先验式路由，即每一个节点平时维护一张路由表，预先存储了目标节点的IP地址及下一跳的位置信息，在发送数据时直接调用表的相关记录，节点间通过周期换路由信息更新表的内容；（2）反应式路由，即后验式，只有当向目的节点发送包时，源节点才在网络中发起路由查找过程，找到相应的路由信息后记录到路由表；（3）混合式路由，包括先验式路由协议和反应式路由协议两部分；（4）机会路由，利用无线网络的广播特性，每次数据包总是转发给一组节点，这些节点根据它们到目标节点的度量（Metric）确定其优先级，然后选择优先级最高的节点再次转发数据包给另外一组节点，如此重复转发直到目的节点.

2.2 无线Mesh网络路由协议的设计原则

Ad hoc网络采用最小跳数优先的路由协议.无线Mesh网络仅依靠跳数还远远不够，还要综合考虑线路状况等多种度量指标，以满足网络的健壮性和容错性并使其能够在链路失效时快速恢复，并通过流量统计进行负载均衡，以充分利用系统资源.

在设计无线Mesh网络路由协议时，重点考虑4个原则[13-14]：（1）路由判据，反映链路的优劣，良好的路由判据提供负载均衡，方便确定最佳路由，是影响无线Mesh网络路由协议性能的核心指标；（2）避免环路，从发送端到接收端采用单一方向，避免因循环转发产生回路而出现的拥塞和死锁；（3）机会平等，在信道竞争和数据传输过程中，各节点在分配网络资源时均能具有相同概率；（4）QoS保障，根据实时链路质量及带宽选择路径，使QoS 需求最大化，保证服务质量.

2.3 无线Mesh网络路由协议的设计方法

无线Mesh网络路由协议的设计方法主要包括两种：一种是借鉴Ad hoc网络的路由协议，结合自身特点，改造或优化原有的路由协议，最大程度地提高网络性能，这种方法较为常见；另一种是设计全新的路由协议，一般适用于制造厂商，研发周期长，消耗大，是研究者改进的基础.

3 AODV路由协议的优化设计

3.1 AODV工作原理[11，15]

AODV协议（Ad hoc On-Demand Distance Vector Routing），即按需距离矢量路由，是一种基于目标的反应式路由协议[16]，其基本数据包包括路由请求RREQ，路由应答RREP，路由错误RERR.当某节点给其他节点传送信息时，若没有现成路由，则以多播形式发出路由请求报文RREQ.RREQ报文携带发起节点和目标节点的IP地址，邻近节点收到RREQ以后，判断目标节点是否就是它本身.如果是，则向发送方回送路由响应RREP；如果不是，则在自己的路由表中查找是否有达到目标节点的路由.如果有，则向发送节点返回RREP，否则继续将RREQ转发到下一节点进行查找.AODV采用定期广播HELLO报文的方式维护路由，一旦发现某一处链路处于断开状态，则发送错误信息报文ERROR通知那些由于链路断裂而不可到达的节点删除相关记录或者进行路由修复.RREQ的格式如图2所示.

AODV路由维护过程：若因为源节点的移动而导致路由失效，则源节点重新发起路由发现过程；如果是目标节点或者中间节点的移动而引起的路由中断，则该链路的上游节点会主动发送一个RRER分组到使用该链路的各个相邻节点，此报文被发送到所有使用该链路的源节点，同时跳计数器设置为无穷大，表示不可达，各源节点需要重新发起路由发现过程；当目标节点检测到与它相连的链路发生错误时，则不会产生主动路由响应报文，而与路径无关的其他任何节点的移动都不会影响寻径，也不需要路由维护.

3.2 AOVD的改进

RREP数据包中包含了一个保留字段Reserved，是系统升级扩展而预留的字段，设置为全0.为了充分利用AODV的按需距离矢量策略，可以将这个字段替换为某个评判标准，即一个计算值，通过此字段，当前节点即可以在RREQ报文中携带到达目的节点的判定信息，作为路由转发的判据值，从而确定下一跳所在的位置.同时，各节点的数据包中需要记录到达目标节点的第一跳的地址，用于确定下一跳的路径是已有路径还是新建路径，可以通过增加一个字段Next Hop IP附加在RREQ扩展信息中，表示从源节点发送到目标节点路径的下一跳.在不影响原有结构的基础上改进RREQ格式包结构，如图3所示.

在图3包格式中，最重要的指标是判据值，AODV采用了最小路由优先的判据标准，但没有充分考虑丢包率、信道干扰和传输速度等因素带来的影响，其结果必定存在一定的偏差.将期望传输次数、加权期望传输次数以及链路干扰等因素作为综合判定的依据，得到的结论更加全面.

假定正向丢包率和反向丢包率分别用Rf和Rr表示，则包传输出错的概率P为

若传输失败，则自动启动重传机制，这样经过反复重传后总是可以达到目标节点，由此求出从源节点到目标节点的期望传输次数ETX为

在一条路径上所有跳的ETX之和就是路径判据，选择各条路径中最小者为传输路径，即min（∑ni=1ETX），其中n表示链路数，该方法反映了丢包率以及路径的长度.考虑到各种正交信道的传输速率不同，因此判据中需要加入数据包大小S和链路带宽两个因素，即得到加权期望传输次数ETT，其算式为

由于其他链路和节点对当前链路存在干扰，影响传输性能，在判据中加入影响因子α，α是可调节数，其范围为[0，1]，初值可设为0.5，用S1表示对当前链路存在干扰的链路集合，S2表示对当前链路存在干扰的节点集合，则当前链路的判据IC可以改进为

其中m表示对当前链路造成干扰的链路数，最后得到综合判据SCS为

这种判据将链路长度，传输质量，丢包率和信道干扰等因子考虑进来，其判断结果更加全面客观.

3.3 算法设计

当发送节点需要向接收节点传送数据时，发送方先检查自己所维护的路由表，确定是否有直达目标节点的路径.如果存在这样的路径，则按照判据计算此路径的评价值Vnow，并与原值Vold比较.若Vnow>Vold，表示相邻节点采用了不同信道传输并且干扰较小，则选择此路径进行数据传输；否则仍然采用原路径传输.如果节点维护的路由表中没有直达目标点的路径，则发送方节点重新发起路由请求建立路径.假定有两个节点S和D，则从源点S到目标点D是最合适路径的条件为：对于任意节点W（S和D除外），由S到D的评判值V不小于S到W及D到W的评判值的最大值.即，V（S，D）>=max{V（S，W），V（W，D）}.

算法的执行过程：初始状态路由表为空，节点集合为S，进入路由发现过程；如果从源节点到目标节点的跳数超过生存时间，则放弃此次操作重新查找；反之则向网络广播RREQ，获取下一跳的位置，并计算其评判值，如果下一跳已经出现在路由表中，需要比较当前评判值与路由表中的值，取其较小者作为当前的路径加入路由表，按此过程继续寻找下一跳，直到找到目标节点为止.

4 性能分析

OPNET是一个网络仿真技术软件包，能够准确的分析复杂网络的性能和行为.此处用OPNET为仿真软件，选取最主要的两个性能参数：端到端的时延、负载作为评价标准，搭建1 000*1 000 m的开阔环境，15个无线节点（含一个根节点）随机分布，数据包为1 kb，所有节点均以2 m/s速度随机移动，数据传输率为1 Mbps，节点功率为0.001 W，仿真时间设置为30 min，同时选取4个节点的简单情况作为参照.仿真结果如图4和图5所示.

图4反映的是在30 m不同的场景范围内，其时延秒数的变化情况.可以看出，当场景只有4个节点时，平均时延较高，而15个节点时平均时延低，大于10 m范围后趋向稳定，时延为0.001 4 s.图5表示了不同的场景范围内，网络的负载情况（bps），可以清晰地显示，15个节点比4个节点场景的平均负载低，10 m范围以后，负载趋向稳定.由此得出结论，当节点数较多时优化后的AOVD协议选择最佳路径进行数据传输，其网络时延和网络负载性能指标均高于节点较少的情况，表明本协议适合于节点较多的大型场景，比原来的AODV协议具有更实用的优势.

5 结语

本文按照无线Mesh网络体系结构的特点，探讨了其路由协议的常用设计方法和原则，在AODV的基础上进行了优化设计，并在仿真平台上对其时延及负载等性能进行了对比分析.虽然路由选择在网络层实现，但如果充分利用来自于MAC的数据进行跨层次设计，并充分考虑各种影响因子设定综合判据标准，无疑能够更好地完善路由性能，而本文并未对这些内容做详细的研究，有待今后进一步研究.

参考文献：

[1] 沈 呈，陆一飞，夏 勤.基于综合判据的无线Mesh网路由协议[J].计算机学报， 2010，33（12）：2300-2311.

[2] DAN A O， FANG X M， MA Z J. Key technology and applications of wireless mesh networks[J].Telecom Eng， 2005，2：16-22.

[3] 王晓翔.无线Mesh网络路由技术研究[D].重庆：重庆大学， 2012.

[4] 李每虎，郭渊博.SE-DSR：一种安全增强的Mesh网络多径动态源路由协议[J]. 计算机工程与科学， 2012，34（5）：17-23.

[5] 张千里.基于蚁群的Mesh网络路由算法模型的设计[J].赤峰学院学报， 2012，34（9）：28-29.

[6] 刘宴兵，吴涛，先兴平.多信道无线Mesh网络路由机制[J].小型微型计算机系统， 2012，33（2）：319-324.

[7] 项 慨，曾园园.多信道无线网状网带宽有效的路由机制设计[J].计算机应用研究， 2012，29（8）：3081-3084.

[8] 赵传强.基于机会路由与多路径路由的无线Mesh网络关键技术研究[D].北京：北京邮电大学， 2010.

[9] GUNGOR V C， LAMBERTET F. Routing metrics and protocols for wireless mesh networks[J].IEEE Network， 2008，2（22）：6-12.

[10] 王梦莹.无线Mesh网络路由技术的改进研究[D].南京：南京邮电大学， 2013.

[11] PERKINS C E， ROYER E M. Ad hoc On-Demand Distance Vector （AODV） Routing[C]//Mobile Comput Syst Appl. Proceedings. WMCSA ′99. Second IEEE Workshop. New Orleans， LA， 1999.

[12] 杜 辉.无线Mesh网络路由协议研究[D]. 武汉：武汉科技大学， 2010.

[13] 张 维，丁恩杰，赵 亮.无线Mesh网络中基于负载平衡的自适应拥塞控制路由策略[J].煤炭技术， 2012，31（8）：177-179.

[14] 陈建华.无线Mesh网络路由协议研究[D].南京：南京信息工程大学， 2009.

[15] LI P， SCALABRINO N， FANG Y G， et al. How to effectively use multiple channels in wireless mesh networks[J]. IEEE Trans Para Distri Syst， 2009，20（11）：1641-1652.

[16] REN W， YEUGD Y， JIN H. TCP performance evaluation over AODV and DSDV in RW and SN mobility models[J]. J Zhejiang Univ Sci A， 2006，7（10）：1683-1689.