Показатели связности для систем с сетевой структурой
В настоящее время в вычислительных системах и связи большое распространение получили системы сетевой структуры.
Одним из важных является вопрос о наличии связи между двумя абонентами сети. для оценки этой задачи будем использовать графы. Сами элементы сети будем считать абсолютно надежными.
Так как мы используем только линии связи, то в данном случае они не будут, является для нас изучаемыми устройствами.
Введем новое понятие – структурная функция двухполюсного графа
Система такого вида называется системой с монотонной структурой. При этом их структурная функция обладает следующими свойствами:
1) если все элементы работоспособны, то и система работоспособна.
2) все элементы отказали, следовательно, система отказала.
3) если для всех i и хотя бы для одного.
При отказе элемента состояние системы не улучшается.
1)если , то замена любого элемента на не уменьшают вероятность связности.
Определим вероятность связности полюсов графов.
Для простоты будем считать, что все ребра одинаково надежны, их вероятность . Пусть есть n ребер. Вероятность того, что откажут i ребер: .
вероятность связности полюсов определяются следующим образом.
Использовать такой метод трудно при большом количестве элементов, поэтому используем методы верхней и нижней граничных оценок вероятности связности.
Введем понятие цепь. Цепь – это такое подмножество ребер графа обеспечивающих связность между полюсами. Простая цепь — это подмножество ребер графа, которое обеспечивает связность его полюсов даже при отсутствии остальных ребер, но отказ любого из элементов цепи приводит к нарушению связности полюсов.
Простая цепь — это последовательное соединение элементов.
nk – число элементов в цепи, ak – множество индексов элементов входящих в .
Простой разрез — это подмножество ребер графа, отсутствие которых приводит к нарушению связности полюсов даже при наличии остальных ребер графа, но введение в граф любого элемента приводит уже к наличию связности полюсов.
Метод Эзари-Прошана
Данный метод позволяет определить верхнее и нижнее граничные значения вероятности связности полюсов графа. Данный метод опирается на следующие положения:
Если события А и В положительно коррелированны, то .
Если распространить это на любое количество элементов, то .
В результате получаем:
для простых разрезов.
для простых цепей.
— 2-стороняя оценка Эзари-Прошана.
Представление произвольного 2-полюсного графа в виде параллельного соединения простых цепей, составленных из независимых элементов, дает верхнюю оценку вероятности связности. Представление этого же графа в виде последовательного соединения простых разрезов дает нижнюю оценку этой вероятности.
Метод Дитвака-Ушакова
1. Представление графа в виде параллельного соединения реберно-непересекающихся простых цепей:
а) Выбираем произвольную простую цепь. Исключаем ее из графа.
б) Выбираем из оставшейся части графа другую простую цепь. Исключаем ее из графа, и т.д. до тех пор пока граф не окажется несвязным или пока не будут использованы все ребра.
2. Представление графа в виде последовательного соединения реберно-непересекающихся простых разрезов:
а) Выбираем произвольный простой разрез.
б) Все вершины с одной стороны оттягиваем в одну точку, а все вершины с другой стороны – в другую точку.
Выполняемые операции эквивалентны введению в граф “абсолютно надежных” ребер. Следовательно любой из полученных оценочных графов имеет завышенную вероятность связности.
В сложных сетевых вычислительных системах аналитическое описание моделей очень громоздкое, а иногда невозможное. В этом случае производят имитацию реального процесса на статистической модели, воспользовавшись статистическими данными о параметрах системы.
Недостатком данного метода является то, что он содержит избыточность приводящую к увеличению объема расчета. Некоторые реализации эксперимента можно не моделировать. Если не работают 1 или 2, то нет необходимости моделировать 3,4,5. если работает 1 и 4, то нет необходимости моделировать 5, т.к. есть уже простая цепь.
