Bi-Objective Topology Design of Communication Networks Using Dynamic Programming
Volume 11, Number 3, May 2015 - Paper 6 - pp. 265-274
BASIMA ELSHQEIRAT1, SIETENG SOH2, SURESH RAI3, and MIHAI LAZARESCU21 University of Jordan, Amman, Jordan.
2 Curtin University, Perth 6845, Western Australia, AUSTRALIA.
3 Louisiana State University, Baton Rouge, 70803 LA, USA.
(Received on September 10, 2014, revised on February 16, and February 25, 2015)
This paper provides an algorithm to design a communication network topology with minimal cost (C) and maximum (s, t) reliability (R) subject to a pre-defined bandwidth (Bmin) constraint, given (i) locations of the various computer nodes, (ii) their connecting links, (iii) each link’s reliability, cost and bandwidth, and (iv) a minimum bandwidth for the network. The bi-objective optimization problem is known NP-hard; henceforth we call the problem NTD-CR/B. We use the dynamic programming (DP) formulation as the engine in our proposed approach, DPCR/B, to generate the topology for solving NTD-CR/B. Further, we propose three greedy heuristics that enumerate and order only k?n (s, t) paths, where n is the total number of (s, t) paths in the network. Each heuristic allows DPCR/B to obtain the selected paths to form the topology using only k paths, which improves the time complexity while producing near optimal topology. Extensive simulations on large networks with various sizes show that DPCR/B is able to generate 91.2% optimal results while using only 1.37-27% of all paths in the grid networks that typically contain up to 299 paths.
Click here to download the paper.
Please note : You will need Adobe Acrobat viewer to view the full articles.