使用蚁群优化进行网络路由

介绍 

路由协议在计算、选择和确定相关路径以将数据从源高效地传输到目的地方面发挥着非常重要的作用。目前已有许多公认的路由算法用于寻找最短路径以及提高网络吞吐量。
在本文中，我将解释一种用于选择数据包路径的算法，该算法以最短路径为导向。每个网络路由算法的目标都是将流量从源头引导到目的地，从而最大化网络性能。通常考虑的性能指标是吞吐量（单位时间内传输的比特数）和成功到达目的地的数据包数量。然而，在我的实现中，我采用的性能指标是边之间的总成本之和。选择最佳最短路径的最优解是选择总成本最小的那一条。
本文分为四个部分。第一部分解释了网络路由及其背后的问题。第二部分简要介绍了 ACO。第三部分涉及我创建的实现及其实验结果。最后，第四部分包含结论以及一些未来的工作范围和本文中使用的参考文献。

1. 网络路由

网络路由是在网络中选择路径以发送网络流量的过程。[1] 通信网络可分为电路交换或分组交换。电路交换网络的例子是电话网络，其中物理电路在通信开始时建立，并在整个通信期间保持不变。与此不同的是，在分组交换网络（也称为数据网络）中，每个数据包可以遵循不同的路由，没有固定的物理电路建立。数据网络的例子是局域网（LAN）和互联网。[2] 在本文中，我将重点关注数据网络。
数据网络的主要功能是确保其用户之间信息的有效分配。这是通过利用网络控制系统来实现的。控制系统最重要的组成部分之一是路由。路由指的是构建和使用路由表的分布式活动。
路由表是所有路由算法的共同组成部分。它用于保存信息以做出本地转发决策。网络中的每个节点都维护一个路由表。它告诉节点传入的数据包接下来要使用哪个链路，以便继续其到该数据包目的节点的旅程。
然而，网络路由问题的主要方面之一是其非平稳性。这意味着，路由的一个特点是网络上的流量随时都在变化。此外，网络的节点和链路可能会突然停止服务，新的节点和链路也可能随时添加。为了创建这个问题的最优解，所有这些特性都必须被考虑在内。这就是最短路径问题。

1.1 最短路径路由

最短路径路由是在解决网络路由问题时应用最短路径算法。其目标是确定两个节点之间的最短路径（最小成本），其中构成该路径的边的成本之和最小化。
至今，许多用于解决最短路径问题的路由算法已被接受。其中之一是 Dijkstra 算法。Dijkstra 算法由荷兰计算机科学家 Edsger Dijkstra 于1959年构思，是一种图搜索算法，用于解决具有非负边成本的图的单源最短路径问题，生成一个最短路径树。[3]
对于图中给定的源节点，该算法找出该节点与每个其他节点之间成本最低的路径（即最短路径）。它也可用于查找从单个节点到单个目标节点的最短路径的成本，方法是在找到到目标节点的最短路径后停止算法。例如，如果图的节点代表城市，边的路径成本代表由直路连接的城市对之间的驾驶距离，Dijkstra 算法可用于找到一个城市与所有其他城市之间的最短路线。因此，最短路径优先（shortest path first）被广泛用于网络路由协议中，最著名的是 OSPF（开放式最短路径优先）和中间系统到中间系统（IS-IS）。[3]
用于解决最短路径问题的 Dijkstra 算法在以下链接中有介绍。

正如我所提到的，网络路由具有可变性，网络的节点和链路可能会突然中断，也可能会创建新的节点和链路。因此，我们有 OSPF，它是一种动态路由协议，能够跟踪整个网络拓扑以及该网络内的所有节点和链路。
此外，如果在一段时间内网络中的最佳路由趋于收敛，而突然发生链路故障，OSPF 将很快在拓扑中检测到它，并收敛到新的无环路路由结构。因此，总结本节，我们现在将收敛性视为后续章节以及我准备的实现中需要解决的潜在问题之一。

2. 蚁群

[5],[6],[7] 蚁群优化 (ACO) 是一种基于真实蚂蚁寻找从源头到食物最短路径行为的算法。它利用了真实蚂蚁在寻找食物时的行为。据观察，蚂蚁在从巢穴到食物的途中，会在其路径上留下一定量的费洛蒙。返回巢穴时，蚂蚁会沿着费洛蒙标记的同一路径返回，并再次在其路径上留下费洛蒙。这样，沿着较短路径的蚂蚁预计会更早返回，因此其路径上费洛蒙的沉积速度会比沿着较长路径的蚂蚁更快。
然而，费洛蒙在一定时间间隔后会以恒定速率蒸发一定量，因此只有蚂蚁频繁访问的路径才会因费洛蒙沉积而被标记保留，而蚂蚁很少访问的路径会因为缺乏费洛蒙沉积而消失，结果新的蚂蚁倾向于只跟随频繁使用的路径。
现在，所有开始旅程的蚂蚁都可以从先前访问过的蚂蚁留下的信息中学习，并在费洛蒙沉积的引导下走向更短的路径。在 ACO 中，许多人工蚂蚁（模仿数据包）为所考虑的优化问题构建解决方案，并通过一种通信方案交换这些解决方案的质量信息，即在旅程的路径上沉积费洛蒙。

2.1 ACO 在网络路由问题中的应用

ACO 算法可以应用于网络路由问题中以寻找最短路径。在网络路由问题中，一组人工蚂蚁（数据包）从源头模拟到目的地。前向蚂蚁第一次会利用路由表中的信息随机选择下一个节点，成功到达目的地的蚂蚁会更新它们访问过的边上的费洛蒙沉积，更新量为 (C/L)，其中 L 是蚂蚁的总路径长度，C 是一个根据实验条件调整到最优值的常数值。下一组蚂蚁现在可以从先前成功访问的蚂蚁留下的费洛蒙沉积反馈中学习，并将被引导遵循最短路径。[2][7]
蚂蚁从节点 i 选择节点 j 的概率由以下公式给出

当然，这是在两个节点之间存在链接的情况下，否则 Pij = 0。这里，τij 是连接节点 i 和 j 的每条边的费洛蒙。ηij = (1/dij)，其中 dij 是节点 i 和 j 之间的距离。α 和 β 是两个参数，它们决定了费洛蒙踪迹和启发式信息的相对影响。

ACO 的主要特点是费洛蒙值由所有成功到达目的地的蚂蚁
（数据包）更新。然而，在添加费洛蒙之前
我们首先必须执行蒸发操作。节点 i 和节点 j 之间边上的费洛蒙蒸发 (ρ)
通过以下公式实现
τij ← (1 - ρ)τij
所以，每个时间点 t={1,2,3,4...n} 代表一次迭代，其中蚁群中的所有蚂蚁
都将向选定的节点移动一步。因此，考虑到这一点，
所有蚂蚁在 n 次迭代后，都会找到解决方案并留下费洛蒙，
费洛蒙的计算公式如下

此外，某只蚂蚁 k 添加到它未经过的边上的费洛蒙量为
0。否则，如果蚂蚁 k 经过了节点之间的某条边，它将留下一定量的费洛蒙，
这个量与蚂蚁 k 从起始节点到目的节点的路径上所有边的总成本成反比。
以下公式展示了这一点
process

Δτij^k 是蚂蚁 k 在访问的边上沉积的费洛蒙量。它通过以下公式计算
expression

其中 C^k 是蚂蚁 k 从起点到目的地路径上所有经过的边的总成本。
这将允许表现更好的蚂蚁在属于最短路径的边上留下更多的费洛蒙。
这是最短路径上的路线。
ACO 在网络路由中应用的另一个优点是，当数据包数量
增加时，该算法也可以用于控制拥塞。在静态路由
算法中，所有从起点到目的节点的包在一段时间后都会遵循一个由算法计算出的
恒定路径，因此我们可能会遇到拥塞问题。结果，
一些数据包将不得不等待。然而，在 ACO 中，由于下一个节点是随机选择的，
并且选择最短路径的概率更高，一些数据包会走其他路径，
这提高了网络性能并对抗了拥塞。
除此之外，在动态环境下，如果在一段时间后最短路径收敛，
而突然我们遇到位于最短路径路线上的两个节点之间的链路故障和断开，
ACO 会迅速跟随另一条路径并收敛于其上。

3. ACO 算法的实现

在解释了网络路由和 ACO 的基本过程和术语以及它们之间可能的联系之后，在本节中，我将解释我创建的用于解决网络路由中最短路径问题的 ACO 算法实现。该实现遵循与 ACO 相同的算法组织结构，在解释之前，我将提供更多关于我创建的实现的环境和结构的细节。
该实现是我用 C# 编程语言编码的一个控制台应用程序。编程环境是 Visual Studio 2010 中的 3.5 .NET 平台。为了使其尽可能与基本的 ACO 相似，我使用了一种面向对象的方法。这样做的结果是，我最终得到了两个主要的类：Ant 和 Edge。在接下来的部分，将展示并解释 UML 类图（图3.1）。

 

 

Ant 类代表 ACO 中的蚂蚁以及网络路由问题中的数据包。为了让蚂蚁成功地穿过网络图，它必须具有这些基本属性，如：antID (AID)、CurrentNode (蚂蚁所在的节点) 和 Name (蚂蚁的字符串表示，以便于跟踪)。除此之外，为了让蚂蚁能用费洛蒙量更新走过的路径，它必须有一个堆栈 (LIFO)，在上面它将添加它走过的链接，在这里是边 (edge)。这里使用的堆栈是一个泛型堆栈，它将 Edge 类的对象实例添加到自身中。该堆栈表示为字段：path。为了处理更多关于堆栈的过程，Ant 类包含多种方法来满足 ACO 算法的实现。
Edge 类代表 ACO 中的图以及网络路由问题中的网络路由表。为了让蚂蚁移动，它必须有某种地图，在这种情况下它是一个图。我用于测试的图都是有向图。这个图，表示为路由表，由不同数量的边组成，这意味着它被表示为一个 Edge 类对象实例的数组。每个 Edge 对象都有其属性。其中一些对于蚂蚁的堆栈很重要，而另一些对于创建图很重要。这些属性是：EdgeID、FirstNode (起始顶点，即节点)、SecondNode (FirstNode 可以结束的节点)、Pheromone (FirstNode 和 SecondNode 之间边上的费洛蒙量) 和 Cost (FirstNode 和 SecondNode 之间边的权重)。除此之外，Edge 类有一个方法用于以视觉上美观的方式呈现它们。
在解释了 Ant 和 Edge 类之后，我现在将简要介绍一下作为我主程序的 Program 类。Program 类包含各种方法，用于显示结果和图表，或执行 ACO 算法在主方法 (Main) 中正常运行所需的一些小操作。在下一节中，我将解释 Main 函数以及我的实现中用于解决网络路由问题的算法。
在进入主算法之前，我首先开发了几个图，这些图将作为主函数中 ACO 算法的测试用例。这些测试图是在主程序中作为方法创建的，它们是：TestGraph_1、TestGraph_2 和 TestGraph_3。TestGraph_1 的图示在下图中作为一个例子，展示了实现中使用的图，而其余两个将在本文的后续阶段展示。

在启动 ACO 算法之前，我们需要的下一件事是蚂蚁。由于它们代表网络路由中的数据包，因此它们是这场戏中的主要演员。我创建的初始蚂蚁种群由五只蚂蚁组成，并通过 createAnts 方法实现。它返回一个蚂蚁数组，表示为一个蚁群。下面的代码片段简要介绍了蚂蚁的特性。

  public static Ant[] createAnts(Ant[] ant)
{
ant[0] = new Ant(1, "Yellow ant", 1);
ant[1] = new Ant(2, "Red Harvester", 1);
ant[2] = new Ant(3, "Fire ant", 1);
ant[3] = new Ant(4, "Native Brown ant", 1);
ant[4] = new Ant(5, "Kitchen ant", 1);
return ant;
}

在启动 ACO 算法之前的最后一步是声明和设置一些算法正常运行所需的重要设置。这些是

• - EvaporationAmount (double) - 在时间 t={1,2...n} 的每次迭代中的蒸发量；
• - Tstart (int) - 时间循环中的开始时间（表示为：1个时间单位 = 1次迭代）；
• - Tend (int) - 时间循环中的结束时间；
• - Tconverge (int) - 链路故障发生在收敛边上的时间单位；
• - Convergence_On (bool) - 如果发生链路故障则返回 true，以便某些程序运行，否则为 false，这也是初始设置；
• - random (int & double) - Random 类的对象实例，为图中边的概率选择提供随机值；

现在，在为 ACO 创建了运行环境之后，我将解释我的实现中使用的 ACO 算法，并通过下图中的伪代码进行简要说明。

nt Tstart;
int Tend;
int Tconverge;
bool Convergence_On ← false;
double EvaporationAmount;
while(Tstart < Tend)
{
If(Tstart = Tconverge)
{
displayResults(graph);
ConvNum ← ChangeAfterConvergence(graph, graph.StartNode, graph.EndNode);
SetAntsToStartNode(antColony);
}
Foreach(Ant a in antColony)
{
If(a.CurrentNode == graph.EndNode)
{
a.AddPheromone(graph);
a.CurrentNode ← graph.StartNode;
a.clearTheStack();
} 

Else
{
a.ToString();
While(!Convergence_On)
{
edgeNum ← chooseEdge(graph, a.CurrentNode);
if(graph.edgeNum == ConvNum)
{continue;}
Else
{
a.pushToStack(graph.edgeNum);
a.CurrentNode = graph.SecondNode;
Convergence_On ← true;
}
}
Convergence_On ← false;
}
}
Evaporation(graph, EvaporationAmount);
Tstart++;
}	 

在 C# 中执行此伪代码的等效编程表示后，编译结果会通过 Program 类中的方法显示在控制台中。这些方法是：displayResults() 和 TheBestRoute()。它们在 ACO 算法完成其在时间循环中的任务后启动。

示例 1：TestGraph_1

在下图中，我们有8个节点，每个节点都通过边与其他某个节点相连。每条边都有其成本。起始节点是节点1，而结束节点是节点8。我们必须找到这些节点之间的最短路径，同时要记住，最短路径是构成它们之间路径的所有边的总成本最小的那条。由于这是有向图，我们只能从左侧向右侧移动。

在编译程序之前，我将列出这个问题的一些可能解。这将是一个包含起点和终点之间可能路径以及每条路径总成本的列表。最佳路径，即最短路径，用绿色高亮标记。
路径 -> 路径总成本

• a) 1-2-5-8 -> 10
• b) 1-2-6-8 -> 10
• c) 1-2-7-8 -> 8
• d) 1-3-5-8 -> 8
• e) 1-3-6-8 -> 8  
• f) 1-3-7-8 -> 6
• g) 1-4-5-8 -> 12
• h) 1-4-6-8 -> 9
• i) 1-4-7-8 -> 12

所以，最优解是：1->3->7->8，总成本为：6。在我创建的程序中对此图执行100次迭代后，我们得到的结果如编译计算的截图所示

 

经过 100 次迭代的编译后，会向我们展示 ACO 在该图中的结果，方法是显示所有边以及它们上面的费洛蒙量。之后，计算出的最佳迭代结果与我们之前手工计算的结果相同。结果是：1->3->7->8，最短路径的总权重为：6。
现在，我们将模拟网络路由中发生的链路故障，并删除最佳路径中的最后一条边，以打破那条收敛的路径。我们将再执行100次迭代，并得到以下结果

 

在打破收敛之后，最佳即最短路径现在是：1->3->5->8，路径的总成本等于8。如果与我们之前提到的结果列表进行比较，这是正确的结果。

4. 结论

通过实施 ACO 算法来解决网络路由问题，我得出结论，该算法可以有效地用于解决网络路由最大的问题之一，即寻找起点和终点之间的最短路径。尽管该算法并不总是能找到最短路径，但它无疑为问题本身带来了更多积极的方面，因为它最小化了网络路由必须应对的其他问题，如拥塞、收敛中断等。
总而言之，未来应继续对 ACO 算法进行研究，然而，在应用于网络路由问题时，应考虑更多因素，例如：拥塞控制、延迟因素、不同类型的网络路由和方向。

参考文献

[1] - 路由 - [在线文章] - 访问日期：2011年6月3日 - 链接：http://en.wikipedia.org/wiki/Routing
[2] - Marco Dorigo & Thomas Stutzle - "蚁群优化" - 麻省理工学院出版社版，年份：2004年。
[3] - Dijkstra 算法 - [在线文章] - 访问日期：2011年6月3日 - 链接：http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
[4] - Prim 算法 - [在线文章] - 访问日期：2011年6月2日 - 链接：http://en.wikipedia.org/wiki/Prim's_algorithm
[5] - M. Dorigo, V. Maniezzo & A. Colorni, 1996. "蚁群系统：通过协作智能体群进行优化", IEEE
[6] - Mcgraw-Hill 的计算机科学高级主题系列，优化中的新思想。
[7] - Dr. Samim Konjicija - 讲座幻灯片 - SSST 大学，年份：2011
[8] - Gianni Di Caro - "蚁群优化及其在电信网络自适应路由中的应用" - 年份：2004。

历史与更新

要获取更多图表、示例、源代码和关于此主题的详细信息，请参考我的个人网页。