Topological optimization of a reliable communication network
Topological optimization of a reliable communication network
复制标题
可靠通信网络的拓扑优化
DOI：
10.1109/24.740489
复制
发表时间：
1998
影响因子：
5.9
通讯作者：
Sheng
中科院分区：
文献类型：
--
作者：
Sheng
本文考虑的约束下的骨干网络设计：最小的总链路成本，1-FT（容错1链路故障）。随着网络规模的不断扩大，骨干网的布局设计对网络的性能和可靠性至关重要。1-FT主干可以承受任何1-链路故障。另一方面，主干网布局中链路的总成本是一个实际问题。因此，问题是要找到一个网络拓扑的一组节点，其总的链路成本最小化，受到的条件，骨干网络可以容纳1链路故障。该问题是NP-难的，基于启发式搜索的方法，希望获得最优或次优的解决方案。本文提出了一种基于遗传算法的有效方法来解决这个问题。主干布局的表示基于有序链接的列表。遗传算子试图产生更经济有效或更可靠的布局。仿真结果表明，该算法可以有效地找到一个次优解的大多数情况下。
This paper considers backbone network design under the constraints: minimal total link cost, and 1-FT (fault-tolerant to 1 link-failure). As networks become huge, the backbone layout design is essential to network performance and reliability. A 1-FT backbone can survive any 1-link failure. On the other hand, the total cost of the links in backbone layout is a practical concern. Therefore, the problem is to find a network topology for a set of nodes whose total link cost is minimized, subject to the condition that the backbone network can accommodate 1 link failure. The problem is NP-hard, and methods based on heuristic search are desired to obtain optimal or sub-optimal solutions. This paper proposes an efficient method based on genetic algorithms to solve the problem. The representation of a backbone layout is based on a list of ordered links. The genetic operators attempt to generate a more cost-effective or reliable layout. Simulation shows that the proposed algorithm can efficiently find a sub-optimal solution for most cases.