Разработка и исследование комплекса моделей и методов для летающих сенсорных сетей тема диссертации и автореферата по ВАК РФ 05.12.13, доктор наук Киричек Руслан Валентинович

• Киричек Руслан Валентинович
• доктор наук
• 2018

Оглавление диссертации доктор наук Киричек Руслан Валентинович

ВВЕДЕНИЕ

Глава 1. АНАЛИЗ ТЕХНОЛОГИЙ ТЕЛЕКОММУНИКАЦИЙ XXI ВЕКА

1.1 Беспроводные сенсорные сети

1.1.1 Алгоритмы выбора головного узла в беспроводных сенсорных сетях

1.1.2 Модели трафика для беспроводных сенсорных сетей

1.1.3 Модели и методы защиты беспроводных сенсорных сетей от потоков ложных событий, клонирования и преднамеренных электромагнитных воздействий

1.2 Концепция Интернета вещей

1.3 Тактильный Интернет

1.3.1 Концепция Тактильного Интернета

1.3.2 Эволюция задержек в сетях и системах связи

1.3.3 Эволюция требований к скорости передачи

1.3.4 Приложения Тактильного Интернета

1.4 Дополненная реальность

1.4.1 Дополненная реальность как приложение Интернета вещей

1.4.2 Применение технологии дополненной реальности как части Интернета вещей

1.5 Сети связи пятого поколения

1.6 Летающие сети

1.7 Выводы по главе

Глава 2. НОВЫЙ ВИД СЕТЕЙ СВЯЗИ ОБЩЕГО ПОЛЬЗОВАНИЯ — ЛЕТАЮЩИЕ СЕНСОРНЫЕ СЕТИ

2.1 Предпосылки появления летающих сенсорных сетей

2.1.1 Мобильные целевые сети MANET

2.1.2 Автомобильные целевые сети VANET

2.1.3 Летающие целевые сети FANET

2.2 Типовая структура летающей сенсорной сети

2.3 Архитектура летающих сенсорных сетей

2.3.1 Типы узлов

2.3.2 Топологии сети

2.4 Анализ международной деятельности по исследованию летающих

сетей

2.5 Теоретические и практические направления исследований в области летающих сенсорных сетей

2.5.1 ЛСС и системы массового обслуживания

2.5.2 Кластеризация наземного и летающего сегментов. Оптимизация маршрута сбора данных

2.5.3 Задачи управления ЛСС

2.5.4 Модельная сеть и тестирование ЛСС

2.6 Задачи диссертационной работы

2.7 Выводы по главе

Глава 3. ЛЕТАЮЩАЯ СЕНСОРНАЯ СЕТЬ КАК СИСТЕМА И СЕТЬ МАССОВОГО

ОБСЛУЖИВАНИЯ

3.1 Беспилотный летательный аппарат как системы массового обслуживания

3.2 Рой БПЛА как сеть массового обслуживания

3.3 Модель доставки данных с нательных сетей в сеть связи общего пользования на базе беспилотных летательных аппаратов

3.4 Модель фрагмента летающей сенсорной сети для передачи данных

на большие расстояния

3.5 Выводы по главе

Глава 4. РАЗРАБОТКА И ИССЛЕДОВАНИЕ МОДЕЛЕЙ ЛЕТАЮЩИХ СЕНСОРНЫХ СЕТЕЙ

4.1 Использование БПЛА в качестве узла целевых автомобильных сетей (УАЫЕТ)

4.1.1 Сценарии использования БПЛА

4.1.2 Значение для ИТС при внедрении услуг на базе БПЛА

4.2 Методы выбора оптимального маршрута для сбора данных посредством БПЛА

4.3 Комплекс моделей преднамеренного электромагнитного воздействия на летающие сенсорные сети, методы обнаружения и защиты от них

4.3.1 Обзор международной деятельности по исследованию преднамеренных электромагнитных воздействий

4.3.2 Деятельность по разработке стандартов и выработке рекомендаций

по защите от ПД ЭМВ в России и за рубежом

4.3.3 Модель преднамеренного электромагнитного воздействия

на летающую сенсорную сеть

4.3.4. Модель искажения данных в кабельных линиях связи

4.3.5. Обнаружение источника ПД ЭМВ в беспроводных сенсорных сетях

4.3.6. Модель изменения архитектуры летающей сенсорной сети при обнаружении преднамеренных электромагнитных воздействий

4.3.7. Модель повышения помехозащищенности каналов связи к воздействиям ПД ЭМВ

4.4 Выводы по главе

Глава 5. МОДЕЛЬНАЯ СЕТЬ ЛАБОРАТОРИИ ИНТЕРНЕТА ВЕЩЕЙ

5.1 Архитектура модельной сети

5.2 Анализ видов тестирования летающих сенсорных сетей на базе модельной сети

5.2.1 Виды тестирования

5.2.2 Подходы к тестированию узлов в беспроводной сенсорной сети

5.2.3 Виды взаимодействия сегментов летающей сенсорной сети и методы их тестирования

5.3 Тестирование фрагмента летающей сенсорной сети на базе БПЛА общего пользования

5.4 Организации гетерогенных шлюзов на базе БПЛА

5.5 Выводы по главе

Глава 6. МЕТОД ИДЕНТИФИКАЦИИ БПЛА И ПЕРЕДАЧА МУЛЬТИМЕДИА-

ДАННЫХ В ЛЕТАЮЩИХ СЕНСОРНЫХ СЕТЯХ НА БАЗЕ ТЕХНОЛОГИИ

LORA

6.1 Метод идентификации БПЛА на базе архитектуры цифровых

объектов

6.2 Организация центра идентификации и контроля полетов БПЛА общего пользования в Умном городе

6.3 Тестирование сервиса идентификации и контроля воздушного движения БПЛА

6.3.1 Тестирование маршрутных алгоритмов на быстродействие

6.3.2 Нагрузочное тестирование серверного программного обеспечения

6.3.3 Тестирование функциональной части системы по передаче и приему сообщений с использованием технологии LoRa и протокола LoRaWAN

6.3.4 Тестирование наземного комплекса

6.3.5 Тестирование полета БПЛА с отображением его позиции на карте

6.3.6 Тестирование визуализирующей части на предмет построения маршрутов

6.4 Метод передачи мультимедиа-данных в летающих сенсорных сетях на

базе технологии LoRa и протокола LoRaWAN

6.5 Выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

Приложение А. СИМУЛЯЦИЯ ПОЛЕТА БПЛА ПО ВЫБРАННОЙ

ТРАЕКТОРИИ ДВИЖЕНИЯ

Приложение Б. ТЕСТОВЫЕ СПЕЦИФИКАЦИИ ДЛЯ ЛЕТАЮЩИХ

СЕНСОРНЫХ СЕТЕЙ

Приложение В. ДОКУМЕНТЫ, ПОДТВЕРЖДАЮЩИЕ ВНЕДРЕНИЕ ОСНОВНЫХ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ

ВВЕДЕНИЕ

Введение диссертации (часть автореферата) на тему «Разработка и исследование комплекса моделей и методов для летающих сенсорных сетей»

Актуальность темы диссертации

Начало XXI века ознаменовалось достаточно широким внедрением беспроводных сенсорных сетей, представляющих собой первые самоорганизующиеся сети, которые начали использоваться на сетях связи общего пользования (ССОП) во многих странах мира, включая и Российскую Федерацию. Множество научно-исследовательских работ в этой области, появление стандартов Международного союза электросвязи, успешное внедрение пилотных проектов способствовали тому, что в начале второго десятилетия XXI века эти работы были продолжены уже в направлении создания и внедрения концепции Интернета вещей. Концепция Интернета вещей, технологической основой которой во многих ее приложениях и стали беспроводные сенсорные сети (БСС), подразумевает прежде всего принципиальное изменение количественных характеристик сети. Включение вещей, и физических, и виртуальных, в клиентскую базу сетей связи приводит к необходимости решения проблем построения сетей связи, в которых число терминалов сети будет исчисляться триллионами, в отличие от существующих традиционных сетей, принципы построения которых ориентировались на миллиардную клиентскую базу. Такое количественное изменение в области сетей связи привело мировое научное сообщество к осознанию того факта, что сети при реализации концепции Интернета вещей должны быть самоорганизующимися. Последнее потребовало пересмотра основных подходов к разработке и исследованию моделей и методов построения сетей, многие из которых были опробованы на этапе внедрения беспроводных сенсорных сетей.

Однако не только количественные изменения оказали влияние на формирование сетей связи во втором десятилетии XXI века. Технологический прогресс дал возможность приступить к созданию летающих сетей, Тактильного Интернета, использованию Дополненной реальности для предоставления новых услуг телекоммуникаций, к созданию сверхплотных сетей с ультрамалыми задержками, так называемых сетей связи пятого поколения. Тактильный Интернет предполагает, что задержки в сетях связи должны уменьшиться в 100 раз по сравнению с традиционными ССОП до 1 мс. Широкое внедрение приложений Дополненной реальности также требует принципиального уменьшения задержек. Эти задачи требуется решить в рамках проведения научно-исследовательских работ в области сетей связи пятого поколения.

В диссертации исследования сконцентрированы на летающих сетях. Появление беспилотных летательных аппаратов, сначала достаточно больших для решения задач

военного характера, а затем и мини-, микро-БПЛА расширило область их применения и на гражданские задачи. При этом первоначально использование этих аппаратов с точки зрения сбора информации для гражданских целей в основном базировалось на использовании результатов видеосъемки и осуществлялось, как правило, не объединенными в сеть БПЛА.

Достаточно широкое распространение БПЛА, возможность (при определенных регуляторных условиях) их использования даже физическими лицами привели к появлению целого ряда новых научно-исследовательских задач. В первую очередь возникла необходимость постановки и решения комплекса научно-исследовательских задач в области сетей беспилотных летающих аппаратов (БПЛА). Масштабное внедрение к настоящему времени беспроводных сенсорных сетей и необходимость сбора информации с них даже в условиях нахождения этих сетей в труднодоступных районах привели к необходимости рассматривать БПЛА или сеть БПЛА как элементы этих сетей с возможностью выполнения функций, например, головных узлов сенсорной сети. При этом для сбора информации с сенсорных полей с использованием БПЛА должны использоваться протоколы беспроводных сенсорных сетей, а для передачи информации в ССОП — протоколы сетей связи общего пользования. Использование БПЛА физическими лицами требует, естественно, разработки современных моделей и методов для их идентификации.

Именно эти взаимоувязанные новые научно-исследовательские задачи и легли в основу диссертации, в которой определен и исследован новый вид сетей связи — летающие сенсорные сети, которые вследствие широкого распространения беспроводных сенсорных сетей и БПЛА общего пользования органично входят в комплекс взаимодействующих сетей электросвязи ССОП.

Степень разработанности темы

Исследованию проблем летающих сетей, именуемых, как правило, FANET (Flying Ad Hoc Networks), в последнее десятилетие посвящено достаточно много работ отечественных и зарубежных ученых А. Е. Кучерявого, П. А. Абакумова, А. В. Абилова, Д. С. Васильева, I. F. Akyildiz, O. K. Sahingoz, I. Bekmezci, Y. Altshuler, V. Yanovsky, P. DeLima, G. York, D. Pack, R. R. McCunea, G. R. Madey, H. Yamomoto, K. Yamasaki, T. H. Phuong, E. P. de Freitas, D. Orfanus.

Эти работы посвящены общим принципам построения сетей FANET (I. F. Akyildiz, O. K. Sahingos, I. Bekmezci), использованию беспилотных летательных аппаратов и их роя для поиска цели (Y. Altshuler, V. Yanovsky), поиску цели, специально оборудованной

сенсорными датчиками в военных целях (P. DeLima, G. York, D. Pack), протоколам маршрутизации сетей FANET (А. В. Абилов, Д. С. Васильев), поведению головных узлов сенсорных сетей в трехмерном пространстве (А. Е. Кучерявый, П. А. Абакумов), использованию БПЛА для позиционирования в университете (H. Yamomoto, K. Yamasaki, T. H. Phuong). Наиболее близкой к заявленной тематике является работа E. P. de Freitas, который совместно с D. Orfanus улучшал связность беспроводных сенсорных сетей в военных операциях с использованием специализированных БПЛА.

Летающая сенсорная сеть включает в себя два сегмента — наземный и летающий. Исследованию проблем построения и функционирования беспроводных сенсорных сетей на плоскости, концепции Интернета вещей и ее приложений, планируемого перехода к сетям связи пятого поколения посвящено достаточно много работ отечественных и зарубежных ученых В. М. Вишневского, К. Е. Самуйлова, В. К. Сарьяна, С. Н. Степанова, М. А. Шнепса, Б. С. Гольдштейна, А. К. Канаева, В. Г. Карташевского, М. О. Колбанева, А. Е. Кучерявого, Е. А. Кучерявого, А. И. Парамонова, А. П. Пшеничникова, А. В. Рослякова, Н. А. Соколова, В. О. Тихвинского, П. А. Абакумова, С. Д. Андреева, В. А. Мочалова, А. В. Прокопьева, N. Al-Qadami, W. Heinzelman, O. Yonis, D. Kim, K. Lindsey, A. Salim.

В представляемой работе, в отличие от известных, разрабатывается и исследуется комплекс моделей и методов для летающих сенсорных сетей, построенных с использованием БПЛА общего пользования на основе протоколов беспроводных сенсорных сетей ZigBee, 6L0WPAN, Thread, RPL и др. Такой подход позволяет говорить о новом виде сетей — летающих сенсорных сетях, которые, как правило, являются частью комплекса взаимодействующих сетей электросвязи ССОП и предназначены для предоставления новых услуг как пользователям ССОП, так и устройствам этих сетей при межмашинном взаимодействии M2M (Machine-to-Machine) при реализации концепции Интернета вещей.

Цель и задачи исследования

Целью диссертационной работы является определение нового вида сетей связи, входящих в ССОП, — летающих сенсорных сетей — и разработка комплекса моделей и методов анализа и синтеза для них.

Для достижения поставленной цели в диссертации последовательно решаются следующие задачи:

• анализ концепции Интернета вещей и современных технологий телекоммуникаций и обоснование необходимости создания нового вида сетей связи

общего пользования — летающих сенсорных сетей;

• определение теоретических и практических направлений исследований в области летающих сенсорных сетей;

• разработка методологии решения комплекса теоретических и практических задач в области Интернета вещей на основе использования модельных сетей, в том числе для летающих сенсорных сетей;

• разработка модели представления беспилотного летательного аппарата как системы массового обслуживания;

• разработка модели представления роя беспилотных летательных аппаратов как сети массового обслуживания;

• разработка методов использования БПЛА для беспроводных нательных сетей WBAN с целью увеличения их связности;

• разработка метода выбора оптимального маршрута для сбора данных посредством БПЛА;

• разработка комплекса моделей преднамеренных электромагнитных воздействий на ЛСС, методы обнаружения и защиты от них;

• разработка метода сбора информации посредством БПЛА с использованием протоколов крупномасштабных малопотребляющих сетей.

Научная новизна работы

Научная новизна работы состоит в следующем.

1. Предложен новый вид сетей связи, входящий в комплекс взаимодействующих сетей электросвязи ССОП, — летающие сенсорные сети, отличающиеся от известных тем, что наземный сегмент ЛСС представляет собой совокупность сенсорных полей, а летающий — общедоступных БПЛА, причем взаимодействие между летающим и наземным сегментами обеспечивается с использованием протоколов беспроводных сенсорных сетей.

2. Определены новые теоретические и практические направления исследований в области летающих сенсорных сетей с учетом представления этих сетей как одного из базовых приложений концепции Интернета вещей.

3. Разработана методология решения комплекса теоретических и практических задач на основе использования модельных сетей, отличающаяся от известных тем, что на созданных модельной сети и первой в стране Лаборатории Интернета вещей существует возможность проведения натурного и имитационного моделирования для приложений Интернета вещей, в том числе для сенсорных сетей, летающих сенсорных

сетей, Тактильного Интернета, Дополненной реальности.

4. Разработана математическая модель беспилотного летательного аппарата, отличающаяся от известных тем, что БПЛА представляется как система массового обслуживания и в предложенной модели учитываются параметры скорости перемещения БПЛА, высоты его пролета и плотности сенсорной сети.

5. Разработана математическая модель для роя беспилотных летательных аппаратов, отличающаяся от известных тем, что рой БПЛА представляется как сеть массового обслуживания, а основной характеристикой модели является средняя длительность передачи информации между элементами роя. Получены соответствующие характеристики для роев, имеющих формы куба и шара.

6. Разработан метод использования БПЛА с целью увеличения связности наземных сегментов, отличающийся от известных тем, что БПЛА используется для увеличения связности в беспроводных нательных сетях WBAN.

7. Разработан метод выбора оптимального маршрута для сбора данных посредством БПЛА, отличающийся от известных тем, что для решения задачи коммивояжера используется модифицированный метод случайного штрафования вершин графа маршрута.

8. Разработан комплекс моделей влияния на летающие сенсорные сети преднамеренных электромагнитных воздействий, методы обнаружения и защиты от них, отличающиеся от известных тем, что для обнаружения используется анализ параметров функционирования наземного сегмента БСС, а защита осуществляется за счет реконфигурации архитектуры ЛСС.

9. Разработан метод сбора информации посредством БПЛА, отличающийся от известного использованием для этих целей протоколов крупномасштабных малопотребляющих сетей для передачи видеоизображения на значительные расстояния, исчисляемые километрами.

Теоретическая и практическая значимость

Теоретическая значимость диссертации состоит прежде всего в определении нового вида сетей связи, входящего в ССОП, — летающих сенсорных сетей, а также в разработке комплекса моделей и методов анализа и синтеза для них. Важными достижениями, обогащающими теорию телетрафика, и теорию массового обслуживания, являются представление одиночного БПЛА как системы массового обслуживания и роя БПЛА как сети массового обслуживания. Разработка метода выбора оптимального маршрута для сбора данных посредством БПЛА с использованием

модифицированной задачи коммивояжера со случайным штрафованием вершин графа маршрута также представляет собой существенный теоретический вклад. Важными теоретическими результатами представляются разработанный метод увеличения связности беспроводных нательных сетей WBAN при использовании БПЛА, комплекс методов по защите летающих сенсорных сетей от преднамеренных электромагнитных воздействий и новый метод сбора информации с сенсорных полей, предусматривающий передачу видеоизображения с БПЛА на основе использования протоколов крупномасштабных малопотребляющих сетей связи на значительные расстояния, исчисляемые километрами.

Практическая значимость диссертационной работы состоит в создании научно обоснованных рекомендаций по созданию и планированию летающих сенсорных сетей и возможности их использования в различных отраслях народного хозяйства.

Полученные в диссертационной работе результаты внедрены ФГУП Научно-исследовательским институтом радио в 2016-2017 годах в рамках выполнения государственных контрактов по научно-техническому и методическому обеспечению выполнения Минкомсвязью России функций администрации связи Российской Федерации в части, касающейся международно-правовой защиты интересов Российской Федерации в области электросвязи и радиосвязи, в виде предложений проектов стандартов (вкладов) от имени администрации связи Российской Федерации (Министерства связи и массовых коммуникаций Российской Федерации) в Сектор стандартизации электросвязи Международного союза электросвязи (МСЭ-Т), ПАО «Ростелеком» при проведении совместных исследований на модельной сети Лаборатории Интернета вещей СПбГУТ и под эгидой Международного союза электросвязи при реализации региональных инициатив для стран СНГ, в научно-исследовательских и опытно-конструкторских работах АО «Московский ордена Трудового Красного Знамени научно-исследовательский радиотехнический институт», при выполнении ООО «Специальный Технологический Центр» технического проекта опытно-конструкторской работы, в ПАО «ГИПРОСВЯЗЬ» при разработке «Методики планирования малопотребляющих сетей дальнего радиуса действия, в том числе для передачи изображений», а также при чтении лекций, проведении практических занятий и лабораторных работ на кафедре сетей связи и передачи данных СПбГУТ им. проф. М. А. Бонч-Бруевича.

Часть результатов диссертационной работы получена при выполнении ряда научно-исследовательских проектов, где автор диссертационной работы являлся руководителем и исполнителем, в том числе при исследованиях по грантам РФФИ, ФЦП

и НИР, выполняемых по приоритетным научным направлениям в СПбГУТ.

Методология и методы исследования

Объектом исследования являются летающие сенсорные сети.

Предметом исследования является комплекс моделей и методов для летающих сенсорных сетей.

Методы исследования

Для решения поставленных в работе задач использовались методы теории вероятностей, теории массового обслуживания и теории телетрафика, имитационного моделирования, а также натурные эксперименты.

Основные положения работы, выносимые на защиту

1. Новый вид сетей связи, входящий в комплекс взаимодействующих сетей электросвязи ССОП, — летающие сенсорные сети.

2. Методология решения комплекса теоретических и практических задач для летающих сенсорных сетей на базе модельной сети.

3. Модель представления БПЛА как системы массового обслуживания и роя БПЛА как сети массового обслуживания.

4. Метод использования БПЛА для беспроводных нательных сетей WBAN с целью увеличения их связности.

5. Метод выбора оптимального маршрута для сбора данных посредством БПЛА на основе решения задачи коммивояжера модифицированным методом штрафования вершин.

6. Комплекс моделей и методов обнаружения и защиты летающих сенсорных сетей от преднамеренных электромагнитных воздействий.

7. Метод передачи видеоизображения посредством БПЛА с использованием протоколов крупномасштабных малопотребляющих сетей на большие расстояния, исчисляемые километрами.

Публикации

Основные результаты диссертации изложены в 212 опубликованных работах, в том числе в 21 работе, опубликованной в журналах из перечня ВАК Министерства образования и науки Российской Федерации; в 35 работах, опубликованных в трудах, индексируемых Scopus, и 25 в Web of Science; 1 патенте на изобретение, 1

свидетельстве о государственной регистрации программы для ЭВМ и 18 вкладах на 11-ю и 20-ю Исследовательские комиссии МСЭ-Т.

Структура и объем работы

Диссертация состоит из введения, шести глав, заключения, списка литературы и приложения. Общий объем диссертации 316 страниц, включая 130 рисунков, 29 таблиц, список литературы из 472 наименований. В приложении к диссертационной работе приведены результаты симуляции полета БПЛА по выбранной траектории движения, тестовые спецификации для летающих сенсорных сетей и документы, подтверждающие внедрение основных результатов диссертационной работы.

Личный вклад автора

Результаты диссертационной работы получены автором самостоятельно, математические модели, методы анализа и вычислительные алгоритмы, экспериментальные исследования проведены и разработаны при его преобладающем участии или под его научным руководством. Направления исследований диссертационной работы, формулировки проблем и постановки задач обсуждались с научным консультантом проф. А. Е. Кучерявым, что отражено в совместных публикациях, в которых основные результаты и их доказательства принадлежат автору.

Степень достоверности и апробация результатов

Достоверность полученных результатов подтверждается корректным применением математического аппарата, имитационным и натурным моделированием, а также широким обсуждением результатов диссертации на международных и отечественных конференциях, на заседаниях и семинарах Международного союза электросвязи.

Апробация результатов

Основные положения диссертационной работы были представлены и обсуждались на следующих конгрессах, конференциях и семинарах: на 8-м и 9-м Международных симпозиумах по электромагнитной совместимости и электромагнитной экологии (Санкт-Петербург, 2009, 2011), международных симпозиумах: EMC Europe (Вроцлав, 2010), EMC Europe (Йорк, 2011), EMC (Лонг-Бич, 2011), EMC Asia (Чеджудо, 2011), 8-м Международном конгрессе по ультрасовременным системам связи и управления ICUMT (Лиссабон, 2016), Международных конференциях по современным

технологиям связи 1САСТ (Пхёнчхан, 2015-2017), Международных конференциях по проводным и беспроводным сетям и системам следующего поколения NEW2AN (Санкт-Петербург, 2015-2017), Международных конференциях «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь» DCCN (Москва, 2015-2017), XI Международной научной конференции «Перспективные технологии в средствах передачи информации» — ПТСПИ (Владимир — Суздаль, 2015), 2-й Международной научно-технической конференции студентов, аспирантов и молодых ученых «Интернет вещей и 5G» INTHITEN (Санкт-Петербург, 2016), на XVII Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (Самара, 2016), Международных научно-технических и научно-методических конференциях «Актуальные проблемы инфотелекоммуникаций в науке и образовании» АПИНО (Санкт-Петербург, 2014-2017), 2-й и 3-й Международных конференциях по искусственному интеллекту и промышленным технологиям А11Е (Пекин, 2016; Шанхай, 2017), 30-й Европейской конференции по симуляции и моделированию ECMS (Регенсбург, 2016), 7-й Международной конференции по информационным наукам и их приложениям Ю^А (Хо Ши Мин, 2016), XX Международном форуме МАС2016 «Формирование Единой сети электросвязи России на базе сетей последующих поколений» (Москва, 2017), Конференции российских молодых ученых в области электротехники и электроники 2017 ElConRus (Санкт-Петербург, 2017), 31-й Международной конференции по информационному сетевому взаимодействию ЮОШ (Дананг, 2017), 15-й Международной конференции по проводной/беспроводной связи в Интернете WWIC (Санкт-Петербург, 2017), Международной конференции по будущим сетям и распределенным системам ICFNDS (Кембридж, 2017), Международной конференции по беспроводной связи, сетям и приложениям WCNA (Шэньчжэнь, Гуанчжоу, 2014), 10-й Международной конференции «Обеспечение доверия и безопасности при использовании ИКТ» (Москва, 2011), II Международной научно-практической конференции «Актуальные достижения европейской науки» (София, 2011), всероссийских конференциях: «Региональная информатика» (Санкт-Петербург, 2010), «Информационная безопасность регионов России» (Санкт-Петербург, 2011), а также на заседаниях 11-й Исследовательской комиссии МСЭ-Т (Женева, 2017), 20-й Исследовательской комиссии МСЭ-Т (Сингапур, 2016; Дубай, 2017; Женева, 2017) и Региональной группе ИК20 МСЭ-Т для Восточной Европы, Центральной Азии и Закавказья (Санкт-Петербург, 2017).

Содержание диссертационной работы

Во введении отмечена актуальность темы диссертационной работы. Показано, как в настоящее время изменилась структура сетей связи. Представлены объект и предмет диссертации.

Глава 1 диссертационной работы посвящена анализу технологий телекоммуникаций XXI века, рассмотрены предпосылки появления и становления концепции Интернета вещей. Проанализировано ее влияние на сети связи в краткосрочной и долгосрочной перспективе, а также взаимосвязь с сетями связи пятого поколения 5G/IMT-2020. Отмечается, что одним из наиболее важных технологических достижений XXI века является создание и широкое распространение беспилотных летательных аппаратов (БПЛА).

Глава 2 раскрывает, что же такое летающие сенсорные сети. Проанализированы предпосылки появления летающих сенсорных сетей. Предложена типовая структура летающей сенсорной сети. Сформулированы теоретические и практические направления исследований в области летающих сенсорных сетей, а также задачи, которые предполагается последовательно решить в ходе диссертационной работы.

В главе 3 разработаны модели систем и сетей массового обслуживания для летающих сенсорных сетей. Предложено беспилотный летательный аппарат, осуществляющий сбор данных с наземного сегмента, рассматривать как систему массового обслуживания, а рой БПЛА как сеть массового обслуживания.

В главе 4 представлен комплекс моделей, которые были разработаны для различных приложений Интернета вещей. Рассматривается разработанный в диссертации метод выбора оптимального маршрута для сбора данных посредством БПЛА на основе решения задачи коммивояжера модифицированным методом случайного штрафования вершин графа маршрута. Представлен комплекс моделей искажения, обнаружения и защиты фрагментов ЛСС от преднамеренных электромагнитных воздействий (ПД ЭМВ). Рассмотрены механизмы и последствия возникновения ошибок в кабельных линиях связи на базе технологии Ethernet. Представлена модель обнаружения ПД ЭМВ на беспроводную сенсорную сеть (наземный сегмент ЛСС) путем анализа параметров функционирования БСС.

В главе 5 представлены структура и описание основных элементов модельной сети Лаборатории Интернета вещей, а также тестирование фрагмента летающей сенсорной сети, выполненного на базе лабораторных стендов. В главе проводится анализ видов тестирования летающих сенсорных сетей на базе модельной сети. Приведено описание базовых видов тестирования: соответствия (conformance),

совместимости (compatibility), взаимодействия (interworking), а также новых видов — тестирования толерантности к задержкам; выявления вторжений в сенсорную сеть.

Глава 6 посвящена организации воздушного движения беспилотных летательных аппаратов в умных городах. В частности, БПЛА рассматривается как летающая интернет вещь в пределах сети оператора связи. Предложен метод идентификации БПЛА, доставки данных об идентификаторе в ССОП, а также передачи видеоизображения с БПЛА на базе протоколов крупномасштабных малопотребляющих сетей на значительные расстояния, исчисляемые километрами. Приведены результаты исследования параметров передачи видеоизображения на базе технологии LoRa, в частности для передачи изображений на фрагменте модельной сети Лаборатории Интернета вещей СПбГУТ.

Глава 1. АНАЛИЗ ТЕХНОЛОГИЙ ТЕЛЕКОММУНИКАЦИЙ XXI ВЕКА 1.1. Беспроводные сенсорные сети

Беспроводные сенсорные сети, как уже отмечалось во введении, явились технологической основой для появления концепции Интернета вещей. Кроме того, модели и методы построения беспроводных сенсорных сетей, и это естественно, широко используются при построении наземного сегмента летающих сенсорных сетей. Поэтому аналитическую часть диссертации и начнем с детального рассмотрения беспроводных сенсорных сетей.

Прошло уже более 10 лет с момента первой публикации в журнале «Электросвязь» [188] по беспроводным сенсорным сетям как новой составляющей сетей связи общего пользования [195], позволяющей сделать новый шаг в развитии общества на пути его преобразования на основе всепроникающих сетей [324, 343, 359, 382, 446]. За это время отечественными учеными достигнуты большие успехи в исследованиях беспроводных сенсорных сетей в области разработки алгоритмов выбора головного узла, моделей трафика для таких сетей, моделей и методов защиты беспроводной сенсорной сети от потоков ложных событий. На основе результатов этих исследований в начале второго десятилетия XXI века в СПбГУТ при непосредственном участии и под руководством автора диссертации были организованы работы в области Интернета вещей [167, 148], которые в 2012 году были материализованы в Лабораторию Интернета вещей [367]. В настоящее время ведутся работы в области новых приложений Интернета вещей [185, 243], которые отражают развитие беспроводных сенсорных сетей на новом этапе их эволюции — в летающей форме и в условиях наномира.

Список литературы диссертационного исследования доктор наук Киричек Руслан Валентинович, 2018 год

Источник данных

Вид сети

Рисунок 4.5 - Роль БПЛА в системе «БСС — БПЛА — шлюз» Например, возможны следующие варианты:

• Транзит трафика через сеть БПЛА. В этом случае БПЛА оборудован узлом БСС, который выступает в роли транзитного (возможно, головного) узла [67, 68]. Также

БПЛА оборудован средствами связи «БПЛА — БПЛА», которые образуют сеть между подвижными объектами, обеспечивающую маршрут трафика к шлюзу.

• Транзит трафика через узел БПЛА. В этом случае БПЛА оборудован узлом БСС, который выступает в роли транзитного и/или головного узла, и средствами связи со шлюзом, находящимся в зоне связи шлюза.

• Доставка данных. В этом случае БПЛА оборудован узлом БСС, который выступает в роли головного узла или шлюза. Получаемые узлом данные хранятся в его запоминающем устройстве в течение времени, необходимого для перемещения БПЛА к точке базирования, где производится считывание собранных данных. В этом случае имеет место задержка доставки данных, равная времени движения БПЛА.

Рассмотрим последний из вариантов использования БПЛА как наиболее вероятный. В этом случае систему можно рассматривать как сеть, толерантную к задержкам [310, 332]. В этой сети имеют место два основных способа передачи (транспортировки) данных: первый — с помощью технологий беспроводной связи (БСС — БПЛА) и второй (механический) — перемещение БПЛА в пространстве. Вероятно, что в данном случае второй способ требует существенно большего времени. Однако одним из основных показателей качества функционирования сетей, толерантных к задержкам, является время доставки данных.

В связи с вышесказанным будем рассматривать метод выбора траектории движения БПЛА в ЛСС, направленный на минимизацию времени доставки данных.

Обзор существующих методов выбора траектории движения БПЛА

Существует множество возможных методов выбора траектории движения БПЛА в определенной местности. Все они отличаются критериями выбора, которые зависят от поставленной задачи и цели полета БПЛА. Так, в [353] рассматривается решение задачи выбора оптимальной траектории движения БПЛА в зависимости от препятствий, встречающихся на его пути, столкновения или взаимодействия с которыми требуется избежать.

Множество исследовательских работ на тему оптимизации траектории движения БПЛА связано с применением БПЛА для военных целей [432]. Такое положение связано с обширным применением БПЛА для военных задач, о чем упоминалось в разделе 1.6. Для военных целей в качестве критериев для выбора траектории БПЛА могут использоваться такие задачи, как, например, предотвращение обнаружения БПЛА вражескими локаторами и т. д.

В [415] рассматривается задача отслеживания и позиционирования БПЛА при наличии действующей наземной беспроводной сети. Авторами предложен метод выбора траектории БПЛА, при которой БПЛА использует наземную беспроводную сеть для передачи информации о координатах своего местоположения. Расчет и построение маршрута при этом происходит заблаговременно.

Такой метод накладывает определенные ограничения на выбор траектории — путь БПЛА должен проходить в зоне действия радиосигнала наземной беспроводной сети, т. е. зависеть от сетевого покрытия. Кроме того, возможность БПЛА передавать и принимать информацию о местоположении зависит от пропускной способности наземной сети.

В данной диссертационной работе исследуется вопрос выбора траектории движения БПЛА гражданского назначения.

Позиционирование БПЛА над наземным сегментом ЛСС

При использовании БПЛА для взаимодействия с узлами наземной сенсорной сети необходимо решить ряд задач, связанных с позиционированием БПЛА над территорией, обслуживаемой БСС. При этом возможен ряд вариантов взаимодействия, в зависимости от наличия, полноты и достоверности данных о топологии сети [66, 372]:

1) топология сети полностью неизвестна;

2) топология сети полностью известна;

3) имеются неполные данные о топологии сети.

При этом под топологией в данном случае понимаются параметры, характеризующие расположение узлов сети. Рассмотрим эти варианты.

Взаимодействие БПЛА и наземного сегмента ЛСС при неизвестной топологии сети

Будем полагать, что при движении над территорией обслуживаемой БСС, состоящей из N узлов, БПЛА имеет возможность определять свои координаты в пространстве, т. е. координату точки O = (x0, y0, z0), а также определять расстояние между этой точкой и любым действующим узлом БСС ni = (xi, yi, zi), находящимся в зоне связи roi. Узлы сети обладают функцией определения расстояния между собой rij. Если

R = ЫI, i,j = 1...N ,

сеть связанная, то матрица ||j| содержит полную информацию

о структуре сети, за исключением топологических характеристик, таких как

географические координаты ее узлов. Однако в данной задаче информация о сети не

локализована в виде указанной матрицы. Каждый из узлов сети располагает лишь данными о расстоянии до соседних узлов (инцидентных вершин). Таким образом, БПЛА имеет возможность получить информацию от узлов, с которыми в данный момент имеет возможность обмена информацией о расстояниях до соседних с ними узлов. Задача исследования топологии сети заключается в получении данных о координатах ее узлов. Для этого БПЛА должен исследовать территорию, обслуживаемую БСС, например, как показано на Рисунок 4.6.

Рисунок 4.6 - Исследование топологии сети

Будем полагать, что для решения задачи позиционирования узлов сети могут быть использованы данные о координатах БПЛА O = (x0, y0, z0), данные о расстоянии до узлов БСС в зоне его действия roi и данные, получаемые от этих узлов, о расстоянии до соседних с ними узлов ry.

Для решения задачи нахождения координат узлов БСС целесообразно использовать метод пространственной линейной засечки [191], который позволяет определить неизвестные координаты точки (узла сети) по расстоянию до точек (узлов сети или БПЛА) с известными координатами. При использовании данного метода составляется система уравнений вида:

(Х - xj)2 + (y -У,У + (Zi - ZjУ = j i = 1 • • К

(4.1)

где (x,У',z^ i 1""К — известные координаты K точек;

(, У,, )

— искомые координаты j-й точки;

— расстояние между i-й и искомой точкой.

r

Данная система разрешима, относительно неизвестных координат (Х/' '^ ^, в случае, когда число уравнений не меньше, чем число искомых координат. В случае трехмерного пространства система (4.1) должна содержать минимум три уравнения, т. е.

К > 3.

При движении БПЛА над территорией, обслуживаемой БСС, возможны два варианта: в зоне его действия нет ни одного узла, есть один или более узлов сети. В первом случае очевидно, что БПЛА (его вычислительное средство) не может произвести никаких действий в части оценки координат элементов БСС. Во втором случае такие действия могут быть выполнены, однако эти действия будут зависеть от числа доступных узлов БСС.

Рассмотрим возможные варианты. Будем полагать, что координаты всех элементов сети и БПЛА рассматриваются в трехмерном пространстве.

1. В зоне действия БПЛА находится один узел п БСС (Рисунок 4.7).

Для определения координат узла требуется минимум три уравнения системы

(4.1). В этом случае необходимо получить координаты трех точек 0, 0, 0 на траектории следования БПЛА и расстояние между этими точками и точкой

г(1) г (2) г(3)

расположения узла п 0, 0] и 0] .

(х? - х; )2 - )2 + (

.(1)

+ и ^ -2}) = (г

(х02) - x )2 + (у02) - уу )2 + (

,(3)

.(2)

+ и^ - 2;) = \г,

(х03) -х;)2 +(у03) -)2 + (

(3)

+ и^ - 2}) = \Т

)2 ^ )2 )2 =(Й} )2 )2 = } )2

(4.2)

Решением системы (4.2) являются координаты узла п = (х''У}'^).

2. В зоне действия БПЛА находится несколько узлов п'' ^ =2"'^ БСС. На Рисунке 4.8 приведена схема взаимного положения БПЛА и узлов БСС. В зоне действия БПЛА в данном примере находится три узла, причем эти узлы находятся в зонах

— „ г г г

действия друг друга и могут оценить расстояния между собой 12, 13 и 23.

хо, Уо, 20

Рисунок 4.8 - Положение БПЛА и узлов БСС Данные о расстояниях между узлами могут быть переданы БПЛА. При наличии данных о координатах БПЛА °(х°'Уо'2о), расстоянии от точки его положения до узлов

г г г V г г

БСС 01, 02, 03 и расстоянии между этими узлами 12, 13 и 23 может быть построена следующая система уравнений.

хо - х1 )2 +(Уо - У1)2 +(20 - 21 )? = = г2 '01

хо - х2 )2 +(Уо - У 2 )2 +(20 - 22 )2 = г2 '02

хо - х3)2 +(Уо - У3)2 +(20 - 23 )2 = г2 '03

х1 - х2 )2 + (У " У 2 )2 +(21" - 22 )2 = = г2 12

х1 - х3)2 +(Уг " У3)2 +(21" -23 )2 = г2 13

х2 - х3 )2 +(У2 - У3 )2 +(22 - 23 )2 = г2 23

(4.3)

Решением данной системы являются координаты точек п1, п2, п3.

Если наряду с указанными исходными данными, приведенными выше, имеются данные об узлах, соседних с п1, п2, п3, и расстояниях до них, причем у них есть общие соседние узлы, то система (4.3) может быть дополнена уравнениями для общих соседних узлов. Для примера, на Рисунке 2.3 это узел п4, а дополнительные уравнения

(х4 - х)2 +(у4 - у )2 +(г4 - ^)2 = г42!

(х4 - Х2 )2 + (У4 - У 2 )2 + (24 - 2 2 )2 = Г42

(х4 - Х3 )2 + (У4 - У3 )2 + (24 - 23 )2 = Г43 (4 4)

Таким образом могут быть вычислены и координаты узлов БСС, находящихся вне зоны действия БПЛА.

Обобщая рассмотренные примеры, можно сделать вывод о том, что потенциально возможное число вычисляемых координат узлов сети равно числу доступных связанных узлов и их общих соседей, причем связанность последних должна быть не менее трех (для трехмерной задачи).

Обобщая рассмотренные примеры, можно сделать вывод о том, что для решения задачи позиционирования узлов сети необходимо определить логику (алгоритм) управления движением и функциями БПЛА.

Алгоритм можно определить следующим образом. Решающее устройство БПЛА содержит следующие переменные (элементы):

Уo,2о) ■

координаты БПЛА

г = Ы, 1, 1 = 0... N

• квадратная матрица расстояний

п = |Ы I 1 = 0. N

• матрица координат узлов 11 1,1 ;

е = |Ы I 1 = о. N -

• матрица признаков получения информации л ||йг|1' , в которой

отражается факт приема данных (полезной информации) от узлов сети (необходима

в том случае, когда параллельно решается задача опроса узлов сети);

где N — общее число узлов в сети. Полагаем, что установлено однозначное

соответствие между i — индексом узла в матрице — и его идентификатором.

„ г7 =да, 1, 1 = 0.N, 1 Ф 1

Вначале все элементы матрицы 1 , а элементы

г7 = 0, 1,1 = 0. N, 1 = 1 п. = 0 е. = 0 п

1 ^ , все элементы матрицы 1 и , кроме п0, который равен

координатам БПЛА.

При обнаружении в зоне действия БПЛА q — новых узлов производится измерение расстояния до каждого из них, полученные данные заносятся в матрицу г, также в эту матрицу заносится информация о расстояниях до соседних с ними узлов.

Для вычисления координат выбираются те строки матрицы п (узлы), для которых соответствующие элементы матрицы п = 0 (не определены координаты) и которые содержат не менее трех элементов гу ^ да, кроме элемента i = j, причем минимум, чем для трех этих элементов, известны координаты узлов, т. е. п] ^ 0.

На основе выбранных данных строится система уравнений вида (4.1), решением которой являются координаты узлов, соответствующих выбранным строкам матрицы г. Вычисленные координаты заносятся в матрицу п. Для узлов, с которыми был проведен сеанс связи (прием полезной информации), делается соответствующая отметка в матрице д ^ = 1).

Для решения подобных систем уравнений обычно используется метод наименьших квадратов [135], который для системы уравнений (4.1) может быть записан как:

(X'У,'2}) = аг§ т 1П X д/ь -XУ+(У1 -У,)2 + (2-у-г

*1 у2 ¿=1

(4.5)

Задача нахождения минимума суммы в выражении (4.5) по переменным х, у, ъ решается с использованием численных методов оптимизации.

150

200

Пройденный путь, м

Рисунок 4.9 - Изменение числа узлов сети в зоне БПЛА, полученное методом

имитационного моделирования

Матрица п, в некоторый момент времени ^ фактически содержит информацию о топологии сети, которая была получена до этого момента времени. Эта информация может быть использована для выбора траектории движения БПЛА. На основе данных из матрицы п могут быть определены границы исследованной на данный момент времени области на обслуживаемой территории и координаты ближайших узлов сети, с которыми еще не был произведен сеанс связи. При покрытии всей территории матрица п содержит

2

30

25

20

15

10

5

0

0

50

полную информацию о расположении узлов сети. Эта информация может быть использована для дальнейшего взаимодействия с БСС, а также для локализации событий, регистрируемых узлами сети [150].

Взаимодействие БПЛА и наземного сегмента ЛСС при известной топологии сети

Доставка (транспортировка) данных предполагает сбор и доставку данных в точку пространства, где возможна их передача в шлюз. При наличии полной информации о топологии сети взаимодействие БПЛА с узлами БСС в первую очередь предполагает снятие полученной (накопленной) информации (информация о топологии сети может быть получена, например, при построении сети, если фиксируются координаты каждого из узлов при его размещении, либо с помощью метода, описанного выше.

Сбор данных производится с использованием технологии связи между узлами БСС, имеющей ограниченный радиус связи. Поэтому, в зависимости от масштабов сети и требований ко времени доставки данных, сбор данных представляет собой перемещение БПЛА между узлами или группами узлов БСС и считывание данных. Траектория движения БПЛА в этом случае зависит от характера размещения узлов сети на обслуживаемой территории. Если радиус связи БПЛА может обеспечить взаимодействие с некоторым числом узлов БСС, то целесообразно найти точки, в которых может быть обслужено максимальное число узлов. Тогда траектория движения БПЛА будет линией, соединяющей данные точки. От выбора траектории существенно зависит длина маршрута БПЛА, а следовательно, и время доставки данных. На Рисунке 4.10 приведены примеры покрытия узлов БСС кругами с радиусом, равным радиусу связи БПЛА, при различном характере размещения узлов по территории.

Для нахождения траектории, при движении по которой БПЛА имеет возможность считать информацию со всех узлов сети, требуется найти покрытие всех узлов БСС. При этом следует исходить из минимума затрат времени. Полагая, что скорость движения БПЛА постоянна, требуется найти траекторию наименьшей длины.

Будем полагать, что зона действия БПЛА представляет собой круг радиуса R, а считывание информации с узлов БСС может производиться в произвольных точках (пример показан на Рисунке 4.11). Разделим данную задачу на две составляющих:

1) нахождение минимального числа точек, в которых производится считывание информации (минимизация);

2) определение оптимального маршрута движения БПЛА между этими точками.

Нахождение минимального числа точек считывания информации заключается в покрытии исходного множества точек (узлов) сети минимальным числом кругов радиуса R. Для решения такой задачи может быть применен метод кластерного анализа, в частности метод FOREL [51, 124, 209, 234].

/ • Ч / • « \ J^^^i \ \ • Ч * % > V.

+/ ( • • [ _з i \ *■ / \ • J9 V у" '

• • • 1 • f^L \ • VI • • \ • • V • 1 • • • \ • • • \ \ • • \

• • • .N • • « • 1

150

0 50 100 150 200 0 50 100 150 200

Рисунок 4.10 - Различный характер размещения узлов на территории обслуживания

200

200

100

50

50

0

Рисунок 4.11 - Пример траектории движения БПЛА при известной топологии сети

Алгоритм FOREL решает задачу кластеризации, при решении которой минимизируется суммарное квадратичное расстояние элементов кластеров (узлов БСС) от центров масс этих кластеров. Минимизируемая функция может быть записана как:

м = ±

г=1 ^, (4.6)

где к — число кластеров;

с

' — множество элементов 1 -го кластера;

— координаты центра масс * -го кластера;

— координаты центра масс 7 -го элемента кластера.

Значение (х ^У представляет собой эвклидово расстояние между элементом кластера и центром масс кластера.

Рассмотрим данный алгоритм для двумерного пространства (плоскости). В данном случае каждый элемент рассматривается как точка на плоскости

и характеризуется своими координатами ( 7, 7}).

Координаты центра масс * -го кластера определяются как:

1 "I 1 "I

^ =1XX, У^ =1 Ху,

(4.7)

Также каждый объект (точка) может характеризоваться кроме координат

некоторым параметром («массой») т . Тогда центр масс будет определяться как (центр масс плоской фигуры):

1 п 1 п

= Xт7х7, у™ = Xт,у1, т(Е) = Хт1

т, 7=1 т, 7=1 7<=Л . (4.8)

В FOREL задается размер кластера К. В двумерной задаче на геометрической плоскости под К понимается максимальное расстояние от элемента кластера до его центра масс (радиус).

Каждый элемент также рассматривается как точка на плоскости и характеризуется

своими координатами ( , ).

Координаты центра масс * -го кластера определяются согласно (4.7) или (4.8). Алгоритм кластеризации включает в себя следующие основные шаги:

1. Задаются границы области, координаты объектов (точек) 1 = {11'12'"'1п} и максимальный размер кластера номер кластера * =1.

т

2. Выбирается случайная точка * в заданной области. Эту точку на начальном этапе принимаем за центр масс кластера.

3. Все объекты, находящиеся на расстоянии не более R, приписываются к данному кластеру.

4. Для полученного кластера вычисляется центр масс, согласно формулам (4.7)

т т

или (4.8) '. Если вычисленные координаты центра масс совпадают с точкой ', то

полагаем, что кластер * определен, все приписанные данному кластеру точки помечаются номером кластера и исключаются из дальнейшего рассмотрения. Переход к п. 5 (поиск следующего кластера).

Если вычисленные координаты центра масс не совпадают с точкой, то процесс

т. = т. 0

поиска продолжается, т. е. принимаем г г, переход к п. 3.

5. Проверяем, остались ли объекты, не отнесенные ни к одному кластеру. Если нет, то все кластеры определены, завершение поиска (к п. 6).

Если объекты остались, то переход к п. 2 (поиск очередного кластера).

6. Выводим данные о принадлежности объектов к кластерам, центре масс полученных кластеров. Конец поиска.

Примечание. Во время поиска очередного кластера может оказаться, что на удалении менее К от выбранного центра масс нет ни одного объекта. В таком случае следует произвести выбор нового центра масс (случайный выбор). Общий алгоритм FOREL приведен на Рисунке 4.12.

Следует отметить, что аналогично кластеризации в двумерном пространстве данную задачу можно решать и для трехмерного пространства, в случае, когда элементы сети расположены не на плоской поверхности.

После решения задачи выбора точек снятия данных необходимо найти траекторию движения БПЛА. Вероятно, можно предъявлять различные требования к свойствам искомой траектории, например, такие как протяженность (длина), число посещаемых точек снятия данных, угол изменения направления движения, высота полета и т. д. При решении данной задачи будем принимать в качестве критерия только длину пути. Найденные точки снятия данных представим вершинами полного графа. Будем полагать, что БПЛА может начинать и заканчивать облет точек сбора в любых точках над обслуживаемой территорией. Эти точки могут находиться как в вершинах полученного графа, так и вне графа. В последнем случае граф должен быть дополнен двумя вершинами, соответствующими этим точкам. Можно показать, что если требуется начинать и заканчивать облет в одной и той же точке, то она может быть представлена двумя точками, расстояние между которыми равно нулю. В общем случае искомая траектория представляет собой маршрут, при движении по которому, при обходе всех вершин графа, длина пройденного пути минимальна.

Если протяженность маршрута оказывается больше максимально допустимой (возможной дальности полета БПЛА или времени доставки данных), то следует отыскать несколько маршрутов, обеспечивающих параллельное решение данной задачи снятия данных. В общем случае решение задачи, состоящей в том, чтобы «стянуть» заданное число вершин исходного графа ребрами с минимальным суммарным весом, связано с нахождением минимального дерева Штейнера ^МТ). Известно, что данная задача не имеет общего решения [51, 172]. Если дополнить требования к маршруту, потребовав, чтобы он проходил через каждую из вершин только один раз, то данная задача сводится к задаче поиска минимального гамильтонова цикла или цепи (задача коммивояжера). Данная задача относится к классу ЫР-сложных задач. При относительно малом числе вершин графа она может быть решена полным перебором возможных вариантов. Однако при росте числа вершин (размера сети) ее сложность возрастает экспоненциально. Подробнее о решении задачи коммивояжера написано в следующем разделе.

Математическая задача поиска оптимального маршрута

Задача коммивояжера

Задача коммивояжера (от фр. commis voyageur — бродячий торговец; англ. Travelling salesman problem, сокращенно TSP) — задача, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. Задача коммивояжера является одной из самых известных задач комбинаторной оптимизации.

В классической задаче коммивояжера рассматривается n городов и матрица попарных расстояний между ними. Требуется найти такой порядок посещения городов, чтобы суммарное пройденное расстояние было минимальным, каждый город посещался ровно один раз и коммивояжер вернулся в тот город, с которого начал свой маршрут. Другими словами, во взвешенном полном графе требуется найти гамильтонов цикл минимального веса.

Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжера (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), метрическая задача коммивояжера (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжера. Также существует обобщение задачи, так называемая обобщенная задача коммивояжера.

Задача коммивояжера относится к классу NP-полных задач. Для лучшего понимания рассмотрим существующие классы сложности задач распознавания.

Класс Р (от англ. polynomial) — класс задач полиномиальной сложности. Такие задачи называются также практически разрешимыми. Класс P состоит из задач распознавания, разрешимых за полиномиальное время. Другими словами, число элементарных операций для решения таких задач ограничено сверху полиномом от длины записи исходных данных.

Класс EXP — класс задач экспоненциальной сложности. В общем случае (т. е. для исходных данных, наиболее «неудобных» для любого из алгоритмов, решающих задачу) требуется количество операций, увеличивающееся с ростом n, по крайней мере, экспоненциально.

Класс NP (от англ. non-deterministic polynomial) — недетерминированной полиномиальной сложности. Класс NP содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество времени. Данный класс является более широким и включает в себя все задачи P-класса.

В классе NP выделяют задачи, к которым можно свести любую другую задачу из класса NP за полиномиальное время. Такие задачи называются NP-полными. В некотором смысле эти задачи образуют подмножество «самых сложных» задач в классе NP.

Представление задачи коммивояжера в виде графа

Для возможности применения математического аппарата для решения поставленной проблемы ее следует представить в виде математической модели. Проблему коммивояжера можно представить в виде модели на графе, то есть используя вершины и ребра между ними. Таким образом, вершины графа соответствуют узлам,

а ребра (hj) между вершинами г и i— пути сообщения между этими узлами. Каждому

ребру (h 3) можно сопоставить критерий выгодности маршрута сч ^ который можно понимать как, например, расстояние между узлами, время или необходимые энергетические затраты на преодоление данного расстояния и др.

В целях упрощения задачи и гарантии существования маршрута обычно считается, что модельный граф задачи является полностью связным, то есть что между произвольной парой вершин существует ребро. В тех случаях, когда между отдельными узлами не существует сообщения, этого можно достичь путем ввода ребер с максимальной длиной. Из-за большой длины такое ребро никогда не попадет к оптимальному маршруту, если он существует.

Гамильтоновым циклом называется маршрут, который проходит через каждую вершину графа ровно по одному разу. Таким образом, решение задачи коммивояжера — это нахождение гамильтонова цикла минимального веса в полном взвешенном графе.

В зависимости от того, какой критерий выгодности маршрута сопоставляется величине ребер, различают различные варианты задачи, важнейшими из которых являются симметричная и метрическая задачи.

В общем случае асимметричная задача коммивояжера отличается тем, что она моделируется ориентированным графом, т. е. для ее решения следует также учитывать направления ребер графа. В случае симметричной задачи все пары ребер между

одними и теми же вершинами имеют одинаковую длину, то есть для ребра (hJ) одинаковы длины с~1з ~ а моделируемый граф является неориентированным. В симметричном случае количество возможных маршрутов вдвое меньше асимметричного случая.

Симметричную задачу коммивояжера называют метрической, если относительно длин ребер выполняется неравенство треугольника. Условно говоря, в таких задачах

обходные пути длиннее прямых, то есть ребро от вершины г до вершины 3 никогда не

Существующие методы решения задачи коммивояжера

Ниже рассмотрены группы методов решения задач коммивояжера, которые относят к простейшим.

Метод полного перебора (метод «грубой силы», англ. brute force)

Точное решение задачи коммивояжера можно найти методом полного перебора всех возможных вариантов, то есть «вручную» вычислить длины всех возможных маршрутов и выбрать маршрут с наименьшей длиной. Однако даже для небольшого количества узлов решать задачу таким способом практически невозможно. Для простого

маршрутов, то есть для 15 узлов существует 43 миллиарда маршрутов, а для 18 узлов — уже 177 триллионов. Таким образом, метод полного перебора с уверенностью можно назвать непригодным для нахождения решения задачи коммивояжера.

Метод случайного перебора

Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится довольно быстро, так что можно находить решение многократно и запоминать наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска.

Алгоритм штрафования вершин

В этом алгоритме используется идея преобразования матрицы весов графа, при котором различные категории деревьев штрафуются по-разному, но в то же время относительные веса всех деревьев в пределах одной категории не изменяются. Цель при этом состоит в том, чтобы разделить различные категории и сделать категорию гамильтоновых цепей менее штрафуемой, а тогда применение алгоритма минимального дерева автоматически приведет к кратчайшей гамильтоновой цепи.

Рассматривается полный граф. К каждому элементу строки или столбца матрицы весов этого графа добавляется достаточно большое число. Получается результирующая матрица весов. Далее находится кратчайший остов графа. Если он оказывается гамильтоновой цепью, то задача решена. Если нет, происходит

бывает длиннее пути через промежуточную вершину k: Ct3 ^ Clfc + ckj.

варианта, симметричнои задачи с п узлами, существует

возможных

штрафование вершин, степень которых больше 2, после чего вновь ищется кратчайший остов графа и т. д., пока не будет найдено решение.

Жадные алгоритмы

Жадный алгоритм — алгоритм нахождения наикратчайшего расстояния путем выбора самого короткого, еще не выбранного ребра, при условии, что оно не образует цикла с уже выбранными ребрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за «жадность».

К жадным алгоритмам можно отнести такие методы, как метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения.

Метод ближайшего соседа

Метод заключается в следующем: узлы последовательно включаются в маршрут, причем каждый очередной включаемый узел должен быть ближайшим к последнему выбранному узлу среди всех остальных, еще не включенных в состав маршрута.

Рассмотрим пример, который покажет неэффективность данного метода. Пусть есть сеть, узлы которой расположены в виде ромба (Рисунок 4.13). Коммивояжер стартует из узла 1. Алгоритм ближайшего узла на следующем шаге добавит в маршрут узел 2, затем 3, затем 4; на последнем шаге придется возвращаться в узел 1 по самой длинной диагонали ромба. В результате получится не кратчайший, а длиннейший путь.

Метод ближайшего города на каждом шаге алгоритма проводит допустимый маршрут по текущему подмножеству пунктов обхода, уже включенных в маршрут, добавляя к нему новый пункт из числа еще не включенных в маршрут, для которого найдется ближайший сосед из числа пунктов, уже принадлежащих маршруту обхода плана. Новый пункт включается в маршрут после своего соседа, которому он обязан включением. Звенья маршрута модифицируются так, чтобы расширенный маршрут являлся допустимым.

Метод самого дешевого включения на каждом шаге алгоритма проводит допустимый маршрут по текущему подмножеству пунктов обхода, уже включенных в маршрут, добавляя к нему новый пункт, включение которого между некоторыми смежными пунктами приводит к минимальному увеличению стоимости (длины) маршрута [244].

Среди вышеописанных жадных алгоритмов по качеству оптимальности решения лучшим является метод самого дешевого включения, однако он же требует максимальной вычислительной трудоемкости. Наименее трудоемким из описанных жадных алгоритмов является метод ближайшего соседа.

Метод минимального остовного дерева (деревянный алгоритм)

Деревянный алгоритм для решения задачи коммивояжера — следующий: на исходном графе сети строится кратчайшее остовное дерево и удваиваются все его ребра. Результатом является связный граф, вершины которого имеют только четные степени. Затем строится эйлеров цикл, начиная с вершины 1, цикл задается перечнем вершин. Просматривается перечень вершин, начиная с 1, и зачеркивается каждая вершина, которая повторяет уже добавленную в последовательность. После этого остается путь, который и является результатом алгоритма. Доказано, что деревянный алгоритм ошибается менее чем в два раза, поэтому такие алгоритмы называют приблизительными, а не просто эвристическими.

Метод имитации отжига

Название данного алгоритма связано с методами имитационного моделирования в статистической физике, основанными на технике Монте-Карло. Исследование кристаллической решетки и поведения атомов при медленном остывании тела привело к появлению на свет вероятностных алгоритмов, которые оказались чрезвычайно эффективными в комбинаторной оптимизации.

Алгоритм имитации отжига относится к классу пороговых алгоритмов локального поиска. На каждом шаге этого алгоритма для текущего решения ik в его окрестности N(ik) выбирается некоторое решение j, и если разность по целевой функции между новым и текущим решением не превосходит заданного порога tk, то новое решение j заменяет текущее. В противном случае выбирается новое соседнее решение.

На практике применяются разные модификации алгоритмов, описанные ниже.

Метод ветвей и границ

Метод ветвей и границ является одним из методов неявного перебора, в основе которого лежит идея последовательного разбиения множества допустимых решений. На каждом шаге метода элементы разбиения (подмножества) подвергаются анализу на содержание оптимального решения. Если рассматривается задача на минимум, то проверка осуществляется путем сравнения нижней оценки значения целевой функции на данном подмножестве с верхней оценкой функционала. В качестве оценки сверху используется значение целевой функции на некотором допустимом решении. Допустимое решение, дающее наименьшую верхнюю оценку, называют рекордом. Если оценка снизу целевой функции на данном подмножестве не меньше оценки сверху, то рассматриваемое подмножество не содержит решения лучше рекорда и может быть отброшено. Если значение целевой функции на очередном решении меньше рекордного, то происходит смена рекорда. Пусть подмножество решений просмотрено, если установлено, что оно не содержит решения лучше рекорда. Если просмотрены все элементы разбиения, алгоритм завершает работу, а текущий рекорд является оптимальным решением. В противном случае среди не просмотренных элементов разбиения выбирается множество, являющееся в определенном смысле перспективным. Оно подвергается разбиению (ветвлению). Новые подмножества анализируются по описанной выше схеме. Процесс продолжается до тех пор, пока не будут просмотрены все элементы разбиения.

Метод генетических алгоритмов

Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Данный алгоритм является разновидностью эволюционных вычислений. Генетические алгоритмы служат главным образом для поиска решений в многомерных пространствах поиска.

Общая схема алгоритма состоит из следующих шагов: инициализация начального поколения; оценка особей в поколении по определенным критериям; отбор лучших из оцененных особей; скрещивание особей для формирования нового поколения; мутация особей нового поколения (возможны как небольшие изменения, так и создание совершенно новой особи). Данный набор действий повторяется итеративно, тем самым моделируя «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть: нахождение глобального либо субоптимального решения; исчерпание

числа поколений, отпущенных на эволюцию; исчерпание времени, отпущенного на эволюцию [179].

Примером генетического алгоритма может служить алгоритм муравьиной колонии. Алгоритмы муравья, или оптимизация по принципу муравьиной колонии, основаны на присущих муравьям способностях ориентации в физическом пространстве и нахождении оптимального пути между муравейником и другими объектами окружающей среды (в частности, источником пищи). При этом при нахождении источника муравьи помечают путь к муравейнику феромонами (которые привлекают других муравьев для прохождения по данному пути). Когда другие муравьи проходят по помеченному пути и также находят источник пищи, они также помечают данный путь, и концентрация феромонов пути увеличивается. Таким образом, чем больше муравьев успеет пройти по пути, тем больше концентрация феромонов на данном пути и тем больше вероятность того, что другие муравьи также выберут данный путь. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения не только статичных, но и динамических проблем, например, в изменяющихся сетях.

Сравнительный анализ методов выбора траектории движения БПЛА Выбор методов поиска маршрута движения БПЛА в условиях задачи

Определим исходные данные для задачи. Примем найденные на предшествующем этапе точки сбора данных (центры масс кластеров в решении задачи

X = {х } / = 1 к

кластеризации) * ^ "' , где k — число найденных точек, за вершины полного графа G. Причем будем полагать, что граф неориентированный. Такое предположение допустимо, когда нет ограничений на направление движения БПЛА над территорией обслуживания. Для задания точек начала и конца маршрута дополним исходный граф

двумя вершинами и х соответственно. Полагаем, что координаты точек и х известны, следовательно, могут быть вычислены и расстояния от них до всех остальных вершин графа. Будем полагать, что решением задачи является маршрут между

заданными вершинами и х, проходящий через все вершины графа. Полагаем, что

маршрут должен начинаться в вершине и заканчиваться в вершине х, а также проходить через каждую из вершин графа только один раз, длина маршрута должна быть минимальна. При данных ограничениях решением задачи будет кратчайшая гамильтонова цепь (маршрут коммивояжера). Для ее решения могут быть использованы различные методы, точные — полного перебора — или приближенные, например

алгоритм, использующий дерево решений, или алгоритм штрафования вершин [172]. Точные методы требуют слишком большого объема вычислений, поэтому, с учетом имеющихся требований и простоты реализации, отдадим предпочтение алгоритму штрафования вершин (алгоритму Кристофидеса). Этот алгоритм имеет относительно простую реализацию и обеспечивает сходимость к оптимальному решению в большинстве случаев. Как показано в [172], в случае несходимости алгоритма к оптимальному решению может быть получено близкое к оптимальному решение. Метод, реализуемый алгоритмом штрафования вершин, основан на последовательном поиске кратчайших остовов графа (SST) и «штрафовании» вершин в них, степень которых превышает 2. Результатом выполнения алгоритма является кратчайший остов

x x

графа, все вершины которого, кроме вершин 5 и 1, имеют степень 2, т. е. искомый маршрут, длина которого близка к длине гамильтоновой цепи.

Если в задаче требуется построить несколько маршрутов, то исходный полный граф может быть разделен на необходимое число полных подграфов, для каждого из которых должна быть решена задача поиска оптимальных маршрутов движения БПЛА. Поиск маршрута алгоритмом штрафования вершин. Полагаем, что граф задан матрицей длин ребер:

c <œ; i, j = 1...k

ij ? J J

где k — число вершин графа.

Заменим значения в строках или столбцах i = s и i = t или j = s и j = t значениями

c = c + N ' j = 1 k c = c + N * i = 1 k

sj sj ' J ■■■ или is is , где N — достаточно большое число, т. е.

N >> cj ; i, j = 1. k

Со =

. Получим результирующую матрицу

С =

i, j = 1. k

Далее находим кратчайший остов по матрице C. Если он является гамильтоновой цепью, т. е. каждая из вершин графа, кроме s и t, имеет степень, равную 2, то задача решена. Если нет, то «оштрафуем» те вершины графа, степени которых превышают 2. Если вершина r имеет степень больше 2, то:

crr = cir +n-(Cr -2), i,Г = 1...к,

где п — величина штрафа.

Для обновленной матрицы C вновь находится кратчайший остов и производится проверка на гамильтонову цепь. Итерации повторяются, пока очередной кратчайший остов не будет представлять собой гамильтонову цепь, последняя и является решением

задачи. В общем случае, если число итераций слишком велико, а кратчайшая цепь еще не найдена, то итерационный процесс может быть остановлен, а для поиска использован иной метод. Следует отметить, что отличная от нуля вероятность того, что поиск не сойдется к оптимальному решению, характерна для многих известных методов. Данная проблема требует дальнейшего изучения, однако в рамках решаемой задачи в качестве практического решения можно предложить в таком случае модифицировать исходный граф, например, добавлением новой вершины со случайными координатами или изменением координат вершин, степень которых превышает 2, на случайную величину, лежащую в границах точности их оценки. Последнее фактически эквивалентно штрафованию вершины на некоторую случайную величину. В случае несходимости алгоритма и в таком случае, т. е. для гарантированного получения маршрута, возможно использовать, например, эвристический метод «ближайшего соседа», который дает менее точное решение, но гарантирует получение решения.

Возможность получения решения задачи зависит от того, существует ли искомый гамильтонов цикл (или цепь), и от сходимости алгоритма. Необходимое условие существования гамильтонова цикла следует из его определения и состоит в том, что все вершины исходного графа должны иметь степень не менее 2. В качестве достаточного условия можно использовать условие Поша [234], которое состоит в том, что если число

к, 0 < к < —

вершин графа п > 2 и если для любого 2 число вершин со степенями, не

превосходящими К не превосходит К то граф содержит гамильтонову цепь. Существенная особенность данной задачи состоит в том, что исходный граф является полным, т. е. каждая вершина связана с каждой, следовательно, каждая вершина имеет степень п -1. В этом случае условие Поша выполняется, следовательно, любой возможный граф является гамильтоновым графом. В этом случае возможность получения решения зависит только от сходимости алгоритма поиска маршрута (гамильтоновой цепи).

Сходимость и время выполнения алгоритма штрафования вершин существенно зависят от величины штрафа п. В [172] показано, что при слишком малой величине штрафа требуется большее число итераций, а при большой величине штрафа алгоритм может не сходиться. В той же работе предложено несколько подходов к выбору величины штрафа п.

Таким образом, в рамках данной работы проводится исследование и сравнительный анализ трех приближенных методов решения задачи коммивояжера для поиска кратчайшего пути по точкам:

1. Метод штрафования вершин штрафами постоянной величины.

2. Метод штрафования вершин штрафами случайной величины (модификация метода 1).

3. Метод ближайшего соседа.

Вышеперечисленные методы были выбраны ввиду простоты их реализации, высокой степени сходимости и близости получаемого пути к оптимальному.

Проведение тестирования выбранных методов

В качестве средства для тестирования рассматриваемых методов выбора кратчайшей траектории движения была использована программа, написанная на кафедре СС и ПД СПбГУТ. Программа написана на языке C# при помощи среды разработки Visual Studio.

Visual Studio — это бесплатная, полнофункциональная и расширяемая интегрированная среда разработки для создания современных приложений для Windows, Android и iOS, а также веб-приложений и облачных служб. Данный продукт позволяет разрабатывать как консольные приложения, так и приложения с графическим интерфейсом, в том числе с поддержкой технологии Windows Forms, а также веб-сайты, веб-приложения, веб-службы как в родном, так и в управляемом кодах для всех платформ, поддерживаемых Windows, Windows Mobile, Windows CE, .NET Framework, Xbox, Windows Phone.NET Compact Framework и Silverlight. Интерфейс программы тестирования показан на Рисунке 4.14.

Программа позволяет задать необходимое количество узлов наземного сегмента сети, через которые необходимо построить маршрут и которые являются вершинами графа (в интерфейсе программы — параметр n); сгенерировать случайное расположение данных узлов на плоскости (в рамках задачи — в наземном сегменте сети ЛСС; в интерфейсе программы — запускается при помощи кнопки <GenGraph>); провести эксперимент по нахождению кратчайшего пути через эти точки, используя один из трех методов выбора кратчайшего маршрута: метода штрафования вершин, его модификации со «случайными штрафами» и метода «ближайшего соседа» (в интерфейсе программы — запускаются при помощи кнопок <Penalty>, <Random Penalty> и <N neighbor>).

Form!

□

MalrC

I I Random Penalty

Prim's alg.

GenGraph Penalty alg.

1 6 1335,8021

6 14 679,1341 1

14 19 595,8046 2

19 12 530,273 2

12 5 543,9257 2

5 15 473,4983 2

15 3 596,293 2

3 17 555,1821 2

17 Э 557,4383 2

3 18 550,8891 2

18 4 581,6806 2

4 13 510,6581 2

13 11 552,2346 2

11 1G 564,9611 2

1G 10 520,9042 2

10 20 535,120 2

20 7 451,1248 2

7 8 571,5032 2

8 2 1389,342 2

n = 20

MST Len = 1223.573 Iter = 592

H_

Iteration

593

Penalty

n penalty

N neighbor

Рисунок 4.14 - Интерфейс программы тестирования

В ходе выполнения расчетов программа отображает исходное расположение узлов наземного сегмента сети, полученный путь через все узлы, рассчитанную матрицу расстояний между узлами, через которые проходит путь, полученную длину пути и количество итераций, после которых был рассчитан путь.

Для анализа сходимости алгоритма и времени его выполнения были проведены испытания на достаточно большом наборе случайных полных графов различной размерности. При этом использовались постоянные положительные штрафы. Величина п выбиралась исходя из распределения длин ребер исходного графа. Ниже приведены результаты тестирования алгоритмов штрафования вершин, его модификации со «случайными штрафами» и метод «ближайшего соседа». Тестирование было произведено на графах различной размерности от 10 до 60, для каждого из размеров было проведено 20 тестирований на случайных графах. Вершины случайного графа представляли собой пуассоновское поле точек на плоскости, в области, ограниченной квадратом, а длины ребер — расстояния между ними. На Рисунке 4.15 приведен пример найденного маршрута в графе из 60 вершин.

Примеры результатов, полученных различными методами поиска, приведены на Рисунке 4.16. В примере: исходное поле точек, маршрут, найденный методом «постоянных штрафов». Для метода «случайных штрафов» приведены два варианта решения.

Анализ результатов тестирования метода

По результатам тестирования были получены оценки вероятности сходимости алгоритмов и погрешность длины полученного пути по отношению к методу «штрафования вершин» с постоянными штрафами, приведенные в Таблице 4.1.

Таблица 4.1. - Результаты тестирования алгоритмов поиска оптимального пути

Число вершин Постоянные штрафы Случайные штрафы Метод «ближайшего соседа»

Вероятность сходимости Среднее число итераций Среднее число итераций Относительная ошибка длины пути, % Относительная ошибка длины пути, %

10 1 95 94 0,91 12,92

20 1 610 147 3,72 17,05

30 1 4106 235 7,80 21,52

40 0,90 10 426 1168 20,87 26,14

50 0,45 13 475 1861 34,22 22,68

60 0,15 15 573 2426 38,33 21,57

Исходное поле «Постоянные штрафы»

п = 30 1508,1

«Случайные штрафы» - решение 1 «Случайные штрафы» - решение 2

/. = 1575,9 /.= 1615,2

«Ближайший сосед»

/. = 1955,5

Рисунок 4.16 - Примеры результатов поиска пути различными методами

На Рисунке 4.17 приведена зависимость вероятности сходимости для метода «постоянных штрафов» от числа вершин графа.

Число вершин

Рисунок 4.17 - Зависимость вероятности сходимости для метода «постоянных

штрафов» от числа вершин графа

Как было получено в эксперименте, вероятность сходимости начинает заметно снижаться при числе вершин графа больше 30, при числе вершин более 40 наблюдается резкое снижение вероятности сходимости алгоритма. Следует отметить, что алгоритмы «случайных штрафов» и «ближайшего соседа» обеспечивали 100%-ную сходимость во всем диапазоне размеров графа.

На Рисунке 4.18 приведена зависимость относительной ошибки длины найденного маршрута для методов «случайных штрафов» и «ближайшего соседа», по отношению к методу с постоянными штрафами.

Как видно из приведенных графиков, при малом числе вершин величина относительной ошибки метода «случайных штрафов» ниже, чем метода «ближайшего соседа». Однако при увеличении числа вершин до 45-50 наблюдается рост ошибки данного метода, по сравнению с методом «ближайшего соседа». Следует отметить, что вычислительная сложность этих методов существенно отличается в пользу метода «ближайшего соседа».

На Рисунке 4.19 приведена зависимость числа итераций для методов «постоянных штрафов» и «случайных штрафов». Здесь под итерацией понимается однократное выполнение алгоритма поиска минимального остовного дерева. Как видно из рисунка, число итераций, необходимых для получения решения, при использовании метода «случайных штрафов» значительно меньше, хотя и соизмеримо с числом итераций для метода «постоянных штрафов».

Число вершин

Рисунок 4.18 - Зависимость относительной ошибки длины найденного маршрута для методов «случайных штрафов» и «ближайшего соседа»

Число вершин

Рисунок 4.19 - Зависимость числа итераций для методов «постоянных штрафов» и

«случайных штрафов»

На данном рисунке не приведены значения числа итераций для метода «ближайшего соседа», т. к. он использует иной способ поиска маршрута, который в данном сравнении можно рассматривать как одну-единственную итерацию, независимо от числа вершин графа, соизмеримую по сложности с поиском остовного дерева.

Следует отметить, что возможно улучшить результаты работы алгоритма, именуемого в данной работе методом «постоянных штрафов», выбрав более эффективную стратегию «штрафования» вершин, как предложено в [51, 172]. В данной работе упомянутые модификации данного метода не рассматривались. Вероятно, эти модификации улучшат его сходимость, но существенно не уменьшат его вычислительную сложность, по сравнению с эвристическим методом «ближайшего соседа».

4.3. Комплекс моделей преднамеренного электромагнитного воздействия на летающие сенсорные сети, методы обнаружения и защиты от них

4.3.1. Обзор международной деятельности по исследованию преднамеренных электромагнитных воздействий

Открытое обсуждение проблемы преднамеренных электромагнитных воздействий началось на конференции АмерЭМ 1996 года с пленарной лекции профессора В. Лоборева [83, 399]. В феврале 1997 года на Цюрихском симпозиуме по электромагнитной совместимости Международный союз радиоинженеров URSI образовал специальный подкомитет с целью изучения проблемы электромагнитного терроризма под руководством Х. Уипфа. В феврале 1998 года состоялись парламентские слушания в конгрессе США. С этого момента исследования в США и ряде европейских стран (в первую очередь в Германии и Швеции) получили резкое ускорение.

Важным событием стала резолюция Совета URSI по преступной деятельности с помощью электромагнитных средств [449]. В 2000 году «Угроза электромагнитного терроризма» впервые стала отдельным разделом в списке тем Вроцлавского симпозиума по ЭМС 2000 года.

В 2001 году состоялась первая отдельная секция с рецензируемыми статьями Цюрихского симпозиума по ЭМС [430]. Затем доклады, связанные с ПД ЭМВ, стали появляться на каждом симпозиуме по ЭМС и на некоторых других конференциях. Из отечественных публикаций следует отметить раздел по ПД ЭМВ «Технологии защиты систем безопасности от электромагнитного терроризма» в книге [47]. Первая, целиком посвященная этой проблеме коллективная монография [301] появилась в России. Наконец, на Цюрихском симпозиуме по ЭМС 2007 года в Мюнхене впервые состоялся вводный курс по ПД ЭМВ (Tutorial on Intentional IEMI). Этот факт ярко свидетельствует о том, что накопилось уже довольно много научных исследований по этой проблеме, чтобы можно было знакомить с ее основами, и что необходимо знакомить с этой проблемой широкий круг специалистов [336, 337]. В течение последующих пятнадцати лет была

испытана огромная номенклатура объектов, начиная с вооружения и военной техники и заканчивая банкоматами, кассовыми аппаратами и т. п. [214, 302].

Позже появились книги из серии «Библиотека ЭМС» [46, 123], которые рассматривают специфику мощных электромагнитных воздействий на аппаратуру и средства телекоммуникации, а также справочник «Оружие мира» [255], в котором описаны основные типы электромагнитного оружия.

В России ежеквартально издается журнал «Технологии ЭМС», который освещает отечественные исследования по проблеме электромагнитных воздействий.

Ежегодно проводятся международные конференции и симпозиумы по данной проблеме. Основные из них: AMEREM/EUROEM, EMC (USA), EMC Asia, EMC Europe. В течение года проводятся рабочие встречи, организуемые идеологом данного направления Уильямом Радаски и его соратниками и объединяющие специалистов из разных стран по проблеме защиты от преднамеренных электромагнитных воздействий. Наиболее активными участниками являются США, Германия, Швеция, Япония, Китай и др.

4.3.2. Деятельность по разработке стандартов и выработке рекомендаций по защите от ПД ЭМВ в России и за рубежом

Как уже отмечалось, URSI инициировал, а Международная электротехническая комиссия (МЭК) организовала активную работу по созданию ряда новых стандартов, связанных с защитой от ПД ЭМВ. Эта работа идет по обычной схеме координации МЭК и ее подкомитетов с другими организациями (Рисунок 4.20 [14]).

Стоит отметить, что в 1999 году при МЭК был создан технический подкомитет ТК77С, занимающийся исключительно вопросами стандартизации в области преднамеренных мощных электромагнитных воздействий и защиты от них [54]. Доклады по состоянию работ по стандартизации в области ПД ЭМВ регулярно делают на симпозиумах по ЭМС Мануэль Уик и Уильям Радаски, председатель ТК77С в МЭК.

В настоящий момент основное внимание стандартов ^77C смещено в сторону защиты от ЭМИ высокой мощности (High Power Electromagnetic — HPEM). В настоящее время разработано более 21 международного стандарта и 5 технических докладов МЭК [1-21], в которых изложены обзор данного вида ЭМИ, методология измерений, параметры нагружения при испытаниях [340, 345, 346, 429, 436].

В странах ЕС

CENELEC

Институт стандартов Англии, VDE (Германия)

Рисунок 4.20 - Организация международной деятельности в области стандартов по ЭМС

За последнее время дополнительно разработаны стандарты (Тамбица 4.2) по методам защиты распределенных систем электронной инфраструктуры от ПД ЭМВ и методам оценки устойчивости систем к HPEM воздействиям [7, 20, 21], а также методам тестирования для оборудования и систем на устойчивость к данному виду воздействий.

Таблица 4.2 - Стандарты МЭК по защите и испытаниям от ПД ЭМВ

IEC/TR 61000-4-35 Электромагнитная совместимость. Части 4-35. Методы испытаний и измерений. Краткое руководство по устройствам, моделирующим HPEM.

IEC 61000-4-36 Электромагнитная совместимость. Методы испытаний и измерений. Преднамеренные силовые электромагнитные воздействия. Методы тестирования устойчивости оборудования и систем.

IEC/TS 61000-5-8 Электромагнитная совместимость. Части 5-8. Руководства по монтажу и подавлению помех. Методы защиты от HEMP для распределенной инфраструктуры.

IEC/TS 61000-5-9 Электромагнитная совместимость. Части 5-9. Руководства по монтажу и подавлению помех. Оценки магнитной восприимчивости на уровне системы для HEMP и HPEM.

В мире

IEC

В 2005 году МСЭ-Т были начаты обсуждения рекомендаций, связанных с исследованием влияния ПД ЭМВ на телекоммуникационную аппаратуру. До 2020 года запланировано выпустить ряд рекомендаций, в которых будут приведены значения ряда параметров воздействующего электромагнитного поля, таких как напряженность поля на различных расстояниях от источника излучений, длительность импульсов, частота следования и т. д., которые позволят оценить степень риска, и предложены соответствующие меры противодействия электромагнитным атакам как потенциальной угрозы для информационной безопасности [447, 448]. Одной из последних является Рекомендация МСЭ-Т ИК 5 K.81 "HPEM immunity guide for telecommunication systems", посвященная испытаниям на устойчивость телекоммуникационной аппаратуры и центров обработки данных к ПД ЭМВ [23, 122], а также стандарт IEEE P1642 "Recommended Practice for Protecting Public Accessible Computer Systems from Intentional EMI" [32], в котором приводятся практические методы защиты компьютерных систем от ПД ЭМВ.

Опираясь на международный опыт создания стандартов, направленных на защиту от электромагнитной угрозы, в России ведется работа по созданию системы национальных стандартов в области защиты информации от преднамеренных электромагнитных воздействий.

При Федеральной службе по техническому и экспортному контролю РФ (ФСТЭК) сформирован технический комитет по стандартизации «Защита информации» (ТК 362). Этим комитетом разрабатывается целевая система стандартов по защите от ПД ЭМВ [54, 163, 365, 366, 367, 471].

В 2007 году данная угроза включена в состав ГОСТ Р 50922-2007, содержащий термины, определения и перечень факторов, воздействующих на информацию. В этом же году разработан ГОСТ Р 52863-2007 «Защита информации. Автоматизированные системы в защищенном исполнении. Испытания на устойчивость к преднамеренным силовым электромагнитным воздействиям. Общие требования». Этот ГОСТ устанавливает [31]:

• требования устойчивости к ПД ЭМВ;

• степени жесткости испытаний;

• методы испытаний.

В начале 2010 года принят ГОСТ Р 51317.1.5-2009 «Совместимость технических средств электромагнитная. Воздействия электромагнитные большой мощности на системы гражданского назначения. Основные положения». Стандарт дает общее введение в данную область деятельности, термины и определения, а также содержит

сведения об электромагнитных воздействиях большой мощности, их влиянии на системы гражданского назначения и методах защиты систем от электромагнитных воздействий большой мощности.

В 2014-2015 годах приняты и введены в действие ГОСТы:

• ГОСТ Р 56103-2014 «Защита информации. Автоматизированные системы в защищенном исполнении. Организация и содержание работ по защите от преднамеренных силовых электромагнитных воздействий. Общие положения».

• ГОСТ Р 56093-2014 «Защита информации. Автоматизированные системы в защищенном исполнении. Средства обнаружения преднамеренных силовых электромагнитных воздействий. Общие требования».

Введение стандартов в действие в совокупности с ГОСТ Р 52863-2007 позволило образовать основу нормативной базы, которая стала одной из основополагающих компонент отечественной системы организационно-технических мероприятий по защите информации от данной угрозы. Последующее развитие и конкретизация нормативной базы должны производиться уже преимущественно на ведомственном уровне.

Дальнейшими направлениями деятельности по данной тематике являются:

1. Разработка ГОСТ по организации и проведению контроля защищенности автоматизированных систем в защищенном исполнении (АСЗИ) от ПД ЭМВ.

2. Развитие и конкретизация положений стандартов в нормативных документах ведомств/отраслей с учетом их специфики. Такими документами должны стать:

• модель угроз;

• специальные требования и рекомендации;