双归属环形网络拓扑规划算法设计

Algorithm for Dual-Homing Ring Network Design

本文研究了一种高效的双归属环形网络拓扑规划算法,提出了在满环与非满环间调整节点的启发式搜索算法,当节点数在1 500个以内时,本算法都能很快求解,而现有算法通常只能处理几百个节点的中等规模网络。本文首先给出了相关数学模型,然后详述了初始拓扑生成过程及采用的启发式优化算法。最后通过将CPLEX规划结果、人工规划结果和算法规划进行比对,验证算法性能。

This paper develops an efficient algorithm to design hierarchical dual-homing ring network. A heuristic algorithm that adjusts nodes between full-rings and non-full rings is presented. The solution can be obtained for up to 1 500 nodes in a small amount of time, while the existing algorithms usually can only handle a few hundred nodes. First this paper presentes the mathematical model, and then details the initial topology generation algorithm and the heuristic algorithm. Finally, the performance of the algorithm is verified through compare the topology with results obtained from the CPLEX and manual design.