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

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

Содержание
Введение

1. Методы расчета характеристик связности случайного

_ графа

1.1. Определения и обозначения

1.1.1. Понятие случайного графа

1.2. Характеристики случайных графов

1.3. Метод ветвления и его модификация

1.4. Использование покрывающих деревьев при точном вычислении надежности графа

1.5. Редукция цепей

^ 1.6. Расчет коэффициентов полинома связности
1.7. Приближенные методы вычисления вероятности связности графа
1.8. Выводы
2. Оптимизация структур сетей по критерию максимума
вероятности связности
2.1. Оптимально-связные структуры сетей
2.2. Оптимальная достройка кольцевых структур
2.3. Оптимальное соединение кольцевых структур
^ 2.3.1. Пересечение циклов
2.3.2. Соединение двух циклов
2.4. Оптимальное циклическое соединение циклов
2.5. Выводы
3. Программная реализация алгоритмов
3.1. Поиск цепи
3.2. Перенумерация вершин разрешающей цепи
® 3.2.1. Реализация перенумерации
3.3. Реализация расширенной формулы Мура-Шеннона
Содержание
3.3.1. Варианты результатов стягивания и удаления
3.3.2. Оконечные рассчитываемые варианты графов
3.4. Реализация редукции цепей
3.5. Реализация метода Чена-Ли
3.6. Реализация расчета коэффициентов полинома связности .
3.6.1. Оконечные состояния при расчете полинома связности
3.6.2. Ветвление по мультиребру
3.6.3. Использование ветвления по цепям
3.6.4. Учет “прикрепленных деревьев”
3.6.5. Учет “прикрепленных циклов”
3.7. Выводы
4. Экспериментальное исследование алгоритмов ,
4.1. Формула Мура-Шеннона
4.1.1. Классический вариант ветвления по ребрам
4.1.2. Расширенная Формула Мура-Шеннона
4.1.3. Применение последовательно-параллельной редукции
4.1.4. Метод Чена-Ли
4.2. Расчет и использование полинома связности
4.2.1. Зависимость вероятности связности от типа графа
4.3. Выводы
Заключение
Литература

Введение
Задачи структурной оптимизации информационно-вычислительных сетей с точки зрения надежности и живучести, равно как задача расчета этих характеристик, являются одними из основных при проектировании подобных сетей [3, 6-8, 12, 23, 24, 28, 29, 38, 50, 56, 59-62, 68, 69, 72, 73, 75, 79, 80, 82]. Одним из важнейших показателей надежности работы сетей связи является их связность.
Существует много характеристик связности, что делает задачу не однозначной: реальным целям проектирования соответствуют различные целевые функции и ограничения [23]. В классической теории графов под связностью понимают либо реберную, либо вершинную связность. В зависимости от того, какая математическая модель описывает рассматриваемую задачу, различными авторами связность может трактоваться несколько иначе. Попытка систематизировать и классифицировать понятие связности и характеристик, связанных с ней, введенных за последние 30 лет, сделана в работе В.К. Попкова [31].
Одной из наиболее распространенных характеристик связности сети является вероятность связности заданного подмножества вершин то есть вероятность того, что в конкретный момент времени между каждой парой этих вершин существует хотя бы один путь при заданных вероятностях присутствия ребер (эту вероятность для краткости часто называют надежностью ребра, в данном исследовании также используется этот термин). Существует два крайних варианта: к = 2 и к = га, где п - число вершин сети. Некоторые авторы (см., например, [51]) рассматривают в качестве основного показателя среднюю вероятность существования хотя бы одного пути по всем парам ребер. При рассмотрении сетей с равнонадежными каналами многие выводы, особенно при сравнении надежности различных структур, можно сделать с помощью так называемого полинома надежности или полинома связности, который показывает зависимость вероятности связности сети (графа) от надежности одного канала (ребра). Мы будем придер-
1.6. Расчет коэффициентов полинома связности

(1.25)

Е д - (в + 1) +

а согласно (1.18)

г = П Р% рг1- « + 1) X (

П Рг 1=
1/» г=

П Рг ■ Рз+

= £ П Рз - [(й +*) - Ч П Р
1=1 У#г
= П Рг' £ Рг 1 - (в + 1) -
з / з+
(1126)
i=l г=
что и требовалось доказать.
Применение редукции по целым цепям дает выигрыш во времени вычислений как за счет сокращения совокупного числа операций на вычисления по формулам, так и снижения числа рекурсий и, особенно, проведения перенумераций вершин за один раз. Снижение числа рекурсий по сравнению с расширенной формулой Мура-Шеннона достигается за счет того, что редукция цепей может привести к рассчитываемой размерности до выполнения ветвления по редуцированному ребру, тогда как при ветвлении по цепям рассчитываемая размерность достигается после стягивания по цепи либо ее удаления.
1.6. Расчет коэффициентов полинома связности
Расчет коэффициентов полинома связности требует применения точных методов. В простейшем случае это метод ветвления по Муру-Шеннону. В отличие от случая вычисления численного значения надежности, в данной задаче необходимо рекурсивное вычисление коэффициентов полинома (1.7) с приведением подобных после каждого выхода из рекур-