Heuristic algorithms for finding the minimum Steiner tree in the problem of optimizing the deployment and motion control of several flying information and telecommunication robots

Скорочена інформація про документ
dc.contributor.authorLysenko, Olexandr
dc.contributor.authorValuiskyi, Stanislav
dc.contributor.authorNovikov, Valeriy
dc.contributor.authorSushyn, Ihor
dc.contributor.authorChumachenko, Serhii
dc.contributor.authorGuida, Oleksandr
dc.date.accessioned2023-04-03T08:49:02Z
dc.date.available2023-04-03T08:49:02Z
dc.date.issued2022
dc.description.abstractBackground. The article explores the problem of combining the motion control of existing FITRs and the deployment of new FITRs so that the number of new FITRs deployed to support the communication of terrestrial subscribers can be minimized. This problem is formulated as the Steiner Minimum Tree Problem (SMT) with existing mobile Steiner points with a constraint on the edges length of the network graph. Objective. Improve the mathematical model for ensuring the connectivity of episodic radio networks using FITRs and improve the algorithms for providing the connectivity of episodic radio networks using FITRs. Methods. The two algorithms (deploying new FITRs before moving existing FITRs, and moving existing FITRs before deployment of new FITRs) separate the problem and solve the deployment problem, the movement one after the other. In contrast, the algorithm for deploying new FITRs while moving existing FITRs optimizes the deployment problem and the control of movement across and solves these two problems simultaneously. Results. A proposed method includes three heuristic algorithms for placing new FITRs, taking into account the movement of existing FITRs (that is, considering scenarios for moving existing FITRs: deploying new FITRs before, after, or during the movement of existing FITRs) for the SMT problem with existing mobile Steiner points with a constraint on the edges length of the network graph. Conclusions. Evaluation of the effectiveness of the proposed algorithms in various scenarios shows that algorithms taking into account the movement of existing FITRs are always more efficient (in terms of the number of newly added FITRs) than an algorithm without taking into account the movement of existing FITRs.uk
dc.description.abstractotherМета дослідження. Удосконалити математичну модель забезпечення зв’язку епізодичних радіомереж з використанням ЛІТР та вдосконалити алгоритми забезпечення зв’язку епізодичних радіомереж із використанням ЛІТР. Методика реалізації. Два алгоритми: розгортання нових ЛІТР до початку переміщення існуючих ЛІТР і переміщення існуючих ЛІТР до початку розгортання нових ЛІТР розділяють проблему та вирішують проблему розгортання, переміщення одна за одною, тоді як алгоритм розгортання нових ЛІТР під час переміщення існуючих ЛІТР оптимізує проблему розгортання та керування рухом поперек і вирішує ці дві проблеми одночасно. Результати дослідження. Запропоновано метод, який включає три евристичні алгоритми розміщення нових ЛІТР з урахуванням переміщення існуючих ЛІТР для задачі МДШ з існуючими мобільними точками Штейнера із обмеженням довжини ребер графу мережі: алгоритми розгортання нових ЛІТР до початку переміщення існуючих ЛІТР, переміщення існуючих ЛІТР до початку розгортання нових ЛІТР і розгортання нових ЛІТР під час переміщення існуючих ЛІТР. Висновки. Оцінка ефективності запропонованих алгоритмів у різних сценаріях свідчить, що алгоритми з урахуванням переміщення існуючих ЛІТР завжди мають кращу продуктивність, ніж алгоритм без урахування переміщення існуючих ЛІТР з точки зору кількості нових доданих ЛІТР. Серед трьох алгоритмів розміщення нових ЛІТР з урахуванням переміщення існуючих ЛІТР, алгоритм переміщення існуючих ЛІТР до початку розгортання нових ЛІТР кращий за алгоритм розгортання нових ЛІТР до початку переміщення існуючих ЛІТР у більшості сценаріїв, а алгоритм розгортання нових ЛІТР під час переміщення існуючих ЛІТР завжди має найкращу ефективність у всіх сценаріях.uk
dc.format.pagerangePp. 53-61uk
dc.identifier.citationHeuristic algorithms for finding the minimum Steiner tree in the problem of optimizing the deployment and motion control of several flying information and telecommunication robots / Stanislav V. Valuiskyi, Olexandr I. Lysenko, Serhii M. Chumachenko, Valeriy I. Novikov, 3 Oleksandr G. Guida, Ihor O. Sushyn // Information and telecommunication sciences : international research journal. – 2022. – Vol. 13, N. 2. – Pp. 53-61. – Bibliogr.: 7 ref.uk
dc.identifier.doihttps://doi.org/10.20535/2411-2976.22022.53-61
dc.identifier.orcid0000-0002-7276-9279uk
dc.identifier.orcid0000-0002-6625-9969uk
dc.identifier.orcid0000-0003-4199-9968uk
dc.identifier.orcid0000-0003-4866-4351uk
dc.identifier.orcid0000-0002-8894-4262uk
dc.identifier.orcid0000-0002-2019-2615uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/54193
dc.language.isoenuk
dc.publisherNational Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"uk
dc.publisher.placeKyivuk
dc.relation.ispartofInformation and telecommunication sciences : international research journal, 2022, Vol. 13, N. 2(22)uk
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectflying information and telecommunication robotsuk
dc.subjectлітаючі інформаційно-телекомунікаційні роботиuk
dc.subjectmobile episodic radio networkuk
dc.subjectмобільна епізодична радіомережаuk
dc.subjectalgorithmuk
dc.subjectалгоритмuk
dc.subjecttopologyuk
dc.subjectтопологіяuk
dc.subjectlocationuk
dc.subjectрозміщенняuk
dc.subject.udc621.396.4uk
dc.titleHeuristic algorithms for finding the minimum Steiner tree in the problem of optimizing the deployment and motion control of several flying information and telecommunication robotsuk
dc.title.alternativeЕвристичні алгоритми пошуку мінімального дерева Штейнера в задачі оптимізації розгортання та керування рухом кількох літаючих інформаційно-телекомунікаційних роботівuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
269102-620670-1-10-20221216.pdf
Розмір:
1.61 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.1 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Information and telecommunication sciences: international research journal, Vol. 13, N. 2