Основы построения телекоммуникационных систем

Соответственно номеру зачетной книжки выберем Кировоградскую область, т.к. она соответствует №17, а также запомним p=0,817.

Выберем десять городов, соответствующие нашей области:

1. Кировоград
2. Бобринец
3. Долинская
4. Новоукраинка
5. Новомиргород
6. Каменка
7. Знаменка
8. Александрия
9. Чигирин
10. Кривой рог

1 СИНТЕЗ ТОПОЛОГИИ СЕТИ ЭЛЕКТРОСВЯЗИ МЕТОДОМ М - СТРУКТУР

Составим матрицу расстояний для нашего графа:

Рисунок 1.1 – Граф сети

В соответствии с алгоритмом Прима сначала выписывается первая строка матрицы без первого столбца, что соответствует организации связи от первой вершины и соответствует организации связи от первой вершины (центрального пункта) к остальным - м ():

Выбираем в этой строке минимальный элемент . Далее вычеркиваем соответствующий ему 7-й столбец матрицы и, двигаясь по 7-й строке, сравнивается значение приведенных в ней элементов с их значениями в первой строке без первого и 7-го столбцов. Если значение элемента 7- й строки в соответствующем столбце оказывается меньше значения, указанного в первой строке, то эти значения меняются местами. Если наименьшим будет значение в первой строке, то замена не производится. Таким образом формируется следующая строка:

При этом цифрой 7 в скобках обозначены те значения длин, которые взяты из седьмой строки.

Вновь выбираем минимальный элемент строки . Действуя аналогично предыдущему, получаем новую строку:

Выбираем минимальный элемент строки . Ниже показан дальнейший процесс поиска:

В соответствии с алгоритмом Прима рассчитаем кратчайшее связное дерево (КСД). Оно будет содержать ребра: L1,7, L7,8, L7,3, L3,2, L1,5, L5,4, L3,10, L7,6, L6,9, общей длиной 442 единицы.

Структура такой сети представлена на рис. 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 – Надежность связи