Содержание к диссертации
Введение
1 Балансировка загрузки узлов вычислительной сети с помощью протокола локального голосования 15
1.1 Предварительные сведения 21
1.2 Задача балансировки загрузки 22
1.3 Протокол перераспределения заданий 24
1.4 Использование протокола локального голосования на практике 28
2 Оптимизация процесса балансировки загрузки узлов вычислительной сети с задачами разных приоритетов 33
2.1 Балансировки загрузки сети, выполняющей задания с разными приоритетами 33
2.2 Дифференцированный консенсус 36
2.3 Оценка оптимального размера шага алгоритма 48
2.4 Стоимостные ограничения на использование связей
2.4.1 Рандомизация использования связей 50
2.4.2 Условия достижимости дифференцированного консенсуса 51
2.4.3 Оптимизация размера шага алгоритма 60
3 Имитационное моделирование и адаптация размера шага алгоритма 62
3.1 Моделирование поведения сетевой системы, выполняющей задания нескольких классов, перераспределенных по протоколу локального голосования (2.4) в условиях помех, задержек, изменяющейся структуры связей сети 62
3.2 Моделирование поведения сетевой системы, выполняющей задания нескольких классов приоритетов, при наличии разных стоимостных ограничений на использование связей для обмена заданиями каждого класса 65
3.3 Исследование зависимости эффективности достижения консенсуса в сетевой системе от выбора размера шага алгоритма 68
3.4 Поисковый алгоритм стохастической аппроксимации с рандомизацией на входе для адаптации размера шага протокола локального голосования 71
Заключение 78
Литература
- Протокол перераспределения заданий
- Дифференцированный консенсус
- Условия достижимости дифференцированного консенсуса
- Моделирование поведения сетевой системы, выполняющей задания нескольких классов приоритетов, при наличии разных стоимостных ограничений на использование связей для обмена заданиями каждого класса
Введение к работе
Актуальность темы. В последнее время все большее внимание уделяется задачам распределенного взаимодействия в сетях и управления в сетевых динамических системах. Интерес к тематике управления в динамических сетях вызван приложениями в различных областях, включая, например, обмен информацией в многопроцессорных сетях, логистические сети, производственные сети, сенсоры и беспроводные сети, скоординированное движение БПЛА, подводных объектов и мобильных роботов, распределенные системы управления электрических сетей, сложные кристаллические решетки и наноструктурные объекты. В работах Ч. Абдал-лы (С. Abdallah), Р. П. Агаева, Б. Р. Андриевского, П. Антсаклиса (P. Antsaklis), Д. Баиллеула (J. Baillieul), Р. В. Берда (R.W. Beard), Ф. Булло (F. Bullo, Т. Виксека (Т. Vicsek), В. А. Виттиха, В. И. Городецкого, И. А. Каляева, Д. Кортеса (J. Cortes), Ф. Льюиса (F. Lewis), А. С. Матвеева, А. С. Морса (A. S. Morse), Р. М. Мюррея (R. М. Murray), Р. Олфати-Сабера (R. Olfati-Saber), В. Рена (W. Ren), Г. А. Ржевского, Г. Таннера (Н. Tanner), А. Л. Фрадкова, М. Хуанга (М. Huang), П. Ю. Чеботарева и других заложены основы теоретического описания методов анализа и синтеза децентрализованного адаптивного мультиагентного управления, обсуждаются многочисленные потенциальные практические приложения в управлении сложными производственными, энергетическими системами.
Н. О. Амелина, Д. Армбрустер (D. Armbruster), А. Глашенко, И. Грачев, С. Иноземцев, И. А. Каляев, А. С. Михайлов, С. Э. Парсегов, А. В. Проскурников, П. О. Скобелев, П. С. Щербаков и др. активно изучали алгоритмы управления в сетях, узлы которых выполняют определенные действия параллельно. Подобные сетевые системы применяются в вычислительных, производственных сетях, сетях обслуживания, транспортных и логистических сетях. Несмотря на объем работ по тематике управления децентрализованными системами, удовлетворительные решения предложены для ограниченного класса задач. Такие факторы, как переключения топологии связей, помехи и задержки при измерении состояний агентов значительно повышают сложность решения задач. Достаточно простые адаптивные алгоритмы часто демонстрируют удовлетворительную производительность, но остаются открытыми вопросы их теоретического обоснования и достижения оптимальной производительности. Как правило, при постановке задачи предполагается, что все задания, выполняемые системой, одинаково важны для исполнения.
На практике во время работы системы одни задания имеют более высокую важ-
ность, чем другие. Это может быть вызвано необходимостью выполнения системных запросов для поддержания работы всей системы; некоторые задания могут иметь более высокую срочность, в то время как для других заданий время их выполнения в системе не так критично; у системы могут быть несколько групп пользователей, которым требуется разный уровень обслуживания. В таких ситуациях для дифференциации заданий разных классов вводят приоритеты, которые учитываются при принятии решений об очередности выбора заданий на исполнение.
В последнее время набирает популярность концепция интернета вещей — соединения различных объектов в сеть для организации их взаимодействия, проводятся многочисленные эксперименты по организации взаимодействия групп мобильных роботов, наблюдается все возрастающее применение беспилотных летательных аппаратов, как в военных, так и в гражданских целях. Перечисленные тенденции актуализируют разработку и применение мультиагентного подхода в управлении группой объектов, поскольку, с одной стороны, подобными группами зачастую неэффективно управлять централизованно, с другой — объекты в таких группах способны самостоятельно организовывать и поддерживать взаимодействие внутри группы.В подобных системах устройства, как правило, обладают ограниченным запасом энергии, в связи с чем встает проблема организации взаимодействия агентов в системе, учитывающего расходы на обмен данными по сети.
Обозначенные проблемы и тенденции подтверждают актуальность темы диссертационного исследования.
Целью работы является разработка и исследование алгоритмов повышения эффективности децентрализованного перераспределения между узлами вычислительной сети очередей задач с разными уровнями приоритетов в условиях переменной структуры связей, помех и задержек при передаче информации. Для достижения этой цели были поставлены и решены следующие задачи:
-
исследовать применимость алгоритма локального голосования для решения задачи дифференцированного консенсуса в децентрализованной вычислительной сети с заданиями разных приоритетов в условиях случайно изменяющейся структуры связей, помех и задержек при передаче информации по каналам связи;
-
оптимизировать величину размера шага протокола локального голосования, по которому функционирует система в заданных условиях;
-
исследовать применимость алгоритма локального голосования для решения задачи дифференцированного консенсуса при наличии усредненных ограничений на использование связей внутри сети. Оптимизировать величину размера шага протокола локального голосования при наличии ограничений на использование связей внутри сети;
-
разработать пакет прикладных программ для моделирования процесса перераспределения заданий разных приоритетов между агентами в сети.
Методы исследования. В диссертации используются методы теорий исследования операций, управления, графов, вероятностей и математической статистики; применяется стохастическая аппроксимация, рандомизированные алгоритмы, имитационное моделирование.
Основные результаты. В ходе выполнения работы получены следующие научные результаты:
1) предложена рандомизированная модификация алгоритма локального голосо
вания для достижения дифференцированного консенсуса в вычислительной
сети с заданиями
нескольких приоритетов в условиях случайного изменения связей, при помехах и задержках в каналах связи. Установлены условия достижения дифференцированного среднеквадратического є-консенсуса в этих условиях. Получена оценка отклонения значений на узлах в сетевой системе от консенсусного значения;
-
получена оценка оптимального размера шага алгоритма локального голосования для системы в условиях случайного изменения связей, помех и задержек в каналах связи;
-
предложена рандомизированная модификация алгоритма локального голосования для задачи достижения дифференцированного консенсуса в системе с заданиями разных приоритетов при наличии стоимостных ограничений на использование связей для передачи информации внутри системы. Получена оценка оптимального размера шага алгоритма локального голосования при таких ограничениях;
-
разработан пакет прикладных программ для моделирования процесса перераспределения заданий разных приоритетов между агентами в мультиагент-
ной сети в условиях случайного изменения связей, помех и задержек в каналах связи.
Научная новизна. Все основные научные результаты диссертации являются новыми.
Теоретическая ценность и практическая значимость. Теоретическая ценность результатов заключается, во-первых, в предложении основанной на алгоритме локального голосования рандомизированной управляющей стратегии для решения задачи дифференцированного консенсуса и получении условий ее работоспособности в мультиагентной системе, обладающей изменяющейся структурой связей, при наличии помех и задержек при передаче данных внутри системы. Во-вторых, в обосновании оптимизации выбора размера шага предложенного алгоритма управления для увеличения производительности системы. В третьих, в представлении рандомизированной управляющей стратегии для решения задачи дифференцированного консенсуса в системе со стоимостными ограничениями на использование связей для обмена информацией между агентами в условиях изменяющейся структуры связей, помех и задержек при передаче данных, в получении условий ее работоспособности и оптимизации ее по размеру шага.
Сформулированная управляющая стратегия может применяться для организации работы децентрализованных вычислительных, логистических, коммуникационных сетей, обладающих разными классами обслуживания, в том числе при стоимостных ограничениях на использование связей внутри сети. В функционирующей по предложенному протоколу системе будет поддерживаться сбалансированный уровень загрузки узлов по всем классам поступающих заданий. Апробация работы. Результаты диссертации докладывались на семинарах кафедры системного программирования математико-механического факультета СПбГУ, на семинаре School of Life Science and Technology of Huazhong University of Science and Technology (December 1-3, 2015, Wuhan, Hubei Province, China), на конференции «XIII Форум университетских партнеров Intel, (Нижний Новгород, 27-28 января, Россия, 2014)» на российских и международных конференциях по оптимизации и теории управления: Шестой и Седьмой традиционных всероссийских молодежных летних школах «Управление, информация и оптимизация» (пос. Григорчиково, Московская обл., Россия, 22-29 июня, 2014; г. Солнечногорск, Московская обл., Россия, 14-20 июня, 2015), XII Всероссийском совещании по проблемам управления ВСПУ-2014 (Москва, Институт проблем управления им. В.А. Тра-
пезникова РАН РАН, 16-19 июня 2014), 2014 IEEE Multi-conference on Systems and Control (October 8-10, 2014, Antibes/Nice, France), IFAC Conference on Modelling, Identification and Control of Nonlinear Systems (MICNON'15) (June 24-26, 2015, Saint-Petersburg, Russia), 14th European Control Conference (ECC'15) (July 15-17, 2015, Linz, Austria), 2015 IEEE Multi-Conference on Systems and Control (MSC'15) (September 21-23, 2015, Sydney, Australia), 3rd IEEE International Conference on Control, Decision and Information Technologies (CoDIT'16), April 6-8, 2016, Saint Julian's, Malta.
Результаты диссертации были использованы в работах по грантам РФФИ 13-07-00250 «Адаптивное управление динамическими системами с использованием рандомизированных алгоритмов», 15-08-02640 «Мультиагентное управление и консенсус в сенсорных, беспроводных и вычислительных сетях», 16-07-00890 «Рандомизированные алгоритмы в автоматическом управлении и при извлечении знаний», ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014-2020 годы» 6.56.1224.2014 «Разработка мультиагентной технологии управления распределенными гетерогенными вычислительными ресурсами для адаптивной балансировки загрузки устройств в реальном времени при решении комплексных вычислительных задач».
Публикация результатов. Основные результаты исследований отражены в работах [1-13]. Соискателем опубликовано 13 научных работ, из которых шесть опубликованы в изданиях, индексируемых в базе данных Scopus, и две в журналах, входящем в перечень рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук
Работы [1-8, 10] написаны в соавторстве. В работе [1] Ю. В. Иванскому принадлежит модификация протокола локального голосования для решения задачи дифференцированного консенсуса при стоимостных ограничениях и моделирование поведения системы, функционирующей по предложенному протоколу, Н. О. Амелиной — общая постановка задачи. В [2] Ю. В. Иванскому принадлежит модификация протокола локального голосования для учета потенциала направления, а соавторам — общая постановка задачи, детализация алгоритмов управления. В статье [8] Ю. В. Иванскому принадлежит описание особенностей мультиагентного подхода к решению задач с использованием вычислительных сетей, соавторам принадлежат описание различных аспектов работы и создания адаптивной мультиагентной ОСРВ. В работах [3, 4, 5, 6, 7, 10] Ю. В. Иванскому принадлежат формулировки
утверждений об оценках на размер окрестности достижения консенсуса, на размер оптимального шага и доказательства этих утверждений, а соавторам — общие постановки задач.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 115 источников. Текст занимает 92 страницы и содержит 8 рисунков.
Протокол перераспределения заданий
В ходе решения широкого круга практических задач, возникающих при сборе информации в сенсорных сетях [88], при распределенных вычислениях [19], управлении роботизированными сетями [67], обмене информацией в многопроцессорных сетях [12], распределении заданий в транспортных сетях [79, 102], распределенном управлении процессами обучения [35], управлении ресурсами на предприятиях [42, 43] и многих других встает задача достижения консенсуса. Задачи достижения консенсуса возникают при роевом управлении [108,111,114], групповом управлении транспортными средствами [112].
В [30] рассматривается задача управления роем динамических объектов на основании согласования значений потенциалов движения объектов внутри роя. Под роем понимается совокупность D динамических объектов ij, (і = 1,.. . , п), решающих задачи из некоторого множества путем взаимодействия. При этом вводятся следующие предположения: Все динамические объекты ij, (і = 1,. .. , п) одинаковы.
Объект di Є D может осуществлять обмен сообщениями с некоторым подмножеством объектов Di Є D, находящихся в пределах некоторой зоны, ограниченной радиусом Л, которую обычно называют «зоной видимости». С помощью такого информационного обмена объекту di может быть доступна информация о состоянии объектов подмножества Di. Объект d{ движется на расстоянии г І ОТ СВОИХ ближайших соседей.
Для решения поставленных задач оператор предоставляет каждому объекту d{ карту потенциалов, определяющую перспективность движения в определенном направлении. Однако, у объектов нет сведений о наличии преград на пути следования. По мере движения у каждого объекта формируется собственная потенциальная картина мира.
Движение каждого объекта d{ характеризуется направлением Si и значением потенциала выбранного пути W{.
Для формирования управления каждый объект роя d{ Є D в момент времени t = О,1,.. . имеет зашумленную информацию о своем собственном направлении движения, усиленным (домноженным) на текущий потенциал своего маршрута: іл і і і,і УІ =9t+ vt 9І = w\s\, и, если D\ т 0, зашумленные наблюдения о направлениях движения соседей, также домноженные на потенциалы маршрутов соседей: где vlt J, vlt 1 — помехи, а 0 lif h — целочисленная задержка, h — максимально возможная задержка. Положим vlt J = 0 и fif = 0 для всех остальных пар (i,j), для которых они не были определены. Так как система начинает работу при t = 0, то неявное требование к множеству соседей: j Є D\ — t — Kf 0. Консенсусное мультиагентное управление, формируемое по протоколу локального голосования задается следующим соотношением: где а - величина шага протокола управления, Т)\ С Dt) bbJ О, Vj Є D\. Положим bhJ = 0 для других пар (i, j). Динамика изменения направления движения объекта описывается разностным уравнением: st+i = st + uti с управлением щ Є R.
Алгоритм локального голосования имеет потенциальное применение при подсчете сумм в задаче опознания со сжатием (compressive sensing) [31] в ходе фазы сжатия исходного сигнала. Значения вещественного одномерного дискретного сигнала конченой длины / из Жа составляют вектор N х 1. Пусть / выражается в некотором ортонормированном базисе где х — вектор коэффициентов x\j], Ф = (01, 02, Фк) — матрица, составленная из базисных векторов. Пусть у — вектор М х 1, полученный в результате измерения /, в результате действия оператора измерения А М х N на вектор /: V = Af.
Предположим, что вектор / представим в виде линейной комбинации s базисных векторов ф и при этом s « N (такой вектор называется s-разреженным). Задача опознания со сжатием (compressive sensing) состоит в проектировании такой матрицы А, чтобы любой s-разреженный вектор размера N мог быть «сжат» до размера М без существенной потери информации; и в проектировании алгоритма восстановления х по сжатому сигналу у [29]. При этом А выбирается случайно по некоторым правилам. Компоненты вектора у при этом могут вычисляться параллельно, независимо друг от друга. По сути операция кодирования / в у представляет собой вычисление суммы компонентов / со случайными весами. В силу природы получения у, измерения может быть представлено взаимодействием агентов по вычислению компонентов у.
Протокол локального голосования может применяться при построении RAID-подобных распределенных систем хранения данных [44]. Пусть в системе из п агентов, і, і = 1,.. . ,n — номер агента, t — время, N = {1,. .. ,п} — множество агентов, хранятся данные, представленные числами. Обозначим х\ , у\ — числа на агенте под номером і в момент времени tk- При вычислении и хранении т видов контрольных сумм от данных на агентах целостность данных будет сохраняться, если в системе данные находятся на (п — т) агентах.
Пусть данные передаются без помех, задержек, и на агентах хранится по одному числу. Расчет контрольных сумм проходит в заданные интервалы времени. В начале интервала происходит вычисление значения целочисленной функции / от числа на агенте и полученное значение сохраняется в заранее зарезервированной области памяти:
Дифференцированный консенсус
Агенты, имеющие каждый свою производительность должны распределить ее среди всех классов заданий таким образом, чтобы, с одной стороны, обеспечить очередность выполнения заданий согласно их приоритетам, а с другой стороны (принимая во внимание «проблему голодания») чтобы задания с низким приоритетом не простаивали «бесконечно», дожидаясь своей очереди на исполнение. Такого поведения можно добиться за счет введения вероятностных приоритетов. Каждому классу заданий поставим в соответствие долю производительности Pki к = 1,... ,т, одинаковую для конкретного класса к для всех агентов. На каждом агенте задания из очередей будем выбирать случайно с вероятностью, задаваемой следующей формулой:
Здесь — вероятность выбора на исполнение агентом і задания класса А; в момент времени t. Таким образом, чем больше Р&, тем выше вероятность выбрать на исполнение задание класса к. Отсюда, производительность агента распределяется между всеми классами заданий следующим образом: (2-і) АЇ = ікРІ Здесь р обозначает число заданий класса к, в среднем выполняемое на агенте і в течение единичного временного интервала. Заметим, что по определению pt , если в момент времени t очередь из заданий класса к на агенте і оказалась пуста, то вычислительные ресурсы агента і , требующиеся для выполнения pt, заданий, будут распределены между другими классами заданий с вероятностями, отношение которых равно отношению долей производительности Pki к ф к для соответствующих классов заданий.
Для всех к = 1 .. .т, = 0,1,... динамика сетевой системы определяется следующим образом: (2-2) qtfc+1 = q"-p" + + utfc, где р = \р1 ], И Z = \z%t } — векторы размерности п, р\ обозначает количество заданий приоритета к, выполненных агентом і в момент времени t, г-й элемент z\ обозначает число новых заданий класса к, поступивших в систему на агента г в момент времени t; щ Є W1 является вектором управляющих воздействий размерности п (состоит из перераспределенных на агентов заданий класса к в момент времени t), который следует выбирать основываясь на информации о длинах очередей на соседних агентах qj. , j Є Щ, где Щ — множество {j Є N : af 0}.
Положим plav ф 0, Vi Є N и Pk ф 0, к = 1,...,ш. В [17] было доказано, что минимальное время работы системы достигается тогда, когда загрузка агентов, определяемая как отношение длины очереди к производительности, равна на всех агентах в сети. Следовательно, важно достичь следующей цели.
Цель управления состоит в том, чтобы поддерживать сбалансированную (равную) загрузку по всей сети для всех уровней приоритета, удовлетворяя при этом требование на ограничение стоимости.
В такой постановке можно решать задачу достижения консенсуса для состояний агентов х\ по каждому уровню приоритета к, где t і,к Pav Для балансировки загрузки сети (чтобы повысить общую производительность сети и уменьшить таким образом время завершения выполнения всех заданий) естественно использовать протокол перераспределения заданий во время работы сети.
Предположим, что для формирования управляющей стратегии и каждый агент і Є N опирается на зашумленные данные о состояниях соседей, которые также могут приходить с задержкой: (2.3) у? к = + ш? \ jeN , где ті 3, — помеха, 0 ctf d — целочисленные задержки, a d — максимально возможная задержка.
В [17, 62] исследуются свойства алгоритма управления, называемого протоколом локального голосования, для задачи балансировки загрузки в стохастической сети. Величина управляющего воздействия протокола локального голосования для каждого агента определялась взвешенной суммой разностей между информацией о состоянии самого агента и информацией о состоянии его соседей.
Рассмотрим следующее семейство протоколов. Определим для каждого к = 1,. .. , т hk _ ,J-,k \ hi,j (ai,j,k _ i,k\ t xt )i где 7 0 — шаг протокола управления, a Щ С Щ — множество соседей узла і (заметим, что можно использовать не все доступные связи, а лишь некоторое их подмножество), bl J — коэффициенты протокола. Используя протокол (2.4), система работает таким образом, что задания одного приоритета распределяются между агентами равномерно. Пусть Bt = [bfJ] — матрица протокола перераспределения заданий в момент времени t. (Положим b%f = О, когда af = 0 или j ф Щ.)
По построению матрицы , соответствующий граф Qst большую часть времени будет иметь такую же топологию, как граф QAV задаваемый матрицей At, или более разреженную. Предположим, что d = 0. Тогда динамика системы с обратными связями, функционирующей по протоколу (2.4), будет иметь следующий вид: Перепишем (2.5) в векторном виде. Определим векторыХ = [xlt }i=i...n, R = [rt ]i=i...n; Zk = \zt ]і=і...п из пространства Мп, и матрицу п х п Wk = [w%t3, ]i,j=i...n- Динамика системы с обратными связями, оперирующей по протоколу (2.4), может быть представлена к векторами и имеет вид: В случае, если d 0 мы «искусственно» добавляем rid новых агентов в имеющуюся топологию сети.
Условия достижимости дифференцированного консенсуса
Рассмотрим пример сети из пяти агентов, соединенных в кольцо. Предположим, что связи между агентами пропадают с вероятностью , а «диагональные» связи могут появляться с такой же вероятностью. Максимальная задержка при информационном обмене d равна 1, вероятность появления задержки равна и одинакова для всех ребер. Пусть в системе присутствуют три различных класса заданий. Доли производительности равны 4 : 2 : 1, то есть при условии, что все очереди непусты, производи тельность агентов будет разделена между классами следующим образом:
На Рис. 3.1 показана зависимость длин очередей заданий qt всех приоритетов на агентах от времени в системе, работающей по описанному протоколу. В примере на агентов поступают задания со сложностью в 1 условную операцию, а производительности агентов равны 1 условной операции за такт.
Длины очередей агентов в примере для трех классов заданий. трех классов заданий сходятся к одному значению, вследствие перераспределения заданий, и уменьшаются, поскольку происходит выполнение заданий и очереди сокращаются. Чем больше доля производительности для класса заданий, тем быстрее уменьшаются соответствующие этому классу состояния агентов, что отражается на графике в виде угла наклона траектории, к которой сходятся длины очередей. «Всплески» траекторий возникают вследствие окончания выполнения системой заданий одного из приоритетов. Как только на одном агенте какая-то из длин очередей становится равна нулю, производительность агента, выделенная под эту очередь, перераспределяется между остальными непустыми очередями агента, и, как следствие, уменьшается его загрузка по другим приоритетам. Получив информацию о новом состоянии агента, его соседи начинают пересылать ему больше заданий соответствующих приоритетов, по которым загрузка агента уменьшилась. Но поскольку по загрузке был достигнут консенсус (с заданной точностью), задания соответствующего приоритета вскоре закончатся и на соседях, и уже агент, в свою очередь, отдаст часть полученных от соседей заданий, поскольку их за грузки выровняются. Со временем агенты снова придут к консенсусу по длинам очередей заданий остальных приоритетов.
Моделирование поведения сетевой системы, выполняющей задания нескольких классов приоритетов, при наличии разных стоимостных ограничений на использование связей для обмена заданиями каждого класса
Рассмотрим сеть из пяти агентов, обладающую топологией, изображенной на Рис. 3.2. Агенты образуют две группы {1, 2} и {3, 4, 5}. Предположим, что связь между агентами пропадает с вероятностью jx. Пусть стоимость связей между агентами внутри групп сравнительно низкая и равна 1, а стоимость связи между группами сравнительно высока и равна 5. Наибольшая задержка при передаче информации по каналам d равна 1, а вероятность появления задержки одинакова для всех связей и равна о- Помехи при передаче данных по каналам связи имеют нормальное распределение с нулевым средним и дисперсией aw = 3. Производительности агентов равны 8, 2, 1, 4 и 10 условных вычислительных инструкций в единицу времени. Количество заданий подчиняется закону распределения Пуассона с параметром Л = 3. Пусть в систему поступают задания двух классов. Доли производительности заданы 2 : 1, то есть на агенте с непустыми очередями производительность агентов будет рас 2 пределена между классами как р и р соответственно. Матрица сетевой топологии А имеет следующий вид:
Заметим, что граф, задаваемый такой матрицей сбалансирован. Пусть на систему наложены следующие стоимостные ограничения: {ck}k=i,2 = {6,1.5}. Стоимостные ограничения для класса 1 выполнены, если матрица управляющего протокола Ваю выбрана равной А. Чтобы удовлетворить ограничениям на задания класса 2, нужно уменьшить интенсивность использования «дорогих» связей 2 - 4 и 4 - 2. Этого можно достичь за счет случайного использования связей с вероятностью ттт. С учетом задержек, расширенная матрица управляющего протокола для приоритета 2 имеет следующий вид:
На рис. 3.3 показано поведение загрузок агентов в описанной системе. Загрузки в нижней части графика соответствуют приоритету 1, и, поскольку для этого приоритета разрешено использовать все связи в любой момент времени, загрузки агентов выравниваются быстрее. Как только агенты завершают выполнение всех заданий приоритета 1, освободившаяся производительность направляется на задания приоритета 2 и загрузка агентов по этому приоритету начинает сокращаться быстрее. Загруз ке агентов по приоритету 2 соответствуют верхние графики. Поскольку использование связей 2 — 4 и 4 — 2 для обмена заданиями между группами {1,2} и {3, 4, 5} ограничено, загрузка выравнивается сначала внутри групп, а затем, по мере обмена заданиями между группами, загрузка выравнивается во всей системе.
При выполнении ограничений A3 на размер шага состояния агентов в системе будут сходиться к консенсусному значению. Однако величина оптимального размера шага управляющего протокола для системы, работающей в различных условиях, будет различной, в связи с чем встает задача выбора оптимальной величины размера шага для повышения производительности системы. Оценим эффективность достижения консенсуса в системе, функционирующей по управляющему протоколу, за временной интервал Т с помощью функционала где F( ,Xo:i,wi) = y t=1 \\Xtj — X W . Xo;/ обозначает вектор начальных состояний агентов, Xt — вектор состояний агентов в момент времени , Х — вектор, состоящий из одинаковых элементов равных среднему значению загрузки агентов по всей системе в момент времени t, wi обозначает помехи. Заметим, что J- одновременно характеризует как скорость сходимости, так и степень сходимости — усредненное отклонение состояний агентов в системе от консенсусного значения.
Моделирование поведения сетевой системы, выполняющей задания нескольких классов приоритетов, при наличии разных стоимостных ограничений на использование связей для обмена заданиями каждого класса
Выше были получены формулы для расчета оптимальной величины шага протокола перераспределения заданий. Для вычисления с их помощью оптимальной величины шага необходимо знать такие параметры функционирования системы, как дисперсия помех или средняя сложность приходящих в систему заданий. На практике такие параметры функционирования системы зачастую неизвестны и, более того, могут меняться со временем. В такой ситуации актуальной становится задача адаптивного выбора размера шага для алгоритма перераспределения заданий. В случае, когда скорость (время) сходимости представляет собой выпуклую функцию от шага алгоритма, выбор оптимального шага сводится к задаче градиентного спуска. В условиях неизвестной целевой функции подбор размера шага может эффективно осуществляться с помощью алгоритма стохастической аппроксимации.
Развитие псевдоградиентных алгоритмов стохастической аппрокси мации рассмотрено в [28]. Алгоритм стохастической аппроксимации (СА) был предложен Роббинсом и Монро в 1951 г. [103], в 1952 в статье Ки-фера и Вольфовица он получил развитие для решения задач оптимизации [89]. В 1954 г. Блюм распространил алгоритм С А на многомерный случай [69]. В традиционной процедуре СА, основанной на аппроксимации вектор-градиента целевой функции, используется по два измерения для приближения каждой компоненты вектор-градиента (2d измерений в случае пространства размерности d). В конце 80-х - начале 90-х гг. XX века Граничиным в [25,26] и Поляком с Цыбаковым в [40,97] были предложены поисковые алгоритмы стохастической аппроксимации с рандомизацией на входе, требующие на каждой итерации всего одно значение (или два значения) целевой функции. Направление при этом, подобно алгоритму случайного поиска [41], выбирается случайно вдоль линии, проходящей через оценку оптимизируемой функции на предыдущем шаге. В англоязычной литературе подобные алгоритмы, получившие название SPSA (simultaneous perturbation stochastic approximation) были предложены Спалом [106,107].
В алгоритмах СА традиционно шаг алгоритма выбирался убывающим до нуля с течением времени. Сейчас активно исследуются возможности применения алгоритмов СА для оптимизации нестационарных функционалов качества [28]. При этом в задачах трекинга (отслеживания дрейфа (изменений) параметров) часто используют неубывающий (постоянный) размер шага (достаточно малый) [20,70,77,78,90,110]. Распределенные асинхронные алгоритмы С А рассматривались в [109]. В [17] алгоритм СА с постоянным размером шага использовался в мультиагент-ных системах для балансировки загрузки узлов вычислительной сети в условиях статистических помех в наблюдениях, переменной топологии и задержек. В [24, 27, 76, 80] показаны применения алгоритма СА для решения задач при почти произвольных помехах.
Зафиксируем возможный интервал изменения размера шага протокола локального голосования [jmin ijmax]- Например, МОЖНО ВЗЯТЬ 7mm = іт,сІеаШВ » max = rndea1 Я Угпгп- РаССМОТрИМ ПОСЛЄДОВаТЄЛЬНЬІЄ Вре менные интервалы длины Т тактов работы системы и перенумеруем их / = 1,2,. ... Для каждого интервала будем выбирать свой размер шага алгоритма и оценивать эффективность работы управляющего алгоритма F[ на интервале / будем по формуле (3-2) Fl = - Y, 1№- 12 t=(l-l)T+l
Типичный вид графиков на Рис. 3.6, 3.7 подсказывает идею о возможном использовании поискового алгоритма стохастической аппроксимации с рандомизацией на входе [28] для адаптации размера шага протокола локального голосования.
Выберем случайно начальное значение % из интервала [jmin ijmax]-Будем пересчитывать размер шага следующим образом. По окончании временного интервала /, / = 1,2,... длины Т оценим эффективность работы F[ управляющего протокола в течение временного интервала по формуле (3.2). Размер шага будем пересчитывать по окончании временного интервала /,/ = 1,2,..., раз в Т тактов работы системы.
Алгоритм адаптации размера шага. 1) Инициализация. Установим значение счетчика итерации алгоритма пересчета оценки размера шага / = 0. Установим счетчик тактов в системе t = 0. Определим допустимый интервал для размера шага [jmin ijmax]- Выберем из интервала начальное значение размера шага 7о и установим оценку размера шага 7/ = 7о- Зададим размер временного интервала Т (число тактов, совершаемых системой за выбранный промежуток времени).