Лекція 2
Питання лекції 2
Морфологічний опис мережі
Морфологічний опис мережі за допомогою графа
Морфологічний опис мережі за допомогою графа
Морфологічний опис мережі за допомогою графа
Морфологічний опис мережі за допомогою графа
Морфологічний опис мережі за допомогою графа
Морфологічний опис мережі за допомогою графа
Морфологічний опис мережі за допомогою графа
Морфологічний опис мережі за допомогою графа
Морфологічний опис у матричній формі
Морфологічний опис у матричній формі
Морфологічний опис у матричній формі
Потокова модель мережі
Потокова модель мережі
Потокова модель мережі
Вероятностная модель сети
Вероятностная модель сети
Вероятностная модель сети
Литература
1.12M
Category: draftingdrafting

Математичний опис мереж зв'язку

1. Лекція 2

Математичний опис мереж зв'язку
1

2. Питання лекції 2

1.
2.
3.
4.
Морфологічний опис мережі за
допомогою графа
Морфологічний опис у матричній
формі
Потокова модель мережі
Імовірнісна модель мережі
2

3. Морфологічний опис мережі

Формалізація опису мережі необхідна для рішення завдань аналізу
та синтезу ( проектування)
Опис телекомунікаційної мережі може бути:
Морфологічний
Функціональний
Морфологічний опис - це опис складу, конфігурації мережі й
взаємозв'язків її елементів
Морфоло́ гія (від греч. μορφή «форма» + греч. λογία «наука») у
широкому розумінні - наука про форми й будову.
Функціональний опис - це опис процесів функціонування мережі
й закономірностей зміни її параметрів
3

4. Морфологічний опис мережі за допомогою графа

Основні поняття теорії графів
Граф - математичний інструмент морфологічного опису мережі.
Граф G( N, M ) описує структуру мережі, у якій, кількість вершин N
відповідає кількості комутаційних центрів ( КЦ), а ребра M гілкам/лініям/каналам зв'язку, що з'єднує КЦ
Граф називається позначеним, якщо його вершини й ребра мають
ідентифікаційні написи
Граф називають орієнтованим, якщо в ньому є орієнтовані ребра
4

5. Морфологічний опис мережі за допомогою графа

Вершини nі й nj суміжні, якщо існує ребро mіj
Ребро mіj є інцендентним ( прилягаючим) для
вершин nі й nj
n1
n1
n2
m
14
m24
m42
m 23
n3
n2
m12
m34
n4
n3
n4
Приклад графа, що відображає структуру 4- вузлової мережі
5

6. Морфологічний опис мережі за допомогою графа

Властивість декомпозиції графа
Будь-який граф G ( N, M ) можна розбити на два підграфа G ( N0,
M0) і G ( NT, MT ):
G ( N, M ) = G (N0, M0 ) U G (NT, MT)
Подграф
G ( NO,MO)
Граф G ( N,M)
Підграф G ( N0, M0 ) відповідає
мережі кінцевих КЦ
Подграф
G ( Nt,Mt)
Підграф G ( NT, MT ) відповідає
мережі транзитних КЦ
6

7. Морфологічний опис мережі за допомогою графа

Ізоморфізм (от греч. ísos — рівний, однаковий, подібний і
морфо- форма).
Загальне поняття ізоморфізму означає наявність подібності в
різних об'єктів.
Два графа G ( N, M ) и G’ ( N’, M’ ) називаються ізоморфними, якщо
між множинами їхніх вершин і ребер можна існує однозначна
відповідність вершин {ni} {n’i} і ребер {mij} {m’ij}
Приклад ізоморфних графів
n1
n2
m12
n'1
m
14
m
m24
m42
23
m'14
m'24
m'42
m'23
m'34
m34
n3
n'2
m'12
n4
n'4
n'3
7

8. Морфологічний опис мережі за допомогою графа

Маршрут ( шлях)
Маршрутом m у графі називається послідовність, у якій
чередуються вершини і ребра
Послідовність починається й закінчується вершиною
Кожне ребро послідовності інциндентне двом вершинам
m = n1 U n2 U n3 U…U nk-1 U nk, де nk N
Маршрути або шляхи в графі звичайно визначаються для
виділених напрямків зв'язку (між будь-якою парою вершин)
Маршрути ( шляхи) бувають:
Незалежні - це маршрути, які не мають спільних ребер (гілок)
ni (m 1) N (m 2) и ni (m 2) N (m 1)
N (m 1)/ N (m 2) =
Залежні - маршрути із спільнимии ребрами ( гілками)
N (m 1)/ N (m 2) = N (m 2)* N (m 1) =
8

9. Морфологічний опис мережі за допомогою графа

Приклад незалежних маршрутів у мережі в напрямку 1-5
N (m 1) = { 1, 2, 3, 11, 4, 5}
N (m 2) = { 1,9,10,6,5}
1
2
10
3
11
4
9
5
8
7
6
Довжина шляху в графі - кількість вхідних у нього ребер
D(m 1) = 5 ; D(m 2) = 4
Найкоротший шлях між двома вершинами - це мінімальна відстань
між цими вершинами, що виражена в кількості ребер
min m ( 1 -5) = 4
9

10. Морфологічний опис мережі за допомогою графа

Діаметром графа D називається мінімальна відстань між
найбільш віддаленими вершинами
D= min max (i,j)
2
3
i,j
1
10
11
4
9
Діаметр графа:
D=4
5
8
7
6
Кожна вершина графа ni має степінь Deg ni .
Deg ni – це число рівне числу інцидентних ребер
Напрмклад. Deg 7 = 3; Deg 6 = 4; Deg 1= 2
10

11. Морфологічний опис мережі за допомогою графа

Переріз графа G ( N, M ) по вершинах ni являє собою множину
вершин {ni}, видалення яких приводить до утворення незв'язаних
підграфів.
Переріз графа G ( N, M ) по ребрах mij (або реберний переріз)
являє собою множину ребер {mij}, видалення яких приводить до
утворення незв'язаних підграфів.
Переріз графа G по вершинах:
{2,10,7}
1
2
10
Переріз графа G по ребрам:
{m23, m10,11, m11,6, m65}
1
3
11
4
9
2
10
3
11
4
9
5
8
7
6
Підграфи: G1(1,9,8) и G2 ( 3,4,5,6,11,)
5
8
7
6
Підграфи: G1(1,2,9,10,7,8,6) и G2 ( 3,4,5,11,)
11

12. Морфологічний опис у матричній формі

Для аналітичних досліджень застосовується матрична форма опису
структури мережі.
Основні типи матриць
Суміжності || A||
Потужностей ||V|| ( N*N)
Інциденцій ||B||
Матриці ||A|| і ||V|| мають розмірність ( N*N), де N – число вузлів (вершин)
A=
aij =
{
a21
a12

a1j

a1N
v21
v12

v1j

v1N
a21
a22

a2j

a2N
v21
v22

v2j

v2N












ai1
ai2

aij

aiN
vi1
vi2

vij

viN












aN1
aN2
aNN
vN1
vN2
aNj
1 , якщо КЦ i та КЦ j з'єднані ребром
0 , якщо КЦ i і КЦ j не з'єднані ребром
V=
vNj
vNN
vij – параметр лінії зв'язку на
гілці mij (кількість каналів)
12

13. Морфологічний опис у матричній формі

Якщо іj = jі, то матриці ||A|| та ||V|| можна представити в трикутній формі
( включені тільки наддіагональні елементи)
a21
a12

a1j

a1N
a22


a2j



a2N

aij

aiN


A=
v21
v12

v1j

v1N
v22

v2j

v2N




vij

viN


V=
aNN
vNN
Приклад опису 5 вузлової мережі
2
1
1
3
2
3
5
4
4
5
1
2
3
4
5
0
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
2
3
4
5
1
2
3
4
5
0
1
0
1
1
0
1
1
1
0
1
1
1
1
0
13

14. Морфологічний опис у матричній формі

Матриця інцендентності
||B||
розмірністю N*M, у якій
||В|| = {bij},
bij
=
{
-
це
матриця
1 , якщо ребро mij інцендентне вершині ni
0 , якщо ребро mij не інцендентне вершині ni
Між матрицями суміжності та інцендентності існує взаємна відповідність
А=ВТВ – 2*I,
де
ВТ – транспонована матриця інцендентності,
I–
одинична матриця, розмірності М*М
14

15. Потокова модель мережі

Для
функціонального
використовуються
Потокова модель мережі
Імовірнісна модель мережі
опису
мережі
Функціональний опис мережі характеризує
основні процеси її функціонування:
Передача повідомлень
Розподіл інформації
Вихід з ладу й відновлення елементів мережі
Якість обслуговування на галузях і напрямках
зв'язку мережі
15

16. Потокова модель мережі

Потокова модель характеризує здатність мережі по передачі
повідомлень від джерел інформації до споживачів в умовах
нормального її функціонування
Процес передачі повідомлень по мережі можна описати матрицею
C11(t11,p11) C12(t12,p12)
C22(t22,p22)
C=


C1j(t1j,p1j)
C2j(t2j,p2j)

Cij(tij,pij)





C1n(t1n,p1n)
C2n(t2n,p2n)

Cin(tin,pin)

Cnn(tnn,pnn)
де Cij(tij,pij) – кількість повідомлень, обслужених на гілці mіj за час tіj
при дотриманні імовірнісно-часового параметра ріj
Cij(tij,pij) = 0 при аij =0 (за умови відсутності гілки mіj)
16

17. Потокова модель мережі

Середня кількість одночасно функціонуючих
повідомлень у мережі можна розрахувати у вигляді
Сф = SS Cij(tij,pij)
Середня кількість повідомлень одночасно
переданих у напрямку зв'язку можна також
розрахувати як суму переданих повідомлень по всіх
галузях, що входить в усі шляхи даного напрямку
Сн =
SS Cм(tij,pij)
17

18. Вероятностная модель сети

У будь-який довільний момент часу t канал галузі mіj може могти
Вільний/ Зайнятий
Для сталого режиму роботи мережі знаходження кожної гілки mіj
у зайнятому стані можна описати матрицею
Матрица вероятностей отказа в обслуживаниии
pm11( t)
P=
pm12( t)
pm22( t)



pm1j( t)
pm2j1( t)


pm1n( t)
pm2n( t)



pmij( t)

pmin( t)


pmnn( t)
де pmij(t)
– імовірність відмови в обслуговуванні на гілціі mіj у
довільний момент часу t
18

19. Вероятностная модель сети

Оцінити ймовірність обслуговування повідомлення в напрямку
зв'язку можна за допомогою формули.
якщо m=1 ( одному шляхи встановлення з'єднання)
q=
П(1 – pij)
ij
p= 1- q = 1-
П(1 – pij)
ij
якщо m=k>1 ( при k шляхів встановлення з'єднання)
Q=1-
П(1 - П(1 – pij))
k
P=
ij
П(1 - П(1 – pij))
k
ij
19

20. Вероятностная модель сети

Надійність мережі може бути описана у
вигляді матриці
Матрица вероятностей безотказной работы
rm11( t)
R=
rm12( t)
rm22( t)



rm1j( t)
rm2j1( t)

rmij( t)

rm1n( t)
rm2n( t)



rmin( t)



rmnn( t)
де rmij(t)
– імовірність безвідмовної роботи галузі mіj у
довільний момент часу t
20

21. Литература

Романов А. И. Телекоммуникационные сети и управление: Учебное
пособие –К. ИПЦ « Киевский университет», 2003, -247с.
Корнышев Ю.Н., Фань Г.Л. Теория распределения информации – М.:
Радио и связь, 1985
Сети ЭВМ. Под редакцией В.М. Глушкова – М.: Связь, 1977
Бусленко Н. П. Моделирование сложных систем – М. : Наука, 1978
Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового
обслуживания – М.: Наука, 1966
Клейнрок Л. Коммутационные сети – М.: Наука, 1970
Шварц М. Сети ЭВМ. Анализ и проектирование - М.: Радио и связь,
1981
Советов Б.Я. и др. Построение сетей интегрального обслуживания –
Л.: Машиностроение, Лен отд-е, 1990
Клейнрок Л. Вычислительные сети с очередями – М.: Мир, 1979
Хилс М.Т. Принципы коммутации в электросвязи - М.: Радио и связь,
1984
Френк Г. , Фриш И. Сети, связь и потоки – М.: Связь, 1978
21
English     Русский Rules