基于蚁群算法的网络层析故障链路诊断*

康英来，范晓波

（中国电子科技网络信息安全有限公司，四川 成都 610000）

0 引言

故障链路会带来网络服务的中断，定位网络中的故障链路非常重要，将有助于网络工程师和因特网服务提供商（Internet Service Provider，ISP）监视网络性能，并提供与客户约定的服务水平协议（Service Level Agreement，SLA）相匹配的网络服务。很多原因都可能导致链路故障，除了物理链路故障之外，一些如路由器配置错误等“软”错误也会导致链路连接失败[1]。

为了定位网络中的故障链路，最直接的方法是在网络内部节点部署探针监测链路性能参数。然而，出于安全或商业因素考虑，内部节点通常是不协作的，使得直接监测变得不可行[2]。近年来，一种叫作网络层析成像（Network Tomography）的技术[1-4]广泛应用于链路故障诊断中。该技术在网络边缘节点发送探测包，通过探测包的行为推断网络中的链路状态。由于网络层析成像仅利用节点的转发行为，不需要内部节点的合作，因此相对直接测量它具有更广泛的应用场景。

采用网络层析技术识别故障链路的思路最早由Padmanabhan 和A Coates 等人[2-3]提出。这种框架首先选择某些边缘节点作为探测点，探测点与探测点之间形成探测路径，然后在探测路径上发送探测包。假设网络中存在一些故障链路，显然经过故障链路的探测包是不可达的。通常0表示正常（非故障）链路，1表示故障链路，因而链路的状态是布尔型的。类似地，探测路径的状态也是布尔型的（即1 表示路径不可达，0 表示路径正常）。故障链路诊断的目的是从路径的状态推断链路的状态，这可建模为一个优化问题，即找出最小的链路失效集，以解释探测路径的状态。

然而，这个优化问题是多项式复杂程度的非确定性（Nondeterministic Polynomial，NP）完全的[5]。当前文献广泛采用贪婪式算法求解。文献[5]提出一种基于因子图-和积方法来估计先验概率；基于同样的思想，文献[6]提出一种类似的方法CLINK，联立多个路径状态方程估计链路故障的先验概率。然而，由于先验概率的估计需要长时间的路径测量，会影响链路推断的实时性。文献[7]提出了一种线性规划（Linear Programming，LP）松弛方法来定位网络中故障的链路，实验验证该方法在某些情况下精度较高。文献[8]提出一种迭代算法TOMO 方法，在每次迭代中选择失效路径经过最多次数的链路当作故障链路。该方法易于实现，容易扩展至大规模网络。

不同于上述链路故障定位方法，本文提出一种基于蚁群算法的网络层析故障链路诊断框架。蚁群算法最初用来解决旅行商问题（Traveling Salesman Problem，TSP）[9]，后来被引进用来分析普遍意义上的优化问题。受它在解决NP 完全问题时具有优良解特性的启发，本文首次将其引入到网络故障链路诊断。

1 模型与框架

遵循当前网络分析中的约定，本文将网络的逻辑拓扑代替网络实际拓扑。逻辑拓扑可由图G=(V，L)来表征，其中V为图的顶点集合、L为图的边集合。网络拓扑中，顶点vi∈V可以表示物理拓扑的主机或路由设备，而边li∈L表示顶点之间的单个链路或多条链路。不失一般性，假设网络中共有n条链路。

为了监测网络中的链路状态，从顶点集合V中选择一部分节点S⊂V（通常为边缘节点）作为探测点，探测点与探测点之间形成探测路径，然后在探测路径上发送探测包。令布尔变量yl表示路径pl的状态，布尔变量xk表示链路ek的状态。此外，约定对于路径和链路均用0 代表正常，用1 代表不可达或故障。显然，经过故障链路的探测包始终是不可达的。因此，对于探测路径pl，有式（1）成立：

其中“∨”表示布尔代数中的OR 操作，rlk也是布尔变量，表示pl是否经过链路ek（当且仅当路径pl经过链路，rlk取值为1，否则为0）。式（1）的含义显而易见，即当路径经过任意一条故障链路时，则路径不可达。

假设网络中共有m条探测路径。由于对于每条探测路径都有类似等式（1）成立，为了简便起见，将m个等式写成矩阵形式，即有[7]：

式（2）中的每一项都由式（1）确定。其中，y=(y1，y2，…，ym)为m维向量，代表m条探测路径的状态；x=(x1，x2，…，xn)为n维向量，代表n条链路的状态；R=[rlk]为一个m×n的矩阵；⊙为布尔矩阵中的相乘操作。由于网络中的路由相对固定，因此链路故障诊断便建模为给定布尔向量y和布尔矩阵R，求解布尔向量x。

在实际网络中，根据探测路径不能完全确定链路状态，式（2）存在多个解。为了得到x的值，转而求解如下优化表达式[6-7]：

然而，求解式（3）是NP 完全的。由于链路或路径的状态是布尔型的，式（3）是一个典型的0-1规划问题，或者是一个组合优化问题。本文尝试利用蚁群算法求解式（3）得到网络链路状态。值得注意的是，不同于将蚁群算法运用到网络路由寻优[10]，本文不是网络寻路问题，而是将其建模为解决故障链路诊断中的优化问题。

2 蚁群算法求解故障链路

蚁群算法是根据蚁群觅食行为而得来的一种算法，具有分布计算、信息正反馈（通过信息素）和启发式搜索的特征。蚁群算法首次用来解决旅行商问题[9]，后来被引进用来分析普遍意义上的优化问题，特别是在解决组合优化问题中具有独特的优势[11]。本文将其引入到网络故障链路诊断框架。

在定位网络故障链路时，首先将蚂蚁随机放置到网络的各个探测点，然后蚂蚁在网络中进行随机行走，行走的路线不应违背式（2），即只能在不可达路径对应的链路上行走，蚂蚁会在沿途释放出一种叫做信息素的物质，这种物质会影响后来的蚂蚁路线，指导其以较大概率选择信息素较多的链路。如此迭代，最终使得优化表达式（3）的优化目标变小，从而解决本文的故障链路求解问题。

蚁群算法的相关符号定义如下：

Na：蚂蚁数量，蚂蚁数量不宜过大和过小，如果太大则信息素分布太均匀，反之易陷入局部最优点，根据文献[9]的建议，蚂蚁数量约为网络节点数量的1.5 倍；

Nb：网络节点数；

Q：信息素常数，表示蚂蚁遍历一次所释放的信息素总量，值越大，则蚂蚁受到信息素选择链路的影响越大，收敛越快，但也容易收敛至局部最优点；

τij(t)：在t时刻，网络节点i和网络节点j之间的信息素浓度（节点i、j构成网络里的一条链路）；

蚂蚁在运动过程中，其运动路线受链路上信息素浓度的影响，具体来说，在t时刻，蚂蚁k的转移概率为：

其中α为信息素浓度的指数参数；allowk表示蚂蚁当前位置下一个可行的网络链路，它需要符合优化表达式（3）的优化条件，即只能在不可达路径对应的链路上行走，且不包含已经经过的链路。需要注意，在经典的蚁群算法中，转移概率还和启发函数有关。由于在优化目标（3）中，所有链路权重一样，因此问题中不应有启发函数。

当所有蚂蚁走完全程时，此时表达式（3）中的条件y=R⊙x得到满足，即完成搜索故障链路的一次迭代，在下一次迭代开始，更新每条网络链路的信息素：

每只蚂蚁由于走过路径不一样，在链路上留下的信息素的量也不一样。经过的链路数越少，即表达式（3）的优化目标越小，此时应在经过的链路上留下较多的信息素，以指导后来的蚂蚁以较大概率选择这些链路。蚂蚁k在网络节点i和网络节点j之间留下的信息素数量为：

其中Lk为蚂蚁k在本次迭代中经过的链路数目。由此可见，若经过的链路数目越少（即||x||1的值越小），留下的信息素越多，后来的蚂蚁更有可能经过这些链路。

蚁群算法求解故障链路的算法流程是在式（4）～式（6）之间迭代，直到满足最大迭代次数或状态改变少于预设阈值，然后将当前链路的信息度浓度按降序排序，逐步选择排序靠前的链路直到满足式（3）中的优化条件，此时所选的链路便是算法诊断的故障链路。

注意和传统的蚁群算法相比，求解故障链路的蚁群算法在初始放置点和可行路径上都受约束。蚁群的初始放置点只能放在探测点上，且所有蚂蚁必须在不可达路径对应的链路上行走。同样，一次迭代过程中蚂蚁不需要回到最初出发点，只需其行走的路径满足表达式（2）即可。

传统的蚁群算法在迭代开始前，在所有链路上的信息素相等。为了使得算法更快收敛，本文在上述蚁群算法上做如下改进。

在初始时刻，链路上的信息素和经过该链路的不可达路径数成正比，即：

其中，nij为经过节点i和节点j的不可达路径数目，c为预设的常数。通过式（7）设置链路的初始浓度后，蚂蚁将倾向于选择被多条不可达路径经过的链路。这显然和优化表达式的优化目标一致，从而加速算法的收敛。

综上所述，本文蚁群算法求解故障链路的算法流程如下：

1.输入网络拓扑、路由矩阵R，路径测量y；

2.初始化蚁群算法各个参数；

3.随机放置蚂蚁到各个探测点，按式（7）初始化各链路的信息素浓度；

4.对于每只蚂蚁，根据式（4）不断选择下一个网络节点直到满足条件（2）；

5.根据式（5）更新信息素；

6.根据式（6）更新转移概率；

7.重复步骤3～步骤6，直到满足最大迭代次数；

8.输出链路状态x，其中状态为1 的链路即为故障链路。

3 仿真和性能分析

为了验证本文所提算法的有效性，在真实的网络拓扑上进行试验。网络拓扑采用Rocketfuel 项目[12]所测量的实际ISP 骨干网络拓扑AS1755。AS1755 是欧洲的骨干网络（Ebone），总共含有163 个路由器和300 条链路。所有实验都是在MATLAB 上编码完成。

试验假设网络中故障链路占比为q，q值表示网络所遭受的故障级别。实验仿真在不同的故障级别下算法的性能，设定q从0%到25%。为了诊断网络中的故障链路，设置网络中度为1 的边缘节点为探测节点，然后在探测节点间按照最短路径路由建立探测路径，由此可建立布尔矩阵R。在探测路径上发送探测包，并记录探测路径的状态，由此可得路径测量向量y。根据算法流程表1，即可获得网络中的故障链路集合。

实验首先分析了在求解故障链路时，改进前的蚁群算法和优化初始信息素改进后算法的收敛速度。为了判断是否收敛，将当次得到的链路状态和上次迭代得到的链路状态进行比较。若连续5 次迭代的链路状态均一样，则判定算法已经收敛。实验结果如图1 所示，可以看出，在定位网络故障链路时，若采用所有链路上的信息素相等的初始条件，算法要在150 次后才开始收敛；而采用式（7）改进后的蚁群算法，迭代100 次左右就进入收敛状态，从而能够大幅度减少算法运行时间。

图1 改进前和改进后的蚁群算法在链路故障定位中的收敛速度

同样地，将本文提出的算法和其他故障链路诊断算法进行了比较。由于TOMO 算法[8]简单易实现且能取得较好结果，它广泛运用于链路故障诊断中。本文采用精度（Precision）和召回率（Recall）两个性能指标和TOMO 进行比较。精度是预测正确的故障链路数占预测故障链路总数的比例；召回率为预测正确的故障链路数占实际故障链路数的比例。两者计算如下：

其中，TP为被判定为故障链路，而事实上也是故障链路的数目；FP为被判定为故障链路，但事实上是正常链路的数目；FN为被判定为正常链路，但事实上是故障链路的数目。

实验结果如图2 和图3 所示，分别表示不同算法进行链路诊断时的精度和召回率。可以看出，本文方法在性能上相比TOMO 算法有一定改进，尤其是在诊断精度上，且当网络中故障链路较多时，这种优势逐渐明显。TOMO 方法在迭代时选择失效路径经过最多次数的链路当作故障链路，这种选择有可能会误判一些正常链路，且这种选择是不可逆的。本文蚁群算法在选择时是一种概率选择，本次迭代的错误诊断有可能在下次迭代中被蚁群“修正”。事实上，本文可以在TOMO 算法基础上进行蚁群算法迭代，即将TOMO 算法的运行结果作为蚁群算法的初始状态，从而改进网络层析中故障链路的诊断精度。

图2 不同算法进行链路诊断时的精度

图3 不同算法进行链路诊断时的召回率

4 结语

本文提出了一种新的网络故障链路诊断方法。首先将故障链路诊断问题建模成一个0-1 规划问题，由于该问题是NP 难的，本文利用蚁群算法在解决组合优化问题中独特的优势，提出基于蚁群算法的故障链路诊断方法。不同于传统的蚁群算法，求解故障链路时蚁群在初始放置点和可行路径上都受约束。本文利用故障链路求解中优化目标的特性，对蚁群算法的初始信息素浓度进行优化，以加快算法的收敛速度。在网络拓扑中的仿真结果表明，本文算法在故障链路检测中具有较好的精度和召回率。