Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Визначення місць розміщення мережених вузлів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут телекомунікації, радіоелектроніки і електронної техніки
Факультет:
Не вказано
Кафедра:
Кафедра Телекомунікацій
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Методи математичного моделювання
Група:
ІМЗм-12
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Інститут телекомунікації, радіоелектроніки і електронної техніки
Кафедра Телекомунікацій
Лабораторна робота №1
з дисципліни : “Методи математичного моделювання”
на тему: “Визначення місць розміщення мережених вузлів”
Львів 2008
МЕТА РОБОТИ
Визначити оптимальне місце розміщення кожного мережевого вузла для проектування мереж арифметичним, геометричним методом та при внесенні перешкоди у район підключення.
ТЕОРЕТИЧНІ ВІДОМОСТІ
За визначенням мережевий вузол - представляє собою центральну точку в зоні підключення, яка відповідає за передавання та обробку інформації.
Якщо між місцями розміщення джерел інформації та вузлом існують однозначні лінійні залежності, тоді вигідно застосувати відомий метод визначення центру ваги. В літературі цей метод часто називають арифметичним.
Місце розміщення стовпчика визначається таким чином, щоб як зліва, так і справа від нього була приблизно однакова кількість джерел інформації. Якщо позначити суму джерел і приймачів інформації в деякому стовпчику через Qsj, тоді для кожного стовпчика Sk можна записати модуль різниці сум джерел інформації, просумованих по стовпчиках, розміщених від нього зліва і справа, у вигляді:
Dsk= (1)
Критерій вибору місця розміщення стовпчика буде мати вигляд:
Dsk ( min ( 2 )
Аналогічно для вибору місця розміщення рядка необхідно знайти такий рядок zl , для якого зверху і знизу буде приблизно однакова кількість джерел інформації.
Для модуля різниці сум джерел інформації, просумованих по рядках, розміщених зверху і знизу від рядка zl , справедливий вираз:
Dzl = ( 3 )
Критерій вибору місця розміщення рядка, як і для стовпчика, має вид:
Dzl ( min ( 4 )
Для наочності розрахунку матриця доповнюється чотирма рядками і стовпчиками. Рядок Dsk відповідає виразу ( 1 ), а стовпчик Dzl - виразу ( 3 ). Одержані суми по стовпчиках і по рядках дозволяють здійснювати простий контроль обчислень, так як одержані суми повинні бути однакові.
При розробці оптимальних телекомунікаційних мереж необхідно мінімізувати необхідні затрати (капітальні вкладення, розхід кабелю та інші затрати). В геометричному методі для вибору місця розміщення рядка і стовпчика використовуються самі затрати на лінію.
Для всіх джерел інформації, розміщених зліва від стовпчика sk, можна визначити “горизонтальний” компонент затрат наступним чином:
Ask зліва = Ask-1 зліва + ( 5 )
Таким же чином можна визначити “горизонтальний” компонент затрат для всіх джерел інформації, розміщених справа від стовпчика sk :
Ask справа = Ask+1 справа + ( 6 )
Загальні затрати на лінію Ask одержуються у вигляді сум обох компонентів (рис.3):
Ask = Ask-1 зліва + Ask+1 справа + ( 7 )
Критерій вибору місця розміщення стовпчика має вигляд
Ask ( min ( 8 )
Аналогічно після сумування затрат на лінію, для джерел інформації, розміщених зверху і знизу від рядка zl, справедливий вираз:
Azl = Azl-1 зверху + Azl+2 знизу + ( 9 )
Шукане місце розміщення рядка повинно задовільняти умові
Azl ( min ( 10 )
Обраховані затрати, необхідні для вибору місця розміщення рядка і стовпчика з допомогою цього методу, який називається геометричним методом, більш значимі. Тому для великих мереж чи районів підключення має сенс робити розрахунок за допомогою ЕОМ.
В реальних умовах можуть виникнути причини (наприклад, водяні перешкоди, перепад висот, скальний грунт, залізничні споруди і т.д.), що не дозволяють виконувати прокладку траси. Перешкода повинна обходитись при прокладці траси, або на її подолання необхідно додаткові затрати. Якщо для спрощення рахувати, що найменший перерозхід затрат буде мати місце при обході перешкоди (необхідний обхід), то можливий єдиний підхід до розгляду впливу усіх перешкод.
Перешкода (наприклад, русло річки) буде перешкодою лише в тому випадку, якщо вона перетинається з трасою. Однак, якщо місця розміщення джерел встановлені, то необхідність подолання перешкоди залежить від місця розсташування вузла. Якщо в мережі чи в районі підключення є перешкоди, для обходу яких потрібне значне завищення затрат на лінію, то кожний квадрат сітки повинен послідовно прийматись за місце розміщення вузла і з урахуванням можливого напрямку прокладки траси повинні розраховуватися сукупні затрати на лінію.
Для скорочення збільшеного об’єму обсчислювань в цьому випадку пропонується наступний метод. Спочатку визначають місця розміщення рядків і стовпчиків при відсутності перешкоди. Після цього знову розраховують сукупні затрати на лінію (“горизонтальні” і “вертикальні” компоненти) для початкового квадрату растрової сітки і для всіх восьми суміжних квадратів, враховуючих необхідні напрямки трас.
Якщо в районі підключення існує ділянка дії перешкоди, то очевидно, що горизонтально розміщені перешкоди можуть викликати принципіально тільки “горизонтальний” компонент, а вертикально розміщені – “вертикальний” компонент перевитрат затрат.
Якщо перешкода займає непарну кількість стовпчиків, наприклад ((l-р), …, (l-2), (l-1), (l), (l+1), (l+2), …, (l+p)(, і очіковане місце розміщення вузла лежить вище перешкоди, то утворюються перевитрати на лінію Mj, які можуть вираховуватися по сумах джерел для стовпчиків нижче перешкоди Qs j нижн. Якщо очікуване місце розміщення вузла лежить вище перешкоди, то визначальну роль відіграють суми джерел для стовпчиків вище перешкоди Qs j верхн.
Дослідження показали, що загальні перевитрати МАj так само, як перевитрати Мj, залежать від довжини перешкоди. Якщо цю залежність виразити через множник fj, то перевитрати на лінію можна вирахувати так: MAj = 2 fk Mk (11)
Якщо перешкода розміщується на лінії растрової сітки між рядками h і h+1, то для Mj справедливо
Mj верхн. = 2 gij (12)
або
Mj нижн. = 2 gij (13)
де gij – кількість джерел і приймачів інформації в квадраті Aij.
ХІД РОБОТИ
Задати район підключення у вигляді квадрату 15. Кількість джерел інформації у кожній з клітинок вибираємо довільно.
Знайти місце розсташування вузла арифметичним методом.
На одній площині побудувати графіки
Qsj ліве
-Сумування кількості вузлів з ліва
Qsj праве
-Сумування кількості вузлі справа
Dsk
-Різниця Qsj ліве- Qsj праве
Qzi верх
-Сумування кількості вузлів верху
Qzi нижн
-Сумування кількості вузлів знизу
Dzl
-Різниця Qzi верх- Qzi нижн
Знайти місце розсташування вузла геометричним методом
На одній площині побудувати графіки
Ask ліве
-Сумування кількості вузлів з ліва
Ask праве
- Сумування кількості вузлівправа
Ask
-Сума Ask ліве+ Ask праве
Azl верхн
-Сумування кількості вузлів верху
Azl нижн
-Сумування кількості вузлів знизу
Azl
-Сума Azl верхн+ Azl нижн
Внести перешкоду у вказаний район підключення. Подивитись, як змінилося місце розсташування вузла.
РЕЗУЛЬТАТИ ЕКСПЕРИМЕНТУ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Qzi
Sym Qzi
Sym Qzi2
Dzi
1
7
7
7
17
17
13
12
12
12
12
12
10
10
10
10
168
168
2806
2638
2
9
13
13
13
13
13
12
11
11
9
16
8
8
8
8
165
333
2638
2305
3
6
6
6
13
15
12
16
16
16
9
9
9
9
13
13
168
501
2473
1972
4
12
6
14
13
15
12
16
16
16
9
19
19
19
19
19
224
725
2305
1580
5
12
6
15
15
15
8
8
8
8
9
19
20
20
20
17
200
925
2081
1156
6
12
9
9
9
9
10
10
20
8
9
19
12
12
17
17
182
1107
1881
774
7
12
12
9
9
9
18
10
20
11
13
11
9
24
7
7
181
1288
1699
411
8
12
12
18
18
9
18
10
20
11
13
11
11
24
6
7
200
1488
1518
30
9
8
10
10
10
8
18
10
20
11
13
20
20
24
6
7
195
1683
1318
365
10
9
9
9
9
14
14
14
14
11
13
13
8
8
8
8
161
1844
1123
721
11
11
11
11
17
14
18
18
18
18
18
18
8
19
8
13
220
2064
962
1102
12
11
11
11
17
14
9
9
9
6
15
15
8
19
8
13
175
2239
742
1497
13
13
13
16
17
17
17
15
9
6
6
6
16
19
8
13
191
2430
567
1863
14
13
8
8
8
11
16
16
9
6
10
10
16
16
16
16
179
2609
376
2233
15
13
8
14
11
11
16
16
9
19
11
11
11
11
18
18
197
2806
197
2609
Qsj
160
141
170
196
191
212
192
211
170
169
209
185
242
172
186
Sym Qsj
160
301
471
667
858
1070
1262
1473
1643
1812
2021
2206
2448
2620
2806
Sym Qsj2
2806
2646
2505
2335
2139
1948
1736
1544
1333
1163
994
785
600
358
186
Dsj
2646
2345
2034
1668
1281
878
474
71
310
649
1027
1421
1848
2262
2620
Згідно з арифметичним методом вузол розташовується в квадраті А88
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Qzi
Az verh
Aznuz
Azl
1
7
7
7
17
17
13
12
12
12
12
12
10
10
10
10
168
0
19880
19880
2
9
13
13
13
13
13
12
11
11
9
16
8
8
8
8
165
168
17242
17410
3
6
6
6
13
15
12
16
16
16
9
9
9
9
13
13
168
501
14769
15270
4
12
6
14
13
15
12
16
16
16
9
19
19
19
19
19
224
1002
12464
13466
5
12
6
15
15
15
8
8
8
8
9
19
20
20
20
17
200
1727
10383
12110
6
12
9
9
9
9
10
10
20
8
9
19
12
12
17
17
182
2652
8502
11154
7
12
12
9
9
9
18
10
20
11
13
11
9
24
7
7
181
3759
6803
10562
8
12
12
18
18
9
18
10
20
11
13
11
11
24
6
7
200
5047
5285
10332
9
8
10
10
10
8
18
10
20
11
13
20
20
24
6
7
195
6535
3967
10502
10
9
9
9
9
14
14
14
14
11
13
13
8
8
8
8
161
8218
2844
11062
11
11
11
11
17
14
18
18
18
18
18
18
8
19
8
13
220
10062
1882
11944
12
11
11
11
17
14
9
9
9
6
15
15
8
19
8
13
175
12126
1140
13266
13
13
13
16
17
17
17
15
9
6
6
6
16
19
8
13
191
14365
573
14938
14
13
8
8
8
11
16
16
9
6
10
10
16
16
16
16
179
16795
197
16992
15
13
8
14
11
11
16
16
9
19
11
11
11
11
18
18
197
19404
0
19404
Qsj
160
141
170
196
191
212
192
211
170
169
209
185
242
172
186
Ask l
0
160
461
932
1599
2457
3527
4789
6262
7905
9717
11738
13944
16392
19012
Ask p
20272
17626
15121
12786
10647
8699
6963
5419
4086
2923
1929
1144
544
186
0
Ask
20272
17786
15582
13718
12246
11156
10490
10208
10348
10828
11646
12882
14488
16578
19012
Згідно з геометричним методом вузол розташовується в квадраті А88
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Qzi
7
7
7
17
17
13
12
12
12
12
12
10
10
10
10
168
9
13
13
13
13
13
12
11
11
9
16
8
8
8
8
165
6
6
6
13
15
12
16
16
16
9
9
9
9
13
13
168
12
6
14
13
15
12
16
16
16
9
19
19
19
19
19
224
12
6
15
15
15
8
8
8
8
9
19
20
20
20
17
200
12
9
9
9
9
10
10
20
8
9
19
12
12
17
17
182
12
12
9
9
9
18
10
20
11
13
11
9
24
7
7
181
12
12
18
18
9
18
10
20
11
13
11
11
24
6
7
200
8
10
10
10
8
18
10
20
11
13
20
20
24
6
7
195
9
9
9
9
14
14
14
14
11
13
13
8
8
8
8
161
11
11
11
17
14
18
18
18
18
18
18
8
19
8
13
220
11
11
11
17
14
9
9
9
6
15
15
8
19
8
13
175
13
13
16
17
17
17
15
9
6
6
6
16
19
8
13
191
13
8
8
8
11
16
16
9
6
10
10
16
16
16
16
179
13
8
14
11
11
16
16
9
19
11
11
11
11
18
18
197
160
141
170
196
191
212
192
211
170
169
209
185
242
172
186
Qsj
0
160
461
932
1599
2457
3527
4789
6262
7905
9717
11738
13944
16392
19012
Ask l
20272
17626
15121
12786
10647
8699
6963
5419
4086
2923
1929
1144
544
186
0
Ask p
20272
17786
15582
13718
12246
11156
10490
10208
10348
10828
11646
12882
14488
16578
19012
Ask
0
0
0
0
0
0
526
702
526
0
0
0
0
0
0
Ман
20272
17786
15582
13718
12246
11156
11016
10910
10874
10828
11646
12882
14488
16578
19012
Askн=Ask+Man
0
0
0
0
0
0
620
866
620
0
0
0
0
0
0
Маv
20272
17786
15582
13718
12246
11156
11110
11074
10968
10828
11646
12882
14488
16578
19012
Askv=Ask+Mav
Наявність перешкоди призвела до того, що оптимальне місце розміщення вузла змістилось в квадрат А8_10.
ВИСНОВОК
На цій лабораторній роботі я визначив місце розміщення вузла шляхом оцінки кількості джерел і приймачів інформації і місць їх виникнення, тобто за арифметичним методом отримав розміщення вузла в квадраті А88. При використанні методу мінімізації затрат (геометричний метод) отримав, що оптимальне місце розміщення вузла є квадрат А88. Для визначення впливу місцевих умов на оптимальне міісце розміщення вузла ввів перешкоду у стовпцях 7,8,9 і провівши розрахунки визначив, що оптимальне місце розміщення вузла змістилось в квадрат А8_10.
10.02.2013 23:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора