Методика решения задачи размещения

Считаются заданными: площадь региона , количество абонентов в сети , капитальные затраты на установку одного ВЦ и АП и соответственно; стоимость 1 км магистрального канала связи между ВЦ W₃ и стоимость 1 км канала связи между АП и ВЦ . Нужно определить координаты установки ВЦ и АП, их количество в регионе, а также конфигурацию системы обмена данными, чтобы обеспечить минимум затрат и возможность обработки объемов информации.

Из очевидных геометрических соображений следует, что капитальные затраты на магистральные каналы связи между ВЦ можно определить из следующего выражения:

(9)

где — индекс рассматриваемого ВЦ; — индексы находящегося правее и — находящегося ниже ВЦ (см. рис. 2); —проекция прямой, связывающей -й ВЦ с ВЦ, находящиеся ниже по диагонали, на вертикальную и горизонтальную оси координат, жестко связанных с контурами региона.

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

Основываясь на аналогичных рассуждениях, можно прийти к выводу, что минимизация суммарной длины каналов связи между ВЦ и АП также достигается при равномерном размещении АП в зоне обслуживания ВЦ.

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

.

Здесь и — размеры зоны, заданной в виде прямоугольника со сторонами и (рис. 2).

Для конкретных структур сети ЭВМ значения , , и могут быть вы­браны из некоторого множества вариантов. В частности, с учетом рекомендаций о равномерном распределении ВЦ и АП в регионе значения и для любого варианта могут быть вычислены следующим образом:

, (11)

, (12)

. (13)

Найдем частные производные от полных затрат W по переменным R н г с целью определения экстремальных значений этих величин для функции W и приравняем их нулю:

(14)

Решая совместно эти два уравнения как систему путем подстановки, получим искомое соотношение, которое является уравнением 11-й степени относительно R:

(15)

Выражения для коэффициентов в общем виде необычайно громоздки, поэтому рассмотрим пример расчета со следующими данными: [км²]; ; [тыс. грн.]; [тыс. грн.]; [тыс. грн./км]; [тыс. грн./км].

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

1) среднее расстояние между АП и ВЦ:

км;

2) оптимальное число узлов (ВЦ в данном случае) в сети:

3) среднее число АП, подсоединяемых в каждом узле,

где — среднее число абонентов в одном узле.

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

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

Предположим, что в результате вычислений получилось равно восьми, а реальное место расположение ВЦ, объединяемых в сеть, соответствует схеме, показанной на рис. 3.

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

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

Для решения задачи минимизации структуры воспользуемся моделью сети в виде взвешенного графа, у которого веса дуг характеризуют, например, протяженности каналов между соответствующими узлами ИС. Так как рассматривается сеть с относительно малым числом ребер, для нее удобным способом решения задачи минимизации структуры является алгоритм Краскала, который заключается в следующем [1].

 

Рисунок 3 - План размещения узлов в синтезируемой сети

 

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

Затем, пользуясь списком, строим минимальное покрывающее дерево, начиная с первого ребра и добавляя последующие по порядку. Если очередное выбранное ребро приводит к образованию цикла, то его отбрасываем. После выбора ребра ( —число вершин графа) процесс заканчивается.

 

Таблица 1 – Список ребер с их весовыми значениями

 

Вес ребра	Ребра	Примечание
0,5	(1,2)
1,0	(1,8), (3,6), (6,7)
1,8	(3,7) отбрасываем	Приводит к циклу
1,9	(2,3), (2,7) отбрасываем
2,0	(2,6) отбрасываем
2,1	(7,8) отбрасываем
2,2	(1,7) отбрасываем
2,3	(1,3), (4,5) и (1,3)	(1,3) отбрасываем
2,8	(1,6) отбрасываем
3,0	(6,4)
3,5	(3,4) отбрасываем
5,5	(5,6) отбрасываем
5,8	(5,7) отбрасываем
8,0	(1,5) отбрасываем