автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Электронные аукционы в мультиагентной системе для управления телекоммуникационными ресурсами

На правах рукописи

Бородин Алексей Александрович

ЭЛЕКТРОННЫЕ АУКЦИОНЫ В МУЛЬТИАГЕНТНОЙ СИСТЕМЕ ДЛЯ УПРАВЛЕНИЯ ТЕЛЕКОММУНИКАЦИОННЫМИ РЕСУРСАМИ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Краснодар - 2006

Работа выполнена в ГОУ ВПО «Кубанском государственном технологическом университете»

Научный руководитель:

Кандидат технических наук, профессор Частиков Аркадий Петрович

Официальные оппоненты:

Доктор физико-математических наук, профессор Лежнев Виктор Григорьевич Кандидат технических наук, доцент Булатникова Инга Николаевна Ведущая организация:

ООО «Южный Телеком»

Защита состоится 14 июня 2006 г. в 14 часов на заседании совета Д 212.100.04 в Кубанском государственном технологическом университете по адресу: 350072, г. Краснодар, ул. Московская, 2, конференц-зал

С диссертацией можно о5накомиться в библиотеке Кубанского государственного технологического университета.

Автореферат разослан 13 мая 2006 г.

Ученый секретарь диссертационного совета _

кандидат технических наук, доцент ~~ A.B. Власенко

Общая характеристика работы

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

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

ситуациях централизованный подход невозможен, посколц^ ЭДЩЙФ^ДОЛЬНАЯ

БИБЛИОТЕКА С.-Петербург

ОЭ Ш^ккМЬ У

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

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

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

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

Особенно остро эта проблема встает перед коммуникационными сетями, соединяющимися с глобальными сетями типа Интернет Параллельно с развитием Интернета эволюционировали и средства доступа к нему, а

также скорости подключения. Если, допустим, десятилетие назад модемное подключение по телефонной линии на скорости передачи данных порядка 2 Кбит/с секунд было типичным для конечных пользователей, теперь же полосы пропускания выросли до скоростей порядка нескольких Мбит/с пиковой пропускной способности. Вместе с полосами пропускания растут и потребности в информационных потоках, так что эффективное распределение подобных коммуникационных ресурсов стало основным для оптимизации производительности всей сети в целом.

Насколько остро стоит проблема перегруженности каналов для конечных российских пользователей? Можно утверждать, чго широкополосный доступ в Интернет по доступной цене начался для них с внедрением технологии ADSL в 1998-1999 г. в Москве и Санкт-Петербурге. Если первоначально стоимость подключения и абонентская плата были весьма высоки (порядка $600 за подключение, S200 за 1 Гб трафика в месяц и средней стоимости клиентского ADSL модема $800-1000), то сейчас стоимость ADSL доступа сократилась на порядок: в Москве, например, по тарифному плану «Нео» подключение на скорости 160 Кбит/с и неограниченным объемом трафика стоит сейчас $24 Может показаться, что современный пользователь Интернет не имеет проблем с высокоскоростным подключением по приемлемой цене. На самом деле существует целый класс сетей, в которых не гарантируются необходимый уровень качества сетевых ресурсов или требуемая пропускная способность. Примером могут служить так на-

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

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

Значительный вклад в развитие теоретических исследований и практических разработок в сфере устранения перегруженности сетей внесли такие зарубежные исследователи как F. Kelly, Н. Jiang, S. Jordan, A.A. Lazar, J. К. Mackie-Mason, J. Murphy, L. Murphy, A. Odlyzhko, T. Sandholm, S. Shenker.

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

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

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

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

Достижение этой цели требует решения следующих основных задач:

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

- проведение анализа алгоритма аукциона «Второй прогрессивной цены» (РБР), особенностей его применения к распределению коммуникационных ресурсов, в частности, пропускных способностей коммуникаци-

онных каналов. Выявление его возможных недостатков и поиск путей их преодоления;

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

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

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

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

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

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

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

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

Реализация результатов работы. В настоящее время разработанная мультиагентная система реализована на языке С# для среды .NET Framework в виде распределенных программных модулей и используется в Интернет-провайдере ООО «Кубань он Лайн» для распределения Интернет-канала 1 Мбит/с между корпоративными пользователями, подключенными к ее маршрутизатору по Ethernet-каналам (акт внедрения прилагается).

Апробация результатов исследования. Результаты работы докладывались и обсуждались на:

VIII Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (г. Краснодар, 2002 г.);

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

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

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

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

Работа содержит 22 рисунка, 2 таблицы и библиографический список из 127 наименований на 10 страницах.

Содержание работы

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

В первой главе проведен обзор и анализ отечественной и зарубежной литературы, Интернет-источников, посвященный исследованиям проблемы перегрузки коммуникационных ресурсов в компьютерных сетях и различных подходов теории игр и распределенного искусственного интеллекта для ее решения. Рассмотрены такие подходы, как «плоское» ценообразование, приоритетное ценообразование, «цены Парижского мегро», «умные рынки», краевое ценообразование и др. Для сравнительного анализа этих подходов использованы такие критерии, как совместимости с существующими техноло! иями, требованиям к измерениям для учета и тарификации, поддержке управления трафиком или контролем перегрузок, предоставлению индивидуальных гарантий (^оЯ, степени сетевой эффективности, степень экономической эффективности, воздействию на социальную справедливость; временным рамкам установления цен. Результаты анализа приведены в таблице 1.

Таблица 1

Критерий Плоское Парижского метро Приоритетное Умные рынки Краевое/ ожидаемой пропускной способности Ответное Эффективной пропускной способности Пропорционально-справедливое

Совместимость IP 1Р, \ТМ 1Р ATM. RSVP ATM, VN ATM ATM, IP

Измерения для биллинга Нет Нет Да Да Да (локально) Да Да (локально) Нет

Контроль перегрузок Нет Да (относительное) Да (относительное) Да (относительное) Да (САС) Да Да (САС) Да

Индивидуальное (ЗоБ Нет Нет Нет Нет Да Частично Да Нет

Сетевая эффективность Низкая Различная Высокая Высокая Высокая Высокая Высокая Высокая

Экономическая эффективность Низкая Различная Высокая Высокая Различная Высокая Высокая Высокая

Социальная справедливость Да Да Нет Нет Да Да Да Да

Временные рамки Длительные Длительные Короткие Короткие Средние/ длительные Короткие Короткие Короткие

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

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

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

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

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

Рассмотрим количество Q некоторого ресурса и набор агентов I = {1, ..., 1}, соревнующихся за него.

<Uf lief

Заявка /-го агента s, = (<7,,/>,)е S, =[О,0]х[о,°о) означает, что он запрашивает количество ресурса q, по цене за единицу р,. Профиль заявки - это

s = (i, . Пусть ^(i, ,...,st.....s!) , т.е. профиль заявок оппонентов

/-го агента, полученный из s удалением s,. Когда требуется подчеркнуть зависимость от некоторой заявки агента s„ профиль 5 записывается как (s,;.?.,).

Распределение в аукционе PSP производится по правилу распределения А,

А:

5 = (<:/,/>) > = (a(j), ф)) Jui

где S = П,е; S,.

i-й ряд А (s), A,(s)=(a,(s),Ci(s)) - это распределение ресурса агенту /. Он получает количество a,(s), за что с него взимается плата c,(s).

Для у > О определено

й 0'. •*-,) =

е-

Правило распределения РБР определено следующим образом:

«,(*) = «шп(<Г,.а(А.О> (О

Для фиксированной характеристики оппонентов s_„ Q,(phs J равно максимальному доступному количеству при цене заявки вр,. Смыслом РБР является принцип исключения-компенсации- сперва ресурс достается иг-

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

Теорема 1: При предположении 1, \/ге I, Ул., е Б.,, такого, что £?, (0, $.,) = 0, для любого е > 0, существует правдивый е-лучший ответ.

При анализе правила аукциона возникает следующая проблема.

Определив

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

Можно указать, что уравнение (3) не верно для случая агентов, указывающих в предложении одинаковую цену за единицу полосы пропускания. Действительно, рассмотрим случай, когда = 100, / = 4, - (60; 4), 52 = (70; 4), = (40; 2) и = (10; 1). В результате имеем с,(5)) = (30,

180), (в2 (■?); с2(5)) = (40; 200) и (а^сМ) = М«); с4(*)) = (0;0). Поскольку

считается очевидным равенство

(3)

имеем

Тогда

Р"'/>(г,5,,№ = 60 * С,(5) .

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

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

Рассмотрим следующий пример, иллюстрирующий эту ситуацию. Пусть (3= 100, / = 2, = (60; 4), 52 = (70; 4), распределение будет Л|(я) = 30 и а2(л') = 40, что приводит к неполному использованию полосы пропускания относительно запрошенного количества. Авторами РБР подчеркивается, что оставшаяся нераспределенная полоса пропускания - только техническое допущение, поскольку пользователи предпочтут изменить свои предложения так, чтобы это не случилось в равновесии

В практических ситуациях агенты постоянно входят в игру и покидают ее, что приводит к частым «переходным» ситуациям. Желательно получить полное распределение полосы пропускания.

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

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

Решить эту проблему предлагается путем модификации и обобщения правила распределения:

а{ (я) = тт

к "Х.Л-**»'

(4)

общая стоимость остается прежней:

сД-о=Е р ,К -О - ; 01 •

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

Для нового правила распределения (4) необходимо показать обоснованность его использования.

Теорема 2. При выборе правила распределения (4) имеет место ра-

Р,(Г,5 ,)<& .

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

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

Теорема 3. Если каждый агент размещает предложение согпасно теореме 1, то невозможна ситуация, при которой несколько агентов

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

В третьей главе рассмотрены практические вопросы разработки и создания мультиагентной системы. Представлены многоуровневая ролевая, объектная и функциональная структуры всей системы и отдельных составляющих ее интеллектуальных агентов, агентов-продавцов, агентов-покупателей, а также алгоритмы их действий. Подробно рассмотрены основные модули агентов. Таковым является модуль принятия решений в агенте, представляющем пользователя ресурсов, который должен моделировать функцию полезности пользователи и ее первую производную. Для этого использован подход нечеткой логики, который позволяет пользователю указывать агенту свои предпочтения правилами вида «ЕСЛИ время = поздний вечер И потребление трафика запущенными программами = выше среднего И важность высокой скорости = незначительна ТОГДА оценка ресурса = невысокая». Для термов лингвистических переменных, таких как «потребление трафика запущенными программами», пользователь сам задает коэффициенты их принадлежности к нечеткому множеству. Работу с правилами, а также фаззификацию/дефаззификацию переменных выполняет библиотека Free Fuzzy Logic Library.

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

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

внедрение на основе краснодарского Интернет-провайдера ООО «Кубань он Лайн» для эффективного распределения полосы 1 Мбит/с между ее потребителями. В силу организационных вопросов канал с большей пропускной способностью предоставлен быть не может, при этом им пользуется большое количество потребителей, что приводит к проблеме постоянной перегрузки канала.

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

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

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

р<

р. -Ь-

чз

41

<-......->

а5 Ч5 с5 -

Рисунок 2 - Эффект снижения стоимости трафика при больших объемах: а5 < «, => с5 /д5 > с4 /а4

Проведены эксперименты на модели с параметрами, близкими к реальным. Выявлен эффект «объемных скидок», при котором агент с большим запросами получает часть ресурса по «оптовым» ценам, более низким, чем менее крупные покупатели пропускной способности (рисунок 2).

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

Основные результаты работы

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

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

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

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

3. Предложена концепция проведения электронного аукциона «Второй прогрессивной цены» в мультиагентной интеллектуальной системе для эффективного распределения ограниченного Интернет-канала между пользователями.

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

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

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

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

Публикации по теме диссертации

Основные положения диссертации изложены в следующих публикациях:

1. А.П. Частиков, A.A. Бородин. Применение протокола голосования в системах распределенных интеллектуальных агентов // Материалы VIII Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». Краснодар, 2002.

2. А.П. Частиков, A.A. Бородин. Анализ современных средств разработки интеллектуальных агентов // Материалы IX Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». Краснодар, 2003.

3. А.П. Частиков, A.A. Бородин. Абстрактные структуры агентов // Труды КубГТУ: Научный журнал. - Краснодар: Изд-во КубГТУ, 2003.

4. А.П. Частиков, A.A. Бородин. Формальная модель аукциона в много-агентной системе и проблемы обучения // Материалы X Юбилейной всероссийской научно-практической конференции «Инновационные процессы в высшей школе». Краснодар, 2004.

5. A.A. Бородин. Экспериментальное обоснование недостатков фиксированных платежей за доступ в Интернет И Труды II Всероссийской научной конференции молодых ученых и студентов. - Краснодар, 2005.

6. А.П. Частиков, A.A. Бородин. Градация интеллектуальности программных агентов // Труды II Всероссийской научной конференции молодых ученых и студентов. - Краснодар, 2005.

7. A.A. Бородин, А.П. Частиков. Проблемы безопасности систем интеллектуальных агентов // Труды I Всероссийской научной конференции молодых ученых и студентов. - Краснодар, 2004.

8. A.A. Бородин, А.П. Частиков Обеспечение надежности систем взаимодействия агентов в многоагентных системах // Труды I Всероссийской научной конференции молодых ученых и студентов. - Краснодар, 2004.

9. А.П. Частиков, A.A. Бородин. Применение объектно-ориентированного проектирования к разработке мультиагентных систем // Труды II Всероссийской научной конференции молодых ученых и студентов. - Краснодар, 2005.

10. А.П. Частиков, А А. Бородин. Применение аукционов в мультиагентных системах для эффективного выделения ресурсов беспроводных сетей // Известия высших учебных заведений. СевероКавказский регион. Технические науки. №4, 2005.

Отпеч ООО «Фирма Гамзд» Зак № 575 тираж 150 экз ф А5, г Краснодар, ул Пашковская 79 Тел 255-73-16

Н21 1 6 8 9

ВВЕДЕНИЕ.

1 СОСТОЯНИЕ ВОПРОСА. ИССЛЕДОВАНИЕ И АНАЛИЗ ИНФОРМАЦИОННЫХ ИСТОЧНИКОВ.

1.1 Общие сведения и определения.

1.1.1 Мультиагентные системы.

1.1.2 Механизмы коммуникации в системах распределенных интеллектуальных агентов.

1.2 Обзор существующих подходов к тарификации абонентов Интернет-провайдеров.

1.2.1 Тарифы ЮТК.

1.2.2 Тарифы «Южного Телекома».

1.3 Недостатки традиционных подходов к ценообразованию.

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

1.5 Анализ существующих подходов к формированию цены.

1.6 Метод «умных рынков».

1.7 Электронные аукционы.

1.8 Выбор метода решения задачи перегруженности сетей.

1.9 Выводы.

2 АУКЦИОН ВТОРОЙ ПРОГРЕССИВНОЙ ЦЕНЫ.

2.1 Условия аукциона.

2.1.1 Оценки агентов.

2.2 Правило распределения.

2.3 Анализ игр PSP.

2.3.1 Предпочтения пользователей.

2.3.2 Равновесие PSP.

2.3.3 Эффективность.

2.4 Алгоритм заявок и сходимость.

2.4.1 Сходимость в динамической игре.

2.5 Санкции против неправдивых агентов.

2.6 Случай предложений с одинаковыми ценами.

2.7 Информационно-теоретическая основа оценок.

2.8 Формальная модель агента.

2.8 Выводы.

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

3.1 Логическая структура.

3.2 Функциональная структура.

3.3 Объектная модель.

3.3.1 Агент-покупатель.

3.3.2 Агент-продавец.

3.4 Предметная область.

3.4.1 Распределение полосы пропускания между крупными потребителями.

3.5 Выбор аппаратных и программных средств реализации.

3.5.1 Технология Remoting.

3.6 Выводы.

4 ТЕСТИРОВАНИЕ СИСТЕМЫ.

4.1 Требования к аппаратному обеспечению.

4.2 Требования к программному обеспечению.

4.3 Тестирование мультиагентной системы.

4.4. Время сходимости аукциона.

4.5 Симуляция игры в одном узле.

4.6 Выводы.

Современные компьютерные системы проделали огромный путь развития от одиночных самодостаточных рабочих станций до глобальных сетей, опутавших весь мир. Дни изолированного программного обеспечения быстро уходят вместе с победным шествием Интернет, 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].

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

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

Цель работы

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

Задачи исследования

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

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

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

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

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

Методы исследования

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

Научная новизна

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

Практическая ценность

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

Реализация результатов работы

В настоящее время разработанная мультиагентная система реализована на языке С# для среды .NET Framework в виде распределенных программных модулей и используется в Интернет-провайдере ООО «Кубань он Лайн» (г. Краснодар) для распределения Интернет-канала 1 Мбит/с между корпоративными пользователями, подключенными к ее маршрутизатору по Ethernet-каналам;

Апробация результатов исследования

Результаты работы докладывались и обсуждались на: VIII Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (г. Краснодар, 2002 г.);

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

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

Публикации

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

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

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

Структура и объем работы

Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 156 страницах.

4.6 Выводы

В главе 4 приведены результаты экспериментальных исследований работоспособности и эффективности интеллектуальной мультиагентной системы.

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

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

Исследована также экспериментально зависимость времени сходимости от размера платы за предложение е и подтверждена их обратная зависимость.

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

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

Заключение

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

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

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

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

3. Предложена концепция проведения электронного аукциона «Второй прогрессивной цены» в мультиагентной интеллектуальной системе для эффективного распределения ограниченного Интернет-канала между пользователями.

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

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

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

1. Бородин А.А. Обеспечение надежности систем взаимодействия агентов в многоагентных системах // Труды I Всероссийсской научной конференции молодых ученых и студентов / А.А. Бородин, А.П. Частиков. Краснодар, 2004.

2. Бородин А.А. Применение аукционов в мультиагентных системах для эффективного выделения ресурсов беспроводных сетей / А.А. Бородин, А.П. Частиков. Известия высших учебных заведений. Северо-Кавказский регион. Технические науки. №4, 2005.

3. Бородин А.А. Проблемы безопасности систем интеллектуальных агентов // Труды I Всероссийсской научной конференции молодых ученых и студентов / А.А. Бородин, А.П. Частиков. Краснодар, 2004.

4. Бородин А.А. Экспериментальное обоснование недостатков фиксированных платежей за доступ в Интернет // Труды II Всероссийсской научной конференции молодых ученых и студентов. Краснодар, 2005.

5. Буч, Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд.; перевод с англ. М.: Изд-во «БИНОМ», СПб.: Невский диалект, 1999 г.

6. Гаврилова, Т.А. Базы знаний интеллектуальных систем / Т.А. Гаврилова, В.Ф. Хорошевский. СПб.: Питер, 2001.

7. Дубров, A.M., Моделирование рисковых ситуаций в экономике и бизнесе / A.M. Дубров, Лагоша Б.А., Е.Ю. Хрусталев. М.: Финансы и статистика, 2000.

8. Маклин, С. Microsoft .NET Remoting. М.: Издательско-торговый дом «Русская Редакция», 2003.

9. Методы интерполирования. http://www-2net.spbstu.ru/NumMetAnterpol/interpolt.html

10. Ю.Милицкий, А. О домашних сетях и пользе арифметики. http://provider.net.ru/article.03.php

11. Навигатор. Тарифные планы, http://navigator.stcompany.ru/tarif.php

12. Нейман, Д., Моргенштерн О. Теория игр и экономическое поведение / Д. Нейман, О. Моргенштерн. М.: Наука, 1970.

13. Остин, Дж. Слово как действие // Новое в зарубежной лингвистике. Вып. 17. Теория речевых актов. — М., 1986.14.0уэн, Г. Теория Игр; перевод с англ. Врублевской И.Н., Дюбина Г.Н., Ляпунова А.Н. М.: Едиториал УРСС, 2004.

14. Петросян, JI. А. Теория игр: Учебное пособие для университетов / Л. А. Петросян, Н. А. Зенкевич, Е.А. Семина. М.: Высшая школа, 1998

15. Рихтер, Д. Программирование на платформе Microsoft .NET Framework /Пер. с англ. -М.: Издательско-торговый дом «Русская Редакция», 2002.

16. СТРИМ. Сравнить СТРИМ. http://stream.ru/compare/

17. СТРИМ. СТРИМ Нео. http://stream.ru/tariffs/neo/

18. Тарасов, В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. -М.: Эдиториал УРСС, 2002.

19. Тоффлер, Б.Э. Словарь маркетинговых терминов / Б.Э. Тоффлер, Дж. Имбер. -М., 2000.

20. Троелсен Э. С# и платформа .NET. Библиотека программиста. СПб.: Питер, 2002.

21. Частиков А.П. Абстрактные структуры агентов // Труды КубГТУ: Научный журнал / А.П. Частиков, А.А. Бородин. Краснодар: Изд-во КубГТУ, 2003.

22. Частиков А.П. Анализ современных средств разработки интеллектуальных агентов // Материалы IX Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» / А.П. Частиков, А.А. Бородин Краснодар, 2003.

23. Частиков А.П. Градация интеллектуальности программных агентов // Труды II Всероссийсской научной конференции молодых ученых и студентов / А.П. Частиков, А.А. Бородин. Краснодар, 2005.

24. Частиков А.П. Применение объектно-ориентированного проектирования к разработке мультиагентных систем // Труды II Всероссийсской научной конференции молодых ученых и студентов / А.П. Частиков, А.А. Бородин. -Краснодар, 2005.

25. Частиков А.П. Применение протокола голосования в системах распределенных интеллектуальных агентов // Материалы VIII Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» / А.П. Частиков, А.А. Бородин. Краснодар, 2002.

26. Частиков А.П. Формальная модель аукциона в многоагентной системе и проблемы обучения // Материалы X Юбилейной всероссийской научно-практической конференции «Инновационные процессы в высшей школе» / А.П. Частиков, А.А. Бородин. Краснодар, 2004.

27. Южный Телеком. Тарифы на ADSL, http://adsl.ugtel.ru/pay.

28. Disel. Тарифные планы, http://diselcom.ru/krasnodar/tarifs

29. NAG.RU. Английские пользователи страдают от перегруженности линий ADSL, http://news.nag.ru/6266.

30. Agorics Technical Report Add004P. Real-time video delivery with market-based resource allocation. Technical report, Sun Microsystem Labs, SunConnect, Ago-rics, Inc., 1994.

31. Algorics, Inc. Going, Going, Gone! A Survey of Auction Types -http://www.agorics.com/Library/auctions.html

32. Altman E. Non zero-sum stochastic games in admission, service and routing control in queueing systems. Queueing Systems, 23, 1996.

33. Anania L., Solomon R. J. Flat: The Minimalist Price. Internet Economics, L. W. McKnight and J. P. Bailey, Eds., Cambridge, Massachusetts, 1997, MIT Press.

34. ATM: История развития, структура и протоколы, коммутационное оборудование, внедрение ATM в сети электросвязи России. Проверка соответствия трафика с помощью алгоритма "дырявого ведра". http://www.wiznet.ru/techn/atm/atm52.htm

35. Basar Т., Olsder G. J. Dynamic Noncooperative Game Theory. Philadelphia: SIAM, Classics in Applied Mathematics, second edition, 1999.

36. Bovopoulos A.D., Lazar A.A. Decentralized algorithms for optimal flow control. In Proc. of the 25th Allerton Conf. On Comm., Control and Computing. University of Illinois at Urbana-Campaign, Oct. 1987.

37. Brown M. Traffic Control HO WTO. http://linux-ip.net/articles/Traffic-Control1. HOWTO/elements.html

38. Clark D. D. Internet Cost Allocation and Pricing. Internet Economics, L. W. McKnight and J. P. Bailey, Eds., Cambridge, Massachusetts, MIT Press 1997.

39. Clarke E.H. Multipart pricing of public goods. Public Choice, 1971.

40. Cocchi R. et al. A Study of Priority Pricing in Multiple Service Class Networks. Proc. Sigcomm '91, Sept. 1991, Oxford University Press.

41. Cocchi R. et al. Pricing in Computer Networks: Motivation, Formulation, and Example. ACM/IEEE Trans. Net., vol. 1, 1993.

42. Cocchi R., Shenker S., Estring D., Zhang L. Pricing in computer networks: Motivation, formulation, and example. IEEE/ACM Trans. Networking, 1(6), Dec 1993.

43. Coordination Methods for Open Distributed Systems. http://www.sics.se/isl/coord/

44. Coucoubetis C. et al. An Intelligent Agent for Optimizing QoS-for-Money in Priced ABR Connections, Telecommunication Systems.

45. Coucoubetis C., Kelly F., Weber R. Measurement-based Usage Charges in Communication Networks. Statistical Laboratory Research Report 1997-19, University of Cambridge, to appear in Operations Research, 1997.

46. Coucoubetis C., Siris V. A. An Evaluation of Pricing Schemes that are Based on Effective Usage. Proc. IEEE Int'l. Conf Communications (ICC '98), Atlanta, Georgia, US A June 1998.

47. Coucoubetis C., Siris V. A., Stamoulis G. D. Integration of Pricing and Flow Control for Available Bit Rate Services in ATM Networks. Proc. IEEE Globecom '96, London, UK, Nov. 1996.

48. DeVries S., Vohra R. Combinatorial auctions: A survey. 2000.

49. Drexler K.E., Miller M.S. Incentive engineering for computational resource management. In B. Huberman, editor, The Ecology of Computation. Elsevier Science Publishers/North-Holland, 1988.

50. Edell R., McKeown N., Varaiya P. Billing Users and Pricing for TCP. IEEE JSAC, vol. 13, no. 7, Sept. 1995.

51. Edell R., Varaiya P. Providing Internet Access: What we Learn from INDEX. Submitted to IEEE Network, Apr. 1999.

52. FIPA Dutch Auction Interaction Protocol Specification -http://www.fipa.org/specs/fipa00032/XC00032E.pdf

53. Fishburn P. C., Odlyzko A. Dynamic Behavior of Differential Pricing and Quality of Service Options for the Internet. June 1998.

54. Free Fuzzy Logic Library, http://ffll.sourceforge.net/

55. Fudenberg D., Tirole J. Game Theory. MIT Press, 1991.

56. Fuzzy Control Language specification. http://www.fuzzytech.com/binaries/ieccd 1 .pdf

57. Gagliano R.A., Fraser M. D., Schaefer M. E. Auction allocation of computing resources. Communications of the ACM 38(6), 1995.

58. Gibbens R. J., Kelly F. P. Resource Pricing and the Evolution of Congestion Control. June 1998.

59. Gong J., Marble S. Pricing common resources under stochastic demand. Preprint -Bellcore, April 1997.

60. Gong J., Spriganesh P. An economic analysis of network architectures. IEEE Network, pp. 18-21, March/April 1996.

61. Groves T. Incentives in teams. Econometrica, 41(3), July 1973.

62. Gupta A. et al., "Priority Pricing of Integrated Services Networks," Internet Economics, L. W. McKnight and J. P. Bailey, Eds., Cambridge, Massachusetts, 1997, MIT Press.

63. Gupta A., Stahl D. O., Whinston A. B. Pricing of Services on the Internet. IMPACT: How ICC Research Affects Public Policy and Business Markets, A Volume in Honor of G. Kozmetsky, F. Phillips and W.W. Cooper, Eds., Quorum Book, CT, MIT Press.

64. HardinG. Tragedy of Commons. Science, 162, 1243-1248, 1968.

65. He M., Leung H.F., Jennings N.R. A fuzzy logic based bidding strategy for autonomous agents in continuous double auctions. IEEE Transactions on Knowledge and Data Engineering, 2002.

66. Honig M. K., Steiglitz K. Usage-Based Pricing of Packet Data Generated by a Heterogeneous User Population. Proc. IEEE Infocom '95, Boston, MA, Apr. 1995.

67. Hsiao M.T.T., Lazar A.A. A game theoretical approach to optimal decentralized flow control of markovian queueing networks with multiple controllers. In Proc. Of Performance 87, Brussels, Belgium, Dec. 1987.

68. Hsiao M.T.T., Lazar A.A. Bottleneck modeling and decentralized optimal flow control II. Individual objectives. In Proc. 19th Annual Conf On Inf. Sci. And Systems, pp 558-563, Baltimore, MD, March 1985. Johns Hopkins University.

69. Hsiao M.T.T., Lazar A.A. Optimal decentralized flow control of markovian queueing networks with multiple controllers. Performance Evaluation, 13(3), Dec. 1991.71.http://www.telemultimedia.ru/telemultimedia/archive/n04/22.html

70. Huberman В., Clearwater S.H. A multiagent system for controlling building environments. In Proc. Of the first International Conf N Multi-Agent Systems (ICMAS-95), San Francisco, CA, June 1995.

71. Jacobson V. Congestion avoidance and control. In Proc. ACMSIGCOMM, 1988.

72. Jiang H., Jordan S. Connection Establishment in High-Speed Networks. IEEE JSAC, vol. 9, no. 7, Sept. 1995.

73. Jiang H., Jordan S. The Role of Price in the Connection Establishment Process. European Trans. Telecommunications and Related Technologies, vol. 6, no. 4, July-Aug. 1995.

74. Kalai E., Lehrer E. Rational learning leads to Nash equilibrium. Econometrica, 61(5), September 1993.

75. Kalyanaraman S., Ravichandran T. Dynamic Capacity Contracting: A framework for Pricing the Differentiated Services Internet. 1st Int'l. Conf. Information and Computation Economics, May 1998.

76. Kelly F. Charging and Accounting for Bursty Connections. Internet Economics, L. W. McKnight and J. P. Bailey, Eds., Cambridge, Massachusetts, 1997, MIT Press.

77. Kelly F. Charging and Rate Control for Elastic Traffic. European Trans. Telecommunications, vol. 8, 1997.

78. Kelly F. Charging and Rate Control for Elastic Traffic. Nov. 6, 1998, presentation given at Nortel Networks.

79. Kelly F. On Tariffs, Policing, and Admission Control for Multiservice Networks. Operations Research Letters 15, 1994.

80. Kelly F. Tariffs and Effective Bandwidths in Multiservice Networks. Int'l. Tele-traffic Conf. ITC 44, 1994.

81. Kelly F., Maulloo A.K., Tan D. К. H. Rate Control for Communication Networks: Shadow Prices, Proportional Fairness, and Stability. Journal of the Operational Research Society 49, 1998.

82. Knapik M., Johnson J. Developing intelligent agents for distributed systems: exploring architecture, technologies and applications. McGraw-Hill, 1998.

83. Korilis Y.A., Lazar A.A., Orda A. Architecting noncooperative networks. IEEE J. Select. Areas Commun., 13(7), Sep. 1995.

84. Kurose J., Schwartz M., Yemini Y. A microeconomic approach to decentralized optimization of channel access policies in multi-access networks. In Proc. 5th Int. Conf. On Distributed Computing Systems IEEE, pp. 70-77, May 1985.

85. Lazar A.A., Orda A., Pendarakis D.E. Virtual path bandwidth allocation in multiuser networks. IEEE/ACM Trans. Networking, 5(6), Dec 1997.

86. Lazar A.A., Semret N. Auctions for network resource sharing. Technical Report CU/CTR/TR 468-97-02, Columbia University, 1997.

87. Mackie-Mason J. К., Varian H. R. Pricing the Internet. Int'l Conf. Telecommunication Systems Modelling, Nashville, TN, USA, March 1994.

88. MacKie-Mason J., Murphy L., Murphy J. Responsive Pricing in the Internet. Internet Economics, L. W. McKnight and J. P. Bailey, Eds., Cambridge, Massachusetts, 1997, MIT Press.

89. MacKie-Mason J.K., Varian H.R. Pricing congestible network resources. IEEE Journal on Selected Areas in Communications, 13(7), Sep 1995.

90. Maille P. Market clearing price and equilibria of the progressive second price mechanism. Technical Report 1522, IRISA, Mar 2003. submitted to RAIRO Operations Research.

91. Maille P., Delenda A. Reserved price in progressive second price auctions.

92. Maille P., Tuffin B. Multi-bid auctions for bandwidth allocation in communication networks. In Proc. IEEE INFO-COM, Mar 2004.

93. Maille P., Tuffin B. The progressive second price mechanism in a stochastic environment. Netnomics, 5(2): 119-147, Nov 2003

94. McAfee R.P., McMillan J. Multidimensional incentive compatibility and mechanism design. Journal of Economic Theory, 46(2), 1988.

95. Merkato Overview, Apr, 2002. http://www.invisiblehand.net/pubdl.php?wpid=6

96. Mitchell B. DSL vs Cable Internet Speed Comparison. "Computing & Technology", http://compnetworking.about.com/library/weekly/aal 11200b.htm

97. Murphy J., Murphy L. Bandwidth Allocation by Pricing in ATM Networks. IFIP Transactions C: Communication Systems, no. C-24, 1994.

98. Murphy J., Murphy L., Posner E. C. Distributed Pricing for Embedded ATM Networks. Proc. Int'l. Teletraffic Congress ITC-14, Antibes, France, June 1994.

99. Murphy L., Murphy J. Feedback and Pricing in ATM Networks. Proc. IFIP TC6 3rd Wksp. Perf. Modelling and Evaluation of ATM Networks, Ilkley, England, July 1995.

100. Murphy L., Murphy J. Pricing for ATM Network Efficiency. Proc. 3rd Int'l. Conf. Telecommunication Systems Modelling and Analysis, Nashville, USA, Mar. 1995.

101. Murphy L., Murphy J., MacKie-Mason J. Feedback and Efficiency in ATM Networks. Proc. IEEE ICC, Ilkley, England, July 1995

102. Myerson R.B. Optimal auction design. Mathematics of Operations Research, 6(1), February 1981.

103. Noam E.M. Taking the next step beyond spectrum auctions: Open spectrum access. IEEE Communications Magazine, 33(12), Dec 1995.

104. Odlyzhko A. The economics of the internet: Utility, utilization and quality of service. Technical report, AT&T Labs Research, 1998.

105. Odlyzko A. A Modest Proposal for Preventing Internet Congestion, Sept. 1997.

106. Odlyzko A. The history of communications and its implications for the Internet. AT&T Labs Research. June 16, 2000.

107. Orda A., Rom R., Shimkin N. Competitive routing in multiuser communication networks. IEEE/A CM Trans. Networking, 1 (5) Oct 1993.

108. Parris C., Ferrari D. A Resource-based Pricing Policy for Real-time Channels in a Packet-switching Network. Int'l. Сотр. Science Institute, Berkley, Technical Report tr-92-018,1992.

109. Rosenschein J.S., Zlotkin G. Rules of Encounter. MIT Press, 1994.

110. Sandholm T. An algorithm for optimal winner determination in combinatorial auctions. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence. Stockholm, 1999.

111. Sandholm T. Limitations of the Vickrey Auction in Computational MultiAgent Systems. In Proceedings of ICMAS-96, 1996.

112. Sandholm T. Negotiation Among Self-interested Computationally Limited Agents. PhD thesis, University of Massachusetts, Amherst, 1996.

113. Schuster G.M., Katsaggelos A.K. Rate-Distortion Based Video Compression. Kluwer Academic Publishers, 1997.

114. Semret N. Market Mechanisms for Network Resource Sharing, Ph.D. thesis, Columbia University, 1999.

115. Shenker S. et al. Pricing in Computer Networks: Reshaping the Research Agenda. ACM Computer Communication Review, 1996.

116. Shenker S. Making greed work in networks: A game-theoretic analysis of switch service disciplines. In Proc. ACMSIGCOMM, 1994.

117. Siris V. A. et al. Usage-based Charging using Effective Bandwidths: Studies and Reality. 16th Int'l. Teletraffic Congress (ITC-16), Edinburgh, UK, June 1999.

118. The POPCORN project: Global Distributed computation over the internet in Java, http://www.cs.huji.ac.il/labs/popcorn/

119. Theory of Data Compression, http://www.data-compression.com/theory.shtml

120. UMBC KQML Web http://www.cs.umbc.edu/kqml/

121. Using Intelligent Agents to Implement an Electronic Auction for Buying and Selling Electric Power http://www.agentbuilder.com/Documentation/EPRI/

122. Waldspurger C.A., Hogg Т., Huberman В., Kephart J.O., Stornetta W.S. Spawn: A distributed computational economy. IEEE Transactions on Software Engineering, 18(2), 1992.

123. Walrand J., Varaiya P. High-performance Communication Networks, Morgan Kaufmann, New Jersey, USA, 1st edition, 1996.

124. Weiss G., ed. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. MIT Press, Cambridge, MA, 2000.

125. Председатель комиссии: Члены комиссии:технический директор Лихоткин А.В., системный администратор Лебедь И.Н.

126. Председатель комиссии: Технический директор1. А.В. Лихоткин

127. Члены комиссии: Системный администратор1. И.Н. Лебедь