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

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