|
Контрольная: Основы построения телекоммуникационных систем
Контрольная: Основы построения телекоммуникационных систем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ
КАФЕДРА «СЕТИ СВЯЗИ»
контрольная работа
по дисциплине «Основы построения телекоммуникационных сетей»
Выполнил
Принял
ст. гр. ИСС-01-1
Захарцов А.А.
______________
Харьков 2003
Соответственно номеру зачетной книжки выберем Кировоградскую область, т.к.
она соответствует №17, а также запомним p=0,817.
Выберем десять городов, соответствующие нашей области:
- Кировоград
- Бобринец
- Долинская
- Новоукраинка
-
Новомиргород
- Каменка
- Знаменка
- Александрия
-
Чигирин
- Кривой рог
1 СИНТЕЗ ТОПОЛОГИИ СЕТИ ЭЛЕКТРОСВЯЗИ МЕТОДОМ М - СТРУКТУР
Составим матрицу расстояний  для нашего графа:
Рисунок 1.1 – Граф сети
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 1 | 0 | 79 | 60 | 71 | 57 | 68 | 39 | 61 | 102 | 120 | 2 | 79 | 0 | 43 | 64 | 0 | 0 | 94 | 154 | 0 | 142 | 3 | 60 | 43 | 0 | 0 | 0 | 0 | 51 | 0 | 0 | 58 | 4 | 71 | 64 | 0 | 0 | 51 | 0 | 0 | 0 | 0 | 0 | 5 | 57 | 0 | 0 | 51 | 0 | 69 | 101 | 0 | 103 | 0 | 6 | 68 | 0 | 0 | 0 | 69 | 0 | 60 | 0 | 48 | 0 | 7 | 39 | 94 | 51 | 0 | 101 | 60 | 0 | 35 | 87 | 0 | 8 | 61 | 154 | 0 | 0 | 0 | 0 | 35 | 0 | 91 | 150 | 9 | 102 | 0 | 0 | 0 | 103 | 48 | 87 | 91 | 0 | 0 | 10 | 120 | 142 | 58 | 0 | 0 | 0 | 0 | 150 | 0 | 0 |
В соответствии с алгоритмом Прима сначала выписывается первая строка матрицы 
без первого столбца, что соответствует организации связи от первой вершины и
соответствует организации связи от первой вершины (центрального пункта) к
остальным  - м (
):
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | 79 | 60 | 71 | 57 | 68 | 39 | 61 | 102 | 120 |
Выбираем в этой строке минимальный элемент 
. Далее вычеркиваем соответствующий ему 7-й столбец матрицы 
и, двигаясь по 7-й строке, сравнивается значение приведенных в ней элементов с
их значениями в первой строке без первого и 7-го столбцов. Если значение
элемента 7- й строки в соответствующем столбце оказывается меньше значения,
указанного в первой строке, то эти значения меняются местами. Если наименьшим
будет значение в первой строке, то замена не производится. Таким образом
формируется следующая строка:
2 | 3 | 4 | 5 | 6 | 8 | 9 | 10 | | 79 | 51 (7) | 71 | 57 | 60 (7) | 35 (7) | 87 (7) | 120 |
При этом цифрой 7 в скобках обозначены те значения длин, которые взяты из
седьмой строки.
Вновь выбираем минимальный элемент строки 
. Действуя аналогично предыдущему, получаем новую строку:
2 | 3 | 4 | 5 | 6 | 9 | 10 | | 79 | 51 (7) | 71 | 57 | 60 (7) | 87 (7) | 120 |
Выбираем минимальный элемент строки  . Ниже показан дальнейший процесс поиска:
2 | 4 | 5 | 6 | 9 | 10 | 43 (3) | 71 | 57 | 60 (7) | 87 (7) | 58 (3) |
4 | 5 | 6 | 9 | 10 | 64 (2) | 57 | 60 (7) | 87 (7) | 58 (3) |
4 | 6 | 9 | 10 | 51 (5) | 60 (7) | 87 (7) | 58 (3) |
В соответствии с алгоритмом Прима рассчитаем кратчайшее связное дерево (КСД).
Оно будет содержать ребра: L1,7, L7,8, L7,3,
L3,2, L1,5, L5,4, L3,10, L7,6
, L6,9, общей длиной 442 единицы.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 1 | 0 | 0 | 0 | 0 | 57 | 0 | 39 | 0 | 0 | 0 | 2 | 0 | 0 | 43 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 0 | 43 | 0 | 0 | 0 | 0 | 51 | 0 | 0 | 58 | 4 | 0 | 0 | 0 | 0 | 51 | 0 | 0 | 0 | 0 | 0 | 5 | 57 | 0 | 0 | 51 | 0 | 0 | 0 | 0 | 0 | 0 | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 60 | 0 | 48 | 0 | 7 | 39 | 0 | 51 | 0 | 0 | 60 | 0 | 35 | 0 | 0 | 8 | 0 | 0 | 0 | 0 | 0 | 0 | 35 | 0 | 0 | 0 | 9 | 0 | 0 | 0 | 0 | 0 | 48 | 0 | 0 | 0 | 0 | 10 | 0 | 0 | 58 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Структура такой сети представлена на рис. 1.2.
Рисунок 1.2 - Структура КСД
Выберем 5 городов, из нашей матрицы и составим для нее матрицу расстояний,
перенумеровав города снова.
1. Кировоград
2. Новомиргород
3. Знаменка
4. Каменка
5. Чигирин
Рисунок 1.3 - Матрица  расстояний графа 
1 - й шаг. Выполняем сначала редукцию строк текущей матрицы 
расстояний. Для этого в каждой строке определяем минимальный элемент и найденное
значение вычитаем из элементов соответствующей строки. Результаты выполнения
редукции строк в виде матрицы 
приведены на рис. 1.4, где дополнительный вектор - столбец 
содержит вычитаемые при редукции константы.
Рисунок 1.4 - Редуцированная по строкам матрица расстояний на 1 - м шаге
алгоритма
Затем выполняем редукцию столбцов, результаты которой в виде матрицы 
приведены на рис. 1.5, где дополнительный вектор - строка 
содержит вычитаемые при редукции константы. Значение 
элемента, расположенного на пересечении вектора - столбца 
и вектора - строки  ,
равно сумме всех вычитаемых констант: 
= 249. Это значение является нижней границей 
длин всех маршрутов на данном шаге: 
=249.
Рисунок 1.5 - Редуцированная матрица расстояний на 1-м шаге алгоритма
Рисунок 1.6 - Начальный узел дерева решений
По редуцированной матрице 
расстояний далее определяем минимальные ненулевые значения ее строк и столбцов,
которые записываем соответственно в виде вектора - столбца 
и вектора - строки  .
Матрица  вместе с
этими векторами показана на рис. 1.7.
Рисунок 1.7 - Редуцированная матрица и значения минимальных ненулевых
элементов для 1-го шага алгоритма
Соответствующие элементам векторов 
и  значения
вторичных штрафов 
для различных звеньев или пар вершин 
с нулевыми значениями расстояний между ними приведены в табл. 1.1.
Таблица 1.1 - Вторичные штрафы на 1 - м шаге алгоритма
Как видно из табл. 1.1, максимальное значение 
равно 51. Выбирая звено 
, можно получить выигрыш в расстоянии, равный 51, т.е. больший, чем при выборе
любого другого звена, за исключением звеньев 
,  . Следовательно, в
качестве базового звена на 1 - м шаге ветвления выбирается звено 
, а  , 
Нижней границей длин маршрутов из подмножества 
на следующем (2 - м шаге) является величина 
.
Следовательно, модифицированная матрица 
расстояний после вычеркивания 4 -й строки и 5 -го столбца, а также замены
элемента на пересечении 5 -й строки и 4 -го столбца матрицы 
на  имеет вид,
приведенный на рис. 1.8.
Рисунок 1.8 - Текущая матрица расстояний для 2-го шага алгоритма
2 - й шаг. Выполняем сначала редукцию строк текущей матрицы 
расстояний. Для этого в каждой строке определяем минимальный элемент и найденное
значение вычитаем из элементов соответствующей строки. Результаты выполнения
редукции строк в виде матрицы 
приведены на рис. 1.9, где дополнительный вектор - столбец 
содержит вычитаемые при редукции константы.
Рисунок 1.9 - Редуцированная по строкам матрица расстояний на 2 - м шаге
алгоритма
Затем выполняем редукцию столбцов, результаты которой в виде матрицы 
приведены на рис. 1.10, где дополнительный вектор - строка 
содержит вычитаемые при редукции константы. Значение 
элемента, расположенного на пересечении вектора - столбца 
и вектора - строки  ,
равно сумме всех вычитаемых констант: 
= 49. Это значение позволяет определить новую нижнюю границу 
длин всех маршрутов на данном шаге: 
= 298.
Дерево решений теперь может быть изображено так, как это показано на рис. 1.10.
Рисунок 1.10 - Редуцированная матрица расстояний на 2 - м шаге алгоритма
Рисунок 1.11 - Дерево решений на 2-м шаге алгоритма
По редуцированной матрице 
расстояний далее определяем минимальные ненулевые значения ее строк и столбцов,
которые записываем соответственно в виде вектора - столбца 
и вектора - строки  .
Матрица  вместе с
этими векторами показана на рис. 1.12.
Рисунок 1.12 - Редуцированная матрица и значения минимальных ненулевых
элементов для 2-го шага алгоритма
Соответствующие элементам векторов 
и  значения
вторичных штрафов 
для различных звеньев или пар вершин 
с нулевыми значениями расстояний между ними приведены в табл. 1.2.
Таблица 1.2 - Вторичные штрафы на 2 - м шаге алгоритма
Как видно из табл. 1.2, максимальное значение 
равно  . Выбирая
звено  , можно
получить выигрыш в расстоянии, равный 
, т, е. больший, чем при выборе любого другого звена, за исключением звена
,  , 
. Следовательно, в качестве базового звена на 2 - м шаге ветвления выбирается
звено , а 
,  Нижней границей
длин маршрутов из подмножества 
на следующем (3 - м шаге) является величина 
= .
Модифицированная матрица 
расстояний после вычеркивания 1 -й строки и 2 -го столбца имеет вид, приведенный
на рис. 1.13.
Рисунок 1.13 - Текущая матрица расстояний для 3-го шага алгоритма
3 - й шаг. Выполняем сначала редукцию строк текущей матрицы 
расстояний. Для этого в каждой строке определяем минимальный элемент и найденное
значение вычитаем из элементов соответствующей строки. Результаты выполнения
редукции строк в виде матрицы 
приведены на рис. 1.14, где дополнительный вектор - столбец 
содержит вычитаемые при редукции константы.
Рисунок 1.14 - Редуцированная по строкам матрица расстояний на 3 - м шаге
алгоритма
Затем выполняем редукцию столбцов, результаты которой в виде матрицы 
приведены на рис. 1.15, где дополнительный вектор - строка 
содержит вычитаемые при редукции константы. Значение 
элемента, расположенного на пересечении вектора - столбца 
и вектора - строки  ,
равно сумме всех вычитаемых констант: 
= 2. Это значение позволяет определить новую нижнюю границу 
длин всех маршрутов на данном шаге: 
= 300.
Дерево решений теперь может быть изображено так, как это показано на рис. 1.16.
Рисунок 1.15 - Редуцированная матрица расстояний на 3 - м шаге алгоритма
Рисунок 1.16 - Дерево решений на 3 - м шаге алгоритма
По редуцированной матрице 
расстояний далее определяем минимальные ненулевые значения ее строк и столбцов,
которые записываем соответственно в виде вектора - столбца 
и вектора - строки  .
Матрица  вместе с
этими векторами показана на рис. 1.17.
Рисунок 1.17 - Редуцированная матрица и значения минимальных ненулевых
элементов для 3-го шага алгоритма
Соответствующие элементам векторов 
и  значения
вторичных штрафов 
для различных звеньев или пар вершин 
с нулевыми значениями расстояний между ними приведены в табл. 1.3.
Таблица 1.3 - Вторичные штрафы на 3 - м шаге алгоритма
Как видно из табл. 1.3, максимальное значение 
равно  . Выбирая
звено  , можно
получить выигрыш в расстоянии, равный 
, т.е. больший, чем при выборе любого другого звена, за исключением звена 
,  , 
. Следовательно, в качестве базового звена на 3 - м шаге ветвления выбирается
звено , а 
,  Нижней границей
длин маршрутов из подмножества 
на следующем (4 - м шаге) является величина 
= .
Модифицированная матрица 
расстояний после вычеркивания 2-й строки и 4 -го столбца имеет вид, приведенный
на рис. 1.18.
Рисунок 1.18 - Текущая матрица расстояний для 4-го шага алгоритма
4 - й шаг. Выполняем сначала редукцию строк текущей матрицы 
расстояний. Для этого в каждой строке определяем минимальный элемент и найденное
значение вычитаем из элементов соответствующей строки. Результаты выполнения
редукции строк в виде матрицы 
приведены на рис. 1.19, где дополнительный вектор - столбец 
содержит вычитаемые при редукции константы.
Рисунок 1.19 - Редуцированная по строкам матрица расстояний на 4 - м шаге
алгоритма
Затем выполняем редукцию столбцов, результаты которой в виде матрицы 
приведены на рис. 1.20, где дополнительный вектор - строка 
содержит вычитаемые при редукции константы. Значение 
элемента, расположенного на пересечении вектора - столбца 
и вектора - строки  ,
равно сумме всех вычитаемых констант: 
= 0. Это значение позволяет определить новую нижнюю границу 
длин всех маршрутов на данном шаге: 
= 300.
Дерево решений теперь может быть изображено так, как это показано на рис. 1.21.
Рисунок 1.20 - Редуцированная матрица расстояний на 4 - м шаге алгоритма
Рисунок 1.21 - Дерево решений на 4-м шаге алгоритма
По редуцированной матрице 
расстояний далее определяем минимальные ненулевые значения ее строк и столбцов,
которые записываем соответственно в виде вектора - столбца 
и вектора - строки  .
Матрица  вместе с
этими векторами показана на рис. 1.22.
Рисунок 1.22 - Редуцированная матрица и значения минимальных ненулевых
элементов для 4-го шага алгоритма
Соответствующие элементам векторов 
и  значения
вторичных штрафов 
для различных звеньев или пар вершин 
с нулевыми значениями расстояний между ними приведены в табл. 1.4.
Таблица 1.4 - Вторичные штрафы на 4 - м шаге алгоритма
Как видно из табл. 1.4, максимальное значение 
равно  . Выбирая
звено , можно
получить выигрыш в расстоянии, равный 
, т, е. больший, чем при выборе любого другого звена, за исключением звена
. В качестве базового звена на 4 - м шаге ветвления выбирается звено
, а  , 
Нижней границей длин маршрутов из подмножества 
на следующем (5 - м шаге) является величина 
= .
В модифицированной матрице 
расстояний после вычеркивания 3 -й строки и 1 -го столбца остается один нулевой
элемент, соответствующий звену 
(рис. 1.23).
Рисунок 1.23 - Текущая матрица расстояний для 5-го шага алгоритма
5 - й шаг. Поскольку в текущей матрице 
расстояний имеется только один нулевой элемент, соответствующий звену 
, то это звено является последним в определяемом маршруте длиной 
=300.
Дерево решений теперь может быть изображено так, как это показано на рис. 1.24.
Рисунок 1.24 -Дерево решений на 5-м шаге алгоритма
Построенный полный маршрут является оптимальным, если его длина не превосходит
длины любого маршрута, соответствующего другим звеньям дерева, что и имеет
место в данном примере. Он состоит из следующих звеньев или пар вершин 
и имеет суммарную длину 
=300. Этот оптимальный маршрут является минимальным гамильтоновым циклом,
который изображен на рис. 1.25.
Рисунок 1.25 - Минимальный гамильтонов цикл графа 
2 ОПРЕДЕЛЕНИЕ МНОЖЕСТВА ПУТЕЙ МЕТОДОМ ПОСТРОЕНИЯ ДЕРЕВА
Для графа (см. рис. 2.1) построим дерево путей из вершины 1. Данная вершина
является корнем дерева и размещается на нулевом ярусе. Значение ранга пути
здесь R = 0. На первом ярусе (R = 1) размещаются вершины 2, 3,
4, 5. которые имеют непосредственную связь с вершиной 1. Далее на втором ярусе
от вершины 2 размещаются вершины, которые связаны с вершиной 2, а именно 4 и 5.
Вершина 1 исключается из рассмотрения, поскольку путь в вершину 2 прошел через
вершину 1. От вершины 3 на втором ярусе записываются вершины 4 и 5, от вершины
4 — вершины 2, 3 и 5. А от вершины 5 – 2, 3, 4. Аналогично записываются вершины
на остальных ярусах дерева.
Построенное дерево для вершины-истока 1 представлено на рис. 2.2.
Как видим, в дереве есть четыре пути первого ранга (R = 1): a, e, g,
h; десять путей второго ранга (R = 2): ab, 
, ed,  , 
, gj, gc,  , 
, hf. на третьем ярусе (R = 3) записаны пути третьего ранга: abc,
abj,  , 
,  , edf, 
,  , 
, gjd,  , gcf, 
,  , 
, hfb. В конце концов, пути четвертого ранга (R = 4): 
, abjd,  , 
,  , 
, gjdf,  , hfbj.
Естественно, из дерева можно получить множество путей из фиксированной
вершины в любую вершину графа последовательным просмотром ярусов дерева. Так,
 =a+ +edf+ + + +gjdf+gcf+ + +hf;
 = +abj+ + +e+ +gj+ + + +hfbj;
 =ab+ + + +g+ + +hfb;
 =abjd+ +ed+ + +gjd+gc+h;
Рисунок 2.1 – Граф сети
Рисунок 2.2 - Дерево путей из вершины истока 1.
3 АНАЛИЗ СТРУКТУРНОЙ НАДЕЖНОСТИ СЕТИ ЭЛЕКТРОСВЯЗИ
Рассчитаем надежность связи между первой и всеми другими вершинами графа (1-2,
1-3, 1-4, 1-5). Будем считать заданный нами параметр р=0,817 равным для
всех ребер графа показанном на рис. 3.1. Тогда получаем:
Из результатов видно, что самая большая надежность у пути (1,4) равная 0,972.
Рисунок 3.1 – Надежность связи
|
|
|
