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

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

Академия Федеральной службы охраны Российской Федерации

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

Георгиевский Александр Евгеньевич

Преподаватель спецкафедры.

г. Орел

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

При разработке среды АСУ РП особенное внимание уделяется одному из основных ее параметров - повышению производительности.

Производительность среды - это ее способность передавать заданный объем данных в единицу времени без искажений.

Параметр "производительность" оценивают двумя способами. Первый - по количеству произведенной работы в соответствии с предназначением в единицу времени (секунда, минута, час), т.е. по объему полезной информации, представленной в форме двоичных элементарных электрических посылок (в "цифре"), [бит/с].

Второй - по среднему времени задержки стандартного сообщения в среде, [с]. За стандарт принимается байт или килобайт двоичной информации. Чем меньше задержка в среде, тем она производительнее.

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

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

(1)

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

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

.(2)

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

.(3)

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

(4)

или

.(5)

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

.(6)

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

.(7)

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

(8)

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

.(9)

информация поток управление радиоэлектронный

При таком наборе пропускных способностей каждый канал будет иметь как минимум значение л_i и, кроме того, некоторый запас по данному параметру. Стоимость минимальной пропускной способности i-го канала равна л_id_i единиц. При расчете конечной средней задержки в проектируемой среде полная стоимость получится больше. Разность между полной стоимостью и минимально допустимой величиной равна D_e (8) - добавочной стоимости.

По формуле (9) добавочная стоимость сначала нормируется с помощью стоимостного коэффициента d_i и затем распределяется по всем каналам пропорционально квадратному корню из интенсивности трафика л_id_i. Т.о., формула (9) обозначает набор пропускных способностей по закону квадратного корня.

С учетом вышеизложенного, минимальная средняя задержка прохождения сообщения в среде Т будет рассчитываться по формуле:

(10)

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

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

2. В задаче распределения потоков (РП) считается, что пропускные способности заданы, а потоки надо определить так, чтобы минимизировать среднюю задержку.

В теории потоков решается задача о потоках различных грузов с нелинейной целевой функцией [2]. Для каждого узла j и k требуется перевезти в среде от отправителя j к получателю k определенный груз (переслать сообщение) г_jk.

Задача распределения потоков различных грузов требует минимизации нелинейной функции Т по потокам л_i для удовлетворения внешних требований к потокам г_jk.

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

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

Рассмотрим поток по кратчайшим путям. Примем в среде, что каждый канал имеет номинальную длину l_i. В такой среде надо найти кратчайший путь между узлом-источником j и узлом назначения k и организовать передачу требуемого потока г_jk по этому пути.

Для отыскания множества кратчайших путей воспользуемся алгоритмом Флойда [3].

Примем в среде всего N узлов. Пусть D₀ = (d_jk) - матрица порядка NЧN, элемент которой d_jk дает длину прямого канала между узлами j и k. Если такого канала нет, то этот элемент равен бесконечности. При рассмотрении любого пути р_jk его длину (сумму длин каналов) обозначим через l(р_jk).

Задача состоит в вычислении матрицы H=h_jk) порядка NЧN, где h_jk - длина кратчайшего пути, соединяющего узлы j и k. Алгоритм кратчайших путей Флойда начинает с матрицы расстояний D₀ и итеративно изменяет ее, проходя через последовательность из N матриц (на n-м шаге матрица обозначается через D_n).

В конце он приходит к матрице кратчайших путей D_n = H. Если начать с n = 0 и d_jk(0) = d_jk, то матрица D_n+1 получится из D_n с помощью итерации:

.(11)

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

Метод отклонения потока использует в качестве длины выражение:

,(12)

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

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

(13)

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

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

.(14)

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

.(15)

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

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

.(16)

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

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

7) Отклонение потока. f ⁽ⁿ⁺¹⁾ = (1 _ б)f ⁽ⁿ⁾ + бц.

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

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

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

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

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

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

3) Если Т для потока f ⁽ⁿ⁺¹⁾ ? Т для потока f ⁽ⁿ⁾, то остановка; поток f ⁽ⁿ⁾ дает локальный минимум. В противном случае положить n = n + 1 и перейти к шагу 1.

При завершении 1 шага C_i будет задаваться равенством (9), а характеристика Т - равенством (10). l_i задаются соотношением:

.(17)

Далее решаются задачи нахождения реализуемого начального потока f ⁽⁰⁾ и, анализируя локальные минимумы, находят глобальный. Для этого повторяется алгоритм ВПС и РП для многих различных начальных реализуемых потоков. Они находятся случайным назначением каналам исходных длин. Если условие D_e > 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.

Annotation

Algorithms for optimizing the performance of the ICS environment radioelectronic enterprises. Georgievsky A.E.

The optimization algorithms of radio-electronic enterprise automated control system environment productivity are considered in the article. The general problem of automated control system environment productivity increasing, stream distribution, environment topology choice and problem solving are spoken in detail.

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