Диагностирование бортовых систем обработки информации и управления с использованием динамических моделей тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Лукоянов Егор Васильевич

• Лукоянов Егор Васильевич
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Лукоянов Егор Васильевич

ВВЕДЕНИЕ

ГЛАВА 1. Анализ современных методов диагностирования бортовых систем обработки информации и управления

1.1 Иерархический подход в техническом диагностировании

1.2 Методы диагностирования бортовых систем обработки информации

1.3 Методы диагностирования бортовых систем управления

1.4 Выводы

ГЛАВА 2. диагностические динамические модели бортовых систем

обработки информации и управления

2.1 Синтез иерархической диагностической динамической модели распределённой вычислительной системы

2.1.1 Структура параллельной диагностической динамической модели с независимыми цепями и со слиянием цепей

2.1.2 Алгоритм синтеза иерархической диагностической модели со многими точками слияния

2.2 Условия наблюдаемости и управляемости иерархической модели

2.3 Интервальная диагностическая динамическая модель систем управления

2.4 Выводы

ГЛАВА 3. Алгоритмы диагностирования бортовых вычислительных и

управляющих систем

3.1 Алгоритм обнаружения отказов с использованием линейной стационарной диагностической динамической модели РВС

3.2 Алгоритм обнаружения отказов с использованием линейной периодически нестационарной диагностической динамической модели РВС

3.3 Анализ алгоритма обнаружения отказов с использованием линейной периодически нестационарной диагностической динамической модели РВС с асинхронными обменами

3.4 Алгоритм обнаружения отказов основе интервальной диагностической динамической модели СУ

3.5 Алгоритм принятия решения об отказе на основе аппарата нечеткой логики

3.6 Алгоритм поиска отказов основе интервальной диагностической динамической модели СУ

3.7 Выводы

ГЛАВА 4. Результаты практической апробации методов диагностирования

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

4.1 Структура и функциональное назначение составных частей макета навигационного комплекса АНПА

4.2 Тестовое диагностирование вычислительной системы макета навигационного комплекса АНПА

4.3 Функциональное диагностирование систем управления составных частей навигационного комплекса АНПА

4.4 Выводы

ЗАКЛЮЧЕНИЕ

ПЕРЕЧЕНЬ ИСПОЛЬЗОВАННЫХ АББРЕВИАТУР

СПИСОК ПУБЛИКАЦИЙ АВТОРА

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

Введение диссертации (часть автореферата) на тему «Диагностирование бортовых систем обработки информации и управления с использованием динамических моделей»

ВВЕДЕНИЕ

Актуальность и степень научной проработки темы диссертации.

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

Для обоих типов диагностирования в современной научной литературе представлены решения, соответствующие различным постановкам задачи диагностирования и объектам разных уровней сложности. Среди наиболее известных авторов, занимавшихся проблемой ТД, можно назвать Preparata F. P., Metze G., Chien R. T., Бурдонова И. Б., Данилова В.В., Сперанского Д.В., Колесова Н.В. и др. Также большой вклад внесли в решение задач диагностирования, но в области ФД следующие авторы Patton R.J., Isermann R., Lafortune S., Frank P.M., Sampath M., Clark R.N., Подкопаев Б.П., Пархоменко П.П., Жирабок А.Н., Мироновский Л.А., Шумский А.Е. и др. Тем не менее, время выдвигает в данной области новые проблемы, требующие углубленного

исследования. Так в области ТД оказались мало исследованными вопросы диагностирования сложных распределенных вычислительных систем, а в области ФД - вопросы диагностирования при наличии неопределенности в модели объекта диагностирования. Эти вопросы исследуются в настоящей диссертации, что и определяет ее актуальность. В обоих этих случаях исследования опираются на динамические модели объектов.

Объект исследования - бортовые системы обработки информации и управления.

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

Цель работы состоит в исследовании и развитии методов диагностирования нарушений в сложных бортовых системах обработки информации и управления (СОИУ) путём совершенствования используемых диагностических моделей и снижения сложности используемых процедур синтеза средств диагностирования.

Для достижения поставленной цели решены следующие задачи.

- проведен анализ методов тестового и функционального диагностирования бортовых СОИУ;

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

- сформулированы и доказыны достаточные условий наблюдаемости и управляемости иерархической модели для бортовых РВС реального времени;

- разработан алгоритм синтеза теста для обнаружения отказов в бортовых РВС реального времени;

- разработан алгоритм функционального диагностирования для обнаружения и поиска отказов в бортовых системах управления (СУ) в условиях наличия в их моделях неопределенностей;

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

Научная новизна результатов диссертационной работы:

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

2) Достаточные условия наблюдаемости и управляемости иерархической диагностической динамической модели для бортовых РВС реального времени.

3) Алгоритм синтеза теста для бортовых РВС реального времени, который обнаруживает любые нарушения адресации в межмодульных обменах РВС.

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

Практическая значимость результатов диссертационной работы:

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

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

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

Положения, выносимые на защиту:

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

2) Достаточные условия наблюдаемости и управляемости иерархической модели для бортовых РВС реального времени.

3) Алгоритм синтеза теста для бортовой РВС реального времени.

4) Алгоритм функционального диагностирования бортовых СУ в условиях наличия в их моделях неопределенностей.

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

Материалы диссертации докладывались и обсуждались на XII Международном симпозиуме Intelligent Systems (Москва, 2016 г.), X Международном симпозиуме IFAC Fault Detection, Supervision and Safety for Technical Processes (Варшава, 2018 г.), III Международной научной конференции по проблемам управления в технических системах (Санкт-Петербург, 2019 г.), Международных семинарах «Навигация и управление движением» (International workshop navigation and motion control, Санкт-Петербург, 2016, 2017, 2019 гг., Самара, 2020 г.), XVIII - XXIII Конференциях молодых ученых «Навигация и управление движением» (Санкт-Петербург, 2016-2021 гг.), XXXI Конференции памяти выдающегося конструктора гироскопических приборов Н.Н. Острякова (Санкт-Петербург, 2019 г.), XIII Всероссийском совещании по проблемам управления (Москва, 2019 г.), XII Мультиконференции по проблемам управления (Дивноморское, 2019 г.), VIII Всероссийской научно-технической конференции «Технические проблемы освоения Мирового океана» (Владивосток, 2019).

Автор находился на научной стажировке в Университете Севильи (Universidad de Sevilla), проходящей в рамках VIII International Summer School on Fault Diagnosis of Complex Systems, г. Севилья, 17.06.2019 - 21.06.2019 г.

Внедрение и апробация результатов.

Основные результаты работы использованы при выполнении грантов РФФИ 16-08-00530а и 19-08-00052а, кроме того, предложенные решения в рамках инициативной работы в АО «Концерн «ЦНИИ «Электроприбор». были применены при разработке навигационного комплекса для АНПА.

Публикации.

По материалам диссертации опубликовано 22 работы, из них 4 статьи в журналах, рекомендуемых ВАК, 4 публикаций в изданиях, индексируемых Scopus и Web of Science, и 14 публикаций в прочих изданиях, индексируемых РИНЦ.

Личный вклад автора.

В диссертационной работе изложены результаты, которые были получены либо лично автором, либо при его непосредственном участии.

Структура и объем диссертации.

Диссертация состоит из введения, четырех разделов, заключения, перечня использованных аббревиатур, списка публикаций автора, списка литературы. Общий объем диссертации составляет 153 страницы, в тексте имеется 42 рисунка, 23 таблицы, список литературы содержит 134 наименования.

ГЛАВА 1. АНАЛИЗ СОВРЕМЕННЫХ МЕТОДОВ ДИАГНОСТИРОВАНИЯ БОРТОВЫХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ

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

1.1 Иерархический подход в техническом диагностировании

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

СД широко применяются на всех этапах жизненного цикла любой системы [28, 61, 72, 76, 77, 84, 95, 103, 107, 117, 121], как технологические средства при создании системы и ее отладке так и на этапе применения системы в штатных условиях эксплуатации. Качество СД существенно влияет на надежность системы. В этом случае применяются как встроенные, так и внешние СД, как СД работающие в реальном времени, так и СД, анализирующие работу системы в режиме постанализа. Кроме того, СД часто применяются на этапе восстановления системы после отказа.

Средства диагностирования подразделяются на тестовые [8, 14, 31, 32, 59, 66, 113, 122] и функциональные [5, 21, 28, 47, 55, 68, 78, 89, 103, 109, 117]. При этом соответственно говорят о тестовом диагностировании (ТД) и функциональном диагностировании (ФД). В первом случае диагностирование осуществляется на основе специально формируемых тестовых воздействий во время перерывов в функционировании диагностируемой системы (ДС) или ее подсистемы по прямому назначению (рисунок 1.1а), во втором - на основе рабочих воздействий в процессе функционирования диагностируемой системы или ее подсистемы по прямому назначению (рисунок 1.1 б).

Тестовые воздействия

Реакция

ДС

(подсистема ДС)Л

Рабочие воздействия

—►^Средства Т.Д^Ц—

уподсистема ДСу —►^Средства ФД^^—

Реакция —►

т

Решение об отказе

{

Решение об отказе

(а) (б)

Рисунок 1.1 - Тестовое (а) и функциональное (б) диагностирование.

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

На практике «проклятие размерности» преодолевается с помощью

иерархического подхода [35], который применяется как при проектировании

бортовых систем обработки информации и управления, так и при проектировании

для них средств диагностирования. Определяя иерархический подход при

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

следующие уровни проектируемых конструктивных единиц: транзистор,

10

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

Тот же смысл имеет иерархический подход и в техническом диагностировании, который позволяет декомпозировать задачу диагностирования. Действительно, с одной стороны, на практике разработчик СД получает задание и отчитывается, как правило, на языке конструктивных единиц - СД модуля, СД прибора и т.п. В то же время, с другой стороны, приступая к исполнению задания, он, прежде всего, определится с математической моделью диагностируемого объекта, что обусловит в значительной степени и рассматриваемый далее класс отказов и используемый метод диагностирования. Так или иначе, для синтеза СД определяющим является используемая модель, а для иерархического подхода -шкала моделей. Однако при диагностировании удобно говорить не об одной шкале, а о трех шкалах: математических моделей компонент системы, классов отказов, методов диагностирования. Каждая шкала имеет несколько уровней. У всех шкал число уровней одинаковое. Чаще всего их четыре: безынерционные преобразователи, динамические устройства, мультирежимные системы, распределенные системы. В случае вычислительных систем эти уровни можно назвать: вентильный, функциональный, алгоритмический, сетевой [34].

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

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

(а) (б)

Рисунок 1.2 - Иерархии компонент (а) и средств диагностирования (б)

распределенной системы.

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

таком виде. Его скорее следует рассматривать как некоторый предел, к которому можно стремиться [35].

1.2 Методы диагностирования бортовых систем обработки информации

Поясним правила построения тестовой проверки для безынерционных преобразователей [35]. При этом, очевидно, что простейшим является случай, когда входы и выходы элемента, с которым соотносится рассматриваемый отказ, доступны. Тогда проверкой является пара «входное воздействие - эталонное значение выхода». Причем входное воздействие таково, что реакция устройства при отсутствии и наличии отказа различна. Такое воздействие обычно называют тестовым. На рисунке 1.3 представлены два примера аналогового (а) и цифрового (б) функциональных преобразователей, реализующих в определенном смысле похожие функции. Это сделано специально для демонстрации близости идей диагностирования аналоговых и цифровых объектов.

Рисунок 1.3 - Примеры аналогового (а) и цифрового (б) преобразователей.

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

Тестовое диагностирование безынерционных преобразователей.

(а)

(б)

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

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

Тестовое диагностирование дискретных динамических устройств.

Ситуация существенным образом осложняется, если объект представляет собой динамическую систему. В том случае он имеет следующую структуру (рисунок 1.4), включающую два безынерционных функциональных преобразователя ф и 5, а также инерционный блок А (интеграторы, задержки, триггеры).

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

и

рО

*(к> —) Н1У

х(к +1)

Рисунок 1.4 - Модель конечного автомата.

Однако реализовать на практике такое предложение, как правило, будет затруднительно, т.к. входные векторы этих преобразователей имеют в своем составе не только независимые входы и, на которых можно формировать любые входные сигналы, но также сигналы обратных связей, значения которых определяются внутренним состоянием объекта х. В результате процесс формирования требуемых тестовых наборов [ит, хт ] на входе безынерционных преобразователей превращается в многошаговую процедуру (рисунок 1.5), порождающую определенную тестовую последовательность. Начальный отрезок этой последовательности устанавливает объект из начального состояния х в тестовое состояние х . В этом состоянии на вход объекта подается входной сигнал ит, а затем полученная реакция устройства в виде его состояния хт транслируется на выход объекта путем организации соответствующего чувствительного пути.

Рисунок 1.5 - Структура тестовой последовательности.

В результате значение выхода ут объекта будет зависеть от результатов проверки [ит, хт ]. Проверка связей между безынерционными преобразователями

через инерционные элементы составляет второй этап диагностирования, который обычно выполняется попутно с первым.

Принципы тестового диагностирования мультирежимных систем.

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

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

Как уже отмечалось, мультирежимную систему обобщенно можно представить в виде двух взаимодействующих объектов - управляющего (УУ) и операционного устройств (ОУ) (рисунок 1.6). По этой причине, когда мы говорим о проверке информационных связей между режимами, то по существу мы подразумеваем проверку управляющего устройства, а если представлять его как некоторую иерархию управляющих модулей, то проверку модуля верхнего уровня иерархии, отвечающего за переключения между режимами.

11 У

УУ

ОУ

Рисунок 1.6 - Обобщенная структура мультирежимной системы.

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

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

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

Функциональное диагностирование дискретных динамических устройств с

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

Помехоустойчивое кодирование играет существенную роль при создании практически любых систем связи [11, 24, 49], в том числе при защите информации как внутри систем обработки информации, так при межсистемных обменах информацией. При этом под кодом понимается набор двоичных кодовых слов, которыми представляется передаваемая по каналу связи информация. При этом каждое передаваемое слово размерности п, кроме к информационных разрядов, содержит п - к дополнительных (контрольных), которые связаны с информационными некоторыми (обычно линейными) контрольными соотношениями. При передаче через канал обмена какие-то разряды слова могут искажаться под воздействием помех. Предполагается, что в результате должны нарушаться использованные при формировании кода контрольные соотношения, поэтому, проверяя их при приеме, можно обнаружить или даже исправить возникшие искажения. Определение правил выбора контрольных соотношений и составляет содержание теории помехоустойчивого кодирования.

Этот подход широко применяется в каналах обмена современных информационно-управляющих систем. Упрощенно его реализация представлена на рисунке 1.7.

г

Линия связи

Кодирование | п информации I

Декодирование информации

Рисунок 1.7 - Функциональное диагностирование шины компьютера.

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

Список литературы диссертационного исследования кандидат наук Лукоянов Егор Васильевич, 2021 год

С/ с.

Н = НУ, н =

Л к

к

У:

О ..

о ..

о о

1

о

о о

0

ООО

. О -а; . О -ои

. 1 -а!.

0

И

22

> £

2=1

О

о

п = п.

И

Р 2

О

... И

рр

о о

о

1

п

В матрице У единицы стоят в столбцах с номерами п,П>•••>пр. Причем к _

^ П, к = 1, р. Использование этой матрицы позволяет ввести в соотношения

2=1

матрицу Н, преобразующую вектор значений последних интеграторов ХИ1,ХИ2,•••,х в цепочках в выходной вектор у,у2,...,ур системы. Для нас важно,

24

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

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

Теория построения наблюдателей выхода развита достаточно хорошо [14, 21, 28, 68]. Синтез наблюдателей выхода осуществляется по другим правилам. На рисунке 1.13 представлен случай, когда с помощью наблюдателя выхода диагностируется линейная система, однако известны алгоритмы построения таких наблюдателей и для нелинейных систем [19, 22].

наблюдателя выхода.

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

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

Функциональное диагностирование в условиях наличия неопределенностей в модели диагностируемой системы.

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

Проблема обработки невязки.

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

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

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

1.4 Выводы

1) В настоящей главе приведен обзор современных методов диагностирования систем обработки информации и управления. Обзор построен в соответствии с порядком, диктуемым иерархическим подходом.

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

ГЛАВА 2. ДИАГНОСТИЧЕСКИЕ ДИНАМИЧЕСКИЕ МОДЕЛИ БОРТОВЫХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ

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

2.1 Синтез иерархической диагностической динамической модели распределённой вычислительной системы

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

подхода является то, что диагностическая модель встраивается в систему, исполняется параллельно с основным ПО системы и позволяет упрощать процесс ее тестового диагностирования. В силу указанной особенности подход назван диагностированием с параллельной моделью [А1, А6, 33]. Данную диагностическую модель с точки зрения рассматриваемого класса отказов можно отнести к дискретно-событийным системам [70, 74, 75, 80, 99], когда работа системы представляется на языке последовательностей некоторых событий. В данном случае это события информационных обменов между ПМ. Подобные модели широко применяются при анализе и тестировании сложных систем [7, 42, 81, 93, 119, 126, 134]. В работах [А11, 12, 13, 97] представлены алгоритмы синтеза диагностической модели в рамках тестового диагностирования с параллельной моделью. В настоящей главе изложен более общий подход к синтезу модели, а также приводятся доказательства условий наблюдаемости и управляемости для предлагаемой модели. Использование усовершенствованных моделей позволяет снижать сложность теста и сокращать объем диагностической информации, передаваемой между ПМ, тем самым улучшая показатели надежности. Свойства наблюдаемости и управляемости модели существенным образом влияют на сложность процедур построения тестов. При этом в наблюдаемой модели существует возможность оценивания текущего состояния модели по виду наблюдаемой выходной последовательности, а для управляемой модели существуют входные последовательности, переводящие систему между парой ее любых состояний.

2.1.1 Структура параллельной диагностической динамической модели с

независимыми цепями и со слиянием цепей

Кратко опишем подход к тестированию РВС с параллельной моделью, иллюстрируя его на простом примере (рисунок 2.1). Здесь на рисунке 2.1а представлен граф межмодульных связей исходной системы. Система содержит три функционально связанных ПМ: ПМ, ПМ2 и ПМ3, которые могут быть размещены как на разных процессорах системы, так и на одном. Каждый из ПМ

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

(а) (б)

Рисунок 2.1 - Пример системы в виде графа межмодульных связей (а), система с параллельной моделью и средствами диагностирования (б) На рисунке 2.1 б система приведена совместно с параллельной моделью £, включающей три компоненты: щ., I = 1,3. Здесь щ. - диагностический алгоритм, который является вводимой избыточностью. Средства диагностирования формируют для системы тестовые данные (ы[ - для ПМ, ы'2 - для ПМ2), дополняя ими входные данные для системы, и анализируют выходную реакцию -у2. Состав СД: генератор тестов (далее - ГТ), генератор эталонных реакций

(далее - ГЭР) и компаратор (далее - К). В каждый ПМ по каналам обмена

поступает информация, которая обрабатывается штатными алгоритмами,

30

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

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

31

асимптотическая сложность процедур построения теста для которой будет характеризоваться полиномиальной зависимостью от размерности системы. Существенное влияние на снижение сложности построения теста оказывает относительная простота получения наблюдаемых и управляемых моделей в линейном случае [А12, А14], что крайне важно для построения эффективных тестов [А13, А15]. Заметим, что для нелинейного штатного ПО эти свойства, как правило, весьма ограничены и с трудом поддаются анализу.

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

j = 1, т, из такого числа динамических звеньев V г = 1, П , через сколько ПМ

проходит данный путь.

Структура модели для рассматриваемого примера, состоящая из т независимых цепей приведена на рисунке 2.2. На рисунке изображены динамические звенья V . - где г это номер звена в цепи, j - номер цепи.

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

Рисунок 2.2 - Структура модели с независимыми цепями для рассматриваемого

примера системы

Отсюда можно сформулировать требование к звеньям цепей модели. Они должны быть линейны и определены в двоичном поле Е = {0,1}:

Ху (к +1) = ^; хг, ] (к) + gг, ] иг, ] (к), уг,, (к) = Иг, ] хг, ] (к), г = , ] = 1т (2.1) где хи(к)^¥",ии(к)^¥д,уи(к)^¥р - векторы состояния, входа и выхода соответственно для г -го звена модели ] -й цепи, п - размерность вектора состояния, q - размерность входного вектора, р - размерность выходного вектора, е ¥'"'"/ е ¥"'\\\11 е ¥'"'" - матрицы динамики, входа и выхода соответственно, п , т - число звеньев в ] -цепи и число цепей в модели системы

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

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

Однако применение такой модели РВС может в некоторых случаях потребовать передачи через каналы обмена большого количества

диагностической информации, что не всегда допустимо. В подобных ситуациях целесообразно воспользоваться приемом, заключающимся в обработке нескольких массивов информации одним звеном (слияние вычислительных путей) [13]. Этот вариант иллюстрируется на рисунке 2.3.

Рисунок 2.3 - Структура модели со звеном слияния для рассматриваемого

примера системы

Здесь выходные массивы информации звеньев уи и у32 обрабатываются звеном у21 , а звено у42 исключается. В результате сокращается размерность выходного вектора у'ъ, а, следовательно, и объем выдаваемой из ПМ в каждом такте диагностической информации.

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

звеньев хг (к), г = 1, п , а с помощью матриц j(k)), С(j(k)), Н(j(k)) описывается

перенос информации между ПМ системы, а также между ПМ и СД в каждом j (к) -м информационном обмене. Так будет, если выполняется предположение о единственности обмена в каждый момент времени. На практике это предположение не всегда выполняется, однако, как показано в работах [А1, 97],

это не является препятствием для использования таких моделей при построении тестов. Рассмотрим следующее свойство систем рассматриваемого класса:

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

Для удобства описания свяжем с каждой последовательностью матриц на интервале, равном периоду обработки штатных данных в исходной системе, свою

последовательность индексов, множество которых обозначим через Г = {у5 ,

где Т = п +1, так как добавляются дополнительные сеансы обмена информацией

с СД. Значения последовательностей индексов получаются в результате циклического сдвига начальной последовательности на интервале равном Т . Например, при Т = 3 имеем множество последовательностей индексов матриц Г = (У1,У2,Уз} = {1,2,3; 2,3,1; 3,1,2}, которое состоит из трех последовательностей. Тогда для описания модели получим:

х(к+1)=¥(ухлк)шк)+о(Уяитт, у(*)=щу.итт, (2.2)

где х(^) е Fл'",u(i:) е Fл'?,y(¿) е - векторы состояния, входа и выхода,

- матрицы динамики

входа и выхода соответственно, ](к) = 1, N - счётчик информационных обменов.

Матрицы в этих уравнениях зависят от текущего значения счетчика информационных обменов, т.е. модель является нестационарной. Более того, она является периодически нестационарной [2, 56, 101], т.к. из-за периодичности входного потока процессы обработки данных в системе периодические. Напомним, что свойства наблюдаемости и управляемости для нестационарных систем зависят от используемых для наблюдения и управления интервалов времени, задаваемых последовательностями индексов у5 еГ, поэтому говорят о -наблюдаемости и -управляемости.

Пример 2.1. Проиллюстрируем применение свойства 2.1 на рассматриваемом примере слияния двух цепей (рисунок 2.3). Временная диаграмма процессов вычислений в системе представлена на рисунке 2.4.

п 01 02 • * * От Оо В п 01 02

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

Введем следующую нумерацию для звеньев цепей, и, как следствие, для описывающих их матриц и векторов: 1 -, 2-у12, 3-у22, 4-у32,0-у21 .

Предполагая следующий формат вектора состояния модели

х = [х х2 X х4 X ]Т, имеем последовательность матриц обменов на периоде,

заканчивающимся сеансом приема тестовой информации от СД (нулевые элементы матриц не показаны):

Р1,о(1)

Е

Е

Е

Е

*3,4(3) =

§0Ь1 Е

^2,3 (2)

Е

Е

§3Ь2

Е

Е

Е

Е

§4Ь3

Е

*4,О(4) =

Е

Е

Е

Е

§0Ь4 ^

\сД (5) =

Е

Е

Е

Е

Е

,1,2(6) =

Е

Е

Е

где Е - единичная матрица, il, gг, Ьг - матрицы динамики, входа и выхода

соответствующих динамических звеньев, г = 0..4, ^ ,(т(](к))) - матрица

динамики модели со слиянием цепей, соответствующая сеансам обмена г, j = 0..4.

К сожалению, предложенные ранее [12, 13] алгоритмы синтеза наблюдаемой и управляемой диагностической модели не обладают достаточной общностью. Действительно, эти алгоритмы обслуживают только две следующие ситуации: модель с независимыми цепями и модель с одной точкой слияния. Таким образом, вне рассмотрения оказались ситуации, когда точек слияния более одной. Вопросы о том, как производить синтез в подобных случаях и какая в этом случае будет модель системы, рассматриваются в следующем пункте.

2.1.2 Алгоритм синтеза иерархической диагностической модели со многими

точками слияния

Иерархическая диагностическая модель, как и модель с независимыми цепями или модель с одной точкой слияния рассматривается в рамках концепции параллельной модели, включая преимущества обеих. Алгоритм синтеза иерархической диагностической модели состоит из трех основных этапов [А3, А21]:

а) Определить по виду исходного информационного графа распределенной вычислительной системы структуру диагностической модели с независимыми цепями согласно положениям, изложенным в пункте 2.1.1.

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

5 = argmin(dim уа) (2.3)

где 5 - результирующая иерархическая модель со многими точками слияния,

гр ГГ1 ГГ1 ГГ1

У а = [У^ У^ .. У^ ] - диагностический вектор, составленный из выходных

векторов диагностических алгоритмов, Р - количество диагностических алгоритмов модели, соответствующее количеству программных модулей.

в) Задать для каждого динамического звена результирующей иерархической структуры линейную динамическую систему (2.1, 2.2), удовлетворяющую условиям наблюдаемости и управляемости.

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

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

Постановка задачи. Дано множество двусвязных списков Ь = {/ }т=1,

где т - общее количество списков, ^ = ^Ул ^, V г = {у. }*4 - множество узлов j -го списка, п - количество узлов в j -ом списке, N =

Е

V ;=! )

nj

- общее количество

узлов всех списков из множества L. Пусть задано отображение р : V. ^ P множества V узлов i -го списка на множество программных модулей P исходной рассматриваемой системы. Требуется разработать алгоритм слияния списков.

Алгоритм предполагает рекурсивное слияние очередного списка со структурой из списков, объединенных на предыдущих шагах. На каждом шаге формируется не более одного узла слияния. Обнаружение точки слияния осуществляется по правилу:

а) если ) = p(vh) и р(Хч) ф p(vh_,), где vk е у. и vh е У7 узлы списков lt

и l соответственно, то узел vk является точкой слияния. Индексы h и к в

начальный момент имеют значения соответствующие хвостовому узлу списка.

Входные данные: L - множество двусвязных списков, M = 0 множество узлов слияния, P - множество ПМ исходной системы.

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

Алгоритм. Для решения поставленной задачи будем использовать структуру данных типа хеш-таблица, с хеш-функцией для определения ключей доступа к таблице h(k) = к mod | P |, где к - ключ, значение некоторого параметра,

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

Каждый узел списка имеет следующую структуру: Node{list - num,pm - num,*next,*prev[]}, где list - num - номер списка, которому принадлежит узел, pm - num - номер ПМ, которому принадлежит узел (результат работы функции p(v)) и который является входным параметром для хеш-функции для вычисления индекса в хеш-таблице, *next - указатель на следующий узел списка, * prev[] - динамический массив указателей на предыдущие узлы списка, в том числе после процедуры слияния.

Псевдокод алгоритма представлен на рисунке 2.5 а.

i: procedure Cm ainMerc v.(L, M, P) 2: T MakeHash(\P\,0) 3: M MakeVectorQ 4: key 0 5: node <— 0 ¡5: for all I E L do 7: key HashSearch{T. Tail(l))

& if T\key\ ± 0 then

9: node NodeMerge{T[key], Tail{l))

10: PushBack(M, node)

11: else

12: HashInsert(T, Tail(l))

13: end if

14: end for

15: return |L| - \M\ - 1

16: end procedure

(a)

IT: procedure NODEM ERG E( ЛГ1, N 2)

mergednode 4— 1)

if Nl.liattium ^ N2.listnitm then

if Nl.nodenum == N2.nodenum then for all prev £ iVl .prei.'[] do

if prev.nod.enum == N2.prev .nodenum then mergednode <— NodeM erge(prev, N2.prev) retiirn mergednode end if end for

jVl.prei'U i- PushBack(N2.prev) N2.prev.next 4— .VI DeleteNodes(N2) mergednode <— N1 return mergednode end if end if end procedure

(6)

Рисунок 2.5 -Алгоритм слияния цепей (а), процедура объединения двух

вершин разных цепей (б).

Суть алгоритма заключается в следующем:

а) на первом этапе (строки 6-14) хвостовые узлы всех списков по ключу заносятся в хеш-таблицу. При этом проводится проверка на наличие в ячейке хэш-таблицы более чем одного узла. В случае обнаружения вызывается процедура NodeMerge (рисунок 2.5б, строки 17-34), которая возвращает номер узла слияния. Получившийся узел заносится в множество М (процедура РшИБаек);

б) процедура слияния списков NodeMerge является рекурсивной, так как в процессе процедуры слияния происходит спуск по имеющемуся списку (структуре), до тех пор, пока вершины объединяемых списков совпадают. В

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

в) в конце алгоритма по разности мощностей исходного множества Ь и получившейся в результате процедур слияния мощности множества М, вычисляется количество списков, которое не участвовало в слиянии;

г) на момент конца работы алгоритма множество М содержит всевозможные узлы слияния.

Пример 2.2. Продемонстрируем процедуру поиска узлов слияния на простом примере, представленном на рисунке 2.6.

Рисунок 2.6 - Пример графа межмодульных связей

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

Таблица 2.1. Перечень списков.

Номер списка Список

/1 н^СХ о-

/2 о-

Номер списка Список

/з

/4 о-

Рассмотрим пару списков (^, /2). Начиная с концов списков последовательно начинаем искать совпадающие по значению узлы, вплоть до вершины со значением (2), которая и будет являться узлом слияния. Отразим этот факт в таблице 2.2. Далее аналогичным способом получим узел слияния для списков

/з и /4.

Таблица 2.2. Перечень списков после слияния.

Номера списков Структура после слияния Точка слияния

/1 и /2 2

¡и |Ь

/ и /2 и /3 1

)—

И1

/ и /2 и /3 и /4 о-1 3

0—1

Результирующая асимптотическая сложность алгоритма является логарифмической с полиномиальным коэффициентом 0(| Ь |2Ы), однако при условии |Ь|«:АА она становится логарифмической 0(1о§Л^) и зависит от общего

количества звеньев в модели N.

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

а) структура, состоящая из независимых цепей (совпадает с исходной),

М = 0;

б) структура, состоящая из множества независимых цепей и множества структур с несколькими точками слияния, если |Ь| - |М| Ф 0;

в) полностью иерархическая структура, если |Ь| - М1= 0.

2.2 Условия наблюдаемости и управляемости иерархической модели

Сформулируем достаточные условия наблюдаемости и управляемости рассматриваемой диагностической модели, когда точек слияния более одной. При этом будем следовать логике доказательства, примененной в [12, 13], которая предполагает переход от периодически нестационарной модели к стационарной. Известно следующее свойство.

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

Для любой периодически нестационарной модели (2.2), имеющей на периоде функционирования один сеанс приема информации от СД, описываемый для некоторой последовательности индексов матрицами Г(у5(Ы)), С(у5(Щ),

Н(у,(N)), и один сеанс выдачи информации в СД, описываемый матрицами Г(у5(N -1)), С(у5(N -1)), Н(у5(N -1)), существует стационарная модель:

х(Т +1) = Ах(Т) + Ви(Т), у(Т) = Сх(Т), (2.4)

которая при любой входной последовательности формирует выходные последовательности, совпадающие с выходными последовательностями периодически нестационарной модели при у^. При этом х(Т), и(Т), у(Т) - вектора состояния, входа и выхода стационарной модели, А, В, С - матрицы динамики, входа и выхода, Т - период (рисунок 2.4) нестационарной модели, а матрицы:

Т

А = ¥п (у,) = П Р(У, (Т -1 +1)), В = С (у , (Т)),

¿=1

С = Н(у5 (Т - 1))Ж-1 (у, (Т - 1))Ж-1 (у, (Т ))А = Н(у5 (Т - 1))А.

■

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

Поиск условий осуществляется при следующих предположениях:

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

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

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

Утверждение 2.1. [12] Матрица динамики А1 стационарной цепи I, состоящей из V = (у }*=1 звеньев является неособенной нижней блочно-

п

треугольной с характеристическим многочленом ф = ^ф, где фг -

2=1

характеристический многочлен 2 -го звена, и имеет вид:

А1

»1.

f

2 12

п г

К2,3

1—1

Я . 1

п—1,п п

где 1 - матрица динамики /-го звена, К. .+1 = g¿+1h. - матрица связи между /-м и (/+1)-м звеньями.

Доказательство. Матрица сеанса обмена в нестационарной модели цепи по определению (см. пример 2.1) и в соответствии со свойством 2.2 является нижней блочно-треугольной с блоками 1 и К г+1. Во всех ее блоках на главной диагонали, кроме одного, расположены единичные матрицы Е. Единственный «неединичный» блок, который описывает обмен между соседними звеньями у и в данном сеансе имеет вид:

Е 0 '

ё+А 1+1.

где - произведение матриц входа и выхода, образующая матрицу связи

между /-м и (/+1 )-м звеньями.

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

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

Е

2,2+1

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

то и матрица А1 будет также неособенной. ■

а/

Утверждение 2.2. [13] Матрица динамики А стационарной модели Б/ со слиянием т цепей является неособенной нижней блочно-треугольной с

характеристическим многочленом ф

§/

фт

П (ф), ■

]=1 -1

ф ) , где ф0 - характеристический

■ К),

многочлен звена слияния у е М в степени т, (ф

многочлен] -й стационарной цепи, и имеет вид:

характеристический

А=

а;

К1,0 К

2,0

П ет

^т, 0

где А1. - матрица динамики у -й цепи, К 0 - матрица связи между у -й цепью и звеном слияния, 1 - матрица динамики звена слияния.

Доказательство. Формирование матриц динамики цепей было рассмотрено при обсуждении предыдущего утверждения. Они располагаются

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

Поскольку все матрицы А'., а также матрица 1т неособенные, то и матрица А

/

также неособенная. Степень т вхождения матрицы 1 в выражение для А объясняется тем, что звено слияния срабатывает т раз за период (т раз принимает информацию). ■

ак

Утверждение 2.3. [А17] Матрица динамики А стационарной иерархической модели 5,к является неособенной нижней блочно-треугольной с

характеристическим многочленом ф ^ = ф^

П (фБ )к •

к=1 к

где ф^ - характеристический

многочлен звена слияния у е М в степени q, фБ - характеристический многочлен

подсистемы Б, которая может быть представлена как моделью цепи, так и моделью с одной точкой слияния, и имеет вид:

АБ

»1,0 К

2,0

где матрица динамики АI соответствует к -й подсистеме.

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

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

Утверждение 2.4. [А2] Иерархическая стационарная модель Бк, включающая ц=|М| точек слияния, наблюдаема и управляема, если для любой

точки слияния г = 1, ц, в звене слияния скалярных подсистем из множества (Б }1=\, выполняется:

к

а) подсистемы (Б }|=1 наблюдаемы и управляемы;

б) характеристические многочлены ((фБ)Лч=1 подсистем, характеристический многочлен ф матрицы динамики звена слияния и

многочлены (ск }д=1 числителей передаточных функций (Зк }д=1 звена слияния взаимно просты.

Доказательство. Покажем сначала наблюдаемость иерархической структуры Бк. Базис пространства выходных последовательностей иерархической структуры в ' -ой точке слияния, заданный на периоде Т (период выходных

последовательностей свободного движения иерархической структуры Бк), при свободном движении складывается, во-первых, из базиса подпространства выходных последовательностей свободного движения звена слияния и, во-вторых, из базисов аналогичных подпространств объединяемых подсистем, переработанных звеном слияния и заданных на том же периоде.

Первый базис - базис подпространства р выходных последовательностей свободного движения звена слияния - представляется воспроизводящей матрицей

Т

[10] V этого звена, повторенной — раз на периоде Т, где Т - период выходной

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

4>(х) = ^-(1 + ^ + ^ +... + Хт~т-) = (2.5)

¿■+Х2Т-+... + ХТ-Т'

еч \ / т ед '

Многочлен для второго вектора получается из (2.5) умножением на х, для третьего - на х2 и т.д. для последнего - на х"'_1 (щ - размерность звена слияния).

Далее для описания остальных базисов - базисов подпространств выходных последовательностей свободного движения подсистем, переработанных звеном слияния - удобно воспользоваться известным [10] d-преобразованием для последовательностей над полями Галуа. В этом случае последовательности

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

Л = И,№ +Е)"хь = ^±Е!хЪ (2.6)

фГq (Х)

где (xfJq + Е)п - матрица алгебраических дополнений, выраженных степенными многочленами, ф* (х) - многочлен, двойственный [10] к характеристическому многочлену ф (х).

Базис подпространства р выходных последовательностей свободного движения к-й подсистемы представляется воспроизводящей матрицей V этой

Т

подсистемы, повторенной — раз на периоде Т, где Тк - период выходной

Тк

последовательности свободного движения к-й подсистемы, т.е. базис имеет вид [У7 V, • • • V/ ]. Следуя (2.6), но учитывая обработку в звене слияния получаем многочлен, описывающий первый вектор из базиса к-й подсистемы

*/(*) = + * + ^ + - + ^ )Л = (2.7)

с (Х)

Подставляя в (2.7) ^ = » , получаем:

фг q (х)

*: (х) = ^ Щ. (2.8)

фк(х) ф„(х)

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

я

а( х)П х) + £ К (х)^к (х)Л (х) = 0, (2.9)

к=1

где a(x) и К (x) - многочлены, отражающие сдвиги базисных векторов, просуммированных в подпространствах р и Рк соответственно. Подставляя выражения для , и ^ , получаем

гТ Я 1 _1_ УТ

1 + х ^ 1 + х ск (х) а(х)-+ £ К (х)--^- = 0,

фГ* (х) к=1 фк (х)фр (х)

а после преобразования имеем:

а( х)ф*.(х)П Фк(х) = Х

£=1 к=1

Кк( х)Фг ,(х)ск(х)П Ф .(х)

^=1

я Фк

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

зависимости неверно и базисные векторы из подпространств Р и Р линейно независимы.

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

Утверждение 2.5. [ А2] Если модель (2.4) наблюдаема (управляема), то модель (2.2) у 8 -наблюдаема (у8 -управляема).

Таким образом, условия наблюдаемости и управляемости (утверждение 2.4), сформулированные для стационарной модели, являются также и условиями у8 -наблюдаемости и у8 -управляемости для нестационарной.

Утверждение 2.6. [А2] Если периодически нестационарная модель -наблюдаема и уз -управляема, и все матрицы динамики этой модели неособенные, то она полностью наблюдаема и управляема.

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

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

Пример 2.3. Продолжим пример 2.1, конкретизировав вид звеньев. Будем использовать однородные цепи, т.е. состоящие из одинаковых звеньев. Чтобы выполнить условие (2.5) из утверждения 2.4, выберем для звеньев цепей размерность, равную 3, а для звена слияния, равную 2. Пусть описание звеньев имеет вид:

а) звенья нестационарных цепей:

е = е = е = е = е1 12

1 0 1" 1 0 0 010

§1 § 2 §3 §4

Ь1 =Ь2 =Ь3 =Ь4 =[0 0 Фе =Фг2 = Фг3 = Фг4 =Х' + х2 + 1 б) звено слияния нестационарной модели:

, Ь0 =[0 1], ^ = х2 + х +1,

"1 1" "1"

1 0 , §0 0

в) звенья стационарных цепей:

"1 0 1"

f = f = f = f

2 13 4

1 о о 0 1 0

5 §1 §2 §3 §4

, Ь1=Ь2 = [0 0 1],

й3=й4=[0 1 0], ф? =ф? =ф? =ф? = д:3 +х2 +1,

г) звено слияния стационарной модели:

{ = р =

"0 1" "1 Г

1 1_ 5 §0 1 0_

Й0 = [1 1], =х2 +х + \.

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

2.3 Интервальная диагностическая динамическая модель систем

управления

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

Перейдем к рассмотрению интервальной модели системы, используемой далее для решения второй задачи, а именно, ФД систем управления в условиях модельной неопределенности. При этом построение классических наблюдателей Люенбергера, используемых в детерминированном подходе и сходящихся к точному значению состояния системы, как будет показано в главе 3, будет недостаточно эффективным. Применение методов скользящих режимов [127, 128], адаптивных наблюдателей с расширенным вектором состояния [91, 92, 123], наблюдателей с большим коэффициентом обратной связи [87, 106, 132] или других методов компенсации возмущения в некоторых конкретных случаях может разрешить проблему, однако в целом при наличии неопределенности ошибка оценивания состояния не стремится к нулю. Тем не менее, в этом случае существует возможность синтеза интервального наблюдателя, который, используя информацию о входе и выходе системы, формирует в каждый момент времени на множестве допустимых значений интервал, в котором находится вектор состояния. В этом случае ширина интервала пропорциональна уровню неопределенности в системе и может быть настроена через параметры наблюдателя. Интервальный наблюдатель также

52

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

Существует несколько методов построения интервальных/конечно-множественных наблюдателей [104, 105, 115]. В работе будет рассмотрен подход, который основан на теории монотонных систем [88, 98]. Впервые эта идея была предложена в [37] и уже получила значительное развитие в зарубежной литературе. Главное ограничение при построении интервального наблюдателя состоит в обеспечении свойства кооперативности динамики ошибки интервальной оценки. Решение этой проблемы было предложено в работах [79, 111, 112] для линейных стационарных систем и расширено на линейные нестационарные системы с переменными параметрами [17, 39, 40, 85, 108], а также на особый класс нелинейных систем [124, 125].

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