2.3 Вибір місця розташування вузла комутації

Комутаційних вузол (КВ) проектованої мережі доступу повинен розташовуватися таким чином, щоб було забезпечено мінімізацію довжини кабельних трактів від комутаторів доступу до комутаторів розподілення (магістральних лінків). Такий спосіб розташування КВ дозволить значно зменшити вартість побудови мережі. Для визначення місце розташування комутаційного вузла можна застосувати декілька різних методів, однак найбільш простим та легким є спосіб запропонований теорією графів. Згідно з теорією графів комутаційний вузол доцільно розташувати у точці, яку називають медіаною графу. Для визначення медіани графу спочатку, представимо нашу мережу у вигляді графу, де в якості ребер будуть відстані між будинками, розраховані по довжині кабельної каналізації, а в якості вершин будуть самі будинки, в яких розташовані кінцеві вузли. Таким чином ми отримуємо модель нашої мережі у вигляді в зваженого графу (див. рисунок 2.4). Відповідно до наведеного графу сформуємо матрицю ваг та зведемо її в таблицю 2.1.

Рисунок 2.4 – Модель мережі у вигляді графу

Таблиця 2.1 – Матриця ваг побудованого графу

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
1	-	50	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
2	50	-	40	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
3	-	40	-	85	-	60	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
4	-	-	85	-	40	65	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
5	-	-	-	40	-	-	-	-	-	-	-	-	-	-	-	-	-	-	85	85	-	-
6	-	-	60	65	-	-	40	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
7	-	-	-	-	-	40	-	65	-	50	-	-	-	-	-	-	-	-	-	-	-	-
8	-	-	-	-	-	-	65	-	40	85	-	-	-	-	-	-	-	-	-	-	-	-
9	-	-	-	-	-	-	-	40	85	-	-	-	-	-	95	95	-	-	-	-	-	-
10	-	-	-	-	-	-	50	-	-	-	40	-	-	-	-	-	-	-	-	-	-	-
11	-	-	-	-	-	-	-	-	-	40	-	105	-	-	-	-	-	-	-	-	-	-
12	-	-	-	-	-	-	-	-	-	-	105	-	40	-	-	-	-	-	-	-	-	-
13	-	-	-	-	-	-	-	-	-	-	-	40	-	85	-	-	-	-	-	-	-	-
14	-	-	-	-	-	-	-	-	-	-	-	-	85	-	40	-	-	-	-	-	-	-
15	-	-	-	-	-	-	-	-	95	-	-	-	-	40	-	50	-	-	-	-	-	-
16	-	-	-	-	-	-	-	-	95	-	-	-	-	-	50	-	40	-	-	-	-	-
17	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	40	-	40	-	-	-	-
18	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	40	-	40	-	-	-
19	-	-	-	-	85	-	-	-	-	-	-	-	-	-	-	-	-	40	-	50	-	-
20	-	-	-	-	85	-	-	-	-	-	-	-	-	-	-	-	-	-	50	-	40	-
21	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	40	-	50
22	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	50	-

Для пошуку медіани графу спочатку треба побудувати мінімальне покривне дерево. Для вирішення цієї задачі скористаємось алгоритмом Прима, який реалізується шляхом присвоєння міток вершин , які вводяться в шуканий граф , і послідовного введення в нього найбільш коротких ребер , загальна кількість яких не повинна перевищувати і при цьому забезпечувати зв'язність між усіма вершинами покривного дерева . Покрокова форма алгоритму Приму має наступний вигляд:

Крок 0. Шукана мережа в початковому стані містить вершин і не містить ребер. Обирається одна довільна вершина та позначається , як «вибрана». Решта вершин позначаються , як «невибрані».

Крок 1 . Відшукується ребро , що належить з мінімальною вагою, у якого вершина належить множині « обраних » вершин , а вершина - до множині « невибраних » вершин.

Крок 2 . Ребро включається в шукану мережу , а вершина виключається з підмножини « невибраних » вершин і включається в підмножину « обраних » вершин. Якщо підмножина « невибраних » вершин виявилося порожнім - кінець роботи алгоритму . В іншому випадку - перехід до кроку 1 .

Знайдене за допомогою алгоритма Прима мінімальне покривне дерево зображено на рисунку 2.5.

Рисунок 2.5 – Мінімальне покривне дерево

Для вирішення задачі щодо оптимально місця розташування комутаційного вузла, для побудованого мінімального покривного дерева знайдемо медіану графу. Вершина , що належить , являється медіаной графу , якщо вона задовольняє умові: .

Величина називається медіанної довжиною графа і являє собою найменшу сумарну довжину ребер, що з'єднують вершину з іншими вершинами графа. Алгоритм визначення медіани графу включає наступні кроки:

Крок 1. У вихідній матриці ваг , яка відповідає довжині ребер, знайти суму елементів для кожного рядка.

Крок 2. Серед множині значень знайти мінімальне значення. Вершина і буде медіаною графа.

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

Відповідно до отриманих розрахунків медіаною графу є дві вершини за номерами 11 та 12, сумарна довжина кабелю до яких становить 5610м. Враховуючи напрям прокладки магістрального кабелю до транспортної мережі IP\VPLS в якості місця розташування комутаційного вузла обираємо будинок за номером 12.

Таблиця 2.2 – Матриця пошуку медіану графу

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	
1	-	50	90	215	255	150	190	255	295	240	280	385	425	510	550	600	640	680	720	770	810	860	8970
2	50	-	40	165	205	100	140	205	245	190	230	335	375	460	500	550	590	630	670	720	760	810	7970
3	90	40	-	125	165	60	100	165	205	150	190	295	335	420	460	510	550	590	630	680	720	770	7250
4	215	165	125	-	40	65	105	170	210	155	195	300	340	425	465	515	555	595	635	685	725	775	7460
5	255	205	165	40	-	105	145	210	250	195	235	340	380	465	505	555	595	635	675	725	765	815	8260
6	150	100	60	65	105	-	40	105	145	90	130	235	275	360	400	450	490	530	570	620	660	710	6290
7	190	140	100	105	145	40	-	65	105	50	90	195	235	320	360	410	450	490	530	580	620	670	5890
8	255	205	165	170	210	105	65	-	40	115	155	260	295	380	420	470	510	550	590	640	680	730	7010
9	295	245	205	210	250	145	105	40	-	155	195	300	335	420	460	510	550	590	630	680	720	770	7810
10	240	190	150	155	195	90	50	115	155	-	40	145	185	270	310	360	400	440	480	530	570	620	5690
11	280	230	190	195	235	130	90	155	195	40	-	105	145	230	270	320	360	400	440	490	530	580	5610
12	385	335	295	300	340	235	195	260	300	145	105	-	40	125	165	215	255	295	335	385	425	475	5610
13	425	375	335	340	380	275	235	295	335	185	145	40	-	85	125	175	215	255	295	345	385	435	5680
14	510	460	40	425	465	360	320	380	420	270	230	125	85	-	40	90	130	170	210	260	300	350	5640
15	550	500	460	465	505	400	360	420	460	310	270	165	125	40	-	50	90	130	170	220	260	310	6260
16	600	550	510	515	555	450	410	470	510	360	320	215	175	90	50	-	40	80	120	170	210	260	6660
17	640	590	550	555	595	490	450	510	550	400	360	255	215	130	90	40	-	40	80	130	170	220	7060
18	680	630	590	595	635	530	490	550	590	440	400	295	255	170	130	80	40	-	40	90	130	180	7540
19	720	670	630	635	675	570	530	590	630	480	440	335	295	210	170	120	80	40	-	50	90	140	8100
20	770	720	680	685	725	620	580	640	680	530	490	385	345	260	220	170	130	90	50	-	40	90	8900
21	810	760	720	725	765	660	620	680	720	570	530	425	385	300	260	210	170	130	90	40	-	50	9620
22	860	810	770	775	815	710	670	730	770	620	580	475	435	350	310	260	220	180	140	90	50	-	10620