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

  • Антонова, Анастасия Анатольевна
  • кандидат технических науккандидат технических наук
  • 2012, Москва
  • Специальность ВАК РФ05.13.01
  • Количество страниц 153
Антонова, Анастасия Анатольевна. Исследование сложных нестационарных телекоммуникационных систем и разработка метода управления потоками данных: дис. кандидат технических наук: 05.13.01 - Системный анализ, управление и обработка информации (по отраслям). Москва. 2012. 153 с.

Оглавление диссертации кандидат технических наук Антонова, Анастасия Анатольевна

Введение.

Глава 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. Выводы.

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

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

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

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

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

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

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

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

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

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

Быстрое развитие новых сетевых услуг, приводящее к изменениям в составе трафика, в сочетании со снижением уровня доходов на бит передаваемой информации тоже ставят перед разработчиками сетей ряд требований. Это такие задачи, как преодоление неустойчивости планирования; экономически более эффективная масштабируемость; улучшение использования полосы пропускания и структуры сети; более эффективное управление рабочими характеристиками сети. Эксплуатация 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 г.

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

Похожие диссертационные работы по специальности «Системный анализ, управление и обработка информации (по отраслям)», 05.13.01 шифр ВАК

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Антонова, Анастасия Анатольевна

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

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

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

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

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

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

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

Заключение

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

Список литературы диссертационного исследования кандидат технических наук Антонова, Анастасия Анатольевна, 2012 год

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.

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