АЛМАТИНСКИЙ ИНСТИТУТ

ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра автоматической

электросвязи

ПРОЕКТИРОВАНИЕ СЕТЕЙ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ.

Программа и методические указания к контрольным заданиям

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

Алматы 2005

СОСТАВИТЕЛЬ: Данилина Г.П. Проектирование сетей телекоммуникационных систем. Программа, методические указания и контрольные задания для студентов радиотехнических специальностей заочной формы обучения.- Алматы: АИЭС, 2005. - с.

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

Ил. 12, табл. , библиогр. 8 назв.

Рецензент: доцент кафедры АЭС кандидат технических наук К.Х. Туманбаева

Печатается по плану издания Алматинского института энергетики и связи на 2005 г.

Предисловие

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

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

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

1 Программа курса

Программа рассчитана на 94 часа – самостоятельной работы 52 часа, аудиторных занятий 42 часа, в том числе 25 часов лекций, 17 часов практических занятий.

1.1 Содержание учебного материала

1.1.1Введение

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

Глобализация связи и ее персонализация (2 часа).

1.1.2 Общие сведения о проектировании

Определение процесса проектирования. Виды проектирования, стадии. Блочно-иерархический подход (БИП) – теоретическая основа проектирования современных технических объектов. Концепции БИП. Понятия о больших системах (2 часа).

1.1.3 Моделирование больших систем

Принципы выделения подсистем. Уровни моделирования. Формы представления моделей, требования к ним. Задачи анализа и синтеза (2 часа).

1.1.4 Методы оптимизации

Структура и архитектура сетей. Представление структур графами. Методы оптимизации топологий. Критерии оптимизации. Модели задач синтеза и методы их реализации. Маршрутизация (6 часов).

1.1.5 Сеть как система массового обслуживания

Марковские случайные процессы: процесс гибели и размножения, метод диаграмм интенсивностей переходов. Однолинейные марковские системы массового обслуживания.

Аналитические методы теории сетей. Сети, зависящие от нагрузки. Показатели качества функционирования однородных сетей (4 часа).

1.1.6 Сети интегрального обслуживания

Структура сетей с интеграцией служб. Расчет доступности. Проектирование сетей интегрального обслуживания, этапы построения СИО, критерии оценки эффективности, модель (6 часов).

1.1.7 Построение модели оптимизации параметров сети сотовой связи (3 часа)

1.2 Примерный перечень практических занятий

1.2.1 Синтез структуры сетей:

- централизованных;

- в путевой форме;

- с фиксированными доплатами.

1.2.2 Общая задача топологического синтеза

1.2.3 Задача распределения каналов

1.2.4 Задача систем массового обслуживания:

- подсчет показателей качества функционирования однородных сетей;

- оптимизация пучка каналов на прямых и обходных направлениях.

1.3 Перечень РГР

1.3.1Оптимизация структуры сети.

1.3.2 Анализ архитектуры.

1.3.3 Методы маршрутизации.

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

2.1 Состояние и перспективы развития связи

Изучение настоящего курса начинается с краткого повторения основных положений понятия телекоммуникации, ее состава, современного состояния развития с точки зрения возможностей и целесообразности проектирования.

2.1.1 Что является «рабочим объектом» телекоммуникации?

2.1.2 Главная цель создания телекоммуникационных систем (Т – система).

2.1.3 Комплекс задач, решаемый Т-системой, их основное содержание.

2.1.4 Особенности современного состояния телекоммуникаций.

2.1.5 Функции ЭВМ в Т-системе.

2.1.6 Направления совершенствования связи.

2.2 Общие сведения о проектировании

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

2.2.1 Что такое «блочно-итерационный подход»? Его концепции.

2.2.2 Понятие «большая система». Свойства больших систем. Является ли телекоммуникация «большой системой»?

2.2.3 Стадии проектирования. Какие стадии являются обязательными?

2.3 Моделирование больших систем

Следует обратить внимание на типы моделирования, обосновать преимущества математического моделирования.

2.3.1 Каковы уровни моделирования и формы представления моделей?

2.3.2 Как выделяются подсистемы?

2.3.3 Как строятся математические модели?

2.3.4 Что такое критерии и ограничения?

2.4 Методы оптимизации

Студентам следует понять и запомнить особенности расчетов на сетях, различать два основных типа задач – задачи анализа и синтеза.

2.4.1 Структура и архитектура сетей.

2.4.2 Как формализуется структура сетей?

2.4.3 Какие методы применяются при оптимизации структуры?

2.4.4 Как строится модель синтеза централизованной сети?

2.4.5 В чем состоит идея методов реализации этих моделей?

2.4.6 Где используются методы построения кратчайших путей?

2.5 Сеть как система массового обслуживания

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

2.5.1 Что такое «простейший поток»?

2.5.2 Понятие о «процессах гибели и размножения».

2.5.3 Использование названных процессов в теории массового обслуживания.

2.5.4 Как применяются методы теории массового обслуживания в Т-системах?

2.5.5 Показатели качества функционирования однородных сетей.

2.6 Сети интегрального обслуживания

Необходимо изучить общий подход к проектированию СИО

2.6.1 Критерии оценки эффективности.

2.6.2 Иерархия моделей процессов и математические схемы их формализации.

2.6.3 Анализ вариантов построения технологической структуры.

2.6.4 Синтез структуры магистральных сетей.

2.7 Оптимизация параметров сотовой связи

Следует знать особенности систем подвижной связи, их преимущества и недостатки.

2.7.1 Учитываемые параметры.

2.7.2 Критерии оптимальности.

2.7.3 Система ограничений.

2.7.4 Подход к реализации модели.

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

3 Методические указания к контрольной работе

Контрольная работа состоит из трех заданий:

а) решения задач синтеза сетей различного типа - транспортных и централизованных;

б) построения кратчайших путей на сети.

Для выполнения контрольной работы необходимо:

- изучить теоретические и методические основы каждого задания;

- рассмотреть пример выполнения задания;

- определить вариант исходной информации по указаниям, приведенным в каждом задании;

- выполнить необходимые расчеты и оформить соответствующий отчет.

3.1 Решение задач синтеза транспортных сетей

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

В настоящей работе рассматриваются два метода построения топологии сетей.

Задание к задаче №1:

- изучить постановку задачи исследования;

- выбрать вариант исходной информации;

- преобразовать сеть в сеть с одним источником;

- записать модель;

- решить ее указанным методом;

- изобразить на чертеже оптимальный граф с распределением потока на его дугах;

- указать величину целевой функции.

3.1.1 Под транспортной сетью будем понимать сеть, имеющую:

- некоторое множество источников S, т.е. вершин, генерирующих поток с заданной интенсивностью или получающих его из вершин других сетей

S={i, i,… i},

D= {d , d ,… d };

- некоторое множество стоков Т, т.е вершин, поглощающих поток

Т={j, j,… j };

D= {- d, - d,… - d };

- вершины с нулевой интенсивностью d=0, называемые перевалочными пунктами.

Всем дугам поставлены в соответствие две функции: функция стоимости f(x) и пропускная способность r- при этом функция f(x) обладает следующими свойствами

f(х) =0, если х=0, _. (3.1)

f(х) >0, если х>0.

При решении задачи синтеза транспортных сетей (СТС) функция f(х) представляет затраты на перемещение потоков cх и затраты на создание сети p>0.

Для выполнения условия (3.1) вводится специальная функция

                                         (3.2)

и функция стоимости принимает вид

f()=c+ph(), (3.3)

где c- стоимость перемещение единицы потока,

p- стоимость создания дуги (ij).

Обычно сеть описанного вида при решении заменяется сетью с одним источником и одним стоком, выполняя следующие преобразования. В сеть вводятся две дополнительные вершины: источник S и сток Т,- которые соединяются так называемыми мнимыми дугами

(S, i), (S, i),…(S, i)

(j,T), (j,T),… (j,T).

Рисунок 3.1 – Сеть с несколькими источниками и стоками

Рисунок 3.2 – Сеть с одним источником и одним стоком

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

r = d r=- d

d= d =

d= 0 d= 0

c= 0 c = 0

p= 0 p= 0

3.1.2 Экономико – математическая модель задачи синтеза транспортных сетей

На построенной таким образом сети G = () необходимо построить такое распределение потока от источника S к стоку Т, чтобы затраты на создание и эксплуатацию сети G = () были минимальными при выполнении определенных ограничений

(3.5)

(3.4)

min ,

(3.6)

0 ,

(3.7)

,

(3.8)

h()= .

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

3.1.3 Алгоритм задачи СТС [6]

(3.9)

Задача имеет смысл, если интенсивности источника и стока равны по величине и противоположны по знаку

Алгоритм состоит из последовательности повторяющихся шагов.

Шаг 0. Произвести первоначальное распределение потока, удовлетворяющее ограничениям (3.5 - 3.9).

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

Шаг 2. Для каждой хорды () строится цикл из дуг дерева . Направление обхода этого цикла определяется из следующих условий:

а) если х то поток по хорде () может только увеличиваться и направление обхода цикла совпадает с направлением ();

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

(3.11)

а на дугах отрицательной полуцепи уменьшена на

. (3.12)

Изменение потока в цикле возможно только на меньшую из этих величин

. (3.13)

Шаг 3. Подсчет величин потока в цикле выразим соотношением

х (3.14)

Шаг 4. Оценка целесообразности изменения потока в цикле производится следующим способом:

рассчитывается функция

и функция F, где определены по (3.14).

Значения F сравниваются: если , остается старое распределение и алгоритм продолжается для другой хорды с шага 2;

если -, производится изменение потока в цикле по (3.14) и переход к Шагу 1.

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

3.1.4 Описанный метод реализации модели (3.4 – 3.10) проиллюстрируем небольшим примером.

d₁=30 ; d₅= -30;

Рисунок 3.3 - Исходный граф транспортной Рисунок 3.4 - Первоначальное

cети распределение потока

Пусть на рисунке 3.3 приведен граф некоторой транспортной сети, имеющий вершину – источник 1, сток – вершину 5, с интенсивностями ед, ед. На каждой дуге записаны исходные данные: первое число – пропускная способность , второе число – стоимость перемещения единицы потока , третье - стоимость создания ребра . Если на ребре есть поток, то он записывается как числитель над величиной пропускной способности.

Шаг 0. Произведем первоначальное распределение потока, удовлетворяющее соотношениям (3.5-3.7).

Будем насыщать последовательно дуги, исходящие из вершины 1.

На дуге 1-2 пропускная способность , следовательно, положим равным , т.е.

В вершине 1 осталось нераспределенным единиц потока, а ( рисунок 3.4).

Следующая рассматриваемая дуга (1-3) с пропускной способностью . Поток определяется формулой

Далее распределяется поток от вершин с ненулевой интенсивностью:

;

Распределение потока приведено на рисунке 3.4

Шаг 1. Построим дерево графа, включив в него основные дуги, т.е. дуги, поток на которых удовлетворяет условиям На графе рисунка 3.4 таких дуг три: (1-3); (2-5); (3-5). Поскольку рассматриваемый граф имеет пять вершин, то дерево состоит из n-1=5-1=4 дуг, поэтому включим еще одну дугу, поток на которой равен или 0 и которая не образует с ранее выделенными замкнутого цикла. Этим условиям удовлетворяет любая из дуг (1-4), (4-3) или (4-5). Пусть это будет дуга (1-4). Дуги дерева на рисунке 3.4 выделены жирными линиями.

Шаг 2. Для каждой дуги – хорды строится цикл и определяется величина возможного изменения потока.

Для хорды (1-2) цикл состоит из дуг (2-5), (3-5) и (1-3), направление обхода цикла определяется величиной потока на хорде: если =r, то направление обхода цикла противоположно направлению хорды.

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

Определим возможную величину изменения потока в цикле по формулам (3.11-3.13)

Шаг 3. Подсчитывается величина нового распределения потока в цикле по формуле (3.14)

Шаг 1. Определяется целесообразность изменения потока в цикле. Для этого подсчитываются значения функции стоимости при старом и новом распределении потока и сравниваются

Потоки в цикле не меняются. Проверяется другой цикл, например, цикл для хорды (2-3).

Шаг 2. Поток на хорде (2-3) равен нулю, поэтому обход цикла совпадает с направлением хорды (2-3). Следовательно,

Изменение потока в цикле определяется по формулам (3.11-3.13)

Шаг 3. Подсчет величины нового потока в производится по формуле (3.14).

Шаг4. Определяются значения функций при старом и новом распределении потока

Полученное неравенство говорит о целесообразности изменения потока. Новое распределение потока приведено на рисунке 3.5.

Проверим оптимальность приведенного распределения, проанализировав циклы для всех хорд.

Рисунок 3.5- Второе распределение потока и соответствующее ему дерево

Шаг 2. Рассмотрим хорду (1-4). Ей соответствует цикл Т.к. то направления обхода цикла совпадает с направлением хорды (1-4).

Шаг 3. Новый поток в цикле определим по формуле 3.14

Шаг 4. Подсчет целевых функций производится при старом и новом распределении потоков.

Изменяем поток в цикле и переходим к шагу 1.

Шаг 1. Новое распределение, приведенное на рисунке 3.6

1

а)

а) б)

Рисунок 3.6- Третье распределение потока (а), оптимальный граф (б).

Проверки целесообразности изменение потоков для всех циклов сети.

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

3.1.5 В приложении А по последней цифре номера зачетной книжки определяется вариант сети. Если сеть с несколькими источниками или стоками – произвести ее преобразование, записать экономико-математическую модель и решить ее. Привести чертеж оптимальной сети.

Разработать блок – схему программы алгоритма.

3.2 Решение задачи синтеза централизованной сети

Задание к расчетно-графической работе:

- изучить постановку задачи;

- выбрать в Приложении Б вариант задания по последней цифре номера зачетной книжки, а в Приложении В- по предпоследней цифре вектора {r_j}и { f_j};

- решить задачу вручную и оформить результаты решения.

3.2.1 Централизованной называется сеть, если в ней существуют 2 иерархических уровня:

- терминалы , которые могут подключаться к удаленному концентратору или непосредственно к центральной ЭВМ;

- удаленные концентраторы , которые соединяются с центральной ЭВМ.

Рисунок 3.7 - Граф централизованной сети

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

Итак, заданными являются:

- множества терминалов и концентраторов (), ЭВМ-;

- стоимость линий связи, заданных матрицей стоимости ;

- стоимость создания концентраторов .

Определить:

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

Обозначим такие соединения с переменной , при отсутствии связи .

Будем называть концентратор открытым, если он используется, и закрытым в противном случае. Эта ситуация отражается переменной :

, если открыт (к нему подключен хотя бы один терминал);

- закрыт.

Очевидно, что , если ;

, если . (3.15)

Тогда целевая функция стоимости запишется в виде

(3.16)

.

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

(3.17)

,

Первое ограничение означает, что каждый терминал должен быть подключен либо к ЭВМ (), либо к одному из концентраторов.

Второе ограничение связано с заданной возможностью подключения к концентратору ограниченного числа терминалов.

Задача представлена целочисленной (ноль-единичной) моделью линейного программирования.

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

3.2.2. Алгоритм метода добавления

Агоритм основан на идее последовательного улучшения плана и представляет итерационный процесс.

Шаг 0. Первоначально план прикрепления терминалов представлен множеством

т.е. все терминалы прикреплены к ЭВМ. Очевидно, что это самое дорогое решение.

Итерация 1

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

Шаг 1. Откроем . Эффект от изменения присоединения к вместо определим по формуле

. (*)

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

(включены только , число их меньше ).

Аналогичных шагов будет (по числу концентраторов).

Шаг (m+1). Определяются наименьшие затраты

Следовательно, откроем концентратор , присоединив к нему .

Итерация 2

Считая открытым концентратор , будем открывать по очереди еще по одному концентратору.

Шаг 1. Откроем при открытом , оценим:

для i, не присоединенных к ; (**)

для g= 1,…,k , т.е. для тех , которые присоединены к .

Выбираются наибольших разностей (**) и подсчитываются затраты

Шагов будет m-1 (по числу закрытых еще концентраторов).

Шаг m. Определяется наименьшее значение функции

Итерация 3

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

Последняя итерация состоит в открытии всех концентраторов одновременно.

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

Исходные данные приведены в матрице , векторах и .

r=2

f₁=3

f₂=2

f₃=3

f₄=1

Шаг 0. Подсчитаем F₀ по формуле

Итерация 1. Открываем . Подсчитаем разность стоимости подключения терминала к ЭВМ или .

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

Шаг 2. Открываем

Шаг 3. Открываем

Шаг 4. Открываем

К₁

Рисунок 3.7 – Прикрепление терминалов после первой итерации

Итерация 2

Шаг 1. При открытом К₄ открываем К₁:

а) ; б) .

Шаг 2. При открытом К₄ открываем К₂:

а) ; б) .

Шаг 3 При открытом К₄ открываем К₃:

а) ; б) .

Прикрепление терминалов показано на рисунке 3.8

Рисунок 3.8 - Прикрепление терминалов после 2 итерации

Итерация 3

Шаг 1. При открытых К₃ и К₄ открываем К₁:

а) С_i₀-C_i₁ ; б) ; в) .

Шаг 2. При открытых К₃ и К₄ открываем К₂

а) С_i₀-C_i₁ ; б) ; в) .

Уменьшение целевой функции показывает целесообразимость открытия концентратора К₁ (рисунок 3.9).

Рисунок 3.9 - Прикрепление терминалов после III итерации

Итерация 4. Проверим целесообразность открытия К₂ при открытых К₁, К₃, К₄:

а) ; б) ; в) .

г)

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

3.3 Решение задач маршрутизации

Под маршрутизацией будем понимать процедуру установления на графе путей определенного качества. Под качеством понимается как монологическая характеристика (соединение двух заданных вершин, одной со всеми или каждой с каждой), так и количественная – число дуг, минимум стоимости, максимум пропускной способности и.т.д. В общем случае задача может быть сформулирована как задача целочисленного математического программирования, но учет особенностей задачи значительно сокращает процедуру ее решения. Разработано большое количество методов ее решения [2], некоторые из которых были рассмотрены при изучение курса «Основы сетей и систем телекоммуникаций». Однако широкое приложение этих методов в сетях коммутации пакетов делает целесообразным рассмотрение дополнительных методов, основанных на других идеях. Рассмотрим метод динамического программирования и метод Флойда [7 ]

Указания к выполнению задания:

- определить вариант задания (по последней цифре зачетной книжки в Приложении Г определяется номер графа);

- выбрать любой метод реализации из 2-х описанных;

- изучить методические указания и алгоритм решения;

- описать все этапы решения;

- начертить оптимальный подграф и определить соответствующую ему стоимость.

3.3.1. Метод динамического программирования

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

Алгоритм рассмотрим на конкретном примере.

Пусть дан граф (3.10)

Рисунок 3.10 – Исходный граф

Для решения задачи исходный граф разбиваем на три подмножества (рисунок 3.11).

727

7

Рисунок 3.11 – Декомпозиция задачи и результаты вычислений

Обозначим - кратчайшее расстояние до вершин на этапе ; - расстояние от вершины до . Значение будем вычислять с помощью рекуррентного уравнения

где минимум ищется по всем возможным маршрутам от вершин до . Значения при полагаем .

Этап 1.

(из вершины 1),

(из вершины 1).

Этап 2.

(из вершины 4),

(из вершины 3).

Итоговые результаты этапа 2:

(из вершины 4),

(из вершины 3).

Этап 3.

(из узла 5).

Итоговые результаты этапа 3:

(из вершины 5).

Итак, кратчайшее расстояние от вершины 1 до вершины 7 равно 21. Чтобы восстановить последовательность вершин, образующих кратчайший путь, необходимо просмотреть итоговые результаты каждого этапа (от последнего к первому) и выписать номер вершины, для которых величина минимальна. Для нашей задачи кратчайший маршрут проходит через вершины 7, 5, 4, 1.

3.3.2. Метод Флойда (R.W.Floyd)

Этот алгоритм позволяет найти кратчайшие пути между любыми двумя вершинами графа.

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

На -й итерации к элементам матрицы применяется треугольный оператор

(3.18)

Для вычисления проводится сравнение величины (это длина пути от к без участия вершин, номера которых равны или больше ) с величиной (т.е. длина пути от к плюс длина пути от к ). Если путь через -ю вершину ближе, то элемент изменяет своё значение.

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

Итак, алгоритм Флойд заключается в следующем:

а) иницализируем матрицу значениями длин дуг; диагональным элементам присваиваем нулевые значения. Иницализируем нулями матрицу путей . Полагаем ;

б) рассматриваем возможность применения треугольного оператора ко всем элементам матрицы , т.е. если верно неравенство

то выполняем следующие действия:

1) заменяем в матрице элемент на сумму ;

2) в матрице элемент заменяем на ;

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

Рассмотрим пример. Граф и матрица длин приведены на рисунке 3.12.

Рисунок 3.12 – Граф и матрица длин.

Здесь все рёбра ненаправленные, кроме одного.

Выполняя пункт б) алгоритма Флойда, выделяем в матрице весов первую строку и первый столбец и пытаемся применить треугольный оператор ко всем элементам матрицы, т.е. проверяем, не является ли какой -либо путь короче, если идти через вершину . Видим, что улучшить можно только значения и . Заменяем на и устанавливаем ; аналогично заменяем на и устанавливаем Получаем

Полагаем выделяем вторую строку и второй столбец матрицы . Треугольный оператор применяется к элементам и . Новые матрицы весов и путей:

Полагаем выделяем третью строку и третий столбец матрицы . Треугольный оператор применяется к элементам и . Новые матрицы:

Полагаем выделяем четвёртую строку и четвёртый столбец матрицы . Треугольный оператор применяется к элементам и . Новые матрицы:

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

По матрице кратчайших путей можно узнать длину кратчайшего пути из любой вершины. Например . Чтобы восстановить сам ближайший путь, надо воспользоваться матрицей P . Например, если нас интересует маршрут из v в v, находим, что p=4, значит, кратчайший маршрут проходит через вершину v₄ . Ту же процедуру повторяем для каждого сегмента полученного пути 1. Так, для перехода 1 имеем р₁₄=2, а для перехода 4 р₄₅=0, для перехода 1 - , следовательно, кратчайший путь 1→ 2 →4 →5.

Приложение А

3 4

5 6

9 10

Приложение Б

1 2

	К₀	К₁	К₂	К₃	К₄
Т₁	10	5	8	11	3
Т₂	4	5	2	2	8
Т₃	0	7	10	4	6
Т₄	4	5	7	3	2
Т₅	7	0	5	4	12
Т₆	9	0	7	4	8
Т₇	5	10	11	12	0

	К₀	К₁	К₂	К₃
Т₁	5	7	6	9
Т₂	5	1	4	3
Т₃	2	4	7	1
Т₄	1	4	2	10
Т₅	0	7	4	8
Т₆	7	11	5	9
Т₇	9	5	10

	К₀	К₁	К₂	К₃	К₄
Т₁	8	11	4	3	7
Т₂	2	5	1	4	3
Т₃	8	5	7	6	9
Т₄	2	4	6	7	11
Т₅	0	11	8	7	5
Т₆	8	3	4	3	5

3 4

	К₀	К₁	К₂	К₃
Т₁	8	2	1	4
Т₂	0	8	6	9
Т₃	12	8	11	0
Т₄	5	4	7	9
Т₅	7	4	5	3
Т₆	6	0	2	4

5 6

	К₀	К₁	К₂	К₃
Т₁	4	2	4	5
Т₂	3	6	7	9
Т₃	2	4	0	6
Т₄	3	2	4	5
Т₅	5	7	4	3

	К₀	К₁	К₂	К₃
Т₁	4	2	5	3
Т₂	5	8	0	7
Т₃	2	5	3	6
Т₄	7	4	2	4
Т₅	3	4	5	1

7 8

	К₀	К₁	К₂	К₃
Т₁	4	1	2	3
Т₂	0	5	4	3
Т₃	7	1	2	4
Т₄	4	5	2	0
Т₅	3	4	2	5
Т₆	4	3	6	1

	К₀	К₁	К₂	К₃	К₄
Т₁	8	4	5	6	3
Т₂	0	4	3	1	2
Т₃	5	6	4	2	7
Т₄	4	5	11	2	0
Т₅	3	4	9	2	5
Т₆	7	9	10	4	3

	К₀	К₁	К₂	К₃
Т₁	4	0	2	3
Т₂	7	4	5	0
Т₃	5	4	7	8
Т₄	0	4	1	2
Т₅	10	7	5	9
Т₆	3	4	2	5
	К₀	К₁	К₂	К₃
Т₁	4	0	3	5
Т₂	2	4	0	6
Т₃	3	2	4	0
Т₄	2	4	3	1
Т₅	5	6	3	2
Т₆	0	3	2	4

9 10

Приложение В

n	1	2	3	4	5	6	7	8	9	0
r	4	2	1	2	1	2	2	3	1	3
r	2	2	3	1	2	2	3	3	2	3
r	2	3	2	2	2	2	2	2	2	2
r	0	3	0	2	0	0	0	0	0	0
f	4	2	5	4	2	6	3	4	3	2
f	2	1	5	6	3	3	4	4	3	5
f	5	5	4	4	2	2	4	3	3	4
f		4		3	3			2

Приложение Г

0 1

2 3

4 5

6 7

8 9

Приложение Д

n	0	1	2	3	4	5	6	7	8	9
i	16	2	6	3	5	5	17	1	4	6

Список литературы.

1. Теория сетей связи /Под ред. В.Н. Рогинского.-М.: Радио и связь, 1981.

2. Шварц М. Сети ЭВМ. Анализ и проектирование. – М.: Радио и связь,

1981.

3. Шварц М. Сети связи. Протоколы, моделирование и анализ.-М.: Наука, 1982.

4. Основы построения сетей и систем электросвязи. Методические указания и контрольные задания /Сост. А.П. Пшеничников, Г.Л. Слепова.-М.: НИС, 1991.

5. Основы сетей и систем телекоммуникации (Сост. Данилина Г.П. МУ к РГР).-Алматы: АИЭС, 1999.

6. Данилина Г.П. Сетевой метод выделения частичного подграфа с заданными свойствами на мультиграфе. Сб. «Математические методы оптимизации в горном деле».- Алма-Ата: Наука Казахстана, 1968.

7. САПР ЭВМ. Варианты заданий и методические указания. Сост. Земсков Ю.В. – ВПИ ВолгГТУ, 2002.

8. Крук Б.И., Попантонопуло В.Н., Шувалов В.П. Телекоммуникационные системы и сети. Современные технологии. –М.: Горячая линия – Телеком, 2003.

Содержание

Предисловие 3

1 Программа курса 3

1.1 Содержание учебного материала 3

1.2 Примерный перечень практических занятий 4

1.3 Перечень РГР 4

2 Методические указания к изучению теоретического материала 4

3 Методические указания к контрольной работе 6

3.1 Решение задач синтеза транспортных сетей 6

3.2 Решение задач синтеза централизованных сетей 15

3.3 Решение задач маршрутизации 22

3.3.1 Метод динамического программирования 23

3.3.2 Метод Флойда 25

Приложение А 28

Приложение Б 30

Приложение В 32

Приложение Г 33

Приложение Д 34

Список литературы 36

Сводный план, 2005 год

Галина Петровна Данилина

Проектирование сетей телекоммуникационных систем

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

Редактор Сыздыкова Ж.М.

Формат 60х84

Бумага типографская №1

Заказ цена тг.

Подписано в план « »______________

Тираж экз.

Объем уч.-изд.

Копировально-множительное бюро

Алматинского института энергетики и связи

050013, Алматы, ул. Байтурсынова, 126

n	1	2	3	4	5	6	7	8	9	0
r	4	2	1	2	1	2	2	3	1	3
r	2	2	3	1	2	2	3	3	2	3
r	2	3	2	2	2	2	2	2	2	2
r	0	3	0	2	0	0	0	0	0	0
f	4	2	5	4	2	6	3	4	3	2
f	2	1	5	6	3	3	4	4	3	5
f	5	5	4	4	2	2	4	3	3	4
f		4		3	3			2

n	1	2	3	4	5	6	7	8	9	0
r	4	2	1	2	1	2	2	3	1	3
r	2	2	3	1	2	2	3	3	2	3
r	2	3	2	2	2	2	2	2	2	2
r	0	3	0	2	0	0	0	0	0	0
f	4	2	5	4	2	6	3	4	3	2
f	2	1	5	6	3	3	4	4	3	5
f	5	5	4	4	2	2	4	3	3	4
f		4		3	3			2

n	1	2	3	4	5	6	7	8	9	0
r	4	2	1	2	1	2	2	3	1	3
r	2	2	3	1	2	2	3	3	2	3
r	2	3	2	2	2	2	2	2	2	2
r	0	3	0	2	0	0	0	0	0	0
f	4	2	5	4	2	6	3	4	3	2
f	2	1	5	6	3	3	4	4	3	5
f	5	5	4	4	2	2	4	3	3	4
f		4		3	3			2