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

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

АСТРАКОВ Сергей Николаевич

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

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

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

IО ФЕБ 2014

Иркутск - 2014

005545244

Работа выполнена в Федеральном государственном бюджетном учрежден науки Конструкторско-технологическом институте вычислительной техни Сибирского отделения Российской академии наук.

Научный консультант: доктор физико-математических наук

Голушко Сергей Кузьмич, КТИ ВТ СО РАН, директор

Официальные оппоненты: член-корреспондент РАН

Федотов Анатолий Михайлович, ИВТ СО РАН, зам. директора

Ведущая организация: Институт вычислительной математики

и математической геофизики СО РАН

(г. Новосибирск)

Защита диссертации состоится 24 апреля 2014 г. в 14.00 на заседай диссертационного совета Д 003.021.01 в Федеральном государственно бюджетном учреждении науки Институте динамики систем и теор управления Сибирского отделения Российской академии наук (ИДСТУ С РАН) по адресу: 664033, г. Иркутск, ул. Лермонтова, 134.

С диссертацией можно ознакомиться в библиотеке и на официальном сай www.idstu.irk.ru ИДСТУ СО РАН.

Автореферат разослан 10 февраля 2014 г.

доктор технических наук, Горнов Александр Юрьевич, ИДСТУ СО РАН, гл. научн. сотрудник

доктор физико-математических наук Хамисов Олег Валерьевич, ИСЭМ СО РАН, зав. отделом

Ученый секретарь диссертационного совета, кандидат физико-математических наук

Т.В. Груздев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

В диссертационной работе исследуются также модели круговых покрытий, которые непосредственно связаны с проблемами повышения эффективности мониторинга пространственных областей с помощью беспроводных сенсорных сетей. Это напрямую связано с вопросами экономии затрат, поиском оптимальных структур расположения сети датчиков и временных режимов их работы. Ранее это тематика рассматривалась, в основном, в работах зарубежных авторов: М. 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 и др. В геометрической постановке каждому сенсору сети можно сопоставить круг окружающего пространства, в котором сенсор способен выполнять контрольные действия или передавать (принимать) сигнал. Задача о покрытии заданной области кругами соответствует задаче мониторинга этой области с помощью сенсорной сети. При этом эффективность покрытия и мониторинга определяется отношением суммарной площади кругов к площади области. Это и есть плотность покрытия, которую при проектировании стараются уменьшить. Результаты исследований сенсорных сетей широко востребованы в высокотехнологичных производственных областях. В данной работе рассмотрены новые постановки задач и разработана классификация покрытий.

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

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

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

равновесным состояниям систем, о Проектирование эффективных систем мониторинга пространственных областей и объектов на основе беспроводных сенсорных сетей.

1 Dolev S., Schiller Е. Self-Stabilizing Group Communication in Directed Networks // Proc. of 6th International Symposium «Self-Stabilizing Systems». San Francisco (USA), 2003. P. 61-76.

4

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

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

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

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

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

Практическая и теоретическая значимость. Работа имеет теоретический характер, однако полученные результаты могут служить методической основой для разработки тарифных планов, определять стратегию экономического сотрудничества, находить эффективные технические решения при мониторинге объектов и оптимизации коммуникационных систем. Отдельные результаты диссертации были использованы в Программе фундаментальных научных исследований государственных академий наук по Проекту 1.4.1.5. «Математическое моделирование и вычислительные технологии в задачах принятия решений по управлению технологическими процессами предприятий нефтегазового и горнодобывающего комплексов и других сложных объектов» (№ гос. регистрации 01201154503). В течение 2007-2009 гг. исследования были поддержаны российско-индийским грантом РФФИ (проект 08-07-91300-ИНД_а), в 2010-2012 - грантом РФФИ (проект 10-07-92650-ИНД_а). В 2013 году получен грант РФФИ (проект 13-07-00139_а) на исследование по теме «Разработка математических моделей и методов оптимизации мобильных беспроводных сенсорных сетей».

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

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

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях: Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2003, 2006, 2012), Международный семинар «Вычислительные методы и решение оптимизационных задач» (Бишкек, 2004), XIII и XIV Байкальские международные школы-семинары «Методы оптимизации и их приложения» (Иркутск-Байкал, 2005, 2008), Всероссийская научно-практическая конференция «Системы автоматизации в образовании, науке и производстве» (Новокузнецк, 2005, 2007), Российская конференция «Дискретная оптимизация и исследование операций» (Владивосток, 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). Кроме того, результаты диссертации докладывались и получили положительную оценку на следующих представительных семинарах: «Дискретные экстремальные задачи» (Институт математики СО РАН, 2012, 2013); «Информационные технологии» (Институт вычислительных технологий СО РАН, 2011, 2012, 2013), «Моделирование инфо-коммуникационных систем» (Институт вычислительной математики и математической геофизики СО РАН, 2013), «Дифференциальные уравнения, управление и системный анализ» (Институт динамики систем и теории управления СО РАН, 2013).

Публикации и личный вклад. По теме диссертации автором опубликованы монография и 34 печатные работы, в том числе 13 статей [2-14] из журналов, рекомендованных ВАК для опубликования основных результатов докторских диссертаций. Все выносимые на защиту результаты получены соискателем лично. В совместных работах вклад соискателя является значимым: ему принадлежат постановки задач, основные идеи доказательств теорем и утверждений, построение алгоритмов и расчеты оптимальных параметров. Конфликт интересов с соавторами отсутствует.

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

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

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

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

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

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

Мультиграф МС=(У,£) (Е допускает кратные 2-элементные подмножества множества V), псевдограф РС = (У,Е) (Е допускает кратные ребра и петли) и гиперграф.

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

Элементы множества Е называют обобщенными ребрами, «связывающими» ¿-элементные подмножества множества V, к<п. Если к > 3, то обобщенное ребро нельзя изобразить с помощью линии. Например, для гиперграфа НС^ = (V, Е), где V = {1,2,3,4}, Е = {{<?, = {1}, е2 = {1,2,3}, е3 = {1,2,3,4}, е4 = {3,4}, е5 = {4}}, имеется два 1-элементных ребра е\ и , одно 2-элементное , одно 3-элементное е^ и одно 4-элементное ребро е3. Вместо ребер элементы Е естественнее называть полями, так как соответствующие элементы одновременно взаимодействуют на них. Любой гиперграф, например ЯС4, можно задавать матрицей инцидентности

'1110 0" 0 110 0

В =

0 1110 ч0 0 1 1 1,

Единичный элемент Ьу матрицы В показывает присутствие «участника» / на

поле }, а нулевой элемент Ъц матрицы - отсутствие «участника» I на поле у. Сумма

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

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

Рис. 1.1. Гиперграф ЯС4 = (У,Е), где £ = {{£>, = {1},е2 = {1,2,3}, е3 = {1,2,3,4}, е4 ={3,4}, е5 = {4}}

Определение. Ресурсная система 5 = (У ,Е,0) - это взвешенный гиперграф Нй = {у ,Е), каждой вершине г'е V которого присвоен ресурс qi, где (2 = (д1уд2,...,дп) - ресурсный вектор системы, /г = |У|.

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

П

• - общий ресурс системы 5;

• Е{ = {ej е Е: ieej} - подмножество полей, инцидентных элементу г;

• у — {уе V : {г,у} с: е]} - множество смежных элементов для элемента I на поле (все элементы поля кроме элемента г);

• V,- = {уе У : е Е, {/,у}се,} - множество всех смежных элементов для элемента г (объединение всех У,у по /);

• Ху - ресурс элемента г на поле е^ € Е[; набор всех хи определяет некоторое распределение общего ресурса (2 (состояние системы);

Х =

- матрица состояния системы 5 .

Элемент I имеет возможность активно «действовать» своим ресурсом на подмножестве полей е. е Е1, сохраняя при этом балансовое соотношение

<7(. = ^ х:] (сумма элементов строки матрицы X ).

Каждый столбец матрицы X полностью определяет одно элементарное к-взаимодействие, а все столбцы матрицы состояния задают полную систему взаимодействий в данной модели. Если к = 1, то на поле этого взаимодействия е 1 е присутствует только один элемент /, поэтому такое поле можно называть

внутренним для элемента г.

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

• система состоит из множества связанных между собой элементов и рассматривается как единое целое',

• определена устойчивая структура связей между элементами системы,

• задана форма существования системы в виде состояния, определяемого ресурсными взаимодействиями между элементами или подмножествами.

Во второй главе исследованы состояния динамических ресурсных систем, моделируемых графом С = (У,£'), и = |У|, ш = |£'|. Динамика системы - это последовательность состояний, которые определяются перераспределениями ресурса после оценки элементами своего текущего состояния.

Пусть каждая вершина /е V распределяет свой однородный ресурс в количестве qi по инцидентным ребрам е.^Ег Предположим, что известно начальное распределение ресурса

г(0). „ - 2>(0)

е^Е,'

Если система развивается и эволюционирует, то на любом временном шаге к определяется новое распределение , к= 0, 1, 2, ... :

[Г0]-> -> [г,]-> х2 -> [г2]->... -> [г, ]-»... ,

где Хр,^!, —,Хк> ... - это последовательные состояния системы, а 7о,71,...,7^,... - это пошаговые требования или управления, связанные со стратегией поведения и целями. Другими словами, управление Тк побуждает систему к изменению и приводит к новому состоянию Хк+1.

Определим управление Тк, к = 0, 1, 2, ... , перехода

Для этого зададим систему оценочных функций {сц}, /е V, е] е £,

определяющих «полезность» для элемента I на поле ег Понятно, что функция сц

(к} (к)

должна зависеть от переменных ' и , 56 Уу. Заданная система функций

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

Ч = с<;\ = ••• = Ч ' где ек • еЛ ' е1 е Е' ■ (2.1)

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

Поскольку элемент I может поменять только свое распределение [х^},то новое распределение следует получать из соотношений (2.1), заменяя х^

на . Следовательно,

сМк+1)'^)= соп51 . (2-2)

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

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

Тк

11 " е^Ё'^У: (2.3)

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

Во второй главе рассматриваются несколько классов функций {с,у},

ге V, е) е Е1. Каждый класс вместе с графической структурой определяет

некоторую свою динамическую модель. Все исследуемые модели разбиваются на два больших класса: % и Бнс. Группа БСг содержит модели со структурой обычных графов С, в которых допускаются петли и ребра без кратных повторений. Модели группы Бнс имеют более сложную структуру, которые задаются гиперграфами НС, но не могут быть описаны с помощью графов С.

Для моделей группы два элемента у 6 V взаимодействуют на поле

е - {(, ]} = {у,(} ресурсами хц и х]1, направленными друг на друга. Поэтому оценочные функции с,у зависят от двух аргументов: с,у = с,у(у е V,, или е - е Е1. Очевидно, что множества и V,- отождествляются между собой. Если же поле задается петлей, то фактически оценочная функция для элемента г определяется одним аргументом сц{хц,хн)-сц{хц). Следовательно, состояние

системы задается квадратной матрицей X порядка п.

В ранних работах использовались два вида простых функций:

(а) с,у (*,у, хр) = хц - ху,-, где г е У, у е ;

(б) с,у(хц,хп) = хц + хп, где г'е V, у'е V; .

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

1. с,у (дг,у,хр) = ахц + Ъхр, где а,Ь<= Я; / е V, у е V.;

2. Сц(хц,хр) = а1хц+Ь1хр, где а^Ь^ е Л; ; е V, У е V,;

3. Си(хи,хл) = ацхц+Ьцхц+С1ц, где ац, Ьц, йц € Л ; 1еУ, ]еУг

Случай 1 является однородным, так как функция Сц (дг,у, Хр) = ахд + Ьх^

одинаково для всех элементов оценивает свой ресурс пропорционально а и ресурс «соседа» пропорционально Ъ. Каждый последующий случай обобщает предыдущие варианты и, тем самым, может определять более универсальную модель. Случай 3 позволяет различным образом оценивать и свой, и чужой ресурс на разных полях. Сформулируем основные результаты для моделей группы Б а. Пусть задана ресурсная система 5 на полном графе С = (1/,£), и=|У|, в

которой последовательность состояний определяется системой

оценочных функций сц (х^, х;(-) = х,у - х;,-, где г е V, ]е К.. Тогда справедливы следующие результаты.

Теорема 2.1. Последовательность состояний

* *

определяет два предельных состояния: четное Хе1,еп и нечетное X , удовлетворяющих соотношениям:

(a) Х1а=ШХ™ = X', Х'ш=\шгХ<и+" =(*У;

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

V,,

п(п- 2) п(п-2)

1 ( Л 1 ( 4

1 I х-1 ш) ^ гт I /-гт А V гт х—1 (О)

где r^ Ii-E^ 1Г-—7 К1"!^

n — l\xV, reV, J П — 1 ^JeV, seV,

Теорема 2.2. Множество состояний системы S = (V ,E,Q) всегда имеет устойчивое состояние X — + (Х*)Т), которое вычисляется по формулам

x^-ixf' + xf)--— (Л0)+/Г), iev, jeVr

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

Обозначим через количество ресурса вершины г, выделенного на ребро (г, j)e Е. Поскольку на функционирование ребра (г, j) выделяется ресурс как вершиной 1, так и вершиной j, то суммарный ресурс ребра (i, j) равен х^ + Xß. Величины Ху и Xß будем называть весами дуг (i,j) и (у, г)

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

min (х(к) +x(t"1)) max;

jeV, U Jl (j*)

*Г= о; *?>=а «.лев, (2Л8)

jzv,

„(*-1)

] е V,-, на момент

где V, - множество смежных с 1 вершин, а величины Хр

решения задачи (2.18) следует считать известными.

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

всегда участник с номером I определяет свою стратегию из области X,- с Л1. Это ограничивает возможности применения модели в экономических и технических приложениях, так как участнику системы, состоящей из п элементов, иногда приходится определять свои отношения к каждому участнику системы в

отдельности, т.е. выбирать стратегию из области X,- с Я

п-1

Процесс изменения весов дуг определим рекуррентными соотношениями:

(*+1) _ ,-(*) хи

~ и II '

} г .

4

V Ц,Ле Е-, хФ =0, V (/,у)е Е, (2.19)

где р\ = ' - степень вершины I.

Соотношениями (2.19) определяется последовательность состояний сети. Пусть Г - матрица смежности графа О, й = diag{dl,...,dn} - диагональная матрица, А - матрица, полученная делением /-ой строки матрицы Г на <11. Тогда имеют место следующие утверждения.

Лемма 2.9. В случае не двудольного графа С

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

*г = = + Г'О{Е- (Д - Ь)2У - /'°'О{Е - (д—ь)2)1

. е е' А---

V 4 ¿и

Д—- —

й. а,

22

где /<0) = (/,<0),..., /„<0>А Е - единичная матрица, е - 1-ый координатный орт,

Ь = -

¿г ¿1 ¿2

А ¿2

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

Пусть теперь граф С является двудольным. Тогда множество вершин V разбивается на две доли К1 и V2, | V11 = щ, | У2| = и2 . Введем матрицы Д[ е М, Д2 6 М„2ХП1, аналогичные матрице А, но соответствующие первой и второй долям. Их строчные суммы равны единице, а количество ненулевых элементов в у'-м столбце равно степени у'-й вершины. Степень у-ой вершины обозначим через ,

если у е V1, и через если у е V2. Пусть = ; бй =

jA jft

d 1

jA >

s M.

h = l,2; A' =

Д,Д

1^2 '

Д7Д

2^1

Лемма 2.10. ß случае двудольного графа G

если ieV', то lim//2t) = lim//"+,)

ß2

еслг^К2, то Нт/(Ш=^; Ит/.("+,)

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

*Г = !й2 x™=xl°>+fmD(E-A') x'f1 = Iimi;2-'" = -х';:> - fm)D{E - А')

г

d

е'

~dj)

е'

4) sk

h=l,2.

гоМ

Следствие 2.7. В пределе на каждой итерации четные х^еп и нечетные члены последовательности переходят друг в друга, поэтому состояние,

заданное весами ху = [х^'еп + ) , является допустимым и стационарным.

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

x\f+l) = oa i = у;

ie {1,2,..., и}, у-{1,2,..., 4

(2.20)

г'е {1,2,..., и}.

и —а )

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

13

Лемма 2.11. Для координат вектора стабилизации Т7^ выполняется

п Г \ п

соотношение ^Г//** = ^ |1 + —1> 8 = _ суммарный потенциал системы.

;=1

п — \

1=1

Лемма 2.12. Для каждого ге{1, 2,...,«} выполняется следующее

рекуррентное соотношение: /1

(*+1)

1

п-1 а

+с(, где

с. = —!_ + I есть постоянная величина.

' «-IV а) V Л а) а п-\)

Лемма 2.13. В момент времени к для каждого ге {1, 2, ... ,п} выполняется

следующее соотношение

/<*>=Г__!_ А") /-да+с (я-Цд

и-1 а) ' ' Ь + {п-\)а

1- -

1 Ь п — 1 я

Теорема 2.11. Для устойчивого поведения вектора стабилизации необходимо

и достаточно выполнение условия

1 Ь

<1

При этом условии предельные

(2.21)

п — 1 а

значения координат вектора стабилизации равны

= Нт /,»> =с,. = Д + *

' *-*» ' 1 Ь + (п-\)а Ь + (п-1)а{ \ а) а п-1

Теорема 2.12. В условиях рассматриваемой модели для решений системы выполняются следующие утверждения.

A. Решение системы, заданное соотношениями

1 Г ь №'

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

B. При условии |£>/а|<1 любое начальное решение системы в результате преобразований (2.20) при к —» °° стремится к решению (2.21).

Приведем пример конкурентных взаимодействий. Пусть три фирмы (политические партии) Ау, А2, А^ распределяют свои фиксированные ресурсы <7 у = 80, Ц2 = 50, <73 = 40 друг против друга, улучшая свои конкурентные положения. Противостояние предполагает оценку отношений по формуле Су = сц (Ху, х^) = Ху — х^. Тогда рекуррентные соотношения (2.20) принимают вид

х(к+!)__„(*).,. ¿(к)

где//*+1Ц/;.Ч / = 1,2,3.

При начальном решении

'(0).

0 50 3(Г| 40 0 10 20 20 0

, /(0) =(10;-10; 0),

имеется неравновесная ситуация (рис. 2.3, а).

По расчетному алгоритму (2.20) на двух первых шагах получаем

' 0 45 35^

Г 0 50 30' 40 0 10 30 10 О

/

(1) .

: (5; — 5; 0); Х{1) =

45 0 5 30 10 О

, /(2) = (2,5;-2,5; 0).

При к —> °° решение стремится к устойчивому состоянию, которое вычисляется по формулам (2.21):

(0 45 35' X* = 45 0 5 , /* =(0;0;0). .35 5 0,

Рис. 2.3. Состояние системы: (а) начальное, (б) конечное равновесное

Задача об оптимальном обслуживании коммуникационной сети.

Полагаем, что коммуникационные сети — это системы транспортных дорог, линии связи и т.д. Рассмотрим небольшую коммуникационную систему, состоящую из четырех верщин (рис. 2.4). Пусть ресурсы вершин, участвующих в обслуживании сети, заданы следующими количественными значениями: = 50, <72 = 40, <7з =30, <73 =20. Поскольку пара вершин совместно обслуживает свою линию, то уместно считать, что с у = с ^ = с у (ху, х^) = Хц + х ^.

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

Рис. 2.4. Обслуживание коммуникационных линий Показано, что некоторое начальное решение, например

*<°> =

(0 20 20 10'

10 0 20 10

20 10 0 0

10 10 0 0

(0 30 40 20'

30 0 30 20

40 30 0 0

20 20 0 0

стремится к оптимальному (устойчивому) решению. По формуле (2.19)

(к) _ Р1 +41

д*+1)

У Я •'<

Численные расчеты для к = 10, 20:

¿ = 1,2,3,4 V Е.

Лю)_

,(20)_

О 20,2499 11,1223 18,6177 7,7501 0 14,8823 17,3677

О О

О О

20,2500 11,1250 18,6250' 14,8750 17,3750

О О

О О

О

28,00000 28,0073 ^ 27,9927 О

28,0000

28,0000 28,0073 27,9927' О 28,0073 27,9926

16,8750 13,1250 ^19,3750 10,6250 О

7,7500 0 14,8750 17,3750 ^(20) _

16,8750 13,1250 О 0 ~ 28,0000 28,0000

^19,3750 10,6250 О 0 ] ^28,0000 28,0000

(20) показывает, что обслуживание линий проходит равномерно.

28,0073 о о

27,9926 0 0

28,0000 28,0000 28,0000'

О 28,0000 28,0000

О О

О О

Матрица С

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

В третьей главе исследованы ресурсные системы структура которых

задается гиперграфом ЕЮ. С помощью таких систем можно моделировать не только парные, но и групповые взаимодействия.

Пусть система 5 состоит из п агентов, которые имеют соответствующие ресурсы ..., qn ■ Каждый агент / действует на одном глобальном рынке Р (с

участием всех агентов) и на одном внутреннем поле (без участия других). Следовательно, ресурс q¡ распределяется на две составляющие: для внутреннего поля хи и для общего поля х1р, где хи + х1р = д1.

Зададим систему оценок элемента / на внутреннем поле и на внешнем поле при помощи функций /„■ и /¡р:

/и=ОХц,

]р

1 = 1,2,..., п.

(3.1)

Общее состояние системы определяется состоянием агентов и задается матрицей

хПх22—хпп (3.2)

Л —

{х1р х2р -хпр )

Таким образом, в системе 5, находящейся в состоянии X, каждый агент может проводить оценки удовлетворенности своего распределения с помощью соотношений (3.1) и предпринимать соответствующие действия по перераспределению.

Система 81. Обозначим базовую модель через 51 = 5 (и, д, /), где п - число элементов, <? = (<71, Яп) ~ ресурсный вектор, / - условное обозначение

системы оценочных функций. Система функций / зависит от двух параметров а и /?, поэтому модель 51 = 5(п, /{«,/?}) определяется п + 2 параметрами: п для д и 2 для /.

Условие равновесия имеет вид:

Г /„=/,„

< _ или 4 т , 1=7, 2, ..., п. V-3'

К[

Система имеет 2п неизвестных и 2и уравнений, поэтому можно ставить вопрос о существовании и единственности равновесных состояний. После преобразований система (3.3) сводится к системе линейных уравнений:

2ссх{р +Рх2р + Аз Р +- + Р*пр =ас1\' Рх1р+2 ах2р +0хЪр +... + Рхпр =си}2\

РЧр + РХ2 Р +Р*ъР +-+2ахпр =щп.

Определитель основной матрицы системы равен А = (2сх-Р)п~х (2а+(п -1)/?).

Имеется два особых случая, когда А = 0 при 2а - /} = 0 и при 2ал-(п-Х)Р = 0. Во всех других случаях А^О и система уравнений имеет единственное решение, которое определяет единственное равновесное состояние.

Теорема 3.1. Для системы 51 = 5(и, /{а,/?}) выполняются следующие утвержден ия.

(а) Если 2а — /3ф0 и 2а + (п — \)/3 Ф 0, то существует единственное равновесное состояние X :

щ,(2а + (п-\)/3)-а/3(2

Х'р (2а - Р)(2а + (п - \)/3) ' . , _ , _ я .

,• о,,, , о/ п^ I = 1,2,...,и, где О - оощии ресурс системы. _ д, (а ~Р)(2а + (п -1)/?) + аг/?(2.

' _ (2а-Р)(2а + (п-\)Р) '

(б) Если 2а — Р = 0, то существует множество равновесных состояний при условии = = ••• =Чп =Ч и выполнении следующих соотношений:

и 2 2« м 2 2 п

(в) Если 2а + (п-\)Р = 0, то при условии <71+<72 + ••• +Чп = 0 существует однопарачетрическое семейство равновесных состояний

хпр ~ '> хпп = Чп ~

х,„ = < + ——-(<?,-—<7„), I = 1,2,..., п — 1, где г - любое число.

2 п

*и =-' + — ((" +1)9/ + (и -1)<7„). 2л

Рассмотрим более общие модели.

Система Б2. Игроки различным образом оценивают эффект своего ресурса на внешнем и внутреннем поле:

/и = а\хп > ■/¡р=а2х,р+А1>7>, / = 1,2,..., п.

(3.4)

Модель 52 = 5(п, <7,/{а^а^,/?}) определяется п + Ъ параметрами: и для q и 3 для /.

Система вЗ. Для каждого агента его оценочные функции дополнительно могут содержать «бонусные» надбавки или штрафы, не связанные с количеством распределенного ресурса:

/и = а\хи+аь

(3.5)

Данная модель 53 = 5(л, <7,включает дополнительно параметры с1 = (41, йг, ..., ¿„), й = (А1, Л2, •••> Ю-

Для систем 52 и 53 в работе доказаны обобщенные аналоги теоремы 3.1.

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

Динамика системы Пусть Х{к), к= 0,1,2,... последовательные

состояния системы. Предположим, что начальное решение

^и(0) х22(0) ... хпп(0) Л

Х(0) =

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

хи(к + \)Л

(* + !) = 2

а

МУ,

(3.6)

1 = 1,2,..., п.

{к)

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

Для дальнейшего исследования можно рассмотреть только второе соотношение из (3.6). Представим его в матричной форме: X р(к + \) = ^-А-Хр{к),

где

'0 1. .1

Хр(к + \) = х2р(к + 1) . я = 42 II S? 1 0. .11 *2Р(к)

SipU + Dj КЯп, {11. •10.

По индукции состояние на шаге к +1 можно выразить через начальное состояние:

X „ (к +1) = (е- А + А2 - А3 +... + (-1)* Ак\+ (-l)t+1 Ак+1Хр (0).

(3.7)

Для сходимости процесса достаточно выполнение условия ||А || < 1 для любой из известных норм матрицы А, например,

, = шах

:ахХЫ' NI' = maxZkl-

• j=i ' ,=i

(3.8)

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

(и- \)Р

2 а

<1.

(3.9)

Спектральная норма ||А||2=р(А) = тах|Дг|} (максимальное по модулю

собственное число матрицы А) определяет необходимое и достаточное условие

сходимости. Легко показать, что матрица А имеет два собственных значения:

В , (п-\)В ,

Л. =——, Я, =-—, причем первое значение имеет кратность п— 1.

2 а 2 а

Следовательно, необходимое и достаточное условие сходимости имеет вид

II А II _{П~\)Р

2а

< 1 и совпадает с условием (3.9).

Переходя к пределу в соотношении (3.7) при условии ||А||<1, получим вид

равновесного решения, не зависящего от начального состояния:

к-* °° 2

(3.10)

Соотношение (3.9) гарантирует сходимость со скоростью убывающей геометрической прогрессии с множителем // = Ца||. Если Z(0) = Х(0) — X и Z(k) = Х(к) — X*определяют соответственно начальное отклонение и отклонение на шаге к, то \Z{k)\ =|а* • Z(0)||<||Af • ||Z(0)|| = //||Z(0)||. Следовательно, за к

шагов отклонение уменьшится в £ = ßk раз. Поэтому количество итераций Inf

к =

+1 гарантирует уменьшение начального отклонения в е раз.

Теорема 3.4. Последовательные состояния Х(к), к = 0, 1, 2, ... системы 51, удовлетворяющие стационарным итерационным соотношениям (3.6), сходятся со скоростью убывающей геометрической прогрессии к единственному равновесному состоянию при лШбых начальных условиях тогда и только тогда,

когда выполняется соотношение

(я-РД

2 а

<1.

Динамика системы Б2. Для системы 52 равновесная стратегия развития определяет следующие итерационные соотношения:

__. Р

(3.11)

хи{к + \)-.

хф(к + 1)=-

ог, + а2

ЕМ*);

г = 1,2,..., п.

«1 + «2 ^

ах +а2

Тогда можно получить следующий результат, аналогичный теореме 3.4.

Теорема 3.5. Последовательные состояния Х(к), к = 0, 1, 2, ... системы 52, удовлетворяющие стационарным итерационным соотношениям (3.11) сходятся со скоростью убывающей геометрической прогрессии к единственному равновесному состоянию X * при любых начальных условиях тогда и только тогда,

когда выполняется соотношение

(п-\)Р

<1.

Компоненты равновесного состояния удовлетворяют соотношениям «2

X,- = Нт X (к) = -

-(Е-АГ-ч

х; = Нт Хр(к) = —

Динамика системы ЯЗ. Итерационные соотношения

1 ..... Р

(Я + ЛГ1-? •

Хц (* + !) = -

х,0(к + 1) =

0Г| +а 2

1_

а, +а2

-(«2?« +М +

«1 +«2 «1 +«2 ^

/ = 1,2,..., и.

(3.12)

Теорема 3.6. Последовательные состояния Х(к), к = 0, 1, 2, ... системы 53, удовлетворяющие стационарным итерационным соотношениям (3.12), сходятся со скоростью убывающей геометрической прогрессии к единственному равновесному состоянию X* при любых начальных условиях тогда и только тогда,

когда выполняется соотношение

(и -1)/?

«1 +аг2

<1.

Компоненты равновесного состояния удовлетворяют соотношениям:

Х:=ПтХ(к)=-

1

-(Е-Л)"1 -(«2<? - А +1г )•

X* =НтХ„(£) =-{Е + А)~х -(а.о +<1 -к),

где 7 = (Л1,(1~..,<1п)Т, 1Г = (к1,к2,...,кп)Т.

В четвертой главе рассмотрен ряд математических моделей «справедливого распределения» материальных ресурсов, основанных на естественных принципах равновесия. В настоящее время такого рода исследования объединены в Теорию рационирования, которая активно формируется в основном зарубежными авторами (Э. Мулен, Дж. Нэш, Р. Ауманн, JL Шепли, С. Шенкер и другие). В общем виде модели характеризуются следующим образом: задан объем ресурса (например, деньги или товар), который должен быть распределен между получателями, имеющими различные претензии на ресурс. Понятие «справедливости» распределения зависит от критериев, которые могут быть реализованы различным образом.

Пусть везде далее ресурс Е распределяется между п претендентами. Требования претендентов зададим вектором d2, ••., dn), а искомое решение обозначим (дГ|, х2, ..., хп). Представим разные методы реализации рациональных распределений на основе принципа f-равновесия.

Стратегия равных потерь. Для поиска решения будем использовать оценочную функцию / = f(d,x).

Соответствующие оценки для каждого претендента будут равны

/, = f(d¡,xl) = dl

/2=f{d2,x2) = d2-x2, ^ ^

f„=f(dn,xn) = dn-xn.

Из условия равновесия /у = /2 = ... = /„ = / после суммирования уравнений системы (4.1) получаем «/ = dl+d2+— +dn-{xl+x2+... + хп) и / = (0-Е)/п. Зная / , можно из (4.1) найти решение (д^, х2, ..., хп)\

X, = dx ~ fi =d\~ -(D-E)ln,

x2 = d2 — (D — E)/n,

~L=dn -(D-E)ln.

В работе Р. Ауманна3 принцип равных потерь реализуется для двух претендентов похожим образом. Каждый претендент I уступает претенденту у величину {E-di)+, где 5+=шах{5,0}. Величина спорной части Е -(Е - dl)+ -(E-d2)+ делится поровну между двумя претендентами:

E-(E-dl)+-(E-d2)++(E_d2)+; X2 = E-(E-dl)+-(E-d2)+HE_dih

Представим реализацию пропорционального распределения при помощи принципа /-равновесия. В качестве оценочной функции возьмем / = f(d, х) = х/d .

Если / = /; = х-/, то х- = /• • , ¿ = 1,2,..., и. После суммирования по г

3 Aumann R.J. and Maschler M. Game Theoretic Analysis of bankruptcy Problem a from the Talmud // Journal of Economic Theory. - 1985. - Vol. 36. - P. 195-213.

получаем соотношения ^Jfidi = f^ldj = / • D = = E, f = —.

/=1 /=1 ¡=i D

£

Следовательно, x, =f-d:= — d:, / = 1, 2,..., n.

D

Заметим, что точно такое же распределение получится при использовании

оценочной функции /, = fi(d,x) = ——-. Объясняется это тем, что функции / и /j

d

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

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

В разделе 4.2 рассмотрены распределительные модели страховых операций, основанные на равновесных принципах.

Модель 1. Пусть Е - некоторая годовая сумма выплат, которую приходится восстанавливать страховой фирме. Зададим множество клиентов в количестве и и страховые суммы S,-, / = 1,2,...,п. Требуется определить коэффициент к и страховые взносы dt=k-при известной вероятности наступления страхового случая р (считаем, что для каждого страхового случая вероятность одинаковая). Балансовые соотношения суммарных поступлений и выплат имеют вид

п п

E = Zdt, Р^=Е. /=1 (=1

d■ " 1 л

Так как Si = —, то ]Г 5, = — ^ d,. Следовательно, к = р и dj = р ■ 5,-.

к ,=1 к |=1

Определение страхового взноса по формуле dt= р- 5,- отвечает

«справедливому» равновесному принципу 5,- /dj= р = const.

1

Модель 2. Пусть Е0 — сумма административных расходов и налоговых отчислений. Все другие обозначения соответствуют Модели 1. Тогда балансовые соотношения принимают вид:

п п (4 3)

i=1 1=1

Из (4.3) после преобразований получим итоговые соотношения

у Е) '\Е)\Е) р \^Е + Еа)

Последнее соотношение показывает, что увеличение вероятности р или административных расходов Е0 уменьшает возможные выплаты З1,-. Заметим, что по сравнению с Моделью 1 «мерой» равновесия стал новый коэффициент к.

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

предусмотреть производственный резерв E¡, который скорректирует второе

л

балансовое соотношение p^S, = Е-Ех и приведет к новым результатам:

= d¡=kS¡ íЕ+Е"

S¡ (E-El)

— = —-!-Ц- = const.

di p(E + E0) i

ß~E\) KE~E\

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

Пятая глава посвящена разработке оптимальных моделей круговых (сенсорных) покрытий плоских областей. В той или иной форме эти задачи рассматривались в работах зарубежных авторов Wu J., Yang S., Wang L., Pottie G.J., Kaiser W.J., Cardei M., Du D„ Carie J., Simplot D„ Dai F., Zhang H., Hou J.C. и др. В работе4 было предложено несколько интересных моделей покрытий. Однако их расчеты не совсем корректны, так как определяют эффективности покрытия для одного стандартного элемента покрытия, а не в целом для покрываемой области. В диссертационной работе сделаны уточнения их оценок. Кроме того, предложены значительные улучшения эффективности покрытий за счет оптимального «зацепления» соседних кругов (модели второго уровня).

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

' к V27V

12 I

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

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

Модели первого уровня. Рассмотрим однородное покрытие плоскости кругами одного радиуса R. Это означает, что каждая точка области принадлежит, по крайней мере, одному кругу из рассматриваемого покрытия, а центры кругов определяют некоторую правильную регулярную решетку. Рассмотрим два вида покрытий: (а) Модель А-1 и (Ь) Модель В-1 (рис. 5.1).

d= — V27

1-Я-

tg

= 1,018955892.

4 Wu J., Yang S. Energy-Efficient Node Scheduling Models in Sensor Networks with Adjustable Ranges // Intern. J. of Foundations of Computer Science. - 2005. - Vol. 16, № 1. - P. 3-17.

5 Toth G. F. Covering the Plane with Two Kinds of Circles // Discrete Comput. Geom. - 1995. - Vol. 13. _P. 445-457.

а) Ь) с) <!) '

Рис. 5.1. Элементы покрытий, а) Модель А-1; Ь) Модель В-1; с) Модель А-2; (1) Модель В-2

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

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

Для Модели А-1 получаем

_ /?2зУз ля1 зл/з Пй_ (5Л)

$РА- 1 = ——. = —, КА_Х = — « 0,8272.

4 2 1Л

Для Модели В-1 эффективность КВ1 немного ниже:

5/?в_,=2Л2, Кв_{ =- = 0,6366.

Считается, что энергетические затраты пропорциональны площади сенсорных кругов с коэффициентом пропорциональности /г. Поэтому коэффициент энергетических затрат Е = /и/К обратно пропорционален К. Значения этого показателя соответственно для Модели А-1 и Модели В-1 равны:

=1^ = 1.2092^; Ед-1 = ~~ ~ 1,5708//. (5 3)

Модели второго уровня. Удалось значительно улучшить показатели эффективности покрытия за счет небольшого «наезда» больших соседних кругов друг на друга, а открывшуюся часть закрыть кругом небольшого размера. При этом площадь двукратного накрытия существенно уменьшится, а внутренний круг будет давать сравнительно небольшую добавку. Решая экстремальную задачу можно точно рассчитать лучший вариант «перекрытия» и соотношение между радиусами большего и меньшего кругов. Это и будут две оптимальные модели второго уровня, изображенные на рис. 5.1: с) Модель А-2 и (1) Модель В-2.

Теорема 5.1. Оптимальные параметры Модели А-2, определяющие наилучшие показатели эффективности покрытия К и Е, имеют вид

0,1796/?; = КА_2= ^ = 0,902; £А_2 «1,108^.

л/31 31 62 11л

Теорема 5.2. Оптимальные параметры Модели В-2, определяющие наилучшие показатели эффективности покрытия К и Е, имеют вид

Модели А-2 и В-2 сравнимы по качеству. Однако Модель В-2 имеет преимущество за счет более простой структуры решетки центров кругов.

В разделе 5.2.4 впервые предложена классификация регулярных покрытий плоскости. Любое конструктивное регулярное покрытие отнесем к одному из классов вида Со\„(п: р!/кь р2/к2,..., рп/к„), где и< - стандартная плитка покрытия, п - число разных размеров кругов, р1 - число кругов вида (, участвующих в покрытии плитки м>, к1 - доли кругов вида г, покрывающих плитку. Если ы -минимальная стандартная плитка, то обозначения однозначно определяют структуру покрытия и позволяют находить соответствующий класс моделей. Значение п является показателем сложности класса покрытий. Например, Модель А-2 будет принадлежать классу Соу№(2:112,Ц). Из рис. 5.9 видно, что минимальный фрагмент в этом случае является составной частью всех возможных плиток и представляет собой прямоугольный треугольник с острыми углами по 30 и 60 градусов.

Рис 5.9. Варианты плиток и минимальный фрагмент для Модели А-2

Соответствующие обозначения для других плиток согласованы между собой: Соуи,1(2:36,11), Соч „2(2\\Х,6Ъ), Соу„,3(2: 16,26). Каждая запись показывает, что в целом количество кругов одного размера в два раза меньше, чем другого:

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

Теорема 5.1*. В классе моделей правильной треугольной структуры А уровня сложности п = 2 рекордным по плотности является Модель А-2* из класса Соуи,(2 :112,1?) (рис 5.10) со следующими оптимальными параметрами:

_2 = 1,1781//.

3/6 :1/1 = 1/1: 6/3 = 1/6 : 2/6 = 1: 2.

= 1,0882796 при г = —= 0,1091Д, 2721

где Е>, - плотность покрытия.

Рис 5.10. Фрагмент модели покрытия класса Cov (2:112, 1г)

Расчеты по модели приведены в приложении 2. Заметим, что по сравнению с; Моделью А-2 класса Соу№(2:112,1б) маленький круг теперь находится не в вершине минимальной плитки, а на ее стороне.

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

¿^ЙШШк

^---/

Рис 5. П. Примеры моделей покрытий третьего уровня

Модели достаточно эффективные, но не являются наилучшими в своем классе. Далее приведем наилучшие модели третьего уровня в сериях А и В.

Модель В-3. Рассмотрим класс покрытий Соу^З :44,1{А[), где w -квадратная плитка со стороной а . Для минимальной плитки обозначение имеет вид Cov„,(3:lg,lg,i2) (рис. 5.12). Найдем в этом классе модель, для которой плотность покрытия минимальна.

А R

Шт

Рис 5.12. Фрагмент модели покрытия класса Соу^З: 18,18,12) Плотность покрытия будет выражаться следующей формулой:

D{a,ß) = ^

1

-+ 1

sin(ar + ß)

+ 1

cos(or + ß)

+ 4\ tg| a + ^ |-tga

cos a ) \ cos ОС Исследуя функцию на экстремум, находим оптимальные соотношения: min D(a,f3) ~ 1,093 845, #=19,08°, ¡3 ~ 13,15°, Я = 0,529а, г = 0,224я /7 = 0,067а.

В сравнении с плотностью оптимальной Модели В-2 квадратной структуры из класса Соу„,(2:14,14), имеющей значение тт£> = 1,1781, плотность покрытия для новой модели стала практически в два раза ближе к единице.

Модель А-3 представляет аналогичный класс покрытий треугольной структуры. Для правильной треугольной плитки обозначение класса будет иметь вид Соу№(3:36, 11,3]), а для минимальной плитки - Соу„,(3:112, 1б.'2) •

Рис 5.13. Фрагмент модели покрытия класса Соу (3:112,1 б, 12 ) Используя обозначения углов согласно рисунку, получаем формулу

D{a,/3)=^= V3

0,5

2

cos а

1-

cos(60° — ос — jB)

Y

1 sin(60° -а-р) л/з cos or

Y

+ 31 tgl or + 4

-tg a

и находим оптимальные параметры модели:

min D(a, /3) ~ 1,067678, « = 14,32°, £ = 10,31°, Л = 0,5160а, г = 0,0798 а. 0,0492 а .

Минимальная плотность оптимальной Модели А-2 треугольной структуры (обобщением которой данная модель является) равна mini) = 1,1084, что существенно больше. Заметим, что это значение также больше соответствующего показателя для Модели В-3 с квадратной структурой.

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

Теорема 5.3. При построении покрытия по типу Модели А-2 для ограниченных областей, имеющих площадь S, оптимальный размер больших кругов и их количество оценивается по заданному ценовому признаку р и по функции энергии мониторинга f(r)=jU- га следующими соотношениями:

г \\1 а

6 р

Л =

/и(а~ 2) 1 + 31

(

N{=-

л

ц(а-2)\ 1 + 31

s2la

6 р

(5.13)

Теорема 5.4. При построении покрытия по типу Модели В-2 для ограниченных областей, имеющих площадь Б, оптимальный размер больших кругов и их количество ог^енивается по заданному ценовому признаку р и по функции

энергии мониторинга /(г) =Ц- га следующими соотношениями:

4 р

fj(a-2)\ 1 + 5

/V,

ß{a-2)^1 + 5

4/>

Л/а

(5.14)

z1

Многие реальные объекты моделируются бесконечно длинными полосами.. Это автомобильные дороги и железнодорожные пути, различные линии связи, государственные границы, трубопроводы и прочие сооружения, у которых длина| существенно превышает ширину. Модели мониторинга подобных объектов рассмотрены в главе 6. Задачи сводятся к поиску наименее плотного покрытия бесконечной полосы, которые ранее практически не рассматривались. При исследованиях учтены граничные особенности и определены наиболее' эффективные модели в разных классах покрытий.

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

Модель 6.1. Регулярное однослойное покрытие полосы шириной к изображено на рис. 6.1.

Рис. 6.1. Однослойное и двухслойное покрытия полосы одинаковыми кругами Плотность покрытия всей полосы совпадает с плотностью прямоугольника и

о

равна й = Б/ / Бр, где - площадь кругов, покрывающих прямоугольник

СИЕЕ, а Яр — площадь С О ЕЕ. Оптимальным является покрытие, имеющее минимальную плотность £> = л! 2 = 1,5708, которая достигается при а = л14,

Я = /г/л/2 и расстоянии между центрами соседних окружностей й = /г.

Модель 6.2. Двухслойное покрытие с треугольной решеткой (рис. 6.1). Пусть /г - ширина полосы, - радиус круга, - расстояние между центрами соседних кругов одного слоя, а - угол между радиусом, проведенным к точке пересечения двух соседних окружностей одного слоя, и прямой АВ, проходящей через центры кругов этого слоя.

Плотность покрытия имеет вид р(а) = -

cosor(l + 3sin а)

D(á) достигается при sin а = (л/73-1)/12 = 0,62867; угол ог = 38,95°

4/7

Минимум функции

R

1 + sinar 3 + V73 Минимальная плотность такого покрытия

min D(a) =

0,3465h, d =

2^70 + 2л/73 3(3 + л/73)

; 0,5389/г.

48л-

л/70 + 2л/73(3 + л/73) 28

: 1,3998-

Замечание 6.1. Отметим нетривиальный результат. Треугольник АБС,

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

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

граничным эффектом. В случае правильной треугольной решетки плотность

1 4л

I покрытия больше и равна —j= ~ 1,451.

5V3

Модель 6.3. Многослойные покрытия полосы кругами одного радиуса. Для

j заданного числа слоев п плотность покрытия имеет вид

rw s Sf пл

D(a)= — =-.

) Sp 2(и-1 + (и + 1) sin a) cosa

2 (и —1)

Условие оптимальности: 2sin а-\--sin а-1 = 0.

(п +1)

Из этого следует, что

sin а = 0,25

и-1 и +1

+ Ö — -

и-1 й + 1

V

cosa

1,25(7

= 0,25^8-2р2 +2р^]р2 +8 j,

и-1

где р =-. Это дает возможность вычислить оптимальное значение плотности

п + 1

покрытия D(a) и определить соотношение между радиусом и шириной полосы

_^-.

п -1 + (и +1) sin Cf

Устремив п в бесконечность, получим предельное значение р= 1 и sin а =1/2, что соответствует значению а = л! 6. Предельное значение плотности 2 л

limD = —1= ~ 1,2092. Эта асимптотическая оценка соответствует классическому 3V3

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

Модель 6.4. Пусть центры кругов радиуса R расположены на средней линии полосы и два соседних круга пересекаются, оставляя непокрытой область около границы полосы, которая покрывается кругами радиуса г (рис. 6.2).

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

D{a,ß) = ®=-Í:

Sp 4cosacosp^

2 + 2sin ör+sin(a-yß)-4sina sin|

29

л a-ß ~44 2 .

Минимум функции D(a,/3) не удается найти аналитически. С использованием, вычислительных методов получено:

min D(a,jB) ~ 1,294 при Д = 0,6266/г, г = 0,18252 /г, йг=27°, ^ = 37°. а,р

Модель 6.5. Рассмотрим четырехслойное покрытие, изображено в правой части рис. 6.2. Пусть центральный угол для дуги большой окружности, отсекаемой^ малой окружностью, равен 2(р. Тогда плотность покрытия равна

л

D{<p) = -

-(4 + (-ч/з • tg(30° + (£>) -I)2)).

л/3(3 + 4sin(30° + 2(р))

В результате численного решения находим оптимальные значения: !

min D(<p) = 1,2542 при £>=11,5°, R = 0.3229 h, г = 0,08595/2. »>

Замечание 6.2. Отметим, что добавление кругов радиуса г позволил^ существенно уменьшить плотность покрытия по сравнению с Моделью 6.2.

Модель 6.6. Рассмотрим пятислойное покрытие, изображенное на рис. 6.3 Круги радиуса R определяют основную прямоугольную структуру, круги радиуса

г} используются в центральной части полосы, а круги радиуса г2 находятся на

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

D(a, <р) Минимальная

S¿ Sp

7Г(3 - sin 2а + 2(cos а ■ tg(or + <р) - sin а) )

4 cos or(cos а + sin(a + 2<р))

плотность min D(a, <р) ~ 1,23355

а,ср

достигается

при|

а = 26,36°, ^> = 13,18°, Я = 0.2956й, г^ОДЗЗб/г, г2 = 0,0874/г.

Замечание 6.3. Если упростить модель, потребовав равенства радиусов внутренних и граничных кругов, то плотность покрытия немного изменится:

D(a)■

4(1 +cos 2 а)

min D(a) = 1,256638 при а «30,94°, R = 0,29147 h,

= 0,10014 h.

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

\ eiii ) \.................-й

/ —

с........ \.....

]

Рис. 6.3. Пятислойное и шестислойное покрытия полосы кругами трех радиусов

Модель 6.7. Рассмотрим шестислойное покрытие, состоящее из кругов трех радиусов (рис. 6.3). Используя обозначения углов, принятых в Модели 6.6, получим следующее выражение для плотности покрытия:

1 + (cos а! л/3 - sin а)2 + (cos а ■ tg(a + ср) - sin а)2)

D(a,cp) =

cos а(л/3 ■ cos а + 2 sin(or + 2(р)) 30

Минимальная плотность для данной модели min D{a,(p) =1,20396 достигается при

a,q>

а ~ 21,11°, (р~ 14,32°, R = 0,31748 h, /j« 0,05248 A, г2 =0,09717А.

Замечание 6.4. Если потребовать равенства радиусов меньших кругов, то плотность покрытия будет зависеть от одной переменной и ее оптимальное значение немного увеличится:

ч 2л- 7-2cos2a-2V3-sin2а

О(а) =---¡=-т=-,

3 2л/3 + 2V3 ■ cos 2а - sin 2а

min D(a) = 1,23387 при « = 17,72°, 7? = 0,33383 А, г = 0,24568/? = 0,08202 А .

а

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

В разделе 6.3 рассмотрены различные модели мониторинга полосы внешним образом. Это означает, что по некоторым причинам «недоступности» мы не можем располагать сенсорные устройства внутри области. Такая постановка задачи ранее не рассматривалась. Исследования показали, модели внешнего мониторинга полосы более тесно связаны с моделями покрытия плоскости, чем модели обычного мониторинга полосы.

Рассмотрим покрытие плоскости кругами одного радиуса, имеющее правильную треугольную решетку расположения кругов (рис. 6.9). Между центрами кругов можно выделить два типа прямолинейных полос, покрытых внешним образом: SA-l(l) и SA-1(2) с одинаковыми плотностями, но разными структурами. Оптимальность покрытия полос следует из оптимальности покрытия плоскости. Очевидно, что плотность покрытия полосы в два раза больше I соответствующей плотности покрытия плоскости.

Приведем основные характеристики моделей.

Модель SA-l(l): D

= 2 Da, = 4лг/V27 = 2,4184,

£4-1(1)

Модель SA-1(2): DSA_l(2) = 2£>дч =4;r/V27 = 2,4184,

R = 2/г/З = R = 2h.

' 0,6667 h.

г

■ ш К i 1 X ' '

■

CÍ©

р В Я Hl L £ ч

f^y^XZZ 7

Рис. 6.9. (1) Модель А-1 покрытия плоскости кругами одного радиуса и соответствующие модели внешнего покрытия полосы: (2) Модель SA-I(l), (3) Модель SA-l(2)

Модель А-2 порождает единственную эффективную Модель SA-2 покрытия полосы внешним образом (рис. 6.11):

Модель SA-2: DSA_2 =

1 \п

9л/з

2,2168, R =

W31 Зл/З

а,0715 А, г =

Зл/З

= 0,19245 А.

Рис 6.11. Модель SA-2 покрытия полосы внешним образом

Модель В-2 определяет две Модели SB-2(1) и SB-2(2) для покрытия полос разными способами, но с одинаковой плотностью (рис 6.12):

Модель SB-2(1): DSB_2(X) =^ = 2,3562, R = = 1,1180/г, г = ~. [

— » 2,3562, R = _ 0,7906/г, г= * 4 2V2 2л/2

Модель SB-2(2): DSB_2(2) = ^ = 2,3562, Я = ^^ = 0,7906/г, г = -г-?= = 0,3536/г.

Рис 6.14. Элемент покрытия полосы кругами трех радиусов и его минимальный фрагмент

Рис 6.12. Модели 8В-2(I) и ХВ-2(2) покрытия полосы внешним образом

Рассмотрим специальное покрытие плоскости кругами трех различных радиусов: Модель вА-З. На рис. 6.14 изображены элемент покрытия и его! минимальный фрагмент из класса Соуи,(3:14,12,12) ■ Исследования показали, что| размер фрагмента (соотношение между катетами прямоугольного треугольника) так же является параметром оптимизации. Заметим, что шестиугольник, изображенный на рис. 6.14, немного растянут вдоль горизонтали. С учетом обозначений фрагмента] это значит, что выполняется соотношения для углов: а >30°, а + р = 90°. Функция плотности покрытия достаточно сложна и зависит от трех параметров:

1 —ctgor ctgi»

8(sinörcos$o) ( co+Y

90° —a-<p

-J-tgfflj

сщ(а+ф) 2sin«'cos^

со - arccos(2 sin а ■ cos ф).

Оптимальные параметры для данного внешнего покрытия: пипй5Л_3 =2,186, а = 29,79°, /9 = 60,21°, И =1,064 а, г = 0,2003а, /7 = 0,0305а.

Аналогичная Модель ЯВ-З класса Соу^З'.Ц,ЦЛг) третьего уровня получена по типу квадратной структуры с минимальной плотностью Я5В_3 = 2,30906. Возможны более сложные специальные модели внешнего покрытия полосы, но они дают незначительное уменьшение плотности при существенном повышении сложности класса.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

I. Монографии

1. Астраков С.Н. Ресурсные системы. Равновесные методы поиска оптимальных решений. - Lambert Academic Publishing, 2011. - 157 с.

II. Публикации в ведущих рецензируемых научных журналах и в изданиях, рекомендованных ВАК

2. Астраков С.Н. Моделирование устойчивых взаимоотношений на графах / Вестник КузГТУ. - 2005. - № 2. - С. 94-97.

3. Астраков С.Н. Некоторые методы распределения ресурсов в динамичесы сетевых моделях // Известия вузов. Черная металлургия. - 2006. - № 4,- С. 7-11.

4. Астраков С.Н. Равновесные методы поиска рациональных распределений / Вестник РГТЭУ. - 2009. - № 5. - С. 45-50.

5. Астраков С.Н., Анисова М.А. Математическое моделирование экономически взаимодействий на графах // Вестник РГТЭУ. - 2009. - № 6. - С. 39-43.

6. Zalubovsky V., Astrakov S., Erzin A., Choo H. Energy-efficient Area Coverage b Sensors with Adjustable Ranges // Sensors. - 2009. - № 9. - P. 2446-2460.

7. Астраков C.H., Ерзин А.И., Залюбовский B.B. Сенсорные сети и покрыта плоскости кругами // Дискретный анализ и исследование операций. - 2009. - № 3. -С. 3-19.

8. Astrakov S., Tahonov I. A Dynamic Model of Group Interactions // International Journal of Biomedical Soft Computing and Human Sciences. - 2011. - V. 18, № 1. P. 77-84.

9. Astrakov S., Erzin A. Min-Density Stripe Covering and Applications in Senso Networks // ICCSA, Part III, LNCS. - 2011. - № 6784. - P. 152-162.

10. Астраков C.H., Тахонов И.И. Равновесное распределение ресурсов в модели групповых взаимодействий // Вестник НГУ. Сер. Математика, механика, информатика. -2011.- Вып. 3. - С. 61-76.

11. Астраков С.Н., Ерзин А.И. Построение эффективных моделей покрытия при мониторинге протяженных объектов // Вычислительные технологии. - 2012. Т. 17, № 1.-С. 26-34.

12. Астраков С.Н., Ерзин А.И., Сенсорные сети и покрытие полосы эллипсами / Вычислительные технологии. - 2013. - Т. 18, № 2. - С. 3-17.

13. Astrakov S., Erzin A. Covering a Plane with Ellipses // Optimization. Journal of Math. Program, and Operation Research. - 2013. - V. 62, № 10. - P. 1357-1366.

14. Astrakov S., Erzin A. Efficient Band Monitoring with Sensors Outer Positioning // Optimization. Journal of Math. Program, and Operation Research. - 2013. - V. 62, № 10.-P. 1367-1378.

III. Статьи в профессиональных журналах и научных сборниках

Общее количество - 24 работы, из них наиболее значимые:

15. Астраков С.Н., Ерзин А.И. Одна модель саморегулирующейся системы // Математические структуры и моделирование. - 2004. - № 13. - С. 30-38.

34

16. Астраков С.Н., Ерзин А.И. Моделирование устойчивых взаимоотношений на графах // Материалы 13-й Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск: ИГУ, 2005. - Т. 1. - С. 413420.

17. Астраков С.Н. Моделирование устойчивых взаимодействий на графах // Проблемы информационной экономики: Сб. науч. тр. под ред. P.M. Нижегородова. — Вып. 4: Моделирование инновационных процессов и экономической динамики. - М.: ЛЕАНД, 2006. - С. 293-302.

18. Астраков С.Н., Ерзин А.И., Залюбовский В.В., Раха С. Модели и методы регулярного покрытия в сенсорных сетях // Материалы 14-й Байкальской международной школы-семинара «Методы оптимизации и их приложения». -Иркутск, ИГУ. - 2008. - Т.. 1. - С. 322-331.

19. Astrakov S. Search for Intelligent Methods of Equilibrium Distribution // Program and Abstracts of International Conference on Operations Research. - Augsburg: University of Augsburg, 2008. -P. 215.

20. Astrakov S., Erzin A., Zalubovsky V., Choo H. Energy-efficient Area Coverage by Sensors with Adjustable Ranges // 7th Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. - Seoul (Korea), 2009. - 8 p. - 1 электрон, опт. диск (CD-ROM).

21. Астраков C.H., Ерзин А.И. Покрытие бесконечной полосы кругами одного и двух радиусов // Труды ИВМиМГ «Информатика». - Новосибирск, 2009. - Вып. 9. -С. 143-146.

22. Astrakov S. The full efficient monitoring of stripe with external deployment sensor // Program and Abstracts of 21-st International Symposium on Mathematical Programming. - Berlin, 2012. - P. 100.

23. Астраков С.Н. Мониторинг полосы с внешним расположением сенсорных датчиков // Математические структуры и моделирование. - 2012. - Вып. 25. -С. 52-62.

Редакционно-издательский отдел Федерального государственного бюджетного учреждения науки Института динамики систем и теории управления СО РАН 664033, Иркутск, ул. Лермонтова, д. 134 E-mail: rio@icc.ru

Подписано в печать 23.01.2014 г. Печать цифровая. Бумага офсетная. Формат 60x84/16. Усл. печ. л. 2 Тираж 110 экз. Заказ № 201

Отпечатано в типографии «Срочная полиграфия» ИП Малыгин Алексей Михайлович 630090, Новосибирск, пр-т Академика Лаврентьева, 6/1, оф. 104 Тел. (383) 217-43-46, 8-913-922-19-07

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

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

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

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

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

СИСТЕМАХ

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

Диссертация на соискание ученой степени доктора физико-математических наук

Новосибирск - 2014

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 4

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

1.1 Основные принципы системного анализа 55

1.2 Графические методы представлений общей структуры системы 60

1.3 Применение графических представлений для моделирования реальных систем и процессов 65

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

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

2.1 Принципы моделирования многосторонних взаимоотношений 67

2.2 Линейная модель конфликтных взаимодействий 75

2.3 Моделирование отношений двух коалиций 83

2.4 Модели коммуникационных сетей 94

2.5 Однородная модель взаимодействий на полном графе 102

2.6 Специальные содержательные модели 107

2.6.1 Конкурентные взаимодействия 107

2.6.2 Обслуживание коммуникационных сетей 109

2.6.3 Оптимизация нелинейных технологических процессов 111

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

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

3.1 Базовая модель взаимодействий 118

3.2 Однородная модель оценки отношений 126

3.3 Неоднородные оценки взаимодействий 129

3.4 Индивидуальные оценки взаимодействий 132

3.5 Динамические модели и итерационные процессы 133

3.6 Модель для двух общих полей взаимодействий 140

3.7 Общий итерационный алгоритм изменений состояний 142

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

4.1 Рациональные модели распределений 145

4.1.1 Принципы «справедливости» и критерии распределений 146

4.1.2 Стратегия равных потерь 149

4.1.3 Реализация пропорционального распределения при помощи

принципа f-равновесия 150

4.1.4 Системы равновесных функций 150

4.2 Равновесные стратегии в страховании 152

4.3 Выводы по равновесным распределениям 155

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

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

5.1 Проблемы мониторинга и сенсорные сети 167

5.2 Модели покрытий для сенсорных сетей 158 5.2.1 Модели первого уровня 158

5.2.2. K-модели второго уровня 160

5.2.3. Модели второго уровня 162 5.2.4 Классификация регулярных покрытий 166

5.3 Эффективность покрытий ограниченных областей 173

5.3.1 Построение типовой функции затрат 174

5.3.2 Функция затрат для кругового сенсорного покрытия 175

5.3.3 Оптимизация затрат для моделей третьего уровня 176

5.3.4 Обсуждение результатов и выводы 180 ГЛАВА 6. ЭФФЕКТИВНЫЕ ПОКРЫТИЯ ПРОТЯЖЕННЫХ ОБЪЕКТОВ 182

6.1. Покрытие полосы кругами одного радиуса 183

6.1.1 Однослойные покрытия 184

6.1.2 Двухслойные и многослойные покрытия 185

6.2. Специальные модели покрытий кругами двух и трех радиусов 188 6.3 Мониторинг полосы с внешним расположением датчиков 193 6.4. Общий анализ результатов по сенсорным сетям 203

ЗАКЛЮЧЕНИЕ 208

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

ПРИЛОЖЕНИЕ 1 219

ПРИЛОЖЕНИЕ 2 221

ПРИЛОЖЕНИЕ 3 225

ВВЕДЕНИЕ

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

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

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

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

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

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].

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

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

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

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

о Поиск аналитических и численных решений, соответствующих равновесным состояниям систем.

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

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

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

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

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

Теоретическая и методологическая основа исследования. Во-первых, это математические модели общего равновесия (JI. Вальрас, В. Парето, Т. Купманс, К. Эрроу, Ж. Дебре, Р. Раднер, JI. Гурвич, Д. Нэш, Л. Макензи, Т. Лунберг, X. Никайдо, Т. Негуши, В.И. Данилов, А.Д. Новиков,

A.И. Соболев, С.Л. Печерский, В.И. Опойцев и др.). Во-вторых, это теория социального выбора и рационального поведения (Э. Мулен, Л. Шепли, С. Шенкер, С. Едлинг, С. Стем, Р. Франк, Д. Грин, М. Олсон, В. Ванберг, И. Шапиро, М. Фармер, М. Зафировский, В. Культыгин, В. Кокорев, Р. Швери,

B. Радаев, Г. Рузавин и др.). Отметим влияние теории игр, которая тесно переплетается с вышеуказанными разделами (Д. Нейман, П. Самуэльсон, Р.Ауманн, Т. Шеллинг, Л. Шепли, Д. Нэш, М. Масчлер, О. Моргенштерн, Р. Люис, Р. Майерсон, К. Гренджер, X. Райфа Д. Быоенен, Р. Гиббоне, П. Янг, Н. Ховард, М.В. Губко, Ю.Б. Гермейер, H.H. Данилов, М.А. Шубин, Ю.Н. Павловский, С.Л. Печорский, A.A. Беляева и др). Кроме того, источником ряда идей послужили исследования по теории систем и системному анализу (Р. Акофф, Л. Берталанфи, У. Черчмен, С. Кунц, С. Донелл, Н. Винер, Д.

Форрестер, Н. Луман, Т. Берне, Е. Флем, Т. Хюбнер, И. Стенгерс, И. Пригожин, В.Н. Садовский, В.Г. Афанасьев, В.Д. Могилевский и др.). Методологической основой разработки новых моделей является теория графов и ее приложения (Л.Р Форд, Д.Р. Фалкерсон, Н. Кристофидес, Р. Дистлер, К. Берж, М. Свами, О.В. Бородин, А.Д. Плотников, В.П. Попов А.Д. Цвиркун и др.). Работа опирается также на исследования, посвященные сходимости итерационных процессов и методам последовательных приближений (Ф.Р. Гантмахер, С.К. Годунов, Д.К. Фадеев, В.Н. Фадеев, В.И. Крылов, В.В. Бобков, A.A. Самарский, A.B. Гулин, A.M. Мацокин и др.).

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

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

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

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

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

1. Разработка принципов моделирования распределенных ресурсных систем на графах и создание математического аппарата для описания таких систем. Предложенная методика поз�