Методика решения задачи размещения
Считаются заданными: площадь региона , количество абонентов в сети , капитальные затраты на установку одного ВЦ и АП и соответственно; стоимость 1 км магистрального канала связи между ВЦ W3 и стоимость 1 км канала связи между АП и ВЦ . Нужно определить координаты установки ВЦ и АП, их количество в регионе, а также конфигурацию системы обмена данными, чтобы обеспечить минимум затрат и возможность обработки объемов информации.
Из очевидных геометрических соображений следует, что капитальные затраты на магистральные каналы связи между ВЦ можно определить из следующего выражения:
(9)
где — индекс рассматриваемого ВЦ; — индексы находящегося правее и — находящегося ниже ВЦ (см. рис. 2); —проекция прямой, связывающей -й ВЦ с ВЦ, находящиеся ниже по диагонали, на вертикальную и горизонтальную оси координат, жестко связанных с контурами региона.
Величина не зависит от значений и . В то же время согласно неравенству Коши вторая сумма в квадратных скобках формулы (9) минимизируется при для любых .
Основываясь на аналогичных рассуждениях, можно прийти к выводу, что минимизация суммарной длины каналов связи между ВЦ и АП также достигается при равномерном размещении АП в зоне обслуживания ВЦ.
Исходя из изложенного, определяют капитальные вложения на создание всех ВЦ к АП в обслуживаемом регионе. Опуская промежуточные алгебраические преобразования в формулах, полученных из геометрических построений, приведем основное соотношение для постановки задачи минимизации затрат на проектируемую сеть:
.
Здесь и — размеры зоны, заданной в виде прямоугольника со сторонами и (рис. 2).
Для конкретных структур сети ЭВМ значения , , и могут быть выбраны из некоторого множества вариантов. В частности, с учетом рекомендаций о равномерном распределении ВЦ и АП в регионе значения и для любого варианта могут быть вычислены следующим образом:
, (11)
, (12)
. (13)
Найдем частные производные от полных затрат W по переменным R н г с целью определения экстремальных значений этих величин для функции W и приравняем их нулю:
(14)
Решая совместно эти два уравнения как систему путем подстановки, получим искомое соотношение, которое является уравнением 11-й степени относительно R:
(15)
Выражения для коэффициентов в общем виде необычайно громоздки, поэтому рассмотрим пример расчета со следующими данными: [км2]; ; [тыс. грн.]; [тыс. грн.]; [тыс. грн./км]; [тыс. грн./км].
Найдя корни алгебраического уравнения, для данных значений коэффициентов, найдем множество значений корней . Из этого множества, естественно, исключаются элементы, определяющие мнимые и отрицательные значения, остальные проверяются на соответствие физическому смыслу задачи. Выбрав одно наиболее подходящее значение км, находим далее соответствующие этому значению величины, определяющие оптимальное распределение затрат для синтезируемой сети:
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) отбрасываем |
Дата добавления: 2015-04-10; просмотров: 750;