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

• Гадяцкая, Ольга Александровна
• кандидат физико-математических наук
• 2008

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

Введение

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

1.1. Моделирование сетей связи и исследование их нг.дежностей

1.1.1. Показатели надежности и общие подходы к их расчёту

1.1.2. Оптимизация структур сетей по критериям надёжности

1.1.3. Критерий максимума вероятности связности.

1.1.4. Критерий вероятности передачи потока заданной величины

1.1.5. Критерий EDP.

1.2. Основные определения и формулы.

1.3. Способы вычисления EDP-функционала.

1.3.1. Методы полного перебора

1.3.2. Метод ветвления.

1.4. Полиномы надежности.

1.5. Полиномы надежности для вероятности связности.

1.6. Формулы для расчета EDP.

1.6.1. EDP-полином двухвершинного графа.

1.6.2. EDP-полином трехвершинного графа.

1.6.3. Формула для моста.

1.6.4. Удаление висячей вершины.

1.6.5. Ветвление по цепи длины 2.

1.6.6. Формула для EDP-полинома графа в случае наличия в нем точки сочленения.

1.6.7. Формула для EDP-полинома графа, представляющего собой два несвязных блока.

1.7. Предварительные утверждения.

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

1.9. Формулы полиномов надежности для распространенных сетевых топологий

1.9.1. Полином надежности для цепи

1.9.2. EDP-полином для звезды.

1.9.3. EDP-полином для цикла.

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

1.10.1. Полином надежности для звезды в случае наличия ограничения на диаметр.

1.10.2. Полином надежности для цепи в случае наличия ограничения на диаметр.

1.10.3. Полином надежности для цикла в случае наличия ограничения на диаметр.

1.11. Результаты и выводы к Главе

Глава 2. ТЕОРЕТИЧЕСКАЯ ОПТИМИЗАЦИЯ СЕТЕВЫХ

ТОПОЛОГИЙ ПО КРИТЕРИЮ EDP

2.1. Вспомогательные утверждения.

2.2. Добавление ребра в распространенные сетевые топологии

2.2.1. Добавление ребра в звезду.

2.2.2. Добавление ребра к цепи.

2.2.3. Добавление ребра в цикл.

2.2.4. Сравнение оптимального добавления ребра но критериям EDP и вероятности связности.

2.3. Оптимальное расположение особых вершин отличного веса

2.3.1. Цепь с особой вершиной.

2.3.2. Звезда с одной особой вершиной.

2.3.3. Особая вершина в топологии цикл с присоединенной вершиной

2.3.4. Особая вершина в графе-восьмерке.

2.4. Оптимальное по критерию EDP присоединение структур

2.4.1. Присоединение звезды

2.4.2. Присоединение цепи.

2.4.3. Присоединение графа-восьмерки

2.4.4. Сравнение результатов оптимального присоединения графов по критерию EDP с результатами оптимального присоединения этих графов по критерию максимума вероятности связности.

2.4.5. Оптимальное соединение циклов.

2.5. Результаты и выводы к Главе 2.

Глава 3. ПРОГРАММНЫЕ АЛГОРИТМЫ И ИХ РЕАЛИЗАЦИЯ

3.1. Реализация подсчета коэффициентов обычного полинома надежности

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

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

3.3. Числениые эксперименты.

3.3.1. Ускорение расчетов в случае обычного подсчета коэффициентов полиномов надежности.

3.3.2. Тестирование теоретических результатов из главы

3.3.3. Оптимизация сетевых топологий по критерию EDP с помощью точного расчета полиномов надежности.

3.4. Результаты и выводы к Главе 3.

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

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

Исследованиями различных критериев надежности инфокоммуникационных сетей занимались и занимаются многие ученые. Из отечественных исследователей следует, прежде всего, отметить Артамонова Г.Т., Вишневского В.М., Дудника Б.Я., Егунова М.М., Епихина В.В., Кауля C.B., Кель-манса А.К., Литвака В.И., Ломоносова М.В., Майнагатлева С.М., Нече-пуренко М.И., Мухопада Ю.Ф, Полесского В.П., Попкова В.К, Родионова A.C., Скоробогатова В.А., Толчана А.Я, Харкевича А.Д. Среди зарубежных исследователей это Ball M.О., Colbourn C.J., Koide Т., Moore E.F., Page L.B., Palmer C.R., Perry J.E., Provan J.С., Satyanarayana A., Shannon C.E., Shooman A.M., Van Slyke R., Wood R.K.

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

Если элементы сети выходят из строя с некоторой вероятностью, то становится возможным оценивать математическое ожидание числа несвязных пар узлов сети (EDP, от англ. Expectation of the number of disconnected pairs of nodes). Далее критерий минимума математического ожидания числа несвязных пар вершин будем называть критерием минимума EDP или просто EDP-критерием. Задача точного расчета математического ожидания числа несвязных пар узлов сети довольно нова. В то время, как этот критерий надежности сетей давно известен [12, 32, 36, 50], ранее этот показатель вычислялся только приближенными методами, в основном методом

Монте-Карло [12], в связи с NP-трудностью задачи [52]. Использование приближенных методов обуславливалось, прежде всего, тем, что вычислительные мощности имеющейся техники не позволяли вычислять точные значения функционалов надежности для реальных сетей связи. В настоящее время произошло значительное увеличение возможностей вычислительной техники и поэтому стало возможным использовать точные методы вычисления для сетей реальных размерностей (десятки узлов). Точные методы расчета этого функционала надежности необходимы также для проверки качества приближенных методов расчета. Одни из первых работ о точном вычислении математического ожидания числа несвязных пар узлов - это работы Родионова A.C. и Родионовой O.K. [52, 54, 55]. Программное обеспечение по приближённой оптимизации методом Монте-Карло структур сетей связи с использованием EDP-критерия разработано М.М. Егуновым и используется в ГОУ ВПО СибГУТИ [12].

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Гадяцкая, Ольга Александровна

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

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

2. Теоремы об оптимальности по критерию минимума математического ожидания числа несвязных пар вершин случайного графа (СГ) для определённых топологий СГ и способов их соединения.

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

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

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

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Гадяцкая, Ольга Александровна, 2008 год

1. Ахо A.B., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы // М.: Мир, 2001.

2. Боровков A.A. Теория вероятностей. 2-е изд., перераб. и доп. // М.: Наука., 1986. 431 с.

3. Гадяцкая O.A. Применение EDP-полиномов при выборе оптимальных структур. //Вестник НГУ, Серия: Математика, механика, информатика. Т.8. Выпуск 1, Новосибирск, 2008г. С.3-14.

4. Гадяцкая O.A. Оптимальное соединение случайных графов по критерию минимума математического ожидания числа несвязных пар вершин. // Материалы X Международной конференции "Проблемы функционирования информационных сетей", Новосибирск, 2008 г., С. 28-31.

5. Гадяцкая O.A., Родионов A.C. Исследование некоторых показателей связности случайных графов //IX Международная конференция "Проблемы функционирования информационных сетей"ИВМ и МГ, Новосибирск, 2006 г., С. 87-89.

6. Гадяцкая O.A. О некоторых оптимальных по критерию EDP системах сетевой структуры // VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям. Тезисы докладов. Новосибирск, 2007г. С.89.

7. Дудник Б.Я., Овчаренко В.Ф., Орлов В.К. и др.; Под ред. Б.Я. Дудника. Надежность и живучесть систем связи // М.: Радио и связь, 1984. 216 с.

8. Егунов M. М. Анализ и синтез систем связи с учётом структурной надёжности // 3-й Евразийский форум международная научно-практическая конференция "Связьпром 2006", Екатеринбург: Ростелеком. С. 161-163.

9. Кауль С.Б. Оценка вероятности связности случайного графа // Эффективность и структурная надёжность информационных систем (СМ-7), Новосибирск, 1982. С. 3-6.

10. Кельманс А.К. Некоторые вопросы надёжности сетей // Автоматика и телемеханика, Т. 26, 1965, С. 567-574.

11. Краковская О. С., Толчан А. Я. Оценки вероятности связности графа сети связи // Информационные сети и коммутация, М.: Наука, 1968. С. 138-141.

12. Кристофидес Н. Теория графов: Алгоритмический подход; Пер. с англ. Э.В. Верш-кова, И.В. Коновальцева; Под ред. Г.П. Гаврилова // М.: Мир, 1978. 432 с.

13. Литвак Е.И. О вероятности связности графа // Изв. АН СССР. Техн. Кибернетика № 5, 1975. С. 161-165.

14. Ломоносов М.В., Полесский В.П. Верхняя граница надежности информационных сетей // Проблемы передачи информации, Т. 7, вып. 4, 1971. С. 78-81.

15. Ломоносов М.В., Полесский В.П. Нижняя оценка надежность сетей // Проблемы передачи информации, Т. 8, вып. 2, 1972. С. 567-574.

16. Ломоносов М.В., Полесский В.П. О максимуме вероятности связности // Проблемы передачи информации, Т. 8, вып. 1, 1972. С. 68-73.

17. Мигов Д.А. Выбор разрешающего ребра в методе ветвления и применение сечений для расчета надежности сетей// Мат. X межд. конф. "Проблемы функционирования информационных сетей". Новосибирск: Изд. ИВМиМГ СО РАН, 2008. С. 73-75.

18. Козлов Б.А., Ушаков И.А. Справочник по расчету надежности аппаратуры радиоэлектроники и автоматики // М.: Советское радио, 1975.

19. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях // Наука. Сиб. отд-ние, Новосибирск, 1990, 515с.

20. Попков В. К. Математические модели связности. 2-е изд., перераб. и доп. // Новосибирск: Изд. ИВМиМГ СО РАН, 2006.

21. Родионова O.K. Исследование и разработка методов анализа и синтеза оптимально-связных информационных сетей: Дис. . канд. гехн. наук: 05.13.18. // Новосибирск, 2003.

22. Родионов А.С., Гадяцкая О.А. Применение и расчет EDP-полинома случайного графа // Труды ИВМ и МГ СО РАН (Материалы Третьей азиатской международной школы-семинара "Проблемы оптимизации сложных систем"), Новосибирск, 2007 г. С. 93-107.

23. Родионов А.С., Родионова O.K. О точном вычислении вероятности связности графа // Тр. Междунар. конф. "Вычислительные технологии и математические модели в науке, технике и образовании", Т. 5 Алма-Ата, Казахстан, 2002. С. 140-147.

24. Родионов А.С., Родионова O.K. Некоторые методы ускорения расчета надежности информационных сетей // Мат. 30 Междунар. конф. "Информационные технологии в науке, образовании, телекоммуникации и бизнесе", Гурзуф, Украина, 2003. С. 215-217.

25. Степанов В.Е. О вероятности связности случайного графа Gm(t) // Теория вероятностей и её применения, Т. 15, вып. 1, 1970. С. 56-68.

26. Aggarwal К.К., Chopra Y.C., Bajwa J.S. Topological layout of links for optimizing the overall reliability in a computer communication system / / Microelectonics and Reliability, Vol. 22, 1982. P. 347—351.

27. Bail M.O., Colbourn C.J. and Provan J.S. Network reliability, Handbook of Opérations Research // Network Models, Elsevier North-Holland, 1995, P. 673-762.

28. Buzacott J.A., Chang S.K. Cut set intersection and node partition // IEEE Trans. Reliab. R-33, 1984. P. 385-389.

29. Carlier J., Lucet C. A decomposition algorithm for network reliability evaluation // Discrete Applied Mathematics, Vol. 65, №1-3, 1996. P. 141-156.

30. Colbourn C.J. The Combinatorics of Network Reliability // Oxford University Press, New York, 1987.

31. Colbourn C.J. Some open problems on reliability polynomials // Congr. Numer. 93, 1993. P. 187-202.

32. Erdes P, Renyi A. On Random Graphs I // Publicationes Mathematicae Debrecen 5 (1959), P. 290—297.

33. Jan R.H., Hwang F.J., Chen S.T. , Topological optimization of a communication networksubject to a reliability constraint// IEEE Trans. Reliab. Vol. 42,1993. P. 63—70.

34. Kelmans A. K. Crossing properties of graph reliability functions // Journal of Graph Theory, Vol. 35, Iss. 3, 2000. P. 206-221.

35. Kelmans A. K. On graphs with randomly deleted edges // Acta Math Acad Sci Hung,Vol. 37, Issues 1-3,1981. P. 259-267.

36. Kelmans A. K. Multiple crossings of network reliability functions // RUTCOR Research Report, Rutgers University, 1994. P. 43-94.

37. Koide T., Shinmori S., Ishii H., Topological optimization with a network reliability constraint // Discrete Applied Mathematics, Vol. 115, Issues 1-3, 2001. P. 135-149.

38. Krivoulets V.G., Polesskii V.P. What is the Theory of Bounds for Network Reliability?// Inf. Processes (ISSN: 1819-5822) Vol. 1 n. 2, 2001. P. 199-203.

39. Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer-Verlag Lecture Notes in Computer Science, Vol. 4097, 2006. P. 702-709.

40. Moore E.F., Shannon C.E. Reliable Circuits Using Less Reliable Relays //J. Franclin Inst., Vol. 262, n. 4b, 1956. P. 191-208.

41. Nahman J. Fuzzy logic based network reliability evaluation // Microelectronics and Reliability. Vol. 37, Iss. 8, 1997. P. 1161-1164.

42. Page L.B., Perry J.E. Reliability polynomials and link importance in networks // IEEE Transactions on Reliability, Vol. 43 Iss. 1, 1994 P. 51-58.

43. Reittu H., Norros I. Random graph models of communication network topologies // ICCS-07, Boston, USA, 2007. The paper can be found via http: //arxiv.org/abs/0712.1690

44. Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Optimal Structures // The 2004 International Conference on Computational Science and Its Applications, Springer, Lecture Notes in Computer Science, Vol. 3047, 2004, P. 431440.

45. Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Exact Calculation with Use of Chains // ICCSA-2004, Springer Lecture Notes in Computer Sciences. Vol. 3046. P. 315-324.

46. Rodionov A., Rodionova O. Network Probabilistic Connectivity: Expectation of a Number of Disconnected Pairs of Nodes // HPCC 2006, Springer, Lecture Notes in Computer Science, Vol. 4208, Springer 2006, P. 101-109.

47. Rodionov A.S., Choo H. On Generating Random Network Structures: Connected Graphs // Proc. Intern. Conf. On Information Netwotking ICOIN, Vol. 3, 2004. P. 11451152.

48. Satyanarayana A., Chang M.K. Network reliability and the factoring theorem // Networks Vol. 13, 1983. P. 107-120.

49. Satyanarayana A., Wood R.K. A linear-time algorithm for computing /¿ terminal reliability in series-parallel networks // SIAM. J. Comput., Vol. 14, 1985. P. 818-883.

50. Shooman A.M. Algorithms for Network Reliability and Connection Availability Analysis // Electro/95 Int. Professional Program Proc.,1995. P. 309 333

51. Shooman A.M., Kershenbaum A. Exact graph-reduction algorithms for network reliability analysis // GLOBECOM '91. Countdown to the New Millennium. Featuring a Mini-Theme on: Personal Communications Services, Vol. 2, 1991. P. 1412-1420.

52. Shooman A.M., Kershenbaum A. Methods for communication-network reliability analysis: probabilistic graph reduction // Reliability and Maintainability Symposium, Proceedings, 1992. P. 441-448.

53. Shooman A.M. Algorithms for network reliability and connection availability analysis // Electro-95 International. Professional Program Proceedings, 1995. P. 309-333.

54. Van Slyke R, Frank H. Network Reliability Analysis. Pt. 1 // Networks, Vol. 1, Iss. 3,1972. P. 279-290.

55. Wood R.K. Triconnected Decomposition for Computing ii-Terminal Network Reliability // Networks, Vol. 19, 1989. P. 203-220.