摘 要：为解决Ad Hoc网络的AODV路由协议在通信过程中存在的拥塞问题，提出了改进AODV路由协议的思想。根据网络链路拥塞度的大小采取不同措施和节点路由，建立不相关多径路由分流以避免拥塞。仿真结果表明，改进后的路由协议有效地减少了发生拥塞的几率，从而提高了移动Ad Hoc网络的性能。
关键词：Ad Hoc网络；路由协议；链路拥塞
移动自组网MANET(Mobile Ad Hoc Network)[1]是由一组带有无线通信收发装置的移动终端节点组成的一个多跳、临时性无中心的网络，整个网络没有固定的基础设施,网中的每个终端都可以自由移动、自由加入和退出网络，各网络节点地位相等。Ad Hoc网络具有很高的灵活性，可以广泛应用于不易建立基础设施的环境，如地震后的紧急搜救、军用战术环境和民用应急通信。与单跳的无线网路不同，移动自组网的节点之间通过多跳数据转发机制进行数据通信，需要中间节点进行分组转发决策。
移动自组网路由协议的多数路由协议以单径路由算法为基础，而且在路由选择时以跳数最少(或称为路径最短)作为选择标准，没有考虑网络拥塞问题。由于一条路径的带宽有限，当很多节点都选择跳数最少路径作为路由路径时，骨干节点连接繁忙，从而造成端到端时延和丢包率增大，网络拥塞，影响网络整体性能[2]，而且拥塞引起的路由控制消息丢失会触发更多的路由请求和路由回复，从而加剧网络拥塞。
1 AODV路由协议
网络路由协议是实现网络通信最关键和最核心的问题。目前比较成熟透明的按需距离矢量路由AODV(Ad Hoc on-Demand Distance Vector Routing)[3]基于传统的距离向量路由机制，具有简单易实现、防止循环发生、支持中间节点应答等优点，但也存在一定不足：每次由源节点发起路由请求均只得到一条路由、中间节点的应答路由可能过时等。在AODV协议的仿真实验中发现，随着网络负荷的增加，网络经常出现局部拥塞，吞吐率下降很快。网络中某些节点负荷很大，而节点的链路带宽和处理能力有限，当数据到达速率超过节点处理能力时，数据将阻塞在这些节点中等待传输。一旦这种状况持续一段时间，节点缓冲区会很快溢出，从而造成数据分组丢失。而源节点因在规定时间内没有收到确认而选择重传，这又将进一步加剧该路径节点的拥塞，导致这些节点成为影响网络效率的瓶颈[4]。
为了缓解拥塞对网络性能的影响，提出一种基于AODV路由协议，能够缓解链路拥塞的路由算法LC-AODV。在拥塞节点的上游节点处建立能绕过拥塞节点的旁路，在网络工作路由处于堵塞情况时启动备份路由分流，从而避免拥塞的发生。
2 LC-AODV路由协议
2.1 AODV路由协议的修改
在AODV路由协议中，路由查找过程只建立一条从源节点到目的节点的跳数最少、距离最短的路由。为了缓解拥塞，在一次寻找路由过程中建立多条节点不相关路由，并在路由寻找过程中加入链路拥塞度。
定义1：节点不相关路由，指所建多条路由中，任何两条路径除了源节点和目的节点外，其他节点都不共用。
定义2：链路拥塞度，描述本节点与下一跳邻居节点的拥塞状态，取值为下一跳节点的MAC层接口缓存队列中剩余空间占总队列的比率。
具体修改操作如下：
(1)在AODV路由协议的基础上，针对路由请求RREQ和路由应答RREP控制包分别增加一个条目——链路拥塞度。在源节点需要传输数据时，发送路由请求RREQ消息，当RREQ报文按照不同的路径到达目的节点时，目的节点不是简单地只处理第一个到达的RREQ，对此后到达的RREQ回复相同的RREP，并建立源节点到目的节点的备份路由。
(2)在路由维护阶段，周期性地传输Hello报文以确保链路的连接。但是在LC-AODV路由协议中，同样在Hello消息中增加链路拥塞度这一条目，检测该节点与邻居节点之间链路的拥塞度，并加以动态调整。
2.2 拥塞状态检测
在进行数据传输过程中，当传到一个节点的包个数超过它的处理能力时，节点就会变得拥塞，由于节点队列长度有限，故包会根据队列类型的方式开始丢弃，用R来表示定义2描述的链路拥塞程度[5]。根据R值的不同，设定三种拥塞状态。根据式(1)的划分，LCD为0时表示链路不拥塞，显示为绿色状态；LCD为1时表示链路出现拥塞，但是不是很严重，显示为黄色状态；LCD为2时，链路出现严重拥塞，显示为红色状态。
2.3 LC-AODV工作原理
搭建一个移动Ad Hoc网络，如图1所示，S为源节点，D为目的节点，其他为中间转发节点。当源节点有数据要向目的节点传输，而且S节点中没有到目的节点的路由时，需要建立路由。源节点广播路由请求RREQ，假设在路由建立过程中，找到了两条路由分别为路由1：S-3-4-5-D和路由2：S-1-2-D。路由1先返回路由应答，则路由2作为备份路由存在于网络中。当数据开始传输一段时间后，节点3到节点4之间发生路由拥塞，则节点3启动局部修复，发现可通过节点6到达目的节点，则产生路由S-3-6-5-D，因为通过节点6进行传输时，链路有轻微拥塞，则向上游节点通知备份路由，随时准备发送数据。如果修复不成功，则直接启动备份路由2进行数据传输。当所有路由都失效的情况下，源节点重新启动路由请求过程。
2.4 邻居拥塞表
每个节点维护一个邻居拥塞表，记录本节点所有邻居节点(除去上一跳节点)的拥塞状态。例如在表1中，对于节点S而言，LCDs1的值为0。
3 实验仿真及结果分析
实验采用NS2[6]模拟平台进行模拟，将LC-AODV算法与AODV在相同网络环境和高负载特性下进行仿真和性能对比分析，以便有效评价本算法的性能。网络拓扑结构设计为50个移动节点的网络模型，各节点随机分布在1 200 m×1 000 m的平面矩形区域，每一个节点的最大传输范围为250 m，随机任意方向运动(Random Way Point) ，节点停留时间为0 s，实验模拟时间500 s，运动最大速率为40 m/s，连接为20个CBR，大小为512 B数据流，数据流为3 packets/s，最大连接数为20。物理层选用TwoRayGround无线传播模型，MAC层采用802.11b DCF协议。仿真过程如图2所示。通过数据包的成功传输率和平均端到端传输延迟2个指标来比较。
3.1 数据包的成功传递率
数据包递交率：目的节点收到的数据包数与源节点发送的总数据包数的比率。仿真结果如图3所示。LC-AODV的正确传输率比AODV更高，因为采取抗拥塞措施，节点丢失包的几率就会降低，导致到达目的节点的数据包增加。当节点移动速度不快时，网络的节点位置变化不大，即拓扑结构较为稳定，网络数据包的正确传递率都处于高水平，但是随着节点移动速度增大，数据包丢失增多，网络整体性能下降。而且随着网络拓扑结构变化的加快，两种路由协议之间的差距在慢慢变小，这是因为改进后的路由协议在拓扑结构变化比较快时，路由经常失效，抗拥塞措施作用有所下降。
3.2 平均端到端延迟
传输数据包所需的总延迟包括缓存数据包、新路由发现、在队列中排队、MAC层重传、发送和传播所用的时延总和。仿真结果如图4所示。整体而言，LC-AODV的性能优于AODV路由协议，这是因为采取了抗拥塞措施，在数据传输的时候选择拥塞度低的链路，而且在传输过程中若遇到拥塞会及时地进行链路转移，使得传输更为顺畅。而且在节点移动速度较小时，拓扑变化较小，备份路由存在时间长，导致备份路由在节点移动速度低时较节点移动速度快时的利用率更高，从而速度低时两路由协议的延迟差距更小。
本文针对移动Ad Hoc网络高负载情况下网络路由不能很好适应网络环境的问题，提出了一种抗拥塞的改进AODV路由协议。改进的LC-AODV协议是一个适用于动态Ad Hoc网络的拥塞适应路由协议。利用邻居拥塞表，节点能即时感知与邻居之间的网络拥塞度，并根据拥塞等级采取不同的策略，通过备份路由来快速重新传输数据。结果证明改进后的路由协议可以缓解网络的负载，提高了数据包正确传输率并降低端到端平均延迟。
参考文献
[1] RAMANATHAN R，REDI J.A brief overview of mobile Ad Hoc networks: Challenges and direction[J].IEEE Communications Magazine, 2002, 40(5): 20-23.
[2] KLIAZOVICH D，GRANELLI F. Cross-layer congestion control in Ad Hoc wireless networks[J]. Ad Hoc Networks, 2006(4): 687-708.
[3] PERKINS C E, ROYER E M.Ad Hoc on demand and distance vector(AODV) routing[C]. The second IEEE workshop on mobile computing systems and applications. New Orleans. 1999:90-100.
[4] RAGHAVENDRA H.Congestion adaptive routing in mobile Ad Hoc networks[A]. IEEE Transactions on Parallel Distributed Systems[C].NJ, USA: IEEE Press,2006:1294-1305.
[5] 蒋道霞,刘凤玉.Ad Hoc网络中基于AODV的拥塞适应路由协议[J]. 南京理工大学学报(自然科学版),2009, 33(4):411-416.
[6] 方路平，刘世华，陈盼，等. NS-2网络模拟基础与应用
[M]. 北京：国防工业出版社，2008.