Методические указания по выполнению лабораторной работы № 1

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

Основу проектирования сетей передачи дискретных сообщений (ПДС) составляют математические модели оптимизации структуры многополюсных сетей. Сеть ПДС может быть задана графом или численной моделью.

Совокупность каналов, соединяющих непосредственно пару узлов _i и _j сети, образует ветвь _ij . Простейшей записью структуры сети в графовых моделях является матрица связности, в которой элементы матрицы a_ij принимают значение 1, если есть ветвь, связывающая узлы _i и _j, и 0 – в противном случае. Если в сети нет направленных ветвей, то матрица связности будет симметричной относительно главной диагонали. Если такие ветви есть, то сеть будет несимметричной. Ненаправленная ветвь, соединяющая узлы _i и _j может быть обозначена двумя символами _ij = _ji.

Путь _xy из узла _x в узел _y, представляющий собой упорядоченный набор ветвей, начинающихся в узле _x и заканчивающихся в узле _y , причем конец каждой предыдущей ветви совпадает в промежуточном для данного пути узле с началом последующей ветви, называется самонепересекающимся, то есть не проходящим дважды через один и тот же узел. Если путь состоит из ненаправленных ветвей, то он будет ненаправленным или двусторонним _xy = _yx. Пути могут быть зависимыми и независимыми. Рангом (_xy) пути называется число ветвей, входящих в данный путь. Связностью сети называется минимальное число независимых путей, имеющихся между каждой парой узлов. Сечение сети есть неизбыточная совокупность ветвей, которые нужно изъять из сети, чтобы нарушилась ее связность. Рангом сечения называется число входящих в него ветвей.

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

Для решения задач оптимизации структуры сети ПДС в целом необходимо численное представление структуры. Одной из таких моделей является геометрическая модель. Для упрощения геометрической модели принимаются следующие допущения:

1. Территория многополюсной сети ограничена прямоугольником.

2. На заданной территории все узлы расположены равномерно, образуя поле n_Вn_Г = n, где n_В – число узлов в вертикальном ряду, а n_Г – число узлов в горизонтальном ряду.

3. Число типовых структур сети сокращается до пяти: радиальная, кольцевая, решетчатая, полносвязная, кратчайшесвязная.

Геометрическая модель может быть построена только на основе равномерного размещения узлов, иначе она не может быть построена вообще. При решении конкретных задач необходимо так конструировать территорию сети, чтобы она максимально приближалась к выполнению условия равномерного размещения узлов. В случае невозможности подбора адекватного варианта геометрической модели применяются различные дополнительные методы для уточнения решения.

Одним из частных случаев численной модели является описание структуры кратчайшесвязной сети. Каждая ветвь сети характеризуется такими параметрами как длина l_ij, емкость, надежность и многими другими. Длина ветви определяется расстоянием между узлами _i и _j или другими параметрами ветви (например, стоимостью).

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

Разработано большое количество различных эвристических алгоритмов, базирующихся на принципах Прима и позволяющих построить кратчайшесвязную сеть. Исходные данные для построения такой сети содержатся в матрице L=l_ij расстояний между узлами сети, где l_ij - расстояние между вершинами _i и _j. На первом шаге алгоритма Прима находится минимальный элемент матрицы L. Пусть таким элементом оказался элемент l_ij = l_ji. Тогда первой ветвью дерева минимальной длины будет ветвь, соединяющая вершины _i и _j. В строках матрицы с номерами i и j отыскивается следующий минимальный элемент. Допустим, этим элементом является элемент l_jk в строке k . Тогда второй ветвью дерева минимальной длины будет ветвь, соединяющая вершины _j и _k. Далее процедура повторяется для строк i, j и k. Таким образом, на каждом шаге построения дерева минимальной длины отыскивается ветвь минимальной длины, соединяющая еще не соединенные вершины. Связное дерево минимальной длины будет содержать n-1 ветвей, где n -число вершин графа или число оконечных пунктов сети.

Применение описанной методики целесообразно проиллюстрировать примером. Пусть задано расположение 10 оконечных пунктов (рис.1.1)

Рис. 1.1. План сети

и матрица L расстояний между ними (табл.1.2).

Таблица 1.2. Матрица расстояний
	1	2	3	4	5	6	7	8	9	10
1	0	5,3	5,4	8,6	12,7	12,6	11,7	13,4	12,1	19,8
2	5,3	0	7,0	8,0	8,9	7,3	6,4	11,7	11,8	16,7
3	5,4	7,0	0	3,6	9,6	12,6	13,3	8,5	6,7	15,5
4	8,6	8,0	3,6	0	6,8	11,5	13,7	4,9	3,8	12,0
5	12,7	8,9	9,6	6,8	0	7,4	11,8	5,6	8,3	8,0
6	12,6	7,3	12,6	11,5	7,4	0	5,7	12,5	14,4	14,2
7	11,7	6,4	13,3	13,7	11,8	5,7	0	16,3	17,4	19,3
8	13,4	11,7	8,5	4,9	5,6	12,5	16,3	0	3,5	7,4
9	12,1	11,8	6,7	3,8	8,3	14,4	17,4	3,5	0	10,6
10	19,8	16,7	15,5	12,0	8,0	14,2	19,3	7,4	10,6	0

Минимальным элементом матрицы является элемент l₈₉ = l₉₈ = 3,5. Тогда в соответствии с алгоритмом Прима выписываем восьмую и девятую строки, вычеркнув восьмой и девятый столбцы.

	1	2	3	4	5	6	7	10
8	13,4	11,7	8,5	4,9	5,6	12,5	16,3	7,4
9	12,1	11,8	6,7	3,8	8,3	14,4	17,4	10,6

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

	1	2	3	4	5	6	7	10
	12,1 (9)	11,7 (8)	6,7 (9)	3,8 (9)	5,6 (8)	12,5 (8)	16,3 (8)	7,4 (8)

Цифрой в скобках указывается, из какой строки взят тот или иной элемент. Выбираем минимальный элемент первой вспомогательной строки l₉₄ = l₄₉ = 3,8. С учетом этого выписываем первую вспомогательную строку и четвертую строку матрицы, предварительно вычеркнув из нее восьмой, девятый и четвертый столбцы.

	1	2	3	5	6	7	10
	12,1 (9)	11,7 (8)	6,7 (9)	5,6 (8)	12,5 (8)	16,3 (8)	7,4 (8)
4	8,6	8,0	3,6	6,8	11,5	13,7	12,0

Формируем вторую вспомогательную строку.

	1	2	3	5	6	7	10
	8,6 (4)	8,0 (4)	3,6 (4)	5,6 (8)	11,5 (4)	13,7 (4)	7,4 (8)

Выбираем из нее минимальный элемент l₄₃ = l₃₄ = 3,6.

Продолжая далее аналогичным образом, получим остальные ветви кратчайшесвязной сети: l₃₁ = l₁₃ = 5,4; l₁₂ = l₂₁ = 5,3; l₈₅ = l₅₈ = 5,6; l₂₇ = l₇₂ = 6,4; l₇₆ = l₆₇ = 5,7; l₈₁₀ = l₁₀₈ = 7,4, структура которой будет выглядеть так, как показано на рис. 1.2.

Рис. 1.2. Структура кратчайшесвязной сети

При этом общая длина сети будет составлять 3,5+3,8+3,6+5,4+5,3+5,6+6,4+5,7+7,4=46,7 условных единиц.

Построение кратчайшесвязной сети по описанному алгоритму решает задачу создания сети с минимальной длиной линий связи непосредственно между заданными узлами. В общем случае подобная сеть не является самой короткой, которая может быть вообще создана. В частности, давно известна задача Штейнера: найти кратчайшесвязную сеть для данного множества узлов, допуская добавление в любом месте сети дополнительных транзитных узлов. Решения этой задачи, удобного для проектирования сетей, к настоящему времени не существует.