Topology Design with Minimal Cost Subject to Network Reliability Constraint
This paper addresses an NP-hard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTD-CR), to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. The paper describes a dynamic programming (DP)...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
IEEE
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/29768 |
| _version_ | 1848752894190288896 |
|---|---|
| author | Elshqeirat, Basima Soh, Sieteng Rai, S. Lazarescu, M. |
| author_facet | Elshqeirat, Basima Soh, Sieteng Rai, S. Lazarescu, M. |
| author_sort | Elshqeirat, Basima |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper addresses an NP-hard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTD-CR), to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. The paper describes a dynamic programming (DP) scheme to solve the NTD-CR problem, and proposes a DP approach, called Dynamic Programming Algorithm to solve NTD-CR (DPCR-ST), to generate the topology using a selected sequence of spanning trees of the network, STXmin. The paper shows that our DPCR-ST approach always provides a feasible solution, and produces an optimal topology given an optimal order of spanning trees. The paper proves that the problem of optimally ordering the spanning trees is NP-complete, and proposes three greedy heuristics to generate and order only k spanning trees of the network. Each heuristic allows the DPCR-ST approach to generate STXmin using only k spanning trees, which improves the time complexity while producing a near optimal topology. Simulations based on fully connected networks that contain up to 2.3×109 spanning trees show the merits of using the ordering methods and the effectiveness of our algorithm vis-à-vis to four existing state-of-the-art techniques. Our DPCR-ST approach is able to generate 81.5% optimal results, while using only 0.77% of the spanning trees contained in networks. Further, for a typical 2 × 100 grid network that contains up to 1.899102 spanning trees, DPCR-ST approach requires only k=1214 spanning trees to generate a topology with a reliability no larger than 5.05% off from optimal. |
| first_indexed | 2025-11-14T08:15:52Z |
| format | Journal Article |
| id | curtin-20.500.11937-29768 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:15:52Z |
| publishDate | 2015 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-297682017-09-13T15:26:23Z Topology Design with Minimal Cost Subject to Network Reliability Constraint Elshqeirat, Basima Soh, Sieteng Rai, S. Lazarescu, M. network reliability network optimization network topology design Dynamic programming This paper addresses an NP-hard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTD-CR), to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. The paper describes a dynamic programming (DP) scheme to solve the NTD-CR problem, and proposes a DP approach, called Dynamic Programming Algorithm to solve NTD-CR (DPCR-ST), to generate the topology using a selected sequence of spanning trees of the network, STXmin. The paper shows that our DPCR-ST approach always provides a feasible solution, and produces an optimal topology given an optimal order of spanning trees. The paper proves that the problem of optimally ordering the spanning trees is NP-complete, and proposes three greedy heuristics to generate and order only k spanning trees of the network. Each heuristic allows the DPCR-ST approach to generate STXmin using only k spanning trees, which improves the time complexity while producing a near optimal topology. Simulations based on fully connected networks that contain up to 2.3×109 spanning trees show the merits of using the ordering methods and the effectiveness of our algorithm vis-à-vis to four existing state-of-the-art techniques. Our DPCR-ST approach is able to generate 81.5% optimal results, while using only 0.77% of the spanning trees contained in networks. Further, for a typical 2 × 100 grid network that contains up to 1.899102 spanning trees, DPCR-ST approach requires only k=1214 spanning trees to generate a topology with a reliability no larger than 5.05% off from optimal. 2015 Journal Article http://hdl.handle.net/20.500.11937/29768 10.1109/TR.2014.2338253 IEEE fulltext |
| spellingShingle | network reliability network optimization network topology design Dynamic programming Elshqeirat, Basima Soh, Sieteng Rai, S. Lazarescu, M. Topology Design with Minimal Cost Subject to Network Reliability Constraint |
| title | Topology Design with Minimal Cost Subject to Network Reliability Constraint |
| title_full | Topology Design with Minimal Cost Subject to Network Reliability Constraint |
| title_fullStr | Topology Design with Minimal Cost Subject to Network Reliability Constraint |
| title_full_unstemmed | Topology Design with Minimal Cost Subject to Network Reliability Constraint |
| title_short | Topology Design with Minimal Cost Subject to Network Reliability Constraint |
| title_sort | topology design with minimal cost subject to network reliability constraint |
| topic | network reliability network optimization network topology design Dynamic programming |
| url | http://hdl.handle.net/20.500.11937/29768 |