ЕВРИСТИЧНІ АЛГОРИТМИ ПОШУКУ МІНІМАЛЬНОГО ДЕРЕВА ШТЕЙНЕРА В ЗАДАЧІ ОПТИМІЗАЦІЇ РОЗГОРТАННЯ ТА КЕРУВАННЯ РУХОМ КІЛЬКОХ ЛІТАЮЧИХ ІНФОРМАЦІЙНО-ТЕЛЕКОМУНІКАЦІЙНИХ РОБОТІВ

Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Information and Telecommunication Sciences; No. 2 (2022); 53-61
Information and Telecommunication Sciences; № 2 (2022); 53-61
ISSN: 2312-4121
2411-2976
Popis: Background. 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.
Проблематика. У статті досліджено проблему поєднання управління рухом існуючих літаючих інформаційно-телекомунікаційних роботів (ЛІТР), мобільна епізодична радіомережа, алгоритм, топологія, розміщення ЛІТР та розгортання нових ЛІТР, щоб кількість нових розгорнутих ЛІТР для підтримки зв’язку наземних абонентів могла бути мінімізована. Дана проблема сформульована, як проблема мінімального дерева Штейнера з існуючими мобільними точками Штейнера із обмеженням довжини ребер графу мережі. Мета дослідження. Удосконалити математичну модель забезпечення зв’язку епізодичних радіомереж з використанням ЛІТР та вдосконалити алгоритми забезпечення зв’язку епізодичних радіомереж із використанням ЛІТР. Методика реалізації. Два алгоритми: розгортання нових ЛІТР до початку переміщення існуючих ЛІТР і переміщення існуючих ЛІТР до початку розгортання нових ЛІТР розділяють проблему та вирішують проблему розгортання, переміщення одна за одною, тоді як алгоритм розгортання нових ЛІТР під час переміщення існуючих ЛІТР оптимізує проблему розгортання та керування рухом поперек і вирішує ці дві проблеми одночасно. Результати дослідження. Запропоновано метод, який включає три евристичні алгоритми розміщення нових ЛІТР з урахуванням переміщення існуючих ЛІТР для задачі МДШ з існуючими мобільними точками Штейнера із обмеженням довжини ребер графу мережі: алгоритми розгортання нових ЛІТР до початку переміщення існуючих ЛІТР, переміщення існуючих ЛІТР до початку розгортання нових ЛІТР і розгортання нових ЛІТР під час переміщення існуючих ЛІТР. Висновки. Оцінка ефективності запропонованих алгоритмів у різних сценаріях свідчить, що алгоритми з урахуванням переміщення існуючих ЛІТР завжди мають кращу продуктивність, ніж алгоритм без урахування переміщення існуючих ЛІТР з точки зору кількості нових доданих ЛІТР. Серед трьох алгоритмів розміщення нових ЛІТР з урахуванням переміщення існуючих ЛІТР, алгоритм переміщення існуючих ЛІТР до початку розгортання нових ЛІТР кращий за алгоритм розгортання нових ЛІТР до початку переміщення існуючих ЛІТР у більшості сценаріїв, а алгоритм розгортання нових ЛІТР під час переміщення існуючих ЛІТР завжди має найкращу ефективність у всіх сценаріях.
Databáze: OpenAIRE
Externí odkaz: