2.1 Аналитические методы

Рассмотрим задачу определения надежности связи (вероятности связности) меж­ду узлами сети а_s и а_t, если задано множество путей M_st, которые могут быть использованы для связи указанных узлов, и извест­ны показатели надежности линий связи сети, образующих указанные пути [1].

При использовании одного пути для связи двух узлов сети, надежность связи узлов определяется как надежность этого пути.

Надежность к - ого пути между узлом s и t, при условии независимости элементов сети, оценим вероятностью одновременного работоспособного состояния всех линий связи, образующих этот путь, т. е.

(2.1)

где – вероятность исправного состояния линии связи ij, принадлежащей k – ому пути между узлами s и t ( -вероятность неисправного состояния линии связи ij). Если учитывать надежность узлов, то

, (2.2)

где – показатель надежности i – ого узла, входящего  в путь между узлами s и t. Надежность связи (вероятность связности) двух узлов s и t - ,будем оценивать вероятностью исправного состояния хотя бы одного пути из заданного множества M_st .

Если отдельные элементы пути (их участки или линии связи) образуют по отно-шению к узлам s и t параллельно-последовательную структуру, то для опреде-ления надежности связи (вероятности связности)  можно использовать обычные методы определения надежности структур с таким соединением элементов. При последовательном соединении можно пользоваться формулой (3.1,3.2), а при параллельном соединении элементов общая надежность рассчитывается по формуле

pпар =1 - (1 – p i ), (2.3)

где n - число параллельно соединенных элементов; pi- надежность каждого элемента.

На рисунке 2.1 приведены примеры параллельно-последовательной структуры (рис. а) и с мостиковым соединением (рис. в) по отношению к узлам 1и 3.  

Рис. 2.1 Пример структур сети параллельно-последовательной (а) и с мостиковым соединением (в) по отношению к узлам 1 и 3

Пример 1

Получить выражение для расчета надежности связи (вероятности связности) между 1-ой и 3-ей вершиной графа сети, представленного на рисунке 2.2.

Рис. 2.2 Граф сети

Решение

Анализ графа сети показывает, что по отношению к вершинам 1 и 3 сеть имеет параллельно- последовательную структуру. Поэтому для определения надежности связи P13 можно воспользоваться выражениями 2.1 и 2.2. Тогда

P13 = (2.4)

Если узлы сети абсолютно надежны, то выражение для расчета P13 будет иметь вид:

P13 = (2.5)

Если в структуре сети имеются мостиковые соединения, то ис­пользовать приведен-ные формулы 2.1 и 2.2 нельзя. Напри­мер, для структуры (рис. 2.1 в), отличающейся от структуры (рис.2.1 а) наличием ребра g. Одним из методов расчета надежности свя­зи Pst между узлами s и t для сложной структуры является метод последователь-ного разложения структуры [1]. Метод основан на том свойстве, что надежность структуры, включающей ребро , рассчитывается как:

, (2.6) где - надежность связи между узлами s и t в сети, в которой узлы l и m слиты; - надежность связи между узлами s и t в сети, в которой изъято ребро b_lm. Разложение производится до тех пор, пока ос­тавшиеся структуры не будут параллельно-последовательными. Метод последовательного разложения позволяет определить надежность связи между заданными узлами в виде функции или числового значения. Однако он не работает в случае, если необходимо определить надежность заданного мно­жества путей m_st, меньшего, чем множество всех путей между узлами s и t.

Пример 2

Получить выражение для расчета надежности связи (вероятности связности) между 1-ой и 3-ей вершиной графа сети, представленного на рисунке 2.3. Узлы абсолютно надежны.

Решение Анализ графа сети (рис. 2.3) показывает, что по отношению к вершинам 1 и 3 сеть имеет мостиковую структуру. Для решения поставленной задачи используем метод последовательного разложения структуры сети. Разложение произведем по ребру g.

Тогда

, (2.7)

где - надежность связи в сети, в которой p_g=1, т. е. узлы 2 и 4слиты;

- надежность связи в сети при p_g = 0 , т. е. из сети изъято ребро g.

Рис. 2.3 Граф сети.

Тогда

= (2.8)

= ; (2.9)

* + *( ). (2.10)

Для определения надежности связи узла s с узлом t, при ограниченном числе используемых путей, предлагается воспользоваться следующим алгоритмом:

1. Определим список путей, которые могут быть использованы для связи узла s с узлом t.

2. Каждому пути поставим случайное событие Ai, характеризующее исправное состояние i - ого пути.

3. Определим надежность каждого из указанных путей c учетом заданных показателей надежности элементов сети.

Полученные выражения определяют вероятность наступления каждого события Ai,

соответствующие множеству путей между узлом s и t.

4.  Для определения надежности связи, воспользуемся формулой для расчета вероятности суммы совместных событий Ai, поставленных в соответствие множеству путей между узлами s и t [5].

(2.11)

где t - число путей между узлом s и t.

Ai – событие, поставленное в соответствие i-ому исправному пути из множе-

ства путей ;

P(А_i) – вероятность наступления события А_i;

P(А_i А_j) – вероятность совместного наступления двух событий А_i и А_j;

P(А_i А_j А_к) - вероятность совместного наступления трех событий А_i, А_j и А_к;

.

.

P(А₁ А₂ …А_t) – вероятность совместного наступления t событий А_i.

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

Пример 3

Определить надежность связи (вероятность связности) узла 1 с узлом 3 - Р13 в сети, представленной на рисунке 2.4. При этом для связи указанных узлов могут быть использованы любые допустимые пути. Элементы сети (узлы и линии связи) являются статистически независимыми элементами.

Рис. 2.4 Граф сети

Для определения надежности связи Р13 воспользуемся выше приведенным алгоритмом.

1.Определим пути, которые могут быть использованы для связи узла 1с узлом 3.

= { , }; = { , , }; = { , }.

2. Поставим каждому из указанных путей случайные события Аi, соответствующие работоспособным состояниям этих путей.

А1 поставим в соответствие пути ; А2 – пути ; А3 – пути .

3. Определим вероятность наступления событий Аi, зная маршруты путей и коэффициенты готовности линий связи сети.

Р(А1) = К12 * К23; Р(А2) = К14 * К24 * К23; Р(А3) = К14 * К34.

4. Используя формулу 3.11, определим надежность связи Р13.

Р13 = К12 * К23 + К14 * К24 * К23 + К14 * К34 ­ К12 * К23*К14 * К24 ­ К12 * К23 * К14 * К34 ­

К14 * К24 * К23 * К34 + К12 * К23*К14 * К24 * К34.

Подставляя конкретные значения коэффициентов готовности Кij, рассчитаем Р13. Если коэффициенты готовности для всех линий связи одинаковые и равны 0.9, получим Р13 = 0.97119.

Для определения математического ожидания числа связей в сети М (Х)  воспользуемся основными положениями теории вероятности [5]. Пусть случайная величина Х поставлена в соответствие общему числу действующих связей в сети. При наличии n взаимодействующих друг с другом узлов. Случайная величина X меж - узловых связей в сети будет изменяться в пределах 0 ≤ X ≤ n(n – 1). Если каждой связи в сети поставить в соответствие случайную величину xi, то случайная величина X может быть определена как

, (2.11)

где M – число рассматриваемых связей в сети. Тогда

(2.12) В соответствии с теоремой сложения математических ожиданий

(2.13) Величина является дискретной случайной величиной, принимающей значения 1, если i-ая связь существует в сети, и 0, если i-ая связь отсутствует, т.е. данные события образуют полную группу. Для определения математического ожидания случайной величины необходимо определить вероятности того, что данная величина принимает значение 1 или 0. Тогда

m(xi) = 1*Pi + 0*(1- Pi) = Pi (2.14) Следовательно

(2.15)

Вероятность Pi эквивалентна надежности связи (вероятности связности) узлов, образующих i-ую связь.

С учетом выше сказанного, для определения математического ожидания числа связей М (Х) предлагается использовать следующий алгоритмом:

1. Определим  список взаимодействующих пар узлов сети.

2. Определим пути, которые могут быть использованы для связи каждой пары узлов сети из заданного списка.

3. Для каждой пары узлов, с учетом надежности элементов сети и используемых для связи путей, определим вероятность связности.

 4. Произведем суммирование значений вероятностей связности различных пар уз-лов сети из заданного списка.

В результате получим абсолютное значение математического ожидания числа связей сети – М (Х). Удобнее и нагляднее данную величину выразить в относительных еди-ницах. В этом случае величина М (Х)_отн. может быть рассчитана по формуле:

         М (Х)_отн. = (М (Х)/M_max)·100% , (2.16)

где M_max – число связей в сети из заданного списка при условии, что все элементы сети абсолютно надежны.

Пример 4

Определить математическое ожидание числа связей М(Х)_отн. для сети, представленной на рисунке 2.5, при условии, что используются все допустимые пути для связи узлов сети и коэффициент готовности каждой линии связи (ребер графа сети) равен К_г = 0,9. Узлы сети абсолютно надежны.

Рис. 2.5 Граф сети

Для решения задачи воспользуемся алгоритмом определения математического ожидания числа связей М(Х).

1. Определим список путей, связывающих узлы сети.

m¹₁₂={b₁₂}, m²₁₂ = {b₁₃ ,b₂₃}; m¹₁₃ = {b₁₃}, m²₁₃ = {b₁₂ ,b₂₃};

m¹₁₄ = {b₁₃ , b₃₄}, m²₁₄ = {b ₁₂ ,b₂₃ ,b₃₄}; m¹₂₁ = {b₁₂}, m²₂₁ = {b₁₃ ,b₂₃};

m¹₂₃ = {b₂₃}, m²₂₃ = {b₁₂ ,b₁₃}; m¹₂₄ = {b₂₃ ,b₃₄}, m²₂₄ = {b₁₂ ,b₁₃ ,b₃₄};

m¹₃₁ = {b₁₃}, m²₃₁ = {b₁₂ ,b₂₃}; m¹₃₂ = {b₂₃}, m²₃₂ = {b₁₃ ,b₁₂}; m¹₃₄ = {b₃₄};

m¹₄₁ = {b₁₃, b₃₄}, m²₄₁ = {b₁₂ ,b₂₃ ,b₃₄}; m¹₄₂ = {b₂₃ ,b₃₄}; m²₄₂ = {b₁₂ ,b₁₃ ,b₃₄};

m¹₄₃ = {b₃₄}.

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

P(m¹₁₂) = P (m¹₂₁) = К₂₁; P (m¹₁₃) = P (m¹₃₁) = К₂₃;

P (m¹₂₃) = P (m¹₃₂) = К₂₃; P (m¹₃₄) = P (m¹₄₃) = К₃₄;

P (m¹₁₄) = P (m¹₄₁) = К_13* К₃₄; (P m¹₂₄) = P (m¹₄₂) = К_23* К₃₄;

P (m²₁₂) = P (m²₂₁) = К_13* К₂₃; P (m²₁₄) = (m²₃₁) = К_21* К₂₃;

P (m²₂₃) = P (m²₃₂) = К_13* К₂₁; P (m²₁₄) = P (m²₄₁) = К_21* К_23* К₃₄;

P (m²₂₄) = P (m²₄₂) = К_21* К₁₃*К₃₄.

3. Определим вероятности связности для каждой пары вершин графа (узлов сети).

Р₁₂ = Р₂₁ = К₂₁ + К₁₃ К₂₃ - К₂₁ К₁₃ К₂₃;

Р₁₃ = Р₃₁ = К₁₃ + К₂₁ К₂₃ - К₂₁ К₁₃ К₂₃;

Р₁₄ = Р₄₁ = К₁₃ К₃₄ + К₂₁ К₂₃ К₃₄ – К₁₃ К₂₁ К₂₃ К₃₄;

Р₂₃ = Р₃₂ = К₂₃ + К₁₃ К₂₁ – К₁₃ К₂₁ К₂₃;

Р₂₄ = Р₄₂ = К₂₃ К₃₄ + К₂₁ К₁₃ К₃₄ – К₁₃ К₂₁ К₂₃ К₃₄;

Р₃₄ = Р₄₃ = К₃₄ ;

4. Определим выражение для расчета математического ожидания числа связей в сети

М(Х).

М(Х) = Р₁₂ + Р₂₁ + Р₁₃ + Р₃₁ + Р₁₄ + Р₄₁ + Р₂₃ + Р₃₂ + Р₂₄ + Р₄₂ + Р₃₄ + Р₄₃.

5.Определим максимальное число межузловых связей в сети при абсолютно надежных элементах.

M = m (m-1) = 4 x 3 = 12 (m – число вершин графа сети).

Определим М(Х)_отн., подставив значение К_г = 0,9 в выражение, полученное в пункте 4. Тогда

М(Х)_отн. = М(Х)/ (m (m-1)) 100% = (10.3576 /12) 100% = 86,31%