Средства анализа процессов информационного обмена в распределенных управляющих устройствах

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

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

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

Средства анализа процессов информационного обмена в распределенных управляющих устройствах

Еременко В.Т., к.т.н., доцент

Чудный А.Ю., соискатель кафедры «Информационные системы»

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

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

In article the facility of analysis, capable in good time to trace and avoid appearing collisions of processes of information exchange in portioned controlling systems, on base of searching for of threats and well-timed informed persons, coming to a conclusion are considered. It is proved theorems, defining controlling decisions on base ill-defined relations preferences.

Описание процессов информационного обмена в распределенной управляющей среде характеризуется следующими особенностями [1,2]:

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

сложностью построения адекватной модели (образа) объекта с учетом параметров и определения связи между ними;

сложностью оценки поведения объектов и определения временного интервала для его прогнозирования;

необходимостью разработки математических методов оценки достоверности имеющихся дополнительных знаний, не представимых классическими средствами.

В распределенных управляющих системах (РУС) каждая подсистема не может иметь полной информации о состоянии других: скорость изменения их состояния по большей части сравнима со скоростью передачи информации об этом состоянии. Поэтому никакой элемент распределенной системы не может претендовать на роль "центра", который знает все о других элементах (т.е. имеет информацию о мгновенном состоянии всех элементов) и на этой основе может планировать работу (например, реконфигурацию) всей системы. Кроме того, что такое планирование неизбежно носит ограниченный характер, здесь возникают специфические вопросы надежности: какие действия и кто должен предпринимать при отказе лидера. В РУС возможны новые виды некорректностей, совершенно неизвестные в последовательном программировании [1,3]: взаимные блокировки (дедлоки), когда каждая из нескольких подсистем, строго следуя своей программе, бесконечно ожидает действий других; блокировка прогресса, когда подсистемы бесконечно обмениваются запросами о состоянии друг друга, не выполняя полезной работы; несправедливость, когда, например, один "сверхактивный" процесс может блокировать доступ к общему ресурсу всех других процессов и т.д.

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

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

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

Известно, что формирование плана по устранению угроз в пространстве состояний процессов информационного обмена РУС базируется на отношениях типа: "цель-подцель" "цель-действие", "действие-результат" [4,5]. Любой путь в этом сценарии, ведущий от вершины, соответствующей текущей ситуации, в любую из целевых вершин, определяет план действий.

Все задачи построения плана действий можно разбить на два типа, которым соответствуют различные модели: планирование в пространстве состояний (SS-проблема) и планирование в пространстве задач (PR-проблема).

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

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

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

SG = (S, C, P),

где S множество вершин, описывающих состояния с выделенным множеством начальных S₀ и конечных (терминальных) вершин T;

С множество ребер графа, соответствующих возможным переходам из состояния в состояние и обозначающих степень достижения цели (возможность достижения множества T);

P - вектор признаков состояния,

P = (P₁,... P_n),

где P_i = p_i, p_i - нечеткое множество влияния i-го параметра на достижение цели, p_i i = . Значения контролируемых параметров p_i изменяются в процессе функционирования РУС, а функции принадлежности p_i) определяются на основе методов экспертных оценок.

Предположим, что система имеет m классов управления. Каждый класс содержит информацию о правилах перехода процессов информационного обмена в новое состояние SG.

Тогда задачей РУС будет выбор j-го класса управляющих решений u_j

f (u_j) = (_j, p_{i ji}, _j p_i max,

^{i j}

где _j = (_j1,... _jn), _ji j = 1,...m, i = 1, n, p) = (₁p₁),..., _np_n));

n вектор оценки весов контролируемых характеристик.

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

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

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

априорный и динамический выбор уровня качества от угроз процессам информационного обмена;

Рисунок 1. Внутренняя организация распределенной управляющей системы в виде иерархических процессов и виртуальных комплексов

информационный обмен распределенный управляющий

выбор режимов, протоколов, механизмов, ресурсов, параметров системы контроля (настройка на требуемое качество);

выполнение (регулирование) процессов обнаружения неисправностей.

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

Описания состояний могут представлять собой строки символов, векторы, двухмерные массивы, деревья, списки и т. п. Операторы переводят одно состояние в другое. Иногда они представляются в виде продукций A=>B, означающих, что состояние А преобразуется в состояние В. Пространство состояний можно представить как граф, вершины которого помечены состояниями, а дуги - операторами.

Таким образом, проблема поиска решения задачи <А,В> при планировании по состояниям представляется как проблема поиска на графе пути из А в В. Обычно графы не задаются, а генерируются по мере надобности.

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

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

Алгоритм кратчайших путей Мура. Исходная вершина X₀ помечается числом 0. Пусть в ходе работы алгоритма на текущем шаге получено множество дочерних вершин X(x_i) вершины x_i. Тогда из него вычеркиваются все ранее полученные вершины, оставшиеся помечаются меткой, увеличенной на единицу по сравнению с меткой вершины x_i, и от них проводятся указатели к X_i. Далее на множестве помеченных вершин, еще не фигурирующих в качестве адресов указателей, выбирается вершина с наименьшей меткой и для нее строятся дочерние вершины. Разметка вершин повторяется до тех пор, пока не будет получена целевая вершина.

Алгоритм Дейкстры определения путей с минимальной стоимостью является обобщением алгоритма Мура за счет введения дуг переменной длины.

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

Алгоритм Харта, Нильсона и Рафаэля. В алгоритме объединены оба критерия: стоимость пути до вершины g[x) и стоимость пути от вершины h(x) - в аддитивной оценочной функции f{x) =g(x}-h(x). При условии h(x)<hp(x), где hp(x)-действительное расстояние до цели, алгоритм гарантирует нахождение оптимального пути.

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

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

Производить оценку недоопределенных факторов процессов информационного обмена.

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

Оценивать адекватность комплекса моделей процессов информационного обмена в текущем пространстве состояний.

Строить новое пространство состояний на основе сценариев принятия решений должностными лицами системы управления

Производить поиск (идентификацию) пространства возникновения угроз и осуществлять априорное и апостериорное определение типов угроз и коллизий.

Производить поиск распределения множества агентов в пространстве угроз и распределять множество типов алгоритмов обнаружения угроз по множеству агентов.

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

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

Теорема 1. Если на вход системы РУС поступают нечеткие сообщения, входящие в состав множества S_s, являющегося эталонным и не содержащим нечетко равных ситуаций, то при заданном пороге равенства ситуаций решение принимается на основе критерия

s_o, s_i = max s_o, s_i

s S_s^o

Доказательство. Пусть на вход системы управления поступает информация от агентов распределенной системы. Должностные лица принимают решение на основе множества ситуаций, входящих в состав множества S_s, являющегося эталонным и не содержащим нечетко равных ситуаций при заданном пороге равенства ситуаций. Данное предположение позволяет уменьшить размерность нечеткой модели принятия решения и не снижает эффективности модели в пределах достоверности, ограничиваемой порогом равенства. Тогда возможны два варианта. В первом случае полагаем, что на вход нечеткой модели поступают только хорошо определенные относительно порога равенства ситуации s_0. Тогда отношение нечеткого равенства на множестве

S₁ = S_s S₀,

где S₀ множество входных ситуаций, являющихся множеством нечеткой эквивалентности. Так как множество S_s не содержит нечетко равных ситуаций [4], то число классов эквивалентности нечеткого разбиения не содержит нечеткого разбиения множества S₁ совпадает с числом эталонных ситуаций. Следовательно, любая входная ситуация s₀ нечетко равна только одной эталонной ситуации s_i S_s, которая определяется сравнением с каждой ситуацией s_0, s_i) t, принимается равной ситуации s_i.

Второй вариант сводится к тому, что на вход нечеткой модели могут поступать плохо определенные ситуации s_i =_si (y)/y, s_j =_sj (y)/y, у есть некоторые ситуации. Степень включения ситуации s_i в ситуацию s_j определяется выражением

v(s_i,s_j) = _si(y),_sj (y))

y

Будем считать достоверность ситуации s_i низкой, а саму ситуацию плохо определенной, если хотя бы один признак у_к в этой ситуации плохо определен. В свою очередь, признак у_к считается плохо определенным, если

( Т_d ^k T_k)(_s (Т_d ^k)) (1-t_inc, t_inc).

Другими словами, признак у_к плохо определен в ситуации s_i, если нечеткое значение признака у_к в ситуации s_i содержит термы, со степенью принадлежности большей, чем 1-t_inc и меньшей чем t_inc. Здесь возможны два решения:

доопределить входную ситуацию, а именно уточнить плохо определенные признаки и тем самым перейти к первому варианту;

выявить подмножество S_s^o эталонных ситуаций, нечетко равных s_o.

Считать наиболее близкой s_o ситуацию s_i, имеющую максимальную степень равенства

s_o, s_i = max s_o, s_i ,

s S_s^o

что и требовалось доказать.

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

Ситуация несколько меняется если ввести линейную функцию полезности для заданного класса управляющих решений. Это позволяет учесть относительное влияние каждого из них на достижение целей управления. Докажем это.

Теорема 2. Если характеристики исходной информации для РУС Х заданы нечетким отношением предпочтения с функцией принадлежности

_i x, y): ,

а функция их связи F линейна, то наилучшее решение является элементом множества Парето X_n (R) и оценкой степени достижения цели функционирования системы управления безопасностью информации.

Доказательство. Рассмотрим структуру показателей информационного обмена в виде иерархической структуры G = (X, E, F), где X множество вершин графа G; E множество ребер; F функциональная зависимость, отражающая влияние вершин графа друг на друга.

Вершинами Х графа G являются характеристики системы управления. Предполагая отсутствие в графе G контуров, выделим уровни иерархии V_1,... V_m, причем нижний уровень V_m содержит только те характеристики, которые изменяются в ходе функционирования системы управления (независимость факторов), а на уровне V₂ находятся показатели качества, характеризующие частные цели функционирования, уровень же V₁ характеризует достижение системой цели.

Множество ребер Е отражает структуру влияния характеристик системы управления, причем е_ij тогда и только тогда, когда характеристика Х_i непосредственно влияет на характеристику Х_j. Значением х_i является степень его влияния на характеристики более высокого уровня графа. Таким образом, на основе известной функциональной зависимости F можно вычислить оценки весов любых уровней иерархии, зная лишь значения для нижнего уровня.

Необходимо подчеркнуть, что степень относительного влияния на различные характеристики X_j характеристик X_i в общем случае неодинакова. Вследствие этого веса х_i удобно представить с помощью нечеткого множества. По условию теоремы для каждой вершины X_i нижнего уровня V_m графа G задано нечеткое отношение предпочтения [6] с функцией принадлежности

_i x, y): .

В этом случае четкие значения весов x_i являются элементами множества Парето или множества четко недоминируемых альтернатив [7]. Обозначим через X_n (R) множество Парето, состоящее из всех максимальных решений x по отношению к нечеткому отношению предпочтения

R: X R)=xy,x)R^s x,y, где R^s =x,y) x,y) y,x)

Нечеткое отношение предпочтения R_i задает введенная функция принадлежности _i x,y). В силу нечеткости исходной информации рассмотрим в первом приближении линейную зависимость функции связи

_{N N}

F: x,y) = v_{i i} x,y), v_i = 1,

^{i= 1 i= 1}

где N число непосредственно влияющих на вершину Х_j уровня V_k-1 характеристик X_i уровня V_k с функциями принадлежности x,y), v_i оценка влияния каждой из них на X_j, соответствующая весу дуги e_ij графа G.

Введенная свертка отношений позволяет вычислить нечеткое отношение принадлежности для вершин уровня V_k-1 по известным нечетким отношениям принадлежности вершин V_k.

В случае когда множество X_n (R_i) содержит большое количество решений, используется отношение превосходства х над y:

x y

_q x,y) =

0, x y

где порог различимости x и y, назначаемый лицом, принимающим решение. Лучшей альтернативой считается та, для которой _q x,y) y X_n (R_i). Фактически определяется естественный порядок на множестве допустимых альтернатив: выбирается оценка с большей степенью влияния среди допустимых.

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

Литература

1. Еременко В.Т. Математическое моделирование процессов информационного обмена в распределенных управляющих системах.: Монография / Под общей редакций Константинова И.С. - м.: Машиностроение - 1, 2004. - 224 с.

2. Еременко В.Т., Туякбасарова Н. А. Теоретические основы построения распределенных управляющих систем с использованием структурно-функционального подхода: Монография. - Курск: Курский институт менеджмента, экономики и бизнеса, 2004. - 122 с.

3. Еременко В.Т., Константинов И.С. Моделирование процессов анализа реализаций протоколов информационного обмена для решения задач описания их статического и динамического взаимодействия // Вестник компьютерных и информационных технологий - № 4. - 2004. - С. 11 - 15.

4. Еременко В.Т., Константинов И.С., Коськин А.В. Формирование единой образовательной информационной среды на основе методологии функциональной стандартизации. // Ресурсные центры сферы образования России. Сборник научных статей. / Редколлегия: А.Н. Тихонов (общая редакция), В.П. Кулагин (председатель) и др.ГНУ «Госинфоробр». - М.: Янус-К, 2004. - С. 158 - 161.

5. Еременко В.Т. Базовые положения теории профилирования и тестирования распределенных управляющих систем // Международная научно-практическая конференция «Информационные технологии в науке, образовании и производстве (ИТНОП)» 11-12 мая 2004 г. Орел. Труды конференции. Т.2, С.20 - 27.

6. Мелихов А.Н., Берштейн Л.С., Коровин С.Я. Ситуационные советующие системы с нечёткой логикой ??М.: Наука, 1988. - 272с.

7. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации М.: Наука, 1981. - 208 с.

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