Содержание к диссертации
Введение
1 Состояние вопроса. исследование и анализ информационных источников 17
1.1 Общие сведения и определения 17
1.1.1 Мультиагентные системы 17
1.1.2 Механизмы коммуникации в системах распределенных интеллектуальных агентов 26
1.2 Обзор существующих подходов к тарификации абонентов Интернет-провайдеров 29
1.2.1 Тарифы ЮТК 30
1.2.2 Тарифы «Южного Телекома» 31
1.3 Недостатки традиционных подходов к ценообразованию 31
1.4 Постановка задачи динамического ценообразования с помощью мультиагентных систем 32
1.5 Анализ существующих подходов к формированию цены 32
1.6 Метод «умных рынков» 57
1.7 Электронные аукционы 59
1.8 Выбор метода решения задачи перегруженности сетей 65
1.9 Выводы 68
2 Аукцион второй прогрессивной цены 70
2.1 Условия аукциона 71
2.1.1 Оценки агентов 72
2.2 Правило распределения 75
2.3 Анализ игр PSP 78
2.3.1 Предпочтения пользователей 78
2.3.2 Равновесие PSP 79
2.3.3 Эффективность 85
2.4 Алгоритм заявок и сходимость 86
2.4.1 Сходимость в динамической игре 87
2.5 Санкции против неправдивых агентов 88
2.6 Случай предложений с одинаковыми ценами 91
2.7 Информационно-теоретическая основа оценок 97
2.8 Формальная модель агента 101
2.8 Выводы 106
3 Архитектура системы и ее программная реализация ...107
3.1 Логическая структура 107
3.2 Функциональная структура 113
3.3 Объектная модель 115
3.3.1 Агент-покупатель 117
3.3.2 Агент-продавец 123
3.4 Предметная область 125
3.4.1 Распределение полосы пропускания между крупными потребителями 125
3.5 Выбор аппаратных и программных средств реализации 126
3.5.1 Технология Remoting 127
3.6 Выводы 129
4 Тестирование системы 130
4.1 Требования к аппаратному обеспечению 130
4.2 Требования к программному обеспечению 131
4.3 Тестирование мультиагентной системы 132
4.4. Время сходимости аукциона 132
4.5 Симуляция игры в одном узле 135
4.6 Выводы 143
Заключение 145
Список использованных источников 146
Приложение 156
- Общие сведения и определения
- Условия аукциона
- Логическая структура
- Требования к аппаратному обеспечению
Введение к работе
Современные компьютерные системы проделали огромный путь развития от одиночных самодостаточных рабочих станций до глобальных сетей, опутавших весь мир. Дни изолированного программного обеспечения быстро уходят вместе с победным шествием Интернет, WWW, интрасетей и публичных беспроводных сетей. Программное обеспечение проектируется и разрабатывается с учетом сложных информационных магистралей, состоящих из серверов и клиентов, соединенных множеством локальных и глобальных компьютерных сетей. Однако данные сети являются обоюдоострым мечом. С одной стороны, взаимозавязанное программное обеспечение, распределенное на множестве платформ, представляет собой огромную вычислительную мощь, но, с другой стороны, существует угроза катастрофического усложнения процесса разработки и функционирования программного обеспечения, нарастающая вместе с ростом масштабов сетей.
Разрешение проблемы усложнения современных крупных распределенных систем и снижение их сложности призвана осуществить технология «интеллектуальных» агентов (автономных сущностей, выполняющих порученные им задачи). Изучением, конструированием и применением мулътиагентных систем, в которых несколько взаимодействующих интеллектуальных агентов преследуют некоторое множество целей или выполняют некоторое множество задач [126], занимается распределенный искусственный интеллект (РИИ). Это область исследований и прикладных программ, основывающаяся на идеях, концепциях и результатах многих дисциплин, включая искусственный интеллект (ИИ), информатику, социологию, экономику, организацию и науку управления и философию.
Мультиагентные системы могут играть и в самом деле уже играют ключевую роль в существующей и грядущей компьютерной науке и ее приложениях. Современные вычислительные платформы и информационные среды можно охарактеризовать как распределенные, большие, открытые и гетерогенные. Увеличивающаяся сложность компьютерных и информационных систем идет
параллельно с возрастающей сложностью их применений. Эта сложность часто превышает уровень сложности обычных, централизованных вычислений, поскольку требует, например, обработки данных либо находящихся в географически различных местоположениях, либо имеющих большой объем. Для возможности справиться с подобными приложениями, компьютеры должны действовать скорее как рациональные «индивидуумы», нежели просто как «части» системы. Технологии РИИ необходимы для управления высокоуровневыми взаимодействиями и для обработки информации в сложных приложениях [6].
Существует четыре основных метода преодоления проблемы размеров и сложности систем: модульность, распределение, абстракция и интеллектуальность, т.е. большая разумность при поиске и изменении информации. Использование интеллектуальных распределенных модулей комбинирует все четыре эти метода, создавая подход РИИ.
Централизованные системы в общем случае более эффективнее распределенных: все, что возможно вычислить в распределенной системе, может быть перемещено в отдельный компьютер и оптимизировано. Однако распределенные вычисления более доступны для понимания и разработки, особенно в случаях, когда решаемая проблема сама по себе является распределенной. Распределение вычислений может привести к алгоритмам, которые не были бы найдены при централизованном подходе. В некоторых ситуациях централизованный подход невозможен, поскольку системы и данные принадлежат независимым организациям, стремящимся к сохранению приватности своих данных.
В соответствии с подходом РИИ вычислительные агенты должны быть распределены и внедрены во всей системе. При этом агенты могут функционировать как интеллектуальные прикладные программы, активные информационные ресурсы, «обертки» вокруг обычных неинтеллектуальных компонентов, так и в качестве онлайновых сетевых сервисов. Агенты достаточно хорошо осведомлены об информационных ресурсах, локальных для них, и сотрудничают
друг с другом для предоставления глобального доступа и управления этой информацией.
Итак, можно выделить основные преимущества применения мультиа-гентных систем для решения задач обработки и управления распределенной информацией: 1) информация сохраняется приватной и не сообщается в «центр»; 2) агенты производят интеллектуальную обработку информации; 3) агент эффективно управляет локальными для него данными; 4) распределенная мультиагентная система лучше масштабируется при своем росте.
Перечисленные выше преимущества обосновывают применение мультиа-гентной технологии для решения поставленной в диссертационной работе задачи по нивелированию последствий перегрузки коммуникационных сетей.
Коммуникационные сети характеризуются следующими внешними факторами. Ценность, получаемая пользователем от сети, зависит от других пользователей. Понятие положительных внешних факторов включает в себя увеличение ценности сети при подключении к ней большего числа пользователей. Отрицательные внешние факторы обусловлены разделением ресурсов между пользователями, которые в силу расстояний, их числа или «эгоистичности» не в состоянии координировать свои действия в достаточной мере для достижения наиболее желаемого распределения ресурсов. В самом деле, основная проблема в сетях - проблема совместного использования рассредоточенных ресурсов, таких как пропускная способность канала или размер буфера между пользователями
Особенно остро эта проблема встает перед коммуникационными сетями, соединяющимися с глобальными сетями типа Интернет. Параллельно с развитием Интернета эволюционировали и средства доступа к нему, а также скорости подключения. Если, допустим, десятилетие назад модемное подключение по телефонной линии на скорости передачи данных порядка 2 Кбит/с секунд было типичным для конечных пользователей, теперь же полосы пропускания выросли до скоростей порядка нескольких Мбит/с пиковой пропускной спо-
собности. Вместе с полосами пропускания растут и потребности в информационных потоках, так что эффективное распределение подобных коммуникационных ресурсов стало основным для оптимизации производительности всей сети в целом.
Осознание данной проблемы во многих аспектах сетей и распределенных вычислений привело в последние годы к появлению в исследованиях сетей подходов, основанных на теории игр или некооперативных подходов, в таких областях, как контроль потока [37; 68; 69; 70], доступ к каналам [86; 2], расписания [118], маршрутизация [109; 85] и других областях [87; 33; 50]. В широком смысле можно назвать этот подход «сетевыми играми».
Приняв при разработке сетей за основу подход теории игр, возможно разработать механизмы с распределенным интеллектом и механизмом принятия решений, в которых более эффективное и справедливое использование разделяемых ресурсов происходит из динамики игр [7]. Подобный подход приводит к появлению децентрализованных алгоритмов и может играть ключевую роль в масштабируемых архитектурах, которые предоставляют гарантии качества услуг (QoS), «святого Грааля» современных сетей. Игроками в сетях становятся программные интеллектуальные агенты, а не люди. Агенты запрашивают от имени программных приложений (передачи данных, видео, голоса) сетевые ресурсы, такие как пропускные способности каналов. При соответствующих условиях взаимодействия коллективные действия агентов создают распределенный интеллект, который может достигнуть такого же эффективного результата, как и самый лучший централизованный контроллер.
Централизованный контроль над распределением ресурсов часто невозможен из-за многообразия их собственников. В отличие от компьютера, где все ресурсы монопольно управляются операционной системой, большая мультимедийная сеть с QoS слишком сложна и многофлангова, чтобы управляться из одной точки. Так что предположение об эгоистичности пользователей происходит не из-за пессимизма, но из-за понимания того, что технологии и природа не по-
зволяют пользователям быть неэгоистичными. Наконец, при проектировании на сети с применением подхода сетевых игр ключевой момент ценообразования может быть решен с нуля, а не применен к существующей коммуникационной сети постфактум.
Многие ученые считают, что в достижении желаемого потребления ресурсов определяющую роль играет механизм ценообразования, т.е. применение экономического механизма к проблеме оптимального распределения ресурсов. Коммерческие провайдеры услуг Интернет, он-лайн сервисы и даже телефонные компании разрабатывают свои ценовые политики, призванные удовлетворить меняющиеся потребности клиентов и привести к эффективному использованию ресурсов.
Ключевой при таком подходе является возможность потребителей ресурсов свободно обмениваться денежными единицами. Цены, независимо от того, выражены они в «реальных деньгах» в коммерческих сетях или в «игрушечных» (основанных на квотировании) в закрытой системе, играют фундаментальную роль контрольных сигналов для распределения ресурсов. Роль цен становится очевидной, когда спрос на ресурсы сети превышает предложение, т.е. при существовании «перегрузки» [91; 43]. Даже если сетевые ресурсы являются свободным публичным товаром, ценообразование необходимо для увеличения общественной выгоды и эффективного распределения ресурсов, например, частот в беспроводных сетях [105]. В коммерческих сетях вдобавок к контролю за перегрузкой цены играют двойную роль, сигнализируя о необходимости развития инфраструктуры и финансируя ее [61].
Актуальность работы
Централизованные политики ценообразования, принятые, например, в традиционной телефонии, неадекватны в сетях пакетной передачи данных с множеством интегрированных сервисов, где потребности разных пользователей в ресурсах сильно разнятся по количеству и качеству. Под централизованной политикой понимается ситуация, когда отношение между спросом и ценой оп-
ределяется по априорной формуле, даже если уровни реальной цены могут колебаться в зависимости от спроса -ценообразование в зависимости от времени дня в телефонных сетях.
Централизованная политика цен в реальном мире приводит к произвольно установленным ценам. Существует ряд фундаментальных причин, препятствующих оптимальности централизованного подхода. Составитель политики должен знать предпочтения различных пользователей, в то время как отношение между желаемым и полученным количеством ресурсов может разниться в несколько раз для разных пользователей. Во-вторых, централизованный способ подразумевает возможность рассчитать, объективно сравнить и оптимально сбалансировать пользовательские полезности, что в многосервисных, мультимедийных сетях практически невозможно.
Другим полюсом отношений между распределением ресурсов и ценообразованием является современный Интернет. Ресурсы, выделенные для телефонного звонка, фиксированы, и цена их использования основана на предсказуемом общем спросе в любое данное время. В Интернете же общепринятая практика оплаты за максимальную пропускную способность клиентского подключения (плоские цены) отделяет распределение (т.е. реальное потребление) ресурсов от цен. В мультисервисных сетях (ATM, сети Интернет следующего поколения) ни один из этих подходов не жизнеспособен. Первый - поскольку разнообразие программных приложений (включая те, которые адаптируются к доступности ресурсов) делают более сложным предсказание спроса. А второй -потому что у пользователя, заплатившего однажды фиксированную цену, нет мотивов ограничивать свое потребление ресурсов. Это делает потребление подверженным известной «трагедии общедоступности»: когда право на использование определенного ресурса принадлежит множеству субъектов, каждый стремится в наибольшей степени и максимально быстро его использовать, что приводит к стремительному истощению ресурса [65].
В Интернете благодаря встроенному в протокол TCP контролю перегрузки потоки трафика ведут себя кооперативно: они «отступают» перед лицом перегрузки [73]. Однако мультимедийный трафик с менее «дружелюбным» контролем перегрузки (congestion control) занимает все большую долю общего трафика. Для него такое кооперативное поведение без дополнительных стимулов маловероятно. При плоских ценах существует тенденция или к увеличению перегрузки, отсекающей богатых пользователей, или к увеличению цены, которая отсекает бедных [60] и приводит к избыточности сети. Любой из названных сценариев может быть приемлемым в некоторых контекстах [106], и оба могут даже сосуществовать в мире, где сети отделены или разделены на дешевые сети с низким качеством и дорогие сети с высоким качеством. Когда же потребности отдельных пользователей сильно варьируются, статичное разделение ресурсов неэффективнее сетей, пользователи динамически делят между собой все ресурсы.
Насколько остро стоит проблема перегруженности каналов для конечных российских пользователей? Можно утверждать, широкополосный доступ в Интернет по доступной цене начался для них с внедрением технологии ADSL в 1998-1999 г. в Москве и Санкт-Петербурге [71]. До этого, если не считать подключений по выделенным каналам, которые были практически недоступны «домашним» пользователям, самую высокую скорость подключения обеспечивала технология ISDN (64 или 128 Кбит/с), при этом соединение физически шло по обычной телефонной линии.
С того времени ADSL совершил большой скачок вперед. Если первоначально стоимость подключения и абонентская плата были весьма высоки (порядка $600 за подключение, $200 за 1 Гб трафика в месяц и средней стоимости клиентского ADSL модема $800-1000), то сейчас стоимость доступа сократилась на порядок: в Москве, например, по тарифному плану «Нео» [18] подключение на скорости 160 Кбит/с и неограниченным объемом трафика стоит сейчас $24. В Краснодаре пока цены выше. Например, компания «Южный телеком»
берет единоразово 2,5-3 тысячи рублей за подключение, 1400 руб. абоненсткой платы за 1 Гб предоплаченного трафика и 1,3 рубля за каждый мегабайт сверх предоплаченного [17].
Может показаться, что современный пользователь Интернет не имеет проблем с высокоскоростным подключением по приемлемой цене. На самом деле существует целый класс сетей, в которых не гарантируются необходимый уровень качества сетевых ресурсов или требуемая пропускная способность. Примером могут служить так называемые домашние сети [10] - объединенные в сеть компьютеры жильцов одного дома (обычно это большие многоэтажные дома) числом порядка 20-100 пользователей. Подобные сети предоставляют своим клиентам множество услуг, таких как бесплатные игровые серверы, мультимедийные архивы, обмен информацией с другими хостами и, главное, доступ в Интернет. Если учесть, что подобные сети некоммерческие и строятся усилиями энтузиастов, они не могут обеспечить большую пропускную способность каналов.
Даже сети крупных провайдеров с избыточными пропускными способностями каналов не застрахованы от кратковременных периодов перегрузки, возникающих при всплесках активности пользователей (например, в вечерние часы). Перегрузка каналов приводит к ухудшению таких параметров качества сервиса как вероятность потери пакетов, задержка джиттера, задержка передачи между источником и приемником [30].
Как видим, существует необходимость во внедрении новых подходов к контролю перегрузок каналов, основанных на ценообразовании. Из существующих схем ценообразования (таких как приоритетное ценообразование, краевое или ответное) по ряду причин был выбран механизм «умных рынков» и, в частности, механизм аукциона второй прогрессивной цены.
Вместо попыток централизованно и явно рассчитать цены на ресурсы аукцион децентрализует принятия решений, и цена возникает из оценки пользователями (и желания платить) ценности ресурса. Мотивацией для аукционов
является возможность получения лучшего распределения, поскольку тщательное проектирование правил аукциона может усилить коллективную «разумность» пользователей к результату большему, нежели в централизованной системе.
Цель работы
Цель настоящей работы - поиск, анализ и адаптация алгоритма для эффективного распределения между пользователями ограниченных сетевых ресурсов при их перегруженности, реализация его на практике в виде мультиа-гентной системы.
Задачи исследования
Обобщить опыт распределения ресурсов телекоммуникационных сетей между пользователями, способы решения проблемы перегрузки сетей, выявить основные недостатки существующих подходов и пути их преодоления.
Провести анализ алгоритма аукциона «Второй прогрессивной цены» (PSP), особенностей его применения к распределению коммуникационных ресурсов, в частности, пропускных способностей коммуникационных каналов. Выявить его возможные недостатки и найти пути их преодоления.
Провести анализ возможности проведения сетевых игр, в частности аукциона ВПЦ, в мультиагентной системе.
На основе выбранного алгоритма осуществить программную реализацию мультиагентной системы для проведения аукционов по распределению ресурсов.
Провести экспериментальную проверку применимости найденного алгоритма для задачи распределения пропускной способности Интернет-каналов, определить эффективность итогового распределения и скорость сходимости алгоритма к равновесной точке в реальных условиях.
Методы исследования
Поставленные задачи решены с применением распределенного искусственного интеллекта, теории игр, элементов экономической теории, вычислительной математики, методов математического моделирования, объектно-ориентированного программирования и нечеткой логики.
Научная новизна
Теоретическая значимость выполненных в диссертационной работе исследований заключается в поиске и анализе метода эффективного распределения ресурсов телекоммуникационных сетей и состоит в следующем:
осуществлена постановка задачи преодоления проблемы перегруженности Интернет-каналов с использованием механизма «умного рынка» коммуникационных ресурсов;
предложен метод распределения телекоммуникационных ресурсов на электронном аукционе по протоколу «второй прогрессивной цены» с участием программных интеллектуальных агентов;
разработаны и математически обоснованы модификации правила распределения и алгоритма аукциона, доказано сохранение свойств сходимости, устойчи-вости и оптимальности исходного механизма; разработана формальная модель интеллектуального агента; разработана логическая, функциональная и объектная структура мультиа-гентной системы для проведения электронных аукционов «второй прогрессивной цены».
Практическая ценность
Прикладная ценность полученных результатов заключается в создании интеллектуальной системы электронных аукционов между интеллектуальными агентами, представляющими конечных пользователей коммуникационных каналов. Данная система позволяет повысить эффективность (суммарное общественное благосостояние) распределения долей коммуникационных ресурсов ме-
жду пользователями компьютерных сетей по сравнению с общепринятыми подходами и решить проблему возможной перегруженности ресурсов.
Реализация результатов работы
В настоящее время разработанная мультиагентная система реализована на языке С# для среды .NET Framework в виде распределенных программных модулей и используется в Интернет-провайдере ООО «Кубань он Лайн» (г. Краснодар) для распределения Интернет-канала 1 Мбит/с между корпоративными пользователями, подключенными к ее маршрутизатору по Ethernet-каналам;
Апробация результатов исследования
Результаты работы докладывались и обсуждались на: VIII Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (г. Краснодар, 2002 г.);
I Всероссийской научной конференции молодых ученых и студентов «Со
временное состояние и приоритеты развития фундаментальных наук в ре
гионах» (г. Анапа, 2004 г.);
II Всероссийской научной конференции молодых ученых и студентов «Со
временное состояние и приоритеты развития фундаментальных наук в ре
гионах» (г. Анапа, 2005 г.).
Публикации
По теме диссертации опубликовано десять печатных работ, из них пять тезисов докладов на вышеперечисленных конференциях.
Основные положения, выносимые на защиту
Результаты сравнительного анализа существующих подходов к разделению ресурсов в компьютерных сетях при их перегруженности; принципы построения интеллектуальных агентов и мультиагентных систем;
критерии оценки сетевых игр для их использования в мультиагентных системах;
формальная математическая модель аукциона для итерационного распределения коммуникационных ресурсов на произвольные части; модификация правила распределения ресурсов на аукционе «Второй прогрессивной цены» для случая предложений участниками равных цен за единицу ресурса с математическим обоснованием корректности модификации;
модификация аукциона «Второй прогрессивной цены» в виде дополнительного предложения агентов, не получивших запрашиваемую часть ресурса;
логическая, объектная и функциональная архитектура мультиагентной системы и отдельных типов интеллектуальных агентов, составляющих ее; результаты экспериментальной проверки эффективности созданной мультиагентной системы.
Структура и объем работы
Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 156 страницах. -
Работа содержит 22 рисунка, 2 таблицы и библиографический список из 127 наименований на 10 страницах.
В первой главе проводится углубленный анализ отечественной и зарубежной литературы, Интернет-источников, направленный на исследование проблемы перегрузки коммуникационных ресурсов в компьютерных сетях и различных подходов теории игр и распределенного искусственного интеллекта для ее решения. Рассматриваются такие подходы, как «плоское» ценообразование, приоритетное ценообразование, «цены Парижского метро», «умные рынки», краевое ценообразование и др. По набору критериев оценки проведен сравнительный анализ этих подходов, обоснован выбор подхода «умных рынков» и алгоритма второй прогрессивной цены.
Вторая глава посвящена описанию математического обеспечения разрабатываемой мультиагентной системы для распределения коммуникационных каналов на электронном аукционе. Вначале описана оригинальная версия протокола аукциона «Второй прогрессивной цены», правило распределения, ее свойства сходимости в точку равновесия и эффективности равновесного решения. Далее указаны недостатки протокола, предложен способ их устранения и доказано сохранение желаемых свойств аукциона «Второй прогрессивной цены». В конце второй главы приведена разработанная формальная модель интеллектуального агента и ее специализация для применения при проектировании мультиагентной системы.
В третьей главе рассмотрены практические вопросы разработки и создания мультиагентной системы, обоснован выбор программных и аппаратных средств реализации, представлены многоуровневая ролевая, объектная и функциональная структуры всей системы и отдельных составляющих ее интеллектуальных агентов, а также алгоритмы их действий.
В четвертой главе затронуты вопросы обеспечения надежности системы, ее тестирования, измерения производительности. Также приведены результаты экспериментальной работы мультиагентной системы при использовании агентом-аукционистом модифицированной версии алгоритма «Второй прогрессивной цены».
Каждая глава заканчивается краткими выводами, а вся работа - заключением.
Общие сведения и определения
Под агентом понимается сущность, функционирующая в некоторой среде и способная к автономным действиям в ней для выполнения заложенной в агента цели. Агент считается способным воспринимать информацию из внешней ере-ды с ограниченным разрешением, обрабатывать ее на основе собственных ресурсов, взаимодействовать с другими агентами и действовать на среду в течение некоторого времени, преследуя свои собственные цели [19]. В большинстве проблемных областей с достаточной сложностью у агента нет полного контроля над своей средой, в лучшем случае только частичный. С точки зрения агента одно и то же действие, выполненное дважды в одинаковых обстоятельствах, может привести к совершенно различным последствиям, и действие может не достигнуть желаемого эффекта. Так что агенты, кроме самых тривиальных случаев, должны быть готовы к возможности неудачи. Это происходит, если среда является недетерминированной. Обычно у агента существует набор доступных ему действий. Такое множество возможных действий представляет действенные возможности агента: его возможность изменять среду. Не все действия могут быть произведены во всех ситуациях. У действий есть ассоциированные с ними предусловия, которые определяют возможность применения действия в ситуации. Ключевая проблема, с которой сталкивается агент - это решение, какое из действий предпринять, чтобы лучшим образом выполнить свою миссию. Сложность процесса принятия решений может зависеть от различных характеристик среды. Доступная или недоступная Доступная - среда, в которой агент может получить полную, точную, своевременную информацию о ее состоянии. Детерминированная или недетерминированная Детерминированная - среда, в которой любое действие имеет единственный гарантированный эффект. Статическая или динамическая Статическая - среда, остающаяся неизменной, если не считать воздействия на нее агента. В динамической среде могут происходить другие процессы, помимо функционирования агента, и они также влияют на среду. Физический мир -высоко динамичная среда. Дискретная или непрерывная Среда является дискретной, если существует фиксированное, конечное число действий и информации восприятия. Примеры агентов. Любая система контроля может считаться агентом. Простой агент — это, например, термостат. У термостатов есть сенсор для определения температуры в комнате, который размещен прямо в среде (т.е. комнате) и на выходе дает два сигнала: один показывает, что температура слишком низка, другой - что температура в порядке. Термостату доступны два действия: «включить нагреватель» и «выключить нагреватель». Действие «включить нагреватель» обычно производит эффект понятия температуры в комнате, что, однако, не гарантирует эффект - например, если дверь в комнате открыта. Большинство программных сервисов (например, фоновые процессы в ОС UNIX или службы в ОС MS Windows), отслеживающие программную среду и затем предпринимающие действия для ее модификации, тоже являются агентами. Примером может служить программа WinPopup (Windows), которая ждет поступления входящих сообщений и показывает их пользователю. Термостат в предыдущем примере обитал в физической среде, а программа WinPopup действует в программной среде. Она получает информацию о среде, выполняя программные функции (например, вызов функции API ReadFile), а действия, производимые ею, являются программными действиями (смена иконки на экране, отображение окна и т.д.).
Условия аукциона
Решение описанной в работе задачи управления трафиком и предотвращения перегрузки каналов передачи данных средствами теории игр должно отвечать двум требованиям к реализации: должен быть определен процесс обмена сообщениями, делающий возможным выполнение цели по некоторому распределению; и в игре с равновесием по Нэшу правила распределения должны быть разработаны так, чтобы приводить участников игры к равновесию, при котором достигается желаемое разработчиком распределение. Как критерий эффективности разделения ресурсов принимается понятие эффективности по Парето - разделение эффективно по Парето, если выгода одного из участников рынка не может быть увеличена, не уменьшив при этом выгоду других участников. С точки зрения практического применения для выполнения поставленной задачи искомый механизм должен отвечать следующим требованиям: делить ресурс (т.е. коммуникационный канал) на части произвольного размера; позволять динамически перераспределять части ресурса при вхождении в игру новых участников или уходе старых; быстро сходиться к равновесной точке для уменьшения задержек между запросом ресурса и его получением; достигаемые решения игры должны быть оптимальными. Также из-за распределенной природы игры и решаемой ею задачи необходимо стремиться к механизму, где обменные сообщения как можно меньше по размеру, но при этом несут в себе достаточно информации, чтобы ценообразование и выделение ресурсов могло быть произведено без априорного знания о спросе (рыночных исследований и т.д.) и количество централизованных вычислений сведено к минимуму. Рассмотрим алгоритм Progressive Second Price Auction (аукцион второй прогрессивной цены, PSP) [116], алгоритм аукциона для разделения произвольно делимых ресурсов. Требуется показать, что данный алгоритм отвечает всем перечисленным требованиям для решения поставленной задачи. Далее будут исследованы недостатки механизма PSP и предложены способы для их устранения. 2.1 Условия аукциона При заданном количестве Q некоторого ресурса (в нашей задаче этим ресурсом является пропускная способность канала Интернет, предоставляемая пользователям, например, Q = 5 Мбит/с) и набора агентов /= {1,..., N}, аукцион - это механизм, состоящий из агентов, подающих заявки, т.е. заявляющих о своем желании получить часть ресурса по своей цене, которую они готовы за него заплатить и аукциониста, распределяющего ресурс между агентами на основе их заявок. В данном контексте под агентом мы понимаем пользователя или представляющего его интересы программного интеллектуального агента. Алгоритм PSP не уточняет, как именно происходит оплата агентом полученной части ресурса и на какое время она действует. Далее в главе 3 будет показано, что оплата пользования ресурсом производится через списание средств с расчетного счета агента. Заявка /-го агента s, =(q„p,) є St =[0,Q] x[0,a ) означает, что он запрашивает количество ресурса qt по цене за единицу/ ,. Профиль заявки - это s = (s,,...,s,) . Пусть s4 =(si,...,sl_l,sM,...,Sj) , т.е. профиль заявок оппонентов /-го агента, полученный из s удалением st. Когда требуется подчеркнуть зависимость от некоторой заявки агента sh профиль s записывается как (s s.,) [27]. і-й ряд A(s), Ai(s)=(ai(s),ci(s)) - это распределение ресурса агенту /. Он получает количество a-i(s), за что с него взимается плата ct(s). Следует отметить, что р - это цена за единицу (скажем, цена каждый Кбит/с предоставляемого канала), а с - общая стоимость полученной части канала. Правило распределения А выполнимо, если V s и для V/ є І, cii(s) qi (агент не может получить больше, чем запросил), Ct(s) pAi. (агент не должен платить больше, чем он указал в своей заявке). Приведенная выше формулировка - обобщение обычного аукциона. Он является особым случаем, где aw(s)=Q для некоторого победителя w є I и at(s) = О, V/ Ф w, т.е. продажа целого неделимого объекта одному покупателю, для которого теория хорошо разработана [104]. В подходе PSP распределяются произвольные части всего доступного количества ресурса. Это эквивалентно нарезке ресурса на множество частей, каждая из которых продается как отдельный неделимый объект. Например, канал с пропускной способностью 10 Мбит/с делится на лоты по 1 Мбит/с, и каждый лот продается на отдельном аукционе. При практической реализации аукциона разделяемого ресурса это вылилось бы в огромные накладные расходы на коммуникации. Более того, так как пользователи делали бы заявки на покупку некоторого количества таких лотов, аналитическое предсказание ожидаемого дохода может быть неверным ([56, с. 34]).
Логическая структура
Систему как совокупность интеллектуальных агентов можно разбить на несколько логических уровней. Уровень среды выполнения. Сюда включен программный слой поддержки между операционной системой и непосредственным программным кодом разрабатываемой системы. Он предоставляет агентам дополнительные сервисные функции, которые не обеспечены напрямую операционной системой или недостаточны. В качестве базовой среды выполнения агентов создаваемой экспериментальной мультиагентной системы была выбрана среда Microsoft .NET Framework [16; 21]. Она полностью реализована для всех ОС от Microsoft (Windows 98/ME/NT/2000/XP/2003) и предоставляет реальные возможности повторного использования кода, управления ресурсами, многоязыковой разработки, защиты, развертывания и администрирования. Достоинствами .NET Framework при разработке мультагентной системы являются: автоматическое управление памятью (сборка мусора). Одна из самых распространенных ошибок при программировании - невнимательное отношение к освобождению ресурсов типа файлов, памяти, сетевых соединений, ресурсов баз данных и пр., что может привести к некорректному поведению программы в непредсказуемый момент. CLR автоматически отслеживает использование ресурсов, гарантируя, что не произойдет их утечки; работа на нескольких платформах. При компиляции кода для .NET Framework компилятор генерирует код на общем промежуточном языке (common intermediate language, CIL), а не традиционный машинный код. Такая концепция виртуальной машины позволяет переносить среду на различные программно-аппаратные платформы; обширная библиотека служебных классов, являющаяся неотъемлемой частью среды, включает множество сервисных классов, например, классы коллекций, классы для работы с XML-данными, классы для построения распределенных приложений. Транспортный коммуникационный уровень. Он включает в себя построение транспорта для передачи сообщений между агентами, создание возможностей для обнаружения агентов в сети. В идеале системой могут использоваться несколько альтернативных протоколов, которые равнозначны с точки зрения вышележащих протоколов и обеспечивают доставку сообщений между любыми агентами в гетерогенных системах. В современных коммуникационных сетях используется несколько основных транспортных протоколов, которые могут инкапсулировать сообщения агентов, т.е. сообщения третьего уровня. В основе в большинстве случаев используется протокол TCP/IP, который имеет встроенную поддержку маршрутизации сообщений, адресации хостов, фрагментации пакетов, шифрования и прочее. Физическим транспортом для TCP/IP может быть открытая сеть типа Интернет, закрытая типа Интранет или «экстранет», соединяющая агентов по безопасным туннелям через открытые сети. Одним из вариантов передачи сообщений с помощью TCP/IP является разработка собственного формата сообщений, которые передаются через потоки TCP или в датаграммах UDP от агента к агенту. Это наиболее гибкий и мощный способ, однако требует затрат на проектирование, реализацию и тестирование такого протокола. Вдобавок, каждый агент должен иметь в своей структуре модуль работы с этим протоколом, что может быть затруднительным. Более совершенным решением может стать передача сообщений с использованием стандартных протоколов, таких как HTTP или SMTP. Существует множество программных компонентов, реализующих работу с этими протоколами, что повышает эффективность разработки всей системы и дает выигрыш от повторного использования кода. Все перечисленные протоколы могут быть взаимозаменяемыми, т.е. каждый агент работает по тому протоколу, который ему удобнее. Для поддержки такого решения могут быть созданы специальные сервисные агенты, конвертирующие сообщения и отсылающие сообщения адресату в том формате, в котором он их ожидает.
Требования к аппаратному обеспечению
Вопросы обеспечения отказоустойчивости аппаратного обеспечения достаточно изучены и на практике чаще всего реализуются в серверных решениях - дублирование питания, RAID-массивы с зеркалированием, горячая замена модулей памяти и дисков, кондиционирование помещений и др. Главная уязвимая часть системы - это компьютер, на котором выполняется агент-продавец, а также соединение с ограничителем полосы пропускания и биллингом (если он находится на других хостах). Поэтому агент-владелец ресурса должен размещаться на серверном компьютере, отвечающим следующим требованиям: - серверный вентилируемый корпус с резервным блоком питания; - использование модулей памяти с проверкой четности; - подключение к сети через источник бесперебойного питания большой мощности; - подключение к сети через грозоразрядник серверным сетевым адаптером, имеющим запасные порты; - хранение всей информации на отказоустойчивых массивах жестких дисков, подключенных к RAID-контроллеру. Кроме этого, регулярно должно обеспечиваться резервное копирование информации агента на другой компьютер, который в экстренной ситуации сможет выступить в качестве резервного. Общим требованием для всех компьютеров, на которых выполняются агенты системы, является установленная среда .Net любой версии. В настоящее время полноценную поддержку этой среды предоставляют все версии ОС Windows, начиная с Windows 98. Между тем, полноценная работа агента-аукциониста возможна только на серверной ОС в режиме отдельного сервера, включая Windows NT, 2000 и 2003 Server. Практика показывает, что менее трети сбоев в работе программного обеспечения обусловлены ошибками, допущенными разработчиками. Большая часть - совместимость с другими программами, сбои самой операционной системы, драйверов, антивирусного программного обеспечения и т.д. В результате на компьютере агента-владельца должен быть установлен минимум ПО сторонних разработчиков, а неиспользуемые службы ОС должны быть отключены. В связи с регулярными эпидемиями вирусных и других вредоносных программ должны регулярно устанавливаться все свежие обновления ПО (прежде всего операционной системы), а также закрыты все порты TCP, кроме используемого агентом. Тестирование мультиагентной системы проводилось в несколько этапов: 1. отладка во время программирования модулей агентов, постоянная проверка исходного кода; 2. отладка системы на одном компьютере с эмуляцией множества клиентов; 3. опытная эксплуатация системы в реальных производственных условиях при небольшом количестве агентов пользователей (анализ обратной связи между пользователями и агентами); 4. опытная эксплуатация системы в реальных условиях при полной загрузке Интернет-канала и максимальном числе пользователей канала. В данный момент система прошла все перечисленные этапы тестирования. Программные ошибки, найденные на этапах 1 и 2, исправлены, серьезных дефектов в работе системы на этапах 3 и 4 замечено не было, что позволяет сделать вывод об отсутствии в программной системе алгоритмических ошибок. Очевидным является вопрос о соизмеримости времени сходимости с числом участников аукциона. Мы рассматриваем его путем проведения эксперимента с использованием программной системы, описанной в главе 3. Во всех экспериментах пусть Q = 100. Для каждого пользователя оценка ресурса строго возрастающая и вогнута вплоть до максимума, соответствующего физической пропускной способности линии, и далее становится плоской. Так как только вторая производная оценки необходима для измерения эффективности PSP, достаточной признается модель второго порядка (параболическая). Так что используем оценки в форме Сгенерируем популяцию пользователей с независимыми случайными переменными {#/(0)}/ (соответствующими максимальной цене за единицу, которую пользователь готов заплатить), равномерно распределенными в [10,20] и kt = 0/(0)/ , и qti равномерно распределенной в [50,100]. Все агенты имеют бюджет bj = 100. Плата за заявку зафиксирована на уровне є = 5. Каждый агент пользователя может делать не более одной заявки в секунду (см. алгоритм 1).
![Рациональное управление системой психологической помощи на основе медицинского мониторинга и организации психопрофилактического процесса [Электронный ресурс]](/i/i/4409/168295.png "Рациональное управление системой психологической помощи на основе медицинского мониторинга и организации психопрофилактического процесса [Электронный ресурс] Склярова Татьяна Петровна")
