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

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

005055О

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

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

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

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

Москва 2012 г.

2 2 НОЯ 2012

005055512

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Московский государственный университет приборостроения и информатики», на кафедре «Автоматизированные системы управления и информационные технологии» (ИТ-7).

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

Морозова Татьяна Юрьевна ФГБОУ ВПО МГУПИ, заместитель заведующего кафедрой «Автоматизированные системы управления и информационные технологии» (ИТ-7)

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

Кузнецов Олег Петрович ФГБУН ИПУ РАН, заведующий лабораторией

кандидат физико-математических наук, доцент Хакимуллин Евгений Робертович МИЭМ НИУ ВШЭ, профессор кафедры «Высшая математика»

Ведущая организация: ФГБОУ ВПО НИУ Московский энергетический

институт

Защита состоится 17 декабря 2012 г., в 11.00 часов, конференц-зал, 1 этаж, на заседании диссертационного совета Д 002.086.01, при Федеральном государственном бюджетном учреждении науки «Институт системного анализа Российской академии наук» по адресу: 117312, Москва, проспект 60-летия Октября, 9.

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

Автореферат разослан: /2. ноября 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), (P.Tamayo) и многие другие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработанное программное обеспечение было использовано в системах контроля объектов специального назначения. Разработанное

программное обеспечение внедрено в ООО КБ "ЭлектронСистема", что подтверждено актом о внедрении.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поставлена и решена перколяционная задача узлов. Исходными данными для решения поставленной задачи являются: -множество узлов - N = {п,,п2у•••,«;}; -множество связей — М = {т1,т2>...,тя}-, -количество связей узла - к;

-вероятность установления связей между узлами - рк; -момент перколяционного перехода, в зависимости от изменения характеристик телекоммуникационной сети С0; -средний размер кластера - <Х>;

-вероятность содержания компоненты высокой связности - р3\

-потоки данных —<р{а)\

-направление потоков данных — а — (у, н<).

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

(1)

*=0

гдерк — вероятность того, что случайно выбранный узел имеет степень к; (]1с— вероятность того, что узел выбран учитывая, что он имеет степень к ■ Рк1к ~ вероятность того, что узел имеет степень к ^ и он случайно выбран. Доля случайно выбранных узлов - д. Тогда = Ч ■ В диссертационной работе изучался случай равномерного распределения вероятностей, для которого % = Ч для любого к.

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

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

ИМ

где z — средняя степень узла.

Пусть — производящая функция, характеризующая вероятность

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

удовлетворяет условия самоорганизации вида:

/>(*)=l-^D+^W*)]- (3)

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

(4)

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

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

ГО, Аг = 0

Ск-'е-»" к> 1 (5>

где и - количество узлов телекоммуникационной сети; С— коэффициент кластеризации телекоммуникационной сети; г— коэффициент плотности распределения связей в модели телекоммуникационной сети.

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

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

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

II 40 80 А'

Слепень учла

Рис. 2 Зависимость степени узла от вероятности его появления в модифицированном степенном распределении

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

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

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

Р^^-д+чхв^х)], (6)

Р0(х) = (7)

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

узла.

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

Р0(х) = хВД], (8)

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

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

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

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

виде

< 5 >= Р„(1) = q + ?Сг0(1)/>'(1) = # + (9)

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

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

Чк = в(к^,-к), (11)

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

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

S = l-P0(1) = F0(1)-F0(«i) (12)

>

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

и = (13)

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

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

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

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

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

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

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

Доказано, что поток, имеющий максимальную насыщенность, имеет вид (М и М соответственно минимальные и максимальные

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

(р:{а) - /3{а) нижняя граница пропускной способности дуги а (минимально допустимая величина потока) или для любой дуги а е Ж —» Ж' и <Р-(а) — О для любой дуги 5 IV — множество вершин.

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

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

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

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

(14)

(15)

Алгоритм перераспределения потоков:

Шаг 1. / = 0;^0 =0, V дуге.

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

ШагЗ. Если о, то С - простой путь из Ух в У„ минимальной насыщенности;

ис - простой поток по цепи в сети;

<Рм=<Р!+*с;

г=/+1;

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

(р1 — сильно насыщенный поток данных. Шаг 4. Конец.

В диссертации разработан модифицированный алгоритм, внедренный в практику. На Шаге 3 (нахождение С) проверяется, сколько единиц потока можно пропустить по этому пути. Т.е. определяется наибольшее целое ?, при котором (р, + ¡тс является допустимым потоком. Для определения ? воспользуемся тем, что если А(а)< со, к <р,(а) можно добавить не более единиц потока, не нарушая допустимости.

Аналогично, если А/(а')<<х>, из ^¡(о) можно исключить не более р,(а)-Л(а) единиц потока.

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

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

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

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

Для нахождения начального допустимого потока сформулирована вспомогательная задача на вспомогательной сети N'. Сеть Ж' = (У',А') получается из сети М = (У,А).

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

Каждой дуге а = е А в множестве Л'соответствует три дуги

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

р\а")=р\а")-т-

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

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

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

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

Вспомогательная сеть полностью определяется сетью (компонентой)ТУ и ее функциями ограничений Л и р.

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

аъ"

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

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

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

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

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

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

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

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

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

Размер кластера Рис. 4 Определение размера кластера

На Рис. 4 показано распределение кластеров по размерам, формула (9). Расчет выполнялся на графе с 10б уЗЛОв в диапазоне ниже порога перколяции и для конкретной степени распределения с параметрами: ¿ = 10, г = 2.5 и д = 0.65. Вероятность Р, соответствует тому, что случайно выбранный узел принадлежит кластеру узлов Б и чем больше средний размер кластера, тем меньше вероятность его появления.

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

Степень узла Рис. 5 Скачки перколяционных переходов

-О I- - 1.5 -О- г 2 .1) -А- г - 2.5

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

пропускной способности сети. При г = 2.5 (примерный показатель для данных Интернет), а ¿ = 100, порог протекания является контролем качества (¡с= 0.17. Это указывает на возможность удаления более 80% узлов в сети, что не приведет к разрушению. Этот результат согласуется с исследованиями в области Интернет, которые показывают, что такие сети очень устойчивы к случайным удалениям узлов.

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

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

На Рис. 7 показаны те же данные в зависимости от ктж . Можно удалить все вершины со степенью больше лтах, однако, наибольшая компонента удержится на малых значениях к « кт,,:,. Например, в случае г = 2.5) достаточно ктш = 10.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 сентября 2008 г.). - Воронеж, 2008. - с. 100-104.

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

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

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

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

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

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

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

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

Подписано в печать 09.11.2012 г.

Усл.п.л. - 1.0 Заказ №11405 Тираж: 100 экз.

Копицентр «ЧЕРТЕЖ.ру» ИНН 7701723201 107023, Москва, ул. Б.Семеновская 11, стр.12 (495) 542-7389 \v\vw. chertez.ru

Введение.

Глава 1. АНАЛИЗ СОВРЕМЕННЫХ МОДЕЛЕЙ ИЗУЧЕНИЯ СЛОЖНЫХ ДИНАМИЧЕСКИХ СИСТЕМ НА ОСНОВЕ ТЕОРИИ СЛУЧАЙНЫХ ГРАФОВ И ПЕРКОЛЯЦИИ.

1.1. Сложные динамические сети как приложение теории сложных систем

1.2. Модели сложных сетей на основе теории случайных графов.

1.2.1. Модель Эрдоша - Реньи.

1.2.2. Модель Барабаши - Альберт.

1.2.3. Модели «малого мира». Модель Уотса-Строгатса.

1.3. Перколяция на случайных графах.

1.4. Модели управления потоками данных в ИВС.

1.4.1. Обмен данными в информационно—вычислительных сетях.

1.4.2.Алгоритмы маршрутизации в сети Интернет.

1.4.3. Моделирование работы ИВС.

1.5. Постановка задачи исследования.

1.6. Выводы.

Глава 2. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ ДИНАМИЧЕСКОЙ СЛОЖНОЙ СИСТЕМЫ С ИСПОЛЬЗОВАНИЕМ МОДИФИЦИРОВАННЫХ МЕТОДОВ НА ОСНОВЕ ТЕОРИИ ПЕРКОЛЯЦИИ И ТЕОРИИ СЛУЧАЙНЫХ ГРАФОВ.

2.1. Методы систематического обхода узлов и связей графа.

2.2. Эволюция графов.

2.3. Распределение степеней узлов в случайном графе.

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

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

2.4.2. Принципы организации кластеров ИВС.

2.4.2.1. Алгоритм определения размера кластера.

2.4.2.2. Алгоритм выделения сильносвязной компоненты.

2.4.3. Модель реакции сети на разрушение связей.

2.5. Выводы.

Глава 3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ УПРАВЛЕНИЯ ПОТОКАМИ ДАННЫХ В СЛОЖНЫХ СИСТЕМАХ.

3.1. Алгоритмы управления потоками данных в сложных сетях.

3.2. Теорема Форда - Фалкерсона.

3.3. Построение минимального покрывающего дерева.

3.3.1. Алгоритм Крускалла.

3.3.2. Алгоритм Прима.

3.4. Поиск кратчайших путей из одного узла.

3.4.1. Алгоритм Дейкстры.

3.4.2. Алгоритм Беллмана-Форда.

3.5. Кратчайшие пути для всех пар узлов взвешенного ориентированного графа.

3.5.1. Алгоритм Флойда.

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

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

3.7. Выводы.

Глава 4. РЕАЛИЗАЦИЯ АЛГОРИТМОВ И РЕЗУЛЬТАТЫ ЧИСЛЕННЫХ ИССЛЕДОВАНИЙ.

4.1. Определение размера кластера.

4.2. Изучение порога перколяции сети.

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

4.4. Выбор средства реализации визуализации.

4.5. Структура программного обеспечения.

4.6. Выводы.

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

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

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

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

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

-угроза разрушения сети, возникающая вследствие случайного выхода из строя отдельных узлов;

- необходимость перераспределения информационных потоков.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

1. Albert R, X. Jeong, и A.-J1. Barabasi, Nature (London) 406, 378 (2000).

2. Albert R., Jeong H., Barabasi A. Attack and error tolerance of complex networks //Nature. 2000. - Vol. 406. - pp. 378-382.

3. Baeza-Yates R., Ribeiro-Neto B. Modern Information Retrieval. ACM Press Series/Addison Wesley, New York, 1999. - 513 p.

4. Barabasi, Albert-Laszlo and Reka, Albert. "Emergence of scaling in random networks". Science, 286:509-512, October 15, 1999.

5. Benczur, A. A., Csalogany, K., Sarlos, T. and Uher, M. Spamrank fully automatic link spam detection. In First International Workshop on Adversarial Information Retrieval on the Web, 2005.

6. Berry M.W. Survey of Text Mining. Clustering, Classification, and Retrieval. Springer-Verlag, 2004. - 244 p.

7. Bjorneborn, L., Ingwersen, P. Toward a basic framework for webometrics. Journal of the American Society for Information Science and Technology, 55(14): 1216-1227.-2004.

8. Bollobas B. Random Graphs. — Cambridge Univ. Press, 2001. — 520 c.

9. Bradford, S.C. "Sources of Information on Specific Subjects". Engineering: An Illustrated Weekly Journal (London), 137, 1934 (26 January), pp. 8586.

10. Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. WWW7,- 1998.

11. Broadbent S.R., Hammersley J.M. Percolation processes // I. Crystals and mazes, Proc Cambridge Philos. Soc. pp. 629-641. - 1957.

12. Broder A. Identifying and Filtering Near-Duplicate Documents, COM'OO // Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching. 2000. - pp. 1-10.

13. Cohen R, Havlin S, "Scale-Free Networks are Ultrasmall" Phys. Rev. Lett. 90, 058701 (2003).

14. Cohen R., Erez K., ben-Avraham D., Havlin S. Resilience of the Internet to. Random Breakdown//Phys.Rev.Lett. 85, 4626 (2000).

15. Diestel R. Graph Theory. Electronic Edition, NY: Springer, 2005.

16. Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective. — Springer-Verlag, 1982.— ISBN 0-387-90652-5. (См. документы EWD 570 и EWD 578, воспроизведенные в этой книге.)

17. Donetti L., Hurtado P.I., Munoz M.A. Entangled Networks, Synchronization, and Optimal Network Topology // Physical Review Letters. Vol. 95, - № 18, 2005.

18. Dorogovtsev $.N., Mendes J.F.F. Evolution of Networks: from biological networks to the Internet and WWW, Oxford University Press, 2003.

19. Dorogovtsev, S.N. and Mendes, J.F.F. and Samukhin, A.N., "Structure of Growing Networks: Exact Solution of the Barabasi-Albert's Model", Phys. Rev. Lett. 85, 4633 (2000).

20. Erdos P., Renyi A. On the evolution of random graphs // Bull. Inst. Int. Statist. — Tokyo, 1961. — V. 38. — P. 343-347.

21. Erdos P., Renyi A. On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5. pp. 17-61. -1960.

22. Erdos, P., Renyi A. On Random Graphs. I. // Publicationes Mathematicae 6, -pp. 290-297.-1959.