We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Bi-Objective Topology Design of Communication Networks Using Dynamic Programming.
- Authors
ELSHQEIRAT, BASIMA; SIETENG SOH; RAI, SURESH; LAZARESCU, MIHAI
- Abstract
This paper provides an algorithm to design a communication network topology with minimal cost (C) and maximum (s, t) reliability (R) subject to a predefined 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.
- Subjects
WIRELESS communications; COMPUTER network reliability; DYNAMIC programming; TOPOLOGY; HEURISTIC
- Publication
International Journal of Performability Engineering, 2015, Vol 11, Issue 3, p265
- ISSN
0973-1318
- Publication type
Article