Tree-like structures in telecommunications networks topology are taking on large importance because of their simplicity and relatively low cost. Most network operators build access networks in the tree topology taking into account its cost, robustness to failures, traffic delay introduced by the access network, and modularity of nodes. This article gives a new look on the topological, tree-based access network design. We define the so-called hop and degree constrained minimum spanning forest problem with minimization of the number of trees (HDMSFMT). A bi-criteria HDMSFMT optimization problem is an extension of the well-known formulation of the hop and degree constrained minimum spanning tree problem. It is shown in this paper that HDMSFMT is NP-hard. Two multi-objective heuristics are proposed. A numerical study for the problem of practical sizes is also presented in the paper.
PL
Struktury drzewiaste odgrywają istotną rolę przy projektowaniu sieci telekomunikacyjnych ze względu na swoją prostotę i związany z nimi stosunkowo niski koszt. Większość operatorów telekomunikacyjnych buduje sieci dostępowe o topologii drzewa biorąc pod uwagę koszt, awaryjność, opóźnienie wprowadzane przez sieć dostępowąoraz modularność węzłów. Niniejszy artykuł przedstawia nowy sposób spojrzenia na topologiczne projektowanie sieci dostępowej o architekturze drzewiastej. W artykule zdefiniowano tzw. problem minimalnego lasu rozpinającego z minimalną liczbą drzew przy ograniczeniach na stopień wierzchołka i długość ścieżki (HDMSFMT). Ten NP-trudny, dwukryterialny problem optymalizacyjny jest rozszerzeniem bardzo dobrze znanego problemu minimalnego drzewa rozpinającego przy ograniczeniach na stopień wierzchołka i długość ścieżki. W artykule zaproponowano dwa wielokryterialne algorytmy heurystyczne i zbadano jakość uzyskanych za ich pomocą rozwiązań w zastosowaniu do problemu o praktycznych rozmiarach.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.