УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК

КОНСТРУКТОРСКО-ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ СИБИРСКОГО ОТДЕЛЕНИЯ РАН

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

АСТРАКОВ СЕРГЕЙ НИКОЛАЕВИЧ

МЕТОДЫ ПОИСКА ЭФФЕКТИВНЫХ РЕШЕНИЙ В РАСПРЕДЕЛЕННЫХ

СИСТЕМАХ

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

Новосибирск – 2014 2

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ГРАФИЧЕСКИЕ ПРЕДСТАВЛЕНИЯ СИСТЕМ

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

ГЛАВА 2. МЕТОДЫ МОДЕЛИРОВАНИЯ ДИНАМИЧЕСКИХ

РЕСУРСНЫХ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ

2.1 Принципы моделирования многосторонних взаимоотношений 2.2 Линейная модель конфликтных взаимодействий 2.3 Моделирование отношений двух коалиций 2.4 Модели коммуникационных сетей 2.5 Однородная модель взаимодействий на полном графе 2.6 Специальные содержательные модели 2.6.1 Конкурентные взаимодействия 2.6.2 Обслуживание коммуникационных сетей 2.6.3 Оптимизация нелинейных технологических процессов

ГЛАВА 3. МЕТОДЫ МОДЕЛИРОВАНИЯ ГРУППОВЫХ

ВЗАИМОДЕЙСТВИЙ В РЕСУРСНЫХ СИСТЕМАХ

3.1 Базовая модель взаимодействий 3.2 Однородная модель оценки отношений 3.3 Неоднородные оценки взаимодействий 3.4 Индивидуальные оценки взаимодействий 3.5 Динамические модели и итерационные процессы 3.6 Модель для двух общих полей взаимодействий 3.7 Общий итерационный алгоритм изменений состояний

ГЛАВА 4. РАВНОВЕСНЫЕ МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЙ

4.1 Рациональные модели распределений 4.1.1 Принципы «справедливости» и критерии распределений 4.1.2 Стратегия равных потерь 4.1.3 Реализация пропорционального распределения при помощи принципа f-равновесия 4.1.4 Системы равновесных функций 4.2 Равновесные стратегии в страховании 4.3 Выводы по равновесным распределениям

ГЛАВА 5. МЕТОДЫ ПРОЕКТИРОВАНИЯ ЭФФЕКТИВНЫХ

ПОКРЫТИЙ ДЛЯ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЕЙ

5.1 Проблемы мониторинга и сенсорные сети 5.2 Модели покрытий для сенсорных сетей 5.2.1 Модели первого уровня 5.2.2. К-модели второго уровня 5.2.3. Модели второго уровня 5.2.4 Классификация регулярных покрытий 5.3 Эффективность покрытий ограниченных областей 5.3.1 Построение типовой функции затрат 5.3.2 Функция затрат для кругового сенсорного покрытия 5.3.3 Оптимизация затрат для моделей третьего уровня 5.3.4 Обсуждение результатов и выводы

ГЛАВА 6. ЭФФЕКТИВНЫЕ ПОКРЫТИЯ ПРОТЯЖЕННЫХ

ОБЪЕКТОВ 6.1. Покрытие полосы кругами одного радиуса 6.1.1 Однослойные покрытия 6.1.2 Двухслойные и многослойные покрытия 6.2. Специальные модели покрытий кругами двух и трех радиусов 6.3 Мониторинг полосы с внешним расположением датчиков 6.4. Общий анализ результатов по сенсорным сетям ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ВВЕДЕНИЕ

Актуальность темы исследования.

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

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

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

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

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

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

1) набором элементов (агентов), имеющих некоторый личный ресурс;

2) структурой связей между элементами, определяющих направления взаимодействий;

3) множеством допустимых распределений ресурса по направлениям взаимодействий;

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

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

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

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

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

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

Во второй части диссертационной работы исследуются модели круговых покрытий, которые непосредственно связаны с проблемами мониторинга пространственных областей с помощью беспроводных сенсорных сетей. Ранее это тематика рассматривалась, в основном, в работах зарубежных авторов: M. Cerdei, G. Potte, L. Wang, J. Wu, H. Zhang, J. Hou, S.

Yang, H. Choo, P. Carmi, M. Katz, A. Clementi, P Wan, I. Akyildiz, H. Hupta, H.

Chen, P. Soreanu, Y. Mao, M. Rahman, H. Chizari, P. Nixon и др. В геометрической постановке каждому сенсору сети можно сопоставить круг окружающего пространства, в котором сенсор способен выполнять контрольные действия или передавать (принимать) сигнал. Задача о покрытии заданной области кругами соответствует задаче мониторинга этой области с помощью сенсорной сети. При этом эффективность покрытия и мониторинга определяется отношением суммарной площади кругов к площади области. Это и есть плотность покрытия, которую при проектировании стараются получить как можно меньше. Результаты высокотехнологичных производственных областях. В данной диссертационной работе предложены новые исследования по данной актуальной теме: рассмотрены новые постановки задач и разработана классификация покрытий.

Степень теоретической разработанности темы. В работах [11, 16, 19, 44, 85, 97] предлагаются и частично исследуются модели оценки взаимоотношений сторон. Исследованию свойств различных развивающихся систем посвящен целый ряд работ [13, 21, 39, 43, 67, 82, 83, 91]. Если известны стратегии элементов системы, то основным направлением исследований является изучение поведения системы в течение времени. В игровых постановках элементы с разными интересами часто называют игроками, а состояние равновесия - равновесием по Нэшу [63, 87, 96, 103]. В экономических системах понятие равновесия является одним из ключевых и ему посвящено множество работ, среди которых отметим [38, 40, 66, 75, 76, 88, 100, 115, 121]. Исследованием равновесных состояний занимаются также при изучении саморазвивающихся систем [41, 46, 98, 104, 110, 113]. Одним из приложений последнего направления является исследование моделей теории конфликтов [12, 20, 26, 33, 53, 102, 114]. Вопросы о нахождения равновесий по Нэшу проводились в работах [24, 69, 96, 105].

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

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

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

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

o Создание алгоритмов и программных материалов, позволяющих проводить численные расчеты для конкретных моделей.

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

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

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

Теоретическая и методологическая основа исследования. Вопервых, это математические модели общего равновесия (Л. Вальрас, В.

Парето, Т. Купманс, К. Эрроу, Ж. Дебре, Р. Раднер, Л. Гурвич, Д. Нэш, Л.

Макензи, Т. Лунберг, Х. Никайдо, Т. Негуши, В.И. Данилов, А.Д. Новиков, А.И. Соболев, С.Л. Печерский, В.И. Опойцев и др.). Во-вторых, это теория социального выбора и рационального поведения (Э. Мулен, Л. Шепли, С.

Шенкер, С. Едлинг, С. Стем, Р. Франк, Д. Грин, М. Олсон, В. Ванберг, И.

Шапиро, М. Фармер, М. Зафировский, В. Культыгин, В. Кокорев, Р. Швери, В. Радаев, Г. Рузавин и др.). Отметим влияние теории игр, которая тесно переплетается с вышеуказанными разделами (Д. Нейман, П. Самуэльсон, Р.Ауманн, Т. Шеллинг, Л. Шепли, Д. Нэш, М. Масчлер, О. Моргенштерн, Р.

Люис, Р. Майерсон, К. Гренджер, Х. Райфа Д. Бьюенен, Р. Гиббонс, П. Янг, Н. Ховард, М.В. Губко, Ю.Б. Гермейер, Н.Н. Данилов, М.А. Шубин, Ю.Н.

Павловский, С.Л. Печорский, А.А. Беляева и др). Кроме того, источником ряда идей послужили исследования по теории систем и системному анализу (Р. Акофф, Л. Берталанфи, У. Черчмен, С. Кунц, С. Донелл, Н. Винер, Д.

Форрестер, Н. Луман, Т. Бернс, Е. Флем, Т. Хюбнер, И. Стенгерс, И.

Пригожин, В.Н. Садовский, В.Г. Афанасьев, В.Д. Могилевский и др.).

Методологической основой разработки новых моделей является теория графов и ее приложения (Л.Р Форд, Д.Р. Фалкерсон, Н. Кристофидес, Р.

Дистлер, К. Берж, М. Свами, О.В. Бородин, А.Д. Плотников, В.П. Попов А.Д. Цвиркун и др.).

Работа опирается также на исследования, посвящённые сходимости итерационных процессов и методам последовательных приближений (Ф.Р. Гантмахер, С.К. Годунов, Д.К. Фадеев, В.Н. Фадеев, В.И.

Крылов, В.В. Бобков, А.А. Самарский, А.В. Гулин, А.М. Мацокин и др.).

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

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

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

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

Основными результатами диссертации, вынесенными на защиту, являются:

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

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

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

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

5. Определение оптимальных моделей мониторинга плоских областей сенсорными сетями, допускающие сенсоры двух и трех радиусов треугольная (серия А) и квадратная (серия В).

6. Разработка приближенного метода определения оптимального количества сенсорных устройств для мониторинга ограниченных областей с учетом стоимости и технической характеристики сенсорных устройств (на примере моделей А-2 и В-2).

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

8. Определение понятия внешнего мониторинга области и построение соответствующих эффективных моделей.

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

В течение 2007-2009 гг. исследования поддерживались совместным российско-индийским грантом РФФИ (проект 08-07-91300-ИНД_а). В 2010гг. получена финансовая поддержка исследований грантом РФФИ (проект 10-07-92650-ИНД_а). В 2013 году получен грант РФФИ (проект 13а) на исследование по теме «Разработка математических моделей и методов оптимизации мобильных беспроводных сенсорных сетей». В Toth G.F. Covering the plane with two kinds of circles // Discrete Comput. Geom., 1995, v. 13, p. 445-457.

государственных академий наук, проводится работа по Проекту I.4.1.5.

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

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

диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2003, 2006, 2012), Всероссийская научно-практической конференции «Информационные оптимизационных задач» (Бишкек, 2004), XIII и ХIV Байкальские международные школы-семинары «Методы оптимизации и их приложения»

(Иркутск-Байкал, 2005, 2008), производстве» (Новокузнецк, 2005, 2007), Научно-методический семинар «Информационно-вычислительные принятия решений» ИВТ СО РАН (Новосибирск, 2007, 2011), Российская (Владивосток, 2007). International Conference «Operations Research and Global Business» (Аугсбург, Германия, 2008), 7-th International Symposium on Modelling and Optimization in Mobile, Ad Hoc and Wireless Networks (Сеул, Корея, 2009), V Азиатская Международная школа-семинар «Проблемы оптимизации сложных систем» (Бишкек, Иссык-Куль, Кыргызстан, 2009), операций» (Новосибирск, 2010, 2013), 11-th International Conference on Computational Science and its Applications (Сантадер, Испания, 2011), 25-th Conference of European Chapter on Combinatorial Optimization (Анталия, Турция, 2012), 21-th International Symposium on Mathematical Programming (Берлин, Германия, 2012), Научный семинар «Дискретные экстремальные задачи» ИМ СО РАН (Новосибирск, 2011, 2012), Научный семинар «Моделирование инфо-коммуникационных систем» ИВМиМГ СО РАН (Новосибирск, 2013).

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Граф есть пара множеств G=(V,E), где E состоит из 2-элементных подмножеств множества V.

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

Мультиграф MG=(V,E) (E допускает кратные 2-элементные подмножества множества V), псевдограф PG=(V,E) ( E допускает кратные ребра и петли) и гиперграф.

Гиперграф есть пара множеств HG=(V,E), где E состоит из заданного набора подмножеств множества V, допускающих кратность.

«связывающие» k-элементные подмножества множества V, k n. Если k 3, то обобщенное ребро нельзя изобразить с помощью линии. Например, для гиперграфа HG4=(V,E), где V={1,2,3,4}, E={e1={1}, e2={1,2,3}, e3={1,2,3,4}, e4={3,4}, e5={4}} имеется два 1элементных ребра e1 и e5, одно 2-элементное e4, одно 3-элементное e2 и одно 4-элементное ребро e3. Вместо ребер элементы E естественнее называть полями, так как соответствующие элементы одновременно взаимодействуют на них. Любой гиперграф, в том числе и HG4, можно задавать таблицей или матрицей инцидентности:

«участника» i на поле j, а нулевой элемент bij матрицы – отсутствие «участника» i на поле j. Сумма элементов в столбце матрицы B определяет число участников соответствующего поля, а сумма элементов строки – степень соответствующей вершины. Представление графа с помощью матрицы смежности удобно только для простых случаев; для гиперграфов такое представление теряет практическую ценность.

поля взаимодействий, а между ними проводятся линии, определяющие присутствие соответствующего элемента на заданном поле (рис. 1.1).

Рис. 1.1. Гиперграф HG4=(V,E), где V={1,2,3,4}, E={e1={1}, e2={1,2,3}, гиперграф HG=(V,E), каждой вершине которого iV присвоен ресурс qi, где Q=(q1, q2, …, qn) – ресурсный вектор системы, n=V.

Для описания свойств ресурсных систем введем обозначения:

• Q = qi общий ресурс системы S;

• Ei = {e j E : i e j } подмножество полей инцидентных элементу i;

• Vij = {v V : {i, v} e j } множество смежных элементов для элемента i на поле ej (все элементы поля ej кроме элемента i);

• Vi = {v V : et E, {i, v} et } множество всех смежных элементов для элемента i (объединение всех Vij по j);

• xij ресурс элемента i на поле e j Ei ; набор всех xij определяет некоторое распределение общего ресурса Q (состояние системы);

Элемент i имеет возможность активно «действовать» своим ресурсом на подмножестве полей e j Ei, сохраняя при этом балансовое соотношение Каждый столбец матрицы X полностью определяет одно элементарное kвзаимодействие, а все столбцы матрицы состояний задают полную систему взаимодействий в данной модели. Если k=1, то на поле этого взаимодействия e j Ei присутствует только один элемент i, поэтому такое поле можно называть внутренним для элемента i.

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

элементов, которая рассматривается как целое;

определена устойчивая структура связей между элементами определяемого ресурсными взаимодействиями между элементами Во второй главе исследуются состояния динамических ресурсных систем, моделируемых графом G=(V,E), n=V, m=E. Динамика системы перераспределениями ресурса после оценки элементами своего текущего состояния.

Пусть каждая вершина i V распределяет свой однородный ресурс в количестве qi по инцидентным ребрам e j Ei. Предположим, что известно начальное распределение ресурса Если система развивается и эволюционирует, то на любом временном шаге k определяется новое распределение xij, k = 0, 1, 2,... :

T0, T1,..., Tk,... это пошаговые требования или управления, связанные со стратегией поведения и целями. Другими словами, управление Tk побуждает систему к изменению и приводит к новому состоянию X k +1.

Определим управление Tk, k=0,1,2,…, позволяющее осуществить переход Для этого зададим систему оценочных функций {cij}, i V, e j Ei, определяющих «полезность» для элемента i на поле ej. Понятно, что функция cij должна зависеть от переменных xij и xsj, s Vij. Заданная система функций позволяет реализовать равновесную стратегию. По этой стратегии каждый элемент i стремится так перераспределить свой ресурс, чтобы выполнялись соотношения:

Далее действуем по равновесному принципу Курно: принимаем новое условно-равновесное решение, основываясь на известной информации предыдущего шага.

Так как элемент i может поменять только свое распределение {xij }, то новое распределение {xij +1} следует получать из соотношений (2.1), заменяя xij на xij +1. Следовательно, получается условие Для конкретных моделей нами будут рассматриваться такие семейства оценочных функций, для которых условие (2.2) на каждом шаге достигается однозначно.

Формально, на каждом шаге k элемент i решает следующую задачу:

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

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

Во второй главе рассматриваются несколько классов функций {cij}, i V, e j Ei. Каждый класс вместе с графической структурой определяет некоторую свою динамическую модель. Все исследуемые модели разобьем на два больших класса: SG и SHG. Группа SG содержит модели со структурой обычных графов G, в которых допускаются петли и ребра без кратных повторений. Группа моделей SHG имеет более сложную структуру, которая задается гиперграфом HG, но не может быть описана с помощью графов G.

Для моделей группы SG два элемента i, j V взаимодействуют на поле e = {i, j} = { j, i} ресурсами xij и x ji, направленными друг на друга. Поэтому оценочные функции cij зависят от двух аргументов: cij = cij( xij, x ji ), j Vi или e j Ei. Очевидно, что множества Ei и Vi отождествляются между собой.

Если же поле задается петлей, то фактически оценочная функция для элемента i определяется одним аргументом: cii = cii( xii, xii ) = cii( xii ).

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

Вид (а) предполагает прямое противостояние и оценивает угрозу для элемента i со стороны «соседа» j. Вид (б) определяет оценку сотрудничества для i-го элемента с элементом j, при этом ресурсы того и другого засчитываются одинаково. Оба вида функций являются частными случаями более общих классов линейных функционалов:

Случай 1 является однородным, так как функция cij( xij, x ji )=a xij +b x ji одинаково для всех элементов оценивает свой ресурс пропорционально a и ресурс «соседа» пропорционально b. Каждый последующий случай обобщает предыдущие варианты и, тем самым, может определять более универсальную модель. Случай 3 имеет максимальное обобщение в классе всех линейных функционалов и имеет возможность различным образом оценивать и свой и чужой ресурс на разных полях.

Сформулируем основные результаты для моделей группы SG.

Пусть задана ресурсная система S на полном графе G=(V,E), V=n>2, в которой последовательность состояний X(k)={x ij ) } определяется системой оценочных функций cij( xij, x ji )= xij x ji, где i V, j Vi. Тогда выполняются следующие теоремы.

Теорема 2.1. Последовательность состояний X(0), X(1), …, X(k),… определяет два предельных состояния: четное X * и нечетное X *, удовлетворяющих соотношениям:

(а) X * = k X(2k)=X*; X * = k X(2k+1)=( X*)T;

(b) предельные элементы матрицы весов X* определяются явно по начальным условиям:

Теорема 2.2. Множество состояний системы S с фиксированными формулам Пусть сеть представлена в виде неориентированного графа G=(V,E), каждая вершина которого iV представляет элемент коммуникационной системы, имеющий ресурс в количестве qi. Весь этот ресурс распределяется по инцидентным ребрам таким образом, чтобы суммарные ресурсы этих ребер были одинаковы.

Обозначим через xij количество ресурса вершины i, выделенного на ребро (i,j) E. Так как на функционирование ребра (i,j) выделяется ресурс как вершиной i, так и вершиной j, то суммарный ресурс ребра (i,j) равен xij + xji. Представляя каждое ребро (i,j) парой дуг (i,j) и (j,i), величины xij и xji будем называть весами этих дуг.

В любой последующий момент времени k=1,2,… каждая вершина iV перераспределяет свой ресурс на основании решения задачи:

где Vi – множество смежных с i вершин, а величины x kji1, jVi на момент решения задачи (2.18) следует считать известными. Таким образом, решение задачи задает стратегию поведения вершин сети в каждый момент времени.

Рассматриваемая модель имеет некоторое преимущество в сравнении с игровыми постановками. Например, в работе2 автор обобщает классические равновесий. Но всегда участник с номером i определяет свою стратегию из области Xi R1. Это ограничивает возможности экономических и технических приложения, так как участнику системы, состоящей из n элементов, иногда приходится определять свои отношения ко всем участникам системы в отдельности, т.е. выбирать стратегию из области Xi Rn-1.

соотношениями:

Смольяков Э.Р. Равновесные модели при несовпадающих интересах участников. – М.: Наука, 1986.

где p ik = x kji, di – степень вершины i.

Соотношениями (2.19) определяется последовательность состояний сети.

диагональная матрица, - матрица, полученная делением i-ой строки матрицы Г на d i. Тогда имеет место следующее утверждение.

Лемма 2.9. В случае не двудольного графа G Теорема 2.7. В случае, когда граф G не двудольный циклические пределы с периодом два для весов дуг существуют и равны:

ei – i-ый координатный орт.

Двудольный граф. Пусть граф G является двудольным. Тогда множество вершин V разбивается на две доли V 1 и V 2, V 1 = n1, V 2 = n2.

соответствующие первой и второй долям. Их строчные суммы равны единице, а количество ненулевых элементов в j-ом столбце равно степени jой вершины. Степень j-ой вершины обозначим через d 1, если j V 1 и через d 2, если j V 2. Пусть Лемма 2.10. В случае двудольного графа G:

Теорема 2.8. В случае двудольного графа G циклические пределы с периодом два для весов дуг существуют и равны:

Следствие 2.7. В пределе на каждой итерации четные x ij и нечетные x ij члены последовательности переходят друг в друга, поэтому состояние, заданное весами x ij = (x ij + x ij ), является допустимым и стационарным.

Рассмотрим однородный случай оценочных функций: cij=c(xij,xji)=axij+bxji. В этом случае мы получаем следующие рекуррентные преобразования:

Приведем ряд утверждений для исследуемой модели.

Лемма 2.11. Для координат вектора стабилизации F(k) выполняется системы.

Лемма 2.12. Для каждого i{1,2,…,n} выполняется следующее где ci = Лемма 2.13. В момент времени k для каждого i{1,2,…,n} выполняется следующее соотношение Теорема 2.11. Для устойчивого поведения вектора стабилизации необходимо и достаточно выполнение условия: