Алгоритмы оптимизации производительности среды автоматизированной системы управления радиоэлектронных предприятий

Размещено на http://www.allbest.ru/

Алгоритмы оптимизации производительности среды АСУ радиоэлектронных предприятий

Георгиевский А.Е.

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

При разработке среды АСУ РП особенное внимание уделяется одному из основных ее параметров - повышению производительности. Производительность среды - это ее способность передавать заданный объем данных в единицу времени без искажений. Параметр "производительность" оценивают двумя способами. Первый - по количеству произведенной работы в соответствии с предназначением в единицу времени (секунда, минута, час), т.е. по объему полезной информации, представленной в форме двоичных элементарных электрических посылок (в "цифре"), [бит/с]. Второй - по среднему времени задержки стандартного сообщения в среде, [с]. За стандарт принимается байт или килобайт двоичной информации. Чем меньше задержка в среде, тем она производительнее.

1. Одной из трудных проблем проектирования является оптимальный выбор пропускных способностей (ВПС) из конечного набора их возможных значений [1]. Предположим, что интересующий нас параметр имеет непрерывные значения в некотором диапазоне (лi=Сi). здесь лi - среднее количество информации [бит/с], которое проходит по i-му каналу. Задача ВПС должна быть решена так, чтобы i-й канал имел пропускную способность, не меньшую требуемой и чтобы выполнялось условие Сi > лi.

Рассмотрим линейную стоимостную функцию пропускных способностей:

где di - стоимость в расчете на единицу пропускной способности для i-го канала. Стоимостный коэффициент di может произвольно меняться в зависимости от различных параметров канала, но должен линейно зависеть от пропускной способности.

Для минимизации средней задержки сообщения в среде Т применим метод множителей Лагранжа, который позволит найти максимум и минимум функции при ограничениях-равенствах:

.

Поскольку выражение в квадратных скобках тождественно равно нулю, то если найти минимальное значение G при вариации пропускных способностей Gi, задача ВПС будет решена. Используя метод Лагранжа, получаем систему М уравнений:

.

Из нее следует:

.

Если найти постоянную в, то это выражение будет решением. Эта величина находится с учетом ограничения по стоимости di и путем суммирования по i:

.

Левая часть равенства равна D, следовательно:

.

Определяя добавочную стоимость De как:

и используя последние два равенства вместе с (5), получаем оптимальное решение линейной задачи ВПС:

.

При таком наборе пропускных способностей каждый канал будет иметь как минимум значение лi и, кроме того, некоторый запас по данному параметру. Стоимость минимальной пропускной способности i-го канала равна лidi единиц. При расчете конечной средней задержки в проектируемой среде полная стоимость получится больше. Разность между полной стоимостью и минимально допустимой величиной равна De (8) - добавочной стоимости. По формуле (9) добавочная стоимость сначала нормируется с помощью стоимостного коэффициента di и затем распределяется по всем каналам пропорционально квадратному корню из интенсивности трафика лidi. Т.о., формула (9) обозначает набор пропускных способностей по закону квадратного корня. С учетом вышеизложенного, минимальная средняя задержка прохождения сообщения в среде Т будет рассчитываться по формуле:

где - средняя длина пути.

Величина De играет здесь важную роль. При De > 0 средняя задержка сообщения неограниченно возрастает. Если De>0, задача ВПС решается, т.е. это неравенство является условием устойчивости системы. Если же De?0, то задача не имеет реализуемого решения.

2. В задаче распределения потоков (РП) считается, что пропускные способности заданы, а потоки надо определить так, чтобы минимизировать среднюю задержку. В теории потоков решается задача о потоках различных грузов с нелинейной целевой функцией [2]. Для каждого узла j и k требуется перевезти в среде от отправителя j к получателю k определенный груз (переслать сообщение) гjk. Задача распределения потоков различных грузов требует минимизации нелинейной функции Т по потокам лi для удовлетворения внешних требований к потокам гjk. Согласно обычному закону сохранения потоков в каждом узле, суммарный трафик j - k, поступающий в узел n, равен такому же суммарному трафику, выходящему из него, кроме случаев n=j (узел - источник груза, сообщения) и n=k (узел - адресат, получатель). Имеется ограничение на пропускную способность каждого канала, состоящее в том, что поток лi в канале i должен быть неотрицательным и меньше пропускной способности: 0 ? лi < С. Характеристика Т имеет свойство неограниченного возрастания при стремлении потока к пропускной способности соответствующего канала.

Предлагаемый ниже метод отклонения потока дает точное решение задачи оптимального РП.

Рассмотрим поток по кратчайшим путям. Примем в среде, что каждый канал имеет номинальную длину li. В такой среде надо найти кратчайший путь между узлом-источником j и узлом назначения k и организовать передачу требуемого потока гjk по этому пути. Для отыскания множества кратчайших путей воспользуемся алгоритмом Флойда [3]. Примем в среде всего N узлов. Пусть D0 = (djk) - матрица порядка NЧN, элемент которой djk дает длину прямого канала между узлами j и k. Если такого канала нет, то этот элемент равен бесконечности. При рассмотрении любого пути рjk его длину (сумму длин каналов) обозначим через l(рjk). Задача состоит в вычислении матрицы H=hjk) порядка NЧN, где hjk - длина кратчайшего пути, соединяющего узлы j и k. Алгоритм кратчайших путей Флойда начинает с матрицы расстояний D0 и итеративно изменяет ее, проходя через последовательность из N матриц (на n-м шаге матрица обозначается через Dn). В конце он приходит к матрице кратчайших путей Dn = H. Если начать с n = 0 и djk(0) = djk, то матрица Dn+1 получится из Dn с помощью итерации:

.

После нахождения Dn на n-й итерации получим, что djk(n) - кратчайшее расстояние между узлами по путям, на которых промежуточные узлы принадлежат множеству {1, 2, …, n}. Метод отклонения потока использует в качестве длины выражение:

,

когда поток в канале равен лi. Это линейная скорость возрастания Т при бесконечно малом увеличении потока в i-м канале.

Для реализации алгоритма введем вектор потока на n-й итерации:

i-й компонент л(n)i которого представляет собой полный поток по i-му каналу на n-й итерации. Если начальный поток f(0) реализуем, то оптимальный алгоритм ОП для выбора маршрутов состоит из следующих этапов: автоматизированный радиоэлектронный информационный поток

1) n = 0. Для каждого i = 1, 2, …, М найти

.

2) Найти вn - добавочный стоимостный коэффициент для этого потока:

.

3) Решить задачу поиска потоков по кратчайшим маршрутам, используя длины li. Пусть цi - результирующий поток по i-му каналу, который получается, если весь поток направляется по этим кратчайшим путям. Вектор потоков через ц = (ц1, ц2,…, цМ).

4) Найти bn - добавочный стоимостной коэффициент для потока по кратчайшему маршруту:

.

5) Правило остановки. Если вn _ bn < е, где е > 0 - выбранный допуск, то остановка.

6) Найти такое значение б из интервала 0 ? б ? 1, для которого поток (1 - б)f (n) + бц минимизирует Т.

7) Отклонение потока. f (n+1) = (1 _ б)f (n) + бц.

8) Положить n = n + 1. Перейти к шагу 1.

Наиболее важными этапами алгоритма являются п.1 (вычисление длины), 3 (вычисление потоков по кратчайшим маршрутам), 5 (правило остановки), 6 (вычисление отклоняемой части потока) и 7 (определение самого отклонения потока).

3. Задача выбора пропускных способностей и распределения потоков должна решаться объединением предыдущих задач ВПС и РП в одну. Но, поскольку мы вынужденно задаемся противоречивыми требованиями, нахождение глобально-оптимального решения становится невозможным. Поэтому следует сосредоточиться на поиске локальных минимумов для средней задержки сообщения в среде Т.

Для этого требуется, начиная с реализуемого начального потока, получить оптимальный набор пропускных способностей при линейных стоимостях, по алгоритму ОП найти оптимальные потоки, повторить решение задачи ВПС и задачи РП до отыскания локального минимума. Алгоритм упрощается, т.к. значение б всегда будет равно единице. При известном реализуемом начальном потоке f (0) алгоритм состоит в следующем:

1) n = 0. Выполнить алгоритм ВПС для потока f (n) и найти оптимальное множество пропускных способностей, используя линейные стоимости.

2) Используя длины , выполнить алгоритм ОП при б = 1 на каждом шаге. Полученный в результате оптимальный поток обозначается через f (n+1).

3) Если Т для потока f (n+1) ? Т для потока f (n), то остановка; поток f (n) дает локальный минимум. В противном случае положить n = n + 1 и перейти к шагу 1. При завершении 1 шага Ci будет задаваться равенством (9), а характеристика Т - равенством (10). li задаются соотношением:

.

Далее решаются задачи нахождения реализуемого начального потока f (0) и, анализируя локальные минимумы, находят глобальный. Для этого повторяется алгоритм ВПС и РП для многих различных начальных реализуемых потоков. Они находятся случайным назначением каналам исходных длин. Если условие De > 0 для потока выполняется, то найден реализуемый начальный поток, после чего выполняется алгоритм.

4. В задаче выбора топологии, пропускных способностей и распределения потоков задаются положения узлов и внешние требования к потокам от узлов-источников к узлам назначения гjk. Решение указанной задачи - итерационный метод нахождения локального минимума при решении задач ВПС и РП. Оно основывается на свойстве алгоритма устранять каналы (вносить топологические изменения) по мере выполнения алгоритма. Предлагается следующая последовательность действий:

1) Выбрать исходную топологию.

2) Выполнить алгоритм ВПС и РП. Если при какой-либо итерации нарушается ограничение связности, то прекратить оптимизацию и перейти шагу к 2. В противном случае провести алгоритм ВПС и РП до конца и затем перейти к шагу 2.

3) Дискретизировать непрерывные пропускные способности, полученные в п. 2. Результат может быть округлен до ближайшего допустимого дискретного значения (лi < С), такого, что для него продолжает выполняться условие Т ? Тmax.

4) Провести окончательную оптимизацию потока путем применения алгоритма ОП.

5) Повторить п.2-4 для ряда реализуемых случайных начальных потоков (с помощью случайного выбора исходных длин с потоками, направляемыми по кратчайшим маршрутам).

6) Повторить п.1-5 для ряда начальных топологий. Выбрать ту топологию, которая дает наименьшее Т.

Число повторений в п. 6 и 7 зависит от наличия времени на поиск решения.

Таким образом, в статье сформулирована цель оптимизации производительности среды АСУ РП как задача выбора топологии ее построения для увеличения пропускной способности при обработке информационных потоков. В качестве критерия оптимизации принимается среднее время, проведенное сообщением узла в среде АСУ. Чем быстрее сообщение будет передано адресату, тем быстрее и качественнее пойдет управление технологическими процессами на производстве.

Литература

1. Клейнрок Л. Вычислительные системы с очередями. Том 2. - М.: Мир, 1979.

2. Зайченко Ю.П. Исследование операций. - Киев: Вища школа, 1975. _ 320 с.

3. Свами М.Н. Графы, сети и алгоритмы. - М.: Наука, 1984.

4. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. - М.: Наука, 1987.

Размещено на Allbest.ru