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

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

Анисимов Сергей Анатольевич

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород-2013 г.

31 ОКТ 2013

005536172

Работа выполнена на кафедре «Теория цепей и телекоммуникации» Нижегородского государственного технического университета им. P.E. Алексеева

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

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

Ведущая организация:

доктор технических наук, профессор, КРЫЛОВ Владимир Владимирович

ХРАНИЛОВ Валерий Павлович,

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

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

технического университета им. P.E. Алексеева» (г. Н. Новгород), профессор ШАПОШНИКОВ Дмитрий Евгеньевич, кандидат физико-математических наук, доцент, Научно исследовательский институт прикладной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (г. Н. Новгород), заместитель директора по развитию

Открытое акционерное общество федеральный научно-производственный центр «Научно-производственное предприятие «Полет», (г. Н. Новгород)

Защита диссертации состоится « 5 » декабря 2013 года в 11-00 часов в ауд. 1258 на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603600, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева.

Автореферат разослан « » октября 2013 года.

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

Суркова Анна Сергеевна

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

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

Актуальность работы. Одной из важнейших потребностей общества является решение различных прикладных задач в области молекулярной биологии, гидрологии, систем прогнозирования, и др. Для решения сложных вычислительных задач обычно используют одну из парадигм распределенной вычислительной инфраструктуры. Наиболее перспективный способ -использование гридов, которые объединяют гетерогенные ресурсы, одним из типов которых являются специальные ресурсы хранения: информационные ресурсы (каталоги). Каталог осуществляет обнаружение, учет использования, совместное выделение ресурсов, мониторинг состояния грида. Проанализировав различные реализации архитектур гридов, оказалось, что все они имеют ряд существенных недостатков, связанных с централизацией каталога ресурсов: при выходе из строя центрального каталога ресурсов грид неработоспособен; каталог парализуется частыми запросами при большом количестве ресурсов сети; в каталоге хранится неактуальная информация. Распределение нагрузки на узлы сети крайне неравномерное. Для устранения недостатков, указанных выше, требуется разработать оптимальную топологию вычислительных гридов.

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

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

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

Объект исследования. Вычислительные гриды и энергетические сети.

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

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

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

1. Построение математической модели сетей следующего поколения.

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

3. Разработка протокола поиска ресурсов в перспективных вычислительных гридах.

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

5. Разработка алгоритмов управления отказами в сетях следующего поколения.

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

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

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

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

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

графа и нахождение оптимальной топологии с помощью алгоритмов эвристического поиска.

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

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

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

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

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

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

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

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

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

Результаты исследований, полученные автором в работе (алгоритм маршрутизации в энергосетях следующего поколения), использованы в проектно-конструкторской деятельности ООО «Теком» при выполнении проекта «Разработка системы неоперативного управления и мониторинга трансформаторно-тиристорными регуляторами напряжения и мощности с расщепленной первичной обмоткой трансформатора с ключами однонаправленного тока (ТТРНМ ОТ)». Получены свидетельства о государственной регистрации исходных кодов для распределенной системы мониторинга и управления (РСМУ) и активно-адаптивной системы управления (ААСУ). Данные системы внедрены в рамках работ по государственному контракту ГК№ 16.526.12.6016 от 11 октября 2011 г. по теме «Разработка и

создание типового ряда трансформаторно-тиристорных регуляторов напряжения и мощности с расщепленной первичной обмоткой трансформатора и ключами однонаправленного тока в части разработки активно-адаптивной системы управления (ААСУ) и распределенной системы мониторинга и управления (РСМУ)» ООО «Теком» при строительстве новой цифровой трансформаторной подстанции по адресу г. Нижний Новгород, ул. Минина 24 к.5. Данные работы были выполнены в соответствии с договором №11-692-1 от 11 ноября 2011 года между ООО «Теком» и ФГБОУ ВПО НГТУ им. Р.Е. Алексеева, что подтверждается актом внедрения от 02 сентября 2013 г.

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

- XIV международной научно-техническЬй конференции «Информационные системы и технологии ИСТ - 2008» (г. Нижний Новгород, 2008);

- XIII Нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2008);

- XIV Нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2009);

- XVI международной научно-технической конференции «Информационные системы и технологии ИСТ - 2010» (г. Нижний Новгород, 2010);

- XVII Нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2012);

- XVIII международной научно-технической конференции «Информационные системы и технологии ИСТ - 2012» (г. Нижний Новгород, 2012).

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

Структура и объем диссертации. Текст диссертационной работы состоит из введения, четырех глав, заключения, списка литературы и трех приложений. Объем работы составляет 154 страницы сквозной нумерации, в том числе 142 страницы основного текста (57 рисунков и 11 таблиц), список использованных источников из 60 наименований на 7 страницах, 5 страниц приложений.

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

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

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

гриды. Рассмотрена архитектурная схема вычислительных гридов, ориентированная на использование служб (SOA - Service Oriented Architecture) и существующие стандарты: открытая инфраструктура грид-служб (Open Grid Services Infrastructure - OGSI и структура ресурсов веб служб (Web Services Resource Framework — WSRF). Проанализирована работа инструментального комплекса Globus Toolkit, с помощью которого возможно создание и конфигурация вычислительных гридов. Также показаны задачи информационных ресурсов (каталогов). Был рассмотрен ряд работ в области архитектуры информационных ресурсов в существующих на сегодняшний день вычислительных гридах. Базовым понятием архитектуры системы является топология объединения ее элементов. Основной недостаток построения каталогов в гридах — централизованная топология. Исходя из этого:

• Центральный каталог непременно содержит устаревшую информацию о состоянии ресурсов организации;

• Нагрузка на узлы грида крайне неравномерна, в частности центральный информационный ресурс она гораздо выше, чем на периферийные узлы;

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

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

• Кратчайшая средняя длина минимальна;

• Число связей минимально;

• Степень вершины графа не превышает значение d.

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

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

• Поиск оптимальной топологии грида;

• Разработка децентрализованного механизма динамического обнаружения ресурсов (discovery) в гриде и протокола поиска ресурсов в нем;

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

• Разработка механизма компенсации неравномерных нагрузок;

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

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

• Каскадные аварии;

• Отсутствие достаточной связности между узлами;

• Невозможность компенсации энергодефицита в разных районах города; Ниже сформулированы основные задачи для системы управления

интеллектуальными энергосетями, решаемые в настоящей диссертационной работе:

• Поиск оптимальной топологии энергосети, где критерием оптимальности является равномерность нагрузки в сети.

• Разработка и внедрение алгоритма управления отказами для интеллектуальной энергосети;

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

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

Во второй главе производится построение математической модели сетей следующего поколения на основе теории графов. В начале главы рассмотрен топологический подход к конструированию сетей следующего поколения. Показаны ключевые параметры сетей: количество узлов сети (V), количество связей (£), распределение степеней вершин сети (d), среднее кратчайшее расстояние между узлами сети (С®)> диаметр сети (/D), коэффициент кластеризации (С), вариативность (Кг), степень централизации (О) и другие. Для поиска оптимальной топологии вычислительных гридов по критерию и ограничениям, показанным выше, были проанализированы известные топологии: звездообразная и полносвязная. Также были проанализированы сети тесного мира и методика их построения Ваттса-Строгатса. Исследованы случайные графы Эрдеша-Реньи и безмасштабные сети Барбаши-Альберта, исследована важность закона преимущественного присоединения и влияния вариативности для возникновения эффекта тесного мира. Однако рассмотренные топологии не удовлетворяют одновременно критерию и ограничениям, указанным ранее.

Далее была решена задача поиска оптимальной топологии графа, которая удовлетворяет критерию оптимальности минимума кратчайшей средней длины пути при ограничении числа ребер графа и степени вершины узла. Оптимальной топологией является фрактал с ограниченной степенью вершин (Limited Degree Fractal - LDF), частный случай дерева Кэйли. Пример оптимальной топологии вычислительного грида представлен на рис. 1 для d = 41N = 4, где N - есть количество уровней сети:

Рис. 1. Четырехуровневый полностью заполненный ЬБР фрактал.

Данное дерево имеет К = ¿((с/-1)"узлов, Е=У-1 связей. Диаметр

2

, 1п(К) ' 1п(с/)'

сети равен = 2 • (Л' -1),

Коэффициент кластеризации равен: вершин показано ниже:

1

а средняя минимальная длина равна /,„ 2

С =

Распределение степеней

вершин имеют степень (I

и

-1—- вершин имеют степень 1 с/

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

• граф построен, и в начальный момент времени его узлы свободны;

• каждая вершина графа является каталогом и содержит информацию о ресурсах только смежных с данным узлом вершин;

• если степень вершины равна единице, то при запросе ресурсов у данного узла, происходит передача данной информации инициатору;

• Грид является сетью с отчуждаемыми ресурсами, т.е. существует возможность полного захвата ресурсов другим узлом;

• все узлы грида имеют одинаковое количество ресурсов, т.е.

а=а=-..=е.

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

При запросе ресурсов любой узел передает три поля:

• идентификатор узла, который захватывает ресурсы;

• количество ресурсов, которое необходимо захватить;

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

После обработки запроса адресатом, последний генерирует ответ, в котором содержится таблица, состоящая из трех столбцов:

• маршрут до узла, у которого были захвачены ресурсы;

• количество захваченных ресурсов у данного узла;

• служебные отметки, в случае, если данный узел имеет только одну смежную вершину.

Необходимо упомянуть два важных замечания: во-первых, необходимо предусмотреть механизм отказа от резервирования ресурсов, в случае, если зарезервировано больше ресурсов, чем необходимо инициатору. Во-вторых, захват ресурсов считаем равновероятным. Диаграмма коммуникаций (ресурсные запросы и ответы) для захвата восьмым узлом q = 3 • Q ресурсов

вычислительном гриде, представленным на рис. 2(a), показана на рис. 2(b):

" " 1—

131 ж.

Г 12 ) 1131 И ».; •«!

У/

"ч '4'-(м) -«-"-»К,» ..ч^fT)_

I _

"" ' " |l> I n I .1

Ъ-^^

.....

HIK'JI*!

V -О»!

V - 1 1

©■ ' Й (а) (Ь)

Рис. 2. Вычислительный грид и диаграмма коммуникаций.

Кроме этого, исследуются топологии энергетической сети и показана оптимальная топология энергетической сети, критерием нахождения которой является равномерное распределение нагрузки на узлы сети, а ограничением — степень вершины графа больше двух. Оказалось, что без исключения радиальной топологии невозможно получить приемлемое решение задачи. Таким образом, потребителей питают трансформаторные подстанции," которые являются узлами коммутации одного уровня, связанные между собой и охватывающие всю обслуживаемую территорию. Фактически была предложена равномерно-распределенная сеть, где золы коммутации имеют возможность маршрутизировать нагрузку на и ближайших направлений. Предложена концепция построения распределенной электрической сети, как совокупности равномерно-распределенных узлов нагрузки, организованных таким образом, чтобы территория города была покрыта равномерно-распределенной сетью. Компланарное представление гексагональных сетей представлено на рис. 3:

Рис. 3. Компланарное представление распределительных сетей

В третьей главе диссертационной работы исследуются механизмы распределения нагрузки в вычислительных гридах следующего поколения, оптимальной топологии, поскольку нет данных, что распределение нагрузки в них будет относительно равномерным. Каждый узел грида имеет равное количество ресурсов Q и захватывает ? = К ■ {? ресурсов, где К й <1 — натуральное число. Перед каждым запросом считаем грид ненагруженным. Таким образом, суммируя количество занятых узлов каждого уровня отдельно и относя полученные величины к количеству узлов каждого уровня, имеем распределение нагрузки при заданном радиусе сети, запрашиваемом числе ресурсов и заданной степени вершины грида с1. Аналитическое выражение для нагрузки на произвольный уровень п децентрализованного полностью заполненного грида, в общем виде при ц<.с1 в зависимости от ц, с], N имеет следующий вид:

\

/

+ (<7-1)4,*-, 4,1 +(<*- Ч,<*-„ +

(2)

а-д +1 а-д +1 * d-qг + 1

где: = • 0' символ Кронекера;

J . ^ ^ — инвертированный символ Кронекера; 1> **к

, — степ-функция;

- инвертированная степ-функция.

Было проведено сравнение максимальных нагрузок для грида с организацией информационных ресурсов в виде ЬБР с вычислительной сетью, где каталог — есть центральный узел в звездообразной архитектуре сети. Нетрудно заметить, что при увеличении количества ресурсов в М раз, максимальная нагрузка имеет вид: /?„„ = (м • V -1)6. Т.е. рост максимальной нагрузки составляет приблизительно М раз. При увеличении количества захватываемых ресурсов в К раз, максимальная нагрузка на центральный узел будет неизменной. Для анализа динамики изменения максимальной нагрузки ЬБР сети, была создана программная модель, которая определяет распределение нагрузок каждого уровня грида в зависимости от количества уровней и количества захватываемых ресурсов д = К д , но при этом К<с1. Обнаружено, что:

• Максимальная нагрузка ЬБР сети наличествует на уровне N-2, в случае, если количество уровней больше двух. В противном случае получаем классический грид с максимальной нагрузкой на центральный узел;

• Нагрузка уровня п зависит от:

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

• Нагрузка не зависит от количества узлов сети при N>4. Отсюда следует, что при неизменных значениях <?, с/, нагрузки на уровни 1, N-2, N-1, N будут неизменны при любом N >4. Данное следствие является основным преимуществом 1Л)Р сети над классическим гридом.

• Значения максимальной нагрузки в зависимости от количества уровней децентрализованного грида при захвате q = Q или ? = ресурсов представлены в следующей таблице:

Таблица 1. Значения в зависимости от N при ц-й или д = Ы ■ д

Количество уровней 1ЛЭР сети * плх

N = 2 = ад

ЛГ = 3 ^ =¿<2

N>4

• Для уменьшения максимальной нагрузки необходимо уменьшать степень вершины грида и увеличивать количество уровней сети. Однако, при малых значениях <Л и большом N будет расти средняя минимальная длина пути. Следовательно, 1ЛЭР сеть перестанет проявлять свойства сетей тесного мира.

Получение аналитического выражения для случая К>Ы сопряжено с некоторыми трудностями. Однако, при необходимости ограничения степени вершины для сохранения эффекта тесного мира в графах так, как показано выше, захват д = К-() ресурсов, где К>с!, становится весьма вероятен. Оказалось, что для 1Л)Р сети, где N = 4 | ¿1 = 6, при захвате ^ = (2с/ —1)0 ресурсов, максимальная нагрузка на центральный узел совпадает с максимальной нагрузкой гридов, у которых каталог является центром

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

При авариях на каналах связи либо на ресурсах, степени вершин которых не равны единицам, грид распадется на несколько работоспособных сегментов. Устойчивость LDF сети к ошибкам была экспериментально исследована методами теории перколяции. Была создана программная модель, где случайным образом происходило удаление узлов сети. Оказалось, что при произвольном удалении вершин графа существует критическое значение, выше которого сеть распадется на отдельные сегменты: X = d-1. При ограничениях, налагаемых на d, очевидно, что LDF сети при авариях на нескольких узлах распадутся на кластеры. Предложены методики обнаружения различных видов неисправностей в сегментах сети. Реакция системы на обнаружение той или иной ошибки может быть чрезвычайно разнообразной в зависимости от вида грида, технической возможности, сути ошибки: от уведомления администраторов домена до реконфигурации сети. Все неисправности концептуально можно разделить на два типа:

• Некорректная работа узла - ресурс доступен, каталог ресурсов работает корректно. Для части заданий К, выполненных за последние Т единиц времени, был возвращен код ошибки, либо были возвращены некорректные значения тестовых заданий;

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

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

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

Существует множество теоретических вариантов реконфигурации сети, однако, в силу географической удаленности отдельных узлов существует ненулевая вероятность, что указанный вариант будет единственным. Более того, при наличии технической возможности следует использовать данные каналы, а не держать их в резерве, поскольку данные связи, с одной стороны будут уменьшать неравномерность нагрузки в LDF сети, а с другой стороны уменьшается вероятность потери связности в графе. Стоит также заметить, что при добавлении хотя бы одной связи между узлами последнего уровня, в графе появляются циклы, следовательно, размывается и исчезает само понятие «уровень сети». Под нагрузкой на узел будем понимать количество ресурсов q„ захваченных на ресурсе v, при последовательном захвате q = K Q ресурсов

всеми остальными ресурсами.

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

• Алгебраическая связность максимальна: Я, -> max ;

• Средняя минимальная длина пути минимальна: щ -* min;

Ограничения данной задачи показаны ниже:

• Количество связей в достроенном гриде не более | 1.11V \;

• Степень вершины узла не превышает d.

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

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

р—«с GO g] [Ц Ш »

шшвш "

и М

[Е [Е [И ®

> шшш®

—« ЕШЕ® р—* цз [ц ® Е

М

Рис. 5. Процесс скрещивания по методу кроссинговера Пусть существуют две особи: 5659 и 4769, показанные на рис. 5(a). Изменим вид особей, переписав гены относительно осей в матрице смежности. Вид особей и процесс кроссинговера показан на рис. 5(b). Результат скрещивания и образования популяции показан на рис. 5(c). Для обеспечения генетического разнообразия особей необходимо вводить «мутантов». Т.е. часть генов у части особей заменяются на случайные значения. Разнообразие особей необходимо, чтобы избежать попадания в область локального минимума. Необходимо заметить, что автор использует треугольную матрицу смежности, без главной диагонали. Следовательно, дети должны удовлетворять условиям:

• Для любого гена особи: х> у, х * у;

• Для любой особи: сумма рядов и столбцов матрицы смежности не должна превышать значение d-1;

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

Некоторое количество детей не будет удовлетворять условиям, указанным выше. Следовательно, данные особи не прошли естественный отбор и будут уничтожены. Остается 2L<K<4L особей, для каждой из которых находим алгебраическую связанность и минимальную среднюю длину пути. Ищем лучшие L структур, согласно критерию, указанному ранее. Повторяем в цикле последовательность действий, описанную выше до срабатывания останова генетического алгоритма. Критерий останова генетического алгоритма по поиску оптимальной структуры с добавлением \Е'\ связей: в случае, если на протяжении Я поколений после нахождения какой-либо особи, отсутствуют особи с лучшими параметрами, и при этом, оптимальные параметры особи лучше, чем при добавлении Ifi'l-1 связей, то считаем

Роюттль t Рооитальг

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

Результатом работы генетического алгоритма является | Е'\ * 0,11 У'1 структур, для каждой из которых добавлено |£*| «1...~0,1|П связей и найдены параметры алгебраической связности, и средней минимальной длины пути. Кроме этого, для каждой найденной оптимальной структуры вычисляем набор пик-факторов нагрузок в зависимости от количества захваченных ресурсов.

Генетический алгоритм был верифицирован на сетях:

• /V-* </«.3; |С|-10е ?=(? 6(?;

• N-4: </»4; |К|-5Э; |Г|*1...5; 9*2(7...90.

Для первой сети с помощью генетического алгоритма были найдены оптимальные структуры за 0.13с при // — 41 — 4. При решении задачи с помощью метола полного перебора, задача была решена за 53с. Для второй сети с помощью генетического алгоритма были найдены оптимальные структуры за 64с при // = 20| = 20. При решении задачи с помощью метода полного перебора (с принудительно определенной первой связью), задача была решена за 271ч. Таким образом, показано, что с ростом сети преимущество генетического алгоритма увеличивается.

Далее исследуется результат работы генетического алгоритма на больших сетях. где N = 5. ¿ = 5; = 426; = 1. 43; д = Параметры

генетического алгоритма Н = 2001 £ = 200. Программа была выполнена трижды. Вторая и третья итерации не выявили ни одной структуры, чьи параметры были бы оптимальнее, чем у структур, найденных во время первого выполнения. Время работы генетического алгоритма для первой, второй и третьей итерации равно, соответственно. 382, 374. 378 часов. Ниже показаны изменения максимального пик-фактора нагрузки (в процентах), изменение (в

процентах), рост Л, (в процентах) и нормированное семейство зависимостей пик-фактора нагрузки в зависимости от количества связей, соответственно:

Рис. 6. Изменение максимального пик-фактора нагрузки в процентах

16

Рис. 7. Изменение средней минимальной длины пути в процентах

ш

1

1

н

-

-Ш-

• 1 * •

Рис. 8. Рост алгебраической связности в процентах

В четвертой главе приведен разработанный алгоритм управления отказами в первом уровне интеллектуальной энергосети. Данный алгоритм разработан в рамках работ по государственному контракту ГК №14.516.11.0104 от 14 октября 2013 г. по теме «Разработка алгоритмов управления передачи и распределения электрической энергии в интеллектуальной распределительной электрической сети». Схема данных и примеры аварий в энергетических сетях

показаны ниже:

и

(П. "0 400)

• »I ®.1>

• Ш2 (П. 14. |.0 1| И» 300

Рис. 10. Примеры схемы данных и аварий в энергетических сетях Алгоритм охватывает следующие аварийные ситуации:

• Отказ питающей линии узла, через который не осуществляется транзит (авария между узлами Е и 7 на рис. 10);

• Наличие тока критических значений на одной из линий сети (линия между узлами О и 8 на рис. 10);

• Отказ питающей линии узла, через который осуществляется транзит (авария между узлами 12 и 15, рис. 10), равно отказ высоковольтной линии (авария на линии Р, рис. 10).

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

Каждый узел энергетической сети находится в соответствии с элементом информационной сети. Данный элемент - есть интегрированный модуль системы управления электрическими сетями (ИСУЭС). Кроме этого в сети есть узлы, осуществляющие распределенный мониторинг и управление <узлы РСМ) модулями ИСУЭС.

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

Разработанный протокол маршрутизации работает со следующими допущениями:

• Каждой ИСУЭС присвоен уникальный числовой идентификатор;

• В каждой ИСУЭС содержится список родительских РСМ. Требуется обеспечить маршрутизацию сообщений от ИСУЭС до любой РСМ из этого списка;

• Идентификаторы всех РСМ хранятся в конфигурации ИСУЭС;

• РСМ имеет информацию о топологии всей сети и своевременно получает информацию о ее изменении.

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

В заключении диссертации сформулированы основные результаты работы.

В приложениях диссертации приведены копии документов,

подтверждающие практическое использование результатов исследований.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

3. Исследованы структуры сетей с ограниченной степенью вершин и разработаны для них:

a. алгоритм роста сети;

b. алгоритм управления отказами;

c. протокол поиска ресурсов.

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

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

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

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

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

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

в ведущих рецензируемых научных журналах и изданиях из перечня ВАК министерства образования и науки РФ:

1. Анисимов, С. А. Распределение нагрузки в децентрализованных гридах, обладающих свойствами тесного мира / С.А. Анисимов // Вестник Нижегородского государственного университета им. Н.И. Лобачевского. -2011.-№3(2).-С. 173-179.

2. Анисимов, С. А. Управление отказами в децентрализованных гридах обладающих свойствами тесного мира / С.А. Анисимов // Вестник Нижегородского государственного университета им. Н.И. Лобачевского. -2011.-№6(1).-С. 214-218.

3. Лоскутов, А.Б. Разработка протокола маршрутизации в распределенных электрических сетях 10 - 20 кВ / А.Б. Лоскутов, E.H. Соснина, С.А. Анисимов // Журнал «Информационно-измерительные и управляющие системы». 2012. - №12. - С. 53-58.

Свидетельства о государственной регистрации

4. Свидетельство о государственной регистрации программы для ЭВМ №2013611038. Распределенная система мониторинга и управления трансформаторно-тиристорными регуляторами напряжения и мощности с расщепленной первичной обмоткой трансформатора и ключами однонаправленного тока (ТТРНМ ОТ): заявка №2012660495 от 30.11.2012 РФ / Анисимов С.А., Васин М.А., Ивлев Е.Е., Лоскутов А.Б., Полозов И.В., Савельев М.Е., Смирнов А.И., Суров И.В. (РФ). - Зарегистрировано в Реестре программ для ЭВМ 09.01.2013 (РФ). - 2с.

5. Свидетельство о государственной регистрации программы для ЭВМ №2013611564. Активно-адаптивная система управления трансформаторно-тиристорными регуляторами напряжения и мощности с расщепленной первичной обмоткой трансформатора и ключами однонаправленного тока (ТТРНМ ОТ): заявка №2012660545 от 03.12.2012 РФ / Анисимов С.А., Васин М.А., Ершов В.А., Лоскутов А.Б., Полозов И.В., Смирнов А.И., Суров И.В., Туркин А.Е. (РФ). - Зарегистрировано в Реестре программ для ЭВМ 25.01.2013 (РФ). - 2с.

в прочих научных журналах и изданиях

6. Анисимов, С.А. Алгоритмы управления отказами в энергетических гридах следующего поколения / С.А. Анисимов, М.Н. Ушакова // Технические науки XVII Нижегородская сессия молодых ученых: материалы научно-технической конференции. - Нижний Новгород: НИУ РАНХиГС, 2012. С. 112-114.

7. Анисимов, С.А. Исследование свойств тесного мира сети Интернет / С.А. Анисимов, В.А. Зыбин // Труды НГТУ им. P.E. Алексеева. -2009. -Т. 74. - Вып. 15.-С. 56-63.

8. Анисимов, С.А. Модели грид-систем следующего поколения / С.А. Анисимов // Информационные системы и технологии. ИСТ - 2008: тезисы докладов 14ой Международной научно-технической конференции / НГТУ им. P.E. Алексеева - Н. Новгород: Изд. НГТУ, 2008. - С. 113.

9. Анисимов, С.А. Оценка ключевых параметров в децентрализованных грид-системах, построенных с использованием свойств сетей тесного мира/ С.А. Анисимов // Тезисы докладов 14-й Нижегородской сессии молодых ученых (технические науки) / НГТУ им. P.E. Алексеева -Н. Новгород: Изд. НГТУ, 2009 - С. 31-32.

10. Анисимов, С.А. Перспективы грид-систем / С.А. Анисимов // Тезисы докладов 13-й Нижегородской сессии молодых ученых (технические науки) / НГТУ им. P.E. Алексеева - Н. Новгород: Изд. НГТУ, 2008 - С. 4.

11. Анисимов, С.А. Протокол поиска ресурсов в децентрализованных гридах, обладающих свойствами тесного мира / С.А. Анисимов, В.А. Зыбин, В.В. Крылов // Труды НГТУ им. P.E. Алексеева. - 2010. - Т. 80. - С. 13-19.

12. Анисимов, С.А. Разработка схемы данных для активно-адаптивной системы управления в энергетических распределительных сетях следующего поколения / С.А. Анисимов, И.В. Полозов, М.Н. Ушакова // Информационные системы и технологии. ИСТ - 2012: тезисы докладов 18-ой Международной научно-технической конференции / НГТУ им. P.E. Алексеева - Н. Новгород: Изд. НГТУ, 2012. - С. 232.

13. Анисимов, С.А. Распределение нагрузки в децентрализованных гридах, обладающих свойствами тесного мира / С.А. Анисимов // Информационные системы и технологии. ИСТ — 2010: тезисы докладов 16-ой Международной научно-технической конференции / НГТУ им. P.E. Алексеева - Н. Новгород: Изд. НГТУ, 2010. - С. 124-125.

14. Разработка архитектуры системы управления трансформаторно-тиристорными регуляторами напряжения и мощности с ключами однонаправленного тока (ТТРНМ ОТ) / С.А. Анисимов, А.Б. Лоскутов, И.В. Полозов, А.И. Смирнов, E.H. Соснина // Труды НГТУ им. P.E. Алексеева. - 2013. -№1(98). - С. 184-193.

15. Разработка протокола маршрутизации в распределенных энергетических гридах следующего поколения / С.А. Анисимов, А.Б. Лоскутов, И.В. Полозов, А.И. Смирнов, E.H. Соснина // Труды НГТУ им. P.E. Алексеева. - 2012. - №4(97). - С. 224-231.

Личный вклад автора. Все основные положения диссертации разработаны автором. В работах, написанных в соавторстве, автору принадлежат разработка протоколов маршрутизации [3, 15], разработка схемы данных и протокол управления отказами для гексагональных сетей [6, 12], исследование вариативности [7], разработка протокола поиска ресурсов в вычислительных гридах [11], разработка архитектуры системы управления для перспективных энергосетей [14].

Подписано в печать 21.10.2013. Формат 60 х 84'Лб. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 751.

Нижегородский государственный технический университет им. P.E. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.

Работа выполнена на кафедре «Теория цепей и телекоммуникации» Нижегородского государственного технического университета

им. P.E. Алексеева

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

О 4 2 О 1 4- 5 2 2 2 О Анисимов Сергей Анатольевич

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

и интеллектуальных энергосетей

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

промышленности)» (технические науки)

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

Научный руководитель д.т.н. Крылов Владимир Владимирович

Нижний Новгород - 2013

ВВЕДЕНИЕ.....................................................................................................................3

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ РАЗРАБОТОК В ОБЛАСТИ ПОСТРОЕНИЯ СЕТЕЙ СЛЕДУЮЩЕГО ПОКОЛЕНИЯ.................................10

1.1 Вычислительные и энергетические сети..................................................10

1.2 Существующая архитектура вычислительных и энергетических сетей........................................................................................................................14

1.3 Существующая архитектура информационных ресурсов...................37

1.4 Выводы............................................................................................................46

ГЛАВА 2. АНАЛИЗ МАТЕМАТИЧЕСКОЙ МОДЕЛИ СЕТЕЙ СЛЕДУЮЩЕГО ПОКОЛЕНИЯ..............................................................................48

2.1 Модели грида.................................................................................................48

2.2 Оптимальная топология грида..................................................................61

2.3 Оптимальная топология энергетической сети......................................71

2.4 Выводы............................................................................................................74

ГЛАВА 3. ИССЛЕДОВАНИЕ МЕХАНИЗМА РАСПРЕДЕЛЕНИЯ НАГРУЗКИ НА УЗЛЫ В Ы)Г ГРИДАХ.............................................................75

3.1 Нагрузка в гридах.........................................................................................75

3.2 Алгоритм управления отказами в ЬББ сетях.........................................82

3.3 Борьба с недостатками топологии ЬБР сетей........................................86

3.4 Постановка задачи оптимизации топологии графа.............................88

3.5 Решение задачи оптимизации топологии графа с помощью генетического алгоритма.................................................................................108

3.6 Выводы..........................................................................................................124

ГЛАВА 4. РАЗРАБОТКА АЛГОРИТМОВ В СИСТЕМЕ УПРАВЛЕНИЯ ИНТЕЛЛЕКТУАЛЬНЫМИ ЭНЕРГОСЕТЯМИ.................................................125

4.1 Алгоритмы управления отказами в энергетических сетях следующего поколения....................................................................................125

4.2 Разработка алгоритма маршрутизации в энергетических сетях

следующего поколения....................................................................................131

4.3 Внедрение алгоритмов в интеллектуальных энергосетях.................139

4.4 Выводы..........................................................................................................140

ЗАКЛЮЧЕНИЕ..........................................................................................................141

СПИСОК ЛИТЕРАТУРЫ........................................................................................[143

ПРИЛОЖЕНИЕ 1.....................................................................................................Л 50

ПРИЛОЖЕНИЕ 2.....................................................................................................¡152

ПРИЛОЖЕНИЕ 3......................................................................................................¡154

ВВЕДЕНИЕ

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

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

Актуальность

Одной из важнейших потребностей общества является решение различных прикладных задач в области молекулярной биологии, гидрологии, систем прогнозирования, и др. Для решения сложных вычислительных задач обычно используют одну из парадигм распределенной вычислительной инфраструктуры. Наиболее перспективный способ - использование гридов, которые объединяют гетерогенные ресурсы, одним из типов которых являются специальные ресурсы хранения: информационные ресурсы (каталоги). Каталог осуществляет обнаружение, учет использования, совместное выделение ресурсов, мониторинг состояния грида. Проанализировав различные реализации архитектур гридов, представленные в [12, 13, 15, 16, 30, 35, 42-43, 46, 57], оказалось, что все они

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

Другой важной потребностью является надежное обеспечение электроснабжения. Данная потребность является настолько актуальной, что является одной из основных стратегических целей развития электроэнергетики. В настоящее время в энергетических сетях используются радиальные топологии, которые имеют следующие недостатки: усугубление последствий каскадных аварий, отсутствие достаточной связности между узлами сети, следствием чего является невозможность обеспечить отключенных потребителей электроэнергией, и принципиальная невозможность скомпенсировать дефицит электроэнергии в некоторых районах города. Кроме этого сети 6-10 кВ и ниже практически не имеют управления. Существует концепция Smart grid - интеллектуальных энергосистем следующего поколения, где параллельно энергосетям построена информационная сеть, с помощью которой происходит передача информации между различными устройствами и между потребителями и поставщиками электроэнергии. Для устранения недостатков, указанных выше необходимо предложить оптимальную топологию энергосетей. Топология информационной сети, в данном случае, будет совпадать с архитектурой энергосетей следующего поколения.

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

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

Объект и предмет исследования

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

Цель работы

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

Задачи работы

В данной работе поставлены и решены следующие задачи:

1. Построена математическая модель сетей следующего поколения.

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

3. Разработан протокол поиска ресурсов в перспективных вычислительных гридах.

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

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

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

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

Для решения поставленных задач использовался математический аппарат

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

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

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

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

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

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

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

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

Результаты исследований, полученные автором в работе (алгоритм

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

расщепленной первичной обмоткой трансформатора с ключами однонаправленного тока (ТТРНМ ОТ)». Получены свидетельства о государственной регистрации исходных кодов для распределенной системы мониторинга и управления (РСМУ) [24], (см. Приложение 1) и активно-адаптивной системы управления (ААСУ) [25], (см. Приложение 2).

Данные системы внедрены в рамках работ по государственному контракту ГК № 16.526.12.6016 от 11 октября 2011 г. по теме «Разработка и создание типового ряда трансформаторно-тиристорных регуляторов напряжения и мощности с расщепленной первичной обмоткой трансформатора и ключами однонаправленного тока в части разработки активно-адаптивной системы управления (ААСУ) и распределенной системы мониторинга и управления (РСМУ)» ООО «Теком» при строительстве новой цифровой трансформаторной подстанции по адресу г. Нижний Новгород, ул. Минина 24 к.5. Данные работы были выполнены в соответствии с договором №11-692-1 от 11 ноября 2011 года между ООО «Теком» и ФГБОУВПО НГТУ им. P.E. Алексеева, что подтверждается актом внедрения от 02 сентября 2013 г. (см. Приложение 3).

Апробация работы

Основные результаты работы были доложены на:

• XIV международной научно-технической конференции «Информационные системы и технологии ИСТ - 2008» (г. Нижний Новгород, 2008);

• XIII Нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2008);

• XIV Нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2009);

• XVI международной научно-технической конференции «Информационные системы и технологии ИСТ - 2010» (г. Нижний Новгород, 2010);

• XVIII международной научно-технической конференции «Информационные системы и технологии ИСТ - 2012» (г. Нижний Новгород, 2012).

Публикации

Основное содержание диссертации отражено в 15 публикациях [1-10, 19, 21-22, 24-25], три из которых, опубликованы в изданиях, рекомендованных ВАК [8, 10, 19]. Получены два свидетельства государственной регистрации программ для ЭВМ [24-25].

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

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

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

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

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

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

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

Текст диссертационной работы состоит из введения, четырех глав, заключения, списка литературы и трех приложений. Объем работы составляет 154 страницы сквозной нумерации, в том числе 142 страницы основного текста (57 рисунков и 11 таблиц), список использованных источников из 60 наименований на 7 страницах, 5 страниц приложений.

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

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

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

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

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ РАЗРАБОТОК В ОБЛАСТИ ПОСТРОЕНИЯ СЕТЕЙ СЛЕДУЮЩЕГО ПОКОЛЕНИЯ

1.1 Вычислительные и энергетические сети

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

1.1.1 Предпосылки создания вычислительных и энергетических сетей следующего поколения

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

объединяющие высокопроизводительные компьютерные системы, могут стать средством организации вычислений следующего поколения. В настоящее время существует несколько парадигм распределенного компьютинга: кластерные вычисления, одноранговые сети (Р2Р), общая архитектура брокера объектных запросов (Common Object Request Broker Architecture - CORBA) и др. Кроме данных технологий также развивается парадигма грид-компьютинга. Стоит отличать непосредственно технологию грид и методику параллельных вычислений. Основной задачей грида является коор