基于蚁群算法优化的路由频率动态择径的研究

高月仁，吴 涛，高 峡

(1.唐山曹妃甸联城科技股份有限公司，河北 唐山 063200； 2.华北理工大学，河北 唐山 063200；3.唐山曹妃甸发展投资集团有限公司，河北 唐山 063200)

0 引 言

目前的科技水平正处于创新与发展阶段，随着技术的不断优化、创新，互联网面向社会各个领域大面积普及，社会中的生产生活信息，通过网络接收传送，这其中就离不开路由的支持。路由是通过相互连接的网络，将信息从原地址发送到目的地的活动，通俗来说就是路由将打包的网络信息转送给信息搜索人，其中信息在路由的传送下，需要跨过一些节点后到达目标地，而路由频率动态择径是指在复杂网络下通过路由的移动频率选择一个最优的路由路径[1-3]。

为了让信息可以更快速地传送到搜索人的手中，一些学者提出了路由频率动态择径方法，该方法根据搜索人的搜索目标、搜索指令以及信息源地和接收地地址，选取一个路径用来传递搜索信息。但该路径在反复测试中，传输数据的效果并没有达到预期。文献[4]提出了一种能量感知的ZigBee树型路由EZTR(Energy-aware ZigBee Tree Routing)算法，该算法利用每个节点感知的地址信息，按照ZigBee网络树型结构计算下一跳邻居节点到目的节点之间的跳数，可避免网络的环路效应，通过引入认知概念，在跳数集合中选出最短路径以降低跳数。在ZigBee网络节点能量的感知过程中，当所选路径存在低能量节点时，及时启用备用节点，从而避免节点因能量过度消耗成为失效节点；文献[5]提出了一种基于可靠路径剩余生存期估计的MANET路由发现算法，该算法充分考虑相邻链路剩余生存期相关性，建立优化的多跳路径RPL统计特性分析，提供了更可靠的路由稳定性评估，通过仿真分别与忽略链路RLL相关性的源路由协议及已有稳定性路由协议进行对比；文献[6]提出了基于E-router的能源互联网分层分区优化策略，底层基于E-router的微网经济调度以发电成本最低为目标实行分布式局部优化，上层路由交易中心采用文中所提出的基于图论的电力库交易优化策略，通过E-router选取没有阻塞的最低网损路径进行电量传输，实现效益最大化和阻塞管理，最后，通过仿真验证了所提优化策略和模型的有效性。但是以上3种方法的避障规则存在缺失，导致得到的路由传输路径不是最优。

文献[7]提出了一种基于信任评估的Ad Hoc安全路由协议TEAR，该协议在节点行为信任评估方案的基础上，通过使用链路信任值和路径信任值表示节点和路径的可信度，同时，在链路信任值计算时，引入了基于公共邻居节点的间接信任评估方法和可变时间窗机制，保证了信任值计算的准确性和实效性，实现了安全路径的快速选择；文献[8]提出了基于S3变换的TriBA-Net最短路径路由机制，方法中所用到的文字1、3、2的集合与群论中的三文字集S3群具有相同的含义，其次，设计了一种相隔节点间的通信模型，根据通信路径端点的可能状态，将通信划分为6种宏观数据流动模式，最后，利用S3群的循环置换特性对通信模型进行简化，在XC6VLX550TL芯片上完成了SPR4T路由器的设计实现。但是以上2种方法的最短择径时间较长。

文献[9]提出了一种基于最优跳数的非均匀分簇算法，首先推导了使节点直线传输数据到基站总能耗最小时的最优跳数，得到路由消耗最小的理想路径，然后，根据该理想路径形成的热区引入入簇半径调整簇规模，以平衡节点出任簇头时的簇内和路由中继能耗，最后，在保证能耗均衡的前提下，选择邻居候选簇头中较符合理想路径的节点作为下一跳中继节点，进一步降低能耗速率；文献[10]在分析传统BGP路由选路机制缺陷的基础上，采用SDN控制技术，提出了一种支持传统路由设备和OpenFlow设备的路由反射优化方法，并给出了具体实现算法及部署方案，典型应用场景的测试结果表明，国际访问时延平均缩短了30%，验证了方法的有效性。但是以上2种方法的择径结果与实际最优择径结果相差较大。

针对上述方法存在的问题，本文提出基于蚁群算法优化能力的路由频率动态择径方法。蚁群算法是一个用来寻找最优路径的概率型算法。此次提出的择径方法，利用蚁群算法获取路由频率动态最优传输路径，实现对信息的瞬间传输。该择径方法的提出不仅弥补了常规方法的现有缺陷，同时将择径结果计算到最优，实现海量信息的高速传输，为互联网网络通信能力的发展，提供更加完善的信息传输路径。

1 基于蚁群算法优化的路由频率动态择径方法

1.1 建立目标环境设置关键信息选取规则

基于蚁群算法的择径方法，需要在建立目标环境的基础上，设置关键信息选取规则。利用栅格法，将目标环境设置为大小相同的单元网格，便于选取关键信息、规避障碍数据[11-12]。建立的目标环境需要将路由可识别的路径信息转换成可识别的数字信息，采用坐标法和序号法标记网络环境。序号法将栅格环境中的每个栅格，按照序号1-2的顺序，依次累加直到栅格的最后一个；坐标法则将目标环境转化为二维图像，以坐标的方式记录每一栅格的节点位置[13]。预期建立的目标环境与设置的关键信息选取规则如图1所示。

图1 信息选取规则

假设栅格环境规格为x×y，则存在二维矩阵B(x,y)，此时序号法标记的第l个栅格的位置坐标为(xl,yl)，则横纵坐标的取值为：

(1)

式中：l表示栅格数量；xl、yl表示l位置处的栅格横坐标与纵坐标；b表示单独栅格的边长；f(*)表示纵坐标运动方向的控制函数；g(*)表示横坐标运动方向的跟踪函数[14]。已知图1中的信息选取规则较多，因此利用蚁群算法设置路由对关键信息的选取规则为：

(2)

1.2 设置路由频率动态移动规则

利用关键信息选取规则确定路由大致传输方向后，设置路由频率动态移动规则，确保路由可以根据搜索信息，及时更新传输方向。蚁群算法控制下，路由在初期数据传输中，由于路径上的信息量相差较小，因此可能会导致蚂蚁在方向转变、路径转移的过程中陷入盲目选择的情况，导致消耗大量时间和资源，从而破坏路由的移动频率[18-19]，该范围如图2所示。

图2 盲目移动范围示意图

图2中点A表示蚂蚁所在位置；r表示常规状态下的蚂蚁活动半径；r1表示空间内蚂蚁可移动范围内的有效半径；r′=r-r1，表示蚂蚁盲目活动的超出范围半径。因此在蚂蚁的转移状态中添加引导因子，该因子可伴随目标点和迭代次数的改变而产生动态变化。假设某一节点的引导因子为：

(3)

式中：μ表示引导因子量；m表示蚂蚁总数；ma表示当前蚂蚁a的数量；Mmax表示综合迭代次数；M0表示当前迭代次数；d1表示当前节点到目标地的距离；d2表示当前节点到下一节点的距离[20]。假设当前节点为i，与之相邻的下一节点为j，则从节点i到节点j引入引导因子后的路由移动频率为：

(4)

式中：pij表示节点i到节点j之间的路由移动频率；κ表示移动控制参数；σ表示因素挥发最优值；x表示最大移动频率；ω表示允许存在的移动误差。根据上述公式，实现对路由移动频率的规则设置。

1.3 设置路由避障规则

由于路由在输送数据的途中，会遇见由各种干扰数据组成的障碍节点，因此需要基于蚁群算法，设置路由避障规则。已知障碍节点与目标位置示意图如图3所示。

图3 路由避障示意图

根据图3可知，当路由从出发点出发后，遇见障碍时需要绕行，而绕行则需要重新规划路径。同时路由若绕开多个障碍，可能会延长数据传输线路，增加数据传输时间。因此需要设置避障规则，在路由传送过程中，选择障碍少且最近的线路作为传输路径。利用蚁群算法描述该避障问题，假设集合X=(x1,x2,…,xn)表示路由传送空间中的n个节点，集合Y=(y1,y2,…,yn)表示空间内存在的n个障碍数据。将蚂蚁a所经过的节点记为Da，设蚂蚁的个数为a=1,2,…,m个，在寻找最优路径的过程中，默认蚂蚁的搜索方向是根据关键信息规则而选取的，以设置的移动规则为依据，计算蚂蚁对障碍数据的识别能力：

(5)

式中：q表示障碍识别参数；c(*)表示识别函数；ux、vx表示对蚂蚁经过节点的识别结果；uy、vy表示对障碍的识别结果；ε表示关键信息量；σ表示基准参考值。按照上述识别结果设置避障规则，该规则包括局部避障规则和全局避障规则。当蚂蚁完成一次路径搜索后，假设搜索初始时间为t0，搜索消耗的时间为Δt，则局部避障规则为：

(6)

式中：λid表示路由在i节点与d障碍之间的局部避障规则；γ⊂[0,1]，表示局部关键信息衰减系数；n表示信息数量；o表示路线与障碍之间的互斥参量。局部避障的同时要考虑全局避障，避免由于躲避局部障碍导致全局绕远的情况，因此当蚂蚁绕过局部障碍后，需要统筹全局障碍，重新执行最优路径。全局避障规则为：

λ′(M+1)=(1-γ)λ′(M)+γλid(t0+Δt)

(7)

式中：λ′表示全局避障规则；M表示调整次数。至此实现对路由传输路径的避障规则设置，保证路由在移动的过程中，遇见障碍时迅速做出选择，并以此挑选可行线路。

1.4 增强关键信息素选取最优路径

可行路径中，每一条路径具有相同信息素的初始值，这些数据对蚂蚁的吸引程度十分相似，此时虽有可行的路径，但无法判断出其中的最优解，因此需要扩散蚂蚁可感知的关键数据信息素，让蚂蚁找出可行线路中的最优路径，预期的蚂蚁最优路径选择结果如图4所示。

图4 预期的蚂蚁最优路径选择示意图

根据最优路径选择的预期设定，加强路由对关键信息的感知能力，利用蚁群算法对互联网中产生的初始信息素进行浓度叠加，叠加后的信息素为：

(8)

式中：Q表示信息素的初始数据总量；L表示2个传输节点之间的欧氏距离；当L值越小时，叠加后的信息素Eij(0)的取值就越大，此时的蚂蚁会控制路由向该信息素的节点方向移动。根据上式的Eij(0)值计算信息素差异值：

(9)

(10)

式中：τ表示信息素补偿值；Lij表示起始节点的参考路径。当计算结果为0时，可知所选的路径不是最优，直至计算得出L′最优路径，得到路由频率动态择径的最优选择。

2 仿真实验分析

2.1 实验目的

为了验证本文所提基于蚁群算法优化的路由频率动态择径方法的有效性，对比本文所提出择径方法与常规择径方法之间的现存差异，得出实验测试结论。

2.2 实验环境设置

此次实验选择的操作系统为Windows 7专业版；硬件使用环境为HP-PC Intel(R) Core(TM) i5-6500 CPU @3.60 GHz；开发语言为C#；开发工具为Visual Studio 2017；数据库为SQL Server。将上述工具装入实验检测计算机中，设置实验测试环境参数，设置页面如图5所示。

图5 参数配置界面

利用上述界面设计路由动态传输空间。设置环境参数如表1所示。

1.3 统计学分析 采用SPSS 19.0软件进行处理，计量资料以表示，先做方差齐性检验，若方差齐性，则采用SNK法比较组间差异，不服从齐性分配采用friedman M检验，相关性分析采用person线性检验，P<0.05为差异有统计学意义。

此次实验测试选取的路由器型号为Tenda-AC23；测试选用的计算机型号为GFL-5640，该计算机包含16 GB显存容量，八核心CPU，8 GB运行内存，符合此次实验操作要求。将计算机、路由器与无线网络连接，图6为此次实验操作环境。

表1 实验参数

图6 实验测试环境

导入实验测试算法与数据，运行测试系统，开始实验检测。

2.3 实验指标

本文以路由频率动态的最优路径、择径时间、择径误差为实验指标，采用文献[4]方法、文献[5]方法、文献[6]方法、文献[7]方法、文献[8]方法、文献[9]方法、文献[10]方法和本文方法进行对比实验。

1)最优路径。寻找到最简单、最快、最省事的路径，常规的路由频率动态择径方法设置的避障规则存在缺失，导致得到的路由传输路径不是最优，由此，采用本文方法和文献[4]方法、文献[5]方法、文献[6]方法进行对比分析。

2)择径时间。在路由频率动态择径的过程中会产生大量的时间，能够对择径效率产生影响，择径时间越短，则择径效率越高。采用本文方法与文献[8]方法、文献[9]方法、文献[10]方法，对路由频率动态择径时间进行对比。

3)择径误差。路由频率动态择径结果与实际最优择径结果的拟合度越高，择径误差越小，择径结果越准确。采用本文方法与文献[5]方法、文献[6]方法、文献[7]方法进行对比分析。

2.4 数据集

实验中所使用的数据来源于Koblenz网络数据库(网址：http://konect.uni-koblenz.de/)，共采集数据5000个，进行10组实验，每次使用500个数据。

2.5 实验结果分析

设置若干个干扰数据作为障碍选项，分别利用本文方法和文献[4]方法、文献[5]方法、文献[6]方法，选择路由传输数据的最优路径，图7为此次实验测试结果。

(a) 本文方法的实验结果

(b) 文献[4]方法的实验结果

(c) 文献[5]方法的实验结果

(d) 文献[6]方法的实验结果图7 实验测试结果

为了验证本文方法的有效性，对本文方法、文献[8]方法、文献[9]方法和文献[10]方法的路由频率动态择径时间进行对比，对比结果如图8所示。

图8 择径时间对比

根据图8可知，本文方法的路由频率动态择径时间保持在10～25 s之间，是对比实验中择径时间最短的，说明本文方法能够在最短时间内选择出最优路径。

为了进一步验证本文方法的有效性，将本文方法与文献[5]方法、文献[6]方法、文献[7]方法的路由频率动态择径结果与实际最优择径结果进行对比，对比结果如图9所示。

图9 择径结果误差对比

根据图9可知，本文方法的路由频率动态择径结果与实际最优择径结果的拟合度为99.9%，而文献[5]方法、文献[6]方法、文献[7]方法的路由频率动态择径结果与实际最优择径结果的误差较大。

3 结束语

本文提出的基于蚁群算法的路由频率动态择径方法，以常规方法的现有缺陷为研究切入要点，首先通过建立目标环境设置关键信息选取规则，确定路由大致传输方向，然后设置路由频率动态移动规则和路由避障规则，最后扩散蚂蚁可感知的关键数据信息素，促使得到的传输路径为最优解，完成最优路径的选取。实验结果表明，本文方法的路由频率动态择径为最优，缩短了择径时间。