Tree-based access network design under requirements for an aggregation network

• Autorzy: Czajko M. M. , Wojciechowski J.

Warianty tytułu

PL

Projektowanie sieci dostępowej o strukturze drzewiastej z uwzględnieniem wymagań nałożonych na sieć agregującą

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

access network design; multiple criteria problem; heuristics

PL

projektowanie sieci dostępowej; problem optymalizacji wielokryterialnej; metody heurystyczne

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2009
• Tom: Vol. 50, nr 4
• Strony: 23--27
• Opis fizyczny: Bibliogr. 10 poz., tab.

Twórcy

autor

Czajko M. M.

autor

Wojciechowski J.

• Telekomunikacja Polska S. A.

Bibliografia

• [1] Baños R., Gil C., Paechter B., Ortega J.: Parallelization of population-based multi-objective meta-heuristics: An empirical study. Applied Mathematical Modelling 30 (2006) 578-592.
• [2] Chankong V., Haimes Y. Y., Multiobjective decision making theory and methodology. ISBN: 9780444007100, North-Holland, New York, 1983.
• [3] da Cunha A. S., Lucena A.: Algorithms for the degree-constrained minimum spanning tree problem. Electronic Notes in Discrete Mathematics 19 (2005) 403-409.
• [4] Duh J.-D., Brown D. G.: Knowledge-informed Pareto simulated annealing for multi-objective spatial allocation. Computers, Environment and Urban Systems 31 (2007) 253-281.
• [5] Gouveia L.: Using the Miller-Tucker-Zemlin constraints to formulate minimal spanning trees with hop constraints. Computers and Operations Research 22 (1995) 959-970.
• [6] Gouveia L.: Multicommodity flow models for spanning trees with hop constraints. European Journal of Operational Research 95 (1996) 178-190.
• [7] Leblanc L., Reddoch R.: Reliable link topology/capacity design and routing in backbone telecommunication networks. Paper presented at the First ORSA Telecommunications SIG Conference "Operations Research in Telecommunications", 1990.
• [8] Pióro M., Medhi D., Routing, flow, and capacity design in communication and computer networks, ISBN: 0-12-557189-5, Elsevier, 2004.
• [9] Rahimi-Vahed A. R., Rabbani M.: Tavakkoli-Moghaddam R., Torabi S. A., Jolai R.: A multi-objective scatter search for a mixed-model assembly line sequencing problem. Advanced Engineering Informatics 21 (2007) 85-99.
• [10] Zhou G., Gen M.: Generic algorithm approach on multi-criteria minimum spanning tree problem. European Journal of Operational Research 114(1999) 141-152.