基于蚁群算法的移动自组网AODV路由协议动态优化研究

摘要：现有的AODV路由协议优化研究大多采用高延迟方式。本文对AODV路由协议进行动态优化，并采用蚁群算法对其进行优化。通过对路径规划中的避障规则及关键节点的敏感度进行修正，增加关键路径上的信息素含量，设定信息素水平分区，进而对通信传输最优路径的辨识与规划进行优化。利用蚁群算法，将每个结点的信息素辨识结果与蚁群算法相结合，求得最佳传播路径。试验表明，经过优化的路由通信数据传输平均时延维持在0.3—0.45秒之间，可以有效缓解移动自组网拥塞状况，并且路径节点的变化也逐渐平稳，总体工作效率与性能得到了显著提升。关键词：蚁群算法；移动自组网；AODV路由协议；动态优化移动无线自组网络是一种自组织、快速配置而且无需固定设施的动态网络。当移动自组网拓扑变化时，该算法可以迅速收敛，具有较低的计算量和较少的内存需求，并具有自修复和断开能力。此外，AODV还采用了结点序号的方法来解决移动自组网中的循环和无限计数问题。然而，当有效路由出现连接失效时，存在着对源节点进行修补或局部修补选择不当的问题，这将导致整个移动自组网性能的恶化。因此，本文拟研究一种基于移动自组网的AODV路由协议，采集数据，设置动态频率门限，并通过实验验证了该算法的优越性，提高了协议中分组的动态交付率[1]。一、蚁群算法在不断研究探讨中，学者们根据蚁群“信息素”的变化规律，将其划分为三种不同类型的蚁群算法。循环模型（cycle）：每只蚁群可释放的信息素总量是恒定的。密度模型（denseness）：当蚁群通过一条通路后，不管这条通路有多长，它们都会释放出同样的信息素。数量模型（quantity）：每只蚁群在同一条路径上释放的信息素浓度均相同。在这三种模式的持续试验和实际运用中，以其更具逻辑性和合理性而成为三种模式中的最佳模式。在接下来的研究中，很多学者通过引入各种算法和技术来对蚁群算法进行改进，主要有三种改进方法，分别是根据信息素的更新方式、基于路径选择逻辑的方法以及将其他算法与蚁群算法相结合，从而得到了各种改进算法。（一）基于信息素局部更新方式的改进蚁群算法在此基础上，采用局部弱化信息素作用，使未被走过的路径有一定几率被选中，从而避免陷入局部最优；提高了全局的搜索能力，提高了全局信息素养更新速度；在确定局部最优路径上，提高信息素的作用和集中程度，从而加强正反馈作用，提高收敛速度。（二）基于路径选择逻辑的改进蚁群算法采用一种基于遗传算法的算法，对蚁群算法进行了改进，使得蚁群算法能够在最短时间内得到全部的可行解；为了提高算法的收敛效率，同时保证路径的合理性，采用了一种基于遗传算法的蚁群算法。（三）基于算法融合的改进蚁群算法由于蚁群算法并行性好、分布性能好等特点，蚁群算法更容易与其他算法相结合，通过与各种精确算法和启发式算法的结合，形成一种新的算法，该算法可以将启发式算法的强大全局寻优能力与蚁群算法的正向反馈相结合，从而实现快速、准确求解。从算法层次上来说，它不但在算法层次上进行了持续演化，而且在实践中，它已经被广泛应用于从生产生活中提炼出来的各种问题，例如：车辆路径问题、图像处理问题、移动自组网路由问题、聚类问题等。二、AODV路由协议工作过程（一）AODV路由协议的路由发现在AODV协议中，如果有一方想要向目的方发送一条信息，那么只需在此基础上创建一条路径。为寻找到达目标点的路径，它广播一个路由请求信息RREQ到邻居节点，邻居节点又将消息转发给下一邻近结点，直至到达目标点或有一条有效路径到达目标点。同时，接收RREQ的中间节点按照RREQ协议中提供的信息，创建一条新路径——即“反向路由”。在此基础上，提出了一种基于RREQ协议的逆向路由机制[2]。在到达目标节点或者有一条有效路径的情况下，节点会向源节点发送一条路由应答消息，并在给定的方向上向源节点发送消息。在传送过程中，收到RREP的节点会生成一条新路径，并将其加入“正向路由”路由表。前向路由协议的目的节点是RREP的来源节点，下一节点将RREP发送给它的邻居节点。（二）AODV路由保持过程在路由形成之后，为了维持路由，各节点定期通过广播向邻居发送Hello消息，并将消息限制在发送节点与邻居节点之间。接收到Hello信息的节点将创建或者更新到发送节点的路由。在AODV中，无论何时，当一个节点接收到一个控制报文时，其含义都相当于一个显式Hello消息。因此，无论何时，节点都能保持有效的连通性。当一个节点发现一个路径不可用，就会在路由表中设定这个路径表的条目为无效，然后过一段时间再删除。当有效路径出现故障时，AODV协议提供了局部修补和源端重构两种方法。当断开链的前一节点处于MAX_REPAIR_TTL跳数范围内时，它将启动局部恢复；局部修复是上一节点启动路由发现，并通过对目标节点的序号添加1来对链路进行修复；启动该修补程序的节点会等待一个RREP循环以获取RREQ的访问权限。当断链的前一节点与目标节点之间的距离超过MAX_REPAIR_TTL时，首先对其进行恢复，即在中断链附近的前一节点发出一条RERR信息，源方在收到RERR消息后，发起一条路由查找，源方将其序列号加上1，然后向目标节点发送RREQ。（三）AODV路由协议路由修复过程的缺陷在图1中结点6和结点7之间的链路被切断之后，目的结点D将从源节点S迁移到新的结点，这个时候，结点6开始本地修补，使整个防火网络的性能下降。因此，使用源节点来进行修補，最为合理[3]。若在结点3与结点4之间断开连接，则如在图2中所示，目标结点D移至离源节点近数个跳点的结点3的位置；在这种情况下，如果在源节点上启动重构路由，则会使整个移动自组网的性能降低。这种情况下，还是使用局部节点来进行修复更加合理[4]。三、移动自组网AODV路由协议动态优化本文提出了一种新的基于蚁群算法的AODV路由协议。在进行数据通信时，由于所处环境的影响，其所处的环境是不确定的。在此基础上，提出了一种新的基于蚁群算法的AODV路由协议。以起始点为路由起点，决定了目标节点的具体位置，然后向目标节点出发，在过程中避免遇到任何的干扰和障碍，生成与当前环境相适应的动态路线。新路径的出现将增加数据通信的传输距离，从而增加了数据通信的传送时间。为在保证通信效率的前提下，实现最优路径，需重新制定避障准则，当通信路由遇到这种障碍时，无需再重新规划其他路径，使通信路径最短[5]。将通信环境中存在的多条路径结点和障碍物结点用蚁群算法表示，并将路径结点的信息集成为：X=（x1，x2…xn），以集合的形式表达的障碍节点Y=（y1，y2…yn），给出了最优的数据传送路线和避障路线，a代表蚁群，D描述了蚁群所走过的路线，并能求出理想的最佳路线与实际的最佳路线，并对蚁群在各种障碍下的避让状况进行了分析：在公式（1）中，q是蚁群对障碍的辨识参数，f是不同结点的辨识函数，u、v是不同结点的辨识结果，ε是辨识出的关键性资讯的个数，σ是参加辨识规划的结点资讯总数。在此基础上，提出了一种基于蚁群算法的蚁群算法。通过改进蚁群算法，实现了对避障策略的调整，并改善了对关键路线和优先障碍的选择能力。根据蚁群对每个结点的信息素识别能力，将蚁群划分为不同的等级，以增强蚁群对主要障碍物的吸引，从而增强蚁群对蚁群的吸引力。利用调高路由识别关键节点的灵敏度，縮小最优路径范围，提高其识别最优路径的能力；基于该方法，将关键节点的信息素添加到原始信息素中，并与已知信息素浓度进行融合，获得各节点间的浓度差[6]。（2）式中，Δk表示信息素浓度的差异，η表示信息素的分歧，a表示蚁群轨迹的错误范围，h表示整个路径的长度，Eij表示蚁群感受到的信息素总量。根据以上公式所算出的信息，对最优路径进行判定：公式（3）中，L表示得到的路线结果并且Lij是最初计划的参考路线。通过分析，得出了在给定的条件下，得到的运动轨迹是最优的，反之，如果不满足，则不是最优的。以此能够得到更加科学合理的路由传输路径，实现了移动路由协议动态的优化。四、实验研究利用Matlab作为试验软件，分析了火灾扑救过程中的节点识别率、节点之间的平均传输时间、传输率和丢包率。以NS2为例，在550m×550m的防火网络结构中，选取20个节点，以10m/s的最大运动速度10m/s进行仿真。传统路由通信中，当传送资料相同时，移动自组网速率会影响从起始结点至该区域中各结点的传送速率。在不同的传输路径上，传送节点之间的平均传送时间是恒定的，而路由传送的封包率与接收速率成反比，恒定的移动自组网速率下，增加了传送速率，则会使该地区的移动自组网环境变得更加拥挤，对移动自组网资源的占用也会增加，此外，它还会给网络中的节点带来额外的负荷，从而降低了网络的传输速度和效率[7]。蚁群算法是一种最优路径规划方法，其平均延迟为0.3—0.45秒，而常规算法的延迟大于0.7秒。这是由于本论文所提出的方法可以在多个任务之间实现最优的传送线，减少移动自组网拥塞，减少节点负荷，加快分组的传送速率。在相同的移动自组网环境中，监控并分析了在不同传输速率情况下节点的报文接收率。随着数据传输速率的提升和移动自组网拥塞的加剧，传统通信模式下路由拓扑结构的开销增大，对移动自组网拓扑结构的需求也随之增大，从而加剧了通信系统的不稳定性，极大地提升了通信的失败率。本文提出一种新的基于蚁群算法的无线传感器移动自组网传输路径优化