Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Антонова Анастасия Анатольевна
ИССЛЕДОВАНИЕ СЛОЖНЫХ НЕСТАЦИОНАРНЫХ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ И РАЗРАБОТКА МЕТОДА УПРАВЛЕНИЯ ПОТОКАМИ ДАННЫХ
Специальность 05.13.01
Системный анализ, управление и обработка информации (промышленность)
Автореферат диссертации на соискание ученой степени кандидата технических наук
Москва 2012 г.
Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Московский государственный университет приборостроения и информатики, на кафедре Автоматизированные системы управления и информационные технологии (ИТ-7).
Научный руководитель: доктор технических наук, профессор
Морозова Татьяна Юрьевна
ФГБОУ ВПО МГУПИ, заместитель заведующего кафедрой Автоматизированные системы управления и информационные технологии (ИТ-7)
Официальные оппоненты: доктор технических наук, профессор
Кузнецов Олег Петрович
ФГБУН ИПУ РАН, заведующий лабораторией
кандидат физико-математических наук, доцент
Хакимуллин Евгений Робертович
МИЭМ НИУ ВШЭ, профессор кафедры Высшая математика
Ведущая организация: ФГБОУ ВПО НИУ Московский энергетический институт
Защита состоится 17 декабря 2012 г., в 11.00 часов, конференц-зал,1 этаж, на заседании диссертационного совета Д 002.086.01, при Федеральном государственном бюджетном учреждении науки Институт системного анализа Российской академии наук по адресу: 117312, Москва, проспект 60-летия Октября, 9.
С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Институт системного анализа Российской академии наук.
Автореферат разослан: ___ ноября 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(б) - пример разработанного в диссертационной работе модифицированного степенного распределения, которое больше соответствует реальным сетям, т.к. описывает узлы с большим количеством связей, а не усредняет их.
Существующие методы решения задачи протекания (перераспределения) потоков данных в сетях применимы к стационарным графам, имеющим фиксированную топологию. Однако реальные телекоммуникационные сети имеют нестационарную топологию, случайно меняющуюся во времени. Поэтому для анализа таких сетей в работе привлекаются методы теории случайных графов и теории перколяции. Перколяция в задачах физики - это процесс возникновения протекания жидкости через пористые материалы. Перколяция в случайном графе - это динамический процесс образования пути между заданными точками.
В теории перколяции рассматриваются две задачи: прямая и обратная. Прямая задача - это задача открытия связей, а обратная задача - это задача закрытия (разрушения) связей. В диссертационной работе исследуется порог перколяции и перколяционный переход, который образуется в результате разрушения связей (обратная задача перколяции).
Определение 1. Кластер - это сильно связная компонента в случайном графе.
Методами теории перколяции проведено исследование характеристик сложной нестационарной телекоммуникационной сети, таких как пропускная способность и средний размер кластеров.
В диссертационной работе введены следующие определения.
Определениеа2. Эффект возникновения гигантской компоненты (перколяционного кластера) - эффект, возникающий в случайной среде при неограниченном росте числа связей. Эффект заключается в том, что почти все узлы объединяются в единственную компоненту.
Определение 3. Перколяционный переход - эффект перехода состояния модели из одной фазы в другую: в одной фазе существуют конечные кластеры, а во второй существует один (перколяционный) кластер.
Определение 4. Порог перколяции - числовая величина, описывающая критическое состояние графа, при котором происходит перколяционный переход, то есть количество удаленных ребер (перколяционная задача ребер) или узлов (перколяционная задача узлов) которые надо удалить, что бы граф потерял свою связность.
При выборе подхода к решению поставленных в диссертации задач основным фактором явилась необходимость обеспечения лучшей пропускной способности существующей сети путем изменения взаимодействия ее элементов.
В конце первой главы поставлена задача разработки математического и алгоритмического обеспечения управления информационными потоками в сложных нестационарных телекоммуникационных сетях на основе теории случайных графов и перколяции.
Во второй главе диссертации рассмотрена перколяция на случайных графах. Для различных видов телекоммуникационных сетей рассмотрено решение перколяционной задачи узлов. В реальных сетях узлы, имеющие высокую степень, могут отражать серверную сторону телекоммуникационной сети, поэтому при выходе из строя, их влияние на состояние системы в экстремальных условиях велико. Выявление таких областей графа необходимо для постановки задачи перераспределения связей в области узла с большой степенью.
Результаты решения применимы к управлению потоками данных, протекающих в сложных сетях.
Степень узла зависит от того, какой сетевой объект этот узел представляет. Вероятностное распределение степени узла может быть равномерным или может зависеть от числа подключений к другим узлам. В этих условиях изучаются свойства перколяционных кластеров на случайном графе, такие как связность и порог перколяции.
Для решения задачи объединения региональных телекоммуникационных сетей разработана модифицированная математическая модель основанная на теории случайных графов и перколяции. Изучение свойств модели позволяет оценить риски, связанные с процессом объединения региональных телекоммуникационных сетей.
Поставлена и решена перколяционная задача узлов. Исходными данными для решения поставленной задачи являются:
-множество узлов -
-множество связей -
-количество связей узла - k;
-вероятность установления связей между узлами -
-момент перколяционного перехода, в зависимости от изменения характеристик телекоммуникационной сети
-средний размер кластера - <S>;
-вероятность содержания компоненты высокой связности -
-потоки данных Ц
-направление потоков данных -
Пусть производящая функция вероятности распределения степеней узлов имеет вид
12
где - вероятность того, что случайно выбранный узел имеет степень ; - вероятность того, что узел выбран учитывая, что он имеет степень ;
- вероятность того, что узел имеет степень , и он случайно выбран. Доля случайно выбранных узлов - q. Тогда . В диссертационной работе изучался случай равномерного распределения вероятностей, для которого для любого .
При случайно выбранной связи достигнутый узел имеет степень распределения . Определены условия, при которых случайно выбранная связь приведет к узлу высокой степени. Уравнение (1) для такого узла имеет вид
34
где - средняя степень узла.
Пусть - производящая функция, характеризующая вероятность того, что один конец случайно выбранной связи в сети приводит к перколяционному переходу. Возникший кластер может содержать крайний узел в конце связи с вероятностью или связь может привести к заполненному узлу со степенью с вероятностью . Это означает, что удовлетворяет условия самоорганизации вида:
56
Распределение вероятности размера кластера для случайно выбранного узла выглядит аналогично:
78
Совокупность уравнений (1) - (4) позволяет определить распределение размера кластера для задачи узлов перколяции, средний размер кластера, значение порога перколяции и размеры компоненты.
Для решения поставленной в диссертационной работе задачи создания модели сложной нестационарной телекоммуникационной сети было разработано модифицированное степенное распределение:
910
где - количество узлов телекоммуникационной сети;
- коэффициент кластеризации телекоммуникационной сети;
- коэффициент плотности распределения связей в модели телекоммуникационной сети.
Для этого было изучено и подробно исследовано пуассоновское распределение и классическое степенное распределение количества инцидентных дуг к вершине.
Обоснован выбор главной характеристики модели - вероятности того, что узел имеет заданную степень.
Системы с распределением (5) называются безмасштабными. Именно модифицированное степенное распределение часто наблюдается в реальной структуре существующих сложных сетей. Приведенный график модифицированного степенного распределения (Рис.2) подтверждает возникновение узлов с очень высокой степенью, что практически не наблюдается в моделях телекоммуникационных систем с пуассоновским распределением.
Рис. 2 Зависимость степени узла от вероятности его появления в модифицированном степенном распределении
Было выявлено, что узлы, имеющие высокую степень могут отражать серверную сторону телекоммуникационной сети, поэтому при выходе из строя, их влияние на состояние системы в экстремальных условиях велико.
Добавляя и регулируя переменную в модифицированном степенном распределении (5) количество узлов высокой связности меняется.
В частном случае равномерного распределения вероятности пометки узлов, для всех , уравнения (3) и (4) упрощаются и модифицированная математическая модель приобретает вид:
1112
1314
где и производящие функции для степени узла.
Для перколяционной связи с равномерным распределением получена вероятность:
1516
где находится по формуле (6).
В диссертации использовалась модифицированная производящая функция для нахождения точного аналитического решения задачи узлов перколяции на случайных графах с любой вероятностью распределения степеней узла. Вероятность заполнения является произвольной функцией степени узла.
Результаты показывают, что возможно удаление узлов с определенной степенью для оценки надежности работы сети.
Определен средний размер кластера в сети до порога перколяции в виде
1718
Выражение расходится при . Эта точка отмечает значение порога перколяции. Таким образом, вероятность критической заполненности имеет вид
1920
В главе решался вопрос о надежности сети при удалении узлов с высокой степенью. На языке перколяционной модели, это эквивалентно условию:
2122
где - ступенчатая функция Хевисайда.
Для исследования последствий этого удаления, вычислен размер наибольшей компоненты в сети. При генерации перколяционного перехода функция дает распределение размеров кластеров вершин, которых нет в наибольшей компоненте, что означает, что равна доле графа, который не занят гигантской компонентой. Таким образом, доля , которая занята наибольшей компонентой, вычисляется следующим образом:
, 2324
где - решение условия самоорганизации, которое имеет вид
2526
В случаях, когда уравнение (13) не имеет точного решения, его можно оценить с помощью численной итерации, начиная с начального значения.
Таким образом, во второй главе решена перколяционная задача узлов на случайном графе, в результате решения которой получены зависимости: размера кластера от процента удаленных узлов, размера кластера от максимальной степени узла. Изучена реакция сети на разрушение связей между узлами (например, волоконно-оптические линии связи, кабели электропередач, и т.д.). Также решена комбинированная перколяционная задача узлов и связей, в результате решения которой сделан вывод о необходимости защиты узла с высокой степенью в сложных системах.
Разработан алгоритм выделения и защиты многосвязного узла в сложных системах.
В третьей главе разрабатывается алгоритм управления информационными потоками на основе нахождения узла с высокой степенью.
При объединении региональных телекоммуникационных сетей возникает задача перераспределения информационных потоков. С другой стороны исследования модели телекоммуникационной сети показало, что она нуждается в разгрузке узлов с высокой степенью. Поэтому был предложен алгоритм получения допустимых потоков между фиксированной парой вершин в сети, основанный на методе пометок.
В отличие от существующих алгоритмов работы, с потоками основанных на графах, представленный алгоритм работает не с фиксированными величинами потоков данных, а с максимальной и минимальной их насыщенностью, что позволяет использовать данный алгоритм в условиях неопределенных потоков в случайных графах.
Пусть допустимый начальный поток.
Доказано, что поток, имеющий максимальную насыщенность, имеет вид ( и соответственно минимальные и максимальные границы насыщенности допустимых потоков), то есть когда один или несколько разрезов графа будут насыщены. Это означает, что нижняя граница пропускной способности дуги а (минимально допустимая величина потока) или для любой дуги и для любой дуги , - множество вершин.
Пусть каждой дуге в сети в наибольшей компоненте соответствуют две дуги и .
Каждой дуге приписано соотношение:
2728
2930
Таким образом, связи, которые удалялись из графа, теперь восстанавливаются, но имеют бесконечную длину, и поток будет максимальный, если между узлами и нет путей нулевой длины.
Пусть - граф приращений (структура не зависит от ), - функция расстояния, связанная с потоком , имеющая величину .
Алгоритм перераспределения потоков:
Шага1. ; = 0, дуге.
Шага2. Вычислить минимальное расстояние между и в графе (метод пометок).
Шага3. Если , то - простой путь из в минимальной насыщенности;
- простой поток по цепи в сети;
;
;
Переход к шагу 2.
Иначе
- сильно насыщенный поток данных.
Шаг 4. Конец.
В диссертации разработан модифицированный алгоритм, внедренный в практику. На Шаге 3 (нахождение ) проверяется, сколько единиц потока можно пропустить по этому пути. Т.е. определяется наибольшее целое , при котором является допустимым потоком. Для определения воспользуемся тем, что если , к можно добавить не более единиц потока, не нарушая допустимости.
Аналогично, если , из можно исключить не более единиц потока.
Целое число соответствует минимальному по таким приращениям потока в других , и на Шагеа3 алгоритма определяется не , а .
В главе разработан алгоритм для перераспределения потоков в сетях с ограниченными пропускными способностями дуг.
Если для одной и более дуг, и известен допустимый поток , имеющий вершину , то приведенный алгоритм можно использовать для получения допустимых потоков с величинами, возрастающими от до или убывающими от до.
Нахождение мало насыщенного расстояния от до в текущем графе приращений (Шаг 2).
Для нахождения начального допустимого потока сформулирована вспомогательная задача на вспомогательной сети .
Сеть получается из сети .
Пусть - источник и сток во вспомогательной сети.
Каждой дуге в множестве соответствует три дуги
.
Этим дугам приписывались следующие пропускные способности:
Для дуг, у которых , построение дуг и является избыточным, так как. На практике эти дуги опускаются.
В добавляется конечная дуга , имеющая следующие характеристики:
,
где - целое число, больше, чем величина любого возможного допустимого потока в .
На Рис.а3 приведен пример, вспомогательной сети для заданной сети .
Вспомогательная сеть полностью определяется сетью (компонентой) и ее функциями ограничений и .
Таким образом, если, максимизируя поток в сети , получен насыщающий поток, то из него можно получить допустимый поток в сети . С другой стороны, если максимальный поток в не является насыщенным, то допустимого потока в сети не существует.
Рис. 3 Построение вспомогательной сети (компоненты)
В третьей главе находится максимальный поток в сети, принимая в качестве начального потока, поток тождественно равный нулю.
Для нахождения насыщенного потока в сети необходимо принять в качестве начального потока, поток тождественно равный нулю, и добавлять к нему последовательность простых потоков по цепям от источника к стоку. Текущее значение потока максимально насыщенно, когда в графе приращений не оказывается путей конечной длины. Каждый промежуточный поток, найденный в процессе выполнения процедуры, является допустимым, т.е. получены потоки, реализующие все допустимые значения. Приведена процедура ускорения поиска.
Для сетей с ограниченными пропускными способностями для нескольких или всех дуг необходимо сначала построить соответствующую вспомогательную сеть, а затем максимизировать поток с помощью алгоритма.
Таким образом, для любой сети с ограниченными пропускными способностями предложен практический метод получения любых допустимых потоков между фиксированной парой вершин в сети.
В четвертой главе рассмотрено применение результатов к изучению сети в разных случаях.
Рассмотрена практическая ситуация выхода из строя маршрутизатора в сети передачи данных. В этом случае вероятностная характеристика узлов описывается формулами (6) и (7).
Доказано, что в явной форме решения для уравненияа(6) не существует, но можно определять условия для любого конечного путем применения метода итераций к уравнению (6), начиная с начального значения . Распределение вероятностей размеров кластеров может быть вычислено точно, используя уравнение (4), при .
Чтобы проверить этот подход, было выполнено моделирование перколяционной задачи узлов на случайных графах. Использовался модифицированный закон степенного распределения из формулы (5).
Данное распределение выбрано по двум причинам. Во-первых, работа интернет-ресурса в формуле (16) подчинена степенному закону распределения. Во-вторых, распределение имеет технические преимущества по сравнению с чисто степенным видом, поскольку экспоненциальная составляющая упорядочивает расчеты таким образом, что производящие функции и их производные являются конечными. С другой стороны, для чистой степенной формы расчеты расходятся, указывая, что реальные сети не могут принимать чисто степенной вид и должны иметь некоторые поправки, которые зависят от размера системы.
Рис. 4 Определение размера кластера
На Рис.а4 показано распределение кластеров по размерам, формулаа(9). Расчет выполнялся на графе с узлов в диапазоне ниже порога перколяции и для конкретной степени распределения с параметрами: , и Вероятность соответствует тому, что случайно выбранный узел принадлежит кластеру узлов и чем больше средний размер кластера, тем меньше вероятность его появления.
Для изучения порога перколяции, то есть момента формирования перколяционного кластера (гигантской компоненты), необходимо изменить исходные параметры.
Рис. 5 Скачки перколяционных переходов
На Рис.а5 показано изменение перколяционного порога в зависимости от изменения среднего значения степени узла для разных значений Доказано, что когда значение становится большим, порог протекания становится малым, что свидетельствует о высокой степени пропускной способности сети. При (примерный показатель для данных Интернет), а , порог протекания является контролем качества . Это указывает на возможность удаления более 80% узлов в сети, что не приведет к разрушению. Этот результат согласуется с исследованиями в области Интернет, которые показывают, что такие сети очень устойчивы к случайным удалениям узлов.
На Рис.а6 показана зависимость размера максимальной компоненты от процента удаленных узлов высокой степени. Все вершины со степенью больше не заняты, для , и . Результаты моделирования для систем с вершин. Наблюдается исчезновение максимальной компоненты при удалении небольшого процента узлов высокой степени - уже при 1% в случае сеть становится не рабочей.
Рис. 6 Зависимость размера максимальной компоненты
от процента удаленных узлов
На Рис.а7 показаны те же данные в зависимости от . Можно удалить все вершины со степенью больше , однако, наибольшая компонента удержится на малых значениях . Например, в случае , достаточно .
Рис. 7 Зависимость размера максимальной компоненты
от доли не занятых вершин
По полученным в предыдущих главах результатам разработано программное обеспечение, которое реализует поставленную задачу.
Данное программное обеспечение работает под управлением операционных систем семейства Windows. Проектирование и реализация программного обеспечения осуществлялось на базе объектно-ориентированных технологий.
Исследована эффективность разработанного программного обеспечения. Осуществлена проверка его работоспособности на предприятиях. Разработанное программное обеспечение было использовано на практике в ООО КБ "ЭлектронСистема".
В заключении изложены основные результаты и выводы по диссертационной работе.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1.аПроведен анализ современных моделей сложных нестационарных сетей, основывающихся на теории случайных графов. А так же проведен анализ методов теории перколяции.
2.Разработана математическая модель динамической сложной системы с использованием модифицированных методов на основе теории перколяции и теории случайных графов
3.аРассмотрена потенциальная возможность сети к разрушению связей между узлами. Разработан алгоритм выделения и защиты многосвязного узла в сложных системах.
4.аРазработан алгоритм перераспределения информационных потоков в сложных нестационарных сетях.
5.аРешен ряд практических задач с использованием предлагаемого обеспечения для управления потоками данных в сложной нестационарной телекоммуникационной сети.
6.аРазработано программное обеспечение, позволяющее проводить аналитическое моделирование работы информационно-вычислительных сетей и управлять протекающими в сети процессами, а так же проводить процедуру повышения эффективности функционирования имеющейся сети для улучшения ее характеристик.
СПИСОК ОСНОВНЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ
Статьи в журналах, рекомендованных ВАК:
- Антонов.А., ГоловченкоаЕ.Н., ПетроваД.В. Среда моделирования для решения перколяционных задач // Наукоемкие технологии, 2008. № 7. - с. 26Ц30.
- Антонов.А. Математическая модель динамических процессов, протекающих в нефтенасыщенном пласте земли, на основе перколяционных методов // Промышленные АСУ и контроллеры, 2012. №а3. - с. 33Ц36.
- Антонов.А. Управление параметрами динамических процессов, протекающих в сложных нестационарных объектах, на основе перколяционных методов // Приборы и системы. Управление, контроль, диагностика, 2012. № 4. - с. 17Ц19.
Публикации в других изданиях:
- Антонова А.А. Теоретические исследования работы вихревых турбомашин // Труды IX Всероссийской научно-технической конференции (г. Воронеж, 10 - 12 сентября 2008 г.). - Воронеж, 2008. - с. 100Ц104.
- Антонова А.А. Теоретические исследования работы вихревых турбомашин // Тезисы IXаВсероссийской научно-технической конференции и школы молодых ученых, аспирантов и студентов (г.аВоронеж, 29 мая 2008 г). - Воронеж, 2008. - с. 49Ц50.
- Антонова А.А. Метод управления потоками данных в сетевых структурах // Методы и алгоритмы принятия эффективных решений (МАПР-09): материалы 17-й международной научной конференции. Таганрог: Изд-во ТТИ ЮФУ, 2009. - с. 22Ц27.
- Антонов.А. Математическая модель и алгоритм динамической сложной системы с использованием модифицированных методов // Информационные и телекоммуникационные технологии. Подготовка специалистов для инфокоммуникационной среды: материалы 34-й Всероссийской научно-технической конференции. - Рязань, РВВКУС, 2009. - с. 189Ц192.
- Антонов.А. Изучение свойств динамической перколяционной модели заводнения нефтяного пласта с использованием суперкомпьютерных технологий // Новые информационные технологии (г.аМосква, 18-20 апреля 2011аг.) XIV Всероссийская Научно-техническая конференция. - Москва, МГУПИ, 2011. - с. 74Ц79.
- Антонов.А., Авагян А.С., Никонов В.В. Изучение параметров процесса фильтрации методами теории перколяции. // Сборник трудов международной научно-практической конференции Новейшие научные достижения - 2012. - София: Изд-во Бялгород-БГ ООД, 2012. - с. 13Ц17 .
- Антонова А.А. Методы и модели современной теории сетей // Новые информационные технологии (г.аМосква, 17аапреля 2012аг.) XVаВсероссийская Научно-техническая конференция. - Москва, МГУПИ, 2012, с.71Ц75.
Авторские свидетельства, патенты, информационные карты и алгоритмы:
- Антонова А.А., Морозова Т.Ю., Никонов В.В. Свидетельство о государственной регистрации программ для ЭВМ Программа управления параметрами перколяционной модели. №а2012612744, 16 марта 2012 г.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям