WWW.KNIGA.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Онлайн материалы
 

Pages:   || 2 |

«Институт проблем управления им. В.А. Трапезникова РАН УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ Выпуск 65 СБОРНИК Январь 2017 ТРУДОВ ISSN 1819-2467 Регистрационный номер Эл ...»

-- [ Страница 1 ] --

Институт проблем управления

им. В.А. Трапезникова РАН

УПРАВЛЕНИЕ

БОЛЬШИМИ

СИСТЕМАМИ

Выпуск 65 СБОРНИК

Январь 2017 ТРУДОВ

ISSN 1819-2467

Регистрационный номер Эл №ФС77-44158 от 09 марта 2011 г.

Москва – 2017

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

Институт проблем управления

им. В.А. Трапезникова

УПРАВЛЕНИЕ

БОЛЬШИМИ

СИСТЕМАМИ

СБОРНИК ТРУДОВ

Выпуск 65 Москва – 2017 УДК 519 ISSN 1819-2467 ББК 32.81 У 67 Управление большими системами / Сборник трудов. Выпуск 65. М.: ИПУ РАН, 2017. – 169 с. Дата опубликования: 31.01.2017.

КООРДИНАЦИОННЫЙ СОВЕТ

Академики РАН: Васильев С.Н., Емельянов С.В., Куржанский А.Б., Федосов Е.А., Черноусько Ф.Л.; члены-корреспонденты РАН: Желтов С.Ю., Каляев И.А., Пархоменко П.П., Попков Ю.С.; д-ра техн. наук: Дорофеюк А.А., Кузнецов О.П., Кульба В.В., Лотоцкий В.А., Павлов Б.В., Поляк Б.Т., Рутковский В.Ю.

РЕДАКЦИОННАЯ КОЛЛЕГИЯ

Главный редактор: член-корр. РАН Новиков Д.А. Зам. главного редактора: д-р физ.мат. наук Губко М.В. Отв. секретарь: канд. техн. наук Базенков Н.И. Редактор: канд.

техн. наук Квинто Я.И.

Д-ра техн. наук: проф. Алескеров Ф.Т. (ГУ ВШЭ), проф. Алчинов А.И. (ИПУ РАН), проф. Андриевский Б.Р. (ИПМ РАН), проф. Афанасьев В.Н. (МИЭМ), проф.

Бахтадзе Н.Н. (ИПУ РАН), проф. Бурков В.Н. (ИПУ РАН), проф. Вишневский В.М.



(ИПУ РАН), Галяев А.А. (ИПУ РАН), д-р физ.-мат. наук проф. Ерешко Ф.И. (ВЦ РАН), д-ра техн. наук Зоркальцев В.И. (ИСЭМ СО РАН), проф. Калашников А.О. (ИПУ РАН), проф. Калянов Г.Н. (ГУ ВШЭ), проф. Каравай М.Ф. (ИПУ РАН), д-р экон. наук, проф.

Клочков В.В. (ИПУ РАН), д-ра техн. наук, Коргин Н.А. (ИПУ РАН), проф. Курдюков А.П. (ИПУ РАН), д-ра физ.-мат. наук, проф. Кушнер А.Г., проф. Лазарев А.А.

(МФТИ), д-ра техн. наук: проф. Лебедев В.Г. (ИПУ РАН), проф. Мандель А.С. (ИПУ РАН), д-р биол. наук проф. Михальский А.И., д-р физ.-мат. наук, проф. Непейвода Н.Н.

(ИПС РАН), д-р экон. наук, проф. Нижегородцев Р.М. (ИПУ РАН), д-ра техн. наук:

проф. Орлов А.И. (МГТУ), д-ра физ.-мат. наук: проф. Рапопорт Л.Б. (ИПУ РАН), проф.

Райгородский А.М. (МГУ), проф. Савватеев А.В. (РЭШ), д-ра техн. наук: проф. Самуйлов К.Е. (РУДН), проф. Сидельников Ю.В. (МАИ), Совлуков А.С. (ИПУ РАН) д-ра физ.мат. наук: проф. Соловьев С.Ю. (МГУ), проф. Угольницкий Г.А. (ЮФУ), проф. Уткин В.А. (ИПУ РАН), проф. Хоботов Е.Н. (МГТУ), д-ра физ.-мат. наук: доцент Чеботарев П.Ю. (ИПУ РАН), проф. Чхартишвили А.Г. (ИПУ РАН), проф. Щербаков П.С. (ИПУ РАН).

РЕГИОНАЛЬНЫЕ РЕДАКЦИОННЫЕ СОВЕТЫ

Арзамас – д-р физ.-мат. наук проф. Пакшин П.В. Волгоград – д-ра физ.-мат. наук: проф.

Воронин А.А., проф. Лосев А.Г. (ВолГУ); Воронеж – д-р техн. наук, проф. Баркалов С.А., д-р физ.-мат. наук, проф. Головинский П.А. (ВГАСУ), д-р техн. наук, проф.

Подвальный С.Л. (ВГТУ); Иркутск – академик РАН Бычков И.В., д-р физ.-мат. наук, проф. Лакеев А.В. (ИДСТУ СО РАН); Казань – д-р физ.-мат. наук, проф. Маликов А.И., д-р техн. наук, проф. Сиразетдинов Р.Т. (КГТУ-КАИ); Липецк – д-ра техн. наук: проф.

Погодаев А.К., Сараев П.В. (ЛГТУ); Самара – д-ра экон. наук: проф. Богатырев В.Д., проф. Гераськин М.И., д-р техн. наук, проф. Засканов В.Г. (СГАУ); Петрозаводск – д-р физ.-мат. наук, проф. Мазалов В.В., д-р техн. наук, доц. Печников А.А. (ИПМИ КарНЦ РАН); Санкт-Петербург – д-р физ.-мат. наук: проф. Петросян Л.А. (СПбГУ), д-р техн.





наук проф. Фуртат И.Б. (ИПМ РАН); Старый Оскол – д-р техн. наук, проф. Еременко Ю.И. (СТИ).

Адрес редакции: 117997, г. Москва, ул. Профсоюзная, д. 65.

Адрес в интернете: ubs.mtas.ru.

ИПУ РАН, 2017 СОДЕРЖАНИЕ Системный анализ Иванов Н.Н.

Степень параллелизма обобщенных стохастических сетевых графиков

Анализ и синтез систем управления Фуртат И.Б.

Динамическая компенсация возмущений в условии насыщения сигнала управления

Фуртат И.Б., Нехороших А.Н.

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

Информационные технологии в управлении Ураков А.Р., Тимеряев Т.В.

Алгоритм решения динамической задачи поиска кратчайших расстояний в графе

–  –  –

Управление в социально-экономических системах Новиков Д.А.

Комплексные модели системной оптимизации производственно-экономической деятельности предприятия

Шумов В.В.

Моделирование миграции населения в задачах обеспечения безопасности государства

Управление большими системами. Выпуск 65 УДК 519.179.2 ББК 22.176 + 65.23

СТЕПЕНЬ ПАРАЛЛЕЛИЗМА

ОБОБЩЕННЫХСТОХАСТИЧЕСКИХ СЕТЕВЫХ

ГРАФИКОВ

–  –  –

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

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

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

В работе рассматривается обобщенный вариант стохастических сетевых графиков (ОССГ) [6], в которых допускаются Николай Николаевич Иванов, доктор технических наук, доцент (ivanov.nni@yandex.ru).

Системный анализ двойственные дисциплины возбуждения вершин: классическая дисциплина «И», которой соответствует возбуждение вершины в результате прохождения всех дуг, в нее входящих (вершина типа x в классификации, приведенной в [1]), и альтернативная дисциплина «исключенное ИЛИ» (далее просто ИЛИ), которой соответствует возбуждение вершины в результате прохождения первой из входящих в нее дуг (вершина типа [1]).

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

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

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

Особое значение приобретает этот показатель при проектировании архитектуры ВС, управляющих в реальном времени по программам, структурированным ОССГ. В работах [2, 4, 5, 8, 9], Управление большими системами. Выпуск 65 посвященных проблеме организации временной надежности управляющих в реальном времени параллельных ВС, рассматривалась структуризация управляющих взаимодействующих программных комплексов с помощью сетевых графиков. При этом предлагалась реализация этих комплексов в ВС с ограниченным числом каналов (как правило, двумя). В дальнейшем процедуры обеспечения временной надежности были дополнены организацией аппаратной надежности для случая одиночной неисправности ВС в двухканальной ВС [10]. Использование ограниченного числа каналов ВС предполагало буферизацию готовых к выполнению программных комплексов, что вызывало необходимость назначения их приоритетов и порядка выполнения.

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

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

Следует заметить, что визуальное определение степени параллелизма становится весьма затруднительным в случае достаточно большого числа вершин и дуг, особенно в случае, когда ОССГ не является планарным графом [11]. Рассматриваемые ниже процедуры определения этого показателя осуществимы машинным способом, что снимает все проблемы вычислительного характера.

–  –  –

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

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

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

Определение 1. Дуги u и v сетевого графика, в котором события наступают в соответствии с дисциплиной «И», находятся в отношении W W (u), если они не связаны цепочкой (включая пустую цепочку).

Определение 2. Дуги u и v сетевого графика, в котором события могут наступать в соответствии с дисциплинами «И» или «ИЛИ», находятся в отношении (uv), если они либо не связаны цепочкой, либо каждая соединяющая их (возможно, пустая) цепочка, содержит хотя бы один узел типа «ИЛИ».

Сетевой график (на примере сетевого графика с вершинами только типа И) задает на множестве W отношение следования * W W, при котором две дуги u и v связаны пустой цепочкой и v есть последователь u: u*v. Производя транзитивное и рефлексивное замыкания отношения *, приходим к отношению частичного порядка, задаваемому матрицей А, у которой aii = 1, aij = 1 и aji = 0, если uiuj. Матрица АТ обратного отношения -1 может быть получена транспонированием матрицы А.

Рассмотрим теперь (симметричное, рефлексивное) отношение = –1 с матрицей B = A + AT – E. Отношение, рассматриваемое в определении 1, описывает отношение между дугами как дополнение по отношению к (u, v U, uv u v). Следовательно, заменяя в матрице B нули единицами, а единицы на нули, получаем симметрическую матрицу С, соответствующую отношению. Аналогичные построения проводятся для сетевых Управление большими системами. Выпуск 65 графиков со смешанными типами узлов, за исключением того, что дуги u и v, связанные пустой цепочкой и разделенные вершиной типа «ИЛИ», не могут находиться в отношении *.

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

Максимальный полный подграф графа G называется кликой.

Заметим, что у графа G может существовать несколько клик.

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

эта оценка является точным значением степени параллелизма.

Доказательство.

Пусть для некоторого набора случайных времен прохождения дуг число одновременно проходимых в некоторый момент времени дуг равно k и не существует наборов и моментов времени, для которых это число больше k. Это означает, что число k является степенью параллелизма рассматриваемого сетевого графика. Очевидно, все эти дуги попарно находятся в отношении либо в соответствии с определением 1, либо в соответствии с определением 2. Таким образом, эти дуги образуют полный подграф в некоторой клике графа G, откуда следует неравенство k N, где N – кликовое число графа G.

Пусть теперь для некоторого сетевого графика с единственным типом узлов «И» на графе G, построенном в соответствии с определением 1, существует клика максимального размера N.

Рассмотрим дуги, входящие в эту клику. Пусть для некоторого случайного набора U времен прохождения всех дуг времена окончания прохождения рассматриваемых N дуг равны t1, …, tN.

Очевидно, что существует константа С такая, что C min{ti } max{ti }.

1i N 1i N Поскольку для сетевых графиков с единственным типом узлов «И» выполнение отношения для каждой пары дуг означает Системный анализ независимость времен начала и конца их прохождения друг от друга, можно построить теперь случайный набор, для которого времена окончания прохождения рассматриваемых N дуг совпадают и равны C min{ti }, не изменяя при этом времена 1i N прохождения для остальных дуг в сравнении с исходным набором U. Выбирая некоторый момент времени, заключенный в промежутке [max{ti }, C min{ti }], получаем, что в этот момент 1i N 1i N времени все N дуг проходятся одновременно. Отсюда степень параллелизма удовлетворяет неравенству k N, что для сетевых графиков с единственным типом узлов «И» с учетом выше доказанного неравенства приводит к равенству k = N.

Таким образом, ключевой является задача нахождения клик графа G. Для ее решения может быть привлечен алгоритм Брона–Кербоша [12].

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

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

В качестве примера рассматривается граф, представленный на рис. 1. В соответствии с нумерацией дуг, приведенной на рис. 1, по 45 неупорядоченным парам дуг сетевого графика построены две таблицы – матрицы инцидентности графов GА и GB для случаев, когда события, представляемые вершинами 2 и 4, наступают по дисциплине «И» (матрица А) и по дисциплине «ИЛИ» (матрица В).

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

3. Альтернативный метод

В качестве альтернативного метода нахождения степени параллелизма можно предложить построение дерева состояний сетевого графика [4, 5].

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

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

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

Управление большими системами. Выпуск 65 Алгоритм построения дерева состояний состоит в рекурсивном пополнении состояний дерева, начиная с начального. Если предположить, что построено состояние s k-го уровня этого дерева, то для построения состояний (k +1)-го уровня, непосредственно связанных с состоянием s, нужно из s вывести дуги числом, соответствующим числу дуг сетевого графика, входящих в s. Каждая такая дуга u, помеченная номером выбранной дуги сетевого графика, ведет в некоторое состояние q, которое содержит дуги, входящие в s, за исключением u, и пополненное дугами, активируемыми в случае, если прохождение дуги u вызвало свершение некоторого события.

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

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

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

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

–  –  –

Рис. 3. Дерево состояний графика с дисциплиной «И»

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

На рис. 4 представлена начальная часть левой половины дерева состояний для сетевого графика с рис. 1, в котором узлы 2 и 4 имеют тип «ИЛИ», и в начальном состоянии дуга 1, исходящая из начального состояния, пройдена раньше дуги 2. Например, в вершине (34567) инициализируется дуга 5, ведущая в узел 2 типа «ИЛИ». Однако событие, соответствующее узлу 2, уже свершилось после прохождения дуги 1. По этой причине, исходя из сказанного выше, в вершине (34567) и во всех ее последователях отсутствуют исходящие дуги, помеченные 5.

Управление большими системами. Выпуск 65 Рис. 4. Дерево состояний графика со смешанной дисциплиной Таким образом, находя в дереве все состояния максимальной длины, получаем состояния с дугами, которые могут проходиться одновременно при некоторых наборах времен прохождения дуг. В дереве, приведенном на рис. 3, такими состояниями являются состояния (1 3 4 5), (3 4 6 7) и (4 6 8 9), что соответствует проведенному выше анализу. В левой части дерева состояний, приведенной на рис. 3, можно видеть все состояния, соответствующие наборам дуг, не содержащим дугу 1. Состояния, содержащие эту дугу, находятся в правой части дерева, не показанной на рис. 4. Из рис. 4 (в полном объеме) установлено, что точное значение степени параллелизма равно 5.

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

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

Имитационное моделирование сетевого графика, приведенного на рис. 1 с узлами типа «И», было проведено в иллюстративных целях. Была поставлена цель показать, что для распре

<

Системный анализ

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

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

Времена прохождения дуг, распределенных по нормальному закону N(а, ), ограниченному на интервалах (a – 3, a + 3), при следующих параметрах распределений: x1 = N(5, 52, 1), x2 = x5 = x7 = N(8, 1), x3 = N(6, 1), x4 = N(62, 1), x6 = N(102, 1), x8 = N(7, 1), x9 = N(3, 1), x10 = N(9, 1) (здесь хi – время прохождения i-й дуги) моделировались по методике, описанной в [3].

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

Оно показало, что вероятности появления состояний (1 3 4 5), (3 4 6 7) и (4 6 8 9) имеют следующие значения:

р1345 0,44, р3467 0,07, р4689 0. Таким образом, лишь с вероятностью 0,48 состояния длины 4 при данных распределениях по крайней мере один раз могут оказаться достижимыми.

Для приведенных выше распределений, с уменьшенными в 30 раз среднеквадратическими отклонениями, вероятности перечисленных выше состояний приняли нулевые значения. Необходимое число исполнителей, при котором отсутствуют очереди на прохождение дуг, оказалось равным трем. Этот же результат получен для детерминированных распределений вектора Х при нулевых среднеквадратических отклонениях.

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

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

Управление большими системами. Выпуск 65

Альтернативный метод позволяет для графиков со смешанными типами узлов получать точные значения степени параллелизма. Для ОССГ с узлами только типа «И» оба метода равнозначны по получаемым результатам.

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

3. Точное значение числа исполнителей, необходимое для отсутствия очередей, при распределениях, заданных на конечных интервалах, может быть получено при имитационном моделировании дерева состояний ОССГ. При этом не требуется предварительное построение дерева состояний: для каждого случайного вектора времен прохождения дуг программным путем находится траектория на дереве состояний с определением всех требуемых параметров (максимального числа одновременно проходимых дуг, времени выполнения графика, критического пути и т.п.). Однако этот способ является существенно более трудоемким по сравнению с определением степени параллелизма, особенно при использовании метода, описанного в п. 2.

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

4. Сетевые графики с видоизмененными узлами типа «ИЛИ»

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

Системный анализ На рис. 5 представлен фрагмент графика с видоизмененным узлом 1 типа «ИЛИ», в который первой приходит дуга 1. В этом случае прохождение дуги 2 приостанавливается, если оно уже началось. В противном случае дуга 3 может проходиться одновременно с дугами 4 и 5, чего не может быть в случае, если узел 1 типа «И». Однако по завершении прохождения дуг 4 и 5 прохождение дуги 2 не начнется.

Рис. 5. Фрагмент сетевого графика

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

Определение 2*. Дуги u и v сетевого графика с видоизмененными узлами типа «ИЛИ» находятся в отношении (uv), если они либо не связаны цепочкой, либо всякая непустая цепочка соединяющих их дуг, содержит хотя бы один узел типа «ИЛИ», для которого ни u, ни v не являются входными.

Для графика на рис. 1, в котором узлы 2 и 4 имеют видоизмененный тип «ИЛИ», матрица графа G имеет вид:

–  –  –

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

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

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

Литература

ГОЛЕНКО-ГИНЗБУРГ Д.И. Стохастические сетевые модели планирования и управления разработками. – Воронеж:

Научная мысль, 2010. – 283 с.

ЕЛИСЕЕВ В.В., ИГНАТУЩЕНКО В.В. Проблема надежного выполнения сложных наборов задач в управляющих параллельных вычислительных системах // Проблемы управления. – 2006. – №6. – С. 6–18.

ЕРМАКОВ С.М., МИХАЙЛОВ Г.А. Статистическое моделирование. – М.: Наука, 1982. – 296 с.

ИВАНОВ Н.Н., ИГНАТУЩЕНКО В.В., МИХАЙЛОВ А.Ю.

4.

Статическое прогнозирование времени выполнения комплексов взаимосвязанных работ в многопроцессорных вычислительных системах // Автоматика и телемеханика. – 2005. – №6. – С. 89–103.

ИВАНОВ Н.Н., ИГНАТУЩЕНКО В.В., МИХАЙЛОВ А.Ю.

5.

Вычисление оценок распределения времени выполнения комплексов взаимосвязанных работ в многопроцессорных вычислительных системах // Труды Института. – М.: ИПУ РАН, 2006. – Том XXVII. – С. 124–135.

Управление большими системами. Выпуск 65 ИВАНОВ Н.Н. Аналитико-имитационное моделирование 6.

обобщенных стохастических сетевых графиков // Управление большими системами. 2015. – Вып. 53. – С. 27–44.

7. ИВАНОВ Н.Н. Резервирование в параллельных вычислительных системах, выполняющих комплексы взаимосвязанных работ // Труды 6-й Международной конференции «Параллельные вычисления и задачи управления» (РАСО'2012, Москва). – М.: ИПУ РАН, 2012. – Т. 1. – С. 134–139.

8. ИВАНОВ Н.Н. Оптимальное резервирование в параллельных вычислительных системах, выполняющих комплексы взаимосвязанных работ // Труды XII Всероссийского совещания по проблемам управления (ВСПУ-2014, Москва). – М.: ИПУ РАН, 2014. – С. 7246–7255.

9. ИВАНОВ Н.Н., ШАСТУН В.В. Определение точных верхних оценок времени выполнения сложных наборов задач в управляющих параллельных вычислительных системах // Автоматика и телемеханика. – 2010. – №9. – С. 174–184.

10. ИГНАТУЩЕНКО В.В., ИСАЕВА Н.А. Резервирование взаимосвязанных программных модулей для управляющих параллельных вычислительных систем: организация, оценка отказоустойчивости, формализованное описание // Автоматика и телемеханика. – 2008. – №10. – С. 142–161.

11. ХАРАРИ Ф. Теория графов. – Москва: Мир, 1973. – 300 с.

12. BRON C., KERBOSH J. Algorithm 457– Finding all cliques of an undirected graph // Comm. of ACM. – 1973. – Vol. 16. – Р. 575–577.

–  –  –

THE DEGREE OF PARALLELISM IN GENERALIZED

STOCHASTIC NETWORK

Nikolay Ivanov, Institute of Control Sciences of RAS, Moscow, Doctor of Science (Moscow, Profsoyuznaya st., 65, ivanov.nni@yandex.ru).

Abstract: We propose a novel concept of parallelism degree for generalized stochastic networks. This concept could be used in design of real-time parallel computing systems. It characterizes the maximal load which does not lead to queue emergence. In the case when arc duration distributed according to arbitrary bounded distributions the parallelism degree estimates the minimum number of processors in the network at which no queues emerges on the network arcs. We also developed a method for finding this parameter.

Keywords: generalized stochastic network, path, distributions of arcs duration, Bron–Kerbosh algorithm.

–  –  –

Управление большими системами. Выпуск 65 УДК 519.7 ББК Ж 50

ДИНАМИЧЕСКАЯ КОМПЕНСАЦИЯ ВОЗМУЩЕНИЙ

В УСЛОВИИ НАСЫЩЕНИЯ

СИГНАЛА УПРАВЛЕНИЯ1

–  –  –

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

Приведены условия на параметры объекта и закона управления, при выполнении которых система управления будет работоспособной. Рассмотрен пример моделирования, иллюстрирующий работоспособность приведенной схемы.

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

Результаты раздела 2 получены в ИПМаш РАН при поддержке РНФ (проект №14-29-00142). Результаты разделов 4 и 5 получены при поддержке гранта Президента Российской Федерации (договор №14.W01.16.6325-МД Другие исследования (МД-6325.2016.8)).

частично поддержаны грантами РФФИ (№16-08-00282, №16-08МОН РФ (проект 14.Z50.31.0031) и Правительства РФ (074-U01).

Игорь Борисович Фуртат, доктор технических наук, доцент (Санкт-Петербург, Большой пр-т В.О., д. 61, тел. (812) 321-47-66, cainenash@mail.ru).

Анализ и синтез систем управления

1. Введение

Одним из эффективных способов управления объектами в условиях неопределенностей и возмущений является робастное управление с использованием наблюдателей с большим коэффициентом усиления (high-gain observer). В [1–3, 8] для оценки производных выходного сигнала объекта используются различные модификации данных наблюдателей. В [2] на базе результата [1] получена простая схема управления, представленная последовательным соединением апериодических и форсирующих звеньев. В [6] рассмотрено решение задачи компенсации возмущений с использованием динамического вспомогательного контура и наблюдателя, основанного на последовательном соединении реальных дифференцирующих звеньев. Результат [6] позволил получить в [7] простой регулятор, представленный передаточной функцией, знаменатель которой содержит нулевой корень и малый параметр.

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

Впервые задача управления в условиях неопределенности и насыщения сигнала управления была рассмотрена в [15].

Однако в [15] полученные результаты, касающиеся вопроса насыщения, не имеют строгого доказательства. В [6] на этапе моделирования системы, зная множество возможных значений параметров объекта, предлагалась методика выбора параметров в регуляторе. В [19] для решения задачи функция насыщения сигнала управления заменялась гиперболическим тангенсом от сигнала управления. В [18] предложено адаптивное управление объектами в условии неопределенности, где для частичной компенсации ограничений на сигнал управления параллельно ошибке слежения вводился вспомогательный контур с настраиваемым параметром. В [20] разработан статический Управление большими системами. Выпуск 65 закон управления при условии, что известна модель генератора возмущений. Получены линейные матричные неравенства, выполнение которых гарантирует устойчивость замкнутой системы. В [17] рассмотрено решение задачи управления линейными объектами при использовании H-подхода. Для обеспечения устойчивости замкнутой системы достаточно решения билинейных матричных неравенств.

Наиболее часто используемым методом управления в условиях насыщения сигнала управления является метод «anti-windup» [9, 11–14, 17]. Если в схеме регулирования используются интегральные составляющие, то в условиях насыщения сигнала управления переменные интегрирующего звена могут быть неограниченными (windup) [9, 12]. В данном случае работоспособность системы управления достигается введением контура, предотвращающего рост параметров в регуляторе (anti-windup, [9, 11–14, 17]).

В работах [9, 11–15, 17–20] используется принцип подавления возмущений за счет сильной обратной связи. В условиях ограничений сигнала управления использование сильной обратной связи может привести к потере устойчивости замкнутой системы. В отличие от [9, 11–15, 17–20], в представленной статье построение схемы управления основано на принципе компенсации возмущений, что позволит разработать закон управления, значение которого противоположно значению неопределенностей. В отличие от [2, 6, 7], в данной статье предложен новый закон динамической компенсации возмущений, частными реализациями которого являются решения [2, 6, 7]. При этом структура нового закона управления напрямую не зависит от динамического порядка объекта, что позволит управлять структурно неопределенными объектами.

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

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

2. Постановка задачи

–  –  –

j-я производная функции ym(t), j = 1, …, n; 0 – точность регулирования; T 0 – время, по истечении которого должно быть выполнено неравенство (2). Дополнительно условию (2), потребуем выполнение условия (3) u (t ) u, где u 0 – известная величина. Также необходимо, чтобы все переменные в замкнутой системе были ограниченными.

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

Предположения.

1. Неизвестные коэффициенты операторов Q(p), R(p) принадлежат известному ограниченному множеству.

Управление большими системами. Выпуск 65

2. Полином R() – гурвицев, где – комплексная переменная.

–  –  –

3. Синтез закона управления без учета насыщения сигнала управления Рассмотрим сначала синтез алгоритма динамической компенсации возмущений без учета ограничений (3).

Представим операторы Q(p) и R(p) в виде (4) R( p) R0 ( p) R( p), Q( p) Q0 ( p) Q( p), где Q0(p), R0(p) – произвольные известные линейные дифференциальные операторы, deg Q0 ( p) n, deg R0 ( p) m ;

многочлены Q0() и R0() – гурвицевы; Q(p) и R(p) – линейные дифференциальные операторы с неизвестными deg Q(p) deg Q0(p), deg R(p) m.

коэффициентами, Разложение (4), независимое от структуры эталонной модели, приведено в [5]. В частности, как отмечалось в [4, 5], полиномы Q0() и R0() можно выбирать согласно желаемому качеству переходных процессов в эталонной модели, т.е.

Q0(p)ym(t) = R0(p)r(t), где r(t) – гладкое задающее воздействие и deg Q0(p) – deg R0(p) = n – m.

Подставим (4) в (1) и составим уравнение для ошибки слежения e(t) = y(t) – ym(t) в виде Q0 ( p )e(t ) R0 ( p )u(t ) Q( p ) y (t ) (5) R( p )u(t ) Q0 ( p ) ym (t ) f (t ).

Обозначим (t) = f(t) – Q(p)y(t) + R(p)u(t) – Q0(p)ym(t) и перепишем уравнение (5) как (6) Q0 ( p)e(t ) R0 ( p)u(t ) (t ).

Из структуры (t) видно, что она содержит информацию о параметрической неопределенности и внешнем возмущении в (1). Введем оценку (t ) функции (t) в виде (7) (t ) Q0 ( p)e(t ) ( p) R0 ( p)u(t ), где () – гурицев полином порядка = deg Q0(p) – deg R0(p).

Анализ и синтез систем управления Зададим сигнал управления u(t) как (t ).

(8) u(t ) R0 ( p ) Подставив (7) в (8), перепишем (8) в виде (9) u(t ) 1 ( p) R0 1 ( p)Q0 ( p)e(t ).

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

Утверждение 1. Пусть выполнены условия Предположений 1–3. Тогда существуют (), R0() и Q0() такие, что для любых параметров (1) из класса закон управления (9) обеспечивает робастную устойчивость замкнутой системы и выполнение целевого условия (2).

Доказательство Утверждения 1 приведено в Приложении.

Замечание 1. Закон управления (9) не требует точного знания порядков операторов Q(p) и R(p). Поэтому, закон управления (9) работоспособен для класса линейных структурно неопределенных объектов (см., например, [4, 5]).

Замечание 2. Если в объекте (1) (p) = const, то получим результат, подобный [8]; если (p) = 1 – (Tp + 1), где T 0, то получим результат [2]. При (p) = 2 – (p + 1), где 0 – достаточно малое число, получим результат [6, 7].

4. Структура закона управления в условии насыщения входного сигнала

–  –  –

Управление большими системами. Выпуск 65 Принимая во внимание множество, воспользуемся условиями (12)–(14): |(0)| 1,1510–2, y m 0,21, 2,3108. Как отмечалось, эти условия достаточно грубые. Результаты моделирования показали, что система управления будет работоспособной, например, при ym 0,4, (0) 0,1 3 и = 107. Положим = 107. Рассмотрим объект управления (16) со следующими параметрами: q1 = –1, q2 = –4, q3 = 1, r = 1.

f(t) = 0,1 + 0,3sin t, y(0) 0,1, y(0) 0,1, (0) 0,1. Эталонный y сигнал ym(t) изображен на рис. 1а. На рис. 1б представлены результаты моделирования по e(t), на рис. 2 – по u(t).

–  –  –

Анализ результатов моделирования показал, что замкнутая система робастна по отношению к внешним возмущениям и параметрической неопределенности из заданного класса. В системе управления с начала ее функционирования динамическая ошибка не превышает значения 0,15. Из рис. 2 видно, что u(t) находится в заданном отрезке [–1; 1], тогда как без использования (17) (т.е. при u(t) = uc(t), см. [5, 6]) сигнал u(t) в начальный момент времени достигает значения –104, и только на 0,2 (с) u(t) входит в отрезок [–1,12; 1,12], что недопустимо по условию задачи.

Моделирование показало, что для обеспечения гурвицевости многочлена P() коэффициенты оператора (p) должны быть достаточно малыми, а также необходимо выполнение условия 0 ||1/()|| 1. Стоит отметить, что вместо рационального оператора (p) можно также использовать дробно-рациональные операторы или звено запаздывания.

6. Заключение

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

Управление большими системами. Выпуск 65 Предложена схема управления, обобщающая результаты [2, 6, 7] на случай структурной неопределенности модели объекта и возможности выбора структуры закона управления. Показано, что предложенный закон управления обеспечивает компенсацию параметрических и внешних возмущений. На базе функции, аппроксимирующей насыщение, предложен алгоритм управления в условиях ограничений на регулирующий сигнал. В отличие от [9, 11–15, 17–20], в статье получены условия на параметры объекта управления и регулятора, при выполнении которых схема управления будет работоспособной. Точность регулирования в установившемся режиме зависит от параметров модели объекта управления, закона управления и границ насыщения регулирующего сигнала. Приведены результаты моделирования, иллюстрирующие работоспособность схемы управления. Доказательство работоспособности закона управления базируется на лемме [10, 16], обобщенной для полиномов произвольного порядка.

7. Приложение

–  –  –

Q( p) ym (t ) f (t ).

Преобразуем последнее уравнение к виду P( p)e(t ) 1 ( p)R0 ( p) f (t ) Q( p) y m (t ), где P(p) = (1 – (p))R0(p)Q(p) + R(p)Q0(p). Очевидно, что замкнутая система устойчива, если полином P() гурвицев для любых значений параметров объекта (1) из множества.

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

Лемма. Пусть заданы многочлены D(), T() порядков w и l соответственно. Тогда существуют многочлены K() и G() Анализ и синтез систем управления

–  –  –

1. Предположим, что в процессе функционирования системы ~ uc (t ) u. Тогда из (10) следует, что u(t) = uc(t). Значит, будут выполнены условия утверждения 1. Выясним, при каких параметрах объекта и системы управления первый случай будет справедлив. Перепишем (5) в виде (П.6) e(t ) Q0 1 ( p) R0 ( p)1 ( p)uc (t ).

–  –  –

БОБЦОВ А.А. Синтез закона управления для стабилизации 1.

нелинейной системы по измерениям выхода // Известия РАН. Теория и системы управления. – 2004. – №3. – С. 40–45.

БОБЦОВ А.А., ШАВЕТОВ С.В. Управление по выходу 2.

линейным параметрически неопределенным объектом в условиях возмущающих воздействий и неучтенной динамики // Научно-технический вестник СанктПетербургского государственного университета информационных технологий, механики и оптики. – 2011. – №1(71). – С. 33–39.

МИРОШНИК И.В., НИКИФОРОВ В.О., ФРАДКОВ А.Л.

3.

Нелинейное и адаптивное управление сложными динамическими системами. – СПб: Наука, 2000. – 549 с.

ФУРТАТ И.Б., ЦЫКУНОВ А.М. Адаптивное управление 4.

объектами с неизвестной относительной степенью // Автоматика и телемеханика. – 2010. – №6. – С. 109–118.

ФУРТАТ И.Б., ЦЫКУНОВ А.М. Робастное управление 5.

нестационарными нелинейными структурно неопределенными объектами // Проблемы управления. – 2008. – №5. – С. 2–7.

ЦЫКУНОВ А.М. Алгоритм робастного управления 6.

линейными динамическими объектами по выходу // Мехатроника, автоматизация, управление. – 2010. – №3. – С. 9–14.

ЦЫКУНОВ А.М. Алгоритм робастного управления 7.

нестационарным линейным объектом с компенсацией возмущений // Известия РАН. Теория и системы управления. – 2008. – №4. – С. 33–40.

8. ATASSI A.N., KHALIL H.K. A separation principle for the stabilization of class of nonlinear systems // IEEE Trans. on Automat. Control. – 1999. – Vol. 44, No. 9. – P. 1672–1687.

9. EDWARDS C., POSTLETHWAITE I. Anti-windup and Bumpless-transfer Schemes // Automatica. – 1998. – Vol. 34, No. 2. – P. 199–210.

Анализ и синтез систем управления

10. FEUER A., MORSE A.S. Adaptive control of single-input, single-output linear systems // IEEE Trans. on Automat.

Control. – 1978. – Vol. AC-23, No. 4. – P. 557–569.

11. KANEKO K., OHISHI K. Anti-windup robust controller considering motor dynamics for speed servo system // IEEE Int.

Conference on Mechatronics (ICM-2013), Vicenza, VI, Italy. – 2013. – P. 694–699.

12. KAPASOURIS P., ATHANS M. Multivariable Control Systems with Saturating Actuators Antireset Windup Strategies // American Control Conf. – Boston. – 2004. – P. 1579–1584.

13. LEONOV G.A., ANDRIEVSKII B.R., KUZNETSOV N.V., POGROMSKII A.YU. Aircraft Control with Anti-Windup Compensation // Differential Equations. – 2012. – Vol. 48, No. 13. – P. 1700–1720.

14. LOZIER J.C. A steady-state approach to the theory of saturable servo systems // IRE Trans. on Automatic Control. – 1956. – May. – P. 19–39.

15. MONOPOLI R. Adaptive Control for Systems for Hard Saturation // 14th IEEE Conf. on Decision and Control. – Houston, TX. – 1975. – P. 841–842.

16. NARENDRA K.S., VALAVANI L.S. Stable Adaptive Controller Design – Direct Control // IEEE Trans. on Automat.

Control. – 1978. – Vol. AC-23, No. 4. – P. 570–583.

17. PATRA S., SEN S., RAY G. Robust control of uncertain LTI plant with input saturation constraint: H- loop-shaping approach // Int. J. of Systems Science. – 2010. – Vol. 41, No. 11. – P. 1337–1351.

18. SCHWAGER M., ANNASWAMY A.M. Direct Adaptive Control of Multi-Input Plants with Magnitude Saturation Constrains // 44th IEEE Conf. on Decision and Control, and the European Control Conf. – Seville, Spain. – 2005. – P. 783–788.

19. WEN C., ZHOU J., LIU Z., SU H. Robust Adaptive Control of Uncertain Nonlinear Systems in the Presence of Input Saturation and External Disturbance // IEEE Trans. on Automatic Control. – 2011. – Vol. 56, No. 7. – P. 1672–1678.

Управление большими системами. Выпуск 65

20. YANG Q., CHEN M. Robust Control for Uncertain Linear System Subject to Input Saturation // J. of Applied Mathematics. – 2014. –Vol. 2014. – Article ID 803842. – 12 p.

–  –  –

Igor Furtat, Institute of Problems of Mechanical Engineering Russian Academy of Sciences, ITMO University, Dr.Sc., assistant professor (cainenash@mail.ru).

Abstract: The new algorithm for dynamic compensation of disturbances for linear plants with single input and single output under conditions of parametric uncertainty and external bounded disturbances is proposed. We consider the problem of tracking the plant output to the reference signal without measuring output derivatives. The algorithm is generalized to the given constraints on the control signal. We formulate the conditions depending on the parameters of the plant and the control signal which allow to ensure the stability of the closed loop system. The simulation results illustrate efficiency of the proposed algorithm.

Keywords: robust control, disturbances compensation, control signal constraints.

–  –  –

УДК 681.51 ББК Ж 50

РОБАСТНОЕ УПРАВЛЕНИЕ ЛИНЕЙНЫМИ

МУЛЬТИАГЕНТНЫМИ СИСТЕМАМИ

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

ДЛЯ ОЦЕНКИ ПРОИЗВОДНЫХ1

–  –  –

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

Ключевые слова: робастное управление, задержка, линейноматричные неравенства (LMI), функционал Ляпунова– Красовского, дескрипторный метод.

Результаты раздела 3 получены в ИПМаш РАН при поддержке РНФ (проект №14-29-00142). Результаты разделов 4 и 5 получены при поддержке гранта Президента Российской Федерации (договор №14.W01.16.6325-МД (МД-6325.2016.8)). Другие исследования частично поддержаны грантами РФФИ (№16-08-00282, №16-08-00686), МОН РФ (проект 14.Z50.31.0031) и Правительства РФ (074-U01).

Игорь Борисович Фуртат, доктор технических наук, доцент (cainenash@mail.ru).

Артём Николаевич Нехороших, инженер (becks94@mail.ru).

Управление большими системами. Выпуск 65

1. Введение

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

Для оценки вектора состояния модели объекта с известными параметрами при отсутствии внешнего возмущения широко используется наблюдатель Люенбергера [10]. В [9] предложен фильтр Калмана, оценивающий вектор состояния динамической системы при использовании ряда неполных и зашумленных измерений. В условиях параметрической неопределенности модели объекта и наличия внешних возмущений в [5] был предложен робастный наблюдатель с большим коэффициентом усиления (high-gain observer). Другой вид наблюдателя с большим коэффициентом усиления позже был рассмотрен в [1].

В [11, 12] предложен робастный наблюдатель на скользящем режиме (sliding-mode observer). В [8] разработан нелинейный наблюдатель расширенного состояния (nonlinear extended state observer), основанный на обобщении наблюдателя с большим коэффициентом усиления и наблюдателя на скользящем режиме. В [14] представлен обзор наблюдателей [5, 8, 10–12], примеры расчета и реализации для динамической системы второго порядка, а также приведен сравнительный анализ для каждого наблюдателя при различных видах неопределенностей (параметрическая неопределенность, внешние возмущения и шумы).

Робастные наблюдатели [1, 5, 8, 10–12] нашли широкое применение при синтезе систем управления в условиях неопреАнализ и синтез систем управления деленности. Например, в [13] строится закон управления с оценкой производных выхода объекта, которые реализуются с помощью динамического наблюдателя на скользящем режиме [11, 12], где порядок наблюдателя равен размерности вектора состояния модели объекта. В [4] для синтеза системы стабилизации нелинейных динамических объектов используется закон управления, зависящий от оценок производных выхода объекта, которые получены с помощью динамического наблюдателя с большим коэффициентом усиления [5] и порядком, равным размерности вектора состояния модели. В [1] синтезируется робастный закон управления по ошибке слежения, где для оценки производных сигнала ошибки слежения используется наблюдатель с динамическим порядком, равным 1, где – относительная степень объекта управления. В [3] синтезирована робастная система управления с компенсацией внутренних и внешних возмущений с использованием вспомогательного контура. Для оценки производных сигнала, несущего в себе информацию о возмущениях объекта, в [3] используется динамический наблюдатель [5], порядок которого равен 1.

В [2] предложен регулятор, где для оценки производных используется алгоритм с левыми разностями. В отличие от регуляторов, рассмотренных выше, алгоритм [2] обладает простой структурой, прост в расчете и реализации системы управления и доставляет замкнутой системе требуемые показатели качества. Простота регулятора [2] заключается в его последовательной структуре, т.е. отсутствии обратных связей, имеющихся в регуляторах [1, 3–5, 8–13]. Простота реализации заключается в наличии только звеньев с запаздыванием в составе регулятора.

Данные качества являются важными при построении системы управления большой группой объектов и позволяют значительно уменьшить общую сложность системы управления. Поэтому статья посвящена обобщению применения регулятора [2] на случай децентрализованного управления линейной мультиагентной системой.

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

2. Постановка задачи

–  –  –

p k 1 yi 0 yi 0 k, k 1,..., ni, i, j 1,, N, где yi(t) R – регулируемая переменная; ui(t) R – сигнал управления; fi(t) R – внешнее неконтролируемое ограниченное возмущение; Qi(p), Ri(p), Yij(p) – линейные дифференциальные операторы с неизвестными коэффициентами, deg Qi(p) = ni, deg Ri(p) = mi, deg Yij(p) = nij, ni mi, ni nij, nj nij; ki 0;

yi0k – неизвестные начальные условия; p = d/dt – оператор дифференцирования.

При решении задачи на агенты (1) наложены следующие ограничения.

Предположение 1. Неизвестные коэффициенты операторов Qi(p), Ri(p), Yij(p) и числа принадлежат известному ограниченному множеству возможных значений.

Предположение 2. Многочлены Ri() – гурвицевы, где

– комплексная переменная.

Предположение 3. Доступны измерению сигналы yi(t) и ui(t), но не их производные.

Требуется спроектировать непрерывную систему управления, обеспечивающую слежение выхода каждого агента yi(t) за эталонным сигналом ymi(t) так, чтобы было выполнено целевое условие (2) yi t ymi t при t T,

–  –  –

где ymi(t) – гладкая функция, ограниченная вместе со своими производными, 0, T 0 – время, начиная с которого должно быть выполнено целевое условие (2).

3. Управление структурно определенными объектами

–  –  –

Для формулировки главного результата введем еще следующие обозначения:

Rvj 0, j v = 1, …, – матрицы соответствующих размерностей; I – единичная матрица.

Утверждение 1. Выполнены условия предположений 1–3.

Задано число 0. Если существуют 0 и матрицы P 0, P2 0, P3 0, Svj 0, Rvj 0, j v = 1, …,, такие что матрица 0, тогда система управления, представленная законом управления (7), обеспечивает выполнение целевого условия (2) с точностью в установившемся режиме

–  –  –

Доказательство утверждения приведено в Приложении.

Отметим, что оценка (12), записанная в форме [6, 7], не зависит от h. Однако выражение (12) зависит от min (P), где P является решением линейного матричного неравенства (h) 0.

4. Управление структурно неопределенными объектами Теперь рассмотрим случай, когда порядки операторов Qi(p), Ri(p), Yij(p) неизвестны. Для решения задачи на систему (1) дополнительно к предположениям 1–3 наложим следующее ограничение.

Предположение 4. Известны верхние оценки i относительной степени i, т.е. i i.

Цель управления состоит в выполнении условия (2).

Принимая во внимание уравнения (1) и (2), сформируем ошибку слежения ei(t) = yi(t) ymi(t) в виде (3).

Зададим закон управления в форме i (13) ui t i d vi eiv t, i 1,, N, v 0 где i 0, коэффициенты d0i, d1i,, d i i выбираются так, чтобы полиномы Di d i i i d i 1i i 1 d1i d0i были гурвицевыми. Подставив (13) в (3), получим уравнение вида (5).

Очевидно, что всегда существуют числа i и полиномы Di() такие, что полиномы Fi() будут гурвицевыми.

Для оценки производных сигнала ei(t) воспользуемся следующими уравнениями Из рис. 1 видно, что заданная точность = 0,01 достигается первой системой за время t1 = 1,68 с, второй за t1 = 1,05 с.

На рис. 2 представлены результаты моделирования по ошибке ei(t) = yi(t) ymi(t) при i = 25 и h = 0,01, i = 1, 2.

–  –  –

Управление большими системами. Выпуск 65 Из рис. 3 видно, что заданная точность = 0,01 достигается первой системой за время t1 = 1,68 с, второй за t2 = 0,10 с.

На рис. 4 представлены результаты моделирования по ошибке ei(t) = yi(t) ymi(t) при i = 25 и h = 0,01, i = 1, 2.

Из рис. 4 видно, что заданная точность = 0,01 достигается первой системой за время t1 = 0,33 с, второй за t2 = 0,04 с.

Таким образом, уменьшение времени h позволяет увеличить точность системы управления так же, как и в случае со структурно определенными объектами.

–  –  –

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

В отличие от [1, 3–5, 8–14] в данной статье для оценки производных использовался наблюдатель, приближенное дифференцирование в котором осуществлялось с помощью левых разностей, что позволило сформировать систему управления, не содержащую динамических составляющих.

Полученный алгоАнализ и синтез систем управления ритм компенсирует неопределенности и возмущения с заданной точностью, зависящей от выбора коэффициентов полинома D(p) и коэффициента, а также величины параметра h, определяющего точность оценки производных сигнала e(t). Так как предлагаемый алгоритм управления использует звенья с запаздыванием, то их практическая реализация может быть осуществлена, например, на базе ЭВМ с использованием специального программного обеспечения, например MatLab.

Литература

БОБЦОВ А.А. Алгоритм робастного управления в задаче 1.

слежения за эталонным сигналом // Автоматика и телемеханика. – 2003. – №6. – С. 104–113.

ФУРТАТ И.Б. Робастный статический алгоритм управления линейными объектами // Автоматика и телемеханика. – 2015. – №3 – С. 94–107.

ЦЫКУНОВ А.М. Алгоритмы робастного управления с 3.

компенсацией ограниченных возмущений // Автоматика и телемеханика. – 2007. – №7. – С. 103–115.

4. ATASSI A.N., KHALIL H.K. A separation principle for the stabilization of class of nonlinear systems // IEEE Trans. Automat. Control. – 1999. – Vol. 44, №9. – P. 1672–1687.

5. ESFANDIARY F., KHALIL H.K.Output feedback stabilization of fully linearizable systems // Int. J. Control. – 1992. – Vol. 56, №5. – P. 1007–1037.

6. FRIDMAN E. Introduction to Time-Delay Systems. Analysis and Control. – Basel: Birkhauser, 2014. – 362 p.

7. FRIDMAN E. Tutorial on Lyapunov-based methods for timedelay systems // European Journal of Control. – 2014. – Vol.

20. – P. 271–283.

8. HAN J. A class of extended state observers for uncertain system // Control Decision. – 1995. – Vol. 10, №1. – P. 85–88.

9. KALMAN R.E. A new approach to linear filtering and prediction problems // Trans. ASME – J. Basic Engineer. – 1960. – №82 (Ser. D). – P. 35–45.

Управление большими системами. Выпуск 65

10. LUINBERGER D. Observers for multivariable systems // IEEE Trans. Automat. Control. – 1966. – Vol. AC-11, №2. – P. 190–197.

11. SLOTINE J.J.E., HEDRICK J.K., MISAWA E.A. On sliding observers for nonlinear systems // J. Dynam. Syst., Measurement, Control. – 1987. – Vol. 109. – P. 245–252.

12. UTKIN V.I. Sliding modes in control and optimization. – Berlin: Springer-Verlag, 1992 – 286 p.

13. VELUVOLU K.C., KIM M.Y., LEE D. Nonlinear sliding mode high-gain observers for fault estimation // Int. J. Syst. Sci. – 2011. – Vol. 42, №7. – P. 1065–1074.

14. WANG W., GAO Z. A comparison study of advanced state observer design techniques // Proc. Amer. Control Conf. – 2003. – P. 4754–4759.

Приложение Доказательство утверждения 1. Для доказательства утверждения 1 воспользуемся вспомогательной леммой.

Лемма [2]. Рассмотрим динамическую систему, описываемую дифференциальным уравнением (П.1) xt Axt f t g xt, xt 1,, xt n,, где x(t) Rn, A Rnn – гурвицева матрица, x(t) Rn – ограниченная функция, i 0 – время запаздывания, i = 1, …, n, g(x(t), x(t 1), …, x(t n), ) Rn – непрерывная функция по совокупности аргументов за исключением, может быть, случая, когда = 0, причем g(x(t), x(t 1), …, x(t n), ) 0 при 0 и g(0, 0, …, 0, ) = 0. Дополнительно функция g() удовлетворят условию Липшица g x1 t, x1 t 1,..., x1 t n, g x2 t, x2 t 1,..., x2 t n, (П.2) L0 x1 t x2 t L1 x1 t 1 x2 t 1... Ln x1 t n x2 t n, где L0(), L1(), …, Ln() – липшицевы константы, причем lim Li 0, i = 1, …, n.

–  –  –

ROBUST ALGORITHM USING DELAY FOR MULTIAGENT SYSTEMS

Igor Furtat, Institute for Problems of Mechanical Engineering RAS, St.-Petersburg, ITMO University, St.-Petersburg, Doctor of Science, assistant professor (cainenash@mail.ru).

Artem Nekhoroshikh, ITMO University, St.-Petersburg, engineer (becks94@mail.ru).

Abstract: The paper describes a robust control algorithm for linear multi-agent systems under parametric and structural uncertainties and external unmeasured disturbances. The algorithm includes an observer component which uses left hand side differences for estimation of the derivatives. This allowed us to form a control system without dynamic components. The resulting algorithm ensures required accuracy of difference between the plant output and the reference signal. The simulation results illustrate the effectiveness of the algorithm.

Keywords: robust control, time delay, LMI, LyapunovKrasovskii functional, descriptor method.

–  –  –

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

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

Ключевые слова: динамические кратчайшие расстояния, актуализация графа, коррекция графа, равноудаленные точки.

Введение Задачи, связанные с поиском кратчайших путей (и расстояний, ассоциированных с этими путями), являются одними из самых исследованных в теории графов. В классической (статической) задаче поиска кратчайших путей между всеми вершинами графа (задача APSP) предполагается, что исследуемый граф – его Айрат Ренатович Ураков, кандидат физико-математических наук, доцент (urakov@ufanet.ru).

Тимофей Валерьевич Тимеряев (timeryaev@yandex.ru).

Информационные технологии в управлении структура и веса ребер (дуг) – не меняются с течением времени.

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

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

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

1. Термины и обозначения

–  –  –

2. Существующие алгоритмы Первые алгоритмы решения динамических задач поиска кратчайших путей опубликованы в 60–70-х годах прошлого столетия [1, 8, 18, 19]. Алгоритмы в этих работах на основе свойств кратчайших путей определяют пары вершин, между которыми в результате изменения весов ребер могли измениться расстояния. Расстояния между найденными парами пересчитывается с использованием простых алгебраических и логических операций, а также статических алгоритмов поиска кратчайших путей. Временные сложности этих алгоритмов в худшем случае определяются случаем увеличения веса ребра и не дают улучшения по сравнению с полным пересчетом расстояний графа с использованием статических методов.

Информационные технологии в управлении Авторы [22] представили полностью динамический алгоритм, поддерживающий множественные изменения весов ребер между актуализациями расстояний. В [12] предложили полностью динамический алгоритм для задачи с единственным источником и наибольшей эффективностью на планарных графах и графах с ограниченной степенью вершин. Алгоритмы, улучшающие временную сложность полного пересчета расстояний, были предложены для графов с ограниченными весами ребер [3, 17] и планарных графов [11, 16]. В [7] авторы переложили полностью динамический алгоритм для направленных графов с неотрицательными весами с амортизированным временем (2 3 | |) для любой последовательности модификаций графа.

Алгоритмы приближенного решения задачи рассмотрены в [4, 15, 24]. Многие алгоритмы, решающие динамическую задачу, хранят вспомогательную информацию, используемую при пересчете расстояний, что требует большого объема оперативной памяти при практической реализации и тем самым ограничивает размерность используемых графов. Для возможности работы с большими графами рядом авторов предложены алгоритмы [14, 21], хранящие вспомогательную информацию под управлением СУБД. Распределенные алгоритмы решения задачи рассматриваются в [5, 23].

3. Метод коррекции графа

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

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

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

Во втором случае сперва добавляется новое ребро большего веса, что не влияет на расстояния (и не требует пересчета), после этого удаляется существующее ребро меньшего веса.

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

4. Добавление ребра

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

Добавляемое ребро (0, 0 ) можно представлять как «мост», соединяющий множества вершин = { } и = { }, которые разбивают множество вершин графа на вершины, которые ближе к 0, и вершины, которые ближе к 0 :

= { |(, 0 ) (, 0 )}, (1) = { |(, 0 ) (, 0 )}.

В случае равенства расстояний до 0 и до 0 вершина может быть помещена в любое из множеств,. Будем считать, что 0 и 0. При разбиении вершин графа (1), добавляя Информационные технологии в управлении ребро (0, 0 ), достаточно пересчитать расстояния лишь между парами вершин одна из которых принадлежит, а другая, т.е. (, ) :,. Если обе вершины принадлежат одному из множеств, например,,, то расстояние между ними не изменится. Это обусловлено двумя факторами. Вопервых, добавление ребра (0, 0 ) не изменит принадлежность вершин множеству : расстояние от них до 0 все так же будет не больше чем до 0. Действительно, если бы расстояние от, например, до 0 изменилось, соответствующий путь имел бы вид [,..., 0, 0 ], что означало бы, что (, 0 ) (, 0 ). Во-вторых, кратчайший путь между и не может содержать добавляемое ребро (0, 0 ), так как расстояние от обоих и до 0 не больше чем до 0, и кратчайший путь [,..., ] между и в противном случае содержал бы подпуть вида [,..., 0, 0 ], который не является кратчайшим, что противоречило бы свойству оптимальности кратчайшего пути.

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

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

Предположим, что вершина дерева в направлении от Управление большими системами. Выпуск 65 корня дерева связана ребрами с вершинам +1, +2,..., +.

Также предположим, что в данный момент времени мы пересчитываем расстояние между и некоторой вершиной дерева.

Расстояние между и необходимо пересчитать, если длина пути через добавляемое ребро (0, 0 ) будет меньше текущего расстояния между и, т.е. если выполняется условие (, 0 ) + (0, 0 ) + (0, ) (, ).

(2) Если неравенство (2) не выполняется, величина (, ) не пересчитывается, так как существует путь между и, не проходящий через (0, 0 ) и обладающий не большей длиной. Но в этом случае не надо также пересчитывать расстояния между и вершинами +1, +2,..., +.

Действительно, так как дерево является деревом кратчайших путей, то в случае пересчета расстояния между, например, +1 и соответствующий кратчайший путь имел бы вид [+1,,..., 0, 0,..., ].

(3) Если расстояние между и не было пересчитано, потому что выражение (2) имело форму равенства, то нет необходимости пересчитывать и расстояние между +1 и, так как оно не изменится (не изменится длина подпути [,..., ]). Если же путь между и через (0, 0 ) оказался длиннее, чем путь не проходящий через (0, 0 ), то кратчайший путь между +1 и не может иметь вида (3), так как в этом случае кратчайший путь между +1 и содержал бы не кратчайший подпуть [,..., 0, 0,..., ] между и, что нарушало бы свойство оптимальности кратчайшего пути.

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

Информационные технологии в управлении

соответственно, вершины и, удовлетворяющие условиям (, 0 ) + (0, 0 ) (, 0 ), (4) (, 0 ) + (0, 0 ) (, 0 ).

Схематическое изображение деревьев и представлено на рис. 1. Описание алгоритма пересчета расстояний при добавлении ребра дано в листингах Алгоритм 1, Алгоритм 2. Алгоритмы в данных листингах предполагают, что текущие расстояния между всеми парами вершин графа до добавления ребра (0, 0 ) известны.

–  –  –

Временная сложность сложность строк 6, 7 равна (| | + ||).

Выбор и добавление вершин в очереди в строках 10, 13, 19 и 21 производится не больше | | раз, что с учетом вложенности цикла в строках 12-19 дает временную сложность выполнения строк 9–21 равную (| |2 ). То есть алгоритм 2 имеет временную сложность (| |2 + ||). Пространственная сложность алгоритма 2 доминируется пространственной сложностью алгоритма 1 и равна (| |2 + ||).

5. Алгоритм поиска кратчайших расстояний путем добавления ребер к остовному дереву

–  –  –

тельскую вершину вершины :

(, ) = (, ) + (, ).

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

Согласно результатам, можно сделать вывод:

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

Описание алгоритма определения расстояний между всеми парами вершин графа с использованием алгоритма пересчета расстояний при добавлении ребра приведено в листингах Алгоритм 3, Алгоритм 4.

Алгоритм 4 (Расчет расстояний между всеми вершинами).

ВычислитьРасстояния (, ) 1. = Очередь() // содержит не посещенные ребра 2. = ВыбратьДерево(, ) // заполняется

3. ВычислитьРасстоянияДерева (, )

4. Пока.Размер() 0 =.Выбрать() 5.

0 =.Вершина1() 6.

0 =.Вершина2() 7.

=.Вес() 8.

ДобавитьРебро (,, 0, 0, ) 9.

В алгоритме 3 цикл в строках 3–11 выполняется | | раз – по разу для каждой вершины дерева. Вложенный цикл в строках Информационные технологии в управлении 7–9 выполняется в худшем случае | | 1 раз. Таким образом, временная сложность алгоритма 3 равна (| |2 ). Однако время работы данного алгоритма может быть улучшено до линейного с помощью нахождения всех наименьших общих предков дерева [13]. В алгоритме 4 строка 2 выполняется за (| | + ||) (поиск в ширину), строка 3 за (| |2 ), цикл в строках 4–9 за (||| |2 + ||2 ). Таким образом временная сложность алгоритма 4 равна (||| |2 + ||2 ), пространственная сложность определяется строкой 9 и равна (| |2 + ||).

6. Удаление ребра и равноудаленные точки

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

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

Размеры деревьев и можно уменьшить, но для этого вместо неравенств (4) следует использовать следующие равенства:

(, 0 ) + (0, 0 ) = (, 0 ), (5) (, 0 ) + (0, 0 ) = (, 0 ).

Равенства (5) оставляют в деревьях и только те вершины и, для которых существует кратчайший путь до, соответственно, вершин 0 и 0, проходящий через ребро (0, 0 ).

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

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

На каждом из альтернативных путей между вершинами 0 и 0 существует точка, от которой расстояние до 0 и до 0 одинаково. Будем называть такие точки равноудаленными точками (РУТ). Используя РУТ можно обозначить все возможные варианты альтернативных путей между 0 и 0, ставя в соответствие каждому варианту отличную РУТ. Набор РУТ также определит и все возможные варианты альтернативных путей, не проходящих через ребро (0, 0 ), между всеми парами вершин деревьев и. Действительно, пути между вершинами и через РУТ представляют собой пути, в которых вместо ребра (0, 0 ) содержится подпуть через РУТ. Будем обозначать РУТ = { }, рис. 2 представляет схематическое изображение множества РУТ.

Существует 2 варианта расположения РУТ. Во-первых, РУТ, находящиеся в вершинах графа. Для таких справедливо равенство (, 0 ) = (, 0 ).

(6) Во-вторых, РУТ, находящиеся на ребрах. Такие РУТ находятся на ребрах (, ), удовлетворяющим всем трем неравенствам |(, 0 ) (, 0 )| (, ), (, 0 ) (, 0 ), (7) (, 0 ) (, 0 ).

Расстояния между РУТ на ребрах и некоторой вершиной Информационные технологии в управлении

–  –  –

пересчета расстояний), если использовать не расстояния до РУТ, а приращения (увеличения) расстояний через РУТ.

Будем обозначать (, ) и называть приращением расстояния (, ) увеличение расстояния (, ) после удаления ребра (0, 0 ). Тогда новое расстояние между и после удаления (0, 0 ) определяется по формуле (, ) = (, ) + (, ).

–  –  –

(, 0 ) (, 0 ) (, ), (, 0 ) (, 0 ) = (, 0 ) (, 0 ) (, ), (, ) (, 0 ) + (, 0 ), (, ) (, 0 ) + (0, ) = (, 0 ) + (, 0 ).

–  –  –

ность алгоритма 5 равна (| |3 ), пространственная сложность, как и в предыдущих алгоритмах, равна (| |2 + ||).

7. Вычислительный эксперимент Практическая эффективность предложенного метода актуализации расстояний в динамическом графе была оценена с помощью вычислительного эксперимента. В качестве тестовых данных использовались случайные связные подграфы заданной размерности графов автомобильных дорог европейских стран из проекта OpenStreetMap [20]. Эксперимент состоял в удалении случайного ребра, которое не нарушает связности графа, и последующем добавлении этого ребра обратно к графу, при этом фиксировалось время актуализации расстояний после каждой операции. Данная процедура повторялась 100 раз, после чего определялось среднее время актуализации расстояний каждым из сравниваемых алгоритмов. Исходный код предложенных в статье алгоритмов (ДУТ), алгоритма Дейкстры (СД) и алгоритма разборкисборки графа (СРС) был написан на языке C++, код остальных тестируемых в статье алгоритмов был реализован на языке C.

При компиляции использовался 64-битный компилятор MS Visual Studio 2013 c флагом оптимизации O2. Тесты проводились на ЭВМ с процессором Intel Core i5-4690K и объемом оперативной памяти 24 Гбайт.

Предложенные алгоритмы пересчета расстояний (ДУТ) при добавлении ребра (уменьшении веса ребра) и удалении ребра (увеличение веса ребра) сравнивались с решением задачи статическими алгоритмами – полным пересчетом расстояний: кратным (по числу вершин графа) запуском алгоритма Дейкстры (СД); алгоритмом разборки и сборки графа ([2], СРС); основанном на алгоритме Дейкстры методом, просматривающем только ребра, содержащиеся в локально кратчайших путях ([6], СЛКП).

Также было произведено тестирование быстрых динамических алгоритмов [6]: адаптации алгоритма Кинга ([17], ДК) без ограничения на максимальный вес ребра в графе с временной и пространственной сложностями (2,5 ); алгоритма РамалинИнформационные технологии в управлении

–  –  –

Управление большими системами. Выпуск 65 гама и Репса ([22], ДРР), использующего при пересчете хранимую информацию о кратчайших путях, с временной сложностью (+2 ) и пространственной сложностью (2 ); алгоритма Деметреску и Италиано ([7], ДДИ), пользующегося при актуализации расстояний исторически локальными путями с временной сложностью (2 ) и пространственной сложностью ().

–  –  –

В эксперименте использовалась реализация алгоритма Дейкстры с двоичной кучей из библиотеки Boost Graph Library [25]. Алгоритмы СЛКП, ДК, ДРР и ДДИ использовались в реализации [10]. В тех случаях, когда алгоритмы в реализации [10] не смогли завершить вычисления из-за ошибок в авторском коде, в таблицах стоит прочерк. Характеристики тестовых графов и среднее время актуализации расстояний статическими алгоритмами представлены в таблице 1. Среднее время актуализации расстояний динамическими алгоритмами после удаления и добавления ребра представлены в таблицах 2 и 3 соответственно. Таблица 4 содержит данные о среднем объеме используемой оперативной памяти динамическими алгоритмами. В таблице 5 содержатся дополнительные данные о результатах тестирования разработанного алгоритма ДУТ.

Информационные технологии в управлении

–  –  –

Полученные результаты свидетельствуют о том, что предложенные алгоритмы позволяют существенно сократить время актуализации расстояний после удаления ребра в сравнении с рассмотренными алгоритмами. Так, например, для графов размерности 104 время счета меньше в среднем в 6 раз. Быстрейший пересчет расстояний после добавления ребра производит алгоритм ДК, однако из-за ошибок в авторском коде [10] не ясна его скорость на графах размерности больше 2 · 103. Еще одним важным практическим преимуществом предложенных алгоритмов является использование гораздо меньшего объема оперативной памяти в сравнении с другими динамическими алгоритмами.

8. Заключение

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

–  –  –

изменении весов отдельных ребер.

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

–  –  –

4. BASWANA S., HARIHARAN R., SEN S. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths // Journal of Algorithms. – 2007. – Vol. 62, №2. – P. 74–92.

5. CICERONE S., DI STEFANO G., FRIGIONI D., NANNI U.

A fully dynamic algorithm for distributed shortest paths // Theoretical Computer Science. – 2003. – Vol. 297, №1–3. – P. 83–102.

6. DEMETRESCU C., EMILIOZZI S., ITALIANO G.F.

Experimental analysis of dynamic all pairs shortest path algorithms // Proc. of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. – Philadelphia: Society for Industrial and Applied Mathematics, 2004. – P. 362–371.

7. DEMETRESCU C., ITALIANO G.F. A new approach to dynamic all pairs shortest paths // Journal of the ACM. – 2004. – Vol. 51, №6. – P. 968–992.

8. DIONNE R. Etude et extension d’un algorithme de Murchland // INFOR. – 1978. – №169. – P. 132–146.

9. EVEN S., GAZIT H. Updating distances in dynamic graphs // Methods of Operations Research. – 1985. – №49. – P. 371–387.

10. Experimental Evaluation of Dynamic All Pairs Shortest

Path Algorithms [Электронный ресурс]. – URL:

http://www.dis.uniroma1.it/~demetres/experim/dsp/ (дата обращения: 27.12.2016).

11. FAKCHAROEMPHOL J., RAO S. Planar graphs, negative weight edges, shortest paths, and near linear time // Journal of Computer and System Sciences. – 2006. – Vol. 72, №5. – P. 868–889.

12. FRIGIONI D., MARCHETTI-SPACCAMELA A., NANNI U. Fully dynamic algorithms for maintaining shortest paths trees // Journal of Algorithms. – 2000. – №34. – P. 351–381.

Управление большими системами. Выпуск 65

13. GABOW H., TARJAN R. A linear-time algorithm for a special case of disjoint set union // Journal of Computer and System Sciences. – 1985. – Vol. 30, №2. – P. 209–221.

14. GRECO S., MOLINARO C., PULICE C. Fully dynamic algorithms for maintaining shortest paths trees // Proc. of the 28th International Conference on Scientific and Statistical Database Management. – New York: ACM, 2016. – P. 9:1–9:12.

15. HENZINGER M., KLEIN P., NANONGKAI D. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization // Proc. of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. – Washington: IEEE Computer Society, 2013. – P. 538–547.

16. HENZINGER M., KLEIN P., RAO S., SUBRAMANIAN S.

Faster shortest-path algorithms for planar graphs // Journal of Computer and System Sciences. – 1997. – Vol. 55, №1. – P. 3–23.

17. KING V. Fully dynamic algorithms for maintaining all–pairs shortest paths and transitiveclosure in digraphs // Proc. of the 40th Annual Symposium on Foundations of Computer Science. – Washington: IEEE Computer Society, 1999. – P. 81–99.

18. LOUBAL P. A network evaluation procedure // Highway Research Record. – 1967. – №205. – P. 96–109.

19. MURCHLAND J. The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph // Technical report, LBS-TNT-26. – London: London Business School, Transport Network Theory Unit, 1967.

20. [Электронный ресурс]. – URL:

OpenStreetMap http://wiki.openstreetmap.org/wiki/Planet.osm (дата обращения: 27.12.2016).

Информационные технологии в управлении

21. PANG C., DONG G., RAMAMOHANARAO K. Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL // ACM Transactions on Database Systems. – 2005. – Vol. 30, №3. – P. 698–721.

22. RAMALINGAM G., REPS T. An incremental algorithm for a generalization of the shortest path problem // Journal of Algorithms. – 1996. – №21. – P. 267–305.

23. RAMARAO K., VENKATESAN S. On finding and updating shortest paths distributively // Journal of Algorithms. – 1992. – Vol. 13, №2. – P. 235–257.

24. RODITTY L., ZWICK U. Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs // SIAM Journal on Computing. – 2012. – Vol. 41, №3. – P. 670–683.

25. The Boost Graph Library [Электронный ресурс]. – URL:

www.boost.org/doc/libs/1_59_0/libs/graph/doc/index.html (дата обращения: 27.12.2016).

26. THORUP M. Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles // Proc. of the 9th Scandinavian Workshop on Algorithm Theory. – Berlin: Springer, 2004. – P. 384–396.

Управление большими системами. Выпуск 65

ALGORITHM FOR DYNAMIC ALL-PAIRS

DISTANCES IN GRAPH

Airat Urakov, Ufa State Aviation Technical University, Ufa, Candidate of Sciences, docent (urakov@ufanet.ru).

Timofey Timeryaev, Ufa State Aviation Technical University, Ufa (timeryaev@yandex.ru).

Abstract: Fully dynamic all-pairs graph distances problem for undirected graphs with positive edge weights is considered. Edge weights can change arbitrary so distances between vertices should be kept actual. We propose an algorithm taking into account all possible distance changes by the use of edge addition and deletion procedures.

The developed algorithm uses the notion of points equidistant to the vertices incident to the edge being deleted for an edge deletion procedure. This allows to significantly reduce time and memory complexity of the graph distance actualization task in practical scenarios. The conducted computational experiments showed that the proposed algorithms outperforms the fastest known methods.

Keywords: dynamic graph distances, graph update, equidistant points, graph actualization.

–  –  –

УДК 519.17 + 621.3.05 + 519.67 ББК 22.1

АНАЛИЗ СТРУКТУРЫ

МАГИСТРАЛЬНЫХ ЭЛЕКТРОСЕТЕЙ РОССИИ:

ОЦЕНКА ПРИМЕНИМОСТИ

МОДЕЛИ ТЕСНОГО МИРА

–  –  –

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

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

Ключевые слова: теория сложных сетей, топология сети, тесный мир, электросети, ЕНЭС.

1. Введение Сети объектов транспортной, энергетической и телекоммуникационной инфраструктуры являются пространственным Сергей Вячеславович Макрушин, кандидат экономических наук (s-makrushin@yandex.ru, SVMakrushin@fa.ru).

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

Объектом данного исследования является одна из ключевых инфраструктурных сетей России – Единая национальная электрическая сеть (ЕНЭС) – комплекс магистральных электрических сетей Российской Федерации, основная часть которого управляется ОАО «ФСК ЕЭС»; предметом исследования является топологическая и пространственная структура ЕНЭС.

Целью исследования является анализ ключевых топологических свойств сети, в частности, оценка применимости для качественного описания топологии сети модели тесного мира (small world) [23].

Для проведения исследования используются методы теории сложных сетей (ТСС) [2]: при помощи анализа компьютерной модели сети ЕНЭС определяются характеристики сети, анализируется применимость модели тесного мира для описания сети ЕНЭС. За рубежом методы ТСС активно применяются для исследования различных инфраструктурных сетей национального масштаба, в том числе магистральных электросетей. В частности, только в работе [18] рассмотрено 34 научных статьи по анализу магистральных электросетей 26 стран мира методами ТСС. Несмотря на это, научные исследования ЕНЭС с помощью методов теории сложных сетей еще не получили распространения.

Теория сложных сетей (complex network theory или network theory) изучает сложные взаимодействующие системы, которые могут быть представлены в виде сети (графа). Данное направление исследований начало формироваться в конце 1990х годов с целью изучения свойств больших сетевых структур, обладаюСетевые модели в управлении щих свойствами сложных систем. Математический аппарат теории основывается на теории графов, теории вероятности, математической статистике и некоторых разделах статистической физики. Теория сложных сетей имеет приложения в самых различных областях: биологии, социологии, лингвистике, телекоммуникациях, транспорте, урбанистике, экономике, инфраструктурных сетях. Несмотря на то, что ряд базовых работ по теории сложных сетей (сети Эрдеша–Реньи [8] и пр.) был выполнен в третьей четверти XX века, данное направление как активно развивающийся комплекс взаимосвязанных исследований появилось лишь на рубеже XX и XXI веков. Его развитию послужило появление большого количества доступных для компьютерного анализа массивов данных о сложных сетях и развитие компьютерных инструментов их анализа.

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

2. Модель ЕНЭС

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

Данные для формирования модели сети собраны из официальных документов [3] и интерактивной карты ЕНЭС, представленной на сайте ОАО «ФСК ЕЭС» [4]. Формат исходных данных (PDF и интерактивная карта в браузере) позволял использовать только ручную обработку и внесение данных для создания пригодной для проведения исследования компьютерной модели сети ЕНЭС. Так как модель сети ЕНЭС имеет географическую привязку, то для внесения данных была использо

<

Управление большими системами. Выпуск 65

вана геоинформационная система (ГИС) и глобальная геоинформационная база данных.

В качестве глобальной геоинформационной базы данных был выбран проект OpenStreetMap [17], так как предоставляемые им данные обладают необходимым качеством и являются полностью открытыми. Формат базы OpenStreetMap позволяет полноценно работать с объектами электроэнергетической инфраструктуры, а сама база даже частично содержит необходимую информацию об электростанциях и магистральных электросетях. В качестве ГИС был использован редактор карт проекта OpenStreetMap JOSM. Для удобства при редактировании использовались данные OpenStreetMap, предварительно подготовленные (разделенные по регионам) сообществом GISLab.ru и выложенные в виде файлов в формате OSM [1].

Однако полный набор геоданных по крупным российским регионам оказывался слишком объемен для комфортной работы с ними в редакторе JOSM. Например, размер файла геоданных в формате OSM для Московской области составляет более 200 Мбайт, что значительно превышает возможности JOSM по обработке данных на типичной рабочей станции. Для решения этой проблемы данные, излишние при нанесении объектов электроэнергетической инфраструктуры, были удалены из файла при помощи инструмента osmfilter, что уменьшило объем файлов приблизительно в 10 раз и позволило комфортно работать с геоданными любых регионов Российской Федерации.

В редакторе JOSM на картах регионов были нанесены узлы сети ЕНЭС с указанием названия объекта, его типа (электростанция или подстанция), максимального уровня напряжения, с которым работает узел, его загрузки (на основе данных из [4]), для связей в сети (линий электропередач); был указан их номинальный уровень напряжения. Далее региональные фрагменты ЕНЭС были «склеены» с использованием инструмента osmconvert, в результате чего было получено картографическое представление ЕНЭС, хранящееся в файле формата OSM.

Формат файла OSM является специфичным для геоинформационных систем и не поддерживается библиотеками и инструментами, предназначенными для анализа сложных сетей (в частности, использованной в исследовании библиотекой netСетевые модели в управлении workx [16] и средой Gephi [11]). Для конвертации данных был использован следующий подход: на языке Python автором был написан конвертор собранных данных из формата OSM в формат CSV (были сформированы два отдельных файла для узлов и связей), полученные данные о ЕНЭС были загружены в инструмент для анализа и визуализации сложных сетей Gephi, после чего были сохранены в формат gexf, который хорошо поддерживается инструментами анализа сложных сетей. В данном формате компьютерная модель ЕНЭС использовалась как набор исходных данных для дальнейших исследований.

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

На основании модели для сети ЕНЭС рассчитаны базовые интегральные характеристики сети, такие как: диаметр сети (36 переходов), средняя степень узлов (2,49 связи на узел), среднее межузловое расстояние (11,9 переходов), средний коэффициент кластеризации (0,0807). Распределение степеней узлов построенной модели ЕНЭС показано на рис. 1.

Рис. 1. Распределение степеней узлов сети ЕНЭС Управление большими системами. Выпуск 65 Сравнивая среднюю степень узлов сети ЕНЭС (2,49 связей на узел) с аналогичным показателем, рассчитанным по данным, полученным в 32 зарубежных исследованиях магистральных электрических сетей [18] (медианное значение 2,73 связи на узел), можно отметить, что сеть ЕНЭС является более разреженной по сравнению с большинством европейских и американских аналогов. К сожалению, провести сравнительный анализ других интегральных показателей ЕНЭС и зарубежных магистральных электросетей затруднительно ввиду отсутствия необходимой информации в метаисследовании [18].

3. Модель сетей тесного мира

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

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

Сети тесного мира являются широко распространенным и хорошо исследованным классом сетей. Феномен сетей тесного мира заключается в том, что эти сети обладают компактностью (небольшой длиной кратчайших путей между всеми парами узлов сети), характерной для случайных сетей (сетей Эрдеша– Реньи) [8], и высоким уровнем кластеризации (средним значением коэффициента кластеризации всех узлов сети), характерным для регулярных сетей («решеток»).

–  –  –

Рис. 2. Иллюстрация из пионерской работы Ваттса и Строгатца [23], демонстрирующая принцип построения сети, обладающей свойствами тесного мира (p – вероятность осуществления пересвязывания связей в сети) Д. Ваттсом и С. Строгатцом в работе [23] был предложен алгоритм генерации сетей со свойствами тесного мира, который заключается в случайном изменении связей (пересвязывании) в сети, представляющей собой одномерную решетку, этот процесс иллюстрирован на рис. 2. Пересвязывание (relinkage) даже небольшой доли связей регулярной сети (вероятность пересвязывания для каждой связи определяется параметром модели p) приводит к сильному сокращению средней длины кратчайших путей в сети, при этом средний коэффициент кластеризации, присущий исходной решетке, снижается незначительно. Этот феномен продемонстрирован на графике на рис. 3.

Связи в сетях тесного мира, отвечающие за сильное сокращение длины кратчайших путей в сети, принято называть длинными связями (long link или shortcut). Нужно отметить, что это понятие напрямую не связано с длиной связи, более того, во многих сетях понятие длины для связей может быть вообще не определено, что не мешает выявлять в них «длинные связи», связывающие отдаленные в топологическом смысле узлы сети.

В модели Ваттса–Строгатца связи, образующиеся в результате Управление большими системами. Выпуск 65 пересвязывания узлов, чаще всего становятся длинными связями (на рис. 2 они отмечены серым цветом).

Рис. 3. Изменение основных свойств сети (среднего коэффициента кластеризации C и средней длины путей в сети l) при разных значениях параметра p по отношению к их значениям для решеточно-упорядоченного кольца (правая шкала) и меры принадлежности к сетям тесного мира (левая шкала) (рисунок из работы [21]) Для электросетей длинные связи в сети представляют особый интерес, так как исследования каскадных аварий в электросетях показали, что «длинные связи» в сетях тесного мира являются ключевым элементом процесса возникновения каскадных отключений [14]. В целом же в указанном исследовании показано, что триггером начала каскадной аварии является выход из строя ряда элементов сети, приводящий к потере электросетью качеств сети тесного мира.

Несмотря на большое количество исследований магистральных электросетей методами ТСС, на данный момент отсутствует консенсус об их принадлежности к сетям тесного мира. Хотя в пионерских исследованиях [22] давался положительный ответ на этот вопрос, впоследствии относительно ряда

Сетевые модели в управлении

магистральных электросетей сделан вывод о том, что они не относятся к сетям тесного мира [12, 18].

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

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

4. Определение принадлежности к сетям тесного мира

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

Распространение получила числовая мера принадлежности к тесному миру, впервые предложенная в [13]:

C / Crnd (1) =, l / lrnd где C и Crnd – уровень кластеризации в исследуемой сети и в случайной сети-аналоге, а l и lrnd – средняя длина кратчайших путей в этих сетях. Чем больше значение величины, тем ближе сеть к состоянию тесного мира, а для сети тесного мира характерно значение 1.

Однако анализ меры, проведенный в [21], показывает, что ее применение для построения критерия принадлежности к тесному миру некорректно. В работе [21] показано, что сети, однотипные с точки зрения модели тесного мира, могут иметь значение, отличающееся на порядок только из-за различия в размере сети. Таким образом, выбор любого определенного порогового уровня в качестве критического значения принадлежности к тесному миру будет некорректен, так как для сетей Управление большими системами. Выпуск 65 разного размера данный уровень будет означать существенно различающуюся структуру сети с точки зрения принадлежности к тесному миру. Кроме того, мера не может использоваться для сравнения сетей различного размера.

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

Например, значение, рассчитанное нами для ЕНЭС, равно 14,1, что при помощи графика с рис. 3 может быть интерпретировано двояко: либо структура ЕНЭС близка к случайным сетям (значение 14,1 на нисходящей части графика ), либо к регулярным сетям (значение 14,1 на восходящей части графика ). И, несмотря на то, что значение для ЕНЭС много больше 1, данное значение не может однозначно говорить о принадлежности сети к сетям тесного мира и не может использоваться для сравнения структур сетей с различным количеством узлов. Это вызвано тем, что для интерпретации значения для каждой конкретной сети требуется построение индивидуального графика зависимости от вероятности пересвязывания в модели Ваттса–Строгатца, так как, как было отмечено выше, поведение существенно зависит от размера сети.

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

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

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

Данная процедура была проведена для исследуемой компьютерной модели сети ЕНЭС. Было реализовано 50 повторений процесса рандомизации, по итогам которых были получены средние значения характеристик рандомизированной сети, приведенные в столбце 2 таблицы 1. Средний кратчайший путь в модели ЕНЭС оказался на 4 перехода длиннее, чем в случайной сети-аналоге, а отношение l/lrnd имеет значение 1,50, что очень существенно для сетей с одинаковым количеством вершин.

Отношение средней кластеризации в сети ЕНЭС и случайной сети-аналоге C/Crnd равно 21,1, и качественное изменение значения показателя здесь очевидно. Однако кластеризация для ЕНЭС на порядок меньше теоретического максимума, таким образом, значение для ЕНЭС может на порядок отличаться не только от аналогичного значения в рандомизированной сети, но и от аналогичного значения в регуляризированном аналоге. В данном случае, как и говорилось выше, только сравнение с адекватной сетью-аналогом с высокой кластеризацией (регуляризованным аналогом сети) может корректно показать близость сети ЕНЭС к состоянию тесного мира.

Управление большими системами. Выпуск 65

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

В работе К. Телесфорда и др. [21] было предложено использовать для этих целей алгоритм латтисизации (latticization – приведения к виду решетки), описанный в [20]. Рассмотрение прошедшей латтисизацию сети-аналога позволило Телесфорду с коллегами сформулировать более качественную меру близости сети к тесному миру, имеющую вид l C (2) = rnd, l Clatt где Clatt – уровень кластеризации в латтисизированной сетианалоге. Для сетей тесного мира значение должно быть близко к 0, а для всех сетей, полученных в рамках алгоритма ВаттсаСтрогатца, значение [–1, 1], где значение, близкое к 1, соответствует случайной сети-аналогу, а значение, близкое к –1, – сети-аналогу с регулярной структурой. В работе [21] показано, что слабо чувствительна к размеру анализируемой сети и не демонстрирует одинаковых значений для сетей, находящихся в качественно разных состояниях с точки зрения модели тесного мира Ваттса–Строгатца.

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

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

Принципиальная схема алгоритма латтисизации приведена в виде псевдокода на рис. 4. На каждой итерации внешнего цикла алгоритма латтисизации (строки 1–19) проводится попытка случайного пересвязывания. Для того чтобы пересвязывание не приводило к изменению степеней узлов, оно выполняется по следующей схеме: случайно выбираются две пары узлов (пара nodeA, nodeB и пара nodeC, nodeD), связанных между собой.

Связи внутри пар разрываются и образуются новые перекрестные связи между узлами (nodeA, nodeD и nodeB, nodeC соответственно). Во внутреннем цикле алгоритма (строки 4–13) для пары узлов nodeA, nodeB подбирается подходящая пара узлов nodeC, nodeD: вторая пара узлов не должна иметь совпадений и связей с узлами первой пары и, главное, длина новых перекрестных связей должна быть меньше, чем длина существующих связей внутри пар. Длина связи в алгоритме принимается равной расстоянию между узлами, определяемому функцией Distance, принимающей в виде входных переменных два узла сети.

В алгоритме латтисизации, описанном в [20], расстояние между любыми двумя узлами в сети определяется кольцевой последовательностью узлов по аналогии со структурой, в которой находятся узлы в одномерной решетке (кольце) в алгоритме Ваттса–Строгатца (см. рис. 2). Так как, в отличие от модели Ваттса–Строгатца, при анализе реальной сети информации об исходной кольцевой решетке нет, то кольцевая последовательность узлов определяется случайным образом перед началом процедуры латтисизации. Расстояние между узлами задается равным наименьшему расстоянию между узлами, измеряемому в количестве шагов по кольцевой последовательности между ними. В частности, расстояние между соседними узлами в кольцевой последовательности минимально и равно единице, а расстояние между самыми удаленными узлами, расположенными на противоположных сторонах кольца, равно [N/2], где N – количество узлов в сети.

Управление большими системами. Выпуск 65

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

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

–  –  –

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

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

–  –  –

Для анализа магистральных электросетей метод латтисизации ранее не применялся. Для решения этой задачи авторами была разработана собственная реализация алгоритма латтисизации на языке программирования Python, разработанная на основе описания алгоритма латтисизации, предложенного в [20], и

Управление большими системами. Выпуск 65

анализа его реализации в библиотеке алгоритмов brain connectivity toolbox [7].

В рамках анализа сети ЕНЭС процедура латтисизации была применена к компьютерной модели сети ЕНЭС, характеристики полученной сети-аналога приведены в столбце 3 таблицы 1.

Отношение средних кластеризаций в латтисизированной и исходной сети ЕНЭС Clatt /C составило 2,5, однако это заметное различие существенно меньше более чем двадцатикратного различия в отношении C/Crnd. Средняя длина пути в латтисизированной сети равна 62,8 при 11,9 в исходной модели и 7,9 в рандомизированной, из чего видно, что по длине путей сеть ЕНЭС существенно ближе к рандомизированному аналогу, нежели к регуляризованному при помощи алгоритма латтисизации аналогу. Таким образом, сеть ЕНЭС можно считать близкой к случайной сети-аналогу по средней длине пути и близкой к регулярной сети по уровню средней кластеризации. Значение меры, рассчитанное для сети ЕНЭС, составляет 0,26 (расчет значения см. в таблице 2), что говорит о близости сети ЕНЭС к состоянию тесного мира. Положительное значение показывает, что по своей структуре сеть ЕНЭС существенно ближе к случайной сети, чем к одномерной решетке.

–  –  –

6. Процедура геолаттисизации Так как объектом данного исследования является магистральная электросеть, для которой известна географическая привязка узлов сети, то использование одномерной замкнутой Сетевые модели в управлении решетки в качестве сети-аналога представляется не совсем корректным, тем более что в литературе широко известны модификации модели Ваттса–Строгатца, в которых для построения сетей тесного мира используются двухмерные решетки [15].

Для построения двухмерной регулярной сети-аналога в рамках работы по анализу сети ЕНЭС была разработана авторская модификация алгоритма латтисизации. В ней расстояние, приписываемое связям в сети, определяется на основе данных о координатах узлов, соединяемых этой связью, при помощи расчета длины (в километрах), соответствующей геодезической линии на поверхности земли. В модифицированном алгоритме это расстояние возвращается при вызове функции Distance.

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

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

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

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

Для построения модельной сети рассмотрен прямоугольник на плоскости размером 10 на 20. В точках прямоугольника, имеющих целочисленные координаты, расположены 200 узлов Управление большими системами. Выпуск 65 (см. рис. 5а). Каждый из узлов соединен с ближайшими соседями по горизонтали и вертикали. В решетке с квадратными ячейками коэффициент кластеризации всех узлов будет равен 0, что не позволит провести на такой модели анализ поведения коэффициента кластеризации, поэтому в каждую вторую ячейку модельной сети были добавлены дополнительные диагональные связи. Направление связей во всех ячейках выбрано одинаковым, а положение ячеек с диагональными связями у соседних рядов ячеек чередуется (см. рис 5а). В итоге модельная сеть, изображенная на рис. 5а, имеет 200 узлов, 456 связей, основные свойства модельной сети приведены в столбце 1 таблицы 3.

–  –  –

После случайного пересвязывания 14 связей (3% от общего количества связей) модельной сети она приобрела вид, показанный на рис. 5б, при этом диаметр сети уменьшился более чем в 2 раза, а коэффициент средней кластеризации изменился только на 7,6% (абсолютные значения коэффициентов приведены в столбце 2 таблицы 3). Таким образом, пересвязанная модельная сеть приобрела свойства сети тесного мира.

–  –  –

в) г) д) Рис. 5. Визуализация результата работы алгоритма геолаттисизации на сети ЕНЭС: а) исходная модельная сеть;

б) модельная сеть после случайного пересвязывания (сеть тесного мира); в) пересвязанная сеть после латтисизации (положение узлов сохранено); г) пересвязанная сеть после латтисизации (положение узлов определено алгоритмом Фрюхтермана–Рэйнгольда); д) пересвязанная сеть после геолаттисизации Управление большими системами. Выпуск 65 К полученной сети тесного мира была применена процедура латтисизации. Для данного примера алгоритмом латтисизации было проведено 1606 пересвязываний из 4000 попыток выполнения пересвязывания. Так как при проведении процедуры латтисизации структура связей подстраивается под кольцевую последовательность узлов, определенную случайным образом, то вид связей для латтисизированной модельной сети на исходной сетке будет казаться случайным (см. рис. 5в). Однако применив алгоритм визуализации графов Фрюхтермана– Рэйнгольда [9] (см. рис. 5г), в котором положение узлов определяется структурой связей в сети, мы можем увидеть, что структура связей, полученная в результате латтисизации, действительно подчинена (естественно, не идеально) некоторой кольцевой последовательности узлов. Значения коэффициентов латтисизированной сети приведены в столбце 3 таблицы 3. Как видно, в результате латтисизации исходные характеристики модельной сети восстановлены очень неточно: значение средней длины кратчайших путей завышено более чем в два раза, средний коэффициент кластеризации завышен более чем на 70%.

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

Результат геолаттисизации модельной сети тесного мира, изображенной на рис. 5б, показан на рис. 5д. Даже из визуального анализа рисунка хорошо видна близость структуры геолаттисизированной сети к исходной сети, показанной на рис. 5а. В данном случае алгоритмом геолаттисизации было проведено 69 пересвязываний из 4000 попыток выполнения пересвязывания. Относительно небольшое по сравнению с процедурой латтисизации количество пересвязываний объясняется тем, что в данном случае не происходит преобразования двухмерной решетки к кольцевой последовательности и все пересвязывания производятся только для укорачивания длинных связей, которых в рассматриваемой модельной сети всего 14 штук.

Сетевые модели в управлении

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

Как видно, в результате геолаттисизации исходные характеристики модельной сети восстановлены весьма точно:

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

7. Геолаттисизация сети ЕНЭС

Для повышения производительности алгоритм геолаттисизации был модифицирован. Была изменена работа функции ChooseLinkedNodes (строка 5 на рис. 4): вместо случайного выбора связанных узлов nodeC, nodeD функция стала возвращать связанные узлы, один из которых находится среди m ближайших узлов nodeA.

За счет гарантированного появления одной короткой (в географическом смысле) связи среди новых связей вероятность успешного пересвязывания существенно возросла. Для решения задачи поиска m ближайших узлов применена одна из реализаций алгоритма геохеширования [10]. В результате скорость построения географически латтисизированной сети существенно возросла и стала удовлетворительной для проведения исследования сети ЕНЭС.

На рис. 6 изображен результат применения процедуры геолаттисизации к модели ЕНЭС. Как видно на рис. 6б, при возможности длинные связи в сети заменены алгоритмом на связи с более близкими узлами сети, при этом степени всех вершин сохранены. Так как процесс геолаттисизации, так же как и латтисизации, основывается на случайном пересвязывании, то его результат недетерминирован, и приведенное на рис. 6б Управление большими системами. Выпуск 65 изображение является только одним из возможных исходов применения алгоритма.

–  –  –

Рис. 6.

Визуализация результата работы алгоритма геолаттисизации на сети ЕНЭС: а) исходная модель ЕНЭС с изображением узлов в соответствии с их географическими координатами; б) модель ЕНЭС, прошедшая геолаттисизацию:

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

В результате замены длинных связей на более короткие, локальные, суммарная длина связей между узлами сети снизилась с 48 107 км до 40 579 км, или на 16%. Нужно отметить, что в данном случае речь идет о длине связей, определенной как Сетевые модели в управлении длина кратчайшей линии, соединяющей узлы с определенными координатами (геодезической линии), а не о длине ЛЭП. Информация о фактической длине ЛЭП нам недоступна, и ясно лишь, что она больше, чем длина рассматриваемой нами геодезической линии.

Несмотря на то, что геолаттисизация сократила суммарную длину связей, измеряемую в километрах, всего на 16%, в топологическом смысле удаленные связи действительно были очень важны для связывания сети. После геолаттисизации топологические характеристики сети изменились очень существенно: диаметр сети (максимальная величина кратчайшего пути между всеми парами узлов) увеличился с 36 до 55 переходов (вырос на 52%), средняя длина путей увеличилась с 11,9 переходов до 19,1 (выросла на 61%). Таким образом, некоторые из удаленных связей были длинными не только с точки зрения географической метрики, но и являлись «длинными связями» в понимании модели Ваттса–Строгатца, т.е. они обеспечивали «стягивание»

сети в компактную структуру.

Важные для расчета меры результаты расчета характеристик сети ЕНЭС, прошедшей геолаттисизацию, приведены в столбце 4 таблицы 1. Двумерная модель сети продемонстрировала существенно меньшую среднюю длину путей по сравнению с одномерной – 19,1 вместо 62,8. Это изменение было ожидаемо, так как двумерная решетка с тем же количеством узлов и связей, что и в одномерной решетке, обеспечивает существенно более короткие кратчайшие пути между узлами.

Несмотря на такое изменение, данный показатель исходной сети ЕНЭС все равно существенно ближе к случайной сети-аналогу (разница в 33%), чем к регуляризованному геопространственному аналогу (разница в 60%).

Также ожидаемо у геолаттисизированной сети-аналога относительно одномерного регуляризованного аналога снизилась средняя кластеризация: c 0,20 до 0,17. Это объясняется тем, что географическая (двухмерная) мера близости по сравнению с мерой близости на одномерной решетке определяет более широкий круг ближайших соседей. Так как количество связей в сети фиксировано, то связи между узлами, входящими в круг ближайших соседей в двухмерной решетке менее вероятны, что Управление большими системами. Выпуск 65 и объясняет снижение коэффициента кластеризации узлов и, как следствие, средней кластеризации всей сети. В результате значение меры близости к тесному миру, рассчитанное для сети ЕНЭС с Clatt, определенным по сети, прошедшей геолаттисизацию, составляет 0,19 (расчет значения см. в таблице 2), что существенно ближе к 0, чем величина меры, полученная на основе латтисизации.

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

8. Выявление критических узлов и связей в сети ЕНЭС

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

Из анализа модели тесного мира известно [5, 6], что узлы сетей тесного мира, связанные с длинными связями, обладают высокой центральностью по посредничеству (betweenness centrality).

Центральность по посредничеству определяется как доля кратчайших путей, проходящих через данный узел, среди кратчайших путей, построенных для всех узлов сети:

(u ) (3) g (u ) = s t u st, st где st(u) – количество кратчайших путей между узлами s и t, проходящих через узел u, а st – количество всех кратчайших Сетевые модели в управлении путей между узлами s и t. Центральность по посредничеству характеризует важность узла как посредника на пути между другими узлами. В частности, удаление узла с высокой важностью по посредничеству может привести к увеличению расстояний между многими узлами и, как следствие, увеличению среднего межузлового расстояния и даже увеличению диаметра всей сети.

Рис. 7. Визуализация компьютерной модели сети ЕНЭС. Размер узлов определяется количеством связей (степенью) узла, цвет связей определяется центральностью по посредничеству (синие узлы – наиболее центральные) В рамках данного исследования на основе компьютерной модели ЕНЭС была рассчитана центральность по посредничеству узлов сети ЕНЭС, результаты расчетов визуализированы на сети на рис. 7 и представлены в виде гистограммы на рис. 8. Из рисунков видно, что в сети ЕНЭС есть несколько узлов, имеющих очень высокую центральность по посредничеству и образующих цепь, проходящую через всю центральную часть ЕНЭС.

Перечислим состав этой цепи (в скобках приведена центральность узлов по посредничеству): ПС 750 кВ Ленинградская (0,23) – АЭС Калининская (0,32) – ПС 750 кВ Владимирская Управление большими системами. Выпуск 65 (0,30) – ПС 500 кВ Радуга (0,19) – ПС 500 кВ Арзамасская (0,21) – ПС 500 кВ Осиновка (0,19) – ПС 500 кВ Вешкайма (0,35). Особый статус этих узлов с точки зрения центральности по посредничеству подчеркивает анализ распределения всех узлов по этому показателю: среднее значение центральности по посредничеству среди всех узлов сети составляет 0,0213, медиана 0,0038, значение 90-го, 95-го и 98-го перцентилей, соответственно: 0,0667, 0,1121 и 0,1880. Из анализа распределения величины центральности по посредничеству видно, что все перечисленные узлы относятся к 2% узлов с самой высокой центральностью по посредничеству и имеют значение этого показателя на порядок выше среднего значения по всей сети и на два порядка выше медианного значения по всей сети.

Рис. 8. Гистограмма распределения узлов сети ЕНЭС по уровню центральности по посредничеству Визуальный анализ позволяет объяснить особую роль этих узлов: они обеспечивают очень короткий (в топологическом смысле) путь через центральную часть сети. Обеспечивается это за счет очень большой протяженности ЛЭП на некоторых участках этой цепочки, что особенно важно ввиду прохождения линий по территории с высокой плотностью узлов, для которой характерны относительно короткие (в географическом смысле) связи между узлами. Большая протяженность ЛЭП в этой це

<

Сетевые модели в управлении

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

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

9. Выводы

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

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

Разработанная мера близости к сетям тесного мира и ее базовый вариант ранее не использовались для анализа структуры Управление большими системами. Выпуск 65 магистральных электросетей. Кроме того, методы теории сложных сетей еще не получили распространения при анализе одной из крупнейших мировых магистральных электросетей – Единой национальной (общероссийской) электрической сети. В данной работе новые методы были применены для исследования свойств ЕНЭС, в результате чего был сделан надежный вывод о принадлежности ЕНЭС к сетям тесного мира. Данный вывод позволяет использовать модель сетей тесного мира для ключевых задач исследования ЕНЭС, таких как анализ вопросов надежности (в частности, устойчивости к каскадным отключениям) и эффективности сети. Так как предыдущие исследования показали ключевую роль «длинных связей» (ключевых структур модели тесного мира) в процессе каскадных отключений, то данной работой, по сути, обоснована необходимость проведения анализа уязвимости ЕНЭС к каскадным отключениям с учетом специфики ее топологии (принадлежности к сетям тесного мира). В данном исследовании не только определены общие характеристики сети, но и идентифицированы «длинные связи»

ЕНЭС, формирующие структуру тесного мира и требующие особого внимания при анализе надежности сети.

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

–  –  –

Данные OpenStreetMap в форматах XML и PBF. – 1.

[Электронный ресурс]. – Режим доступа: http://gis-lab.info/ projects/osm_dump/.

ЕВИН И.А. Введение с теорию сложных сетей // Компьютерные исследования и моделирование. – 2010. – Т. 2, №2. – С. 121–41 Схема и программа развития ЕНЭС на 2013–2019 годы. – 3.

Приказ Минэнерго России №309 от 19.06.2013.

Услуги по технологическому присоединению: центы питания. – [Электронный ресурс]. – Режим доступа:

http://portaltp.fsk-ees.ru/sections/Map/map.jsp.

5. BARRAT A., BARTHELEMY M., VESPIGNANI A. The effects of spatial constraints on the evolution of weighted complex networks // J. Stat. Mech. – 2005. - P. 503

6. BARTHELEMY M. Spatial Networks // Condensed Matter, Statistical Mechanics – 2011. - arXiv:1010.0302, Physics Reports №499 - P. 1–101.

Brain Connectivity Toolbox. – [Электронный ресурс]. – Режим 7.

доступа: http://www.brain-connectivity-toolbox.net.

ERDS P., RNYI A. On Random Graphs I // Publ. Math.

8.

Debrecen. - 1959. – Vol. 6, - P. 290–297.

9. FRUCHTERMAN T., REINGOLD E. Graph drawing by forcedirected placement // Software – Practice and Experience. – 1991. – Vol. 21(11) – P. 1129–1164.

10. Geohash is a Python module that provides functions for decoding and encoding Geohashes to and from latitude and longitude

coordinates. – [Электронный ресурс]. – Режим доступа:

https://github.com/vinsci/geohash/.

Gephi: The Open Graph Viz Platform. – [Электронный 11.

ресурс]. – Режим доступа: https://gephi.org/.

12. HAN P., DING M. Analysis of Cascading Failures in Smallworld Power Grid // Int. J. of Energy Science. – 2011 - Vol. 1, No. 2 - P. 99-104.

HUMPHRIES M.D., GURNEY K. Network ’small-world-ness’:

13.

a quantitative method for determining canonical network equivalence // PLoS One 3:e0002051 – 2008.

Управление большими системами. Выпуск 65

14. KIM C.J., OBAH O.B. Vulnerability Assessment of Power Grid Using Graph Topological Indices // Int. J. of Emerging Electric Power Systems. – 2007. – Vol. 8, Issue 6, Article 4.

15. KLEINBERG J.M. Navigation in a small world // Nature. – 2000. – No. 406 – P. 845

16. NetworkX: Python language software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks. – [Электронный ресурс]. – Режим доступа: https://networkx.github.io/.

17. OpenStreetMap. – [Электронный ресурс]. – Режим доступа:

http://www.openstreetmap.org/.

18. PAGANI G.A., AIELLO M. The Power Grid as a Complex Network: a Survey // Physica A: Statistical Mechanics and its Applications. – 2011. - №392(11). – P. 2688–2700.

19. PANDIT S.A., AMRITKAR R.E. Random spread on the family of small-world networks // Phys. Rev. E. – 2001. - No. 63. – Article ID: 041104.



Pages:   || 2 |
Похожие работы:

«Джек Майер Храброе сердце Ирены Сендлер Серия "Проект TRUE STORY. Книги, которые вдохновляют (Эксмо)" Текст предоставлен издательством http://www.litres.ru/pages/biblio_book/?art=6527223 Храброе сердце Ирены Сендлер / Джек Майер: Эксмо; Москва; ISBN 978-5...»

«Power Systems Планирование помещения и аппаратного обеспечения IBM Power Systems Планирование помещения и аппаратного обеспечения IBM Примечание Перед тем, как приступить к работе с этой информацией и о...»

«УДК 666.9 Н.С. ЦАПКО, канд. техн. наук, доц., ХНЭУ им. С. Кузнеца, Харьков ИССЛЕДОВАНИЕ ПРОДУКТОВ ГИДРАТАЦИИ СПЕЦИАЛЬНОГО РЕНТГЕНОКОНТРАСТНОГО БАРИЙСОДЕРЖАЩЕГО ЦЕМЕНТА Статья посвящена исследованию продуктов гидратации отечественного рентгеноконтрастного цемента для стоматологии. Рассмотрена возможность получения рентгеноконтрастного цемента н...»

«УСТАНОВКА РАЗВЕДОЧНОГО БУРЕНИЯ УРБ ЗАЗ Буровые установки типа УРБ-ЗАЗ предназначены для структурно-поискового бурения скважин на нефть и газ, гидрогеологического и эксплуатационного бурения скв...»

«http://vmireskazki.ru vmireskazki.ru › Сказки народов Азии › Индонезийские сказки Петух Панджи Лараса Индонезийские сказки В древние времена царствовал на острове Ява знаменитый раджа по имени Прабу Джойо Кусумо. У раджи было несколько...»

«33 причины для смиренности в намазе Мухаммед Салих Аль-Мунаджид Во имя Аллаха Милостивого Милосердного, Хвала Аллаху Господу Миров, сказавший в Своей ясной книге: И вставайте пред Аллахом покорными, и про молитву: Поистине она тяжела, кроме как для смиренных, и мир и благословение предводителю всех богобоязненных и господину покорных Му...»

«Май 2010 • Ияр–Сиван 5770 Программа JHG Home Дорогие члены общины, друзья и покровители, В солнечный весенний день, понедельник 29 марта, мы отпраздновали Песах. Столы были празднично накрыты, и, как каждый год, были разложены книги "Хагадот" на немецком и русском языках и на иврите. Седер провела раввин Irit Shil...»

«Робин Маккинли Меч королевы Серия "Библиотека настоящих принцесс" Серия "Дамар", книга 2 http://www.litres.ru/pages/biblio_book/?art=6737835 Робин Маккинли. Меч королевы: Азбука, Азбука-Аттикус; Москва; 2014 ISBN 978-5-389-08282-3 Ор...»

«ПРОГРАММА КОМПЛЕКСНОГО РАЗВИТИЯ ТРАНСПОРТНОЙ ИНФРАСТРУКТУРЫ МУНИЦИПАЛЬНОГО ОБРАЗОВАНИЯ СЕЛА ДМИТРИЕВСКОГО КРАСНОГВАРДЕЙСКОГО РАЙОНА СТАВРОПОЛЬСКОГО КРАЯ г. Ставрополь г. Ставрополь 2016 год Страница |2 СОДЕРЖАНИЕ 1 3-5 Паспорт программы 2 6-8 Введение Характеристика существующего состояния транспортной 3 9-...»

«Непал + Тибет!!! Групповой тур!!! маршрут: Катманду ПокхараДулихед – Джангму – Шигадзе – Лхаса Гьянгзе – Шегаре Катманду Действие Номер тура Продолжительность Дни заездов (месяца 2015г.) предложения 15 дней / 14 ночей KZ-GR -04-2015 04.04.-18.04.2015 04.04.2015-17.10.2015 02.05.-16.05.2015 06.06.-21.06.2015 04.07.-18.07.2015...»

«Государственное бюджетное образовательное учреждение начального профессионального образования Профессиональное училище № 1 30.4 Помощник машиниста электровоза Слесарь по ремонту подвижного состава К защите допущена: Зам. директора по УПР _Ив...»

«A/60/4 Организация Объединенных Наций Доклад Международного Суда 1 августа 2004 года — 31 июля 2005 года Генеральная Ассамблея Официальные отчеты Шестидесятая сессия Дополнение № 4 (A/60/4) Генеральная Ассамблея Официальные отчеты Шест...»

«АНИЩЕНКО Ксения Владимировна "Журналист в прямом эфире: традиции и тенденции" ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА по направлению "Журналистика" (научно-исследовательская работа ) Научный руководитель – доцент, к.филол.н. И. А. Куксин Кафедра телевизионной и радиожурналистики Очная форма обучения Вх. №от Секретарь _ Санкт-Петербу...»

«Комитет по осуществлению неотъемлемых прав палестинского народа и Отдел по правам палестинцев Информационная записка Организация Объединенных Наций Нью-Йорк, 2002 год 02-55978.R -2Комитет по осуществлению неотъемлемых прав палестинского народа Мандат и задачи Вопрос о Палестине впервые был по...»

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

«УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОГО УНИВЕРСИТЕТА Том 156, кн. 3 Естественные науки 2014 УДК 595.746 ПУТИ И ЭТАПЫ СОВЕРШЕНСТВОВАНИЯ ПАРАМЕТРИЧЕСКОЙ СИСТЕМЫ ОТРЯДА ВЕЕРОКРЫЛЫХ НАСЕКОМЫХ (INSECTA: STREPSIPTERA) Р.М. Зелеев, А.Р. Сафин Аннотация Продолжено построение параметрической...»

«ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ по направлению 23.04.01 "Технология транспортных процессов". 3 этап. Вступительные испытания в магистратуру проводятся в виде письменного экзамена, включающего 4 вопро...»

«ГЛАВА ПЕРВАЯ ) аждому ведомо: Вселенная, как и жизнь, движется по кругу. По кругу, на ободе которого помечены восемь волшебных точек, дающих полный оборот, или годичный цикл. Этими точками, попарно ле...»

«ЧАСТЬ ПЕРВАЯ ПРАВДИВАЯ ЛОЖЬ ГЛАВА 1 В РУКАХ ВРАГА Рокот вертолетов, зависших над поселком, заглушал морской прибой. Я сидел посреди комнаты на втором этаже дома Али и наблюдал через окно за тем, как ауткомовцы-штурмовики, двигаясь цепочками, пробираются по улицам к центру поселка. Всего с вертушек высадил...»

«ЭЛЕКТРО-ТЕРМИТ ТЕХНОЛОГИЯ АЛЮМИНОТЕРМИТНОЙ СВАРКИ РЕЛЬСОВ С КОРОТКИМ ВРЕМЕНЕМ ПОДОГРЕВА (SkV, SkV-L 50, SkV-L 75) ООО "Алюминотермитная сварка" Санкт-Петербург СОДЕРЖАНИЕ Часть 1. Общие данные об алюминотермитной сварке с использованием технологии SkV фирмы ELEKTRO-THERMIT & Co. KG, Германия.1.1. Назначение и об...»

«З А М Ш И О МАЗЕПЪ. (По поводу книги. М. Уманца „Гет м ат Мазепа*). I. Мазепа до поставленія гтманомъ. Главная задача книги. М. Уманца заключается въ „выдленіи свтлыхъ точекъ въ политической и частной жизни М а­ зепы, такъ какъ „на Мазеп много пятенъ, да притомъ „об­ щая молва сгуст...»

«Государственное бюджетное образовательное учреждение города Севастополя "Средняя общеобразовательная школа №32 имени Л.В. Бобковой" "Рассмотрено и рекомендовано "СОГЛАСОВАНО" "УТВЕРЖДАЮ" к утверждению" на заседании Заместитель дирек...»

«РУССКО-ЯПОНСКИЙ РАЗГОВОРНИК Илья Пушкин © Jerusalem Ilya Pushkin Илья Пушкин РУССКО-ЯПОНСКИЙ РАЗГОВОРНИК Иерусалим 2009 Пушкин И. Русско-японский разговорник. Общение на японском языке. Русско-японский разговорник содержит типичные модели фраз и выражений по широкому кругу тем. Приводятся основные, принятые на сегодняшний день...»

«Сентябрь 2014 • Элул–Тишри 5774–5775 Программ JHG Home Дорогие члены общины, друзья и покровители ! H Еврейский 5774 год приближается с месцем элул к концу. 24-го и 25-го сентября (29 элула и 1-го т...»








 
2017 www.kniga.lib-i.ru - «Бесплатная электронная библиотека - онлайн материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.