高大利

(1.泉州师范学院 数学与计算机科学学院，福建泉州 362000；2.福建省大数据管理新技术与知识工程重点实验室，福建泉州 362000；3.智能计算与信息处理福建省高等学校重点实验室，福建泉州 362000)

网络实际上可以抽象为一个具有权值的有向图，它由许多节点、边以及其方向构成，因此网络路由可以根据实际问题的情况来给这些弧或节点赋予一个权值来进行建模[1]。路由协议运行在网络路由器或三层交换机之上，帮助路由器建立路由表，用来确定到达路径，起到地图导航，负责找路的作用。路由协议作为TCP/IP协议族中重要成员之一，其选路过程实现的好坏会影响整个Internet网络的效率[2]。

一般地，路由协议常用的度量包括[2]：1)路径长度，它是最基本，使用频率最高的路由度量，通常将其称为跳数，即所走路径上的路由器数目大小；2)可靠性，指的是网络相互链接的可依靠性，即其在失效的时候，能否比其他的链接更快地修复；3)时延，一个报文或分组从一个网络的发送端传送到另一个目的端所经历的时间，其中包含许多的因素，例如：带宽、所经网络链接的拥塞情况、物理距离等，时延实际上是多个因数的混合，是一个较为有效和使用频率较高的度量；4)带宽，在模拟信号系统又叫频宽，是指在固定的时间链路中可传输的流通容量，亦即在传输管道中可以传递数据的能力；5)负载，指的是网络资源的忙碌程度，其中可能存在很多方面的计算问题；6)通信开销，在路由优化的问题中，通信开销实际上是指在该网络中，在规定的多个约束条件中找出从源节点到目的节点的最小开销路径，即最佳路径(即加权图上的最优路径)。

蚁群算法作为一种启发式的智能优化算法，从1992年被Dorigo提出来后，许多的学者便开始对其的改进及应用进行了研究[3]。如把该算法应用于TSP问题[4]、无人汽车路径规划问题[5]、机器人问题[6]、资源配置问题[7]和网络路由问题[8]等组合优化问题。蚁群算法属于一种模仿生物进化的算法，它的想法来源于蚂蚁在觅食的行为[9]。蚁群算法具有贪婪启发式的搜索特征，能够在搜索过程的早期就找到一个可以被人们所接受的问题求解[10]。经过一系列的改进，蚁群算法相比较于原始的算法模型，已经得到了更多的改善与拓展[11]。鉴于蚁群算法在路由选路的以上优势和特点，将自适应蚁群算法，应用于网络的路由协议中。即根据蚁群算法的参数自适应调整将路由协议中的多个因素(如跳数、时延和带宽等其它因素)和不同的网络环境来选择一个路由的优化最佳路径。

1 算法思想

一般地，把实际网络中的路由选路问题抽象成最优路径的问题的模型，然后通过蚁群算法来求出相对开销最小的最优路径。建模过程如下：

针对网络模型G(V,E)，其中V表示节点集，E表示边集。把网络中的搜寻路径相关信息的任务用一种控制报文(即蚂蚁)来实现，并分为两类蚂蚁，分别为向前的蚂蚁(从源到目的)和向后的蚂蚁(从目的返回源)。蚂蚁负责搜集从源节点到目的节点的路径信息(即时延、跳数等)，蚂蚁则根据蚂蚁所收集到的信息进行修改路径中节点的路由相关信息[12]。在文中，将问题简化为路径中所经过的节点数表示为跳数，而路径中的边的赋权则表示为时延、带宽等因素。因此本文将主要围绕跳数和时延两个约束条件来进行最优路径的选择，并将网络中路由表替换为信息素表以表示信息素的强度。

开始阶段，将网络每一条边赋予均匀的信息素浓度，通过蚂蚁在搜寻路径的过程来不断更新边的信息素浓度，每个蚂蚁所携带的信息素量都相同。首先将一组数量的蚂蚁放置源节点从源节点出发寻径至目的节点，按照之前介绍的方法进行移动，在寻径的过程中蚂蚁能够记住所走路径的信息和所经过节点的信息，直到最后走到目的节点为止。当蚂蚁走到目的节点之后，会根据搜集到的路径信息，来更新所经路径的路由表(即信息素表)，改变路径上的信息素浓度，再通过不断地迭代循环计算，最后收敛得到最优路径。

根据算法思想，蚂蚁需要拥有以下的属性及特性：1)蚂蚁拥有相同的信息素量，并且每只蚂蚁都能够更新路径中的信息素浓度，这是蚂蚁之间进行信息交换的手段；2)蚂蚁需要拥有记忆功能，能够记住所搜集的路径信息(即跳数和时延)和已经遍历过的节点，保证一个节点一只蚂蚁只会遍历一次，防止蚂蚁多次访问同一节点；3)蚂蚁在网络中的遍历必须拥有一个或者多个终止条件，本文中的蚂蚁的终止条件为到达目的节点；4)蚂蚁需要拥有发现节点阻塞的功能，蚂蚁能够及时发现存在于路径中的阻塞节点，并且需要及时更新存在阻塞节点的路径信息；5)蚂蚁必须要依照算法的节点转移概率规则来决定下一跳的节点。

2 算法实现

基于算法思想，算法的具体计算流程如图1。

图1 算法流程图

2.1 状态初始化

首先需要对网络中的所有节点(节点数量)和每条进行状态初始化，每个节点都分配一个信息素表，并初始化每条弧的权值以及信息素浓度，算法则将信息素浓度的初始值设为1。同时还需要设置好蚂蚁的数量以及每只蚂蚁所携带的信息素量并将这组蚂蚁放置源节点出发。再来还需要设定算法的最大迭代次数、信息素重要程度因子、启发函数重要程度因子、信息素挥发因子，跳数重要程度因子、时延程度因子、跳数影响信息素程度因子、时延重要影响信息素程度因子，为每个蚂蚁创建一个禁忌表，用于记录访问过的节点。

2.2 逐个蚂蚁的路径选择

1)每只蚂蚁在寻径的过程中都会记录下该路径的路由信息和时延。算法中的第k只蚂蚁在I节点选择的下一跳j节点的规则如下式(1)。

(1)

其中τij为边(i，j)上的信息素浓度；ηij=1/dij为节点i转移到节点j的启发因子，需要通过启发式公式计算得到；为蚂蚁ak下一步被允许访问的节点集合，然后通过轮盘赌法实现到对下一个节点的选择并跳跃。

2)第k只蚂蚁在概率转移的规则下完成了对下一节点的选择和跳跃后，就会将节点j加入到蚂蚁的路径信息表中，当再选择下一条的节点时节点j就会被写进禁忌表中，若周围连接的所有节点都在禁忌表中时(即ak∈φ)，该蚂蚁就陷入了死胡同，这种情况就把蚂蚁收集的信息清空，重新初始化状态放到源节点重新出发寻径。

3)当蚂蚁到达目的节点时，蚂蚁将会把搜集到的路径信息(即跳数和时延)放入到路径表route、时延表Timed和跳数表hop当中，然后终止该蚂蚁的生命周期。

2.3 寻找一代蚂蚁的最佳路径

当一代的蚂蚁全部寻径结束后，需要通过对每只蚂蚁搜集到的路径信息进行分析，找出在跳数和时延两个约束条件下最优的路径。在这个过程中，算法设置了跳数重要程度因子ω1、时延程度因子ω2这两个参素来影响对于这代蚂蚁中最优路径的选择。定义第k只蚂蚁的路径开销值Gk，它的计算公式如式(2)。

Gk=hopk*ω1+Timedk*ω2 ，

(2)

hopk为第k只蚂蚁所走路径的跳数，Timedk为第k只蚂蚁所走路径的时延总和，开销值Gk越小，说第k只蚂蚁所走路径的开销越小。因此算法通过对开销值的比对筛选出这一代蚂蚁的最优路径。然后与上一代蚂蚁的最优路径进行对比，若这一代的蚂蚁选出的最优路径开销比上一代蚂蚁要大，则舍弃这代蚂蚁的最优路径，将上一代蚂蚁的最优路径保存为这一代蚂蚁的最优路径。

2.4 信息素的更新

当一只蚂蚁完成一次寻径，到达目的节点后，算法对于该路径上边的信息素浓度更新方式采取了对蚁量系统的改进，蚁量系统的具体规则如式(3)。

(3)

则在算法中每条边上的信息素浓度更新的具体公式如式(4)。

τij=(1-ρ)τij+∑K=1mΔτijk(t),

(4)

其中Δτijk(t)的表示第k只蚂蚁在这条边上信息素浓度的释放，Δτijk(t)的具体计算公式如式(5)。

Δτijk(t)=(Q/hop(k))r1+(Q/Timed(k))r2,

(5)

其中r1与r2分别表示为：跳数影响信息素程度因子、时延重要影响信息素程度因子。通过设立这两个参数来实现跳数和时延共同对信息素浓度更新的影响。

最终算法将会通过不断对上述过程进行循环迭代，让算法的结果逐渐收敛于该网络中开销最小的最优路径。

在上述算法执行过程中，相关参数数值的设定对算法的性能影响会非常大。如：如果蚂蚁数量m的值若设得过大，会导致路径上的信息素浓度比较均匀使收敛速度过慢，过小又会导致收敛速度过快，解的全局最优性降低；迭代次数若过大又会导致计算时间过长，过小可能会导致陷入局部最优解。其他参数相同，参数的设定需要通过不断的测试实验进行自适应调整，然后找到一个合理的数值区间。

3 MATLAB仿真实验

在MATLAB R2020a仿真软件环境下，对传统蚁群算法和本文算法进行仿真，仿真环境为：Windows 10_64位操作系统；Intel®CoreTMi5-7300HQ CPU @ 2.50 GHz处理器；8 GB内存。网络路由协议是基于内部网关OSPF协议进行路由仿真的。

实验利用MATLAB软件构建了一个了网络拓扑图，该图包括25个节点，以英文字母A-Y编号，将A设为源节点，W设为目的节点。图中共有边的数量为125，且都赋予权值(表示为该边的时延大小)，如图2所示。

图2 仿真实验的网络拓扑图

3.1 最优路径选择实验

由于最短路径即是指相对开销程度最小的路径，所以在仿真实验中，设计了由跳数和时延两个约束条件来实现对最优路径的选择，具体方法为：为了简化计算，将跳数抽象为路径中经历的节点个数，将时延抽象为每条边的权值。由于在实际的网络传输开销当中，跳数数量的多少对于开销的大小相较于时延会更大，所以算法的选路的主要规则就是去寻找跳数较小的路径集合中，相对时延较小的路径，并以这两个约束条件来更新信息素浓度。经过实验之后，最优路径寻径结果、最小开销与平均开销走势及最优路径的时延与跳数走势结果如图3、图4和图5所示。

图3 最优路径寻径结果

图4 各代最小开销与平均开销走势图

图5 各代最优路径的时延与跳数走势图

由上图的仿真实验结果知道，在该网络拓扑图中从节点A到节点W开销总值最小的路径(即最优路径为)为A→C→N→O→W，路径的开销值为68(关于开销值的计算公式上节有介绍)，跳数为5，时延为43。通过多次实验最终都收敛于该路径，可以得到该路径就是当前状态的唯一最优路径，多次实验的数据统计如表1。

表1 蚁群优化算法选路结果统计

在真实的网络环境中，对于最优路径的选择会更加复杂多变，需要考虑更多地综合影响，例如带宽、差错率、耗费等。而在本算法中，可以根据实际情况去调整跳数重要程度因子ω1与时延程度因子ω2，还有跳数影响信息素程度因子r1与时延重要影响信息素程度因子r2这两对参数的各自值的大小，来调整两者对选路时的影响程度。同时也可以把如带宽、差错率、耗费这类的因素分配对应的比例来赋予权值，由此来实现在多因素综合影响下选出综合开销最少的最优路径。

3.2 路由阻塞的避障方式

在实际的动态网络当中，时常会发生路由阻塞或者故障的情况，而传统的链路状态算法在处理节点阻塞的情况下会显得比较无力，导致网络的开销增加。笔者则基于蚁群算法给出了两种处理当最优路径中的节点出现阻塞时的解决方案。

1)通过将该节点所连接的边的权值赋予一个相对无限大的权值，通过算法的自适应性使其他节点到该阻塞节点的转移概率降到趋近于0，从而避开阻塞节点去选择其它的最优路径；

2)将阻塞的节点加入到每只蚂蚁的禁忌表中，当蚂蚁到达与阻塞节点相连的节点时，将阻塞的节点直接从下一步被允许访问的节点集合ak中去除。由此来达到避开阻塞节点重新选择其它的最优路径的目的。

在算法迭代第50次时，把节点N设为阻塞节点，然后对这两种节点发生阻塞时的解决方案分别进行仿真实验，并对所得到的结果进行对比。

方案1)结果如图4～图6、图4～图7。

图6 方案1)的各代最小开销与平均开销走势图

图7 方案1)的避障寻径结果

方案2)结果如图8、图9。

图8 方案2)的各代最小开销与平均开销走势图

图9 方案2)的避障寻径结果

从实验结果可知，这两种方案都能在N节点(上图中的红点)发生阻塞后重新找到开销值最小的最优路径，收敛得到的最优路径分别为：A→P→Q→S→W和A→E→M→O→W。这两条路径的开销值都为69，同为最优路径。下面再对这两种解决方案进行多次实验，通过结果统计对比性能，具体结果统计对比如下表2，表中的平均迭代次数指发生阻塞后收敛到新的最优路径的平均迭代次数。

表2 两种避障方案实验结果统计

通过对表中数据对比发现，两种方案在发生阻塞后对最优路径的重新选择的收敛速度上，方案1)表现更优，但两者的差距并不是特别大。虽然在本次实验中两种方案都做到了100%地规避了阻塞节点，但实际方案1)是还存在极小的概率会去访问阻塞节点，而方案2)则可以做到在理论上也100%规避阻塞节点，但若在频繁发生路由阻塞的网络中，则需要频繁性地去更新和维护蚂蚁的禁忌表。经过综合考量，基于算法自身自适应性去规避阻塞节点的方案1)性能更优。

3.3 与其他算法对比

为了展示本文算法的优越性，与传统蚁群算法做了对比，针对传统蚁群算法存在收敛较慢，容易陷入局部最优解的不足。本文算法通过自适应性调整相关参数，如：信息素重要程度因子、启发函数重要程度因子和信息素挥发因子的优化策略，加快了算法的收敛速度，同时也降低了算法陷入局部最优解的概率，提高算法的搜索深度。

在初始时刻，将上述的3个参数设为：α=0.5、β=1、ρ=0.7。当算法迭代到最大迭代次数的1/5时，则设置为α=1、β=3、ρ=0.9。然后在MATLAB上对传统蚁群算法和本文算法分别进行仿真实验，结果如表3、表4所示。

表3 传统蚁群算法仿真结果

表4 本文算法仿真结果

由实验结果显示，当在一开始就把α、β和ρ的数值设的较大的话，虽然能够让算法更快的收敛，但同时也使得算法更容易陷入局部最优解。而本文算法则可以做到，在算法前期的搜索深度更深，不容易陷入局部最优解，而在运行到一定迭代次数后，又能缩小搜索范围向最佳路径靠拢，从而提升收敛速度。因此本算法有效地弥补基本蚁群算法的一些不足，减少算法计算量，提高算法的求解性能。

4 结语

网络中的路由选路优化问题属于组合优化的离散问题，分析了网络路由性能度量参数。然后将自适应蚁群算法进行建模应用于路由协议优化问题中，通过设立多个影响因素(跳数、时延、带宽等)来实现对网络中最优路径的选择，解决最优路由的优化过程。最后仿真实验表明，本文算法能够更好地适应动态变化的网络，扩大了搜索深度，加快了收敛速度，比传统蚁群算法能较好地解决路由优化问题。