摘  要： 在分析经典路由协议AODV的基础上，结合Mesh网络的特点，提出了一种新的路由协议AODV-LS。新的路由协议根据节点带宽以及实时负载量这两个参数计算出节点权重值，根据节点权重值评估链路的性能，根据链路性能选择最优路径。实验结果表明，AODV-LS协议在数据分组投递率、端到端延时和标准化路由负载方面都优于AODV。
关键词： AODV；节点权重值；分组投递率；端到端延时

    无线Mesh网络结合了Ad Hoc网络和传统固定网络的特点，具有高性能、低功耗、自组织、自配置的特点，因此Mesh网络成为家庭网络、社区宽带网络、企业内部网络的优先选择[1]。对于Mesh网络来说，关键问题在于如何实现高品质的路由协议，协议不但要能够及时应对网络拓扑的动态变化，还要实现多跳传输的质量服务。
    Mesh网络目前使用的路由协议基本上都是从Ad Hoc移植过来的，AODV作为 Ad Hoc网络经典的路由协议，适用于动态的、多变的Ad Hoc网络，它同多数其他Ad Hoc路由协议(如DSR、DSDV等)一样,采用最短路径路由算法,但是大量的实验和实践证明了该算法并不适用于无线Mesh环境，主要是因为它以源节点到目的节点的跳数作为路由评价的标准，然而跳数最少的路径在实际中未必是最优的[2-3]。如当跳数最少路径上的节点严重过载时,就会引起大量数据包丢失，增加延迟和降低网络性能。在Mesh中，由于802.11 MAC采用的是分布式协调功能, 在同一时刻的冲突域内只允许两个节点进行通信, 另外在冲突域内存在隐藏节点和暴露节点,当网络负担较重时, 无线网络的性能下降尤为突出,网络吞吐性能远低于理论值[4-5]。
    由于Ad Hoc路由协议先天不足，以及Mesh网络自身的特殊性，现有的Ad Hoc路由协议不能满足Mesh网络的要求，因此本文提出了新的路由算法AODV-LS。
1 AODV算法
    AODV是基于DSDV和DSR提出的一种按需路由。AODV协议当中一个重要的特点就是添加了序列号，可以有效地阻止计数无穷大和路由环路问题。在AODV中每个节点维护一个路由表来记录从路由包中获得的路由信息。当源节点需要发数据时，会查看自己的路由表里有没有该条路径，如果有，则按照路由表项中的信息直接转发数据；否则发起一个路由发现过程。首先，源节点创建一个RREQ包并广播，当邻居节点接收到RREQ包时，该节点将RREQ包中的跳数值加1并在自己的路由表中创建一个反向路由，如果该节点就是目的节点或者该节点存在到达目的节点的路由表项，则该节点就向源节点发送RREP，否则它只广播RREQ。
    RREP的传播是由目的节点向源节点单播完成的。当一个节点收到RREP之后，创建正向路由表项，其中包含目的节点和下一跳节点。根据反向路由表继续传播RREP，直到RREP被源节点接收到。节点移动可以破坏之前的路由，为了增加成功的数据传输率，本地节点能够修复损坏的链路。发生断路时，网络的上游节点向目的地发送RREQ，为了避免环路，应该将RREQ中目的节点的序列号加1。若本地修复成功，目的节点或者包含目的节点路由信息的中间节点创建RREP；如果节点修复失败，则向源节点发送一个RERR包，源节点则重新创建新的RREQ，重新开始路由发现过程[6]。
2 改进的AODV-LS路由协议
2.1 AODV-LS路由选择量度
    AODV-LS中组合量度使用带宽、缓存饱和度两个参数。本文采用了基于 NAV[5]的统计来估算可用带宽，节点所在信道的空闲时间是一个很重要的参数，由节点以及邻居节点的业务量综合决定，在这段时间内节点可以成功地传输数据。Bi=B×Ti/Tc，其中Bi为节点的实时可用带宽，B为信道带宽，Tc为观察时间，Ti为在观察时间内的信道空闲时间。这里还考虑了节点缓存队列饱和度的影响，如果节点缓冲队列已满，网络发生拥塞会引起网路性能的急剧下降，例如时延增大、丢包率增加等。如果在路由发现时考虑节点负载状态，将会降低拥塞，提高网络性能。本文定义缓存饱和度为缓存节点的包的数量与允许缓存的额定包数之比，定义为ri=Ci/Cm，其中，Cm为缓冲队列最大值，Ci是缓冲队列中包数值。
    节点负载越大,缓冲越接近饱和, 其同邻居节点间的链路则越繁忙, 可用带宽越少, 因而通信传输代价同时也就越高。节点i的链路权重Xi计算如下：
    Xi=[Bi/B+(1-Rti)+(1-Rgi)]×10
其中，Rti表示发送缓冲饱和度，Rgi代表接收缓冲队列饱和度。并且一条链路的关键因素是所有中间节点权重的最小值：Xmi=min（X1，X2，X3，X4，…，Xh-1），h为该条路径的跳数。若Xmi越大，说明该条链路负载越少；Xmi越小，说明该条路径上负载越大。为了综合考虑链路状况，还要考虑路由节点的链路权重之和，即：
    Wj=sum（X1+X2+X3，…，Xh-1）
最后给出路由判定量度组合：
    Pj=?琢×Xmi+(?茁×Wj)/(h-1)
式中?琢、?茁值的选取通过试验获得，且?琢+?茁=1。为了尽量避开负载较重的节点，在源节点到目的节点之间找到一条负载较轻的路径，赋予?琢较大的权重。
2.2 路由发现与建立
2.2.1 请求报文与数据报文
    (1)路由请求报文RREQ，包括Type，Hops，RequestNo，DestinationIP，OriginatorIP，PreNode，Xmi，Wj。
    (2)路由响应报文RREP，包括Type，Hops，RequestNo，DestinationIP，OriginatorIP，PreNode，RREQSrc，Xmi，Wj。
2.2.2 路由发现过程
    每个节点都保留一个路由表, 用来存储节点所需要的路由信息，其表项是一个向量（Destination，NextHop，Wj，Hops，Pj，S，X，Xmi，LF），其中Destination表示目的网络，NextHop为到达目的网络的下一跳, Wj为从该节点到达目的网络的累计链路权重，Hops为从该节点达到目的网络的累计跳数，S为路由发现发起的节点，X为路由请求序号，LF为路由表项的生存时间。
    (1)当源节点s要向目的地d转发数据时，若存在s到d的路由，则转发数据即可，如果不存在s到d的路由信息，则创建RREQ报文并广播，RREQ中Type=1，Hops=0，Xmi=0，Wj=0，DestinationIP=d，OriginatorIP=s，Pre-Node=s，RequestNo=(当前节点最新的路由请求序号+1)。
    (2)当节点k接收到RREQ包时，首先查看自身的权重值，如果自身的权重值超过了规定的权重值范围，则直接扔掉该RREQ报文，否则创建反向路由向量,并且用RREQ报文中的值来填充该路由向量（s,RREQ.PreNode,RREQ.Wj,RREQ.Hops，α×RREQ.Xmi+β×RREQ.Wj/（RREQ.Hops-1）,RREQ.RequestNo,RREQ.Xmi,LF）。如果k≠d，并且k中不含有到达d的向量，则修改RREQ报文，若RREQ.Xmi<k.Xmi,则RREQ.Xmi=k.Xmi，否则RREQ.Xmi保持不变，RREQ.Hops=RREQ.Hops+1，RREQ.PreNode=k，RREQ.Wj+k.Xmi,修改后的报文继续广播。如果k=d或者k的路由表中存在到达d的路径，则产生回复报文RREP,RREP中Type=2，RREP.RequestNo=RREQ.RequestNo,RREP.OriginatorIP=d,RREP.RREQSrc=RREQ.OriginatorIP,RREP.DestinationIP=RREQ.PreNode，如果k=d，则RREP.Hops=0，RREP.Xmi=0，RREP.Wj=0，若k路由表中存在到达d的向量，则RREP.Hops=RT.Hops,RREP.Xmi=min(K.Xmi,RT.Xmi)，RREP.Wj=RT.Wj+k.Xmi(这里假设RT是该节点到目的地的向量)，构造响应报文之后以单播的方式转发。
    (3)当节点h收到RREP之后，构造h到下跳节点的正向路由向量（d,RREP.PreNode,RREP.Wj,RREP.Hops,RREP.Pj,RREP.RREQSrc,RREP.RequestNo,RREP.Xmi,LF）,如果h不是s，则更新RREP继续单播下去，直至源节点s接收到RREP。
    在寻找路由定时器超时前，如果源节点s收到相对应的RREP报文，则构建从s到d的路由向量。如果在定时器时间内源节点s收到多个RREP回应，本设计选择前3个做比较。从中选择链路值最大的一个回应。如果出现链路值相等的情况，则选择链路最短的一个。考虑到链路的延时问题，接收到3个RREP包后多余的就直接放弃。

    如果一个本地修复请求到期时，则断路节点的上游节点产生RERR报文，通知源节点本条路由已断路，如果需要，重新发起路由请求。
    (2)节点过载的路由维护。AODV-LS中节点a发送的HELLO报文,还会计算a与邻居的链路权重。当权重值超出规定的范围时, 就广播节点过载LRRERR报文，邻居节点b收到LRRERR报文后，节点b则继续按照(1)中的方式，按节点a不可达时的情况进行路由维护。
3 仿真与分析
    利用NS2(v2.34)对AODV-LS进行仿真，分别对数据包平均端到端延迟、数据包转发率、标准化路由负载等性能进行分析。MAC层采用IEEE802.11标准规定的分布式协调功能,利用CSMA/CA作为传输机制，网络带宽为2 Mb/s，发送数据包的大小为512 B。在仿真过程中，50个无线路由节点在一个800 m×800 m的矩形区域内随机移动，移动速度分布在0～4 m/s的范围内。数据源节点的个数为20，发包率为每秒分别发送 1、2、4、7、10 个包来产生不同的负载。分别对AODV-LS协议和AODV协议进行模拟仿真，并对仿真结果进行分析，得到两个协议在不同停留时间下的数据包转发率、数据包平均端到端延迟和标准化路由负载。
    图2显示了网络中节点发包率变化时，AODV、AODV-LS数据包转发率的曲线。结果表明在网络负载很小时，AODV、AODV-LS都有较高的、相近的数据转发率。而当网络负载增加时，AODV-LS的性能提高十分明显。这是因为AODV-LS尽量避开负载较重的节点，选择负载较轻的路径传输数据，间接地提高了整个网络的吞吐量。

    图3显示分组平均端到端时延的变化曲线，节点发包率较小时，AODV-LS与AODV平均端到端延迟相近，但随着节点发包率的增加，AODV-LS延迟明显小于 AODV。当网络负载增大时，AODV-LS试图找到一条链路状况最好的路径，绕过堵塞的节点，减小了拥塞等待时间。

    本文针对Mesh网络自身的特点，对AODV算法做了改进，提出了新的AODV-LS路由协议，该协议采用节点权重值作为路由建立标准。实验结果表明，由于采用了权重值作为路由判据，整个网络的吞吐性能、包转发率、端到端延时等方面都要优于AODV，体现了良好的性能。
参考文献
[1] AKYILDIZI F，WANG X D，WANG W L.Wireless Mesh networks：Asurvey[J].Computer Networks，2005，47(4)：445-487.
[2] WAHARTE S，BOUTABA R，IRAQI Y，et al.Routing protocols in wireless mesh networks：challenges and design considerations[J].Springer Multimed.Tool Appl.2006，31(3)：285-303.
[3] 符云清，王松健，吴中福.基于链路状态加权的无线Mesh网络路由协议[J].计算机研究与发展，2009，46(1)：137-143.
[4] JUN J，SICHITIU M L.MRP：wireless mesh networks routing protocol[J].Comput.Commun，2008，31(7)：1413-1435.
[5] CHEN L，HEINZELMAN W B.QoS-aware routing based on bandwidth estimation for mobile Ad Hoc networks[J].IEEE Journal on Areas in Communications，2005，23(3)：561-572.
[6] PERKINS C E，ROYER E M.Ad-Hoc on-demand distance  vector routing(AODV)[C].RFC 3561，2003.
[7] 柯志亨，程荣祥，邓德隽.NS2仿真实验——多媒体和无线网络通信[M].北京：电子工业出版社，2009.