Тополого-комбінаторна модель побудови мереж для транспортних засобів
Запропоновано модель побудови радіомережі та визначення маршрутів руху для гетерогенних груп безпілотних апаратів (БПА), безпілотних наземних роботів, надводних безпілотних транспортних засобів та змістовну постановку проблеми оптимізації системи, що складається з БПА і рухомих пунктів керування. Сп...
Gespeichert in:
| Veröffentlicht in: | Компьютерная математика |
|---|---|
| Datum: | 2018 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/161850 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Тополого-комбінаторна модель побудови мереж для транспортних засобів / В.Ю. Корольов, О.М. Ходзінський // Компьютерная математика. — 2018. — № 1. — С. 61-67. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860238319728721920 |
|---|---|
| author | Корольов, В.Ю. Ходзінський, О.М. |
| author_facet | Корольов, В.Ю. Ходзінський, О.М. |
| citation_txt | Тополого-комбінаторна модель побудови мереж для транспортних засобів / В.Ю. Корольов, О.М. Ходзінський // Компьютерная математика. — 2018. — № 1. — С. 61-67. — Бібліогр.: 10 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Запропоновано модель побудови радіомережі та визначення маршрутів руху для гетерогенних груп безпілотних апаратів (БПА), безпілотних наземних роботів, надводних безпілотних транспортних засобів та змістовну постановку проблеми оптимізації системи, що складається з БПА і рухомих пунктів керування. Спеціальна мережа призначена для розгортання у польових умовах відповідно до поставленої задачі, наявних обчислювально-комунікаційних ресурсів та динаміки зміни ситуації.
Предложено модель построения радиосети и определения маршрутов движения для гетерогенных групп беспилотных аппаратов (БПА), беспилотных наземных роботов, надводных беспилотных транспортных средств и содержательную постановку проблемы оптимизации системы, которая состоит из БПА и подвижных пунктов управления. Специальная сеть предназначена для разворачивания в полевых условиях соответственно поставленной задаче наличных коммуникационных ресурсов и динамики изменения ситуации.
The growth of the number of different types of uninhabited vehicle (UV) generates the problem of optimizing their interaction and remote control in a dynamic environment. The paper proposes a model of radio network synthesis and traffic routes for heterogeneous groups of the UV and a meaningful statement of the optimization problem of a system consisting of UVs and moving control station.
|
| first_indexed | 2025-12-07T18:27:12Z |
| format | Article |
| fulltext |
ISSN 2616-938Х. Компьютерная математика. 2018, № 1 61
Запропоновано модель побудови
радіомережі та визначення мар-
шрутів руху для гетерогенних
груп безпілотних апаратів (БПА),
безпілотних наземних роботів,
надводних безпілотних транспо-
ртних засобів та змістовну по-
становку проблеми оптимізації
системи, що складається з БПА
і рухомих пунктів керування. Спе-
ціальна мережа призначена для
розгортання у польових умовах
відповідно до поставленої задачі,
наявних обчислювально-комуніка-
ційних ресурсів та динаміки зміни
ситуації.
В.Ю. Корольов,
О.М. Ходзінський, 2018
УДК 004.94
В.Ю. КОРОЛЬОВ, О.М. ХОДЗІНСЬКИЙ
ТОПОЛОГО-КОМБІНАТОРНА
МОДЕЛЬ ПОБУДОВИ МЕРЕЖ
ДЛЯ ТРАНСПОРТНИХ ЗАСОБІВ
Вступ. Сучасний розвиток безпровідних ра-
діомереж дозволяє об’єднати дистанційно
керовані безпілотні апарати (БПА) у групи
для спільного виконання завдань. Групове
використання БПА дозволяє зменшити час
виконання завдання, повніше використовува-
ти технічні можливості кожного БПА та на
основі моделі інтегрувати гетерогенні назем-
ні, надводні безпілотні транспортні засоби
у мережі для системи збирання даних.
Загальна задача керування рухом груп
БПА розбивається на такі задачі [1 – 5]: пла-
нування шляхів БПА для обстеження терито-
ріально розподілених об’єктів, динамічного
формування мережі керування для рухомих
пунктів керування (РПК), обслуговування
споживачів інформаційних послуг і забезпе-
чення зв’язку. Математичною основою пла-
нування руху груп БПА є задача маршрути-
зації транспортних засобів [1 – 6] та задача
маршрутизація пакетів даних у безпровідних
ad hoc мережах, які в даній роботі пропону-
ється об’єднати на основі тополого-ком-
бінаторної моделі та розв’язування спеціаль-
ної задачі оптимізації.
Тополого-комбінаторна модель (ТКМ) –
це модель, що описує способи утворення
зв’язків між абонентами та сервісами за на-
явних ресурсів. Формально модель описуєть-
ся декартовим добутком, що визначає мно-
жину Q варіантів обслуговування споживачів
обчислювально-комунікаційних сервісів:
.Q R S T M
В.Ю. КОРОЛЬОВ, О.М. ХОДЗІНСЬКИЙ
62 ISSN 2616-938Х. Компьютерная математика. 2018, № 1
Тут R – множина ресурсів, S – множина обчислювально-комунікаційних сервісів
[5, 7, 8], T – множина зв’язків між споживачами технічної системи та в всереди-
ні між віртуалізованими засобами, М – множина маршрутів руху транспортних
засобів.
У множину ресурсів R входять, зокрема, побудовані на основі фізичних при-
строїв передачі та обробки інформації віртуальні комунікаційні сервери, а також
засоби захисту інформації, політики комп’ютерної безпеки мережі, протоколи,
інтерфейси. У системі хмарних сервісів такі ресурси відносяться до інфра-
стуктурного рівня її обчислювальної архітектури [7, 9, 10].
Елементи множини S – це базові програми pi, з яких можуть формуватися
підмножини jS S для виконання окремих сервісів. Для виконання задач
обслуговування абонентів сервісно-орієнтована архітектура, зокрема, має забез-
печувати можливість об’єднання декількох сервісів Sj з різних хмар.
Об’єднуватись для утворення нового агрегованого сервісу SA можуть як уні-
кальні сервіси, так і програми pi з різних сервісів:
.A j
j
S S
Множина T описує топологію мережі у вигляді зваженого графа, де верши-
ни – це абоненти або вузли мережі, а вага ребер характеризує стан каналів
зв’язку. Множина зв’язків визначається поставленими задачами, кількістю або-
нентів, швидкістю передачі даних та економічними чинниками і є розв’язком
задачі пошуку маршрутів руху пакетів даних. Для побудови множин ресурсів R,
сервісів S та зв’язків T запропонована модель використовує результати теорії
масового обслуговування, моделювання агрегативних систем, транспортних
систем та автоматизованих систем керування.
Множина М включає можливі шляхи руху абонентів спеціальної мережі [8].
Отримана множина комбінацій варіантів обслуговування Q є основою для
змістовної постановки задачі оптимізації обслуговування множини абонентів та
описаної вище транспортно-комунікаційної задачі для групи БПА і РПК, а також
синтезу складних технічних систем, що складаються з рухомих роботизованих
систем і рухомих пунктів керування.
Синтез локальної мережі транспортних засобів. Прикладним застосуван-
ня тополого-комінаторної моделі (ТКМ) мережі є опис радіомережі (безпровід-
ної мережі), що динамічно утворюється лініями зв’язку. Стан ліній зв’язку між
абонентами групи БПА змінюється в залежності від задач, середовища поши-
рення радіохвиль та типу інформації, що передається мережею. Топологія мере-
жі описується зваженим зв’язним графом. Для випадків, що потребують підви-
щеної надійності зв’язку, синтезують мережу, що описується повним графом
(чарункова безпровідна мережа). Завдяки цому досягається безперервність обмі-
ну даними за рахунок багатократного резервування каналів передачі даних. Вага
ТОПОЛОГО-КОМБІНАТОРНА МОДЕЛЬ ПОБУДОВИ МЕРЕЖ ...
ISSN 2616-938Х. Компьютерная математика. 2018, № 1 63
дуг між двома вузлами відповідає потужності радіосигналу між двома БПА.
Вершини графу – це БПА або програмний пульт керування на РПК. Маршрути
руху пакетів даних – оптимальні комбінації дуг з меншою вагою, що розрахо-
вуються за потужністю радіосигналів для максимальної продуктивності передачі
даних у мережі.
Наприклад, алгоритм повного перебору може використовуватись для мережі
з 4-х БПА, а для мережі 8-ми БПА використовувався алгоритм Дейкстри. Задача
передачі пакетів даних допускає постановку у вигляді комбінаторної задачі
оптимізації [1 – 8] – задачі маршрутизації. Для загального випадку і великої роз-
мірності мережі прикладне застосування ТКМ потребує відповідної високо-
рівневої обчислювальної архітектури, типу ІЕЕЕ 1516 [4, 7].
Етапи синтезу мережі та постановка задачі оптимізації. Задача синтезу
мережі для транспортних засобів на основі ТК-моделі розділяється на три задачі
(рис. 1), що виконуються послідовно: аналіз можливостей і завдань системи на
основі ресурсів та сервісів, що виконується на пункті керування (наземна стан-
ція керування), синтез топології мережі та конфігурування й адаптивне налаш-
тування систем обробки даних, які надають вхідні дані для розв’язку задачі ком-
бінаторної оптимізації руху групи транспортних засобів.
Після розв’язання задачі синтезу мережі й побудови шляхів руху переходять
до задачі дистанційного керування. Для зменшення складності задачі керування
БПА виконують її декомпозицію на простіші менше пов’язані між собою під-
задачі [4, 5]: задачу побудови шляхів руху для БПА, задачу побудови маневрів
для автопілотування, планування фотозйомки об’єкта, задачу маршрутизації
пакетів даних у мережі [4, 8]. Перелічені задачі розв’язуються окремо різними
математичними методами.
РИС. 1. Послідовність етапів синтезу мережі та розв’язування задачі
комбінаторної оптимізації
В.Ю. КОРОЛЬОВ, О.М. ХОДЗІНСЬКИЙ
64 ISSN 2616-938Х. Компьютерная математика. 2018, № 1
Комунікаційні сервіси. Мініатюризація комунікаційних пристроїв дозволяє
отримати бортовий мережевий пристрій на одному БПА, що здатний виконувати
декілька ролей у мережі. Перелік сервісів S (рис. 1) для синтезу топології мережі
визначається переліком ролей (типів мережевих пристроїв), які здатні підтриму-
вати бортові засоби БПА, на основі яких створюється комунікаційний сервер.
Технології віртуалізації і хмарних обчислень дозволяють реалізувати наступні
ролі комунікаційного сервера: повторювач, концентратор, міст, маршрутизатор,
шлюз, комутатор. Одночасне виконання різних ролей на одній обчислювальній
архітектурі (обчислювальній платформі) забезпечується технологіями віртуалі-
зації обчислювально-комунікаційних сервісних функцій.
Типи обчислювальних платформ для розв’язування задачі. Розвиток мі-
кроелектроніки зробив системи автопілотування компактними та інтегрованими
з набором давачів, навігаційного обладнання і виконавчих механізмів, що дозво-
ляє виділити окремо задачі планування руху та комунікації у окремий рівень
і абстрагуватись від проблем маневрування та підтримки стабільності руху.
Наведемо короткий опис можливостей БПА різних розмірів.
1) малі БПА. Задача побудови шляхів руху групи БПА розв’язується на но-
утбуку, якщо малі БПА об’єднані в групу більшу десятка, то задача розв’я-
зується на польовій робочій станції. На борту кожного малого БПА є спрощений
автопілот, що дозволяє виконувати прості маневри. Задача маршрутизації паке-
тів даних розв’язується на пункті керування (ПК). Малий БПА може виконувати
функції повторювача (ретранслятора зв’язку);
2) середні БПА. Задача побудови шляхів руху групи БПА розв’язується на
робочій станції, а на їх борту є автопілот. Маршрутизація пакетів даних
розв’язується на бортовому комп’ютері БПА та на робочій станції пункту керу-
вання. Середні БПА можуть виконувати ролі ретранслятора та маршрутизатора;
3) великі БПА. Задача побудови шляхів групи БПА розв’язується на польо-
вому сервері. На борту великого БПА знаходиться мобільний комунікаційний
сервер та автопілот.
Задача оптимізація маршрутів руху декількох БПА, що дистанційно керу-
ються з РПК (рис. 2) має вирішувати питання покращення:
- планування руху груп БПА;
- планування руху груп РПК;
- маршрутизації пакетів даних у мережі БПА і РПК;
- вибору ролей комунікаційного пристрою БПА.
Далі наведено приклад змістовної постановки задачі оптимізації для
БПА і РПК.
Змістовна постановка задачі оптимізації руху групи рухомих пунктів
керування (РПК).
Вхідні дані: місця призначення, кількість РПК, ресурс ходу.
Параметри: максимальна дальність передачі сигналу в русі та зупинках;
тривалість стоянок.
ТОПОЛОГО-КОМБІНАТОРНА МОДЕЛЬ ПОБУДОВИ МЕРЕЖ ...
ISSN 2616-938Х. Компьютерная математика. 2018, № 1 65
Вихідні дані: шлях руху кожного РПК, потрібна їх кількість, якість обслуго-
вування: тривалість сеансів керування між БПА і РПК у русі та стоянці; трива-
лість часу автономного руху БПА.
Критерій: мінімізація сумарного шляху РПК та їх кількості.
Змістовна постановка задачі оптимізації руху групи БПА.
Вхідні дані: місця призначення (об’єкти, які слід відвідати), місця посадок
БПА; кількість БПА; ресурс ходу/руху БПА (кількість пального, заряд акумуля-
тора); кількість одночасно запущених БПА (кількість мобільних вузлів підтри-
муваних РПК); час підготовки до польоту (заправка баку, зарядка акумулятора).
Параметри: максимальна дальність передачі сигналу; частота опитування
БПА.
Вихідні дані: шлях руху для кожного БПА; точки створення тимчасової
ретрансляційної лінії до групи РПК.
Критерії: мінімізація сумарного шляху руху БПА та їх кількості; мінімізація
суми радіусів випромінення за лінією розмежування.
РИС. 2. Ілюстрація до змістовної постановки задачі оптимізації БПА і РПК
Зрозуміло, що задача комбінаторної оптимізації [6] буде розв’язуватись цикліч-
но і постійно, оскільки параметри мережі й руху постійно змінюються і в ре-
зультаті буде отримано наближений розв’язок.
В.Ю. КОРОЛЬОВ, О.М. ХОДЗІНСЬКИЙ
66 ISSN 2616-938Х. Компьютерная математика. 2018, № 1
Висновки.
1. Розроблено ТКМ – модель побудови радіомережі транспортних засобів
для проектування систем групового керування безпілотними транспортними
засобами. Модель ґрунтується на використанні спеціальної мережі, що дозволяє
забезпечити її керованість, надлишковість та масштабованість.
2. ТКМ призначена для розгортання адаптивної мережі, яка складається з
мобільних і стаціонарних абонентів, відповідно до поставленої задачі, наявних
обчислювально-комунікаційних ресурсів та динаміки зміни ситуації і може
керуватись як групою радіооператорів і системних адміністраторів, так і спеціа-
лізованим програмним забезпеченням.
3. Запропоновано послідовність операцій для синтезу мережі й маршрутів
руху на основі даних про ресурси та сервіси системи, що дозволяє розділити
обчислювальні процеси наземної станції від процесів на борту транспортного
засобу. Завдяки такому розділенню виконання задач збільшується адаптивність
мережі до змін середовища та збільшується кількість завдань, які може викону-
вати БПА.
4. Подано змістовну постановку задачі оптимізації для групи транспортних
засобів і рухомих пунктів керування, розв’язок якої дозволяє отримати опти-
мальну комбінацію маршрутів руху транспортних засобів за умови обмежених
ресурсів, сервісів та можливостей радіомережі.
5. Напрямом подальших досліджень є побудова моделі планування польотів
груп БПА, які частину шляху пролітають на автопілоті, та інтегральне розв’язу-
вання задачі маршрутизації з мінімізацією необхідних ретрансляцій як додатко-
вого параметру.
В.Ю. Королёв, А.Н. Ходзинский
ТОПОЛОГО-КОМБИНАТОРНАЯ МОДЕЛЬ ПОСТРОЕНИЯ СЕТЕЙ
ТРАНСПОРТНЫХ СРЕДСТВ
Предложено модель построения радиосети и определения маршрутов движения для гетеро-
генных групп беспилотных аппаратов (БПА), беспилотных наземных роботов, надводных
беспилотных транспортных средств и содержательную постановку проблемы оптимизации
системы, которая состоит из БПА и подвижных пунктов управления. Специальная сеть пред-
назначена для разворачивания в полевых условиях соответственно поставленной задаче
наличных коммуникационных ресурсов и динамики изменения ситуации.
V.Yu. Korolyov, O.M. Khodzinskyi
TOPOLOGICAL AND COMBINATORIAL MODEL FOR VEHICLE NETWORKS BUILDING
The growth of the number of different types of uninhabited vehicle (UV) generates the problem of
optimizing their interaction and remote control in a dynamic environment. The paper proposes a
model of radio network synthesis and traffic routes for heterogeneous groups of the UV and a mean-
ingful statement of the optimization problem of a system consisting of UVs and moving control
station.
ТОПОЛОГО-КОМБІНАТОРНА МОДЕЛЬ ПОБУДОВИ МЕРЕЖ ...
ISSN 2616-938Х. Компьютерная математика. 2018, № 1 67
Список літератури
1. Golden B., Raghavan S., Wasil E. The Vehicle Routing Problem: Latest Advances and New
Challenges, New York: Springer, 2008.
2. Гуляницкий Л.Ф. Проблема оптимизации маршрутов транспортных средств с временны-
ми окнами. Компьютерная математика. 2007. № 1. С. 122 – 132.
3. Корольов В.Ю., Огурцов М.І., Ходзінський О.М. Математичне моделювання маршрутів
рухомих дистанційно керованих систем та їх груп при обстеженні території. Інтелекту-
альні системи прийняття рішень і проблеми обчислювального інтелекту: Матеріали
міжнародної наукової конференції. Херсон: Видавництво ПП Вишемирський В.С., 2017.
С. 199 – 201.
4. Корольов В.Ю., Огурцов М.І. Транспортно-комунікаційна задача для груп безпілотних
апаратів. Математичні машини і системи. 2017. № 1. С. 82 – 89.
5. Огурцов М.І., Ходзінський О.М. Розробка алгоритмів розв’язання задачі маршрутизації
транспортних засобів з часовими вікнами. Компьютерная математика. 2016. № 1.
С. 134 – 142.
6. Гуляницький Л.Ф. Прикладні методи комбінаторної оптимізації: навч. посіб. / Л.Ф. Гуля-
ницький, О.Ю. Мулеса. К.: Видавничо-поліграфічний центр «Київський університет»,
2016. 133 с.
7. Корольов В.Ю., Поліновський В.В., Огурцов М.І. Моделювання мереж зв'язку рухомих
дистанційно керованих систем на базі HLA. Вісник Хмельницького національного уні-
верситету. 2017. № 1(245). С. 160 – 165.
8. Корольов В.Ю. Аналіз задачі маршрутизації для тактичних мереж сил спеціальних опе-
рацій. Інформатика, обчислювальна техніка та кібернетика: Вісник університету
«Україна». № 2(18). К.: університет «Україна», 2015. С. 64 – 76.
9. Королев В.Ю., Полиновский В.В. Синтез портабельных информационных сервисов для
флеш-накопителей. Управляющие системы и машины. 2008. № 6. С. 28 – 33.
10. Корольов В.Ю. Персоналізація віртуальних обчислювальних ресурсів і інформаційних
джерел в сервісно-орієнтованих архітектурах. Вісті академії інженерних наук України.
2007. № 4 (34). С. 13 – 20.
Одержано 04.06.2018
Про авторів:
Корольов Вячеслав Юрійович,
кандидат технічних наук, старший науковий співробітник
Інституту кібернетики імені В.М. Глушкова НАН України,
korolyov@i.ua
Ходзінський Олександр Миколайович,
кандидат фізико-математичних наук, старший науковий співробітник
Інституту кібернетики імені В.М. Глушкова НАН України.
okhodz@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-161850 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2616-938Х |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:27:12Z |
| publishDate | 2018 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Корольов, В.Ю. Ходзінський, О.М. 2019-12-24T21:34:28Z 2019-12-24T21:34:28Z 2018 Тополого-комбінаторна модель побудови мереж для транспортних засобів / В.Ю. Корольов, О.М. Ходзінський // Компьютерная математика. — 2018. — № 1. — С. 61-67. — Бібліогр.: 10 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/161850 004.94 Запропоновано модель побудови радіомережі та визначення маршрутів руху для гетерогенних груп безпілотних апаратів (БПА), безпілотних наземних роботів, надводних безпілотних транспортних засобів та змістовну постановку проблеми оптимізації системи, що складається з БПА і рухомих пунктів керування. Спеціальна мережа призначена для розгортання у польових умовах відповідно до поставленої задачі, наявних обчислювально-комунікаційних ресурсів та динаміки зміни ситуації. Предложено модель построения радиосети и определения маршрутов движения для гетерогенных групп беспилотных аппаратов (БПА), беспилотных наземных роботов, надводных беспилотных транспортных средств и содержательную постановку проблемы оптимизации системы, которая состоит из БПА и подвижных пунктов управления. Специальная сеть предназначена для разворачивания в полевых условиях соответственно поставленной задаче наличных коммуникационных ресурсов и динамики изменения ситуации. The growth of the number of different types of uninhabited vehicle (UV) generates the problem of optimizing their interaction and remote control in a dynamic environment. The paper proposes a model of radio network synthesis and traffic routes for heterogeneous groups of the UV and a meaningful statement of the optimization problem of a system consisting of UVs and moving control station. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Системный анализ Тополого-комбінаторна модель побудови мереж для транспортних засобів Тополого-комбинаторная модель построения сетей транспортных средств Topological and combinatorial model for vehicle networks building Article published earlier |
| spellingShingle | Тополого-комбінаторна модель побудови мереж для транспортних засобів Корольов, В.Ю. Ходзінський, О.М. Системный анализ |
| title | Тополого-комбінаторна модель побудови мереж для транспортних засобів |
| title_alt | Тополого-комбинаторная модель построения сетей транспортных средств Topological and combinatorial model for vehicle networks building |
| title_full | Тополого-комбінаторна модель побудови мереж для транспортних засобів |
| title_fullStr | Тополого-комбінаторна модель побудови мереж для транспортних засобів |
| title_full_unstemmed | Тополого-комбінаторна модель побудови мереж для транспортних засобів |
| title_short | Тополого-комбінаторна модель побудови мереж для транспортних засобів |
| title_sort | тополого-комбінаторна модель побудови мереж для транспортних засобів |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/161850 |
| work_keys_str_mv | AT korolʹovvû topologokombínatornamodelʹpobudovimereždlâtransportnihzasobív AT hodzínsʹkiiom topologokombínatornamodelʹpobudovimereždlâtransportnihzasobív AT korolʹovvû topologokombinatornaâmodelʹpostroeniâseteitransportnyhsredstv AT hodzínsʹkiiom topologokombinatornaâmodelʹpostroeniâseteitransportnyhsredstv AT korolʹovvû topologicalandcombinatorialmodelforvehiclenetworksbuilding AT hodzínsʹkiiom topologicalandcombinatorialmodelforvehiclenetworksbuilding |