基于拥塞预警与分流传输的AOMDV协议优化

　　1 引 言
　　研究者们早期提出了多种经典的移动Ad hoc网络路由协议，可分为表驱动路由协议﹑按需路由协议以及混合式路由协议。其中属于按需路由协议的AODV[1]协议，具有开销适中、容易实现、能快速响应拓扑结构变化等优点，应用十分广泛。但是AODV协议是一种单路径的协议，每当路径发生断裂时就需要发起新的路由发现过程，从而大量增加了路由开销和通信时延。针对这个问题，研究者对AODV协议进行了多路径扩展，提出了多种多路径协议如AOMDV[2]协议，AODV-BR[3]协议等。其中AOMDV协议是一种比较成熟的由AODV协议扩展而来的多路径协议，与AODV协议相比，AOMDV协议充分利用AODV协议中已有的路由信息，通过一次路由发现过程在有通信需求却没有可用连接的两个节点之间建立起多条无环并且路径不相交的路径，当主路径发生断裂时，可以立即启用备用路径继续转发数据，从而避免了发起新的路由发现过程，因此节省了大量的路由开销，并且有效地减少了通信时延。然而，AOMDV协议未考虑网络的负载情况，只使用主路径传输数据，只有当主路径断裂时才会使用备用路径，这样将导致在主路径承担过多数据传输业务的同时其他多条备用路径却被闲置，网络的负载将处于失衡的状态，在网络负载较高时将容易导致局部拥塞的发生，网络性能将因此恶化。
　　2 相关研究
　　近年来，关于如何对AOMDV协议进行负载均衡方面的优化，研究者们提出了不少方案：AOMDV+SBA[4]协议和AOMDV-LB[5]协议通过避免负载高的节点参与路由发现过程从而使这些节点不会出现在最终建立的传输路径上。AOMDV-C[6]协议则通过延时转发路由控制分组使负载较低的路径最先被建立，然后作为主路径进行数据传输，同样使传输路径避开了负载高的节点。前面提及的这些协议都是基于AOMDV协议的路由发现过程寻找网络中负载较低的路径并将其作为主路径进行数据传输，其余建立的路径仍作为备用路径并且只有当主路径断裂时才会使用这些备用路径，这样还是会和AOMDV协议一样导致主路径承担过多的数据传输业务，此外，备用路径可能因长期被闲置而导致生存时间过期而被删除，从而这些路径的有效性将不能得到很好的维护。LB-AOMDV[7]协议和QoS-AOMDV[8]协议按照不同的分配机制将数据传输业务分配给基于AOMDV协议的路由发现过程所建立的多条路径，前者根据路径负载的情况进行分配，负载较低的路径将承担较多的数据传输业务，后者则轮流使用这些路径进行数据传输，使每条路径的吞吐量保持一致。两者都避免了数据流量过于集中在主路径上，同时避免了备用路径因长期未被使用而被删除，维护了这些路径的有效性。
　　以上所列出的AOMDV负载均衡改进协议都在一定程度上实现了网络负载的均衡。然而它们对于节点或者路径的负载情况的衡量都是基于在路由发现过程中所收集的各种信息，然而移动Ad hoc网络的拓扑结构是动态变化的，网络的负载情况也将随之不断改变，因此，在路由发现过程中所得到的负载信息将不一定能适应经过一段时间动态变化后的网络。
　　3 基于分流传输机制和拥塞预警的LBAOMDV
　　协议
　　3.1 LBAOMDV协议的概述
　　针对上述提及的AOMDV协议及其负载均衡改进协议中存在的不足，本文设计了一种基于节点负载的拥塞预警机制和一种基于路径使用次数、路径长度以及路径状态的分流传输机制，并以此对AOMDV协议进行了优化，优化后的协议LBAOMDV将利用AOMDV协议的路由发现机制通过一次路由发现的过程在有通信需求却没有可用连接的两个节点之间建立起最多3条无环且路径不相交的路径，然后利用分流传输机制将数据流量分配到各条路径上。当网络中的某个节点进入高负载状态的时候，利用拥塞预警机制通知网络中的其他节点，将通过这个高负载节点的路径暂时地标记为拥塞路径，使部分原来在拥塞路径上进行的数据流量暂时地转移到其他未拥塞的路径上，经过一段时间后，再将路径的拥塞状态恢复为正常状态。
　　3.2 拥塞预警机制
　　移动Ad hoc网络中的节点会经常性地随机移动，这将导致网络的拓扑结构不断发生变化，网络中各节点或者路径的负载情况也会随之发生改变，这样一来，通过路由发现过程所得到负载较低的路径不能一直确保其负载情况一直良好，例如路径中的某些节点可能因为网络拓扑的变化而成为局部网络数据传输的中心节点，其负载可能变得很高，此时，继续在这些路径上进行数据传输很可能会导致拥塞，数据分组将因缓存溢出而被丢失。当面对这种情况时就需要采取及时有效的拥塞预警措施以减少或停止在这些路径上传输数据，同时因为网络拓扑的不断变化，负载高的节点不一定会一直处于高负载状态，所以，可以将通过高负载节点的路径暂时地标记为拥塞路径，在经过一段时间后，将其恢复为正常路径，这样便能更好的适应网络的动态变化。综上所述，本文提出一种基于节点负载的拥塞预警机制。
　　目前，有多种参数可用来衡量节点的负载，其中缓存队列的饱和度作为节点当前流量负载的具体体现，能直接反应节点当前的负载程度，其获取简单且无需额外开销，被多种负载均衡改进协议所使用。节点i的缓存队列饱和度Ci定义如下：
　　Ci=QiQmax（1）
　　其中Qi表示节点i当前的缓存队列的长度，而Qmax则表示节点i缓存队列长度的最大值。因为节点缓存队列长度的监测获得的是一个瞬时值，只能反映节点这个瞬间的负载情况，不能体现节点负载在未来一段时间内的变化趋势，直接用缓存队列长度的瞬时值判断节点负载情况将不够准确，所以节点拥塞判断的度量需在缓存队列饱和度的基础上考虑节点负载的变化趋势。本文采用了一个定时器，每隔一段时间INTERVAL检测缓存队列的长度，Qnew表示最新监测到的缓存队列长度，Qold表示INTERVAL前监测到的缓存队列长度，定义
　　Qadd=Qnew-Qold （2）
　　Qadd表示INTERVAL时间内节点缓存队列的变化情况，能反映节点负载在近期的变化趋势。最终将节点i负载判断的度量Mi定义为：
　　Mi=Qi+QaddQmax （3）
　　当节点的M值大于预先设定的拥塞阈值时，则认为该节点已经处于拥塞状态，通过该节点的路径则被认为是拥塞路径，节点在发送数据的时候应当尽量避免使用拥塞路径。
　　基于节点负载的拥塞预警机制如下所述：节点在每次发送数据分组前，根据式（3）计算节点当前的M值并将其与设定的 拥塞阈值相比较，判断自身的负载情况。如果节点进入了拥塞状态，则广播一个携带了拥塞信息的HELLO分组通知所有邻居节点此节点已经进入拥塞状态，所有收到此HELLO分组的邻居节点将路由表中所有经过拥塞节点的路径都暂时标记为拥塞路径。如果去往某个目的节点的所有路径都已经被标记为拥塞路径，则节点需广播路由拥塞分组通知其他邻居节点经过本节点去往目的节点的所有路径均为拥塞路径。邻居节点收到路由拥塞分组时暂时标记相应的路径进入拥塞状态。如果节点因收到路由拥塞分组而导致其中某些路由表项的全部路径进入拥塞状态，节点同样需要再次形成新的路由拥塞分组并将其广播转发。最终，网络中的路径都将被暂时划分为拥塞路径和正常路径，有多条路径可供数据传输的节点将拥塞路径上的数据流量转移到未拥塞的路径上。本文将拥塞标记的持续时间设为T，当拥塞标记的持续时间超过T后，将路径恢复为正常路径。
　　3.3 分流传输机制
　　将数据传输业务集中在一条路径上，容易导致网络局部的拥塞，而将数据传输业务按照一定的分配机制分配到多条路径上则一方面有利于网络负载的均衡，另一方面能维护所建立的多条路径的有效性。本文在综合考虑负载均衡以及传输效率的基础上，提出一种基于路径使用次数、路径长度以及路径状态的分流传输机制。本文定义在路径j上进行数据传输的代价为Cj。
　　Cj=Nj×Lj（4）
　　其中Nj表示在路径j上进行数据传输的次数，而Lj表示路径j的长度，即在路径j上进行数据传输所经过的跳数。式（4）表明路径使用次数越多，路径长度越长，则使用该路径进行数据传输的代价就越大。当节点有多条路径可供数据传输时，根据式（4）计算每条路径的数据传输代价，然后选择其中数据传输代价最小的路径进行传输，在传输完一个数据分组后，便将路径的使用次数增加1。为了避免使用拥塞路径进行数据传输，被标记为拥塞的路径将不会参加数据传输代价的比较。而当所有路径都为拥塞路径时，将导致因为没有路径参加数据传输代价的比较而找不到代价最小的路径，此时重新根据式（4）计算比较所有路径的数据传输代价，最后选择其中最小的路径进行数据传输。
　4 仿真实验及分析
　　本文通过NS2.34实现了LBAOMDV协议并对其进行了仿真实验，比较其和AOMDV协议的性能。实验将50个节点随机分布在800 m×800 m的场景区域中，节点的移动采用Random Way Point[9]模型，节点的最大移动速度为10 m/s，节点的发射半径为250 m，缓存队列最大长度设为50，信源采用固定比特率，每个分组长度为512 B，每秒发送2个分组，同时启动40个数据通信连接，拥塞阈值设置为0.8，路径的拥塞标记持续时间T设置为6 s。将节点停留时间分别设置为0 s、20 s、40 s、60 s、80 s、100 s六种不同的情况进行仿真，每种仿真的情况进行了5次实验，每次实验的时间为200 s，最终结果取5次实验的平均值。
　　仿真实验将从分组投递率，平均端到端时延，归一化路由开销三个方面来比较LBAOMDV和AOMDV的性能：
　　分组投递率定义为仿真期间成功到达目的节点的分组数与网络中节点总共发送的数据分组数的比值。
　　平均端到端时延定义为网络中所有分组被接收的时间与分组被发送的时间之差的平均值。
　　归一化路由开销定义为网络中所有节点发送以及转发的路由控制分组的总和与节点接收到的数据分组的总和之比。
　　图1描述了LBAOMDV协议和AOMDV协议的分组投递率在不同停留时间情况下的变化情况。LBAOMDV协议因为使用了分流传输机制在多条路径上同时传输数据，使数据流量没有过于集中于一条路径上，维护了多条路径，降低了由重启路由发现过程所导致的数据分组被丢弃的概率。同时由于使用了拥塞预警机制，减少了在拥塞路径上的数据流量，降低了因拥塞而使数据分组被丢弃的概率，所以在分组投递率上要好于AOMDV协议。
　　图2描述了LBAOMDV协议和AOMDV协议的平均端到端时延在不同停留时间情况下的变化情况。LBAOMDV协议因采用了分流传输和拥塞预警机制，减少了在拥塞路径上的数据流量，从而减少了数据分组在缓存队列中的等待时间，同时维护了多条路径，降低了因路径断裂而引起重启路由发现的概率，进一步减少了通信时延，所以，其平均延时要小于AOMDV协议。
　　图3描述了LBAOMDV协议和AOMDV协议的归一化路由开销在不同停留时间情况下的变化情况。LBAOMDV协议因使用了多条路径同时传输数据，维护了多条路径的有效性，从而使重启路由发现的概率要小于AOMDV协议，所以，其路由开销要比AOMDV协议少。
　　5 结束语
　　本文针对AOMDV协议及其负载均衡改进协议中存在的问题提出了基于节点负载的拥塞预警机制和基于路径使用次数、路径长度以及路径状态的分流传输机制，并利用这两种机制对AOMDV协议进行了优化。优化后的协议LBAOMDV通过分流传输机制在使用AOMDV路由发现机制所建立的多条无环且路径不相交的路径上同时传输数据，这样即均衡了网络负载，又维护了多条路径，提高了数据传输路径的稳定性。在此基础上利用基于节点负载的拥塞预警机制标记拥塞路径，减少了在拥塞路径上的数据流量，进一步均衡了网络的负载并降低了拥塞发生的概率。仿真结果表明，与AOMDV协议相比，LBAOMDV协议在网络高负载情况下提高了分组投递率，减少了通信时延和路由开销，提升了整个网络的性能。然而拥塞阈值与拥塞标记持续时间的设定问题有待更进一步的研究。
　　参考文献
　　[1] PERKINS C E，BELDING-ROYER 3561 Ad-hoc On-Demand Distane Vector（AODV）routing[S].2003.
　　.Proceedings of the International Conference for Network Protocols，2001：14-23.
　　.Proceedings of the IEEE WCNC 2000，2000：1311-1316.
　　. Proceedings of the 2010 IEEE 10th International Conference on Computer and Information Technology（ICT），2010：305-312.
　　[5] 刘成，曾格平.基于AOMDV的自适应负载均衡研究[J].广东通信技术 ，2012（10）：28-31.
　　[6] XIA LI，SONG ZHI，SU XIN， et -hoc multipath routing protocol based on load balance and location information[C].Proceedings of WCSP 2009，2009：1-4.
　　. Proceedings of the 2010 International Conference on Computer Engineering and Systems（ICCES），2010：67-72.
　　.Proceedings of the 2011 International Conference on Internet Computing and Information Services（ICICIS），2011：261-264.