Метод объединения связных подграфов или сечений с поглощением

Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

7.34M

Category:

internet

Сети связи. Анализ и синтез структур на основе метода объединения связных подграфов или сечений с поглощением

1. Сети связи

LOGO
Тема № 1:
“ Add your company slogan ”
Анализ и синтез
современных сетей связи по
показателям структурной
устойчивости
Занятие № 9:
Анализ и синтез структур на основе метода
объединения связных подграфов или сечений с
поглощением
Вид занятия: практическое

2. Цели занятия

2
1. Изучение метода объединения связных подграфов или сечений с
поглощением (ПК-11, ПК-16).
2. Изучение синтеза структуры сети методом объединения связных
подграфов или сечений с поглощением (ПК-11, ПК-20).
3. Способствование формированию способности учитывать в своей
профессиональной деятельности современные тенденции развития
инфокоммуникационных технологий (ОК-4).
4. Способствование формированию способности находить и
обосновывать рациональные организационно-технические решения по
применению систем передачи, обеспечивающие требуемое качество
обслуживания абонентов сетей специальной связи (ОК-4).

3. Межпредметные связи

Основа
Применение
Основы построения
инфокоммуникационных
систем и сетей
Теория телетрафика
Средства и комплексы сетей
связи
Сети связи и системы
коммутации
Сигнализация в сетях связи
3
Сети
связи
Дипломное
проектирование
Учебнопроизводственная
практика

4. Литература

4
1. Филин Б. П. Методы анализа структурной
надежности сетей связи. – М. : Радио и связь, 1988. –
208 с.
2. Кузнецов В. В. О некоторых методах оценки и
прогнозирования структурной надежности
мультисервисных сетей связи / В. В. Кузнецов, С. М.
Чудинов, Е. Г. Жиляков // С. 79–88.
3. Надежность и живучесть систем связи / Б. Я. Дуд
ник, В. Ф. Овчарснко, В. К.Орлов и др. ; Под ред.
Б. Я. Дудинка. – М. : Радио и связь, 1984. – 216 с.

5. Учебные вопросы

1
Метод объединения связных подграфов или
сечений с поглощением
2
Синтез структуры сети методом
объединения связных подграфов или
сечений с поглощением
5

6. Метод объединения связных подграфов или сечений с поглощением

1
Метод объединения связных подграфов
6
или сечений с поглощением
Метод объединения связных подграфов с поглощением
Событие связности
двухполюсной сети
Событие связности
многополюсной сети
,,
• заключается в наличии хотя бы одной связной простой цепи (маршрута,
пути) между заданной парой узлов
• заключается в в наличии хотя бы одного остового дерева .
• событие связности i-го подграфа
• объединение событий связности подграфов от первого до -го
включительно
• вероятность события
Операция символьного
умножения ""
•.
(19)
• Она подразумевает, что элемент , повторяющийся в правом множителе
исключаются из рассмотрения в данном множителе, или, что тоже
самое, заменяются полным множеством.
Вероятность связности
графа рассчитывается
итерационной
процедурой
•,
•,
•,
(22)
(23)
(24)

7. Метод объединения связных подграфов или сечений с поглощением

1
Метод объединения связных подграфов
7
или сечений с поглощением
Пересечение
независимых событий:
•,
(26)
Пересечение событий
на самих себя:
•,
(27)
•,
(28)
•,
(29)
Пересечение
зависимых событий:
•,
(30)
•,
(31)
•,
(32)
•,
(33)
•,
(34)
•,
(35)
Пересечение сложных зависимых
событий:
•,
•,
•,
•,
•,
•,
•.
•.
(36)
(37)
(38)
(39)
(40)
(41)
(42)
(43)

8. Метод объединения связных подграфов или сечений с поглощением

Метод объединения связных подграфов
8
или сечений с поглощением
1
Задача 1.
• Граф исследуемой сети связи приведен на рисунке. Все узлы сети
являются абсолютно надежными, а вероятность исправности любой линий
связи равна 0,9. Определить надежность сети связи в направлении 1–5 и в
целом методом объединения связных подграфов с поглощением.
•,.
Дано:
Найти:
•,.
Простые цепи (пути)
•,,
,.
Итеративная процедура расчета вероятности связности
•,
•,
•,
•.

9. Метод объединения связных подграфов или сечений с поглощением

Метод объединения связных подграфов
9
или сечений с поглощением
1
Остовые деревья
,,,
,,,
,,,
,.
Итеративная процедура расчета вероятности связности
,
,
,
.
.

10. Метод объединения связных подграфов или сечений с поглощением

1
Метод объединения связных подграфов
10
или сечений с поглощением
Остовые деревья
•,,,
•,,,
•,,,
•,.
Итеративная процедура расчета вероятности связности
•.
•.
•.

11. Метод объединения связных подграфов или сечений с поглощением

1
Метод объединения связных подграфов
11
или сечений с поглощением
Остовые деревья
•,,,
•,,,
•,,,
•,.
Итеративная процедура расчета вероятности связности
•.
•.
•.

12. Метод объединения связных подграфов или сечений с поглощением

1
Метод объединения связных подграфов
12
или сечений с поглощением
Метод объединения сечений с поглощением
Событие несвязности
двухполюсной и
многополюсной сетей
,,
• заключается в наличии хотя бы одного сечения или со всеми
неисправными элементами, с той оговоркой, что сечения и в общем
случае могут быть различными
• событие несвязности i-го сечения
• объединение событий несвязности сечений от первого до -го
включительно
• вероятность события
Операция символьного
умножения ""
•.
(19)
• Она подразумевает, что элемент , повторяющийся в правом множителе
исключаются из рассмотрения в данном множителе, или, что тоже
самое, заменяются полным множеством.
Вероятность связности
графа рассчитывается
итерационной
процедурой
•,
•,
•,
(44)
(45)
(46)

13. Метод объединения связных подграфов или сечений с поглощением

Метод объединения связных подграфов
13
или сечений с поглощением
1
Задача 2.
• Граф исследуемой сети связи приведен на рисунке. Все узлы сети
являются абсолютно надежными, а вероятность исправности любой линий
связи равна 0,9. Определить надежность сети связи в направлении 1–5 и в
целом методом объединения сечений с поглощением.
•,.
Дано:
Найти:
•,.
Сечения в направлении 1–5
•,,,,
•,,.
Итеративная процедура расчета вероятности связности
•,
•,
•,

14. Метод объединения связных подграфов или сечений с поглощением

Метод объединения связных подграфов
14
или сечений с поглощением
1
Сечения в направлении 1–5
•,,,,
•,,.
Итеративная процедура расчета вероятности связности
•,
•,
•,
•,
•.

15. Метод объединения связных подграфов или сечений с поглощением

Метод объединения связных подграфов
15
или сечений с поглощением
1
Сечения для сети в целом
•,,,,,,,,,,.
Итеративная процедура расчета вероятности связности
,
,
,
,
,
,
,

16. Метод объединения связных подграфов или сечений с поглощением

Метод объединения связных подграфов
16
или сечений с поглощением
1
Сечения для сети в целом
•,,,,,,
•,,,,.
Итеративная процедура расчета вероятности связности
•,
•,
•,
•,
•.

17. Метод объединения связных подграфов или сечений с поглощением

Метод объединения связных подграфов
17
или сечений с поглощением
1
Оценка надежности сети на основе поглощения
• Проектировщикам сети связи или организациям, осуществляющим эксплуатацию
сетей, необходимо лишь убедиться в том, что надежность сети, с одной стороны,
не ниже заданной и, с другой стороны, не имеет экономически необоснованного
запаса надежности, т. е. гарантировать, что истинное значение вероятности
связности находится в некоторых пределах
,
,
• Метод объединения связных подграфов с поглощением - добавление каждого
нового связного подграфа не может привести к снижению оценки надежности сети
• Метод объединения сечений с поглощением - увеличение числа учитываемых
сечений может привести лишь к снижению надежности
Точность оценки
Условие прекращения расчетов
Оценка надежности
•.
Решение о рассмотрении на следующем шаге очередного связного подграфа или сечения
• целесообразно принимать по критерию большего абсолютного приращения надежности
по соответствующему параметру ( или ).

18. Метод объединения связных подграфов или сечений с поглощением

1
Метод объединения связных подграфов
18
или сечений с поглощением
Задача 3.
• Граф исследуемой сети связи приведен на рисунке. Все узлы сети являются абсолютно надежными,
а вероятность исправности любой линий связи равна 0,9. Оценить надежность сети связи в
направлении 1–5 и в целом, если допустимое отклонение от истинного значения не должна
превышать 0,01.
Дано: • , , .
Найти: • , .
Номер
итерации
1
2
3
4
5
Номер
связного
подграфа,
1
2
3
3
4
Номер
сечения,
0,729
0,854
0,866
0,866
0,872
0,729
0,125
0,012
0,012
0,006
1
1
1
2
2
0,1
0,1
0,1
0,109
0,109
0,1
0,1
0,1
0,009
0,009
0,882
0,171
0,046
0,034
0,025
0,019
Следующий
объект
подграф
подграф
сечение
подграф

19. Метод объединения связных подграфов или сечений с поглощением

1
Номер
Номер
итерации
итерации
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
Метод объединения связных подграфов
19
или сечений с поглощением
Номер
связного
подграфа,
1
1
2
2
2
3
3
4
4
5
5
5
5
5
5
6
6
7
7
8
8
9
9
0,59
0,59
0,65
0,65
0,65
0,709
0,709
0,768
0,768
0,774
0,774
0,774
0,774
0,774
0,774
0,779
0,779
0,785
0,785
0,844
0,844
0,85
0,85
0,59
0,59
0,059
0,059
0,059
0,059
0,059
0,006
0,006
0,006
0,006
0,006
0,006
0,006
0,006
0,059
0,059
0,006
0,006
Номер
сечения,
1
1
1
2
2
2
2
2
3
3
4
4
5
5
5
5
5
5
5
0,1
0,1
0,1
0,109
0,109
0,109
0,109
0,109
0,118
0,118
0,126
0,126
0,134
0,134
0,135
0,135
0,135
0,135
0,135
0,135
0,1
0,1
0,1
0,009
0,009
0,009
0,009
0,009
0,009
0,008
0,008
0,008
0,001
0,001
0,001
0,001
0,001
0,001
0,858
0,858
0,31
0,31
0,25
0,25
0,241
0,241
0,182
0,182
0,123
0,123
0,117
0,117
0,109
0,109
0,101
0,101
0,093
0,093
0,092
0,092
0,086
0,086
0,08
0,08
0,021
0,021
0,015
0,015
Следующий
Следующий
объект
объект
подграф
подграф
сечение
сечение
подграф
подграф
подграф
подграф
сечение
сечение
сечение
сечение
сечение
подграф
подграф
подграф
подграф
подграф

20. Выводы

1
Выводы
20
1. Событие связности двухполюсной сети заключается в наличии хотя бы
одной связной простой цепи (маршрута, пути) между заданной парой узлов,
а событие связности многополюсной сети – в наличии хотя бы одного
остового дерева.
2. Как для двухполюсной, так и для многополюсной сети оно
заключается в наличии хотя бы одного сечения или со всеми
неисправными элементами, с той оговоркой, что сечения и в общем
случае могут быть различными.
3. При проектировании реальных сетей связи или оценке действующих
сетей обычно отсутствует необходимость точного расчета надежности сети,
так как исходные данные по надежности элементов сети задаются или
получаются экспериментальным путем, с некоторой конечной точностью.

21. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Синтез структуры сети методом объединения
связных подграфов или сечений с поглощением
Общая постановка
задачи для синтеза
связных графов
21
• где – вероятность связности структуры сети, зависящая как от набора
элементов сети , так и их вероятностей исправной работы .
Решение задачи
• используется либо метод полного перебора, либо метод последовательного
добавления или удаления ребер графа
Суть синтеза
• заключается в последовательном добавлении по одному элементу в
структуру сети связи на каждой итерации, что приводит к появлению новых
связных подграфов.
С точки зрения
связных подграфов
• добавление ребра приводит к увеличению их числа (по крайней мере, их
количество не уменьшается), но влияет на уже рассмотренные связные
подграфы.
С позиции сечений
• может увеличиться и число сечений и могут модифицироваться ранее
исследованные.

22. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Задача 4.
• Граф исследуемой сети связи приведен на рисунке. Все узлы сети
являются абсолютно надежными, а вероятность исправности любой линий
связи равна 0,9. Синтезировать на основе данной сети структуру путем
добавления одного ребра с вероятностью исправной работы 0,9 между
узлами 1 и 3 или 2 и 5 по критерию максимальной надежности в
направлении 1–5 и в целом.
•,.
Дано:
Найти:
•,.
Дополнительные простые цепи
•,,.
Продолжение итеративной процедуры расчета вероятности
22

23. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Дополнительные простые цепи
•,,.
Продолжение итеративной процедуры расчета вероятности
23

24. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Дополнительная простую цепь
•.
Продолжение итеративной процедуры расчета вероятности
Поскольку , то наилучшим вариантом оказывается сеть,
дополненная ребром 1–3
24

25. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Дополнительный набор сечений
•,,,,,,,,,,,.
Продолжение итеративной процедуры расчета вероятности связности
•,
•,
•,
•,
•,
•,
25

26. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Дополнительный набор сечений
•,,,,,,,,,,,.
Продолжение итеративной процедуры расчета вероятности связности
•,
•,
•,
26

27. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Дополнительный набор сечений
•,,,,,,,,,,,.
Продолжение итеративной процедуры расчета вероятности связности
•,
•,
27

28. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Дополнительный набор сечений
•,,,,,,,,,,,.
Продолжение итеративной процедуры расчета вероятности связности
•,
•.
28

29. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Синтез структуры сети методом объединения
связных подграфов или сечений с поглощением
Набор сечений
•,,,,,,,,,,.
Итеративная процедура расчета вероятности связности
,
,
,
,
,
,
29

30. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

31. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Синтез структуры сети методом объединения
связных подграфов или сечений с поглощением
Набор сечений
•,,,,,,,,,,.
Итеративная процедура расчета вероятности связности
,
.
Поскольку , то наилучшим вариантом оказывается сеть,
дополненная ребром 1–3.
31

32. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Задача 5.
• Граф исследуемой сети связи приведен на рисунке 19. Все узлы сети
являются абсолютно надежными, а вероятность исправности любой линий
связи равна 0,9. Синтезировать на основе данной сети структуру путем
удаления одного ребра между узлами 3 и 6 или 4 и 5 по критерию
максимальной надежности в направлении 1–5 и в целом.
•,.
Дано:
Найти:
•,.
Итеративная процедура расчета вероятности связности
•,
•,
•,
•.
32

33. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Итеративная процедура расчета вероятности связности
•,
•,
•,
•.
Поскольку , то наилучшим вариантом оказывается сеть с удаленным
ребром 3–6
33

34. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Синтез структуры сети методом объединения
связных подграфов или сечений с поглощением
Итеративная процедура расчета вероятности связности
,
,
,
,
,
,
,
,
34

35. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Синтез структуры сети методом объединения
связных подграфов или сечений с поглощением
Итеративная процедура расчета вероятности связности
,
,
,
.
35

36. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Синтез структуры сети методом объединения
связных подграфов или сечений с поглощением
Итеративная процедура расчета вероятности связности
,
,
,
,
,
,
,
,
36

37. Синтез структуры сети методом объединения связных подграфов или сечений с поглощением

2
Синтез структуры сети методом объединения
связных подграфов или сечений с поглощением
Итеративная процедура расчета вероятности связности
,
,
,
.
Поскольку , то наилучшим вариантом оказывается сеть с удаленным
ребром 3–6
37

38. Выводы

2
Выводы
38
1. Вследствие того, что в данном методе используется последовательный перебор всех
связных подграфов или сечений, а добавление или удаление того или иного элемента сети
может приводить к возникновению или исключению связных подграфов или сечений, то для
синтеза структур оказывается возможным использовать метод последовательного добавления
или удаления ребер графа.
2. Суть синтеза заключается в последовательном добавлении по одному элементу в
структуру сети связи на каждой итерации, что приводит к появлению новых связных
подграфов.
3. При выборе метода анализа целесообразно сопоставлять число вновь формируемых
связных подграфов и общее количество сечений в результирующем графе.

39. Литература

39
1. Филин Б. П. Методы анализа структурной
надежности сетей связи. – М. : Радио и связь, 1988. –
208 с.
2. Кузнецов В. В. О некоторых методах оценки и
прогнозирования структурной надежности
мультисервисных сетей связи / В. В. Кузнецов, С. М.
Чудинов, Е. Г. Жиляков // С. 79–88.
3. Надежность и живучесть систем связи / Б. Я. Дуд
ник, В. Ф. Овчарснко, В. К.Орлов и др. ; Под ред.
Б. Я. Дудинка. – М. : Радио и связь, 1984. – 216 с.

40. Сети связи

41. Цели занятия

41
1. Изучение метода объединения связных подграфов или сечений с
поглощением (ПК-11, ПК-16).
2. Изучение синтеза структуры сети методом объединения связных
подграфов или сечений с поглощением (ПК-11, ПК-20).
3. Способствование формированию способности учитывать в своей
профессиональной деятельности современные тенденции развития
инфокоммуникационных технологий (ОК-4).
4. Способствование формированию способности находить и
обосновывать рациональные организационно-технические решения по
применению систем передачи, обеспечивающие требуемое качество
обслуживания абонентов сетей специальной связи (ОК-4).

English Русский Rules