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

Ключевые слова: телеметрическая информация, сети Петри, техническая диагностика, параллельная граф-схема алгоритма.

В рамках определения оптимальных параметров при построении модели функционирования и технического диагностирования программируемых логических интегральных схем автономных технических средств (далее — ПЛИС АТС) рассмотрим классификацию моделей для решения задачи технического диагностирования ПЛИС АТС. Анализ моделей для описания процессов функционирования и контроля систем представлен в табл. 1.

Таблица 1

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

Данный аппарат предназначен для формализации стационарных дискретных динамических систем, обладает высокой моделируемой мощностью и необходимым уровнем абстракции. Также данный математический аппарат является универсальным, на его основе могут быть построены модельные конструкции, превосходящие по своим моделирующим возможностям различные дискретные модели с конечным или счетным множеством состояний [3]. Известно, сети Петри используются для моделирования асинхронных систем, функционирующих как совокупность параллельных взаимодействующих процессов. Анализ сетей Петри позволяет получить информацию о структуре и динамическом поведении моделируемой системы [4, 5].

Причинно-следственная связь событий в асинхронных системах задается множеством отношений вида «условия-события».

Построение моделей систем в виде сетей Петри заключается в следующем:

1. Моделируемые процессы описываются множеством событий (действий) и условий, определяющих возможность наступления этих событий, а также причинно-следственными отношениями, устанавливаемыми на множестве пар «события-условия».
2. Определяются события-действия, последовательность выполнения которых управляется состояниями системы. Состояния системы задаются множеством условий, формируемых в виде предикатов. Количественно условия характеризуются величиной, которая выражается числами натурального ряда.
3. Условия, в зависимости от значений их количественных характеристик, могут выполняться или нет. Выполнение условий обеспечивает возможность реализации событий. Условия, с фактом выполнения которых связывается возможность реализации событий, называются предусловиями. Реализация события обеспечивает возможность выполнения других условий, находящихся с предусловиями в причинно-следственной связи. Эти условия называются постусловиями.

В сетях Петри условия − это позиции, а события − переходы.

В соответствии с этим граф сети Петри является двудольным ориентированным мультиграфом. Изображение позиции и перехода на графе показано на рис. 1 [2].

Рис. 1. Составляющие сети Петри: а) позиции, б) переходы

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

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

Сеть Петри определяется пятеркой

где − множество позиций;

− множество переходов;

− функция следования;

− функция предшествования;

− начальное маркирование (состояние) сети;

— множество положительных целых чисел.

Функции и задают множества дуг и соответственно.

Дуги, предшествующие позиции , обозначим множеством , а дуги, предшествующие переходу , множеством .

Здесь запись означает наличие дуги , а запись − дуги . Аналогично, дуги, следующие из и , представим множествами , .

Входные позиции перехода объединяются в множества его предшественников , а выходные позиции — в множества позиций — последователей .

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

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

Если при маркировании возбуждено несколько переходов, то порядок их срабатывания не определен, и, следовательно, может быть представлено несколько последовательностей срабатывающих переходов [2, 4].

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

Безопасность. Позиция сети является безопасной, если для любой .

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

Ограниченность. Безопасность — это частный случай более общего свойства ограниченности. Безопасность позволяет реализовать позицию триггером, а в более общем случае можно использовать счетчик. Любой счетчик ограничен по максимальному числу . Соответствующая позиция также является -безопасной или -ограниченной, если количество меток в ней не может превысить целое число .

Позиция сети является -безопасной, если для всех .

Позиция называется ограниченной, если она -безопасна для некоторого . Сеть Петри ограничена, если все ее позиции ограничены.

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

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

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

Тупик в сети Петри — это переход (или множество переходов), которые не могут быть запущены.

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

Задача покрываемости. Для сети с начальной маркировкой и маркировки определить, существует ли такая достижимая маркировка , что .

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

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

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

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

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

Для каждой существует хотя бы один путь от вершины к и хотя бы один путь от к вершине .

Графическое представление вершин параллельные граф-схемы различных типов представлены в литературе [5].

Управляющие вершины граф-схемы делятся на две группы: вершины «распараллеливания» ( и ) и вершины условного ветвления ( и ).

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

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

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

Существует четыре типа отношений между вершинами параллельной граф-схемы:

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

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

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

Осуществим формальный переход от модели анализа технического состояния ПЛИС АТС в операторной форме к модели, построенной на основе теории сетей Петри, изображенной на рис. 1.

Рис. 1. Схема модели анализа технического состояния ПЛИС АТС

На первом этапе происходит определение разметки сети ПЛИС АТС. С формальной точки зрения разметка сети представляет собой отображение:

где — множество вершин, называемых позициями и графически обозначаемых кружками;

— множество всех натуральных чисел.

Необходимо отметить, что определение разметки сети происходит на основе определения функции инцидентности [4]:

где — множество вершин, называемых перепадами и графически обозначаемыми чертами.

После определения разметки сети вводится отношения непосредственного следования разметок [5]:

где — принадлежность, отношение непосредственного следования разметок;

, — целочисленные вектора для каждого перехода .

На основании отношения непосредственного следования разметок определяется отношение множества разметок, достижимых в .

где — множество всех разметок , достижимых в от начальной разметки , заметим, что и .

На втором этапе происходит определение разметки сети ПЛИС АТС с учетом дополнительной диагностической информации. Необходимо отметить, что разметка . Исходя из этого, разметка сети с учетом дополнительной диагностической информации, представляет собой отображение:

где — множество вершин модели, участвующих при получении дополнительной диагностической информации;

— множество всех натуральных чисел.

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

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

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

или выражение (11) можно представить в виде:

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

— выражение, которое обозначает класс эквивалентности для некоторого набора множества разметок ПЛИС.

Помимо вводится оператор факторизации:

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

или выражение (14) можно представить в виде:

Принятие решения о техническом состоянии ПЛИС с математической точки зрения может быть определено через оператор в следующем виде:

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

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

Литература:

1. Лоскутов А. И. Идентификация бортовой радиоэлектронной аппаратуры космических аппаратов как основа управления реконфигурацией в интересах повышения живучести — Приборы и системы. Управление, контроль, диагностика, 2018.
2. Столяров А. В. Методика построения математической модели процесса функционирования беспилотного авиационного комплекса с целью решения задачи технического диагностирования. — Надежность и качество сложных систем, 2020.
3. Максимов А. А. Один подход к построению конечно-автоматной управляющей сети. — Вестник Московского государственного технического университета имени Н. Э. Баумана. Серия «Приборостроение», 2012.
4. Лукин М. В. Свидетельство о государственной регистрации программ для ЭВМ № 2020662638 от 16.10.2020. Российская Федерация. Программный комплекс идентификации и технического диагностирования бортовой радиоэлектронной аппаратуры космических аппаратов — РОСПАТЕНТ, 2020.
5. Pelletier B. A. Petri Net Generation Tool for the Verification of Skillset-based Autonomous Systems — SkyNet, 2022.