Примеры сетевых топологий

         

Последовательное построение/разрушение


Метод последовательного построения/разрушения базируется на анализе упорядочивания ребер графа. Сначала все ребра находятся в нерабочем состоянии, затем ребра последовательно оказываются “отремонтированы”, т.е. переходят в рабочее состояние одно за другим в специфицированном порядке, пока вся система не перейдет в работоспособное состояние. Оценка надежности определяется тем, сколько времени требуется системе, чтобы стать работоспособной. Это позволяет получить лучшую оценку, чем наивный метод.

Пространство событий для последовательного метода построения состоит из пары (x,p), где х - вектор состояния системы, а p = (p(1),…,p(m)) является перестановкой индексов ребер Е, такой, что для некоторого индекса k мы имеем:

xp(1)=…=?x p(k) =1, xp(k+1)=,…,x p(m) =0.

Если вектор состояния х выбран согласно предписанным вероятностям состояния, а перестановки p выбраны независимо и однородно по отношению ко всем подходящим перестановкам, тогда вероятность реализации конкретной пары (x,p) равна

,

где k равно числу рабочих элементов в х. Метод последовательного конструирования испытывает перестановку

и рассматривает одновременно набор P
всех возможных пар состояний (x,p) p=
и х, согласующимся с
в рамках выше приведенных критериев. Значение надежности набора испытаний (sample)
является условной вероятностью работы системы с учетом P
, то есть, отношение суммы вероятностей пар (x,p) О P
, для которого Ф(х)=1, к вероятности P
. Подробности представлены ниже.

Метод последовательного конструирования

1. Выбираем образец перестановки

=(
(1),…,
(m)) из набора перестановок {1,…,m}. Определяем векторы x(k), k=1,…,m как

2. Определяем первый индекс r=0,…,m, для которого Ф(x(r))=1.

3. Вклад

в оценочный параметр R тогда

4. Складываем набор значений

и делим на число выбранных перестановок набора. Это является несмещенной оценкой R.

Оценка, полученная для каждой выбранной перестановки из набора, имеет меньшую вариацию, чем полученная для одного образца при наивном алгоритме. Наибольшие вычислительные усилия тратятся на этапе 2 и это сильно зависит оттого, как быстро можно обновить значение Ф(x(k)), т.е.
насколько легко можно определить функциональность системы по ребрам, восстановленным одно за другим. Заметим, однако, что восстановление ребер должно производиться только до тех пор, пока система не станет полностью функциональной (в предположении связности системы), так как дальнейшее восстановление ребер графа не изменит рабочего состояния системы. Таким образом, объем выполненной работы может быть много меньше чем порядок m. В случае надежности коннективности было показано, что определение индекса r может быть выполнено почти также легко, как определение Ф(х) для одного значения х, так что последовательные выборки будут получаться по той же цене, что одна выборка в наивном методе. Наконец, при равных вероятностях отказов для ребер мы получаем дополнительное преимущество того, что знаменатель в выражении для этапа 4 (см. выше) всегда равен 1, что сокращает объем вычислений.

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


Содержание раздела