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

• Автор: Гадяцкая, Ольга Александровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Новосибирск
• Количество страниц: 96 с. : ил.

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

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

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

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

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

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

1.1.5. Критерий .

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

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

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

1.3.2. Метод ветвления
1.4. Полиномы надежности.
1.5. Полиномы надежности для вероятности связности.
1.6. Формулы для расиста .
1.6.1. полином двухвершинного графа.
1.6.2. полином трех верши иного графа.
1.6.3. Формула для моста
1.6.4. Удаление висячей вершины.
1.6.5. Ветвление по цепи длины
1.6.6. Формула для полинома графа в случае наличия в нем точки сочленения
1.6.7. Формула для полино.ма графа, представляющего собой два несвязных блока.
1.7. Предварительные утверждения.
1.8. Пример различия результатов оптимизации по критериям вероятности связности и
1.9. Формулы полиномов надежности для распространенных сетевых топологий .
1.9.1. Полином надежности для цепи
1.9.2. полином для звезды
1.9.3. полином для цикла.
1 Полиномы надежности известных графов в случае наличия ограничения на диаметр.
. Полином надежности для звезды в случае наличия ограничения на диаметр.
. Полином надежности для цени в случае наличия ограничения на диаметр.
. Полином надежности для цикла в случае наличия ограничения на диаметр.
1 Результаты и выводы к Главе 1
Глава 2. ТЕОРЕТИЧЕСКАЯ ОПТИМИЗАЦИЯ СЕТЕВЫХ ТОПОЛОГИЙ ПО КРИТЕРИЮ
2.1. Вспомогательные утверждения
2.2. Добавление ребра в распространенные сетевые топологии .
2.2.1. Добавление ребра в звезду.
2.2.2. Добавление ребра к цепи.
2.2.3. Добавление ребра в цикл.
2.2.4. Сравнение оптимального добавления ребра по критериям и вероятности связности
2.3. Оптимальное расположение особых вершин отличного веса . .
2.3.1. Цепь с особой вершиной .
2.3.2. Звезда с одной особой вершиной
2.3.3. Особая вершина в топологии цикл с присоединенной вершиной .
2.3.4. Особая вершина в графевосьмерке
2.4. Оптимальное по критерию присоединение структур .
2.4.1. Присоединение звезды.
2.4.2. Присоединение цепи.
2.4.3. Присоединение графавосьмерки .
2.4.4. Сравнение результатов оптимального присоединения графов по критерию с результатами оптимального присоединения этих графов но критерию максимума вероятности связности
2.4.5. Оптимальное соединение циклов
2.5. Результаты и выводы к Главе 2.
Глава 3. ПРОГРАММНЫЕ АЛГОРИТМЫ И ИХ РЕАЛИЗАЦИЯ
3.1. Реализация подсчета коэффициентов обычного полинома надежности
3.1.1. Замечания о программной реализации подсчета коэффициентов обычного полинома надежности.
3.2. Особенности программной реализации подсчета коэффициентов полинома надежности графа в условиях наличия ограничения на диаметр.
3.3. Численные эксперименты
3.3.1. Ускорение расчетов в случае обычного подсчета коэффициентов полиномов надежности.
3.3.2. Тестирование теоретических результатов из главы 2 .
3.3.3. Оптимизация сетевых топологий по критерию с помощью точного расчета полиномов надежности.
3.4. Результаты и выводы к Главе 3.
Заключение
Литература


Поэтому требуется исследовать различные критерии сетевой надежности, способы расчета соответствующих показателей и разрабатывать инструментарии для оптимального проектирования инфокоммуникационных сетей согласно выбранному критерию надежности. Эти инструментарии должны включать в себя как программные комплексы для быстрого расчета функционалов надежности, так и каталоги уже проверенных на оптимальность решений для различных сетевых топологий. Исследованиями различных критериев надежности инфокоммуникационных сетей занимались и занимаются многие ученые. Артамонова Г. Т., Вишневского В. М., Дудника Б. Я., Егунова М. М., Епихина В. В., Кауля С. Б., Кельманса А. К., Литвака В. И., Ломоносова М. В., Майнагаиева С. М., Нечепуренко М. И., Мухопада . Ф, Полесского В. П., Попкова В. К, Родионова , Скоробогатова В. А., Толчана А. Я, Харкевича А. Д. Среди зарубежных исследователей это М. О., С. Л., i Т. В., , , v , . V . Данная диссертационная работа посвящена исследованию такого критерия надежности сети, как минимум числа несвязных нар узлов. Этот критерий может использоваться как критерий надежности в сетях связи, некоторые элементы которых могут выходить из строя в результате естественных причин изнашивание оборудования, воздействие погодных условий, стихийные бедствия или намеренного разрушения. Он, очевидно, довольно хорошо отражает последствия для сети после выхода из строя ее элементов чем больше несвязных пар узлов появилось, тем значительней разрушение сети. Таким образом, используя этот критерий, можно искать критические точки узлы и линии связи сети, выход из строя которых влечет за собой значительное ухудшение функционирования сети. Такой показатель надежности, как число несвязных пар узлов сети характеризует качество связи с точки зрения абонента, т. Если элементы сети выходят из строя с некоторой вероятностью, то становится возможным оценивать матвхматичсское ожидание числа несвязных пар узлов сети , от англ. Далее критерий минимума математического ожидания числа несвязных пар вершин будем называть критерием минимума или просто критерием. Задача точного расчета математического ожидания числа несвязных пар узлов сети довольно нова. В то время, как этот критерий надежности сетей давно известен , , , , ранее этот показатель вычислялся только приближенными методами, в основном методом
МонтеКарло , в связи с трудностью задачи . Использование приближенных методов обуславливалось, прежде всего, тем, что вычислительные мощности имеющейся техники не позволяли вычислять точные значения функционалов надежности для реальных сетей связи. В настоящее время произошло значительное увеличение возможностей вычислительной техники и поэтому стало возможным испол1зовать точные методы вычисления для сетей реальных размерностей десятки узлов. Точные методы расчета этого функционала надежности необходимы также для проверки качества приближенных методов расчета. Одни из первых работ о точном вычислении математического ожидания числа несвязных пар узлов это работы Родионова Л. С. и Родионовой , , . Программное обеспечение по приближнной оптимизации методом МонтеКарло структур сетей связи с использованием критерия разработано М. М. Егуновым и используется в ГОУ ВПО СибГУТИ . В диссертационной работе рассматривается выбор оптимальных сетевых топологий согласно критерию минимума математического ожидания числа несвязных пар узлов, в случае, когда узлы сети пользовательские терминалы, маршрутизаторы и другое сетевое оборудование абсолютно надежны, а линии связи равно ненадежны и выходят из строя независимо друг от друга с вероятностью р. Такая постановка задачи моделирует ситуацию проектирования новой сети, в случае, если надежность узлов сети предполагается много большей, чем надежность ее линий связи, а линии связи однотипны и находятся в одинаковых условиях. В этом случае функционал представляет собой полином. Целью данной диссертационной работы является разработка и программная реализация алгоритмов для расчета коэффициентов полиномов и создание библиотеки программ на основе этих алгоритмов.