Текущее дерево путей имеет следующий вид:

или

Так как из вершины s в вершину i = 4 имеется два пути с одинаковым весом, тоиз двух путей можно выбрать любой (в дальнейших расчетах выбран первый).

Четвертая итерация

Шаг 2. Так как найдено новое значение i =4¹ t, то пересчитываем временные веса вершин.

d = min { d ₂ ; d ₄ + c₄₂ } = min { 7 , 6 + ¥ } = 7 ;

d = min { d ₂ ; d ₄ + c_4t } = min { ¥ , 6 + 2 } = 8 .

d ₂

Минимальный вес имеет вершина 2. Присваиваем ей постоянный вес

= 7. Положим i = 2.

Шаг 3. Так как i = 2 ¹ t, переходим к шагу 2.

Текущее дерево путей имеет следующий вид:

Пятая итерация.

Шаг 2. Так как найдено новое значение i =2 ¹ t, то пересчитываем временные веса вершин.

d _t = min { d _t ; d ₂ + c_2t } = min { 8, 7+2 } = 8.

Минимальный вес имеет вершина t d _t = 8 . Положим i = t.

d _t

Шаг 3. Так как i = t, алгоритм завершен. Кратчайший путь имеет вес

= 8. Окончательное дерево путей имеет следующий вид:

d _t =8 _{t t}

Таким образом, из вершины s в вершину t найден кратчайший путь с весом .

При расчетах веса узлов и вид текущего дерева на каждой итерации заносятся в таблицу 3.1.

Литература

1. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984.

2. Теория сетей связи / Под ред. В.Н. Рогинского. – М., Связь, 1981.

3. Форд Л.Р., Фалкерсон. Потоки в сетях. – М. Мир, 1966.

4. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. – М.: Мир, 1981.

Варианты заданий

Исходные данные для расчета по двадцати вариантам представлены в таблице 3.2.

Содержание отчёта

1. Описание процедуры расчета по итерациям и шагам.

2. Исходный граф и длина ребер.

3. Таблица итераций.

Таблица 3.1

№ ите-рации

Веса узлов графа

Текущее дерево

0. i = S

∞

1. i = 3

∞

2. i = 1

∞

3. i = 4

∞

4. i = 2

∞

5. i = t

Таблица 3.2

№

Вар.

Вид графа

Веса рёбер графа

№

9 .

10.

№

Вар.

Вид графа

Веса рёбер графа

11.

12.

1 0

13.

1 2

1 4.

1 2

15.

1 0

№

1 6.

1 7.

1 8.

19 .

2 0.

Продолжение таблицы 3.2

Тема 4

Алгоритм поиска маршрутов при динамической маршрутизации вызовов (метод рельефов)

Цель работы

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

Задание

1. Изучить упрощенный алгоритм метода рельефов.

2. Решить задачу нахожденияi-рельефа на графе сети рис. 4.2. Рассмотреть метод устранения петель. Составить j-столбец матрицы рельефов и j-столбец матрицы маршрутов (для установления соединения с узлом i). Числа i и jвзять из таблицы 4.1.

3. Переформировать i-рельеф и внести изменения в матрицу маршрутов при выходе из строя ребра kl . Номер ребра kl взять из таблицы 4.1 в соответствии с выполняемым вариантом.

Теоретическая часть

Основой для любого метода динамического управления потоками сообщений является матрица маршрутов (ММ). ММ – это таблица, содержащая число строк по числу исходящих из рассматриваемого узла ребер и число столбцов по числу узлов сети. Элементами матрицы являются числа, показывающие порядок выбора ребер, исходящих из данного узла, при установлении соединения с любым другим узлом сети.

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

Имеются различные методы, позволяющие изменять матрицы маршрутов в зависимости от ситуации на сети.

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

Прежде чем описывать формальный алгоритм, рассмотрим идею метода рельефов на простейшем примере рис. 4.1. Рассмотрим построение рельефа к узлу 1.

Рис. 4.1. Пример структуры сети связи

Строится рельеф к узлу 1 следующим образом. От смежных с узлом 1 узлов 2, 6 и 5 на каждом ребре, соединяющим эти узлы с узлом 1, ставится стрелка в направлении к узлу 1. Цифра 1 у стрелки показывает вес ребра. Веса ребер, равные 1, указывают на то, что при установлении соединения от узлов 2, 6 и 5 к узлу 1 используются пути в один транзитный участок.

Путь от узла 3 к узлу 1 через узел коммутации 2 ( ) будет содержать 2 транзитных участка, поэтому стрелка от к имеет вес 2 и т.д.

Из узла 6 в направлении к узлу 1 выходят три ребра, веса которых 1, 2 и 3.

Высотой узла 6 по отношению к узлу 1 называется минимальный вес всех исходящих стрелок из узла 6 в направлении к узлу 1. В рассматриваемом случае высота узла 6 по отношению к узлу 1 равна 1.

Рельеф используется при установлении соединения от любого узла сети к узлу 1 для выбора пути с минимальным числом транзитных (коммутируемых) участков.

Матрица рельефов (высот) обозначает число транзитных участков в кратчайших путях от УК _j к УК₁. Например, от УК₄ столбец матрицы рельефов запишется следующим образом:

		1 …
	43	3
R₄ =	46	2
	45	2

Числа в матрице маршрутов задают порядок выбора путей

		1 …
	43	3
M₄ =	46	1 (2)
	45	2 (1)

В рассматриваемом примере пути, начинающиеся с ребер 46 и 45 с точки зрения числа транзитных участков до УК₁ равнозначны, поэтому в скобках в М₄ указан другой возможный порядок выбора.

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

Идея алгоритма заключается в следующем: УК₁ посылает в смежные узлы цифру 1. Смежные узлы рассылают цифру 2, смежные смежным – цифру 3 и т.д.

При этом должны соблюдаться следующие три правила.

Правило 1. Если в УК _i поступили одинаковые цифры с двух и более направлений, то данный УК _i инициирует передачу цифры на 1 больше поступившей по всем без исключения исходящим направлениям. На примере рис. 4.1 это УК₄ . К нему поступила цифра 2 от УК₆ иУК₅ .

Правило 2. Если в УК _i поступает цифра только с одного направления, то УК _i передает цифру на 1 больше поступившей по всем направлениям, кроме того, по которому поступила цифра. По данному направлению будет передана цифра лишь при поступлении в данный УК следующей цифры, т.е. второй по порядку. В примере в УК₃ цифра 2 пришла с одного направления – от УК₂и поэтому в УК₂ от УК₃ цифра 3 не посылается.

После того, как в УК₃ поступит вторая по порядку цифра (в нашем примере 3) от УК₃ к УК₂ будет послана цифра на 1 большая, т.е. 4.

Правило 3. Инициация передачи цифр по всем направлениям производится на каждом УК только один раз после поступления первой цифры.

4. Варианты заданий

№ узлов и ребер	Номера вариантов
№ узлов и ребер	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
i	1	2	1	4	5	5	7	8	9	1	9	4	3	9	1	2	8	1	1	4
j	9	4	3	9	1	2	8	1	1	4	1	2	1	4	5	5	7	8	9	10
k,l	9,10	2,3	3,6	6,9	1,7	2,7	8,9	9,10	1,7	3,4	1,10	2,3	1,2	5,8	5,6	4,5	6,7	8,9	1,10	7,10

Таблица 4.1

Рис.4.2. Структура сети

Содержание отчета

1. Структура сети рис. 4.2 со сформированным i-рельефом.

2. Столбцы матрицы рельефов и матрицы маршрутов для узла j .

3. Структура сети при выходе из строя ребра k , l со сформированным рельефом.

4. Столбцы матрицы рельефов и матрицы маршрутов для узла j при отсутствии

ребра k , l .

Литература

1. Сборник описаний лабораторных работ по курсу «Проектирование и техническая эксплуатация сетей электросвязи». – М.: МТУСИ, 1990.

Тема 5

Алгоритмы нахождения плана распределения каналов

Цель работы

Освоить постановку задачи нахождения плана распределения каналов (ПРК) на первичной сети связи. Изучить приближенные последовательный и параллельный алгоритмы нахождения ПРК.

Задание

1. Ознакомиться с постановкой задачи анализа и структурного синтеза

первичной сети связи.

2. Выполнить нахождение ПРК для заданного варианта сети (рис. 5.2 - 5.3) и заданных в таблицах 5.4 и 5.5 исходных данных последовательным алгоритмом.

3. Выполнить решение задачи параллельным алгоритмом.

4. Сравнить ПРК, полученные разными алгоритмами.

Теоретическая часть

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

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

Для решений задачи нахождения ПРК на первичной сети задаются:

___

Структура первичной сети в виде графа, вершины которого пронумерованы подряд 1, n, где n – число вершин графа, а ребра задаются парами ij, где i , j = 1, n .

2. Емкость каждого ребра в виде матрицы U = ║ u_ij ║ числа каналов первичной сети.

3. Матрица требований между узлами V= ║v_st║, где v_st – требуемое число каналов между узлами s и t вторичной сети.

Требуется найти план распределения каналов между заданными парами узлов с учетом ограниченной емкости ребер первичной сети.

В результате нахождения ПРК решается задача анализа вторичной сети: можно или нельзя получить допустимый ПРК, т.е. ПРК, удовлетворяющий всем требованиям матрицы V = ║ v_st ║, использующий для своей реализации имеющийся ресурс первичной сети.

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

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

Могут быть и другие критерии оптимальности построения ПРК, например, суммарная длина всех путей или суммарное число канало-километров.

Для нахождения ПРК может использоваться метод линейного программирования или приближенные инженерные алгоритмы: последовательный и параллельный.

Последовательный алгоритм нахождения ПРК

1. Из матрицы требований V = ║ v_st ║ выбирается пара вершин s и t, между которыми v_st >0 .

2. По графу сети определяется кратчайший путь (пути) m _st ^min . Кратчайший путь находится по числу ребер или по длине пути.

3. С помощью матрицы U= ║u_ij║ определяется емкость этого пути.

c_st = min u_ij _.

ij Î m _st ^min

4. Из емкости u_ijребер пути m _st ^min вычитается величина c_st . Если v_st > c_st , то вычисляется разность v_st - c_st , которая распределяется по следующему пути между вершинами st, если таковой имеется.

5. Выбирается следующая пара вершин и процесс повторяется до тех пор, пока существует хотя бы одно требование v_st > 0 и, по крайней мере, один путь m _st ^min между выбранной парой вершин с емкостью c_st > 0.

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

Дата добавления: 2019-03-09; просмотров: 243; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 345 6 Следующая ⇒

Мы поможем в написании ваших работ!