К оглавлению

ПРИМЕНЕНИЕ ЗАДАЧИ О Р-ЦЕНТРАХ ДЛЯ СИНТЕЗА ФИЗИЧЕСХОЙ СТРУКТУРЫ КОМПЬЮТЕРНОЙ СЕТИ

В.Н Изотов, ПВ. Комогорцеа, А.В Изотов, Тульское ВАИУ, Россия

Повышение эффективности управления в режиме реального времени невозможно без использования современных информационных технологий. К их числу относится и внедрение перспективных АСУ специального назначения на базе компьютерной сети (КС).

В соответствии с двухразовой моделью “клиент – сервер” каждый узел сети может оборудоваться либо как центр обработки информации (ЦОИ), либо как автоматизированное рабочее место должностного лица (АРМ ДЛ). Если физическая структура сети задана, то при проектировании либо реконфигурации КС. возникает задача выбора числа и мест размещения ЦОИ по узлам сети. На время решения данной задачи накладывается жесткое ограничение, т. к. реконфигурация КС проводится в режиме реального времени.

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

Тогда задана выбора чисти и мест размещения ЦОИ в КС по критерию максимума интенсивности информационных потоков при ограничении на задержку сообщения в сети формулируется следующим образом: требуется определить минимальное число центров обработки информации, обслуживающих информационные запросы от должностных лиц и такое их размещение в узлах сети, чтобы значение времени задержки передачи сообщения для каждого АРМ ДЛ не превышало допустимой величины, а суммарная приведенная интенсивность поступления запросов на узлы КС, в местах расположения которых будут размещены ЦОИ бьла при этом максимальной. Для расчета времени задержки передачи сообщения предлагается использование имитационной модели.

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

при ограничениях

где значения “весов” соответствующих вершин графа.

dij – кратчайшме пути между соответствующими вершинами графа Тmax - максимально допустимое время задержки передачи сообщения.

Для решения данной задачи используется метод. основанный на схеме ветвей и границ. Замена условия целочисленности условием 0 ? хi ? 1, I = 1,…,N позволяет использовать для вычисления нижней границы решения либо точные методы, например, симплексный метод или метод множителей Лагранжа, либо использовать для оценки нижней границы приближенное решение двойственной задачи [2], так как, оптимальные решения основной и двойственной задачи совпадают, те. Q = Z. По отношению к основной задаче двойственная задача

имеет следующий вид: найти при ограничениях

переменные двойственной задачи.

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

Таблица

Таким образом. использование данного подхода, позволяет решить задачу выбора оптимального числа и мест размещения ЦОИ в КС в условиях реального масштаба времени при реконфигурации АСУ специального назначения.

ЛИТЕРАТУРА

1. Кристофидес Н   Теория графов. Алгоритмический подход. - М: МИР, 1978

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М: Мука, 1987.