книги / Надежность и живучесть систем связи

та р(Е) по модифицированному алгоритму показана на рис. 3.6. Метод прямого перебора состояния системы связи применяется ограниченно, но благодаря простоте алгоритмов .используется в качестве вспомогательного средства для проверки правильности работы сложных программ, реализующих более эффективные -ме­ тоды расчета.

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

3.3.Методы прямого перебора состояний путей системы связи

Вторую группу методов, в которых используется принцип пря­ мого перебора, составляют методы .перебора состояний путей ДС. Двухполюсная сеть отображается множеством путей М, и ставит­ ся задача вычисления вероятности исправности хотя бы одного из них.. Если все пути ДС структурно независимы между собой, то

p{E) = \ - Y ] [ \ - p ( e i)].	(3.10)
i=i

Как показано в гл. 1, состояния большинства путей ДС коррелированы друг с другом, поэтому (3.10) — это оценка р(Е)“ оверху [7]. Сущность методов прямого перебора путей состоит в пред­ ставлении (3.10) в виде

Р(Е) = S р (et)-	S Р(etev)+	1)*"1р ( 5 U ) .	(3.11)
<=I	i<v	\ ‘=1 /

Последняя формула представляет собой вероятность суммы совместных независимых событий. Здесь / п= С пл, я —1, .... h.

Для компактной записи алгоритма вычислений преобразуем (3.11). Обозначим In={Inh}, где Ink содержит k-ю комбинацию

я -путей из общего числа сочетаний из h по п,	я=-1, ..., 1п, а
р(Еп) — вероятность -испра1вности хотя бы одно-го	подмножества
Ink путей, определяемая из выражения
Тогда (3.10) имеет вид
	(3.13)

Известны два подхода к исключению -корреляции состояний путей при вычислении р {Ink) • Оба подхода обеспечивают выпол­ нение условия, что степень любого сомножителя в слагаемых (3:11) должна быть не выше единицы. Первый подход основан на вычислении условных вероятностей исправности путей в сла­

гаемых (3.11). Запишем р(/пл)' =р(вг)Р(еу| б0 Э т о произведение содержит п сомножителей.

51

Условные вероятности
p(ejК ? ^ -) =	П Р Г Г ’
	П Р (3/‘)
	эЛе е
где е —множество элементов ДС,	общих для 'пути	р,- и путей
Ь , .... а
г (^)
P(ei)= П р		(ЗЛ4)
shev.
При втором подходе •и-спользуется свойство логического сло­
жения Булевых переменных: а + а + а + ... =й. Тогда
р ( и = П И 4		(3.15)
э£ев

где б есть объединение элементов путей щ е/„й . Указанное свой­ ство применяется при формировании множества б.

Применение преобразования Булевой алгебры более экономич­ но по сравнению с вычислением условных вероятностей. Алгоритм вычисления р(Е) методом прямого перебора состояний путей с использованием преобразования Булевой алгебры имеет 2/l шагов. Особености алгоритма следующие. Номера разрядов двоичных чи­ сел ДСН соответствуют номерам путей. Если v-й разряд ДСН-,.: = 1г то принято, что путь |xv исправен.

шаг k, k^2. Формируется двоичное число ДСНи и определя­ ется число п разрядов, для которых ДС/Д =1. Пути pv состав­ ляют множество 1пк.

Элементы путей pv e / njt включаются в множество б, и по (3.15) вычисляются р{1пк), в соответствии с (3.12)

P n = p A - i + p f y .

После выполнения 2к шагов по (3.13) вычисляется р(Е). Схема алгоритма изображена на рис. 3.7. Длина машинной програм­ мы составляет 383 оператора языка ФОРТРАН без учета про­ граммы формирования множества М.

Пример. Требуется при абсолютно надежных узлах и ptj=0,9 вычислить вероятность р{Е) исправности ДС D3, множество путей которой приведено а табл. 3.1.

Результаты каждого из 15 шагов алгоритма (первый шаг алгоритма соот­ ветствует второму состоянию счетчика) записаны в табл. 3.5. В нижней частитаблицы записаны выражения и значения р{Еп) и р[Е).

Основную долю времени расчетов изложенным методом, как и методом перебора состояний элементов системы, составляет вре­ мя формирования двоичных чисел. Зависимость времени анализа состояний путей (вычисление р (1пк) ) изображена на рис. 3.8. П<ри сравнении зависимостей на рис. 3.7 и 3.8 видно, что время вычис­ ления слагаемых методом -прямого .перебора состояний путей вы-

52

1 Номер /t-го со- | I стояния счетчика |

							Т а б л и ц а	3.5
	Состояние
	разрядов		Множество
	счетчика				Множество	б элементов
			путей	/ пЛ на			Слагаемые p (/nfc)	суммьэ
			ft-м	шагЬ	путей	из 1п к	Р(£ " ) на fc-м шаге
1	2	3	4

2

0

0

0

I

/ . . 2= { |Х 4>

6 = { Ь |,5 ,

^4.5, 64,2}

P (^l,2) = P l,S P 4 ‘.5P4.2

3

0

0

1

0

Л

, з =

ы

б ={1*1,5,

65,2}

Р ( Л , з ) = Р 1,5Р5,2

4

0

0

1

1

/ 2.4=

{(J.3, Р4>

б =

{6|,5,

^5.2,

1*4,5,

Ь4,2}

Р { Ь л )

= Р1,5Р5,2р4.5р4,Г

5

0

1

0

0

. /|.5 = { Ц 2 }

б =

{1*1,4,

&4.S,

Ь5.2}

Р(Л ,5)=Р1,4Р4,5Р5,2

6

0

1

0

1

h . 6=

{ H

2,

Ц4}

б =

{6l,4, 64,5, 65,2, б |,6>64,2}

Р(/2,б) =

=

Pl.4P4.5P5,2Pl.5p4,2

7

0

1

1

0

/ 2.7=

{Ц2>Мз}

б =

{1*1,4, б4,5, 65,2, &l,s}

P ( ‘l2.7)=Pl,4P4,5P5.2Pl.S

8

0

1

1

I

h , 8=

{

l l 2,

Мз,

б =

{1*1,4, 1*4.5, 1*5,2, 1*1,5, 1*4,2}

P ( h , B) =

=

Pl.4p4,5PS,2Pl.5P4.2

9

1

0

0

0

Л . в =

{Mi}

б =

{1*1,4, ^ .г }

P (/l.9) = P l.4P 4,2

ю .

I

0

0

1

^2,10={|А |,

б =

{1*1,4, 1*4.2, &1,5> 64,5}

p (7 2,lo) =Pl,4P4.2Pl.sP4.5-

.11

1

0

1

0

К2.11 = {Ц ьЦ з}

б =

{1*1,4, 1*4.2, Ь 1,5/ 1*5,2}

P ( / 2,ll) =Pl.4P4.2Pl.sP6,fc

12

1

0

1

1

/ 3.12—

{Мь Из

б =

{1*1,4, 1*4,2, 1*1,5, 65,2,

1*4,5}

р(/з,12) =

Ц4>

=

Pl.4P4,2pl,5P5.2P4.6

13

1

1

0

0

^2,13={И ь М2 }

6 =

{1*1,4, 1*4.2, 1*4,5, 65.2}

P(l2,13) =Pl,4P4,2P4.5p5,2-

14

1

I

0

1

/з ,1 4 =

{й!> М2

б =

{1*1,4, 1*4,2, 1*4,5, 1*5,2,1*1,5}

P (/3 ,U ) =

М4>

1

=

Pl.4P4,2P4,5pS.2Pl.S

15

1

1

I

0

h . i 5

=

6 =

{1*1,4, 1*4,2, 64.51 6 б,2, 61,5}

Р(1з,15) =

=

{Мь М2, Мз}

=

Pl,4P4.2P4,sP5,2pl,5

16

1

1

1

1

14,16 =

б =

{61,4, 64,2, 64,5, 65,2, 61.5}

Р ( / 4,1б) =

=

{Ml, М2, Мэ,

=

P l,4P 4.2P4.5Ps.2Pl,S

М4>

р ( £ 1 ) = р ( / 1 > 2 ) + р ( / 1 . з ) + Р ( / д , 5) + Р ( / 1 . 9 ) = 3 - 0 7 8 ;

р ( Е 2) =

р ( / 2 ,.») +

Р ( /2 . б) +

Р (72 . 7) +

Р (72 ,1 о) +

Р (; 2 , 11) +

Р (72 .1 з) =

=

3 ,8 7 0 9 9

;

р ( £ 3 )

=

р ( / 3

8) +

р ( / 3(12) +

р ( / 3

14) +

p ( / 3 il5 ) = 2 , 3 6 1 9 6 ;

р

( £ 4) =

р

( / 4 ( j 6) =

0 159049

;

р

( £ )

=

р

( £ 1) —

Р (Я 2) +

Р (£3) —

— р ( £ 4) =

0,97848

5&

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

Область практического приме­ нения метода перебора состояний путей системы связи в основномсовпадает с областью применения метода перебора состояний ее элементов. Он применяется так­ же и для практического вычисле­ ния р{Е) при большом числе эле­ ментов, но небольшом числе пу­ тей в каждой ДС.

Рис. 3.7. Алгоритм вычисления вероятности исправности двухпо­ люсной сети методом прямого пе­ ребора состояний путей с исклю­ чением. их корреляции с помо­ щью преобразований Булевой

.алгебры

Рис. 3.8. Зависимость вре­ мени анализа состояний пу­ тей при использовании ме­ тода прямого перебора со­ стояний путей

3.4.Методы с применением теоремы разложения

На основе теоремы (разложения [8] построен ряд методов вы­ числения показателей надежности сложных систем, в том числе

.систем связи. Она читается »в принятых «в данной книге обозна­ чениях следующим образом '[18]: функция надежности р(Е) си­ стемы, состоящей из N ненадежных элементов, «равна произведе­ нию «вероятности исправного состояния i-то элемента на функцию надежности системы из N—1 элементов при условии, что ий эле-

мент замкнут накоротко, плюс произведение вероятности отказа i-го элемента на функцию надежности системы из N—\ элементов при условии, что i-й элемент разомкнут.

Очевидно, что к преобразованнойсистеме из N—1 элементов: вновь может .быть применена теорема разложения, затем к си­ стеме из N—2 элементов и т. д. Тогда имеет место формула пол­ ной вероятности

p(E)=%P(N", i)p{E').	(3.16)
i=0
В этой формуле N" — число элементов ДС,	не позволяющих,

производить .вычисления по формулам последовательно-параллель­ ного соединения [N"<N) ; P(N", i) — вероятность состояния сово­ купности N" элементов -при одновременном отказе i=0, ..., N" и исправности N"—i элементов; р(Е' ) — условная вероятность со­ хранения связности ДС .при размыкании i и замыкании накоротко- N"—i элементов, определяемая'по формулам последовательно-па­ раллельного соединения.

Наиболее типичный пример применения теоремы разложения длр расчета надежности системы связи приведен на рис. 3.9. По­ скольку исходный граф может быть преобразован в эквивалент-

Рис. 3.9. Пример применения теоремы разложения для ра­ счета надежности си стемы связи:

а) исходная струк­ тура; б) ребро b1,2

замкнуто накоротко; в) ребро Ьи2 раэомк нуто

ный путем -замены его вершин ребрами и ребер вершинами .[14],. теорема разложения применима для оценки надежности систем связи, состоящей из абсолютно -надежных ребер и ненадежных, вершин.

В (3.16) вероятности P(N"t i) определяются по формулам,,

аналогичным (3.2)		и (3.4) для случаев одинаковых и различных
вероятностей р(э). Отказ ((размыкание) i и исправность (замыка­
ние, накоротко)	N"—i |различных совокупностей элементов приво­
дит, очевидно,	к	различным последствиям, поэтому вероятность-
O s (£') s^.l. Она		вычисляется после анализа состояния ДС D'h,

в’ котором она оказалась после замыкания N"—i и размыкания Г элементов. Общий вйд преобразованной сети показан на рис. 3.10,. а выражение вероятности р (E'h) ее иоправности на k-u шаге

^(^)=п(1-п Т 1-	П рМI)-	(3-17>
f = 4 V = I L	J )

Здесь n=N"—i + 1.

55

Алгоритм вычисления р(Е) с использованием теоремы-разло­ жения .состоит из трех частей: формирования множества путей М

с разделением его па подмножества М и М; .выделения из струк­ туры ДС таких элементов, которые не позволяют для расчета р(Е') применить формулу последовательно-параллельного соеди­ нения элементов (3.17); вычисления вероятности р(Е) за 2*" шагов.

Рис. 3.10. Структура двухполюсной систе­ мы связи на очеред­ ном шаге расчета ее надежности методом с применением теоре­ мы разложения

Использование теоремы разложения для расчета надежности систем связи ограничивается для общего .случая неоколькими фак­ торами, которые вытекают, .во-первых, из условия формулирова­ ния самой теоремы и, во-вторых, из сложности программной реа-

.лизации алгоритма преобразования структур D'h.

Теорема разложения сформулирована .при условиях абсолютно

.надежных вершин и неориентированных ребер графа. В сетях и системах это -не всегда выполняется. Так, если и ребра, -и верши­ ны неабсолютно надежны, то неизвестно, какой надежностью об­ ладает эквивалентная -вершина на рис. 3.9,6. Если ребро Ъ1(2 на рис. 3.9,а — ориентированное, то общий результат, полученный на рис. 3.9,6 и в, будет неправильным, так как при ориентированном ребре b1,2 надежность мостовой схемы ниже. Возможность исполь­ зования теоремы разложения для таких общих случаев доказана в [18], но требуется выполнить -сложные преобразования исходно­ го графа сети. В сложных сетях с высокой размерностью, что •■обычно имеет место на практике, число элементов N" достаточно велико. Поэтому организация перебора большого (несколько де­ сятков) числа элементов равносильна методу прямого перебора ■состояний элементов сети.

Кро-ме того, в данном случае автоматическое формирование ■состояний схем для расчета по (3.17) представляет достаточно •сложную задачу, алгоритмическое и программное решения кото­ рой сводят к минимуму преимущества сокращения числа перебо­ ров. Поэтому -область применения теоремы разложения ограничи­ вается структурами специального клаоса, как, например, лестнич­ ная схема или «.решетка»—схема, элементы которой представляют •собой .мостовые схемы, и некоторыми другими, заранее заданны­ ми -структурами.

Исследовалась сложность алгоритма .вычисления р(Е) двух классов .структур. Первый из них — лестничные схемы с произ­ вольным числом звеньев (рис. 3.11). Алгоритм -построен таким

56

образом, что поперечные ребра могут задаваться ,не обязательно между каждой парой .вершин, а число вершин в .продольных вет­ вях может отличаться одно от другого. Важно, чтобы поперечные ребра не перекрещивались «между собой. Алгоритм вычисления вероятности содержит блок 'формирования множества Э" (попе­ речные ребра), блок формирования двоичных чисел и блок состав­ ления схемы .расчета в -соответствии с состоянием поперечных ре­ бер и расчета вероятности р(Е'к). Длина программы составляет 47 операторов языка ФОРТРАН.

Рис. 3.11. Двухполюс­ ная сеть связи с лест­ ничной структурой с произвольным числом звеньев

Второй алгоритм предназначен для оценки более широкого класса структур. Это ДС -вторичной системы телефонной связи, множество -путей которых состоит только из не пересекающих­

ся между собой путей (М = 0 ) или же оба подмножества М и

М — непустые, но заранее известно, что число не пересекающихся путей 3, а Я^2. Однако оценка надежности проводилась с учетом -возможного совпадения трасс трактов магистральных ка­ налов по сети ЕАСС страны. Число блоков алгоритма остается прежним, но программная реализация блоковформирования мно­ жества элементов Э" и составления схем D \ для расчета резко усложняется. Длина -программы за счет усложнения этих блоков по сравнению с предыдущей возрастает в 7 -рае.

На рис. 3.12 изображены зависимости -времени анализа состоя­ ний и составления схем для расчета по (3.16) от размерности се­ ти-: кривая 1 — для лестничной схемы, кривая 2 получена^ по результатам работы второго алгоритма, который изложен в гл. 6. Сравнение кривой 1 с изображенными на рис. 3.5 и 3.8 показывает, что время вы­ числения р{Е) с применением

Рис. 3.12. Зависимость времени ана­ лиза состояний двухполюсной сети при использовании теоремы разло­ жения

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

57

3.5.Методы с применением преобразований Булевой алгебры

Изложенные в «предыдущих разделах методы и алгоритмы вы­ числения вероятностей р(Е) основаны .на организации полного или сокращенного перебора состояний элементов или путей системы. На каждом шаге алгоритмов проводятся операции над числами (сложение, умножение и реже деление). Вычисление р(Е) логи­ ческими методами производится также по шагам, но их число равно числу путей. Отличие логических методов от изложенных в том, что, во-первых, исключается принцип перебора и, 1во-вторых, на каждом шаге проводятся операции не с числами, а с Булевыми переменными {’13, 34]. На последнем шаге заканчивается состав­ ление выражения р{Е) через исходные вероятности исправности элементов системы.

Сущность логических методов заключается в назначении соот­ ветствия между численными значениями вероятностей состояний элементов p(at), q{9i) = \—р(э*) и Булевыми переменными БПи принимающими значение «нуль» или «единица». Обозначим БВ {Е) выражение функции р{Е) через Булевы «переменные. Оно опреде­ ляется простой формулой параллельного соединения путей ДС

(3.18)

k=\

Здесь БВ (ек) — выражение функции р{ек) через переменные ■БП{. Формула (3.18) .при ее развертывании содержит 2h слагае­ мых,-которые в дальнейшем обозначаются БС{, £= 1, ..., N(BB).

Слагаемые 2>С, в (3.18) вычисляются с применением свойства логического произведения

БП„БПу БПч... = БП„.

(3.19)

Для упрощения преобразований по (3.18) и организации обра­ щений к оперативной памяти ЭВМ при расчетах после формиро­ вания множества путей М «производится перенумерация элементов рассматриваемой ДС порядковыми числами 1, 2, ..., N. Алгоритм вычисления р{Е) «при представлении ДС множеством М имеет h шагов. На первом шаге согласно (3.18)

БВ{Е)х = БВ(ех) = БСх.

Шаг k, 6 ^ 2 , выполняется в два этапа. На "первом этапе произ­ водится логическое умножение каждого слагаемого выражения БВ{Е) h-i на БВ(еь) с учетом (3.19). Умножение, как следует из (3.18), ,(3.19), заключается в дописывании к выражению £ Д (£ )Л_, со знаком плюс слагаемого БВ(ек), а таадке;2АГ.(БВ)л^1 таких сла­ гаемых BCV, которые представляют собой логическое произведе­ ние каждого из слагаемых BCi<=EB(E)h-\ на БВ{ек). Указатель знака a(£Cv) «слагаемых БСЧопределяется по правилу

a(BC4)=pL(BCt)® 1,

N(BB)^X; v * N (БВ)к- х+ Г/.-.., 2 N(BB)k_v

58

Если a£Cv =0, то	слагаемое BCV имеет	знак	«минус»;
N { B B ) — число слагаемых © выражении БВ на		(k—1)-м шаге.
На втором этапе k-ro	шага в полученном выражении		БВ(Е)ь.

проверяется существование одинаковых слагаемых BCit БС„, i= =•1, N(5В) Л, с -противоположными знаками. Поскольку одина­ ковые слагаемые соответствуют равным числам, они из выраже­ ния БВ (E)k исключаются.

После выполнения h шагов вероятность

N (БВ)

р { Е ) = у, a i B C j p i E C j ,

1=1

где p(BCi)— число, представляющее собой произведение исход­ ных вероятностей иоправности элементов, входящих в слагаемое

р{БСг).

Пример. Требуется при абсолютно	надежных узлах и р ц = 0,9 вычислить-
вероятность р ( Е ) исправности ДС D 3,	множество путей которой приведено в

табл. 3.1. Результаты каждого из четырех шагов алгоритма, а также оконча­ тельный результат записаны в табл. 3.6.

Б С \ = Б В [ е х)

Б С 2= Б В (е2) ДСд=Б С \Б С 2

Б С 4= Б В ( е 3)

£С5=БС|£С<

БСц=Б С 2Б С \

БС 7= Б С 3Б С 4

БС в = Б В ( е 4)

БС $ = Б С \Б С 3

БС \3= Б С 2Б С 3

БС ц = Б С 3Б С 3

БС is—Б С 4Б С 3

ВС J3= Б С $ Б С 3

БС ц ==~ Б С 3Б С 3

БС \$ — Б С 7Б С 3

						Таблица 3.6
	Знак					Результаты второй
	слага­
						части ft-го. шага
	емого
	а(БСу)					алгоритма.
	*1,4*4,2
	*1,4 *4,5		*5,2			Одинаковых ела*
	*1.4**4,2 *4,5 *5,2					гаемых нет______
	*5,2 *1,5
	* 1,4 *4.2		*5,2	*1.6
	*1.4	*4.5	*5.2	*1.6
	*1.4 *4.2		*4,5	*6.2	*1.5
	J.2 *4.5		*1,5			£С7= —Б С ц ,
	*1,4	*4,2 *4,5 *1.5				Б С ц = — Б С к
						Слагаемые Б С Ь
	*1.4	*4,2	*4,5	*6,2	*1,5
	*1,4	*4,2 *4,6		*5,2 *1,5		Б С ц , Б С ц , Б С 15.
						из Б В ( Е ) 4
	*4.2	*4,5	*6,2	*1.5
	*1,4	*4,2	*4.5	*5,2	*1,5	исключаются
	*1.4 *4,2		*4,6	*5.2	*1.5
	*1,4	*4,2 *4,5 *6,2 *1.6

р(Е)= J a (ECV) р (£CV) = 0,97848

_•

Схема алгоритма изображена на рис. 3.13. Длина программы составляет 72 оператора языка ФОРТРАН без учета формирова­ ния множества путей М.

Достоинством логических методов и реализующих их алгоритмов является их простота. Однако число слагаемых выражения БВ(Е) в сложных системах достигает больших величин, что тре­ бует значительных ресурсов оперативной памяти. На рис. 3.14 по­ казаны полученные экспериментально усредненные зависимости требующегося числа ячеек ОЗУ ЭВМ для запоминания слагаемых выражения БВ(Е) (кривая /). Зависимость времени вычисления р(Е) от числа путей ДС изображена на рис. 3.15. Сравнение данной зависимости с полученными ранее показывает более ши­ рокие возможности логических методов.

Рис. 3.13. Алгоритм вычисления вероятности исправности двухпо­ люсной сети логическим методом

Рис. 3.14. Зависимость требу­ емого числа ячеек оператив­ ной памяти ЭВМ для работы программы расчета логичес­ ким методом

Рис. 3.15. Зависимость време­ ни вычисления вероятности на ЭВМ БЭОМ-6 логическим методом

Некоторое дополнительное	снижение времени	и размеров
ОЗУ (кривая 2 на рис. 3.14)	достигается благодаря использова­
нию еще одного свойства Булевой алтебры:
£ Я ,Щ = 0.		(3.20)

Использование свойства возможно 1После вынесения за скобки об­ щих множителей -перед организацией умножения БВ (Е) h-iBB (еп) •

60