Алгоритмы ресурсосберегающего автономного контроля массива данных наблюдения в беспилотных летательных аппаратах

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

Если собранная информация представляет собой набор блоков данных (далее – БД), то ее предварительная обработка заключается в последовательном анализе и отбраковке

Басыров Александр Геннадьевич доктор технических наук, профессор, начальник кафедры информационно-вычислительных систем и сетей. Военно-космическая академия имени А.Ф. Можайского, Санкт-Петербург. Сфера научных интересов: информационные вычислительные системы, высокопроизводительная обработка информации. Автор более 150 опубликованных научных работ.

непригодных блоков. Кроме того, возможны и другие действий над БД, например, распознавание, сжатие, фильтрация [5; 6].

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

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

Используемые методы контроля на основе ускоренных испытаний [3; 4] в рассматриваемой постановке задачи неприемлемы из-за малого размера партии продукции, отсутствия статистики по отказам и существенным ограничениям на время и ресурсы контроля БД.

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

Показатель качества ресурсосберегающего анализа данных

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

Показатель качества ресурсосберегающего анализа данных определим выражением k = nnfi - nn ) , n д I N J

где n _n - количество проверенных БД ( n _n <  N ); n _д - количество дефектных БД ( n _д >  1 ); n _дп - количество выявленных в результате проверки дефектных БД ( n _дп <  n _д , n _дп <  n _n ); N – общее количество БД.

При этом свойствами показателя качества являются:

Алгоритмы ресурсосберегающего автономного контроля массива данных ...

– область значений [0,1];

- все параметры ( n _ДП , n _Д , n _П , N ) - целые положительные числа.

Взаимосвязь параметров ( n _ДП , n _Д , n _П , N ) проиллюстрирована на Рисунке 1.

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

Физический смысл показателя (1) состоит в произведении результативности n ДП по- n Д

иска дефектных БД на дополнительную величину затрат — , то есть экономию, связанную с этим поиском.                                 ^N

Рассмотрим следующие типовые варианты размещения дефектных блоков в памяти:

– дефектные БД распределены равномерно в памяти;

– дефектные БД распределены компактно в некоторой области памяти;

– дефектные БД распределены компактно в нескольких областях памяти.

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

Рисунок 2. Варианты размещения дефектных блоков данных в памяти: а – равномерное распределение дефектных блоков в памяти; б – случайное распределение дефектных блоков в памяти; в – компактное распределение дефектных блоков в одной области памяти; г – компактное распределение дефектных блоков в нескольких областях памяти

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

Алгоритмы ресурсосберегающего анализа качества данных

Рассмотрим следующие варианты порядка проверки, то есть предварительной обработки БД в памяти:

– последовательно – блоки проверяются поочередно в порядке их размещения в памяти;

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

– по правилу половинного деления номеров блоков: номер первого БД определяется как целая часть от

N

; номер второго – как целая часть от

N

; третьего – как целая

	3 N		N		3 N
часть от	24	; четвертого – как целая часть от	8	; пятого – как целая часть от	8	;

-	5 N	"	-	7 N	"
шестого – как целая часть от		; седьмого	– как целая часть от		и т. д.
_	8	_	_	8	_

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

Алгоритм 1. Последовательный анализ блоков данных.

Шаг 1. Начало.

Шаг 2. i : = 1 .

Шаг 3. Проверка пригодности i -го БД.

Шаг 4. i : = i + 1 .

Шаг 5. Если i >  N , то переход на шаг 6, иначе - на шаг 3.

Шаг 6. Конец.

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

Шаг 1. Начало.

Шаг 2. Сформировать массив G номеров БД g j = j , g j е G , j = 1, N .

Шаг 3. n : = N .

Шаг 4. На основе датчика случайных чисел сгенерировать целое число b в интервале от 1 до n .

Шаг 5. Проверка пригодности b -го БД.

Шаг 6. Удалить из массива G элемент g_b .

Шаг 7. n : = n - 1 .

Шаг 8. Если n <  1 , то переход на шаг 9, иначе - на шаг 4.

Шаг 9. Конец.

Алгоритм 3. Анализ блоков данных по правилу половинного деления их номеров.

Шаг 1. Начало.

Шаг 2. c : = 1 .

Шаг 3. i : = 2 .

Шаг 4. j : = 1 .

Шаг 5. b : = [ j ■ N / i ] .

Шаг 6. Проверка пригодности b -го БД.

Шаг 7. c : = c + 1 .

Шаг 8. Если c >  N , то переход на шаг 12, иначе - на шаг 9.

Шаг 9. j : = j + 2 .

Шаг 10. Если j >  i , то переход на шаг 11, иначе - на шаг 5.

Шаг 11. i : = i ■ 2 . Переход на шаг 4.

Алгоритмы ресурсосберегающего автономного контроля массива данных

Шаг 12. Конец.

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

На Рисунке 3 представлены зависимости значения показателя (1) от количества проверок пригодности БД для трех описанных алгоритмов при расположении четырех дефектных БД из 20, изображенных на Рисунке 2.

Изображение вариантов размещения БД на графиках (см. Рисунок 3) имеет вид

____________ - последовательный анализ (алгоритм 1);

_____- анализ в случайном порядке (алгоритм 2);

- анализ половинным делением номеров БД (алгоритм 3).

Рисунок 3. Пример зависимости значения показателя (1) от количества проверок для различных вариантов размещения дефектных блоков данных: а – равномерное (см. Рисунок 2, а ); б – случайное (см. Рисунок 2, б ); в – компактное распределение дефектных блоков в одной области памяти (см. Рисунок 2, в ); г – компактное распределение дефектных блоков в нескольких областях памяти (см. Рисунок 2, г )

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

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

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

Имитационное моделирование заключается в следующем.

Генерируются все возможные варианты массива пригодных и дефектных БД заданного размера N .

Каждым из рассматриваемых алгоритмов предварительной обработки БД проводится анализ пригодности сгенерированных БД. На каждом j-м прогоне модели рассчитывается значение функционала ф =

N

1 v , ⁿ да 1 1 i i i i -

N^ n_a I N ) i = 1      A

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

– среднее значение

1 n ^ф=-^1 ; n j = 1

– частота выборки для каждого k -го алгоритма

• -   1 n

h k =- У h kj , n j = 1

где h kj = 1, если h kj = max( h 1 j , h 2 j ,..., h _a j ) ; h kj = 0 - в противном случае; j = 1, n , k = 1, a , a - количество применяемых алгоритмов предварительной обработки БД.

Исходные данные модели: доля ц дефектных БД в общем множестве БД и количество

П итераций моделирования.

Результаты имитационного моделирования представлены на Рисунке 4.

Рисунок 4. Зависимоcти характеристик показателя качества от количества дефектных БД для N = 20: а - зависимость ф от количества дефектных БД; б - зависимость h k от количества дефектных БД

Представленные зависимости наглядно демонстрируют преимущество алгоритма анализа БД по правилу половинного деления их номеров.

Заключение

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

Алгоритмы ресурсосберегающего автономного контроля массива данных ...

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

Из представленных алгоритмов в условиях полной неопределенности размещения дефектных БД в памяти наиболее результативным является алгоритм, определяющий последовательность аназиза БД на основе половинного деления их номеров.

Следует отметить, что для обеспечения ресурсосберегающего анализа данных необходимо определить не только порядок (алгоритм) проверки БД, но и найти оптимальное количество проверок в условиях неопределенности качества БД. Этот выбор связан с обоснованием одной из двух стратегий: первая подразузамевает, что после проверки некоторого подмножества БД остальные БД считаются дефектными, вторая заключается в проверке некоторого подмножества БД и принятии гипотезы, что все остальные БД являются пригодными. Первая стратегия связана с риском забраковать пригодные БД (ошибка первого рода), вторая – допускакет пропуск брака (ошибка второго рода) [4].

Выбор той или иной стратегии представляет собой отдельную задачу [1; 2].