Geum.ru

Стислий конспект лекцій з дисципліни "Телекомунікаційні та інформаційні мережі" (тім) (програма бакалаврського мінімуму) Лектор доц. В.І. Тіхонов

Вид материалаКонспект

Содержание


Построение маршрутных матриц путей 1-, 2- и 3-го выбора по критерию
6.6. Определение оптимального местоположения
Подобный материал:
1   2   3   4   5   6   7   8   9   10   11

^ Построение маршрутных матриц путей 1-, 2- и 3-го выбора по критерию

минимумам транзитности.


Пусть задана топология сети в виде таблицы:



Начало
1
1
1
1
1
2
2
2
2
3
3
3
4
4
5

Конец
2
3
4
5
6
3
4
5
6
4
5
6
5
6
6

Вес
50
40
11
70
15
10
90
60
40
75
20
16
40
50
19



Пусть заданным узлом коммутации является узел 5. Для данного узла коммутации построить маршрутную матрицу путей 1-, 2- и 3-го выбора по критерию минимума транзитности. Максимально допустимая транзитность -3. При равной транзитности выбирать пути наименьшей меньшей длины.


Исходя из заданной табличной топологии сети построим взвешенную матрицу смежности узлов:


Матрица смежности сети




1
2
3
4
5
6

1
Х
50
40
11
70
15

2
50
Х
10
90
60
40

3
40
10
Х
75
20
16

4
11
90
75
Х
40
50

5
70
60
20
40
Х
19

6
15
40
16
50
19
Х




Результирующая маршрутная

Матрица для узла 5

Выбор:
1
2
3
4
6

1 выбор
1
2
3
4
6

2 выбор
6
3
6
6
3

3 выбор
3
?
?
?
?
Поскольку матрица полносвязна, то для узла 5 первая строка матрицы коммутации (первый выбор по условию минимума транзита будет иметь вид (т.е. выбор к узлу совпадает с его номером)

5: 1, 2, 3, 4, 6 ;

Рассмотрим выбор второго уровня. Из узла 5 можно попасть в остальные узлы через транзиты. Например, в узел 1: через 2 (длина пути = 60+50), через 3 (длина пути=20+40), 4 (40+11), 6(19+15). Самый короткий путь из 5 в 1 с одним транзитом – это через пункт 6 (длина пути 34).

Далее, из 5 в 2: через 1(70+50), 3(20+10), 4(40+90), 6(19+40). Самый короткий из них – через пункт 3 (длина пути 30).

Из 5 в 3: через 1(70+40), 2(60+10), 4(40+75), 6(19+16). Самый короткий – через 6(35).

Из 5 в 4: 1(70+11), 2(60+90), 3(20+75), 6(19+50). Самый короткий – через 6 (69).

Из 5 в 6: 1(70+15), 2(60+40), 3(20+16), 4(40+50). Самый короткий – через 3 (36).

Выбор второго уровня для вершины 5:

5: 6, 3, 6, 6, 3


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

5-2-3 -1 Длина пути = 60+10+40=110

5-2-4 -1 60+90+11=161

5
Кратчайший путь третьего уровня транзитности от узла 5 к 1 – это узел 3.

-2-6 -1 60+40+15=115

5-3-4 -1 20+75+11=106

5-3-6-1 20+16+15= 51

5-4-6-1 40+50+15=105


6.5. Построение дерева кратчайших путей, которые обеспечивают

подключение соединительных трактов от заданного узла коммутации

ко всем остальным узлам сети


Пусть задана топология сети в виде таблицы дуг и их весов:



Начало
1
1
1
2
2
3
3
4
4

Конец
2
3
5
3
4
4
6
5
6

Вес
10
15
18
20
17
16
25
14
20



Построить дерево кратчайших путей, которое обеспечивает подключение узла коммутации в пункте 3 ко всем остальным узлам.

Решение:
  1. Построим граф сети.
  2. Применим алгоритм Прима для нахождения

дерева минимального покрытия графа.

Это дерево и результат применения

алгоритма не зависит от того, какая именно

вершина задана в качестве узла коммутации,

и какая точка выбрана в качестве начальной для алгоритма.
  1. Начнем с точки 3. Выберем кратчайшее

продолжение – вершину 1. Покрасим вершины

3 и 1 вместе с соединяющей их дугой.

Будем искать дальнейшие возможные продолжения из всех закрашенных вершин

т всякий раз выбирать минимальные.


Алгоритм закончен, когда закрашены все вершины.

Теперь можно определить общую минимальную длину

всех закрашенных путей:

10+15+16+20+14 = 75

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


^ 6.6. Определение оптимального местоположения

базовой радиостанции, обеспечивающего

минимальную мощность передатчика


Эта задача сводится к отысканию такого узла сети, по отношению к которому минимизируется расстояние до самой удаленной точки; если в этом узле установить радиопередатчик, то это обеспечивает его минимальную мощность. Как правило, в этой задаче граф сети является полносвязным. Для решения задачи удобно представить топологию сети в виде матрицы расстояний, например:


Вершины/

расстояния

(км)

1

2

3

4
Расстояние до самой удаленной точки

1
Х
10
10
15
15

2
10
Х
10
20
20

3
10
10
Х
12
12

4
15
20
12
Х
20


Решение задачи "минимакса" дает выбор вершины 3 для установки базовой станции. При этом мощность передатчика должна обеспечивать связь до самой удаленной точки (расстояние до нее = 12).


6.7. Построение дерева кратчайших путей от заданного узла

коммутации (УК) ко всем остальным узлам сети