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

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

Антонова Анастасия Анатольевна

РАЗРАБОТКА МАТЕМАТИЧЕСКОГО И АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ УПРАВЛЕНИЯ ИНФОРМАЦИОННЫМИ ПОТОКАМИ В СЛОЖНЫХ НЕСТАЦИОНАРНЫХ СИСТЕМАХ НА ОСНОВЕ ТЕОРИИ СЛУЧАЙНЫХ ГРАФОВ И ПЕРКОЛЯЦИИ

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

2 6 ДПР 2012

АВТОРЕФЕРАТ

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

Москва 2012 г.

005019350

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

Научный руководитель: доктор технических наук, профессор

Морозова Татьяна Юрьевна

Официальные оппоненты: доктор технических наук, профессор

Гарипов Вадим Кадимович ФГБОУ ВПО МГУПИ, профессор

кандидат физико-математических наук, доцент

Хакимуллин Евгений Робертович ФГБОУ ВПО МГИЭМ (ТУ), профессор

Ведущая организация: ООО КБ " ЭлектронСистема"

Защита состоится 16 мая 2012 г., в 12-00 часов, на заседании диссертационного совета Д.212.119.02, при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Московский государственный университет приборостроения и информатики» по адресу: 107996, г. Москва, ул. Стромынка, д. 20.

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

Автореферат разослан 14 апрель 2012 г.

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

Г.В.Зеленко

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

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

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

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

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

Рассмотренные аспекты организации функционирования информационных сетей подтверждают актуальность диссертации. Данная тематика так же соответствует Указу Президента Российской Федерации от 7 июля 2011 г. № 899 «Об утверждении приоритетных направлений развития науки, технологий и техники в Российской Федерации». В частности, развития информационно-телекоммуникационных систем.

Для изучения таких сложных объектов, как современные информационные системы, в начале этого века начала активно развиваться теория сложных сетей, которая основывается на классических случайных графах (Альфред Реньи (A.Renyi), Пол Эрдеш (P.Erdos), 1959 г.). Однако в 1999 году А-Л.Барабаши (A-L.Barabasi), Река Алберт (Reka Albert) изучили одно из проявлений феноменологии критических явлений в сложных системах - безмасштабные сети. В изучение случайных графов внесли

свой значительный вклад и русские ученые (В.Е.Степанов, В.Ф.Колчин, А.М.Райгородский и др.).

Динамические процессы, протекающие в информационных сетях, характеризующиеся случайностью и недетерминированностыо, требуют применения адекватного математического аппарата, которым являются методы перколяции. Изучением и развитием теории перколяции занимаются такие отечественные ученые, как: Ю.Ю.Тарасевич, С.А.Просандеев, Х.Кестен, Б.И.Шкловский. Однако основной вклад в развитие теории перколяции внесли зарубежные ученые: С.К.Броадбент (S.K.Broadbent), Ж.М.Хаммерсли (J.M.Hammersley), (R.C.Brower), (Р.Ташауо) и многие другие.

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

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

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

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

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

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

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

4. Разработан алгоритм выделения и защиты многосвязного узла в сложных системах.

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

Объект исследования: процесс взаимодействия элементов сложной нестационарной системы и потоков данных.

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

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

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

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

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

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

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

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

Разработанное программное обеспечение было использовано в системах контроля объектов специального назначения. Разработанное программное обеспечение внедрено в ООО "ТриоИнжиниринг", что подтверждено актом о внедрении.

Одним из основных результатов, полученных в ходе исследования, является алгоритм управления информационными потоками данных, который использован в учебном процессе при подготовке специалистов по ГОСВПО 230101 на кафедре «Персональные компьютеры и сети» ФГБОУ ВПО «Московский государственный университет приборостроения информатики», что подтверждено актом о внедрении.

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

Апробация работы. Наиболее важные результаты докладывались на международной конференции «Новейшие научные достижения - 2012» (Болгария, г. София, 2012 г.), международной конференции «Методы и алгоритмы принятия эффективных решений» (г. Таганрог, 2009 г.)

Основные положения и результаты работы докладывались и обсуждались на кафедре «Автоматизированные системы управления и информационные технологии» ФГБОУ ВПО «Московский государственный университет приборостроения и информатики».

Публикации. По теме диссертации опубликовано 11 научных работ, в том числе, три - в журналах, рекомендованных ВАК РФ. Получено свидетельство о государственной регистрации программ для ЭВМ в Федеральной службе по собственности, патентам и товарным знакам (РОСПАТЕНТ) № 2012610363,24 января 2012 г.

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

Основная часть диссертации содержит 138 страниц машинописного текста, включая 31 рисунков и 5 таблиц.

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

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

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

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

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

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

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

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

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

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

В диссертационной работе введены следующие определения.

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

Определение 2. Сильно связная компонента (кластер) - это множество узлов, где любые два узла достижимы друг из друга.

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

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

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

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

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

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

Определение 4. Степень узла - сумма числа входящих и выходящих связей.

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

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

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

Пусть производящая функция вероятности распределения степеней узлов имеет вид

по

^¡>(*) = О)

о

гдерк- вероятность того, что случайно выбранный узел имеет степень к; <7^- вероятность того, что узел помечен, учитывая, что он имеет степень к; РкЧк ~ вероятность того, что узел имеет степень ^ и он помечен. Обозначим общую долю занятых узлов - д Тогда = В

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

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

(2)

ъм 2

где 2 - средняя степень узла.

Пусть Я|(х) - производящая функция, характеризующая вероятность

того, что один конец случайно выбранной связи в сети приводит к перколяционному кластеру данного числа занятых узлов. Кластер может содержать крайний узел в конце связи с вероятностью 1-/^(1) или связь может привести к заполненному узлу со степенью к с вероятностью /^(1). Это означает, что удовлетворяет условия самоорганизации вида:

(3)

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

(4)

Совокупность уравнений (1) - (4) позволяет определить распределение размера кластера для задачи узлов перколяции, средний размер кластера, значение порога перколяции и размеры компоненты.

В частном случае равномерного распределения вероятности пометки узлов, Цк=Ц для всех к , уравнения (3) и (4) упрощаются:

/>(х) = 1-<7+фсОДх)], (5)

ад = 1-3+фс<ад(дг)], (6)

где С0{х) = ^кркхк и С,(х) = 5о1£1 производящие функции для степени узла.

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

ОД =*[/>(*)], (7)

где /{(х) находится по формуле (5).

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

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

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

виде

< 5 >= ^(1) = д + дв0(\)р;(1) = д[1 + 1. (8)

Выражение расходится при 1-^(1) =0. Эта точка отмечает значение порога перколяции. Таким образом, вероятность критической заполненности имеет вид

(9)

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

дк=в(кпах-к), (10)

где в - ступенчатая функция Хевисайда.

Для исследования последствий этого удаления, вычислен размер наибольшей компоненты в сети. При генерации перколяционного перехода функция Р0(х) дает распределение размеров кластеров вершин, которых нет в наибольшей компоненте, что означает, что /£{1) равна доле графа, который не занят гигантской компонентой. Таким образом, доля 5, которая занята наибольшей компонентой, вычисляется следующим образом:

(11)

»

где и - решение условия самоорганизации, которое имеет вид

(12)

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

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

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

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

Пусть (р0 =0 допустимый начальный поток.

Доказано, что поток, имеющий максимальную величину, имеет вид г = М. (М- н Л/ соответственно минимальные и максимальные границы величин допустимых потоков), то есть когда один или несколько разрезов графа {№;№'} будут насыщены. Это означает, что <р:(а) = /3(а) нижняя граница пропускной способности дуги а (минимально допустимая величина потока) или для любой дуги ае№—>1¥' и <р:(а) = 0 для любой дуги а е IV' —> п 1 IV — множество вершин.

Пусть каждой дуге а = (у,иО в сети N в наибольшей компоненте 1^,<р) соответствуют две дуги а и д' = (>у,у).

Каждой дуге приписано соотношение:

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

Пусть / - граф приращений (структура не зависит от <р), Л.-функция расстояния, связанная с потоком (р., имеющая величину г.

Алгоритм определения максимального потока: Шаг 1. / = 0; % = О, V дуге.

Шаг 2. Вычислить минимальное расстояние / между Ух и У2 в графе / (метод пометок).

Шаг 3. Если со, то С - простой путь из У, в Уп кратчайшей длины; ас - простой поток по цепи в сети; (РМ=(Р,+ТС; |=/+1;

Переход к шагу 2. Иначе

<,ц\ - максимальным потоком. Шаг 4. Конец.

В диссертации разработан модифицированный алгоритм, внедренный в практику. На Шаге 3 (нахождение С) проверяется, сколько единиц потока можно пропустить по этому пути. Т.е. определяется наибольшее целое I, при котором Щ + 1тс является допустимым потоком. Для определения / воспользуемся тем, что если Л(а)< оо, к щ(а) можно добавить не более Р{а)—(р^а) единиц потока, не нарушая допустимости.

(13)

(14)

Аналогично, если Л,(а')<°о, из Щ{а) можно исключить не более щ(а)-Л(а) единиц потока.

Целое число соответствует минимальному по таким приращениям потока в других С, и на Шаге 3 алгоритма определяется не <рм, а <Рм=Щ+1тс.

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

Если Л(а) > 0 для одной и более дуг, и известен допустимый поток Щ, имеющий вершину 1, то приведенный алгоритм можно использовать для получения допустимых потоков с величинами, возрастающими от г до М или убывающими от / до М .

Нахождение кратчайшего расстояния от У„ до У, в текущем графе приращений (Шаг 2).

Для нахождения начального допустимого потока сформулирована вспомогательная задача на вспомогательной сети N'.

Сеть Ы' = (У\А') получается из сети М = (У,А).

Пусть У0,Ул+1 - источник и сток во вспомогательной сети.

Каждой дуге а = (V, И/) е А в множестве Л' соответствует три дуги

Этим дугам приписывались следующие пропускные способности: А'(а') = А"(а") = А"Ха"')----0,

/}\а") = /}\а")-Л(а).

Для дуг, у которых Л(а) = 0, построение дуг (а") и (а'") является избыточным, так как А = ¡5 - 0. На практике эти дуги опускаются.

В ЛГ добавляется конечная дуга Ь', имеющая следующие характеристики:

I >

где г - целое число, больше, чем величина любого возможного допустимого потока в Л^. |

На Рис.2 приведен пример, вспомогательной сети /У'для заданной сети N.

Вспомогательная сеть полностью определяется сетью (компонентой)N и ее функциями ограничений А и /?.

Таким образом, если, максимизируя поток в сети /V', получен насыщающий поток, то из него можно получить допустимый поток <р в сети N. С другой стороны, если максимальный поток в /V' не является насыщенным, то допустимого потока в сети N не существует.

К, К,

Ко (

ъ

Рис. 2 Построение вспомогательной сети (компоненты) N

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

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

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

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

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

Рассмотрена практическая ситуация выхода из строя маршрутизатора в сети передачи данных. В этом случае вероятностная характеристика узлов описывается формулами (5) и (6).

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

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

(О, к = О

<15)

Ск"е-

к> I.

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

20 30 40 я Размер кластера Рис. 3 Определение размера кластера

На Рис. 3 показано распределение кластеров по размерам, формула (8). Расчет выполнялся на графе с 106 узлов в диапазоне ниже порога перколяции и для конкретной степени распределения с параметрами: А: = 10, г = 2.5 и </ = 0.65. Вероятность Р5 соответствует тому, что случайно выбранный узел принадлежит кластеру узлов 5 и чем больше средний размер кластера, тем меньше вероятность его появления.

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

°ч

-О- г - I ..<

0.0

II

Огепет. уч.к|

Рис. 4 Скачки псрколяцпонных переходов

На Рис. 4 показано изменение перколяционного порога в зависимости от изменения среднего значения степени узла для разных значений Г. Доказано, что когда значение к становится большим, порог протекания становится малым, что свидетельствует о высокой степени пропускной способности сети. При г = 2.5 (примерный показатель для данных Интернет), а к = 100, порог протекания является контролем качества qc=0Л7. Это указывает на возможность удаления более 80% узлов в сети, что не приведет к разрушению. Этот результат согласуется с исследованиями в области Интернет, которые показывают, что такие сети очень устойчивы к случайным удалениям узлов.

На Рис. 5 показана зависимость размера максимальной компоненты 5 от процента удаленных узлов высокой степени. Все вершины со степенью больше ктях незаняты, для г = 1.5, г = 2.0 и г = 2.5. Результаты моделирования для систем с 106 вершин. Наблюдается исчезновение максимальной компоненты при удалении небольшого процента узлов высокой степени - уже при 1% в случае г = 2.5 сеть становится не рабочей.

а 0.6

-О- г м

(1.5 1.0 1.5 2.0 2.5

Процент удаленных у июв Рис. 5. Зависимость размера максималыюй компоненты от процента удаленных узлов

На Рис. 6 показаны те же данные в зависимости от ктах. Можно удалить все вершины со степенью больше А'тах, однако, наибольшая компонента удержится на малых значениях к«к1ХВХ. Например, в случае г = 2.5 ? достаточно &1гах = 10.

Рис. 6 Зависимость размера максимальной компоненты от доли незанятых вершин

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

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

Исследована эффективность разработанного программного обеспечения. Осуществлена проверка его работоспособности на предприятиях. Разработанное программное обеспечение было использовано на практике в ООО "ТриоИнжиниринг".

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

I

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

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

2. Разработаны методы управления потоками данных в сетевых структурах (в графах).

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

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

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

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

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

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

Статьи в журналах, рекомендованных ВАК:

1. Антонова A.A., Головченко E.H., Петров Д.В. Среда моделирования для решения перколяционных задач // Наукоемкие технологии, 2008. № 7. - с. 26-30.

2. Антонова A.A. Математическая модель динамических процессов, протекающих в нефтенасыщенном пласте земли, на основе перколяционных методов // Промышленные АСУ и контроллеры 2012 № 3. - с. 33-36.

3. Антонова A.A. Управление параметрами динамических процессов, протекающих в сложных нестационарных объектах, на основе перколяционных методов // Приборы и системы. Управление, контроль, диагностика, 2012. № 4. - с. 17-19.

Публикации в других изданиях:

4. Антонова A.A. Теоретические исследования работы вихревых турбомашин // Труды IX Всероссийской научно-технической конференции (г. Воронеж, 10-12 сентября 2009 г.). - Воронеж, 2009. - с. 100-104.

5. Антонова A.A. Теоретические исследования работы вихревых турбомашин // Тезисы IX Всероссийской научно-технической конференции и школы молодых ученых, аспирантов и студентов (г. Воронеж, 29 мая 2009 г). - Воронеж, 2009. - с. 49-50.

6. Антонова A.A. Метод управления потоками данных в сетевых структурах // Методы и алгоритмы принятия эффективных решений (МАПР-09): материалы 17-й международной научной конференции. Таганрог: Изд-во ТТИ ЮФУ, 2009. - с. 22-27.

7. Антонова A.A. Математическая модель и алгоритм динамической сложной системы с использованием модифицированных методов // Информационные и телекоммуникационные технологии. Подготовка специалистов для инфокоммуникационной среды: материалы 34-й Всероссийской научно-технической конференции. - Рязань, РВВКУС, 2009.-с. 189-192.

8. Антонова A.A. Изучение свойств динамической перколяционной модели заводнения нефтяного пласта с использованием суперкомпьютерных технологий // Новые информационные технологии (г.Москва, 18-20 апреля 2011 г.) XIV Всероссийская Научно-техническая конференция. - Москва, МГУПИ, 2011. - с. 74-79.

9. Антонова A.A., Авагян A.C., Никонов В.В. Изучение параметров процесса фильтрации методами теории перколяции. // Сборник трудов международной научно-практической конференции «Новейшие научные достижения - 2012». - София: Изд-во Бялгород-БГ ООД, 2012. - с. 13-17 .

10. Антонова A.A. Методы и модели современной теории сетей // Новые информационные технологии (г.Москва, 17 апреля 2012 г.) XV Всероссийская Научно-техническая конференция. — Москва, МГУПИ, 2012, с.71-75.

Авторские свидетельства, патенты, информационные карты и алгоритмы:

11. Антонова A.A., Морозова Т.Ю., Никонов В.В. Свидетельство о государственной регистрации программ для ЭВМ «Программа управления параметрами перколяционной модели». №2012612744, 16 марта 2012 г.

Подписано к печати 10.04.2012 г. Формат 60x90/18. Объем 1,0 п. л. Тираж 100 экз. Заказ № 44.

Московский государственный университет приборостроения и информатики 107996, Москва, ул. Стромынка, 20