Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

ТЕСТИРОВАНИЕ АЛГОРИТМОВ МУРАВЬИНОЙ КОЛОНИИ ДЛЯ ФОРМИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ

Ковалев И.В. 1, 2, 3 Ковалев Д.И. 2, 4 Боровинский Д.В. 5 Мансурова Т.П. 4 Ворошилова А.А. 1, 4
1 ФГАОУ ВО «Сибирский федеральный университет»
2 ФГБОУ ВО «Красноярский государственный аграрный университет»
3 ФГБОУ ВО «Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнева»
4 Красноярский краевой Дом науки и техники РосСНИО
5 ФГБОУ ВО «Сибирская пожарно-спасательная академия ГПС МЧС России»
В статье представлены результаты тестирования алгоритмов муравьиной колонии для формирования программного обеспечения системы обработки данных реального времени долговременной орбитальной станции. Система характеризуется временными ограничениями на реализацию множества выполняемых функций и накладываемыми ограничениями на способы реализации программной избыточности при мультиверсионной реализации программного обеспечения. Таким образом, сравнительный анализ модификаций алгоритмов муравьиной колонии, применяемых для формирования отказоустойчивого программного обеспечения, является актуальной задачей для рассматриваемых систем обработки данных реального времени. Представлен состав модулей тестовой программной системы. Все версии программных модулей характеризуются показателями надежности и стоимости их использования. Учитывается, что каждый режим работы станции характеризуется своим набором модулей, которые обеспечивают выполнение функций этого режима, а также своей целевой функцией и ограничениями на итоговое решение. Для каждого из режимов полета долговременной орбитальной станции представлены соответствующие схемы программной системы. Кратко описаны характеристики режимов, входящие в макетный план полета, которому и соответствуют представленные схемы программной системы. Используемая при тестировании модификация алгоритма муравьиной колонии заключается в изменении формулы расчета весов дуг, введении нового коэффициента, учитывающего ресурсоемкость (стоимость использования модуля) и возможности анализа динамической (изменяемой) архитектуры программы для восходящего принципа проектирования программных систем. В статье представлены графики изменения показателей надежности и стоимости использования модулей программной системы в процессе выполнения плана полета. В результате анализа тестовых данных сделан вывод о том, что модифицированный алгоритм по всем параметрам превосходит стандартный, что должно обеспечить его преимущественное использование при формировании программного обеспечения системы обработки данных реального времени долговременной орбитальной станции.
программное обеспечение
система реального времени
алгоритм муравьиной колонии
мультиверсионная программа
тестирование
схема программы
1. Ковалев И.В., Ковалев Д.И., Брит А.А., Сарамуд М.В. Информационная технология для мультиверсионного формирования отказоустойчивых программных систем // Системы управления и информационные технологии. 2021. № 2 (84). С. 56–68. DOI: 10.36622/VSTU.2021.84.2.013.
2. Зенюткин Н.В., Ковалев Д.И., Туев Е.В., Туева Е.В. О способах формирования информационных структур для моделирования объектов, сред и процессов // Современные инновации, системы и технологии. 2021. № 1 (1). С. 10–22. DOI: 10.47813/2782-2818-2021-1-1-10-22.
3. Буховцев Д.Д. Применение модифицированного алгоритма муравьиной колонии для решения задачи календарного планирования распределенных предприятий // Современные инновации, системы и технологии. 2021. № 1 (1). С. 29–42. DOI: 10.47813/2782-2818-2021-1-1-29-42.
4. Балыбердин В.А., Белевцев А.М., Степанов О.А. Анализ основных процессов обеспечения надёжности программных средств АСУ специального назначения // Известия Южного федерального университета. Технические науки. 2015. № 3 (164). С. 62–70.
5. Saramud M.V., Kovalev I.V., Losev V.V., Karaseva M.V., Kovalev D.I. On the application of a modified ANT algorithm to optimize the structure of a multiversion software package // Lecture Notes in Computer Science. 2018. Vol. 10941. P. 91–100.
6. Липаев В.В. Надежность и функциональная безопасность комплексов программ реального времени. М.: ЗАО «Светлица», 2013. 192 с.
7. Данилов А.А. Комплекс программ оценивания надежности и планирования разработки программных средств на основе динамических моделей // Интеллектуальные технологии на транспорте. 2017. № 4. С. 18–24.
8. Грузенкин Д.В., Якимов И.А., Кузнецов А.С., Царев Р.Ю. Определение метрики диверсифицированности мультиверсионного программного обеспечения на уровне алгоритмов // Фундаментальные исследования. 2017. № 6. С. 36–40.
9. Микрин Е.А., Кульба В.В., Павлов Б.В. Разработка моделей и методов проектирования информационно-управляющих систем космических аппаратов // Автоматика и телемеханика. 2013. № 3. С. 38–50.
10. Зубов Н.Е., Ли М.В., Микрин Е.А., Рябченко В.Н. Терминальное построение орбитальной ориентации космического аппарата // Известия Российской академии наук. Теория и системы управления. 2017. № 4. С. 154–173. DOI: 10.7868/S0002338817040138.
11. Микрин Е.А., Сомов С.К. Оптимизация резервирования информации в распределенных системах обработки данных реального времени // Проблемы управления. 2016. № 6. С. 47–52.
12. Быкова В.В. О мерах целостности графов: обзор // Прикладная дискретная математика. 2014. № 4 (26). С. 96–111.
13. Dorigo M., Stutzle T. Ant Colony Optimization. Cambridge: MIT Press, 2004. 305 p.
14. Белых М.А., Барабанов В.Ф., Подвальный С.Л., Донских А.К. Структура интеллектуальной системы поддержки эволюционных алгоритмов // Вестник Воронежского государственного технического университета. 2021. Т. 17. № 3. С. 7–13.
15. Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Однородная распределительная задача на основе моделей адаптивного поведения муравьиной колонии // Программные продукты и системы. 2017. Т. 30. № 2. С. 217–226. DOI: 10.15827/0236-235X.118.217-226.

В работах [1–3] рассмотрен ряд модификаций алгоритма муравьиной колонии, применяемых для решения задач формирования отказоустойчивых программных систем для управления объектами критических приложений. Такие объекты характеризуются сложностью процессов управления, а системы обработки информации в таких объектах непосредственно влияют на эффективность функционирования аппаратных и программных средств, выполняющих ключевые функции по управлению объектом [4–7]. Система обработки данных реального времени долговременной орбитальной станции (ДОС) характеризуется временными ограничениями на реализацию множества выполняемых функций и накладываемыми ограничениями на способы реализации программной избыточности при мультиверсионной реализации программного обеспечения (ПО) [8]. Таким образом, сравнительный анализ модификаций алгоритмов муравьиной колонии, применяемых для формирования отказоустойчивого ПО, является актуальной задачей для систем данного типа [9–11].

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

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

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

Объект управления и постановка задачи

При формулировке тестовой задачи рассматривается четыре группы управляемых процессов в ДОС [9]: процессы движения ДОС; рабочие процессы (целевое назначение ДОС); энергетические процессы; процессы жизнеобеспечения космонавтов. Анализ алгоритмов решения бортовых задач ДОС и их особенностей [10] позволяет ставить задачу формирования мультиверсионного программного обеспечения с динамической (изменяемой) архитектурой.

В общем виде динамическую архитектуру ПО представим, как t-уровневую программную систему с мультиверсиями. Количество мультиверсий i-го типа в f-м модуле программы l-го уровня обозначим bilf , а clf – f-й модуль l-го уровня мультиверсионной программы.

Для каждого модуля j ∈ K имеется множество Dji мультиверсий i-го типа, доступных для него в системе резервирования. Отметим, что для всех модулей одного множества, множество Dji будет иметь один и тот же вид. Тогда «стирание» ребер в графе структуры программы с резервными мультиверсиями модулей, то есть связывающих j-й модуль с доступным для него множеством мультиверсий, соответствует сужению множества F(Dji). Это свидетельствует об удалении тех мультиверсий, в которые входят ставшие недоступными ресурсы. Очевидно, что тогда множество дестабилизирующих воздействий на мультиверсионную программу (резервируемую) может быть частично упорядочено относительно сужения множеств F(Dji), где j ∈ K.

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

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

Результаты решения тестовой задачи

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

Модули тестовой программной системы

Модуль

Назначение

UI

Получение и сбор информации для ее последующего использования

NAV

Выработка управляющих воздействий для движения станции

NAVLIM

Выработка ограничений на управляющие воздействия

ORIENT

Ориентация станции

ROTATION

Вращение станции

MOVE

Движение станции

AMOVE

Сегмент, отвечающий за движение станции

ENERGY

Система энергопитания станции

Solar

Управление солнечными батареями

EManager

Распределение энергии на станции

AESM

Взаимодействие с сегментом, отвечающим за энергоснабжение

LSMonitor

Контроль за параметрами жизнедеятельности

LSManager

Изменение параметров жизнедеятельности

BordSystemM

Слежение за параметрами бортовых систем

BordSystemR

Восстановление систем в случае их сбоя

ObjectSDMonitor

Система слежения за внешними объектами

ObjectSDControl

Система контроля скорости и направления внешних объектов

FuelAnalizer

Сбор и анализ информации об уровнях топлива

RefuelControl

Обеспечение дозаправки станции

ManipulatorControl

Управление внешними манипуляторами станции

ManipulatorLim

Задание ограничений на управляющие воздействия, передаваемые на манипуляторы

DataSaver

Сохранение и отправка данных о работе станции

Схемы ПС каждого из режимов полета ДОС представлены на рис. 1–5. Задача характеризуется следующим планом полета с учетом режима квантования времени [11]:

− Стандартный режим: 0 ≤ t < 100, C → min, Rmin = 0,95.

− Стыковка: 100 ≤ t < 200, R → max, Cmax → 300.

− Стандартный: 200 ≤ t < 300, C → min, Rmin = 0,95.

− Внешняя деятельность: 300 ≤ t < 400, R → max, Cmax → 350.

− Стыковка: 400 ≤ t < 500, R → max, Cmax → 250.

− Коррекция орбиты: 500 ≤ t < 600, R → max, Cmax → 400.

− Микрогравитация: 600 ≤ t < 700, C → min, Rmin = 0,98.

− Стандартный: 700 ≤ t < 800, C → min, Rmin = 0,95.

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

missing image file

Рис. 1. Схема программы в режиме внешней деятельности

missing image file

Рис. 2. Схема программы в режиме коррекции орбиты

missing image file

Рис. 3. Схема программы в режиме микрогравитации

missing image file

Рис. 4. Схема программы в стандартном режиме

missing image file

Рис. 5. Схема программы в режиме стыковки

Стандартный алгоритм построен по классической схеме [13–15]. Модификация алгоритма отражена в [1, 3–5] и заключается в изменении формулы расчета весов дуг, введении нового коэффициента, учитывающего ресурсоемкость (стоимость использования модуля C) и возможности анализа динамической (изменяемой) архитектуры программы для восходящего принципа проектирования ПС.

На рис. 6 представлены графики изменения показателей стоимости использования модулей ПС в процессе выполнения плана полета. В результате анализа полученных данных было установлено, что среднее значение стоимости, которое достигалось при использовании модифицированного алгоритма, на 4,96 % лучше, чем при использовании стандартного алгоритма. Как видно из графика, модифицированный алгоритм быстрее достигает результатов, которые были достигнуты при использовании стандартного алгоритма. При использовании модифицированного алгоритма тратилось в среднем на 70,86 % меньше времени на достижение результатов, полученных с помощью стандартного алгоритма.

missing image file

Рис. 6. Изменение стоимости решения в процессе выполнения плана полета

missing image file

Рис. 7. Изменение надежности ПС решения в процессе выполнения плана полета

На рис. 7 представлены графики изменения показателей надежности ПС в процессе выполнения плана полета. В результате анализа полученных данных было установлено, что среднее значение надежности, которое достигалось при использовании модифицированного алгоритма, на 0,086 % лучше, чем при использовании стандартного алгоритма. График показывает, что модифицированный алгоритм быстрее достигает результатов, которые были достигнуты при использовании стандартного алгоритма. Также при использовании модифицированного алгоритма тратилось в среднем на 59,5 % меньше времени на достижение результатов стандартного алгоритма.

Заключение

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

Проведение исследований по проекту осуществляется при поддержке Краевого государственного автономного учреждения «Красноярский краевой фонд поддержки научной и научно-технической деятельности» в соответствии с заявкой 2021110907918.


Библиографическая ссылка

Ковалев И.В., Ковалев Д.И., Боровинский Д.В., Мансурова Т.П., Ворошилова А.А. ТЕСТИРОВАНИЕ АЛГОРИТМОВ МУРАВЬИНОЙ КОЛОНИИ ДЛЯ ФОРМИРОВАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ // Современные наукоемкие технологии. – 2022. – № 5-2. – С. 189-196;
URL: https://top-technologies.ru/ru/article/view?id=39169 (дата обращения: 17.08.2022).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074