Дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі
The article is devoted to the study of the optimization problem for the hierarchical structure of a multicommodity communication network with discrete flows and parameters when its density changes (the ratio of the number of network arcs to the maximum possible number of arcs for a given number of n...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2023
|
| Теми: | |
| Онлайн доступ: | https://jais.net.ua/index.php/files/article/view/41 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems of Control and Informatics |
Репозитарії
Problems of Control and Informatics| id |
oai:ojs2.jais.net.ua:article-41 |
|---|---|
| record_format |
ojs |
| institution |
Problems of Control and Informatics |
| baseUrl_str |
|
| datestamp_date |
2024-06-04T17:36:25Z |
| collection |
OJS |
| language |
Russian |
| topic |
ієрархічні комунікаційні мережі дискретні потоки і параметри задачі оптимізації комп’ютерне моделювання |
| spellingShingle |
ієрархічні комунікаційні мережі дискретні потоки і параметри задачі оптимізації комп’ютерне моделювання Trofymchuk, Aleksandr Vasyanin, Vladymyr Ushakova, Lyudmila Дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі |
| topic_facet |
ієрархічні комунікаційні мережі дискретні потоки і параметри задачі оптимізації комп’ютерне моделювання hierarchical communication networks discrete flows and parameters optimization problems computer modeling иерархические коммуникационные сети дискретные потоки и параметры задачи оптимизации компьютерное моделирование |
| format |
Article |
| author |
Trofymchuk, Aleksandr Vasyanin, Vladymyr Ushakova, Lyudmila |
| author_facet |
Trofymchuk, Aleksandr Vasyanin, Vladymyr Ushakova, Lyudmila |
| author_sort |
Trofymchuk, Aleksandr |
| title |
Дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі |
| title_short |
Дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі |
| title_full |
Дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі |
| title_fullStr |
Дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі |
| title_full_unstemmed |
Дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі |
| title_sort |
дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі |
| title_alt |
Research the problem of optimizing the hierarchical structure of a sparse and dense communication network Исследование задачи оптимизации иерархической структуры разреженной и плотной коммуникационной сети |
| description |
The article is devoted to the study of the optimization problem for the hierarchical structure of a multicommodity communication network with discrete flows and parameters when its density changes (the ratio of the number of network arcs to the maximum possible number of arcs for a given number of nodes in the network). The network has three levels of hierarchy — a backbone, a zonal and a internal and four types of nodes — backbone nodes of the first, second and third types, forming the backbone and zonal levels of the network, and nodes of the fourth type, which subordinate to each backbone node and form the internal levels of the network. The types of nodes different from one another in functionality. The main task of the study is to establish how the structure of the backbone network changes (the number and location of backbone nodes of the first, second and third types), the scheme of processing and distribution of flows and technical and economic indicators of the network's functioning for various degrees of its density. The principles of organizing the sorting and distribution of flows in a three-level network and its mathematical model are given. A mathematical model of the problem of optimizing the structure of the backbone network and the schemes of sorting and distribution of flows is formulated. The algorithms for solving the problem are based on the discrete analogue of the local descent method proposed earlier by the authors, when the neighborhoods of the metric space of possible solutions are chosen from heuristic considerations, taking into account the peculiarities of the problem being solved. Computer modeling of the problem on a homogeneous network containing 100 nodes with a change in the degree of nodes from 2 to 99 is carried out. The modeling was carried out on the example of a road transport network for the transportation of cargo using a computer program, which is part of the instrumental software of the Information and Analytical Decision Support System (IA DSS), which is being developed at the Institute of Telecommunications and Global Information Space of the National Academy of Sciences of Ukraine. An experimental study of the solution to the problem showed that the best technical, economic and operational indicators of its functioning are achieved with a degree nodes from 9 to 14, when high network connectivity is ensured, and is significantly reduced the average and maximum time of delivery of cargos to recipients. The proposed computer technology for solving problem with changing network density allows you to interactively modeling various options of a network , changing the topology, hierarchical structure, flows, parameters and constraints of the model and from the family of the resived results choose the best option, taking into account the selected a goal function and the accepted constraints; calculate preliminary technical and economic indicators of the network's functioning, estimate the cost of additional resources and plan the amount of investment required for the modernization and construction of its structural elements, which ultimately makes it possible to increase the efficiency functioning of the network by optimizing use of its resources and reducing the operating costs for the processing and transportation of flows. |
| publisher |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine |
| publishDate |
2023 |
| url |
https://jais.net.ua/index.php/files/article/view/41 |
| work_keys_str_mv |
AT trofymchukaleksandr researchtheproblemofoptimizingthehierarchicalstructureofasparseanddensecommunicationnetwork AT vasyaninvladymyr researchtheproblemofoptimizingthehierarchicalstructureofasparseanddensecommunicationnetwork AT ushakovalyudmila researchtheproblemofoptimizingthehierarchicalstructureofasparseanddensecommunicationnetwork AT trofymchukaleksandr issledovaniezadačioptimizaciiierarhičeskojstrukturyrazrežennojiplotnojkommunikacionnojseti AT vasyaninvladymyr issledovaniezadačioptimizaciiierarhičeskojstrukturyrazrežennojiplotnojkommunikacionnojseti AT ushakovalyudmila issledovaniezadačioptimizaciiierarhičeskojstrukturyrazrežennojiplotnojkommunikacionnojseti AT trofymchukaleksandr doslídžennâzadačíoptimízacíííêrarhíčnoístrukturirozrídženoííŝílʹnoíkomuníkacíjnoímereží AT vasyaninvladymyr doslídžennâzadačíoptimízacíííêrarhíčnoístrukturirozrídženoííŝílʹnoíkomuníkacíjnoímereží AT ushakovalyudmila doslídžennâzadačíoptimízacíííêrarhíčnoístrukturirozrídženoííŝílʹnoíkomuníkacíjnoímereží |
| first_indexed |
2025-10-30T02:48:32Z |
| last_indexed |
2025-10-30T02:48:32Z |
| _version_ |
1847373345446690816 |
| spelling |
oai:ojs2.jais.net.ua:article-412024-06-04T17:36:25Z Research the problem of optimizing the hierarchical structure of a sparse and dense communication network Исследование задачи оптимизации иерархической структуры разреженной и плотной коммуникационной сети Дослідження задачі оптимізації ієрархічної структури розрідженої і щільної комунікаційної мережі Trofymchuk, Aleksandr Vasyanin, Vladymyr Ushakova, Lyudmila ієрархічні комунікаційні мережі дискретні потоки і параметри задачі оптимізації комп’ютерне моделювання hierarchical communication networks discrete flows and parameters optimization problems computer modeling иерархические коммуникационные сети дискретные потоки и параметры задачи оптимизации компьютерное моделирование The article is devoted to the study of the optimization problem for the hierarchical structure of a multicommodity communication network with discrete flows and parameters when its density changes (the ratio of the number of network arcs to the maximum possible number of arcs for a given number of nodes in the network). The network has three levels of hierarchy — a backbone, a zonal and a internal and four types of nodes — backbone nodes of the first, second and third types, forming the backbone and zonal levels of the network, and nodes of the fourth type, which subordinate to each backbone node and form the internal levels of the network. The types of nodes different from one another in functionality. The main task of the study is to establish how the structure of the backbone network changes (the number and location of backbone nodes of the first, second and third types), the scheme of processing and distribution of flows and technical and economic indicators of the network's functioning for various degrees of its density. The principles of organizing the sorting and distribution of flows in a three-level network and its mathematical model are given. A mathematical model of the problem of optimizing the structure of the backbone network and the schemes of sorting and distribution of flows is formulated. The algorithms for solving the problem are based on the discrete analogue of the local descent method proposed earlier by the authors, when the neighborhoods of the metric space of possible solutions are chosen from heuristic considerations, taking into account the peculiarities of the problem being solved. Computer modeling of the problem on a homogeneous network containing 100 nodes with a change in the degree of nodes from 2 to 99 is carried out. The modeling was carried out on the example of a road transport network for the transportation of cargo using a computer program, which is part of the instrumental software of the Information and Analytical Decision Support System (IA DSS), which is being developed at the Institute of Telecommunications and Global Information Space of the National Academy of Sciences of Ukraine. An experimental study of the solution to the problem showed that the best technical, economic and operational indicators of its functioning are achieved with a degree nodes from 9 to 14, when high network connectivity is ensured, and is significantly reduced the average and maximum time of delivery of cargos to recipients. The proposed computer technology for solving problem with changing network density allows you to interactively modeling various options of a network , changing the topology, hierarchical structure, flows, parameters and constraints of the model and from the family of the resived results choose the best option, taking into account the selected a goal function and the accepted constraints; calculate preliminary technical and economic indicators of the network's functioning, estimate the cost of additional resources and plan the amount of investment required for the modernization and construction of its structural elements, which ultimately makes it possible to increase the efficiency functioning of the network by optimizing use of its resources and reducing the operating costs for the processing and transportation of flows. Статья посвящена исследованию задачи оптимизации иерархической структуры многопродуктовой коммуникационной сети с дискретными потоками и параметрами при изменении ее плотности (отношение количества дуг сети к максимально возможному количеству дуг для заданного числа узлов в сети). В сети выделены три уровня иерархии – магистральный, зональный и внутренний, и четыре типа узлов – первого, второго и третьего типа, образующие магистральный и зональный уровни сети, и узлы четвертого типа, подчиненные каждому магистральному узлу и образующие внутренние уровни сети. Типы узлов отличаются друг от друга функциональными возможностями. Основная задача исследования – установить, как изменяется структура магистральной сети (количество и расположение магистральных узлов первого, второго и третьего типа), схема обработки и распределения потоков и технико-экономические показатели функционирования сети для разной степени ее плотности. Приведены принципы сортировки и распределения потоков в иерархической сети и ее математической модели. Сформулирована математическая модель задачи оптимизации структуры магистральной сети и схемы сортировки и распределения потоков. Алгоритмы решения задачи основаны на предложенном ранее авторами дискретном аналоге метода локального спуска, когда окрестности метрического пространства возможных решений выбираются из эвристических соображений с учетом особенностей решаемой задачи. Проведено компьютерное моделирование задачи на однородной сети, содержащей 100 узлов при изменении степени узлов от 2 до 99. Моделирование проводилось на примере автотранспортной сети перевозки грузов с помощью компьютерной программы, являющейся частью инструментальных программных средств информационно-аналитической системы поддержки принятия решений (ИАС ППР), разрабатываемой в Институте телекоммуникаций и глобального информационного пространства НАН Украины. Экспериментальное исследование решения задачи показало, что лучшие технико-экономические и эксплуатационные показатели ее функционирования достигаются при степени узлов сети от 9 до 14, когда обеспечивается высокая связность сети и значительно сокращается среднее и максимальное время доставки грузов получателям. Предлагаемая компьютерная технология решения задачи при изменении плотности сети позволяет проектировщику в интерактивном режиме моделировать разные варианты сети, изменяя топологию, иерархическую структуру, потоки, параметры и ограничения модели; из полученных результатов выбирать наилучший на основе выбранной функции цели и принятых ограничений; рассчитывать предварительные технико-экономические показатели функционирования сети; оценивать стоимость дополнительных ресурсов для планирования величины нужных инвестиций на модернизацию и строительство ее структурных элементов, что позволяет повысить эффективность функционирования сети за счет оптимизации использования ее ресурсов и снижения эксплуатационных затрат на обработку и транспортировку потоков. Статтю присвячено дослідженню задачі оптимізації ієрархічної структури багатопродуктової комунікаційної мережі з дискретними потоками і параметрами при зміні її щільності (відношення кількості дуг мережі до максимально можливої кількості дуг для заданого числа вузлів у мережі). У мережі виділено три рівня ієрархії — магістральний, зональний і внутрішній, та чотири типи вузлів — першого, другого і третього типу, що утворюють магістральний і зональний рівні мережі, і вузли четвертого типу, які підлеглі кожному магістральному вузлу і утворюють внутрішні рівні мережі. Типи вузлів відрізняються один від одного функціональними можливостями. Основне завдання дослідження — встановити, як змінюється структура магістральної мережі (кількість і розташування магістральних вузлів першого, другого і третього типу), схема обробки і розподілу потоків і техніко-економічні показники функціонування мережі для різного ступеня її щільності. Наведено принципи сортування і розподілу потоків у ієрархічній мережі та її математичну модель. Сформульовано математичну модель задачі оптимізації структури магістральної мережі та схеми сортування і розподілу потоків. Алгоритми розв’язання задачі засновано на запропонованому раніше авторами дискретному аналогу методу локального спуску, коли околиці метричного простору можливих розв’язків вибираються з евристичних міркувань з урахуванням особливостей розв’язуваної задачі. Проведено комп’ютерне моделювання задачі на однорідній мережі, що містить 100 вузлів при зміні ступеня вузлів від 2 до 99. Моделювання проводилось на прикладі автотранспортної мережі перевезення вантажів за допомогою комп’ютерної програми, яка є частиною інструментальних програмних засобів інформаційно-аналітичної системи підтримки прийняття рішень (ІАС ППР), яка розробляється в Інституті телекомунікацій і глобального інформаційного простору НАН України. Експериментальне дослідження розв’язання задачі показало, що найкращі техніко-економічні та експлуатаційні показники її функціонування досягаються при ступеню вузлів мережі від 9 до 14, коли забезпечується висока зв’язність мережі і значно скорочується середній і максимальний час доставки вантажів одержувачам. Запропонована комп’ютерна технологія розв’язання задачі при зміні щільності мережі дозволяє проектувальнику в інтерактивному режимі моделювати різні варіанти мережі, змінюючи топологію, ієрархічну структуру, потоки, параметри і обмеження моделі; з отриманих результатів вибирати найкращий з урахуванням обраної функції мети і прийнятих обмежень; розраховувати попередні техніко-економічні показники функціонування мережі; оцінювати вартість додаткових ресурсів для планування величини потрібних інвестицій на модернізацію та будівництво її структурних елементів, що в результаті дозволяє підвищити ефективність функціонування мережі за рахунок оптимізації використання її ресурсів та зниження експлуатаційних витрат на обробку і транспортування потоків. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2023-06-05 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/41 10.34229/1028-0979-2021-1-1 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 66 № 1 (2021): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 5-21 International Scientific Technical Journal "Problems of Control and Informatics; Том 66 № 1 (2021): International Scientific Technical Journal "Problems of Control and Informatics"; 5-21 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 66 No. 1 (2021): International Scientific Technical Journal "Problems of Control and Informatics"; 5-21 2786-6505 2786-6491 10.34229/1028-0979-2021-1 ru https://jais.net.ua/index.php/files/article/view/41/59 Copyright (c) 2020 Aleksandr Trofimchuk, Vladymyr Vasyanin, Lyudmila Ushakova https://creativecommons.org/licenses/by-nc-nd/4.0/ |