Topology Design with Minimal Cost Subject to Network Reliability Constraint
| العنوان: | Topology Design with Minimal Cost Subject to Network Reliability Constraint |
|---|---|
| المؤلفون: | Mihai Lazarescu, Sieteng Soh, Basima Elshqeirat, Suresh Rai |
| المصدر: | IEEE Transactions on Reliability. 64:118-131 |
| بيانات النشر: | Institute of Electrical and Electronics Engineers (IEEE), 2015. |
| سنة النشر: | 2015 |
| مصطلحات موضوعية: | Combinatorics, Discrete mathematics, Computational topology, Spanning tree, Grid network, Heuristic, Extension topology, Topology (electrical circuits), Electrical and Electronic Engineering, Safety, Risk, Reliability and Quality, Network topology, Time complexity, Mathematics |
| الوصف: | This paper addresses an NP-hard problem, refered 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, ${\rm STX}_{min}$ . 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 ${\rm STX}_{min}$ 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\times 10^{9}$ spanning trees show the merits of using the ordering methods and the effectiveness of our algorithm vis-a-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 $\,\times\,$ 100 grid network that contains up to $1.899^{102}$ 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. |
| تدمد: | 1558-1721 0018-9529 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::3e09a6063ec216807c823f7c0b923410 https://doi.org/10.1109/tr.2014.2338253 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi...........3e09a6063ec216807c823f7c0b923410 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 15581721 00189529 |
|---|