Bi-Objective Topology Design of Communication Networks Using Dynamic Programming
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Elshqeirat, Basima; Soh, Sie Teng; Chin, K. (2015)This paper addresses an NP-hard problem, called NTD-CB/R, whose solution is of importance to applications requiring one or more Quality of Service (QoS). Specifically, the problem calls for a network topology that meets ...
Van Der Werf, Steven Martĳn (2010)In recent years, a great deal of attention has been given to wireless connectivity solutions that are capable of establishing wireless ad-hoc networks between mobile nodes. Whilst most of these networks are formed using ...
Loh, Ruen Chze (2010)Most of today’s computer communications use only a single (s,t) path to transmit a message from a source node s to a destination node t. There are two major problems with this single path communication. Firstly, the ...