Home > Published Issues > 2018 > Volume 13 No.10, October. 2018 >

A New Heuristic Method Improvement for Ring Topology Optimization: Proposal Algorithm

Syamsul Qamar, Sigit Haryadi, and Nana R. Syambas
School of Electrical Engineering and Informatics, Institut Teknologi Bandung (ITB) Bandung 40132, Indonesia

Abstract—The issue of optimization is very important in designing computer network. Designing a ring topology is about connecting a set of point-shaped nodes which are each connected to two other points, thus forming a circular path forming a ring. This idea tries to formulate an algorithm to optimize the ring topology by using an approach that is on the Traveling Salesman Problem (TSP). There are two variables considered in TSP. Both are the strategy to find the node configuration which has minimum cost as well as the most minimum time consumption for its execution. To measure the extent to which the proposed algorithm can perform optimization, then made a comparison with some existing algorithms such as Brute force, Ant colony, and Bambang. Brute Force has the ability to find the absolute minimum node configuration cost but in terms of time to complete it increases exponentially. While it does not provide the minimum cost, the Ant Colony Optimization algorithm (ACO) has the minimal advantage needed to find the minimum node configuration. This paper proposes a heuristic algorithm to find the sub-minimum node configuration. The proposed algorithm has the shortest time of fewer than 50 seconds to 50 nodes, compared to other algorithms while the cost of node configuration is not always lower than Ant Colony.

Index Terms—TSP, heuristic, ring toplogy, network design, routing algorithm, ant colony, brute force.

Cite: Syamsul Qamar, Sigit Haryadi, and Nana R. Syambas, " A New Heuristic Method Improvement for Ring Topology Optimization: Proposal Algorithm," Journal of Communications, vol. 13, no. 10, pp. 607-611, 2018. Doi: 10.12720/jcm.13.10.607-611.