Специальное математическое и программное обеспечение децентрализованного управления динамической реконфигурацией вычислительной системы на базе мобильных устройств

Рожкова Татьяна Сергеевна

Специальное математическое и программное обеспечение децентрализованного управления динамической реконфигурацией вычислительной системы на базе мобильных устройств тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Рожкова Татьяна Сергеевна

Рожкова Татьяна Сергеевна
кандидат наук
2022

Специальность ВАК РФ00.00.00

Количество страниц 172

Рожкова Татьяна Сергеевна. Специальное математическое и программное обеспечение децентрализованного управления динамической реконфигурацией вычислительной системы на базе мобильных устройств: дис. кандидат наук: 00.00.00 - Другие cпециальности. ФГБОУ ВО «Воронежский государственный технический университет». 2022. 172 с.

Оглавление диссертации кандидат наук Рожкова Татьяна Сергеевна

ВВЕДЕНИЕ

ГЛАВА 1. ИССЛЕДОВАНИЕ СУЩЕСТВУЮЩИХ ПОДХОДОВ К УПРАВЛЕНИЮ ПОТОКАМИ ДАННЫХ МОБИЛЬНЫХ УСТРОЙСТВ В МНОГОУЗЛОВОЙ ДЕЦЕНТРАЛИЗОВАННОЙ СИСТЕМЕ

1.1 Классификация распределённых систем

1.2 Особенности функционирования децентрализованной инфраструктуры

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

1.4 Постановка задачи исследования

ГЛАВА 2. РАЗРАБОТКА МОДЕЛИ ВЗАИМОДЕЙСТВИЯ ВЫЧИСЛИТЕЛЬНЫХ УЗЛОВ В МНОГОУЗЛОВОЙ ДЕЦЕНТРАЛИЗОВАННОЙ СИСТЕМЕ

2.1 Обоснование выбора показателя эффективности управления потоками данных в многоузловой децентрализованной системе

2.1.1 Общие требования к показателям эффективности

2.1.2 Основные характеристики распределенных вычислительных систем

2.1.3 Обзор показателей эффективности управления вычислительными ресурсами

2.2 Детерминированный подход к распределению ресурсов в МДВС

2.3 Стохастический подход к распределению ресурсов в МДВС

2.3.1 Одноагентное обучение с подкреплением

2.3.2 Многоагентное обучение с подкреплением

2.3.3 Теоретико-игровая модель управления потоками ресурсов в многоузловой децентрализованной системе

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

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМА ДЕЦЕНТРАЛИЗОВАННОГО УПРАВЛЕНИЯ ПОТОКАМИ ДАННЫХ МОБИЛЬНЫХ УСТРОЙСТВ И ИМИТАЦИОННОЙ МОДЕЛИ МНОГОУЗЛОВОЙ ДЕЦЕНТРАЛИЗОВАННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ

3.1 Разработка имитационной модели многоузловой децентрализованной вычислительной системы

3.1.1 Концептуальное описание модели

3.1.2 Формализация имитационной модели

3.1.3 Программирование имитационной модели

3.2 Испытание и исследование модели

3.2.1 Стратегическое и тактическое планирование

3.2.2 Предварительная обработка результатов эксперимента

3.2.3 Анализ чувствительности модели

3.3 Оценка эффективности

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

ГЛАВА 4. РАЗРАБОТКА АРХИТЕКТУРЫ ВЫЧИСЛИТЕЛЬНОГО УЗЛА МНОГОУЗЛОВОЙ ДЕЦЕНТРАЛИЗОВАННОЙ СИСТЕМЫ

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

4.1.1 Программно-аппаратные решения современных многоузловых вычислительных систем на основе мобильных терминалов

4.1.2 Анализ существующих проектов многоузловых вычислительных систем на основе мобильных терминалов

4.2 Разработка обобщенной модели процесса функционирования сервиса в составе вычислительной инфраструктуры

4.2.1 Разработка сервис-ресурсной модели вычислительной инфраструктуры

4.3 Разработка структурной модели двухуровневой организации программного обеспечения вычислительного узла многоузловой децентрализованной вычислительной системы

4.3.1 Программные решения поддержки функции распределенного взаимодействия узлов Инфраструктуры С1

4.3.2 Выбор и обоснование формата данных в распределенных реестрах ресурсов и сервисов и протокола взаимодействия узлов в составе Инфраструктуры С1

4.3.3 Выбор и обоснование варианта кворумной модели взаимного информационного согласования типа «ведущий-ведомый»

4.3.4 Разработка варианта протокола взаимного информационного согласования узлов многоузловой децентрализованной вычислительной системы в условиях ее динамической реконфигурации

4.4 Разработка структуры модулей программного обеспечения уровня физической организации вычислительного узла многоузловой децентрализованной вычислительной системы

4.4.1 Выбор и обоснование вычислительной платформы узла многоузловой децентрализованной вычислительной системы

4.4.2 Разработка структуры модулей программного обеспечения узла многоузловой децентрализованной вычислительной системы

4.5 Экспериментальная оценка масштабируемости и динамической устойчивости процесса распределенных вычислений на базе предложенной программно-аппаратной реализации вычислительного узла многоузловой децентрализованной вычислительной системы

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

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

Большой вклад в разработку новых решений в области математического и программного обеспечения подобных систем, связанный с повышением качества функционирования мобильных приложений и сервисов нового поколения, внесли А.С. Хританков, А.И. Тихомиров, В.И. Петренко, И. Голубев, А. Баранов, C. Goldman, S. Zilberstein, J. Vicente, J. Blakley, L. Hong, M. Yarvis. При этом в настоящее время практически отсутствуют подходы к формальному решению задачи распределения вычислительных ресурсов мобильных устройств, а имеющиеся исследования в области математического и программного обеспечения носят узконаправленный характер и, как правило, отражают частные аспекты ее решения.

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

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

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

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

2. Разработать теоретико-игровую модель взаимодействия вычислительных узлов многоузловой децентрализованной вычислительной системы в условиях динамической реконфигурации структуры системы.

3. Разработать алгоритм распределения вычислительных ресурсов и управления потоками данных протокола взаимного информационного

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

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

5. Разработать программное обеспечение процесса функционирования вычислительных узлов многоузловой децентрализованной вычислительной системы.

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

Объект исследования: многоузловая децентрализованная вычислительная система на базе мобильных устройств.

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

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

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

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

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

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

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

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

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

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

Положения, выносимые на защиту:

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

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

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

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

совершенствования программного обеспечения, реализующего вычислительный процесс в распределенной системе обработки информации. Также результаты внедрены в образовательный процесс Академии ФСО России в дисциплину «ЭВМ и периферийные устройства».

Апробация результатов диссертационного исследования. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: XI Всероссийская межведомственная научная конференция «Актуальные направления развития систем охраны, специальной связи и информации для нужд ОГВ РФ» Академия ФСО России, 2018 г., XXIV International Open Science Conference «Modern informatization problems in simulation and social technologies» (Yelm, WA, USA, 2019), IV Международная научная конференция перспективных разработок молодых ученых «Наука молодых -будущее России» ЮЗГУ, 2019 г., XXV International Open Science Conference «Modern informatization problems in simulation and social technologies» (Yelm, WA, USA, 2020), Научная конференция «Научно-техническое и информационное обеспечение деятельности...» ИКСИ Академии ФСБ России, г. Москва, 2020 г., IX Международная научно-техническая и научно-методическая конференция «Актуальные проблемы инфо-телекоммуникаций в науке и образовании», АПИНО 2020 г., XXV Международная научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР - 2020», Межведомственная научно-техническая конференция, посвященная теоретическим и прикладным проблемам развития и совершенствования автоматизированных систем управления и связи специального назначения «НАУКА И АСУ — 2020», XXVII International Open Science Conference «Modern informatization problems in simulation and social technologies» (Yelm, WA, USA, 2021).

Публикации. По результатам диссертационного исследования опубликовано 16 печатных работ, в т.ч. 3 статьи в изданиях, рекомендованных ВАК РФ, патент на изобретение, свидетельство о государственной регистрации

программы, а также статья в издании, индексируемом в Scopus. В работах, опубликованных в соавторстве и приведённых в конце автореферата, лично автором получены следующие результаты: [85] - теоретико-игровая модель взаимодействия вычислительных узлов в многоузловой децентрализованной вычислительной системе; [74, 75] - алгоритм распределения вычислительных ресурсов и управления потоками данных в многоузловой децентрализованной вычислительной системе; [77] - имитационная модель многоузловой децентрализованной вычислительной системы; [88, 84] - структурная модель взаимодействия программных модулей вычислительного узла многоузловой децентрализованной вычислительной системы; [48, 87, 76] - реализация математического обеспечения децентрализованного управления распределением вычислительных ресурсов; [79, 80] - реализация программного обеспечения децентрализованного управления распределением вычислительных ресурсов и потоков данных в многоузловой децентрализованной системе.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложений. Работа изложена на 162 страницах машинописного текста, включая 38 рисунков, 11 таблиц и список литературы из 119 наименований.

ГЛАВА 1. ИССЛЕДОВАНИЕ СУЩЕСТВУЮЩИХ ПОДХОДОВ К УПРАВЛЕНИЮ ПОТОКАМИ ДАННЫХ МОБИЛЬНЫХ УСТРОЙСТВ В МНОГОУЗЛОВОЙ ДЕЦЕНТРАЛИЗОВАННОЙ СИСТЕМЕ

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

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

1.1 Классификация распределённых систем

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

Распределенная система в узком смысле - это набор независимых компьютеров, представляющийся их пользователям единой объединенной системой [1].

Классификация распределенных систем и области применения показаны на Рис. 1.1, особенности их реализации приведены ниже [1, 2, 3, 4].

Распределённые системы

по реализации аппаратных решений

х

мультипроцессоры

1

мультикомпьютеры

по архитектуре сети

шинные

коммутируемые

по составу

X

гомогенные

т

по реализации программных решений

х

сильно связанные (распределенные ОС)

1

слабо связанные (сетевые ОС)

управление

_ -Л

Средства птромежуточного_уровня |

X

гетерогенные

управление

по реализации программной модели

X

а ц § к

* £ О С

8 я

о к

клиент-серверные

двухуровневые

трехуровневые

многоуровневые

одноранговые

1

агентные

по наличию системных свойств

кооперативные мобильные

по назначению

i

интерфейсные информационные

по методу обнаружения ресурсов, доступности ресурсов, методу взаимодействия ресурсов

централизованные

децентрализованные

по размерам и способам администрирования

X

кластеры

X

корпоративного уровня

X

грид-

системы

по типу предоставляемых ресурсов ^

вычислительные

информ ационные

1

передаточные

по области применения

X

транспорт

X

медицина

службы такси

_ перенаправление потоков транспорта

автомобильная обработка видео

безопасность

мониторинг пациентов

- телемедицина

.когнитивная помощь

X

экология

- видеонаблюдение информационная безопасность

_системы физической охраны объектов

X

управление

- энергопотреблением

- управление

отходами _ определение

уровня загазованности

сельское хозяйство

1.

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

дополненная реальность

системы орошения

Рисунок 1.1. Классификация распределенных систем

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

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

По соотношению узлов в сети клиент-серверные системы подразделяют на двухуровневые, трехуровневые, многоуровневые и одноранговые.

В базовой двухуровневой модели клиент-сервер все процессы в распределенных системах делятся на две возможно перекрывающиеся группы: серверы и клиенты. Процессы, реализующие некоторую службу, например, службу файловой системы или базы данных, называются серверами. Процессы, запрашивающие службы у серверов путем посылки запроса и последующего ожидания ответа от сервера, называются клиентами [1].

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

находиться и на машинах клиентов и серверов. Многозвенные архитектуры клиент-сервер являются прямым продолжением разделения приложений на уровни пользовательского интерфейса, компонентов обработки и данных. Различные звенья взаимодействуют в соответствии с логической организацией приложения. Частным случаем архитектуры клиент-сервер является одноранговая архитектура, в которой нет сервера и все узлы наделены равными правами. Агентные системы состоят из множества программных агентов — это еще один тип процессов, которые могут существовать в различных формах. Слово «агент» происходит от латинского agere (делать) и означает соглашение выполнять действия от имени кого-либо [6].

По шкале «централизованный-децентрализованный» выделяют следующие признаки классификации распределенных вычислительных систем: методы обнаружения ресурсов; доступность ресурсов; методы взаимодействия ресурсов [4]. Примером централизованного метода обнаружения ресурсов может служить служба DNS (англ. Domain Name System - система доменных имен). При использовании децентрализованного метода обнаружения ресурсов (например, в сети Gnutella) запрос на поиск отправляется всем узлам, известным отправителю. Эти узлы производят поиск ресурса у себя, и транслируют запрос далее. Примером централизованной доступности ресурсов в распределенной вычислительной системе (РВС) может являться технология веб-сервисов. Существует только один сервер с выделенным IP-адресом, который предоставляет определенный веб-сервис или сайт. Существуют системы, предоставляющие децентрализованные подходы к доступности ресурсов посредством множественного дублирования сервисов, которые могут обеспечить функциональность, необходимую пользователю (BitTorrent, Gnutella, Napster). Централизованный подход к взаимодействию узлов основан на том, что взаимодействие между узлами всегда происходит через специальный центральный сервер. Децентрализованный подход к взаимодействию

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

На основе данной классификации выбраны следующие распределенные системы для проведения дальнейших исследований: гетерогенные, мобильные, децентрализованные распределенные системы, предназначенные для распределения вычислительных ресурсов, называемые в дальнейшем «Многоузловые децентрализованные вычислительные системы» (МДВС) на базе мобильных устройств (Рис. 1.2).

Рисунок 1.2. Многоузловая децентрализованная вычислительная система

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

I

\

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

1.2 Особенности функционирования децентрализованной инфраструктуры

Многоузловая децентрализованная вычислительная система (МДВС) включает в себя вычислительные узлы, сеть и облачный сервис (Рис. 1.3). Вычислительные узлы могут создавать децентрализованную инфраструктуру для совместного использования локальных вычислительных ресурсов.

Вычислительный узел 1

Процессор

Подсистема ввода/вывода

Оперативная память

Коммуникационная инфраструктура

Переферийное устройство

Хранилище данных

Вычисли- Вычисли- Вычисли-

тельный тельный тельный

. узел 2 узел 3 узел K

Рисунок 1.3. Многоузловая децентрализованная система

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

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

Процессор может быть как одноядерным, так и многоядерным, процессор цифровых сигналов, микроконтроллер или другой процессор, или схема обработки / управления.

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

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

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

осуществления. Например, в некоторых вариантах осуществления коммуникационная инфраструктура может включать в себя схему связи ближнего радиуса действия, схему связи Bluetooth R, схему связи Wi-Fi R и/или другую схему беспроводной связи ближнего действия. Кроме того, в некоторых вариантах осуществления коммуникационная инфраструктура может включать в себя схему беспроводной связи большого радиуса действия, такую как, например, схема сотовой связи и/или другие схемы беспроводной связи большого радиуса действия.

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

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

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

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

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

Вычислительный узел

Децентрализованный сервисный модуль

Сервисы децентрализованной облачной инфраструктуры

Модуль виртуальной инфраструктуры

Модуль ^-сервисов

Модуль платформенных сервисов

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

Децентрализованные сервисы узлов

Модуль начальной загрузки

Модуль контекста

Модуль подключения

Модуль конфигурации

Коммуникационный модуль

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

Вариант осуществления уровня децентрализованной виртуальной инфраструктуры показан на рисунке 1.5.

Рисунок 1.5. Вариант осуществления виртуального уровня децентрализованной

инфраструктуры

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

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

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

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

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

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

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

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

Решению проблемы распределения ресурсов в системах с распределенным и децентрализованным управлением посвящено достаточно много исследований [8, 9]. Так, в распределенных системах хранения данных, а также в системах цифровых валют, широкое распространение получила модель децентрализованного управления поиском ресурсов на основе распределенной хэш-таблицы (Distributed hash table - DHT) [10]. Главной особенностью DHT является то, что ответственность за хранение и поиск информации распределена среди множества

узлов, объединенных в равноправную (одноранговую) сеть посредством логических ссылок.

Другой класс задач, связанный с децентрализованным управлением распределенными ресурсами, базируется на проблеме ограничения производительности узлов систем Edge и Fog computing. В большинстве случаев вычислительные ресурсы узлов таких систем не предназначены для выполнения ресурсоемких приложений обработки данных, например, Apache Spark [11]. При этом альтернативное программное обеспечение обработки данных, например, Apache Quarks [11], которое выполняется на ограниченных ресурсах узлов МДВС, обладает низкой функциональностью. Таким образом, важной исследовательской задачей является устранение дисбаланса между функциональностью и производительностью распределенных приложений для МДВС.

Решение этой задачи связано с:

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

- разработкой алгоритмов перераспределения пользовательских запросов на вычисления на основе децентрализованного управления единым распределенным реестром ресурсов МДВС.

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

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

Института прикладной математики им. М.В. Келдыша, в числе которых Н.Е. Балакирев, М.Г. Тонконогов, А.Е. Фирсов в начале восьмидесятых годов были получены результаты, позволившие заложить основу для качественного повышения эффективности использования ресурсов вычислительных систем. Актуальные исследования аукционных методов описаны в отечественных [52,53,54], и зарубежных работах [55]. Большинство авторов формулируют следующие свойства аукционов:

1. Эффективность. Аукционные методы позволяют получить максимальную ценность от сделки.

2. Скорость определения цены товара, которая определяется в результате конкуренции между участниками.

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

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

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

Все модели аукционов можно классифицировать по следующим признакам: число раундов в аукционе, аукцион с повышением или понижением ставок,

аукцион с открытыми или закрытыми ставками, прямой или обратный аукцион, комбинированный или некомбинированный аукцион.

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

В работах [12,13] представлен онлайн аукцион в сенсорных сетях. В приведенных работах структура аукциона - это централизованный аукционный дом, где аукционист - это базовая станция, а сенсорные устройства - участники торгов.

Наиболее популярным способом распределения ресурсов в проанализированных работах является двойной аукцион [14, 15, 16, 17, 18, 19]. В работе [14] представлен совместимый со стимулами механизм аукциона (1САМ) с закрытыми предложениями для торговли ресурсами между покупателями и продавцами. В [15] распределение ресурсов рассматривается как проблема аукциона в экономике сети. Недостатком двойного аукциона в [16] является то, что каждая точка доступа (продавец) предоставляет услугу только для одного оператора мобильной сети (покупателю) в каждый период времени. Многоуровневая архитектура приведена в [17]. В данной работе предлагается модель для распределения вычислительных ресурсов в пограничной вычислительной платформе. При этом система обладает иерархической структурой, в которой главный аукционист должен обладать глобальными знаниями о мобильной системе. В [18] представлены две схемы двойного аукциона с динамическим ценообразованием: двойной аукцион на основе безубыточности (BDA), в котором вычислительные ресурсы пограничных серверов назначаются статически, и, более эффективный, двойной аукцион на основе динамического ценообразования (DPDA), однако, не гарантирующий достоверность продавцов. В статье [19] предложен механизм многораундового комбинированного двойного аукциона, в котором используется платформа облачных вычислений, имеющая

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

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

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

В работах [20, 21, 23] приведен аукцион, который определяет победителя путем применения механизма теории игр и проведения повторяющейся игры с неполной информацией в некооперативной среде. В [23] формулируется игра Штакельберга, которая изучает процессы принятия решений рядом независимых игроков. Данный подход не учитывает предпочтения выполнения задачи. Более того, модель в [23] рассматривает только одного покупателя мобильных ресурсов, что исключает конкуренцию между несколькими покупателями в общей модели.

Классическое распределение ресурсов, а также распределение ресурсов с учетом настроек, приведены в работе [13]. Классическая проблема выделения ресурсов применима к доменам, где задачи не могут совместно использовать ресурсы.

Модель обратного аукциона представлена в [24, 25]. В работе [24] предлагается механизм стимулирования на основе обратных аукционов тС1о^Аис для проведения аукционов в реальном времени. При этом используется удаленное облако или куллеты. В подходе [25] предлагается алгоритм торговли с прогнозом, чтобы помочь брокеру пользователя использовать его способность прогнозирования для распределения ресурса сети в режиме онлайн.

Оптимальный аукцион на основе глубокого изучения распределения ресурсов с использованием нейронных сетей приведен в [26].

Планирование задач в распределенных системах обработки данных описан в [27, 28, 17]. Две главные отличительные особенности модели [28]: планирование заданий осуществляется с использованием единой для всех вычислительных устройств территориально распределенной системы абсолютных приоритетов. Вторая особенность, заключается в том, что использование абсолютных приоритетов делает затруднительным составление расписания запусков заданий.

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

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

Список литературы диссертационного исследования кандидат наук Рожкова Татьяна Сергеевна, 2022 год

T - —

Ui = W1 RP—P + + w3 ^^^^ (2-32)

RP T Si

где w, w и w - веса каждого атрибута; S - минимальная память обслуживания; p - цена за предоставление услуги; Vi - скорость вычисления ресурса, выражается в виде единиц сетки на миллион инструкций в секунду (MIPS); s - объем памяти ресурса; J - запрошенная вычислительная рабочая нагрузка; T - крайний срок выполнения задания; RP - секретная цена бронирования пользователя сетевого ресурса.

Критерий эффективности планирования в распределенной системе с абсолютными приоритетами может быть определен, как минимизация среднего времени обработки высокоприоритетных заданий [28]:

ТО.З. (ТГ.ОТД,ТЛО,ТВ min (2-33)

ТО.З. = ТГ О. + ТД + ТЛ О + ТВ где т0 3 - время обработки задания; тго - время пребывания задания в глобальной

очереди; Тд - время доставки задания в целевую ВУ; тло - время пребывания задания в локальной очереди; т5 - время выполнения задания на вычислительных ресурсах целевой ВУ.

В [18] критерием эффективности системы служит максимальное количество успешных сделок. Целью распределения ресурсов в мобильных пограничных вычислениях (MEC) является определение набора выигравших покупателей и продавцов, а также оплаты ( P и P соответственно), чтобы максимизировать количество совпадающих пар, в то же время удовлетворяя требованиям осуществимости для мобильных устройств (MD):

max \Wb\ (2.34)

Ebj j w - Rj

р) , рЪ<ъ

где Рц - количество доступных единиц ресурсов для М-го пограничного сервера; Ъу - максимальная цена, которую покупатель готов заплатить за пограничный

. Ъ

сервер у; р\ - цена, которую покупатель платит аукционисту; щ - цена предложения.

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

2.2 Детерминированный подход к распределению ресурсов в МДВС

За последнее время появилось множество работ, посвященных совместной оптимизации процесса принятия решений о распределении коммуникационных и вычислительных ресурсов. Как правило, проблемы такого рода формулируются в виде смешанных целочисленных нелинейных программ. В [34,35,36] описана проблема оптимизации вычислений на границе сети, основной задачей которой является минимизация общего энергопотребления мобильными устройствами с учетом требований к задержке пользователей. В работе [37] рассмотрена проблема минимизации суммарной задержки, возникающей при обработке данных и представлен алгоритм принятия решений о распределении ресурсов с учетом наличия в сети нескольких базовых станций и вычислительных серверов. В [38] представлена проблема минимизации задержки в наихудшем случае, однако позволяющая учесть требования пользователей. Для вычислений на границе сети также применяется взвешенная функция полезности энергии и задержки, описанная в [39,40,41,42]. Для решения проблемы динамического изменения среды

существуют также другие модели вычислений на границе сети, описанные в [43,44,45,46,47].

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

Рассмотрим множество взаимосвязанных вычислительных узлов n = {Ni,N2,...,nk} , представленных мобильными устройствами [48]. В общем

случае каждый узел Nk реализует функцию формирования вычислительной задачи, подлежащей распределению.

Zk - задача k-го узла, которая описывается кортежем (Gfc, Bk );

Gk - производительность в флопсах (flops), необходимая для завершения задачи Zk ;

Bk - размер задачи Zk (количество бит, необходимых для кодирования );

fk - производительность в флопсах, выделенная локальным процессором k-го узла для выполнения задачи Zk .

Тогда задержка вычислений при решении задачи на k-м узле определяется следующим образом:

Ч = ^ (2.37)

/к

к

Рис. 2.1. Условное обозначение случая 1 - задача обрабатывается узлом

самостоятельно

Время пребывания задачи на к-м узле, в случае, когда задача полностью решается на узле (Рис. 2.1), на котором она сформирована, определяется как:

тк (ч )=!ч

к=1

К г 1 Л

(2.38)

Як ~Як,

где: Як - средняя интенсивность поступления задач на к-й узел;

Як - средняя интенсивность обработки задач в к-м узле.

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

шт Тк (1к ) (2.39)

при /к < \шах, Як <Мк,

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

Обозначим долю задачи, обрабатываемой на к-м узле, как , 0 < 2к < 1. При этом 2к = 1, если к-й узел обрабатывает задачу самостоятельно, и 2к = 0 - если к-й узел не обрабатывает поступающую задачу, а перенаправляет ее на у-й узел множества N (Рис. 2.2).

4=ъ

к

у

Рис. 2.2. Условное обозначение случая 2 - задача перенаправляется на другой

узел

Тогда время пребывания задачи на к-м узле, в случае, если она перенаправляется на у-й узел, определяется следующим образом:

где Тк, у

= Вк_

Ску

тк (гк = °) = Ч, у + тк

задержка передачи данных между к-м и у-м узлами,

(2.40)

Ску - пропускная способность канала между к-м и у -м узлами.

Рассмотрим случай, когда для выполнения задачи гк собственных вычислительных ресурсов к-го узла недостаточно (Рис. 2.3). Тогда к-й узел перенаправляет часть (1 - ^ ) = dk задачи гк на у-й узел.

й

к

У

Рис. 2.3. Условное обозначение случая 3 - часть задачи обрабатывается узлом самостоятельно, часть задачи перенаправляется на другой узел

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

К Г

Тк ( ¿к ) = £ч*к*к к=1

Vк -

\ К

+ £Чк (1-¿к )

к=1

• 2к

Чк]

V] -Я] -(1 - ¿к ) 2кЯк

(2.41)

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

К

при

шт тах £ Тк (^)

{/к, 2к }] к=1

К

0 < 2к < 1, £ = 1, Ук к=1

(2.42)

К

£ /к < ^к,тах к=1

/к * 0, Ук

То есть, основываясь модели распределения ресурсов (выражения 2.37-2.41), целью работы является оптимизация вычислительных ресурсов таким образом, чтобы минимизировать максимальную задержку вычислений (выражение 2.42).

2.3 Стохастический подход к распределению ресурсов в МДВС

Для стохастических условий функционирования МДВС предложено использование агентного подхода, при котором вычислительный узел представляется интеллектуальным агентом (ИА), а совокупность вычислительных узлов, с которыми ИА взаимодействует в конкретный момент времени, как среду, в рамках которой он функционирует.

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

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

0 = ( 5,а1, А2, Р, я, о1, о2, о) (2.43)

где 5 - множество возможных состояний среды. А1 и А2 - конечные множества возможных действий для каждого вычислительного узла соответственно. р -функция вероятности перехода. Р (б' | б, «1,«2) - это вероятность перехода из

состояния б е 5 в состояние ^' е ^, когда узлы 1 и 2 выполняют действия «1 и «2 соответственно. я - глобальная функция вознаграждения. я(б,о!«2,б') - это вознаграждение, полученное системой в целом, когда агент 1 выполняет действие «1 , а агент 2 выполняет действие «2 в состоянии б , что приводит к переходу системы в состояние б' . 01 и 02 - конечные наборы наблюдений. О - функция

наблюдения. О(о^,02 | б,а\,«2,б )- вероятность наблюдения 01 и 02 (соответственно двумя вычислительными узлами), когда в состоянии б узел 1 выполняет действие «1, а узел 2 выполняет действие «2, и в результате получается состояние б' .

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

2.3.1 Одноагентное обучение с подкреплением

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

Рис 2.4. Схема одноагентного обучения с подкреплением

Для моделирования одноагентного обучения с подкреплением используется дискретная рекуррентная математическая модель задачи одноагентного обучения с подкреплением, описываемая для момента времени следующими свойствами:

( 5, А, V, О, о, Я, г) (2.44)

где 5 = {я} - множество возможных состояний среды; А = {а} - множество возможных действий вычислительного узла;

v(st,at,st+1): 5х Ах 5 ^[0,1] (2.45)

есть функция перехода, возвращающая вероятность перехода среды из состояния St в состояние St+1 при совершении вычислительным узлом действия at;

О = {о} (2.46)

есть множество возможных наблюдений среды, доступное вычислительному узлу;

, o): 5 X O ^[0,1] (2.47)

есть функция наблюдения, возвращающая вероятность получения вычислительным узлом наблюдения О; в состоянии среды s;;

R = {r} (2.48)

есть множество возможных значений выигрыша вычислительного узла;

r (st,at,st+1): S x A x S ^ R (2.49)

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

2.3.2 Многоагентное обучение с подкреплением

При рассмотрении множества ИА, указанная схема трансформируется в многоагентное обучение с подкреплением (МОП, англ. multiagent reinforcement learning).

При переходе от задачи одноагентного обучения с подкреплением к задаче многоагентного обучения с подкреплением в математической модели происходит

переход от скалярных величин ot,atr к векторам ot,rt.

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

которой вычислительные узлы отсутствуют, включается состояние s^ физической составляющей каждого k-го вычислительного узла:

S = W = {(х,si,...,sk | s,. e Sk,i = Ц)} (2.50)

где Sk - множество возможных состояний k-го вычислительного узла.

Множество доступных действий А одного вычислительного узла становится семейством А множеств Ак доступных действий к-го узла:

А = {а} = {(аг|аг е Ак,I = Ц)} (2.51)

Аналогично, при переходе от задачи одноагентного обучения с подкреплением к задаче многоагентного обучения с подкреплением происходит переход от множеств О и Я к семействам множеств О и Я.

Мощность множества Ак = {а} возможных действий отдельного к-го

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

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

узлов , I = 1, к.

Функция перехода подвергается векторизации:

v( ^, щ, ): 5 х А х 5 ^[0,1] (2.52)

где а( =(а{,...,а\),а\ еАк - коллективное действие всех I = 1,к вычислительных

узлов, оказываемое на среду в момент времени t, где к - количество узлов. Аналогичным образом векторизуются функции и Т.

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

Г * Ту V г, Ту е г (2.53)

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

По наличию в наблюдении 0г- информации, генерируемой другими вычислительными узлами - задачи с коммуникацией.

По признаку конкуренции за получение награды - кооперативные (конкуретные).

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

2.3.3 Теоретико-игровая модель управления потоками ресурсов в многоузловой децентрализованной системе

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

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

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

Пусть = (, , +1,г к ) - решение о предоставлении своих ресурсов всеми узлами, кроме узла к. Учитывая решения 2_к других узлов, вычислительный узел к хотел бы выбрать правильное решение е{0,1} - предоставлять ли свои

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

тр Дк(2к>2_к)>Vk е К (2.54)

2к е{0,1}

где Vк ( Ч, 2_к ) =

если Zk = 0

- служебная функция вычислительного

Ек (2), если zk= 1

устройства к;

Ек - накладные расходы узла, при вычислении задачи самостоятельно;

ЕС (2) - накладные расходы узла, при передаче задачи другим узлам.

Сформулируем вышеприведенную задачу как стратегическую игру

Г = (К\Рк}ЫК,{ук, где множество вычислительных узлов К - это

множество игроков, = (0,11 - это набор стратегий для пользователя к, у к (2к, 2_к) - служебная функция, которая представляет собой функцию

стоимости, которую должен минимизировать игрок к. Игра Г -децентрализованное распределение ресурсов.

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

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

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

* / * * \

Введем понятие равновесия по Нэшу. Профиль стратегии г =( г*,..., ) -

это равновесие по Нэшу в игре с децентрализованным распределением ресурсов,

*

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

^к (4, г-к) ^ ^к (гк, г-к), ^ке нк, к е К (2.55)

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

Введем концепцию наилучшего ответа. Учитывая стратегии г_к других

*

игроков, стратегия к-го игрока г* е является наилучшим ответом, если

ук (4, к (гк, к), е нк (2.56)

Согласно (2.55) и (2.56) в равновесии по Нэшу все пользователи используют лучшие стратегии реагирования по отношению друг к другу.

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

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

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

2. Разработана модель децентрализованной вычислительной системы для детерминированных условий.

3. Разработана модель децентрализованной вычислительной системы для стохастических условий.

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

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМА ДЕЦЕНТРАЛИЗОВАННОГО УПРАВЛЕНИЯ ПОТОКАМИ ДАННЫХ МОБИЛЬНЫХ УСТРОЙСТВ И ИМИТАЦИОННОЙ МОДЕЛИ МНОГОУЗЛОВОЙ

ДЕЦЕНТРАЛИЗОВАННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ

3.1 Разработка имитационной модели многоузловой децентрализованной вычислительной системы

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

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

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

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

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

К функциональным ограничениям разработанной имитационной модели относятся:

- используются распределенные вычислительные сети;

- в качестве вычислительных узлов выступают мобильные устройства с ограниченными вычислительными ресурсами;

- энергетическая составляющая мобильных устройств не учитывается;

- обработка задач ведется без очередей;

- при недостатке ресурсов в сети обработка задачи отклоняется;

- структура вычислительной сети является динамической;

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

Приняты следующие допущения:

- любой вычислительный узел может инициировать создание вычислительной инфраструктуры;

- любой вычислительной узел может быть источником задач;

- закон распределения времени поступления задач задается вручную из представленного набора;

- при добавлении вычислительных узлов и создании задач можно задать определенный набор ресурсов для них;

- учитывается возможность задавания определенного количества вычислительных узлов в системе.

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

Неуправляемые факторы: время обработки задачи, доступность ресурсов вычислительных узлов.

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

3.1.2 Формализация имитационной модели

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

(5, А, V, О, о, Я, г)

где 5 = {¿} - множество возможных состояний среды, А = {а} - множество возможных действий вычислительных узлов, О = {о} - множество наблюдений среды, я = {г} - множество возможных значений выигрыша.

Мощности указанных множеств определены следующим количеством элементов:

1. Для множества 5":

- ¿о - формирование структуры МДВС;

- ¿1 - ввод вычислительного узла в структуру МДВС;

- ¿2 - вывод вычислительного узла из структуры МДВС;

- ¿з - расформирование МДВС.

2. Для множества А:

- а^ - вычислительный узел в составе структуры МДВС определяет достаточность свободных локальных вычислительных ресурсов для решения поступившей на его вход задачи;

- а2 - вычислительный узел обслуживает поступившую на его вход задачу путем заняия всех свободных локальных вычислительных ресурсов;

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

3. Для множества О:

- во - другие вычислительные узлы имеют свободные локальные вычислительные ресурсы;

- в1 - свободные локальные вычислительные ресурсы других вычислительных узлов отсутствуют.

4. Для множества Я:

- г0 - приоритет вычислительного узла при кооперативной обработке задачи, поступившей на его вход, увеличивается;

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

Очевидно, что значения показателей указанных множеств в момент времени ? носят вероятностный характер и определяются следующими функциями, возвращающими соответствующие вероятности значений: функция наблюдения (выражение 3.1); функция перехода (выражение 3.2); функция выигрыша (выражение 3.3).

(3.1)

(3.2)

(3.3)

В соответствии с целями имитационного моделирования, разработаны два алгоритма ее работы.

На рисунке 3.1 представлена структурная схема алгоритма процесса-ведущего. Алгоритм процесса-ведущего описывает полный цикл обработки задач в распределенной системе. Блоки «Ввод задач» и «Проверка очереди» выполняются параллельно: поступающие потоки задач попадают в блок «Ввод задач». Новые задачи поступают в очередь. После синхронизации описанных процессов, задачи помещаются в очередь «Готовы к выполнению». Данные задачи будут рассылаться на узлы-исполнители. Далее для каждого узла-исполнителя отправляется запрос на выполнение задачи в соответствии с наличием у него необходимого количества свободных ресурсов. Если узел-ведомый имеет необходимое количество свободных ресурсов - задача передается на выполнение и цикл завершается, если нет - наличие ресурсов проверяется у следующего узла-ведомого и так далее. Задача помещается в очередь и выполняется. Задача может быть выполнена или не быть выполнена, если узел-ведомый отключился от системы. В случае если задача не выполнена, обратный ответ не возвращается, и узел-ведущий понимая, что задача долго не выполняется, помещает ее в очередь «Готовы к выполнению». Таким образом, задача повторно запускается на выполнение. В случае, если задача выполнена, результат отправляется узлу-ведущему.

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

Начало

Цикл основного процесса

/ Ввод задачи / Проверка очереди Выполняются

Помещение задачи в очередь: Готовы к выполнению

Рис. 3.1 Структурная схема алгоритма процесса-ведущего

Рисунок 3.2. Структурная схема алгоритма процесса-ведомого

На рисунках 3.2, 3.3 представлены структурные схемы моделирующих алгоритмов, описывающие два эксперимента, отличающиеся изменением различных характеристик. Для первого эксперимента - фиксируются параметры потока задач и потока узлов-ведомых, при этом меняется количество узлов в системе. Для второго эксперимента - фиксируются параметры потока задач и количество узлов в системе, при этом меняются параметры потока узлов-ведомых.

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

задается следующими параметрами: интенсивностью входа узлов в систему и интенсивностью выхода (отключения) узлов из системы. Далее вводится количество узлов-ведомых. Длительность цикла «Пока продолжается эксперимент» зависит от области определения параметра количества узлов-ведомых. Далее выполняется эксперимент для заданного количества вычислительных узлов. Задается количество тестов для всех возможных количеств узлов, а также объем моделирования для заданного количества узлов-ведомых в начальный момент времени. Далее генерируется поток задач с заданными характеристиками и происходит выполнение процесса узла-ведущего (Рисунок 3.1). Далее осуществляется регистрация времени выполнения текущей задачи и вывод результатов моделирования.

На рисунке 3.3 представлена структурная схема моделирующего алгоритма № 2. Для данного алгоритма вводятся следующие параметры моделирования: параметры потока задач и количество узлов-ведомых. Вводятся параметры интенсивности потока узлов-ведомых. Далее алгоритм аналогичен представленному на рисунке 2.3.

Программная реализация представленных на рисунках 2 и 3 моделирующих алгоритмов требует выбора среды моделирования. Выбор среды моделирования был сделан в пользу программного продукта российского разработчика - AnyLogic [57,58,59]. К достоинствам этой среды имитационного моделирования следует отнести: наличие необходимых встроенных библиотек, возможность использования языка программирования Java, удобный и интуитивно понятный графический интерфейс, множество примеров моделей и исчерпывающая информационно-справочная документация.

В состав структуры модели в среде имитационного моделирования AnyLogic включены следующие сущности:

- «Source» - создает задачи. Задачи создаются согласно заданной интенсивности. Источником заявок может являться любой из вычислительных узлов.

- «Delay» - задерживает заявки на заданный период времени. Время задержки вычисляется динамически, в зависимости от параметров задачи.

- «Sink» - уничтожает задачи. Задача, поступившая в систему, должна быть удалена.

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

- «DataSet» - класс, написанный на языке Java, используемый для хранения данных типа "double" и поддержания актуальности минимума и максимума хранимых данных для каждого измерения.

- «Event» - класс, написанный на языке Java, используемый для планирования действий в модели. Используются события, происходящие при выполнении заданного условия, например, условия достаточности вычислительных ресурсов.

- «Connections» - содержит связи с контактами своего агента и задает настройки взаимодействия.

Модель в процессе обработки задач представлена на рисунке 3.5 при добавлении 5 вычислительных устройств в систему, на рисунке 3.6 - при добавлении 10 вычислительных устройств в систему, на рисунке 3.7 - при добавлении 50 вычислительных устройств при прочих равных условиях.

Рис. 3.5 Модель в процессе работы при добавлении 5 вычислительных

узлов в систему

Рис. 3.6 Результат моделирования при добавлении 10 вычислительных

узлов в систему

Рис. 3.7 Результат моделирования при добавлении 50 вычислительных

узлов в систему

Испытание и исследование модели производится в ходе проверки ее достоверности. В [60] выделяют три составляющие оценки достоверности модели:

- оценка адекватности модели;

- верификация модели;

- валидация данных модели.

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

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

Для проверки валидации данных модели, в зависимости от целей моделирования, допускается проводить: оценку точности результатов моделирования, оценку устойчивости результатов моделирования или анализ чувствительности имитационной модели. Так как целью имитационного моделирования была оценка времени пребывания задачи в сети в зависимости от количества вычислительных узлов в ее составе, для проверки валидации данных модели был произведен анализ чувствительности отклика модели к изменению соответствующего уровня управляемого фактора при фиксации уровней других факторов [62]. Методика анализа чувствительности представлена в Приложении 3. Проведению вычислительного эксперимента предшествовали этапы стратегического и тактического планирования.

На рисунке 3.8 представлена зависимость среднего времени обработки задач от количества вычислительных узлов в системе. На графике видно, что при значении количества вычислительных узлов свыше 10 тысяч, время обработки задач перестает существенно уменьшаться.

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

50

I о -

<# # # <# # ^ л? л? ^ ^ ^ Л? #

Количество вычислительных узлов в системе, шт

Рис. 3.8 График зависимости времени обработки задачи от количества

узлов в системе

80

70

о

X ■О

5 60

с!

о

3- 50

П5

С!

П5

т

£ 40

о

ю

П5

Ю

° 30

ОС

си ей

20

10

0

О' О' СУ О' О' О' О' О' О' О' V V Отношение количества входящих узлов в систему к количеству выходящих узлов

Рис. 3.9 Зависимость среднего времени выполнения задач от отношения количества добавляющихся в систему узлов к количеству покидающих систему

узлов

3.2.1 Стратегическое и тактическое планирование

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

Для проведения оценки результатов моделирования были выбраны три точки анализа чувствительности модели, представляющие собой уровни значения параметра N - количества вычислительных узлов: 500, 1000, 15000.

Интервалы изменения параметра N для каждой из точек представлены величинами, составляющими 10% от значения параметра N в этих точках, отложенные от своего значения в соответствующих точках в обе стороны на длину интервала изменения: (475,525), (950,1050), (14250,15750).

Тактическое планирование определяет условия проведения каждого прогона в рамках составленного плана эксперимента и связано с вопросами эффективности и определением способов проведения прогонов, намеченных планом эксперимента. Ключевыми задачами тактического планирования являются [60,63]:

- определение длительности имитационного прогона или требуемого числа повторений каждого прогона, обеспечивающего заданную точность результатов моделирования;

- определение длительности переходного режима, задание начальных условий.

В ходе эксперимента, для компенсации влияния случайных погрешностей, при одних и тех же уровнях факторов измерения повторяются несколько раз [65]. Главной задачей при этом является определение числа повторений (параллельных опытов), обеспечивающих достаточную статистическую значимость результатов. Решение этой задачи требует соблюдения баланса между желаемым уровнем точности и затратами на моделирование [63]. Требуемый объем выборки п при условии отсутствия априорной информации о ее законе распределения можно рассчитать, используя выражение 3.4, которое выводится из неравенства Чебышева

значимости а

а

п =

к2

а

(3.4)

Р (I ^ "Н>^72

£

(3.5)

Таким образом, для уровня значимости а = 0,05 и точности й = а

необходимое количество параллельных опытов п = 80 .

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

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

Таблица 3.1

План однофакторного эксперимента

Номер опыта г Уровень фактора х^ (количество вычислительных узлов Ы) Количество параллельных опытов п1

1 475

2 525

3 950 80

4 1050

5 14250

6 15750

3.2.2 Предварительная обработка результатов эксперимента

Обработка результатов эксперимента при равномерном дублировании включает в себя следующие процедуры [65,66,67]:

- определение среднего квадратического отклонения (СКО) и дисперсии для каждого опыта;

- проверку на наличие грубых ошибок (выбросов);

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

- проверку на однородность дисперсий;

- проверку на принадлежность средних двух выборок одной генеральной совокупности.

Описательная статистика отклика модели в проведенном эксперименте представлена в таблице 3.2, где СКО определяется в соответствии с выражением 3.6 [66]:

5 =

1

П _ 2 Е( у-у)

г=1

(3.6)

п -1

Таблица 3.2

Описательная статистика отклика модели

Номер опыта г Уровень фактора X N Среднее отклика у СКО Дисперсия 2

1 475 30,5699 0,3809 0,1451

2 525 27,8272 0,4011 0,1609

3 950 7,5615 0,2641 0,0697

4 1050 6,9009 0,2712 0,0735

5 14250 6,2719 0,1799 0,0323

6 15750 5,9893 0,1339 0,0179

Проверка на наличие грубых ошибок результатов эксперимента проводилась по критерию Граббса [68], эмпирическое значение критерия определяется в соответствии с выражениями 3.7 и 3.8, а критическое - в соответствии с выражением 3.9.

61 = (3.7)

5

G —n -1 t(x/(2n>-2 (39)

K -^\ n - 2 + (3.9)

у a/(2n),n-2

где n_2 - значение распределения Стьюдента со степенями свободы

f — n - 2 и уровнем значимости a / (2n), определяемое при помощи встроенной функции Microsoft Excel «СТЬЮДЕНТ.ОБР».

Результаты проверки представлены в таблице 3.3. Учитывая, что эмпирические значения критерия Граббса не превышают критическое, можно сделать вывод о том, что грубые ошибки отсутствуют.

Таблица 3.3

Результаты проверки выборок на наличие грубых ошибок

Номер опыта i Минимальное и максимальное yj Эмпирические значения Gi и G2 Эмпирическое значение критерия Граббса Gl/G2 Критическое значение критерия Граббса GKp при n — 80, a — 0,05

1 ymin 29,826 1,951776564 0,942719554

ymax 31,359 2,071672355

2 ymin 27,039 1,964906372 1,091992242

ymax 28,549 1,799551234

3 ymin 7,0706 1,858796764 1,030220357

ymax 8,038 1,804240818 3,3061

4 ymin 6,4257 1,752051823 1,010848756

ymax 7,371 1,73340708

5 ymin 5,9252 1,927111275 0,971965237

ymax 6,6286 1,982768205

6 ymin 5,7611 1,704314794 0,882785

ymax 6,2478 1,930545183

Проверка на нормальность проведена по критерию хи-квадрат Пирсона [66,69,70]. Распределение значения величины y в параллельных опытах подчиняется нормальному закону, результаты проверки этой гипотезы представлены в приложении 5.

Проверка на однородность дисперсий для пар опытов, результаты которых будут сопоставляться при анализе чувствительности, производилась с использованием критерия Фишера [67], эмпирическое значение которого определяется в соответствии с выражением 3.30, а критическое - при помощи встроенной функций Microsoft Excel 'Т.ОБР.ПХ" при уровне значимости а и числе степеней свободы выборок f = n -1.

S 2

F = Smx (3.10)

S2 •

Smin

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

Таблица 3.4

Результат проверки однородности дисперсий

Номер опыта i СКО Sj Дисперсия 'Si2 Эмпирическое значение критерия Фишера F Критическое значение критерия Фишера FKp при ./max = /min = 79 а = 0,05

1 0,3809 0,1451 1,10889042 1,4512

2 0,4011 0,1609

3 0,2641 0,0697 1,054519369

4 0,2712 0,0735

5 0,1799 0,0323 1,804469274

6 0,1339 0,0179

Проверка на принадлежность средних одной генеральной совокупности для пар опытов, результаты которых будут сопоставляться при анализе чувствительности, производилась с использованием критерия Стьюдента [71], эмпирическое значение которого определяется в соответствии с выражением 3.11,

f = ni + n2 - 2.

t = f1 - У2 (3.11)

2 2

|SL + S2_

n1 n2

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

Оглавление диссертации кандидат наук Рожкова Татьяна Сергеевна

Рекомендованный список диссертаций по специальности «Другие cпециальности», 00.00.00 шифр ВАК

Методы и средства организации вычислений в туманных средах2022 год, кандидат наук Сафроненкова Ирина Борисовна

Похожие диссертационные работы по специальности «Другие cпециальности», 00.00.00 шифр ВАК

Разработка системы запуска ресурсоемких приложений в облачной гетерогенной среде2013 год, кандидат технических наук Е Мьинт Найнг

Использование виртуализации для увеличения эффективности вычислении2020 год, кандидат наук Чжо За

Список литературы диссертационного исследования кандидат наук Рожкова Татьяна Сергеевна, 2022 год