ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Bookmark

Next issue

4
Publication date:
16 December 2020
-->

Algorithms for formation of control actions in a distributed multi-agent systems

The article was published in issue no. № 4, 2010
Abstract:This work considers interaction of rival intellectual agents in distributed multi-agent information processing systems and different mathematic models of their interaction. Algorithms of forming the control actions are listed.
Аннотация:В работе рассматриваются взаимодействие конкурирующих интеллектуальных агентов в распределенных муль-тиагентных системах обработки информации, различные математические модели их взаимодействия. Приводятся алгоритмы выработки управляющего воздействия.
Authors: (msmu_asu@mail.ru) - , Ph.D, (spex19@mail.ru) - , Ph.D
Keywords: rival agents, control action, information processing, information processing system, multi-agent system, information processing system, agent, counter-agent, intellectual agents, algorithm
Page views: 11358
Print version
Full issue in PDF (6.26Mb)
Download the cover in PDF (1.28Мб)

Font size:       Font:

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

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

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

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

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

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

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

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

Равномерное возрастание числа контрагентов

При равномерном увеличении числа контрагентов их общее число в момент t до начала реализации управляющего воздействия и после определяется следующими формулами соответственно:

                (1)

            (2)

Численность агентов A в момент , реализующих управляющее воздействие, определяется формулой

q(t)=a0+a(t–T).                                                      (3)

Из нее можно сделать вывод о времени до полного восстановления работоспособности распределенной системы обработки информации: q(t)=N, откуда

,                       (4)

где  – относительная скорость увеличения численности агентов.

Основной результат, полученный в работе о равномерном возрастании числа контрагентов и агентов, позволяет достаточно точно оценить время стабилизации tстабилизации, такое, что при t>tстабилизации число контрагентов убывает, n(t)

,                 (5)

где  – относительная скорость увеличения численности контрагентов.

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

Пусть система обработки информации опрашивается с частотой ν. По полученному ответу делается вывод о наличии или отсутствии сбоев в ее функционировании. В случае обнаружения сбоя в качестве значения задержки обнаружения T берется худшая оценка:

.                                                                    (6)

Далее производится детальный опрос системы обработки информации с целью определения числа нормально функционирующих компьютеров Nнорм. В качестве значения n(T) также берется худшая оценка:

,                                               (7)

после чего по формуле (1), в предположении, что n0=0, вычисляется скорость увеличения численности контрагентов V:

.                                                   (8)

По формуле (3) можно оценить требуемое значение скорости увеличения численности агентов a, исходя из желаемого времени нормализации работы системы обработки информации Tнормализации (в предположении, что a0=0):

.                                            (9)

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

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

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

Экспоненциальное возрастание числа контрагентов

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

,                           (10)

(11)

В свою очередь, число агентов A подчиняется дифференциальному уравнению

, откуда

.                                                    (12)

Из формулы (12) следует, что время до полного восстановления работоспособности системы обработки информации агентами A определяется условием q(t)=N, откуда

.                                    (13)

Для нахождения времени стабилизации удобно продифференцировать уравнение (11), приравнять его к нулю и ввести новую переменную y:

Учитывая оценку (13) на максимальное значение t, можно сделать вывод, что y£1

В новых переменных уравнение для нахождения времени стабилизации примет вид

,                              (14)

где .

Откуда следует, что

. (15)

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

Задержка обнаружения T вычисляется по формуле (6), число контрагентов n(T) – по формуле (7), после чего из формулы (10), в предположении, что n0=1, вычисляется скорость увеличения численности контрагентов V:

По формуле (13) можно оценить требуемое значение скорости увеличения численности агентов a, исходя из желаемого времени нормализации (в предположении, что a0=1):

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

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

Экспоненциальное возрастание числа контрагентов и равномерное возрастание числа агентов

Особое внимание следует уделить дискриминационному случаю, когда число агентов может возрастать равномерно, а число контрагентов экспоненциально.

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

,                          (16)

а после введения агентов (в момент ) – формулой

 (17)

Число агентов A определяется выражением

q(t)=a0+a(t–T).                                                      (18)

Из формулы (18) следует, что время до полного восстановления работоспособности системы обработки информации будет

,                       (19)

где – относительная скорость увеличения численности агентов.

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

Сделаем замену переменной:

.                                              (20)

Учитывая оценку (19), после преобразования и дифференцирования уравнения (17) получаем следующую оценку:

.              (21)

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

Задержка обнаружения T вычисляется по формуле (6). Число контрагентов n(T) вычисляется по формуле (7), после чего из формулы (16), в предположении, что n0=1, вычисляется скорость увеличения численности контрагентов V:

.                          (22)

По формуле (18) можно оценить требуемое значение скорости увеличения численности агентов a, исходя из желаемого времени нормализации (в предположении, что a0=1):

.                                            (23)

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

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

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

Литература

1.   Шпак Г. Распределенный кластер не уступит «голубому гену»? // Наука в Сибири. 2005. № 34 (2520). С. 3–4.

2.   Приходько М.А. Взаимодействие конкурирующих интеллектуальных агентов в распределенных мультиагентных системах обработки информации при экспоненциальном и равномерном возрастании числа контрагентов // Информатизация и управление: сб. ст. М.: 2010 (отдельный вып. Горного информ.-аналит. бюл.).


Permanent link:
http://www.swsys.ru/index.php?page=article&id=2617&lang=&lang=en&like=1
Print version
Full issue in PDF (6.26Mb)
Download the cover in PDF (1.28Мб)
The article was published in issue no. № 4, 2010

Perhaps, you might be interested in the following articles of similar topics: