Методы и средства организации вычислений в туманных средах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Сафроненкова Ирина Борисовна
Сафроненкова Ирина Борисовна
кандидат наук
2022
- Специальность ВАК РФ05.13.11
- Количество страниц 166
Оглавление диссертации кандидат наук Сафроненкова Ирина Борисовна
ВВЕДЕНИЕ
1 АНАЛИЗ ПРОБЛЕМ И СОВРЕМЕННЫХ ТЕНДЕНЦИЙ В ОБЛАСТИ ОРГАНИЗАЦИИ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ
1.1 Технология грид-вычислений
1.1.1 Глобальные исследования, основанные на грид-вычислениях
1.2 Технология облачных вычислений
1.2.1 РСАПР на базе технологий облачных вычислений
1.3 Технология туманных вычислений в распределенных системах и проблемы организации вычислительного процесса
1.4 Краткие выводы
2 АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ОПТИМИЗАИЦОННЫХ ЗАДАЧ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ
2.1 Использование популяционных алгоритмов для решения оптимизационных задач в распределенных системах
2.1.1 Модели распараллеливания популяционных алгоритмов
2.1.2 Анализ способов разбиения параллельных популяционных алгоритмов
2.2 Анализ моделей, методов и алгоритмов решения задачи переноса вычислительной нагрузки
2.2.1 Анализ формальных постановок задачи переноса вычислительной нагрузки
2.2.2 Задача переноса вычислительной нагрузки в РИУС, реализованной на базе концепции туманных вычислений
2.2.3 Анализ применения онтологий для решения оптимизационных задач в распределенных системах
2.3 Краткие выводы
3. МЕТОДЫ И СРЕДСТВА ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ В ТУМАННЫХ СРЕДАХ
3.1 Метод формирования ограничений в задаче переноса вычислительной нагрузки в распределенной системе
3.2 Методика размещения вычислительной нагрузки распределённой системы в среде туманных вычислений
3.3 Метод формирования онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенных систем
3.4 Методика выбора стратегии опроса узлов туманного слоя
3.5 Система продукционных правил выбора узлов на основе онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенных систем
3.6 Аналитическая оценка эффективности метода уменьшения времени решения задачи переноса вычислительной нагрузки
3.7 Применение разработанного метода в задачах организации вычислительного процесса в РСАПР
3.8 Краткие выводы
4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ
4.1 Цель и основные задачи построения программных средств
4.2 Вычислительный эксперимент
4.3 Краткие выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
Приложение А
Приложение Б
ВВЕДЕНИЕ
Четвертая промышленная революция (Industry 4.0) рассматривается учеными как интеграция современных концепций распределенных вычислений, сетевых технологий и промышленности [1]. Industry 4.0 предполагает внедрение киберфизических систем в производство и обслуживание разнообразных повседневных потребностей человека, в том числе его трудовую и досуговую деятельность. Более того, перспективным видится объединение множества предприятий в глобальную промышленную сеть Вещей и услуг [2]. Туманные вычисления в настоящее время являются перспективной концепцией организации распределенных вычислений, которые предполагают приближение обработки данных к оконечным устройствам сетей и являются развитием облачной концепции [3]. Это позволяет снизить нагрузку на коммуникативную сеть и сократить время отклика системы. На сегодняшний день туманная инфраструктура реализована посредством многоцелевых децентрализованных платформ, таких как AWS IoT Greengrass, Azure Functions, SONM и др. [4-7].
На базе туманной концепции эффективно реализуются различные распределенные системы, для которых быстродействие является важнейшим критерием. Такие системы являются крайне востребованными во многих областях человеческой деятельности, таких как авиационная и космическая промышленность, атомная энергетика, нефтегазодобывающая отрасль. Системы мониторинга и прогнозирования, функционирующие на базе технологий туманных вычислений, успешно применяются для географически распределенного сбора и последующей обработки разнородных данных, включая отслеживание опасных природных явлений в режиме реального времени и долгосрочную оценку социальных процессов. Управление сложными технологическими процессами и объектами в режиме реального времени,
является возможным с использованием распределенных систем управления, реализованных на базе современных сетевых технологий [8, 9].
В процессе функционирования распределенной системы зачастую возникает необходимость решения задачи реконфигурации системы, процедура которой может повторяться многократно ввиду динамичности туманной среды. Задача реконфигурации связана с переназначением (переносом) решаемых подзадач по работоспособным вычислительным узлам [10]. Задача переноса вычислительной нагрузки относится к классу классу МР-полных, а с учетом весьма большого числа узлов туманного слоя, приводит к необходимости решения оптимизационной задачи большой размерности. Это требует значительных временных затрат, которые могут существенно уменьшить положительный эффект от переразмещения вычислительной нагрузки, а значит, негативно сказаться на эффективности функционирования всей системы.
Задача переноса вычислительной нагрузки, в случае отсутствия заранее подготовленных описаний конфигураций, включает два этапа:
1) выбор вычислительных узлов для размещения нагрузки;
2) решение задачи размещения нагрузки (формирование расписания) [11].
В рамках настоящего исследования автор предлагает метод, позволяющий сократить временные издержки, связанные с процессами реконфигурации системы, за счет сокращения множества узлов-кандидатов для размещения нагрузки и времени его формирования на основе онтологического анализа с целью повышения эффективности функционирования распределенной системы, реализованной на базе технологий туманных вычислений.
Актуальность. Значительное расширение областей применения распределенных систем обусловлено множеством факторов, среди которых: необходимость обрабатывать большие данные в географически распределенной среде, высокие требования к производительности с возможностью масштабируемости вычислительных систем, необходимость совместного использования ресурсов, выполнение требований к отказоустойчивости
вычислительных систем [8, 12- 14]. Распределенные системы, реализованные на базе технологий туманных вычислений, отвечают большей части требований современности. Однако в таких системах имеют место временные издержки, связанные с процессами реконфигурации системы, которые в условиях туманной среды происходят многократно [15], что оказывает негативное влияние на эффективность функционирование системы. Эффективность функционирования системы - это свойство, характеризующее степень способности системы выполнять свою функцию по назначению (достижение цели) [16]. В контексте данной работы эффективность определяется соотношением времени решения собственно функциональной задачи к общему времени, затраченному системой на получение результата с учетом издержек, связанных с организацией вычислительного процесса. Одной из задач, которые решаются при организации вычислительного процесса является задача переноса вычислительной нагрузки. В этой связи, сокращение времени решения данной задачи позволяет повысить эффективность функционирования распределенной системы.
Задача размещения вычислительной нагрузки тесно связана с задачами построения расписаний и двумерной упаковки. Данные задачи не новы, глубоко исследованы и имеют множество приложений. Р.В. Конвей, В.Л. Максвелл, Л.В Миллер, Б.С. Бейкер (B.S. Baker), Э.Дж. Кофман (E.J.Coffman), П. Бракер (P.Brucker), Н.Н. Кузюрин, Грушин Д.А., С.А. Фомин, А.И. Поспелов, С.Н. Жук и ряд других авторов посвятили свои работы исследованию данной проблемы [11, 17-22].
Однако туманная среда обладает особенностями, которые накладывают свои ограничения на модели, методы и алгоритмы, применяемые для решения задачи переноса вычислительной нагрузки [23]. В настоящее время существует ряд работ, в которых предложена математическая модель задачи размещения вычислительной нагрузки, учитывающая географическую распределенность сети, свойственную туманным средам, и метод ее решения для распределенных информационно-управляющих систем (РИУС) [12, 24-25]. Однако предлагаемый
метод является итерационным, что говорит о невозможности предсказания времени завершения его работы. Для широкого круга распределенных систем это является неприемлемым, поскольку в определенных условиях выполнение их функциональных задач становится недостаточно эффективным, либо даже невозможным.
В связи с этим, разработка новых методов, направленных на сокращение временных издержек при организации вычислительного процесса в географически распределенных системах, функционирующих на базе туманных вычислений, является актуальной задачей.
Цель диссертационной работы. Целью настоящего исследования является повышение эффективности функционирования распределенных систем, реализованных на базе концепции туманных вычислений.
При этом основной научной задачей является разработка методов, направленных на снижение временных издержек при организации распределенных вычислений в туманных средах.
Для достижения указанной цели в диссертационной работе были поставлены следующие задачи:
1. Разработать метод формирования ограничений в задаче переноса вычислительной нагрузки.
2. Разработать методику выбора стратегии опроса узлов туманного слоя.
3. Разработать методику размещения вычислительной нагрузки распределенной системы в среде туманных вычислений.
4. Разработать метод формирования предметной онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенных систем.
5. Создать программные средства, реализующие процедуру онтологического анализа.
Объект исследования. Объектом настоящего исследования являются географически распределённые системы, реализованные на базе концепции
туманных вычислений, решающие задачи с использованием алгоритмов с возможностью распараллеливания.
Предмет исследования. Предметом исследования данной диссертационной работы являются методы, направленные на сокращение временных издержек в процессе реконфигурации в распределенных системах, функционирующих на базе концепции туманных вычислений.
Методы исследования. В настоящей работе использованы методы теории исследования операций, теории организации параллельных вычислений, поисковой оптимизации, онтологического инжиниринга, объектно-ориентированного программирования. Основные результаты, полученные в диссертационном исследовании, подтверждаются результатами вычислительного эксперимента.
Научная новизна работы. Научная новизна работы состоит в использовании онтологического подхода к решению задачи переноса вычислительной нагрузки в распределенной системе, функционирующей в туманной среде. В работе:
1. Разработан метод формирования ограничений в задаче переноса вычислительной нагрузки, отличающийся от аналогов применением процедуры онтологического анализа. Это позволяет сократить множество узлов-кандидатов для размещения вычислительной нагрузки и время его формирования за счет знаний о решаемой в распределённой системе функциональной задаче, которые отражены в предметной онтологии (пункт 3, пункт 9 паспорта специальности 05.13.11), страницы 68-72 диссертационной работы.
2. Разработана методика выбора стратегии опроса узлов туманного слоя, отличающаяся учетом сведений о локализации вычислительной подзадачи в туманном слое и топологии сети, и позволяющая сократить время опроса узлов туманного слоя (пункт 9 паспорта специальности 05.13.11), страницы 80-87 диссертационной работы.
3. Разработана методика размещения вычислительной нагрузки, отличающаяся совокупным использованием метода формирования ограничений и методики выбора стратегии опроса туманного слоя. Это позволяет уменьшить время решения задачи переноса вычислительной нагрузки за счет сокращения поискового пространства узлов-кандидатов а также за счет подбора наиболее эффективной стратегии опроса (пункт 3, пункт 9 паспорта специальности 05.13.11), страницы 72-75 диссертационной работы.
4. Разработан метод формирования предметной онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенной системы, отличающийся от аналогов учетом особенности алгоритмических структур популяционных алгоритмов с точки зрения объема и частоты информационных обменов между процессами (пункт 3, пункт 9 паспорта специальности 05.13.11), страницы 75-80 диссертационной работы.
На защиту выносятся следующие новые научные результаты:
1. Метод формирования ограничений в задаче переноса вычислительной нагрузки в распределенной системе, основанный на проведении процедуры онтологического анализа.
2. Метод формирования предметной онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенной системы.
3. Методика размещения вычислительной нагрузки распределённой системы в среде туманных вычислений, основанная на совокупном использовании метода формирования ограничений и методики выбора стратегии опроса узлов туманного слоя.
Практическая ценность работы заключается в том, что разработанные методы и методика позволяют повысить эффективность функционирования географически распределенных систем, реализованных на базе концепции туманных вычислений.
Созданный на основе новых методов и методики программный модуль онтологического анализа для распределённой САПР позволяет автоматизировать процедуру формирования ограничений в задаче переноса вычислительной нагрузки.
Полученные результаты позволяют сократить временные издержки, связанные с организацией вычислительного процесса в части переноса вычислительной нагрузки, в среднем в 2,5 раза в сравнении с методом-аналогом.
Реализация и внедрения результатов работы. Теоретические и практические результаты диссертационной работы внедрены в ФГБУН «Федеральный исследовательский центр Южный научный центр Российской академии наук», использовались в НИР Южного федерального университета, а также были использованы в учебном процессе Института компьютерных технологий и информационной безопасности ЮФУ. Основными из них, в которых автор принял участие в качестве исполнителя, являются: «Методы и средства построения высоконадежных реконфигурируемых систем мониторинга и диагностики на базе технологий «цифровой экономики»» (ГЗ №ГР АААА-А19-119011190173-6); НИР «Разработка и исследование моделей и методов управления самоорганизующимся групповым поведением мобильных роботов в условиях неопределенности» (Программа фундаментальных исследований РАН по приоритетным направлениям, определяемым президиумом РАН № 7, «Новые разработки в перспективных направлениях энергетики, механики и робототехники», № ГР АААА-А19-118020190041-1); НИР «Разработка методологии построения автоматизированных систем раннего предупреждения социальных возмущений» (грант РФФИ № 20-04-60485, №ГР АААА-А20-120071690059-8).
Апробация работы. Основные положения и результаты диссертационного исследования докладывались и обсуждались на конференциях различного уровня, таких как [26- 39]:
1. МНТК «6th Computer Science On-line Conference» (26-29 апреля, г. Прага, Чехия, 2017г.).
2. МНТК «2nd Creativity in Intelligent Technologies and Data Science» (1214 сентября, Волгоград, Россия, 2017г.).
3. МНТК «8th Computer Science On-line Conference» (24-27 апреля, г. Злин, Чехия, 2019г.).
4. МНТК «3rd Conference on Computational Methods in Systems and Software 2019» (3- 5 октября, г. Прага, Чехия, 2019).
5. МНТК «2019 International Seminar on Electron Devices Design and Production» (23-24 апреля, г. Прага, Чехия, 2019г.).
6. МНТК «Информационные технологии в бизнесе и производстве» (1820 февраля, г. Новосибирск, Россия, 2019г.).
7. МК « Conference on Applied Physics, Information Technologies and Engineering» (25-27 сентября, г. Красноярск, Россия, 2019г.).
8. МНТК «International Conference on Interactive Collaborative Robotics» (7-9 октября, г. Санкт-Петербург, Россия, 2020г.).
9. МНТК «10th Computer Science On-line Conference» (1 апреля, г. Злин, Чехия, 2021г.);
10. МНТК «International Conference on Intelligent Information Technologies for Industry» (30 сентября - 04 октября, г. Сочи, Россия, 2021г.).
11. МНТК «International Conference on Interactive Collaborative Robotics» (27-30 сентября, г. Санкт-Петербург, Россия, 2020г.).
12. МНТК «Future Technologies Conference» (28- 29 ноября, г. Ванкувер, Канада, 2021г.).
13. IX Всероссийская НТК «Проблемы разработки перспективных микро-и наноэлектронных систем» (г. Зеленоград, Россия, 2016г.).
14. XVII национальная конференция по искусственному интеллекту с международным участием (21-25 октября, г. Ульяновск, Россия, 2019г.).
15. 14-я Всероссийская Мультиконференция по проблемам управления (27 сентября — 02 октября, Дивноморское, Геленджик, 2021г.).
Основные результаты также были заслушаны и поддержаны на заседании Ученого совета ЮНЦ РАН (Протокол №3 от 20.04.2022г.).
Публикации. По теме диссертационной работы опубликовано 20 работ, в том числе 11 работ в журналах, индексируемых в базе Scopus, 7 работ, опубликованных в журналах из списка ВАК, 1 свидетельство о государственной регистрации программ для ЭВМ.
Личный вклад автора заключается в разработке метода формирования ограничений в задаче переноса вычислительной нагрузки в распределенной системе, новой методики выбора стратегии опроса узлов туманного слоя, методики размещения вычислительной нагрузки распределённой системы в среде туманных вычислений, метода формирования предметной онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенной системы и программного модуля, реализующего процедуру онтологического анализа.
Структура и объем работы. Диссертация состоит из: введения, трех разделов, заключения, изложенных на 166 страницах, содержит 75 рисунков, 13 таблиц, 159 наименований библиографии и приложения.
Во введении изложена цель работы, дано обоснование актуальности темы диссертации, описаны основные научные положения, выносимые на защиту, показана научная новизна и практическая ценность диссертационной работы, представлены апробации, реализации и внедрения диссертационной работы, а также приведено содержание разделов диссертации.
В первом разделе диссертационной работы проведен анализ проблем и современных тенденций в области организации распределенных вычислений. Дан обзор технологий организации распределенных вычислений. Выявлены основные проблемы, возникающие при использовании технологий грид-вычислений и облачной концепции в реализации распределенных систем. Прежде всего, это
возникновение задержек в сети, связанных с передачей больших объемов данных, и, соответственно возросшей нагрузкой на коммуникационные каналы. Сделан вывод, что в настоящее время туманные технологии рассматриваются как наиболее перспективные для реализации распределенных систем с точки зрения возможности смещения вычислительной нагрузки ближе к месту генерации данных. Однако при этом актуализируются проблемы, связанные с возникновением временных издержек при организации вычислений, в т.ч. при решении задачи переноса вычислительной нагрузки.
Во втором разделе диссертационной работы проведен анализ использования популяционных алгоритмов и их параллельных реализаций в решении оптимизационных задач в распределенных системах, описаны модели распараллеливания популяционных алгоритмов. Предложены способы разбиения параллельных реализаций популяционных алгоритмов с точки зрения рационального распределения вычислительной нагрузки в процессе функционирования распределенной системы, реализованной на базе технологий туманных вычислений. Автором проведен анализ математических моделей, методов и алгоритмов решения задачи переноса вычислительной нагрузки, в том числе в туманной среде. Выявлено, что большинство существующих моделей не учитывают географическую распределенность, свойственную туманным средам, и, соответственно, не могут быть использованы. Описаны модель и метод решения задачи реконфигурации в РИУС с использованием метода на основе локальных групп устройств (ЛГУ). Автором показано, что недостатком данного метода является его итеративность, а ввиду большого количества узлов -кандидатов, расположенных в туманной среде, процедура решения задачи переноса вычислительной нагрузки может занять неопределенное время, что, соответственно, негативно скажется на эффективности системы. На данном основании сделан вывод о необходимости ограничения множества узлов-кандидатов для переноса вычислительной нагрузки в распределенной системе. Показано, что использование онтологий в решении оптимизационных задач
весьма и эффективно, на основании чего предложено использовать онтологические модели для решения задач, связанных с организацией вычислительного процесса в распределенных системах.
В третьем разделе диссертационной работы разработан метод формирования ограничений для задачи переноса вычислительной нагрузки в распределенных системах, основанный на проведении процедуры онтологического анализа. Данный метод позволяет уменьшить временные издержки, связанные с организацией вычислительного процесса в распределенной системе за счет сокращения поискового пространства узлов-кандидатов для размещения нагрузки. Предложена методика выбора стратегии опроса узлов-кандидатов, расположенных в туманном слое, с учетом топологии вычислительной сети и их локализации в туманном слое. Разработана методика размещения вычислительной нагрузки распределённой системы в среде туманных вычислений, основанная на совокупном использовании метода формирования ограничений и методики выбора стратегии опроса узлов туманного слоя, заключающейся в возможности подбора наиболее эффективных алгоритмов опроса, необходимых для ее реализации. Разработан метод формирования онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенной системы, позволяющий учитывать особенности алгоритмических структур популяционных алгоритмов с точки зрения объема и частоты информационных обменов между процессами. На основе данного метода получена модель онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенной системы. Проведена аналитическая временная оценка предложенного метода, позволяющая оценить его эффективность в зависимости от используемых алгоритмов и в сравнении с методом-аналогом. Средний выигрыш по времени метода на основе онтологического анализа в сравнении с методом на основе ЛГУ составляет 2,5 раза в зависимости от комбинаций используемых алгоритмов. На примере решения задачи организации
вычислительного процесса в РСАПР проведена оценка эффективности метода на основе онтологического анализа, направленного на сокращение временных издержек. Показано, что применение разработанного метода к решению задачи переноса вычислительной нагрузки в РСАПР позволяет повысить качество проектирования до 5%.
В четвертом разделе диссертационной работы описаны цель и основные задачи построения программного модуля онтологического анализа для распределенной системы автоматизированного проектирования. Приведена и описана укрупненная архитектура программного модуля онтологического анализа, представлено ее назначение и основные функции. В рамках диссертационной работы проведена серия вычислительных экспериментов для оценки эффективности разработанного метода в различных условиях. Результаты вычислительных экспериментов продемонстрировали преимущество предложенного в работе метода по сравнению с существующим методом-аналогом.
В заключении приведены основные выводы и результаты диссертационной работы.
В приложении приведены свидетельство об официальной регистрации программы для ЭВМ и копии актов внедрения.
1 АНАЛИЗ ПРОБЛЕМ И СОВРЕМЕННЫХ ТЕНДЕНЦИЙ В ОБЛАСТИ ОРГАНИЗАЦИИ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ
Понятие «распределенных вычислений» может быть рассмотрено в широком и узком смыслах. Распределенные вычисления в широком смысле рассматривают как теоретическую основу для построения распределенных систем. Под распределенными вычислениями в узком смысле понимают использованием распределенных систем для решения задач высокой вычислительной сложности [40].
В настоящее время не существует строго определения распределенной системы, поэтому для более глубокого понимания данного концепта рассмотрим несколько из них.
Эндрю С. Таненбаум определяет распределенную систему как набор независимых компьютеров, объединенных программным обеспечением промежуточного уровня, и представляющихся их пользователям единой объединенной системой [41].
Также распределенную систему можно понимать как систему, в которой взаимодействие и синхронизация программных компонентов, выполняемых на независимых сетевых компьютерах, осуществляется посредством передачи сообщений.
Таким образом, с аппаратной точки зрения распределенная система представляет собой совокупность взаимосвязанных автономных компьютеров или процессоров, а с программной точки зрения - как совокупность независимых процессов, взаимодействующих посредством передачи сообщений [40- 42].
Ниже представлены основные способы организации распределенных вычислений и приведены примеры распределенных систем.
1.1 Технология грид-вычислений
Зарождение грид-технологий связано с необходимостью решения различных прикладных задач из области науки, медицины, экономики, производства и инженерии высокой вычислительной сложности, решение которых на отдельных компьютерах невозможно получить за разумное время. Грид-технологии рассматриваются как форма распределённых вычислений, в которой «виртуальный суперкомпьютер» представлен в виде кластеров, соединённых с помощью сети, слабосвязанных разнородных компьютеров, работающих вместе для выполнения многочисленных задач [43]. Грид-технологии - способ совместного скоординированного использования распределенных ресурсов [44]. Преимущество грид-технологий заключается в возможности проведения параллельных вычислений на неспециализированных компьютерах, связанных сетью, что значительно уменьшает их стоимость в сравнении с суперкомпьютерами (Рисунок 1). Различают добровольную грид, которые основаны на добровольном предоставлении свободных ресурсов ПК, научные грид-системы, реализующие хорошо распараллеливаемые приложения, и коммерческие, функционирующие на виртуальном компьютере, состоящем из набора физических компьютеров, объединенных посредством технологии грид [45].
Принципы организации грид-инфраструктуры:
- распределенность на множестве административных доменов,
- гетерогенность,
- распределенность,
- динамичность, адаптивность (устойчивость к отказам),
Рекомендованный список диссертаций по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», 05.13.11 шифр ВАК
Разработка системы запуска ресурсоемких приложений в облачной гетерогенной среде2013 год, кандидат технических наук Е Мьинт Найнг
Разработка технологии обеспечения высокоскоростных вычислений на основе облачной инфраструктуры2021 год, кандидат наук Кочовски Петар
Методы управления ресурсами в проблемно-ориентированных распределенных вычислительных средах2014 год, кандидат наук Шамакина, Анастасия Валерьевна
Исследование и разработка системы автоматизации процессов децентрализованного доступа и управления потоками данных облачных ресурсов2014 год, кандидат наук Касимов, Рустам Азатович
Метод и алгоритмы назначения заданий в распределенной информационной системе Интернета вещей2022 год, кандидат наук Степанова Мария Владимировна
Введение диссертации (часть автореферата) на тему «Методы и средства организации вычислений в туманных средах»
- виртуальность,
- механизм обнаружения ресурсов.
Узел Грид
Рисунок 1 - Обобщенная архитектура технологии грид-вычислений
Основные направления использования грид-технологий:
- организация эффективного использования вычислительных ресурсов временно простаивающих компьютеров для решения относительно небольших задач,
- решение очень сложных вычислительных задач, требующих огромные процессорные ресурсы, ресурсы памяти и т.д.,
- вычисления, связанные с обработкой большого объема географически распределенных данных,
- коллективные вычисления, подразумевающие участие пользователей из разных организаций [46].
1.1.1 Глобальные исследования, основанные на грид-вычислениях
Одним из направлений использования грид-технолгий является их применение для проведения глобальных исследований, подразумевающих выполнение огромных вычислений. World Community Grid - глобальная компьютерная сеть, занимающаяся грид-вычислениями для поиска решения глобальных научных задач [47]. Коллективные вычисления такого рода основаны на идеи добровольного участия пользователей в процессе проведения глобальных вычислений. Подключение к сети любого желающего возможно посредством программы-клиента, которая будет использовать вычислительные ресурсы компьютера, который не загружен в данный период времени. Таким образом, World Community Grid можно рассматривать как глобальное сообщество пользователей персональных компьютеров, которые предоставляют неиспользуемое время своих вычислительных систем для реализации глобальных исследовательских инициатив [48]. К настоящему времени в сообществе WCG зарегистрировано более 795 тыс. пользователей, которые представлены в 7,8 млн. вычислительными устройствами (Рисунок 2).
ПК добровольцев
Рисунок 2 - Обобщенная схема глобальных исследований грид-технологий
В настоящее время сообщество WCG проводит следующие проекты (Рисунок 3).
Рисунок 3 - Текущие проекты сообщества WCG
Более того, множество проектов уже являются завершенными: проект по изучению пространственной структуры белков человеческого организма и изучению их функций (Human Proteome Folding — Phase 1), проект по поиску новых методов лечения синдрома приобретённого иммунодефицита (FightAIDS@Home — Phase 1), проект по созданию полной карты белков человеческого организма (Human Proteome Folding — Phase 2), проект по улучшению терапии рака на раннем этапе диагностики (Help Defeat Cancer), проект по расшифровке информации геномов разных организмов (Genome Comparison), проект по поиску лекарств и вакцин от тропической лихорадки (Discovering Dengue Drugs — Together — Phase 1) и др.
Стоит отметить, что в случаях, когда осуществляется географически распределенный сбор данных для последующей их обработки в распределенной системе, то возникают ограничения, связанные с передачей этих данных по каналам связи. Это, в свою очередь, имеет непосредственное влияние на скорость отклика системы, которая является одной из важнейших характеристик распределенных систем.
1.2 Технология облачных вычислений
Развитием грид-технологий привело к зарождению технологии «облачных» вычислений (от англ. cloud computing). Появление облачной концепции относят к началу 1950-х гг. и связано с появлением первых мейнфреймов, которые предоставляли одновременный доступ нескольких пользователей к центральному компьютеру. В 1960-х свое развитие получила концепция Дж. К. Р. Ликлайдера «межгалактической компьютерной сети», основные идеи которой сходны с «облачной» концепцией [49].
Облачные вычисления - это модель, позволяющая легко осуществлять сетевой доступ по требованию к единому пулу настраиваемых вычислительных ресурсов (например, сетей, серверов, систем хранения данных, приложений и услуг), которые быстро выделяются для использования и затем также быстро высвобождаются [50].
Облачные вычисления начали активно развиваться и внедряться в различные отрасли науки и техники 2007 году. Это связано, прежде всего, с активным развитием каналов связи и потребностью пользователей к масштабированию автоматизированных систем [51]. Основные элементы облачной концепции показаны на Рисунке 4.
Internet
>
Рисунок 4 - Концепция облачных вычислений
На базе облачных вычислений функционирует великое множество различных приложений. Это почтовые сервисы, такие как Gmail, Yahoomil, Webmil, Hotmail [52, 53], онлайновые текстовые редакторы - Zoho Writer, Документы Google [54, 55], онлайновые сервисы по работе с графикой - Lunapic, Google Picasa [56]. В настоящее время облачная концепция предлагает разнообразные модели услуг, включая модель «платформа как услуга», модель «программное обеспечение как услуга», модель «инфраструктура как услуга», модель «данные как улсуга» и др. [57]:
Стоит также отметить появление и развитие в России с 2018г. мультиоблачной концепции, которая предполагает наличие распределенной облачной структуры на базе так называемых гиперскейлеров - облачных провайдеров масштаба Google, Amazon или Azure [58].
Ключевые преимущества использования облачных технологий для пользователя отражены на Рисунке 5.
«— Высокая технологичность
Доступность > к
Технологии облачных вычислений
Мобильность
1
Экономичность
Гибкость
Арендность
Рисунок 5 - Преимущества технологии облачных вычислений для пользователя
Ниже по тексту даны пояснения к Рисунку 5. Здесь, под доступностью понимается возможность получения доступа к информации при наличии любого устройства, имеющего подключение к сети Интернет. При использовании облачных технологий, возрастает мобильность лиц, участвующих в разработке какого-либо проекта, поскольку отпадает необходимость привязанности к конкретному рабочему месту. Экономическая эффективность использования
данной технологии связана с отсутствием необходимости дорогостоящего обслуживания аппаратной инфраструктуры, а также приобретением лицензий на используемое программное обеспечение. Использование облачных технологий позволяет резервировать облачные ЦОД в соответствии с требуемой нагрузкой, что повышает эффективность использования вычислительных ресурсов. При этом все требуемые ресурсы выделяются провайдером автоматически, что позволяет говорить о гибкости, свойственной использованию технологии облачных вычислений. Облачные ЦОД обладают огромной вычислительной мощностью, которую пользователь может использовать для решения задач, связанных с хранением, анализом и обработкой данных.
Перечисленные выше особенности позволяют говорить о широкой области применимости технологии облачных вычислений. Одной из них является область систем автоматизированного проектирования (САПР).
1.2.1 РСАПР на базе технологий облачных вычислений
В процессе проектирования элементной базы ЭВА и РЭА разработчики сталкиваются с необходимостью решения задач высокой сложности, что невозможно без использования автоматизированных систем. Перспективным направлением развития САПР в области решения оптимизационных задач видится переход к распределенным процессам проектирования, построенным на базе Интернет-технологий. Интеграция облачных вычислений с САПР - одно из ключевых направлений развития в данной области. Это явилось следствием перехода к методике «сквозного» проектирования в САПР. Основная задача методики «сквозного проектирования» в САПР состоит в сокращении времени отклика автоматизированной системы и повышении оперативности
взаимодействия коллектива разработчиков. Задачи информационного обмена и интеграция автономных приложений осуществляется с использованием Интернет-технологий.
Анализ работ, находящихся в открытом доступе, продемонстрировал заинтересованность научного сообщества в проблеме интеграции САПР и Интерент-технологий. В работе [59] предложен пример реализация топологической САПР печатных плат «TopoR» в рамках развертывания корпоративного облака на основе технологий БД. В работе [60] предложен перспективный вариант построения корпоративного облака для схемотехнической САПР изделий электронной и вычислительной техники. В данном случае автор также использовал технологию БД с использованием модели сервиса данных как услуга.
На сегодняшний день существуют примеры реализованных САПР, функционирующих в облаках [61]. Компании АСКОН и Cloud IT предложили пользователям систему САПР КОМПАС-BD по облачной модели Software as a Service, SaaS [62]. В 2010 году компания Dassault Systemes разработала САПР нового поколения Solidworks, работающий из «облака» на компьютере. «Облачный» проект компании ieDezine, позволяющий производить обработку данных в «облаке», предполагает возможность аренды средств CAE-анализа и их запуска на высокопроизводительном ЦОДе [63]. Компания Autodesk также ведет разработки, связанные с «облачным» развертыванием своих продуктов, среди которых Project Butterfly, Project Neon, Inventor Optimization, Project Twitch. Инструмент компании Autode Fusion 360 позволяет объединить все этапы проектирования на основе «облачных» технологий [64]. Результатом совместной работы компаний Huawei и Siemens в 2018 году является продукт Manufacturing Cloud Desktop [65].
Мировые лидеры в области разработки систем проектирования электронных устройств также предлагают ряд решений по реализации САПР в облаках. Например, компания Synopsys выпустила линейку продуктов, поддерживающие
облачные вычисления. ZeBu Cloud является частью Vérification Continuum Platform, размещенный на виртуальном узле программный комплекс эмуляции, обеспечивающий эмуляцию программного обеспечения, проверку производительности, анализ мощности и валидацию системы для систем на кристалле и сложных функциональных блоков. В данном случае облака обеспечивают очень высокую производительность эмуляции в условиях промышленности. Cloud-Ready IC Validator Solution for Advanced DRC Nodes -продукт, целью которого является валидация передовых проектных норм ИС. Данный продукт позволяет получить результаты проверки проектных норм даже для очень больших объектов проектирования в течение нескольких часов [66].
Компания Cadence также ведет разработки в направлении повышения производительности САПР и считает весьма перспективным использование мощности облака в развитии САПР электроники. OrCAD Capture Cloud - одно из решений компании Cadence. Данное приложение позволяет использовать возможности схемного редактора OrCAD Capture для создания и оформления электрических схем посредством web-браузера. Компания предлагает ряд продуктов, реализованных в облаках: Cadence Liberate Characterization Solution (описание характеристик библиотеки), Xcelium Parallel Logic Simulation (цифровое моделирование), Pegasus Verification System (топологическая верификация), которые способны масштабироваться до тысяч серверов. Уникальные системы, такие как Palladium Cloud и OrCAD Entrepreneur расширяют мощности аппаратного ускорения и оцифровки процесса проектирования в реальном времени [67].
Специалисты компании Mentor полагают, что объединение облака с устройством - это ключевой механизм реализации Интернета Вещей. Разработка компании Mentor - продукт SystemVision Cloud, который позволяет разрабатывать и моделировать сложные аналоговые, цифровые, цифро-аналоговые и электро-механические системы, а также просматривать результат в режиме реального времени [68-69].
Однако наряду с очевидными преимуществами облачной и мультиоблачной концепций, как отмечают специалисты, существует ряд ограничений их применения в области распределенных САПР [70, 71]:
- задержки в сети при передаче данных, связанные с территориальным расположением облака и краевого устройства (например, при моделировании);
- задержки, связанные с обработкой данных в связи с большой вычислительной нагрузкой на облачный сервер (например, обработка графики, расчет схем высокой степени интеграции).
Более того, специфика функционирования РСАПР заключается, в том числе, в неравномерности потребления вычислительных ресурсов. Это связано с тем, что комплексные функциональные задачи РСАПР имеют различную вычислительную сложность на различных этапах проектирования и выполняются коллективом разработчиков параллельно, что приводит к возможности возникновения пиковой нагрузки в сети, что, в свою очередь, может привести к следующему:
- невозможность получения приемлемого по качеству проектного решения на имеющихся мощностях за отведенное время;
- получение приемлемого по качеству проектного решения на имеющихся мощностях за отведенное время, но невозможность его улучшения, что противоречит главному принципу эффективного функционирования РСАПР.
Данные исследований показали, что при традиционном подходе к созданию ИТ-инфраструктуры, во избежание описанных ситуаций, заказчик обычно приобретает под будущие нагрузки дополнительно в среднем 59% вычислительных мощностей и 48% емкостей систем хранения данных.
С другой стороны, из-за внезапных и непредвиденных пиковых нагрузок 57% компаний периодически испытывают трудности из-за недостатка вычислительных мощностей, а половина опрошенных имела опыт остановки ИТ-систем, не справляющихся с нагрузками [72].
Перечисленные проблемы могут быть решены за счет привлечения дополнительных вычислительных мощностей, в том числе за счет резервирования облачных дата центров. Примером такого решения является облачная модель HPE GreenLake, предложенная американской компанией Hewlett Packard Enterprise. Главной особенностью данной модели является возможность при необходимости разместить часть сервисов HPE GreenLake и соответствующих аппаратных решений на внешней локации: в публичном или частном облаке, во внешнем ЦОДе или на оборудовании, физически расположенном на территории заказчика. Данная модель, с одной стороны, позволяет компаниям не переплачивать за оборудование, зачастую приобретаемое «с запасом». И, с другой стороны, дает возможность не беспокоиться о нехватке вычислительных ресурсов для повседневной деятельности. [73].
Стоит также отметить, что на сегодняшний день существует ряд работ, демонстрирующих методы решения задач распределения вычислительной нагрузки и получения дополнительных мощностей в распределенных системах за счет использования устройств туманного слоя [74-76].
1.3 Технология туманных вычислений в распределенных системах и проблемы организации вычислительного процесса
В настоящее время новая парадигма туманных вычислений, которую можно рассматривать как расширение облачной концепции, нашла широкое применение во многих областях. Это связано с тем, что на сегодняшний день облака не отвечают высоким требованиям мобильности, низкой латентности и локальной осведомленности [77]. Перспективным решением в данном случае видится выборочное смещение вычислений, связи, управления и принятия решений к
местам, где генерируются данные, что соответствует основным принципам концепции туманных вычислений [78].
Концепция туманных вычислений является эволюционным этапом развития облачной концепции и в настоящее время занимает лидирующую позицию среди общих тенденций развития информационных технологий. Появление данной концепции тесно связано с зарождением и развитием концепции «Интернета вещей» [79]. Сценарии использования концепции туманных вычислений весьма разнообразны и обуславливаются развитием смежных технологий. Данная концепция успешно используется в создании систем типа «умный» дом, «умный транспорт», электронное здравоохранение, электронное правительство, торговля и финансовые услуги, промышленное производство, управление технологическими и бизнес процессами и многое другое [80, 81].
Термин «туманные вычисления» впервые введен компанией Cisco в 2011г. [78] году и в настоящий момент активно развивается благодаря следующим факторам:
- вычислительные мощности коммуникационного оборудования и устройств, размещаемых в туманном слое, позволяют производить дополнительные вычисления;
- количество конечных устройств растет очень быстро, и эта тенденция сохранится в обозримой перспективе.
- целесообразно разгрузить ЦОД (в том числе облачные) от выполнения сложных вычислительных процессов [82].
Туманные вычисления - это многоуровневая модель, обеспечивающая повсеместный доступ к общей совокупности масштабируемых вычислительных ресурсов. Туманные вычисления минимизируют время сетевого отклика поддерживаемых приложений а также обеспечивают конечные устройства локальными вычислительными ресурсами и, при необходимости, сетевым подключением к централизованным сервисам» [83]. Архитектуру туманных
вычислений можно рассматривать как «прослойку» между облаком и конечными (пользовательскими) устройствами (Рисунок 6).
Пользовательские устройства
Рисунок 6 - Концепция туманных вычислений
Среда туманных вычислений состоит из таких компонентов сети, как роутеры, коммутационные устройства, телевизионные преобразователи, прокси-серверы, базовые станций, датчики и т.д.
Ключевое отличие туманной концепции от облачной заключается в возможности динамического переноса вычислительной нагрузки из облака на периферию сетевой инфраструктуры с задействованием устройств туманного слоя, а так же частичное размещение нагрузки в туманном слое. Это позволяет существенно снизить нагрузку на коммуникационную инфраструктуру сети [84].
Основные проблемы, связанные с организацией концепции «Интернета вещей», и применения технологии туманных вычислений для их решения отражены на Рисунке 7.
Большая географическая распределенность систем и клиентов
Непредвиденные сетевые заторы
Высокая стоимость полосы
пропускания
Мобильность оконечных устройств
Рисунок 7 - Перспективы использования технологии туманных вычислений для решения проблем, связанных с организацией «Интернета вещей»
Крупные облачные провайдеры: Amazon, Google и Microsoft ведут разработки по внедрению концепции туманных вычислений на базе «безсерверной архитектуры» (serverless architecture). Компания Amazon предлагает платформу туманных вычислений AWS IoT Greengrass, которая эффективно расширяет возможности облачной инфраструктуры на устройства туманного слоя, это позволяет обрабатывать данные локально, используя при этом облако для управления, анализа и хранения данных. Такая платформа позволяет программными средствами фильтровать данные устройств и передавать обратно в облако только необходимую информацию [85].
Компания Microsoft предложила решение для бессерверных вычислений -Azure Functions, которое позволяет запускать небольшие фрагменты
программного кода, или функций, в облаке. Функции Azure обеспечивают обработку данных, интеграцию систем, работу с Интернетом вещей (IoT) и построение простых API-интерфейсов [5].
Google представила платформу для Интернета вещей Android Things с поддержкой микрокомпьютеров Intel Edison и Joule™ 570x, NXP Pico i.MX6UL и Argon i.MX6UL, а также Raspberry Pi 3 [86].
Российская компания SONM разработала многоцелевую децентрализованную платформу для реализации сложных вычислительных задач, базирующуюся на технологиях блокчейна и туманных вычислений [6].
На сегодняшний день представлено большое разнообразие туманных платформ, в том числе частных (Cisco IO, Nebbiolo Technologies, ClearBlade, Smartiply Fog, LoopEdge), публичных (Azure IoT, Amazon AWS IoT Greengrass, Google, Yandex и Mail.ru) и платформ с открытым исполнительным кодом (FogFrame2.0, FogFlow, FogBus) [87].
Ключевая особенность технологий туманных вычислений, которая заключается в выполнении большей части обработки данных на «краю» сети, позволяет их использовать в широкой номенклатуре распределенных систем, в том числе системах мониторинга и управления, где время отклика системы является одной из основополагающих характеристик.
Системы мониторинга и прогнозирования. В последние десятилетия необходимость учета сведений о состоянии окружающей среды значительно возросла. Прежде всего, это связано с повышением требований к обеспечению экологической безопасности, что, в свою очередь является залогом устойчивого развития общества. Интенсивное воздействие антропогенных факторов на окружающую среду может вызывать различные последствия, выражающиеся, в том числе, в негативных природных явлениях, которые представляют опасность для населения и различных объектов инфраструктуры. В связи с этим, актуальным является использование систем мониторинга (СМ), обеспечивающих своевременный сбор данных с целью оповещения населения о предполагаемом
наступлении опасных событий [88]. Все многообразие существующих в настоящее время систем мониторинга может быть разделено на системы, которые не осуществляют обработку данных, и на системы, которые способны производить предварительную обработку данных, тем самым повышая функциональность системы [89]. В настоящее время перспективным направлением создания систем мониторинга является реализация такого класса систем на базе технологий «цифровой экономики».
Например, в работе [90] рассмотрена проблема разработки СМ и прогнозирования опасных природных явлений, обеспечивающая обработку больших объемов неструктурированных данных, генерируемых гетерогенными устройствами. Предложено использовать технологию туманных вычислений для размещения некоторых вычислительных задач на узлах сетевого оборудования и мобильных устройств организаций и частных лиц, которые задействованы в проведении мониторинга. Данная технология позволяет снизить нагрузку на коммуникационную сеть и частично разгрузить ЦОДы, что, в свою очередь, предполагает повышение надежности системы и снижает латентность системы.
Появление технологий Интернета вещей и развитие на их основе «умных» городов, территорий, предприятий и домов также способствует активному внедрению систем мониторинга в их инфраструктуру. В работах [91, 92] авторами предложен иерархическая распределенная архитектура туманных вычислений для поддержания интеграции большого числа компонентов инфраструктуры и сервисов в «умных» городах. В качестве примера, демонстрирующего эффективность предлагаемой архитектуры, был реализован прототип системы интеллектуального мониторинга трубопроводов в «умных» городах. На основании полученных результатов, можно сделать вывод о перспективности использования туманных технологий в инфраструктуре «умных» городов, позволяющих значительно повысить их «интеллектуальность».
В работе [93] предложена архитектура интеллектуального распределения воды и мониторинга состояния подземных трубопроводов с поддержкой
Интернета вещей для «умных» городов. Ключевым компонентом разработанной архитектуры является интеграция технологий Интернета вещей и туманной и облачной концепции, позволяющими эффективно решать проблемы, связанные с автоматизированным распределением воды, а также осуществлять мониторинг утечек трубопроводов.
Системы мониторинга активно используются в сфере сельского хозяйства. Например, в работе [94] предложен подход к анализу и обработке данных для распределенного мониторинга сельскохозяйственных культур и почвы, в котором компоненты, реализующие иерархический сбор и моделирование данных, позволяет избежать проблем, связанных с ограничением пропускной способности сети, и сократить энергию, необходимую для передачи данных. Здесь основное внимание уделяется применению технологии туманных вычислений, позволяющих использовать вычислительные ресурсы локальных узлов для дальнейшей передачи частично обработанных данных более высоким уровням системы для принятия решений.
В работе [95] предложена модель распределенной библиотеки системы мониторинга и диагностики для различных областей деятельности (Рисунок 8).
РАСПРЕДЕЛЕННАЯ БИБЛИОТЕКА
Раздел распределенной библиотеки 1. Данные о параметрах системы в отношении которой осуществляется мониторинг и прогнозирование.
Раздел распределенной библиотеки 2. Служебные данные, необходимые для диспетчирования системы, реализации распределённого реестра, прочие данные
Раздел распределенной библиотеки 3. Данные о результатах когнитивного моделирования, прогнозов, расчетов, заключений экспертов
Раздел распределенной библиотеки 4. Данные сторонних систем (например, подсистема анализа социальной активности пользователей и т.д.)
Рн Н
и н н
Рн
«
м м
н
ч ^
Рн
в
и £
От
ВУ ПОЛЬЗОВАТЕЛЕЙ
Локальный диспетчер
Сервисное приложение для записи/чтения данных
Функциональное приложение для подсистемы сбора, хранения и первичной обработки данных
Функциональное приложение для подсистемы поддержки принятия решений
ВУ ЭКСПЕРТОВ 1...К
Локальный диспетчер
Сервисное приложение для записи/чтения данных
Функциональное приложение для подсистемы сбора, хранения и первичной обработки данных
Функциональное приложение для подсистемы поддержки принятия решений
ВУ СЕРВЕРОВ 1...М
Локальный диспетчер
Сервисное приложение для записи/чтения данных
Функциональное приложение для подсистемы сбора, хранения и первичной обработки данных
Функциональное приложение для подсистемы поддержки принятия решений
Рисунок 8 - Распределенная библиотека системы мониторинга и диагностики для
различных областей деятельности
Как видно из Рисунка 8 в распределенную библиотеку поступают данные от подсистемы сбора данных, их описание, результаты их обработки, после чего они доступны для пользователей и экспертов. При необходимости предоставленные подсистемой сервисы могут быть выполнены на облачном или туманном вычислительном слое. Подсистема поддержки принятия решений также имеет доступ к распределенному реестру, а, значит, и к полученным данным от подсистемы сбора. От данной подсистемы в распределенную библиотеку могут попадать данные о результатах когнитивного моделирования, заключение
Похожие диссертационные работы по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», 05.13.11 шифр ВАК
Методы и алгоритмы решения задач оптимизации ресурсов в нестационарных распределенных гетерогенных вычислительных средах2021 год, доктор наук Черных Андрей Николаевич
Анализ и оценка факторов, влияющих на скорость параллельной обработки информации в ГРИД-системах2014 год, кандидат наук Дробнов, Сергей Евгеньевич
Средства кластеризации распределенных данных на основе нейронных сетей Кохонена2020 год, кандидат наук Рукавицын Андрей Николаевич
Исследование и разработка моделей и методов построения инфраструктуры сетей автономного транспорта с использованием технологий Искусственного Интеллекта2023 год, кандидат наук Аль-Свейти Малик
Методы и средства моделирования распределенных систем хранения и обработки данных на основе результатов их мониторинга2021 год, кандидат наук Нечаевский Андрей Васильевич
Список литературы диссертационного исследования кандидат наук Сафроненкова Ирина Борисовна, 2022 год
использования
ресурсов и
минимизации
латентности
Оптимизированный алгоритм планирования задач для минимизации задержек в критически важных приложениях
Б. Джамиль, М. Шоджафар, И. Ахмед, А. Улла, К. Мунир, Х. Иджаз
Имеет ограничение на размеры передаваемых данных
Далее по тексту подробно будет рассмотрен метод на основе локальных групп устройств (ЛГУ), поскольку он учитывает большую часть характеристик, присущих туманной среде.
Формальная постановка задачи. В работе [24] приведена следующая постановка задачи переноса вычислительной нагрузки (ЗПВН) с учетом наличия транзитных участков сети, что свойственно туманным средам. Авторами предложена математическая модель задачи переноса нагрузки из облака на узлы туманного слоя.
Пусть дан граф вычислительной задачи О, с некоторой вычислительной сложностью подзадачи х и объемом информации wi, передаваемой между подзадачами. Граф О разделен на два подграфа О' и О". Необходимо разместить подграф О' на вычислительные устройства (ВУ) сегмента сети Р' туманного слоя, в то время, как вычислительные задачи подграфа О" продолжает исполняться на сегменте сети Р" (Рисунок 19).
Соответственно, такой перенос вычислительных подзадач предполагает решение оптимизационной задачи с определенными критериями и ограничениями, которые частично формируются требованиями самой вычислительной системы. Основным критерием при решении ЗПВН является надежность системы.
Рассмотрим графовое описание набора задач О = {< х, ж >}, где / -уникальный идентификатор вычислительной подзадачи, х - вычислительная
сложность /-ой подзадачи, wi - объем информации, передаваемый i-ой подзадачей в коммуникационную среду.
Вычислительные подзадачи графа G связаны с узлами вычислительных устройств из множества P. Причем P описывается графой структурой P = {< j, pj > list}, где j - идентификатор узла, p— производительность узла, list -
матрица пропускной способности каналов связи между инцидентными узлами сети.
Теперь рассмотрим подграф вычислительных подзадач G', которые требуется перенести в то время, как вычислительные подзадачи подграфа G" продолжают свое исполнение. Между данными подграфами существует несколько информационных потоков. Потоки, связанные с подграфом G' могут быть описаны набором кортежей:
Flow _ in = {< idout, idin, wout in >} - кортеж, описывающий количество
информации, передаваемой между узлом G "idout и узлом G' idin от G" к G'.
Flow _ out = {< idn, idout, win out >} - кортеж, описывающий количество
информации, передаваемой между узлом G' idout и узлом G'' idin от G' к G".
Рассмотрим задачу размещения нагрузки. Пусть имеется подграф вычислительных задач G", связанный с P" , и Flow in, Flow out. Необходимо разместить вычислительные подзадачи подграфа G' на множестве устройств сети P' таким образом, что общее время выполнения вычислительных подзадач G меньше заданного времени T с учетом выполнения критерия надежности системы.
Решением поставленной задачи является установление связи между вычислительными подзадачами G' и вычислительными узлами P', которое может быть описано матрицей A:
A =
< t1}, u >
< tN
u
NM
>
(7)
где to'J - момент времени, когда начинается вычисление i-ой подзадачи j-м узлом,
ujj - доля общей производительности pj заданного j-го узла для выполнения i-ой подзадачи.
Данная модель задачи позволяет связать более одной задачи, приходящей на один узел одновременно, таким образом, улучшая классическую модель формирования расписания [119].
Для дальнейшей разработки модели необходимо рассмотреть следующие параметры:
- L (A) - загрузка узла, порождаемая переносом вычислительной подзадачи на узел;
- Ldist( A, Flow_ in, Flow _ out) - загрузка узла, порождаемая обменом информации между подграфами G'u G'';
- Ltr (A, Flow _ in, Flow_ out) - загрузка узла, порождаемая передачей информации через узел;
- D - список ребер графа P, который определяет маршрут между узлами l и k;
- ListDlk - матрица, описывающая пропускную способность каналов связи между узлами l и k.
Рассмотрим целевую функцию как набор значений функций надежности определенных узлов F
F = е , (8)
где - интенсивность отказов j-го узла, t - время функционирования устройства. Поскольку
Л = 2AT/10, (9)
AT = kL (10)
где L- загрузка устройства,
к - коэффициент, который зависит от типа устройства.
Тогда зависимость между функцией надежности и загрузкой описывается следующей формулой:
Л ->kL/10
F = e J0 (11).
Загрузка устройства зависит от распределения вычислительных задач по ВУ, которые описываются матрицей A. Рассмотренные выше параметры должны быть включены в модель задачи: Lp (A), L&i(A, Flow _ in, Flow _ out) Ltr (A, Flow _ in, Flow _ out)
Таким образом, полная загрузка j-го ВУ описывается следующей формулой: Lj = Lpj (A) + Ldisj (A, Flow _ in, Flow _ out) + Ltj (A) (12).
В случае набора устройств, скалярная целевая функция переходит в векторную.
Главным ограничением для этой задачи является время исполнения T графа вычислительной задачи G, т.е. для:
x
G = G'uG", Vi g G : —^ + tdist (i) < T (13)
PjuJJ
где ^(0 - максимальное время доставки информации от 1-ой подзадачи к подзадаче-получателю данных.
Поскольку модель рассматривает маршруты потока информации, ^(0 описывается функцией:
^ (0 = #( А, G, Р) (14).
Более точно время доставки информации может быть вычислено на основе полной информации о подзадачах, назначаемых на вычислительные узлы с учетом параметров Ц и ListD¡k [24].
Решение ЗПВН в туманной среде с использованием локальных групп устройств. В методе решения ЗПВН, предложенном в работе [120] авторы используют математическую модель постановки задачи, описанную в [24].
Данный метод заключается в формировании ограничений на множество вычислительных устройств в режиме реального времени с использованием «локальной группы устройств».
Под термином «локальная группа устройств» (ЛГУ) понимается множество устройств, которые:
- взаимосвязаны между собой высокоскоростными каналами связи без транзиторных узлов;
- решают подзадачи общей вычислительной задачи G;
- граничные устройства, входящие в состав одной ЛГУ, могут одновременно принадлежать соседним ЛГУ.
Постановка задачи. Пусть дан граф вычислительной задачи G, разделенный на два подграфа G' и G''. Согласно сформулированной выше задачи, необходимо разместить подграф G' на вычислительных устройствах туманного слоя - P', в то время, как вычислительные задачи подграфа G'' продолжают исполняться на вычислительных узлах облачного слоя - P'' (Рисунок 20).
р"
Рисунок 20 - Схема переноса части вычислительной нагрузки
Метод, основанный на формировании ЛГУ состоит из выполнения следующих шагов:
Шаг 1. Поскольку подграф вычислительных задач G' необходимо перенести в «туманный» слой, в «облачном» слое должен быть узел, отвечающий за перенос
нагрузки. Выбор узла-лидера проводится среди узлов, выполняющих общую вычислительную задачу. Например, это может быть алгоритм избрания лидера на деревьях, фазовый алгоритм, алгоритм Финна [121].
Шаг 2. Выбранный узел-лидер опрашивает свою ЛГУ об имеющихся ресурсах для размещения дополнительной нагрузки (Рисунок 21).
Рисунок 21 - Выбранный лидер рассылает запросы в пределах ЛГУ
Шаг 3. Если получен положительный ответ, то данное множество узлов фиксируется (и устанавливаются границы поискового пространства). Затем узел-лидер моделирует размещение вычислительных подзадач по выбранным узлам, решая таким образом оптимизационную задачу размещения нагрузки.
Шаг 4. Если получен отрицательный ответ (в случае, если в рассматриваемой ЛГУ нет узлов с достаточными для размещения ресурсами), затем ЛГУ расширяется следующим образом: каждый узел ЛГУ перенаправляет запрос от «начального» узла далее по своей ЛГУ (Рисунок 22). Данная процедура итерационная и повторяется до тех пор, пока узлы с необходимыми ресурсами не найдены.
Рисунок 22 - Процедура распространения запросов в пределах ЛГУ
Шаг 5. Если задача размещения нагрузки решена, и результат удовлетворяет всем ограничениям задачи, вычислительная подзадача связывается с фиксированным множеством узлов. Если приемлемое решение не получено, процедура повторяется, начиная с п.4 (расширение ЛГУ). Схема данного метода представлена на Рисунке 23.
Решение подзадачи
НЕТ ДА
Решение удовлетворяет?
Подзадачи связываются с множеством ВУ
I
Конец
Рисунок 23 - Схема метода решения ЗПВН с использованием ЛГУ Для временной оценки данного метода, рассмотрим следующие параметры:
N- количество узлов, на котором изначально выполняется вычислительная задача;
N - количество задач, подлежащих к размещению;
- размер ЛГУ для /-го запроса;
- общее количество итераций;
Б - количество итераций, необходимое для формирования ЛГУ с возможностью решить задачу.
Итак, грубая временная оценка метода, основанного на формировании ЛГУ имеет вид:
ь , (15)
где а - коэффициент, связывающий время выбора узла-лидера и количество узлов;
V - коэффициент, связывающий время обработки запросов и количество узлов, которые должны быть опрошены;
у - коэффициент, связывающий размер ЗПВН и время ее выполнения.
Если рассматривать метод на основе ЛГУ применительно к решению ЗПВН в РСАПР, то он является универсальным, поскольку не зависит от структур параллельных алгоритмов, используемых для решения задач проектирования. Однако стоит отметить также следующее. Узел, производящий попытки распределения нагрузки, в начальный момент времени не располагает никакими сведениями о состоянии ресурсов узлов, принадлежащих локальной группе. Таким образом, поиск вариантов размещения производится «вслепую» и сводится к методу проб и ошибок. Таким образом, итерационный характер метода на основе ЛГУ обуславливает невозможность предсказать время завершения его работы. «Худший» вариант работы метода на основе ЛГУ заключается в том, что узлу-лидеру придется опросить все узлы-кандидаты, расположенные в туманном слое. Это, во-первых, едва ли реализуемо, а во-вторых, займет неопределенное время.
Тьоо =оМ +
Ё+
1=\
Как было отмечено выше, временные издержки, связанные, в данном случае, с решением задачи реконфигурации системы, оказывают негативное влияние на эффективность функционирования распределенной системы. Этот эффект усиливается тем фактом, что в туманной среде, которая является динамичной и нестабильной, задача реконфигурации может решаться многократно. В случае метода ЛГУ, поиск варианта размещения может занять неопределённое время, что, в конечном итоге отрицательно отразится на эффективности функционирования системы.
Следовательно, для достижения цели, которая заключается в минимизации времени решения ЗПВН, необходимо решить следующие задачи:
Во-первых, для переноса вычислительной нагрузки необходимо располагать информацией о множестве доступных вычислительных узлов.
Во-вторых, весьма желательно, чтобы это множество не было избыточным, поскольку в условиях перебора вариантов решений увеличение пространства поиска ведет либо к ухудшению качества решения, либо к увеличению времени его получения [122].
Таким образом, актуализируется проблема, связанная с разработкой методов и алгоритмов решения ЗПВН в распределенных системах, реализованных на базе концепции туманных вычислений.
2.2.3 Анализ применения онтологий для решения оптимизационных задач в
распределенных системах
На формальном уровне, онтологию можно рассматривать как систему, состоящую из набора понятий и набора утверждений об этих понятиях, на основе которых можно строить классы, объекты, отношения, функции и теории [123].
Под формальной моделью онтологии О будем понимать:
О = < С, Р, Я, А >,
где С — конечное множество понятий (классов сущностей) предметной области; P — конечное множество свойств этих понятий (классов); R — конечное множество связей между понятиями (классами); А — множество аксиом, утверждений, построенных из этих понятий, их свойств и связей между ними.
Таким образом, структура онтологии содержит следующие элементы: концепты (понятия, классы), атрибуты, отношения, аксиомы, экземпляры.
Под классом подразумевается любая сущность, о которой может быть дана какая-либо информация. Экземпляры представляют собой единичные сущности, принадлежащие классам онтологии. Единицы онтологии (классы и экземпляры) могут иметь свойства - атрибуты. Атрибут описывает внутренние свойства объектов посредством конкретных значений. Каждый атрибут обычно имеет имя и значение, и используется для хранения информации, которая специфична для данной единицы. Отношения представляют тип взаимодействия между понятиями области и формально определяются как подмножество произведения п множеств: Я: С1 х С2...Х Сп. Отношение категоризации является самым распространенным типом отношений, использующимся во всех онтологиях. В различных исследований можно встретить ряд других названий данного типа отношений: таксономическое отношение; отношение ^-А; класс - подкласс; гипоним -гипероним; родовидовое отношение; отношение Аксиомы (правила
вывода) используются, чтобы записать высказывания, которые всегда истинны. Они могут быть включены в онтологию для разных целей, например, для определения комплексных ограничений на значения атрибутов, аргументы отношений, для проверки корректности информации, описанной в онтологии, или для вывода новой информации. Аксиомы позволяют выразить ту информацию, которая не может быть отражена в онтологии посредством построения иерархии понятий и установки различных отношений между понятиями [124-126].
Анализ современных источников показал, что области применения онтологий весьма разнообразны [127-133]. В настоящее время одной из наиболее перспективных областей применения онтологий является проектирование и моделирование, включая решение оптимизационных задач.
Например, в работе [127] предлагается использовать онтологии для формального описания системы биллинга. При этом использование онтологического подхода позволяет упростить компьютерную обработку данных, сократить время вычислений и поиска а также предоставляет возможность логического вывода.
В работе [128] рассмотрена проблема проектирования САПР технологического процесса (САПР ТП) с использованием онтологий. Применение онтологического подхода при описании предметной области позволяет достичь системности и связности между понятиями, а также позволяет наглядно изобразить и объяснить структуру взаимосвязей между понятиями, описывающими деталь с точки зрения ее изготовления. Описана перспективность использования онтологического подхода для разработки новых правил проектирования и создания САПР ТП с развивающейся базой знаний.
В работе [129] рассмотрены вопросы, связанные с интеллектуализацией процесса формирования описания проектируемого изделия как составляющего проектно-конструкторской документации в области проектирования новых моделей одежды. Предполагается, что использование онтологического подхода позволяет повысить качество инженерных решений.
В работе [130] авторами использован онтологический подход к процессу подготовки и принятия решений по реализации промышленных инвестиционных проектов. Онтологические модели обеспечивают возможность выбора более качественного решения в соответствии с заданным критерием оптимальности.
В работе [131] представлен подход к автоматизации управления сложными системами в проблемных ситуациях на основе разработки интеллектуальной информационной системы поддержки принятия решений (ИСППР), что
представляет собой решение оптимизационной задачи, поскольку время формирования рекомендации ИСППР должно находиться в пределах резервного времени для данного типа систем и для соответствующей проблемной области.
В работе [132] предложено использовать средства онтологической поддержки для повышения эффективности проектного мышления. Цель комплекса средств онтологической поддержки заключается в поиске проектных ошибок, их исправление и предотвращение в режиме реального времени.
В работе [133] предложено использовать онтологические модели для решения задач управления группой интеллектуальных подвижных объектов (малоразмерных космических аппаратов) на примере решения задач дистанционного зондирования Земли. Авторы используют идею онтологического описания объектов наблюдения и правил распознавания цели, метод поиска объекта, который соответствует своему онтологическому описанию.
Таким образом, можно говорить о значительном опыте использования онтологий в решении оптимизационных задач, возникающих в системах, основанных на знаниях, в том числе:
- поддержка принятия решений при проектировании сложных автоматизированных систем и процессов;
- управление процессами;
- моделирование и оценка ситуаций;
- логический вывод.
В настоящем диссертационном исследовании предлагается использовать онтологические модели в области создания распределенных систем с точки зрения организации вычислительного процесса.
1. Проведен анализ и показана целесообразность использования параллельных популяционных алгоритмов для решения оптимизационных задач. Данный класс алгоритмов рассмотрен в качестве примера и не ограничивает области применения разрабатываемых в данной диссертации методов, которые могут быть применены к любым классам алгоритмов, обладающих свойством распараллеливания.
2. Описаны модели распараллеливания популяционных алгоритмов и предложены способы их разбиения с точки зрения рационального распределения вычислительной нагрузки в процессе функционирования распределенной системы.
3. Проведен анализ моделей и методов решения задачи переноса вычислительной нагрузки в распределенных системах. Выявлено, что большинство известных моделей и методов не учитывают наличие транзиторных участков, что ввиду большой географической распределенности систем, функционирующих в туманной среде, является важным фактором, ограничивающим их использование.
4. Рассмотрены модель и метод решения задачи реконфигурации в РИУС с использованием локальных групп устройств. Показано, что недостатком данного метода является его итеративность, а ввиду большого количества узлов -кандидатов, распложенных в туманной среде, процедура решения задачи переноса вычислительной нагрузки может занять неопределенное время, что, соответственно, негативно скажется на эффективности функционирования системы. На данном основании сделан вывод о необходимости ограничения множества узлов-кандидатов для переноса вычислительной нагрузки в распределенной системе.
5. Проведен анализ и показана эффективность использования онтологических моделей для решения оптимизационных задач. Предложено использовать модели онтологии в области создания распределенных систем с точки зрения организации вычислительного процесса.
3.1 Метод формирования ограничений в задаче переноса вычислительной
нагрузки в распределенной системе
Эффективность функционирования распределенной системы зависит от многих факторов, среди которых используемые методы поисковой оптимизации, методы распараллеливания алгоритмов, а также способы размещения фрагментов программ, реализующих эти алгоритмы, относительно друг друга, характеристики вычислительных устройств и др. [134, 135].
Если рассматривать понятие эффективности как способность системы выполнять свою функцию по назначению, то сокращение временных издержек на организацию решения вычислительной задачи можно рассматривать как способ повышения эффективности функционирования системы. Следовательно, для повышения эффективности функционирования распределенной системы необходимо сократить время решения ЗПВН.
Существующий метод к решению ЗПВН в РИУС, рассмотренный в п.п. 2.2.2 настоящего исследования, направлен на повышение надежности системы и не уделяет достаточного внимания на проблеме, связанной с временными издержками при реализации данного метода [136-138]. Это налагает ограничения на область применения метода на основе ЛГУ.
В условиях туманной среды ЗПВН относится к классу №-трудных [77]. Это обусловлено, прежде всего особенностями инфраструктуры туманного слоя: количество узлов туманного слоя очень большое и зачастую заранее неизвестно, что, собственно, и ограничивает область применения метода на основе ЛГУ [139].
В настоящем диссертационном исследовании предложен метод формирования ограничений в ЗПВН, направленный на снижение временных издержек при организации распределенных вычислений в туманных средах.
Ключевым компонентом метода формирования ограничений в ЗПВН является онтологический анализ структур параллельных популяционных алгоритмов, используемых в распределенной системе, и способов их разбиения.
Перейдем к описанию метода формирования ограничений для ЗПВН. Предварительно сделаем ряд допущений, которые заключатся в следующем:
1. Каждый узел может предоставить информацию о состоянии своих ресурсов.
2. Множество узлов туманного слоя достаточно большое, но ограниченное, т.е. будем решать поставленную задачу в рамках одного домена.
3. Существует конечное множество способов разбиения параллельных популяционных алгоритмов, используемых в РСАПР, которое может быть описано в виде предметной онтологии.
Шаг 1. Поступление входных данных, содержащих сведения о параллельном популяционном алгоритме и о ресурсах узлов-кандидатов.
Шаг 2. Проведение процедуры онтологического анализа.
Шаг 3. Формирование ограниченного пространства узлов-кандидатов.
Шаг 4. Процедура моделирования размещения вычислительной нагрузки на ограниченном множестве.
Шаг 5. Решение задачи переноса вычислительной нагрузки на ограниченном множестве.
Шаг 6. Получение результата размещения вычислительной нагрузки.
Метод формирования ограничений для ЗПВН может быть представлен в виде схемы (Рисунок 24).
Рисунок 24 - Формирование ограничений в задаче переноса вычислительной
нагрузки
В условиях принятых допущений время решения ЗПВН уменьшается за счет сокращения множества узлов-кандидатов, на которых может быть размещена нагрузка. Для достижения этого автор данного исследования предлагает использовать процедуру онтологического анализа алгоритмических структур параллельных популяционных алгоритмов, реализуемых в распределенных системах для решения вычислительных задач, способов разбиения данных алгоритмов и информацию о состоянии ресурсов узлов туманного слоя, потенциальных для размещения вычислительной нагрузки. Процедура онтологического анализа позволяет сократить множество узлов-кандидатов для размещения вычислительной нагрузки на основании знаний, отображенных в предметной онтологии. В свою очередь, информация об имеющихся ресурсах узлов-кандидатов, расположенных в туманном слое, позволяет оценить их доступность и удаленность от узла-лидера (один из узлов, на котором изначально выполнялась комплексная функциональная задача), функции которого заключаются в сборе, хранении и обновлении информации.
Процедура онтологического анализа позволяет сформировать ограничения для ЗПВН в среде туманных вычислений (Рисунок 25). Это достигается путем
сокращения множества узлов-кандидатов для размещения вычислительной нагрузки на основании знаний о предметной области, отображенных в онтологии.
Процедура онтологического анализа включает [140]:
1. Входные данные, включающие исходные данные переносимой задачи, т.е. информацию о структуре параллельного популяционного алгоритма, реализуемого в распределенной системе и информацию о состоянии ресурсов узлов-кандидатов.
2. Классификация совокупности входных данных в соответствии с классами предметной онтологии.
3. Применение системы продукционных правил к классам онтологии с целью ограничения множества узлов, которое было получено в результате сбора сведений об имеющихся ресурсах.
ОНТОЛОГИЧЕСКИЙ АНАЛИЗ
Классификатор
Применение продукционных правил к классам онтологии
Принятие решения о выборе ограниченного множества узлов для переноса нагрузки
Рисунок 25 - Структура процедуры онтологического анализа
Таким образом, метод уменьшения времени решения ЗПВН заключается в процедуре эффективного формирования ограничений, которую можно рассмотреть с точки зрения скорости и качества ее реализации (Рисунок 26).
Рисунок 26 - Оценки от реализации метода, направленного на уменьшение времени решения задачи переноса вычислительной нагрузки
Иными словами, сокращение времени решения задачи переноса вычислительной нагрузки достигается за счет уменьшения времени формирования ограничений и сокращения поискового пространства с использованием процедуры онтологического анализа.
3.2 Методика размещения вычислительной нагрузки распределённой системы в среде туманных вычислений
Методику размещения вычислительной нагрузки распределённой системы в среде туманных вычислений можно представить в виде блок-схемы (Рисунок 27).
Блок 1 «Процедура избрания узла-лидера» является необходимым этапом для осуществления сбора информации об имеющихся ресурсах узлов, потенциально готовым к размещению вычислительной нагрузки. Условимся, что в качестве узла-лидера, ответственного за перенос нагрузки, выбирается узел из множества узлов, связанных с выполнением вычислительной задачи, назначенной к переносу. При этом выбор лидера может осуществляться любым алгоритмом, используемом для решения задачи о выборах лидера. Например, древесный
Рисунок 27 -Блок-схема методики размещения вычислительной нагрузки распределенной системы в среде туманных вычислений
Блок 2 «Методика выбора стратегии опроса узлов туманного слоя» предназначена для выполнения выбранным узлом лидером следующих этапов: опрос узлов, принадлежащих одному домену, и сбор информации об имеющихся ресурсах данных узлов (в соответствии с п.1. допущений: каждый узел может предоставлять информацию об имеющихся ресурсах).
Информация об имеющихся ресурсах содержит следующие данные об узле:
1) загруженность узла;
2) производительность узла;
3) удаленность узла от узла-лидера.
Проведение опроса начинается с узла-лидера и затем распространяется по всему домену. Важно отметить, что данная процедура может быть осуществлена с использованием различных стратегий опроса, имеющих в своей основе волновые алгоритмы поиска как в глубину так и в ширину. В связи с этим в настоящей работе автором проведено исследование различных стратегий поиска применительно к решаемой задаче и предложена методика выбора стратегии опроса узлов туманного слоя. Подробное описание методики выбора стратегии опроса узлов туманного слоя будет приведено в п.п 3.4 настоящего исследования.
«Информация о переносимом подграфе» представляет собой входную информацию и содержит следующие данные:
1) класс параллельного алгоритма;
2) модель распараллеливания;
3) способ разбиения графа вычислительной задачи;
4) исходное размещение (туман, облако, конечное устройство);
5) регламентированное время выполнения алгоритма;
6) параметры моделей (например, длительность сезона для островной модели параллелизма);
7) требования к ресурсам.
Блок 3 «Онтологический анализ» осуществляет процедуру онтологического анализа, подробно описанную в п.п 3.1 настоящего исследования. Результатом работы данного блока является ограниченное множество узлов-кандидатов для размещения вычислительной нагрузки.
Блок 4 «Решение оптимизационной задачи размещения нагрузки на ограниченном множестве ВУ» осуществляет моделирование размещения на ограниченном множестве узлов-кандидатов.
В Блоке 5 «Решение удовлетворяет?» происходит выбор следующего шага. При положительном ответе - переход на Блок 7 «Размещение подзадач на
ограниченном множестве ВУ», результат которого заключается в связывании переносимых подзадач с узлами-кандидатами.
При отрицательном ответе - переход на Блок 6 «Запуск процесса расширения домена с использованием метода ЛГУ», который позволяет расширять изначально рассматриваемый домен с использованием локальных групп устройств, принцип действия которых подробно описан в п.п 2.2.2 настоящего исследования. После первой итерации расширения домена, множество узлов, входящих в обновленный домен, поступает в Блок 1 и этапы, отраженные в методике (Блок 2 - Блок 3 - Блок 4 - Блок 5) повторятся до получения положительного ответа.
3.3 Метод формирования онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенных
систем
Центральным компонентом метода формирования ограничений в ЗПВН является предметная онтология, положенная в основу онтологического анализа. Онтология - это система, состоящая из набора понятий и набора утверждений об этих понятиях, на основе которых можно строить классы, объекты, отношения, функции и теории [124].
Метод формирования модели онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенных систем разработан на основе методологии, описанной в [141], с учетом особенности алгоритмических структур популяционных алгоритмов с точки зрения объема и частоты информационных обменов между процессами.
Полученная с помощью данного метода модель является каркасом базы знаний о рассматриваемой предметной области - географически распределенных систем, функционирующих на базе концепции туманных вычислений и использующих для решения прикладных задач параллельные реализации
популяционных алгоритмов. Разработка предметной онтологии ведется в программной среде Protégé 5.0.
Шаг 1. Определение классов онтологии. Разрабатываемая онтология включает следующие классы, описывающие исходные данные параллельных популяционных алгоритмов:
- класс популяционного алгоритма в соответствии с классификацией, приведенной в п. 2.1 настоящего исследования;
- модель распараллеливания алгоритма в соответствии с классификацией, приведенной в п. 2.1.1 настоящего исследования;
- способ разбиения параллельного алгоритма в соответствии с ограничениями на способы разбиения, рассмотренные в п. 2.1.2 настоящего исследования;
- исходное размещение: облако, туман, конечное устройство;
- регламентированное время исполнения алгоритма;
- параметры моделей распараллеливания;
- требования к вычислительным ресурсам [142, 143].
Шаг 2. Определение таксономической иерархии классов. Создание классов онтологии с установлением иерархических связей между понятиями ведется в соответствии с множеством концептов описанных выше (Рисунок 28).
Шаг 3. Определение слотов. Для установления отношений между концептами онтологии «Класс_алгоритма» и «Модель», используем вкладку «Object Properties» и создаем свойство «имеет модель», тем самым объявляя, что рассматриваемые классы популяционных алгоритмов имеют модели распараллеливания. Аналогично устанавливаются отношения между классами «Модель» и «Способ_разбиения» через свойство «имеет_способ_разбиения», «Островная_модель» - «Длительность_сезона» через свойство «имеет_параметр». Отношение через свойство «имеет_параметр» между подклассам «Островная_модель» и «Параметры» (Рисунок 29).
Classes Object properties Data properties
M ass hierarchy owl Thing [ ЭШНИЕ
Asserted ■»
т г ВН
▼ С Класс_апгоритма ( • АПЖП
I • АВНГ1
# АИЧО
• ГА
▼ • 0 Модель
Глобальная_ыодель
Диффузионная_модель
Островная_модель
▼ С Параметры
Время_ра6оты_алгоритма Длительность_сезона
▼ 0 Подграф
Размещение ► # Спосо6_раз6иения
▼ ф Пороговые_значения
Пороговое_знаненне_загруженность : ( Пороговое_значение_производительность Пороговое_значенне_удаленность V С Требования_ресурсы I 4 Загруженность
9 Производительность 1 # Удаленность
Рисунок 28 - Иерархия понятий предметной онтологии
Рисунок 29 - Пример отображения отношений между концептами онтологии
Шаг 4. Определение экземпляров классов. Заполнение классов онтологии экземплярами происходит в соответствии с существующими классификациями и проведенным выше анализом. Например, в терминах онтологии имеем: класс онтологии «Класс_алгоритма», который включает в себя соответствующие подклассы: «ГА» (генетический алгоритм), «АВЖП» (алгоритмы, вдохновленные живой природой), «АВНП» (алгоритмы, вдохновленные неживой природой), «АИЧО» (алгоритмы, инспирированные человеческим обществом). В свою очередь, каждый класс может быть заполнен
экземплярами. Например, класс «АВЖП» включает следующие экземпляры: «бактериальная оптимизация», «сорняковый алгоритм», «кукушкин поиск», «алгоритм муравьиной колонии», «алгоритм колонии пчел», «алгоритм светлячков». Класс «АВНП»: «гармонический поиск», «алгоритм гравитационного поиска», «меметический алгоритм», «электромагнитный поиск». Класс «АИЧО»: «алгоритм эволюции разума», «алгоритм стохастического диффузионного поиска». Пример отображения экземпляров подкласса «АВЖП» класса «Класс_алгоритма» в среде Protégé 5.0 приведен на Рисунке 30.
Subclass Of ОД
ФКласс_алгоритма
General class axioms
Subclass Of (Anonymous Ancestor)
Instances ^^
ф алгоритмколонннпчел ф алгоритм_муравьиной_колонии фалгорктм_светлячков ♦ бактериальная_оптимизаиия ф кукушкин_поиск ф сорняковый_алгорнтм
Рисунок 30 - Пример отображения экземпляров предметной онтологии
С использованием метода формирования модели онтологии, получена модель онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенных систем, которая структурирует знания о классах параллельных алгоритмах, используемых в распределенных системах, моделях распараллеливания алгоритмов, изменяемых параметров данных моделей и способах их разбиения, учитывает исходное размещение вычислительных узлов, регламентированное время выполнения алгоритма и требования к вычислительным ресурсам. Аспекты, отраженные в отологии в виде системы иерархии классов и отношений между ними, являются ключевыми в решении ЗПВН в распределенных системах и оказывают непосредственное влияние на эффективность функционирования системы.
©о©
ООО ООО ООО ООО 0©0|
Фрагмент онтологии, отображающей знания о распределении вычислительной нагрузки параллельных алгоритмов функционирования распределенной системы, полученный с применением разработанного метода, приведен на Рисунке 31.
3.4 Методика выбора стратегии опроса узлов туманного слоя
При разработке методики выбора стратегии опроса узлов туманного слоя, будем полагать, что, во-первых, существуют периоды времени, на протяжении которых сеть имеет фиксированную топологию, во-вторых, каналы связи двунаправленные. Будем также полагать, что опрос узлов туманного слоя реализуется посредством волновых алгоритмов, которые отличаются большим разнообразием своих свойств. Среди основных аспектов, позволяющих дифференцировать волновые алгоритмы выделяют: централизацию (децентрализацию), топологию (кольцо, дерево, клики и т.п.), первоначальные сведения (самоидентификация, идентификация соседей, восприятие направления), число решений, сложность (по числу обменов сообщениями, вычислительная сложность алгоритма) [144]. Оценка вычислительной сложности алгоритмов по числу обменов сообщениями и вычислительная сложность алгоритмов по времени приведена в Таблице 2.
Таблица 2 - Оценка сложности волновых алгоритмов
Алгоритм Топология Централизация О Вычислитель ная сложность алгоритма по числу обменов сообщениями Вычислите льная сложность алгоритма по времени
Общие алгоритмы
Кольцевой Кольцо Централизованный да N N
Древесный Дерево Децентрализованн ый нет N O(D)
Эха Произвольн ая Централизованный нет 2|E| O(N)
Опроса Клика Централизованный нет 2N-2 2N-2
Продолжение Таблицы 2
Алгоритм Топология Централизация О Вычислитель ная сложность алгоритма по числу обменов сообщениями Вычислите льная сложность алгоритма по времени
Фазовый Произвольн ая Децентрализованн ый нет 2Б|Б| 2D
Фазовый на кликах Клика Децентрализованн ый нет N(N-1) 2
Финна Произвольн ая Децентрализованн ый нет <4М|Е| O(D)
Алгоритмы обхода
Последоват ельного опроса Клика Централизованный да 2N-2 2N-2
Тора Тор Централизованный да N N
Гиперкуба Гиперкуб Централизованный да N N
Тарри Произвольн ая Централизованный да 2|E| 2|E|
Алгоритмы поиска в глубину
Классическ ий Произвольн ая Централизованный да 2|E| 2|E|
Авербаха Произвольн ая Централизованный нет 4|E| 4N-2
Сидона Произвольн ая Централизованный нет 4|E| 2N-2
С учетом соседей Произвольн ая Централизованный да 2N-2 2N-2
Здесь N обозначает количество процессов, \Е\— количество каналов связи, а В—диаметр сети (измеряемый по числу переходов).
С целью выбора алгоритма, который наилучшим образом подходит к решению поставленной задачи, т.е. реализации процедуры опроса конечного числа узлов туманного слоя, автор данного исследования предлагает новую методику. В основе данной методики положена идея об осведомлённости процессов о топологии сети и сведений о локализации сети в туманном слое.
Под осведомлённостью процессов будем понимать ту информацию о распределенной системе, которая предоставлена в начальном состоянии процессов. К числу сведений такого относят следующую информацию.
1.Топологическая информация (сведения о числе процессов, диаметре графа сети, топологии сети).
2.Отличительные признаки процессов (идентификация процессов).
З.Отличительные признаки соседей, т.е. каждый процесс знает идентификатор своих соседей.
Особенности туманных сред накладывают ограничения на выбор стратеги опроса узлов туманного слоя, в т.ч. локализация узлов-кандидатов для переноса вычислительной нагрузки в пределах туманного слоя играет немаловажную роль в выборе алгоритма опроса. Например, узлы-кандидаты для переноса вычислительной нагрузки могут локализоваться в той части туманного слоя, где располагаются узлы, выступающие в роли агрегирующих устройств (шлюзы, микроконтроллеры). Для дальнейшей передачи агрегированной информации в облако необходимо использовать высоконадежные каналы связи с широкой полосой пропускания (электрический кабель или радиоканал с использованием систем широкополосного доступа). Таким образом, рассматриваемый участок туманного слоя обладает статичностью и снабжен высоконадежными, широкополосными каналами связи. В свою очередь, участок сети, где расположено большое количество сенсорных устройств, причем их число постоянно изменяется, характеризуется большей динамичностью. Взаимодействие между сенсорными устройствами и шлюзами происходит на основе беспроводных связей, таких как Bluetooth и LoRA, мобильной связи поколений 4G и 5G, протоколов ZigBee, Wi-Fi. Стоит отметить, что на данный момент характеристики рассматриваемых коммуникационных каналов уступают по надежности и скорости передачи характеристикам проводных связей между шлюзами и серверами [145, 146].
Для разработки методики выбора алгоритма опроса узлов туманного слоя необходимо принять следующие допущения.
1. Чем ближе узлы-кандидаты расположены к облаку, тем топология сети более статична, характеристики каналов связи лучше, т.е. надежнее, шире полоса пропускания и т.д.
2. Чем узлы-кандидаты расположены ближе к краю сети, тем топология сети более динамична, характеристики каналов связи хуже.
Данные зависимости наглядно демонстрирует схема, приведённая на Рисунке 32.
Статичность Динамичность
Высокосоростные каналы связи Беспроводные каналы связи
Перейдем к описанию методики выбора стратегии опроса узлов туманного слоя, опираясь на свойство осведомленности процессов и принятые выше допущения.
Такие аспекты осведомленности как самоидентификация и идентификация соседей будем считать известными по умолчанию.
В рамках настоящего диссертационного исследования будем также считать, что узел-лидер имеет представление об ориентации сети, т.е. топология сети известна.
Если узел-лидер имеет представление об ориентации сети, то ему известны сведения о топологической информации графа сети (число процессов, диаметр графа сети, ее топология). В этом случае представляется возможным провести анализ удаленности узла-лидера от облака. Результатом данного анализа являются значения параметров D^ D2, измеряемые в хопах. Причем, D1 - расстояние от узла-лидера до «облака», D2 - расстояние от узла-лидера до «края» сети. На основании оценки значений параметров D1 и D2 и принятых выше допущений (рисунок 33) происходит принятие решения о том, какие критерии должны быть учтены при выборе алгоритма опроса. Далее на основании имеющихся оценок сложности волновых алгоритмов, сделать вывод об эффективности применения того или иного алгоритма опроса в конкретном случае.
Например, при расположении узла-лидера ближе к облаку, т.е. D1< D2, вычислительная сложность алгоритма по числу сообщений не играет первостепенной роли при выборе алгоритма опроса, поскольку узлы в данной части сети связаны между собой высокоскоростными каналами связи и обладают большой вычислительной мощностью, что позволяет проводить процедуру опроса без учета задержек на передачу данных по сети. Ethernet является широко распространенной и доминирующей технологией для проводных локальных сетей. В настоящее время скорость систем Ethernet достигает 100 Гбит/с. Например, оптоволоконный кабель обеспечивает скорость передачи данных до 1Гбит/с, беспроводная телекоммуникационная технология WiMax также
обеспечивает скорость до 1 Гбит/с. В этом случае выбор алгоритма опроса осуществляется на основании знаний о топологии сети, т.е. из числа имеющихся волновых алгоритмов выбирается алгоритм с минимальной вычислительной сложностью для рассматриваемой топологии.
Если же узлы-кандидаты для перемещения вычислительной нагрузки располагаются ближе к «краю» сети, т.е. D1>D2, то выбор алгоритма опроса происходит на основании комплексной оценки сложности волнового алгоритма, включающей в себя сложность по обмену сообщениями и сложность по времени. Это объясняется тем, что скорость передачи данных в беспроводных сетях, используемых для реализации технологии Интернета Вещей, значительна ниже скорости, которую обеспечивают сетевые технологии, реализующие связи с облачными центрами хранения и обработки данных. Более того, как правило, узлы «туманного» слоя имеют невысокие вычислительные ресурсы. Например, максимальные скорость передачи в беспроводной сети Zigbee составляет 256 Кбит/с, а реальная скорость варьируется в интервале от 5 до 40 Кбит/с. Помимо учета комплексной оценки сложности при выборе алгоритма опроса, также стоит учитывать топологию сети.
Блок-схема методики выбора алгоритма опроса на основе первоначальных сведений о процессах и информации о локализации узлов-кандидатов в туманном слое приведена на Рисунке 33.
В качестве первого «лучшего» алгоритма из списка алгоритмов выбирается алгоритм, который удовлетворяет требованию по топологии сети. Далее последовательно перебираются и анализируются алгоритмы, находящиеся в списке, до последнего.
Проведем теоретическую оценку выигрыша по времени при выборе алгоритма опроса узлов туманного слоя в случае расположения узла-лидера ближе к облачному слою.
При оценке вычислительной сложности по времени фазового алгоритма и алгоритма с учетом соседей при топологии вычислительной сети линейка,
выигрыш по времени отсутствует, поскольку отношение временных оценок данных алгоритмов равно 1.
При оценке вычислительной сложности по времени фазового алгоритма (Оф) и алгоритма с учетом соседей (Ос) при топологии вычислительной сети кольцо, выигрыш по времени при выборе фазового алгоритма достигает примерно
двух раз, поскольку: ^ = ш г = ~ 2, где при топологии кольцо и = [N/2],
причем [Ы] - целая часть числа N.
При оценке вычислительной сложности по времени фазового алгоритма (Оф) и алгоритма с учетом соседей (Ос) при топологии вычислительной сети 2Э-
Оф 2В 2x2(^^—1) 2 м 1ЛП
решетка, получаем: ^ = = 2(м-1) = 1). Тогда, если N=100, то
выигрыш по времени при выборе фазового алгоритма составляет примерно 5,5 раз.
При оценке вычислительной сложности по времени фазового алгоритма (Оф) и алгоритма с учетом соседей (Ос) при топологии вычислительной сети гиперкуб, диаметр (Э) вычислительной сети определяется формулой 1од2И. Тогда, если N=100, то выигрыш по времени при использовании фазового алгоритма достигает 15 раз.
Отметим, что для конфигураций с большим количеством узлов, выигрыш по времени будет увеличиваться.
Рисунок 33 - Блок-схема методики выбора стратегии опроса узлов туманного слоя
В основе этапа принятия решения о предпочтительном множестве узлов для переноса вычислительной нагрузки лежит система продукционных правил, которая связывает класс онтологии, содержащей знания о переносимом подграфе комплексной функциональной задачи и способах его разбиения, и потенциальное множество узлов для размещения вычислительной нагрузки. Продукционная модель имеет следующий вид:
г =< Б;Ь; А ^ В;д >, (16)
где —класс ситуаций;
— условие, при котором продукция активизируется;
— ядро продукции;
— постусловие продукционного правила [124].
В настоящем исследовании автором разработаны примеры продукционных правил, в соответствии с поставленными целями. Как правило, к разработке продукционных правил привлекаются эксперты. Эксперт - это человек, являющийся профессионалом высокой квалификации в некоторой предметной области. Данные знания формируются из опыта и суждений людей, работающих в данной области, понимающих общие принципы решения ее задач, знающих приемы решения, способных обеспечить управление неточными данными и дать оценку частичных решений [147]. Стоит отметить, что предложенная система продукций может быть расширена, поскольку эксперт способен действовать на высоком уровне, так как много знает об области своей деятельности.
Идея использования продукционных правил для формирования логического вывода на основании знаний, описываемых онтологическими моделями не нова. Например, в работе [148] предложен подход к анализу ситуаций, основанный на
применении семантических технологий. Ключевой идей данного подхода является использование онтологий для описания ситуаций и применение продукционных правил для их анализа.
Основой для разработки системы продукций послужил набор эвристических правил, описанных в работе [149], а также основных принципов распределения подзадач по процессорам в гетерогенных вычислительных системах [110, 150].
Для разработки системы продукций необходимо разработать правила для каждого способа разбиения подграфа вычислительных задач, согласно ограничениям, описанным выше. В этой связи последовательно рассмотрим возможные варианты разбиения в соответствии с существующими моделями распараллеливания.
Модель «Мастер-Подчиненный». Характерной особенностью данной модели параллелизма можно считать высокие накладные коммуникационные расходы, связанные с частым обменом информацией между «подчиненными» и «мастером», при этом объемы пересылаемых данных невелики. Следовательно, ключевым фактором, определяющим эффективность решения ЗПВН, является расстояние d между процессами «мастер» и «подчиненный».
Случай 1 - Способ разбиения: перенос фрагмента «мастер»
ЕСЛИ класс_алгоритма = генетический И способ_разбиения = мастер_перенос И исходное_размещение = облако И время_исполнения = T, И требования_ресурсов = пороговое значение, ТО Vdj ^ min,
где di - расстояние между узлом-кандидатом для перемещения «мастера», и i-м подчиненным, оставшимся на прежнем месте (в рассматриваемом случае в облаке);
Случай 2 - Способ разбиения: перенос фрагмента «подчиненный»
ЕСЛИ класс_алгоритма = генетический И способ_разбиения = подчиненный_перенос И исходное_размещение = облако И время_исполнения =T И требования_ресурсов = пороговое значение, ТО Vdk ^ min,
где dk - расстояние между узлом-кадидатом для перемещения k-го «подчиненного», и «мастером», оставшимся на прежнем месте (в рассматриваемом случае в облаке).
Случай 3 - Способ разбиения: перенос фрагмента «мастер-подчиненный»
ЕСЛИ класс_алгоритма = генетический И способ_разбиения = мастер_подчиненный_перенос И исходное_размещение = облако И время_исполнения =T И требования_ресурсов = пороговое значение, ТО Vd ^ min И Vd., ^ min
г ik .
где di - расстояние между узлом-кандидатом для перемещения «мастера», и i-м подчиненным, оставшимся на прежнем месте (в рассматриваемом случае в облаке);
dik - расстояние между узлом-кадидатом для перемещения «мастера» и узлом-кандидатом для перемещения k-го «подчиненного».
Случай 4 - Способ разбиения: перенос более одного фрагмента «подчиненный»
ЕСЛИ класс_алгоритма = генетический И способ_разбиения = Мподчиненный_перенос И исходное_размещение = облако И время_исполнения =T И требования_ресурсов = пороговое значение, ТО VdB ^ min, где dn - расстояние между узлами-кандидатами для перемещения N подчиненных, n е N, N > 1, и мастером, оставшимся на прежнем месте (в рассматриваемом случае в облаке).
Случай 5 - Способ разбиения: перенос фрагмента «мастер» и более одного фрагмента «подчиненный»
ЕСЛИ класс_алгоритма = генетический И способ_разбиения = мастер_N подчиненный_перенос И исходное_размещение = облако, И время_исполнения =T И требования_ресурсов = пороговое значение, ТО Vd ^ min И Vdn ^ min, где di - расстояние между узлом-кандидатом для «мастера» и оставшихся подчиненных;
dn - расстояние между узлами-кандидатами для перемещения N подчиненных, N > 1, и «мастером».
Параметрами «островной» модели являются: топология связей островов, длительность сезона tmig, стратегия миграции, режим обмена особей. Ключевым фактором, оказывающим влияние на эффективность решения ЗПВН, в данном случае является величина длительности сезона tmig. Очевидно, что при больших значениях данной величины, коммуникационные расходы, присущие данной модели параллелизма, малы. В случае, если величина tm'g имеет достаточно большое значение, то коммуникационные расходы возрастают.
Случай 1 - длительность сезона велика, т.е. tm'g>T, где T - пороговое значение длительности сезона, при котором велична коммуникационных расходов (I) (коммуникационные расходы появляются за счет необхоимости организации взаимодействия процессоров, выполняющих некоторые дополнительные действия) не оказывают влияния на эффектвность решения задачи преноса вычислительной нагрузки.
ЕСЛИ tmig >T И требования_ресурсов = пороговое значение, ТО Vd , d < D, где di - расстояние между узлом-кандидатом для перемещения i-го острова и оставшимися на прежнем месте островами; D - диаметр сети туманного слоя.
Случай 2 - длительность сезона мала, т.е. tmig <T.
ЕСЛИ tmig <T И требования_ресурсов = пороговое значение, ТО d ^ min.
Если рассматривать случай переноса более, чем одного острова (n > 1, n е N, N - «острова» - процессы, на которых выполнялась задача, назначенная к переносу), то будем иметь следующее.
ЕСЛИ tmig >T И требования_ресурсов = пороговое значение, ТО Vd , d < D где di - расстояние между узлом-кандидатом для перемещения i-го острова и оставшимися на прежнем месте островами; D - диаметр сети туманного слоя.
ЕСЛИ tmig <T И требования_ресурсов = пороговое значение, ТО Vd ^ min, Vd ^ min.
где di - расстояние между узлом-кандидатом для перемещения i-го острова и оставшимися на прежнем месте островами;
di - расстояние между узлами-кандидатами для перемещения N островов.
Предложенные продукционные правила позволяют принять решение о выборе вычислительного узла для переноса нагрузки на основании знаний, содержащихся в модели онтологии распределения вычислительной нагрузки параллельных алгоритмов функционирования распределенных систем.
3.6 Аналитическая оценка эффективности метода уменьшения времени решения задачи переноса вычислительной нагрузки
В рамках настоящего исследования с целью проведения аналитической оценки времени реализации разработанного метода формирования ограничений в ЗПВН в туманной среде построены упрощенные модели. Использование данных моделей также позволяет сравнить время, необходимое для реализации разработанного метода, с временем, необходимым для реализации метода на основе ЛГУ.
Поскольку множество узлов-кандидатов для размещения вычислительной нагрузки после проведения онтологического анализа может быть достаточно велико, то будем предполагать, что задача имеет решение.
Итак, оценка времени для реализации метода переноса вычислительной нагрузки, основанного на онтологическом подходе имеет следующий вид:
T =aN + kF + ßF + rNtF , (17)
аЫ - время, необходимое для проведения процедуры выбора лидера; Е - количество узлов в туманном слое;
кЕ - время, необходимое для опроса узлов с использованием алгоритмов опроса; /ЗГ - время, необходимое для проведения процедуры онтологического анализа;
- количество узлов после процедуры онтологического анализа; уЫГ - время, необходимое для поведения процедуры моделирования размещения задач N1 по узлам (алгоритмы составления расписаний). Рассмотрим каждое слагаемое подробнее.
Время, необходимое для проведения процедуры избрания лидера (аЫу), определяется временной сложностью алгоритма, используемого для этой цели. Рассмотрим различные случаи осведомленности узла-лидера о топологии сети.
Топология сети известна. Если топология сети известна и имеет вид дерева, то избрание лидера можно провести, воспользовавшись древесным алгоритмом. Тогда на решение задачи о выборах затрачивается О (Б) единиц времени с использованием обменов сообщениями (Таблица 2).
При помощи фазового алгоритма избрание лидера можно провести в сетях с произвольной топологией, используя О(Б\Е\) обменов сообщениями и затрачивая О (Б) единиц времени (Таблица 2).
При решении задачи о выборах алгоритмов Финна сложность по числу обменов сообщениями составляет О(^\Е\) (Таблица 2).
Топология сети произвольная и заранее неизвестная при условии отсутствии сведений о соседях. Данный случай рассматриваться в рамках данной работы не будет, поскольку наличие осведомленности о соседях является обязательным допущением, принятым в п. 3.1 настоящего исследования.
Сети с неизвестной топологией, но восприятием направления. В тех сетях, в которых отсутствует осведомленность о топологии, наличие восприятия
Сложность по числу обменов сообщениями алгоритма GHS (алгоритм Галладжера—Хамблета—Спиры) составляет O(|Щ + N log N), причем временная сложность может быть понижена до O(N), как показано в [151].
Величина kF - время, необходимое для опроса узлов с использованием алгоритмов опроса, зависит от выбора стратегии опроса, который, в свою очередь определяется методикой выбора, описанной выше (п. 3.4). В данном случае также необходимо рассмотреть случаи о наличии или отсутствии осведомленности о топологии сети.
Топология сети известна. Например, топология сети - гиперкуб, тогда вычислительная сложность алгоритма обхода по времени составит N, где N -количество узлов в туманном слое.
Топология сети неизвестна. Тогда рассматриваем алгоритмы опроса, работающие на произвольной топологии сети. Например, вычислительная сложность по времени алгоритма Сидона составляет 2N-2, где N - количество узлов в туманном слое.
Процедура онтологического анализа занимает время ¡3F и включает в себя выполнение этапов, рассмотренных в п. 3.1 настоящего исследования.
Время, необходимое для поведения процедуры моделирования размещения задач Nt по узлам Fs определяется выбором алгоритма построения расписаний. Задача формирования расписаний широко освещена в литературе. Для ее решения применяются разнообразные методы: случайный поиск, метод ветвей и границ, муравьиные алгоритмы, вероятностные алгоритмы, генетические алгоритмы, метод имитации отжига и различные эвристики [152].
В настоящее время применение различных эвристических методов для решения задачи формирования расписание представляется наиболее эффективным инструментом поиска «лучшего» в некотором смысле решения в
тех случаях, когда нахождение наилучшего решения крайне затруднено или невозможно [153]. Более того, время, затрачиваемое на реализацию таких методов, не зависит от количества задач, назначенных к размещению, а зависит от числа итераций, приводящих к получению удовлетворительного решения.
Проведем исследование зависимости времени, необходимого на реализацию предложенного метода, математическая модель которого описана формулой (17), от различных параметров, рассмотренных выше.
Зависимость времени реализации разработанного метода от выбора алгоритма избрания лидера.
Рассмотрим следующие случаи:
1. Избрание посредством алгоритма Финна на древесной сети (Т ont_based_alg_L_1), сложность по числу обмена сообщениями: 0(Ы \Е\).
2. Избрание посредством GHS алгоритма на произвольной сети ^ ont_based_alg_L_2), сложность по числу обмена сообщениями: 0(\E\+N*logN).
3. Избрание посредством древесного алгоритма ^ ont_based_alg_L_3), сложность по числу обмена сообщениями: О^), где N - число узлов, на которых изначально исполнялась задача.
Проведем исследование оценки по времени вышеперечисленных алгоритмов в зависимости от значения параметра N (Рисунок 34).
1400000 | 1200000 £ юооооо
(С
| 800000
а-
п
= 600000 п
400000
в; 1
а. 200000 ей
0
1
.1
Т оп1_Ьазес1_а1{г_1_1 I ТопЫэа я ес1_а \g_l_2 ТопЫэа 5 ес1_а 1я_Ь_3
5 10 15 20 25 30 35 40 45 Число узлов
Из Рисунка 34 видно, что время, затрачиваемое алгоритмом Финна резко возрастает с увеличением параметра N в то время, как время, затрачиваемое древесным и ОИБ алгоритмами примерно одинаково и имеет незначительный рост с увеличением N.
Теперь проведем сравнение времени, необходимого для реализации разработанного метода при различных вариациях алгоритмов избрания лидера с временем, необходимым для реализации метода формирования ограничений с использованием локальных групп устройств (ТШ§_Ьавеё) при малом числе итераций (1ё=5) (Рисунок 35).
Рисунок 35 -Временная оценка онтологического метода и метода на основе ЛГУ
при 1=5
Из Рисунка 35 видно, что при числе итераций 1ё=5 метод на основе локальных групп устройств занимает значительно меньше времени и в меньшей степени зависит от количества узлов, на которых изначально выполнялась задача.
Далее сравним время, затрачиваемое разработанным методом с использованием различных вариантов алгоритмов избрания лидера с временем, затрачиваемым методом формирования ограничений с использованием локальных групп устройств при числе итераций 1ё=35 (Рисунок 36).
1400000 1200000
2 юооооо -
л
| 800000
= 600000 -
а
400000
я
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.