Методика оптимизации производительности сетей на основе полевых шин

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

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

Методика оптимизации производительности сетей на основе полевых шин

Максаков С.А.

Annotation

In this article the solving of optimization problem of network topology determination on basis of field bus system by criteria of communication delay minimization is presented. At that a linear cost function which takes into account channel parameters is considered. The methodology is based on the Lagrange multiplier methods and performs channel capacity algorithm, on flow distribution, and on network topology determination. The results can be used for topological network engineering.

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

Алгоритм выбора пропускных способностей. Одной из наиболее трудных проблем проектирования СПШ является оптимальный выбор пропускных способностей (ВПС) из конечного набора их возможных значений [3].

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

(1)

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

Примем среднюю задержку сообщения, проходящего по сети

(2)

за главную характеристику сети [5]. Этим выражением учтены и отражены все вопросы, связанные с массовым обслуживанием. Предположим, что пропускные способности каналов имеют непрерывные значения в некотором диапазоне . С точки зрения задержки важно, чтобы выполнялось основное условие .

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

(3)

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

Применим метод множителей Лагранжа для минимизации . Этот метод позволяет отыскивать максимум или минимум функции при ограничениях-равенствах [3]. Основная идея метода заключается в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой специально построенной функции Лагранжа. Для минимизации составим функцию Лагранжа:

, (4)

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

, . (5)

. (6)

или

, . (7)

Постоянную можно найти путем умножения последнего равенства на и суммирования по :

. (8)

Видно, что левая часть равенства равна , поэтому

. (9)

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

(10)

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

, . (11)

При таком наборе пропускных способностей каждый канал будет иметь, по крайней мере, пропускную способность . (т.е. минимальное требуемое значение) и, кроме того, некоторую дополнительную пропускную способность. Стоимость минимальной пропускной способности -го канала равна единиц. Полная стоимость должна быть больше этой суммы, если нужно получить конечную среднюю задержку в проектируемой сети. Разность между полной стоимостью и минимальной допустимой величиной равна и задается равенством (10), поэтому величина может быть добавочной стоимостью. Как следует из формулы (11), эта добавочная стоимость сначала нормируется с помощью стоимостного коэффициента и затем распределяется по всем каналам пропорционально корню квадратному из интенсивности трафика . Если подставить выражение для в (2), то получим

, (12)

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

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

Для СПШ , т.е. одна и та же постоянная величина для каждого канала. При этом можно положить . Здесь - сумма всех пропускных способностей сети, которую также можно обозначить через и считать, что она выражена в битах за секунду. Величина является строго возрастающей функцией средней длины пути. Топологическую структуру сети следует выбрать так, чтобы получить минимальную среднюю длину. Последнее достигается в полносвязной сети (каждая пара узлов в ней соединена каналом связи).

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

В теории потоков в сетях рассматривается задача о потоках различных грузов с нелинейной целевой функцией [2]. Для каждого и требуется перевезти по сети из узла-источника в узел назначения определенный груз . Эта задача распределения потоков различных грузов требует минимизации нелинейной функции по потокам , чтобы удовлетворялись внешние требования к потокам . Предполагается, что пропускные способности заданы. Кроме того, нужно не нарушить обычный закон сохранения потоков в каждом узле. Согласно этому закону, суммарный трафик j-k, поступающий в узел n, равен суммарному трафику j-k, выходящему из узла за исключением случая (узел является узлом-источником) или случая n=k (узел является узлом назначения). Поток в канале должен быть неотрицательным и меньшим пропускной способности этого канала, т. е. . Видно, что характеристика обладает свойством безграничного возрастания при стремлении интенсивности какого-либо потока к пропускной способности соответствующего канала. Таким образом, характеристика включает дополнительное ограничение на пропускную способность как функцию штрафа. Это важное свойство обеспечивает реализуемость решения (по отношению к ограничению на пропускную способность) при использовании любого метода минимизации, который представляется в виде последовательности небольших шагов, и на начальном шаге оперирует с реализуемым решением. Если начать с реализуемого решения, то можно пренебречь ограничением на пропускную способность, и, вследствие этого, задача, которая выглядит, как задача оптимизации с ограничением, будет представлять собой задачу без ограничений по оптимизации потоков различных грузов.

Рассматриваемый ниже алгоритм дает решение задачи оптимального РП, которое удобно использовать при численном расчете [3].

Рассмотрим выражение (2). Эта характеристика выражается просто как сумма слагаемых, каждое из которых зависит лишь от потока в одном канале. Также из (2) следует, что

, . (13)

Отсюда видно, что при всех ; аналогичные рассуждения показывают, что (оба эти неравенства справедливы при удовлетворении ограничений на пропускные способности). Таким образом, можно сделать вывод, что носит выпуклый характер. Кроме того, множество реализуемых потоков само по себе является выпуклым многогранником. Итак, если имеется реализуемое решение, то любой локальный минимум является глобальным минимумом для .

В [3] показано, что для поиска глобального минимума может быть использован метод отклонения потоков (ОП)

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

Для отыскания множества кратчайших путей в сети с узлами целесообразно использовать алгоритм Флойда [4]. Пусть - матрица порядка , элемент которой дает длину канала (которая при этом вычислении считается заданной), прямо соединяющего узел с узлом ; если такого канала нет, то этот элемент равен бесконечности (кроме того, ). Предполагается, что не существует циклов, полная длина которых отрицательна. При рассмотрении любого пути , соединяющего узел с узлом , будем обозначать через его длину (т. е. сумму длин каналов). Задача состоит в вычислении матрицы порядка , где - длина кратчайшего пути, соединяющего узел и узел . Алгоритм кратчайших путей Флойда начинает с матрицы расстояний и итеративно изменяет ее, проходя последовательность из матриц (на -м шаге матрица обозначается через ); в конце он приходит к матрице кратчайших путей .

Если начать с и , то матрица получится из с помощью итерации

(14)

После отыскания на -й итерации получим, что - кратчайшее расстояние от узла к узлу по путям, в которых промежуточные узлы принадлежат множеству .

Таким образом, дойдя до -й итерации, получаем искомый результат .

Для оценки длины канала метод отклонения потока использует выражение

, (15)

когда поток в канале равен . Это линейная скорость возрастания при бесконечно малом увеличении потока в -м канале. Такие длины можно затем использовать для формулировки задачи отыскания потоков по кратчайшим маршрутам. Тогда получающиеся пути представляют собой самые дешевые (т. е. самые лучшие для снижения ) пути, к которым может быть отклонена некоторая часть потока.

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

Для реализации алгоритма, базирующегося на этих идеях, введем вектор потока на -й итерации алгоритма:

(16)

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

1.

2. Для каждого найти

. (17)

3. Найти - добавочный стоимостный коэффициент для этого потока, и

. (18)

4. Решить задачу отыскания потоков по кратчайшим маршрутам, используя длины . Пусть - результирующий поток по i-му каналу, который получается, если весь поток направляется по этим кратчайшим путям. Вектор потоков через

5. Найти - добавочный стоимостный коэффициент для потока по кратчайшему маршруту,

(19)

6. Правило остановки. Если , где , выбранный допуск, то остановка. В противном случае перейти к шагу 7.

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

8. Отклонение потока. Положить .

9. Положить . Перейти к шагу 2.

Наиболее важными шагами алгоритма являются шаг 2 (вычисление длины), шаг 4 (вычисление потоков по кратчайшим маршрутам), шаг 6 (правило остановки), шаг 7 (вычисление отклоняемой части потока) и, наконец, шаг 8 (определение самого отклонения потока). Отклонение потока производится так, чтобы имело место максимальное снижение значения функции . В общем случае это приводит к детерминированной процедуре выбора маршрутов, допускающей альтернативы.

Метод отклонения потока обеспечивает оптимальный выбор маршрутов для трафика в сети и является сравнительно эффективным с точки зрения вычислений, однако оказывается, что существует более простой подоптимальный метод, который дает фиксированную процедуру выбора маршрутов и часто приводит к очень хорошим результатам, требуя намного меньше вычислений. Этот подоптимальный метод просто решает, отклонить ли весь поток или ничего не отклонять для каждого [3].

Рассмотрим алгоритм отыскания потоков, направляемых фиксированной процедурой выбора маршрутов при известном реализуемом начальном потоке :

1. .

2. Используя поток , найти множество кратчайших маршрутов (при величине , определенной равенством (17)).

3. Для каждого требования к потоку провести следующие шаги:

a) Пусть - поток, полученный из путем отклонения всего потока от его пути в потоке к кратчайшему пути .

b) Если справедливы два утверждения: - реализуемый поток и , относящееся к , строго меньше, чем , относящееся к , то перейти к шагу 3c. В противном случае перейти к шагу 3d.

c) .

d) Если все потоки рассмотрены, то перейти к шагу 4. В остальных случаях выбрать любой нерассмотренный поток и перейти к шагу 3а.

4. Если , то остановка; этот метод больше не может улучшить поток, направляемый фиксированной процедурой выбора маршрутов. В остальных случаях положить , и перейти к шагу 2.

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

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

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

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

Таким образом, при известном реализуемом начальном потоке алгоритм состоит в следующем:

1. .

2. Выполнить алгоритм ВПС для потока и найти оптимальное множество пропускных способностей, используя линеаризованные стоимости.

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

4. Если для потока больше или равно для потока , то остановка; поток дает локальный минимум. В противном случае положить и перейти к шагу 2.

Алгоритм сходится, так как имеется лишь конечное число потоков по кратчайшим маршрутам.

При завершении шага 2 (алгоритм ВПС) будут задаваться равенством (11), а характеристика - равенством (3.67), где , заменяются на . При этом задаются равенством

(20)

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

Теперь стоят две задачи:

1. Найти реализуемый начальный поток .

2. Просматривая многие локальные минимумы, найти глобальный минимум.

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

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

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

Эвристическое решение задачи ВТПС и РП представляет собой итеративную форму решения задачи ВПС и РП. Оно основывается на свойстве алгоритма устранять каналы (вносить топологические изменения) по мере выполнения алгоритма ВПС и РП:

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

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

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

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

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

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

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

Таким образом, рассмотренная методика оптимизации производительности СПШ обеспечивает выбор оптимальной топологии сети по критерию минимизации задержки сообщений.

Исследования показали, что применение вышеописанных алгоритмов в аппаратно-программных комплексах повышения производительности сетей промышленной автоматизации позволяет сократить на 20 % среднее время нахождения сообщения в сети, т. е. увеличивает ее производительность в 1,2 раза.

ЛИТЕРАТУРА

сеть топология шина связь

1. Артемов, Н.И. Принципы построения промышленных микроконтроллерных сетей в стандартах Profibus и P-NET [Текст] / Н.И. Артемов, О.Б. Низамутдинов, М.В. Гордеев и др. - Пермь: ПГТУ, НИИУМС, 1996 -312 с .

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

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

4. Свами, М.Н. Графы, сети и алгоритмы [Текст]/ М.Н. Свами. - М., Наука, 1984 - 283с.

5. Максаков, С.А. Математическая модель процессов информационного обмена для сетей на основе полевых шин [Текст] / С.А. Максаков, В.Т. Еременко // Известия Тульского государственного университета.- Тула, 2006. - № 8. - С. 14-24.

Максаков Сергей Анатольевич

Соискатель кафедры «Информационные системы»

Орловский государственный технический университет, г. Орел