WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


На правах рукописи

Соколов Игорь Сергеевич

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

05.13.18 – Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург – 2012

Работа выполнена в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ» им. В.И. Ульянова (Ленина) (СПбГЭТУ) на кафедре «Математическое обеспечение и применение ЭВМ».

Научный консультант: кандидат технических наук, доцент, Балтрашевич Владимир Эдуардович

Официальные оппоненты: доктор технических наук, профессор, Куприянов Михаил Степанович, декан факультета компьютерных техноло­ гий и информатики, СПбГЭТУ кандидат технических наук, Игнатов Дмитрий Игоревич, старший преподаватель кафедры анали­ за данных и искусственного интеллекта, НИУ ВШЭ

Ведущая организация: Открытое акционерное общество «Госу­ дарственный ракетный центр имени ака­ демика В.П. Макеева»

Защита состоится «16» мая 2012 г. в 15 часов на заседании совета по защите докторских и кандидатских диссертаций Д212.238.01 при СПбГЭТУ, располо­ женном по адресу: 197376, Россия, Санкт-Петербург, улица Профессора По­ пова, дом

С диссертацией можно ознакомиться в библиотеке СПбГЭТУ «ЛЭТИ».

Автореферат разослан «13» апреля 2012 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д212.238.01, к.т.н. Щеголева Н.Л.

Общая характеристика работы

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

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

Cуществует определенный задел в литературе, представленный работами Балтрашевича В. Э., Васильева А. В., Кукушкина С. С. и опытно-конструктор­ скими работами, проводимыми в научно-исследовательском центре представле­ ния и контроля информации по космодрому Плесецк, однако, большинство из существующих решений находятся на этапе развития, когда большая часть дей­ ствий выполняется непосредственно экспертом. При этом практически не ис­ пользуется информация о ранее накопленных ГТС с известными структурами.

Как следствие, восстановление структуры одного ГТС с неизвестной структу­ рой от объекта РКТ в среднем требует не менее нескольких часов. Необходимо подчеркнуть, что это труд высококвалифицированных специалистов, нехватка которых является острой проблемой. Таким образом, является актуальной за­ дача разработки методов и моделей восстановления структуры ГТС, которые позволят сократить время восстановления.

Цель и задачи исследования — разработка методов и моделей, обеспе­ чивающих сокращение времени восстановления структуры ГТС c неизвестной структурой за счет повышения степени автоматизации восстановления и ис­ пользования информации о ранее накопленных ГТС с известными структура­ ми.

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

1) анализ существующих решений задачи восстановления структуры ГТС c неизвестной структурой и выработка путей преодоления их основных недо­ статков;

2) разработка трехэтапной процедуры восстановления структуры ГТС с неизвестной структурой;

3) разработка метода экспресс-поиска структуры ГТС c использованием информации о ранее накопленных ГТС с известными структурами;

4) разработка метода последовательного восстановления структуры ГТС с неизвестной структурой, базирующегося на анализе бинарного представления ГТС и позволяющего определить типы медленноменяющихся телеметрических параметров;

5) разработка графовой модели ГТС, учитывающей структуру ГТС и по­ ведение входящих в его состав параметров, и метода комплексного поиска структуры ГТС, использующего данную модель;

6) программная реализации предлагаемой трехэтапной процедуры восста­ новления структуры ГТС.

Объектом исследования диссертационной работы является процесс вос­ становления структуры ГТС.

Предметом изучения являются методы и алгоритмы, позволяющие осу­ ществить восстановление структуры ГТС, а также модели описания ГТС и его структуры.

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

Научную новизну работы составляют следующие положения:

1) Трехэтапная процедура восстановления структуры ГТС с неизвестной структурой, включающая этап экспресс-анализа (применяется метод экспресс­ поиска), этап полного анализа (метод последовательного восстановления) и этап уточнения (метод комплексного поиска).

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

3) Метод последовательного восстановления структуры ГТС с неизвест­ ной структурой, позволяющий на основе анализа бинарного представления ГТС в автоматическом режиме восстановить его структуру и метод включает группу алгоритмов на основе корреляционного анализа и анализа характеристик изме­ нения слов в кадре для построения модели формата кадра и алгоритм опре­ деления типов медленноменяющихся телеметрических параметров с использо­ ванием метрики неточного сравнения символьного представления временных рядов.

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

Практическая значимость работы заключается в разработке алгоритмов и программ восстановления структуры ГТС, позволяющих сократить время, необходимое на восстановление структуры, в среднем в 4 раза.

Материалы диссертационной работы были использованы при выполнении опытно-конструкторской работы (ОКР), посвященной обработке измеритель­ ной информации РКТ и их оснащения (шифр «Модернизация»), и при вы­ полнении ОКР, посвященной системе комплексного анализа результатов пус­ ков РКТ (шифр «Математика-ПИК»), проводимых в ОАО «Научно-инженерный центр Санкт-Петербургского электротехнического университета» («НИЦ СПб ЭТУ»). Результаты работы внедрены в в/ч 85487 (ОКР «Математика-ПИК») и в в/ч 13991-П (ОКР «Модернизация»).

Работа поддержана программой в рамках конкурсов научных достижений аспирантов СПбГЭТУ «ЛЭТИ» в 2011 году.

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

1) трехэтапная процедура восстановления структуры ГТС;

2) метод экспресс-поиска структуры ГТС;

3) метод последовательного восстановления структуры ГТС, включаю­ щий набор алгоритмов построения модели формата кадра ГТС и алгоритм опре­ деления типов медленноменяющихся телеметрических параметров;

4) графовая модель ГТС и метод комплексного поиска структуры ГТС;

Апробация работы. Основные результаты диссертационной работы до­ кладывались и обсуждались со специалистами ОАО «НИЦ СПб ЭТУ», на ка­ федре математического обеспечения и применения ЭВМ СПбГЭТУ, а также на следующих конференциях:

- 14-я всероссийская конференция «Математические методы распознава­ ния образов» (ММРО-14), Владимирская обл., г. Суздаль, 2009 г.

- двенадцатая национальная конференция по искусственному интеллекту с международным участием (КИИ-2010), г. Тверь, 2010 г.

- XIV международная конференция по мягким вычислениям и измерени­ ям (SCM’2011), Санкт-Петербург, 2011 г.

- научные сессии Национального исследовательского ядерного универси­ тета (НИЯУ) «МИФИ», Москва, 2010, 2011 и 2012 гг.

- научно-технические конференции профессорско-преподавательского состава СПбГЭТУ, Санкт-Петербург, 2010, 2011 и 2012 гг.

Публикации. Материалы диссертации опубликованы в 11 печатных рабо­ тах, из них 2 статьи в рецензируемых журналах, 1 статья в нерецензируемых журналах и 7 докладов в сборниках трудов конференций.

Разработанный автором комплекс анализа структур данных был зареги­ стрирован в реестре программ для ЭВМ (свидетельство № 2011616384).

Структура и объем диссертации. Диссертация состоит из введения, глав, заключения и библиографии. Общий объем диссертации 147 страниц, из них 134 страниц текста, включая 36 рисунков. Библиография включает 99 на­ именований на 13 страницах.

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

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

Под телеметрическим параметром (ТМП) понимается измерительная ин­ формация о поведении физического процесса, поведение которого подлежит измерению или контролю телеметрической системой. В зависимости от ско­ рости изменения во времени ТМП делятся на медленноменяющиеся парамет­ ры (ММП) и быстроменяющиеся параметры (БМП). Первые характеризуются шириной спектра от 0 до 50 Гц, а вторые — от 1 до 100 кГц. Большинство па­ раметров, передаваемых от объекта РКТ, относятся к классу ММП, поэтому в настоящей работе будет рассматриваться только этот класс.

Вводится понятие типа ММП как элемента из конечного алфавита априори заданных типов T. С каждым типом ММП ассоциировано эталонное поведение E, которое задается с помощью одной или нескольких реализаций:

E = {E1,..., Em}, (1) где Ei — реализация, задаваемая временным рядом (ei,..., ei ) и определяющая n один из возможных вариантов поведения, m — количество реализаций.

В работе рассматривается ГТС как ограниченный класс телеметрических информационных потоков со сложной циклической структурой, поступающих с объектов РКТ. Межведомственной комиссией по измерительным средствам был разработан стандарт, регламентирующий особенности формирования ГТС — IRIG Standart 106.

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

Работа объкта РКТ сопровождается переключениями режимов работы, что отражается в изменении схемы коммутации датчиков. Данный процесс изме­ нения называется сменой формата кадра. В качестве примера переключения можно привести отделение ступеней ракеты.

Процесс распаковки ГТС на отдельные параметры называется декоммута­ цией и определяется как оператор:

D : (B, S) P, (2) где B = B1,..., BN — последовательность бит (бинарное представление ГТС), S — структура ГТС, P = {P1,..., PK} — набор типизированных ТМП. Последний является кортежем:

Pi = tP, Pi, (3) i где tP T — тип i-го ТМП, а Pi = (pi,..., pi ) — временной ряд измерений i n ТМП.

Описание структуры S состоит из информации о структуре коммутации датчиков в объекте (формат кадра) и информации о функциональном назначе­ нии каждого из передаваемых параметров (информация о типах параметров).

Под архивом ГТС будем понимать набор исходных ГТС и соответствующих им описаний структур.

Задача восстановления структуры ГТС с неизвестной структурой: необ­ ходимо проанализировать бинарное представление ГТС B и на основании зна­ ний об общих принципах формирования сигнала, которые регламентируются стандартом IRIG Standart 106, а также информации о ранее накопленных ГТС с известными структурами, выявить такую структуру анализируемого ГТС S, чтобы в результате его декоммутации, определенной в формуле (2), был полу­ чен истинный набор ТМП P.

Основные существующие подходы к восстановлению структуры ГТС: гра­ фический подход на базе когнитивной графики и подход на основе анализа кор­ реляционных функций и характеристик изменения значений информационных слов в кадре.

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

В рамках второго подхода осуществляется обработка B, сведенного в по­ следовательность информационных слов Xi определенной разрядности Lc. За­ дача определения длины информационного слова и длины кадра решается пу­ тем оценки экспертом периодов между пиками автокорреляционной функции (АКФ). К числу недостатков относятся: большая часть операций выполняет­ ся экспертом, в соответствии с проведенными автором исследованиями только на основании анализа максимальных значений АКФ нельзя выполнить автома­ тическое определение длины кадра и длины слова. Для поиска суб- и супер­ коммутаций производится анализ изменения слов в последовательности кад­ ров, представленных в виде матрицы MT из Lgts строк (длина ГТС в кадрах) с одинаковым количеством столбцов в размере Lf информационных слов (длина кадра в словах). Предполагается оценивание экспертом математического ожи­ дания изменения предшествующих и последующих по времени элементов мат­ рицы MT: большие величины указывают на наличие субкоммутации. К числу недостатков относятся: большой объем операций, выполняемых непосредствен­ но экспертом, в соответствии с проведенными автором исследованиями крайне высокая чувствительность в случае длин слов большой разрядности, наличие сбойных участков может сильно исказить вычисляемую статистику, что приво­ дит к ложным выявлением коммутаций.

Указанные подходы не осуществляют определение типов ТМП, а следова­ тельно, они не решают задачу восстановления структуры ГТС в полном объеме.

Во второй главе описывается предлагаемая трехэтапная процедура восста­ новления структуры ГТС c неизвестной структурой и вводятся предлагаемые модели. На рисунке 1 представлена схема данной процедуры, которая состоит из трех этапов:

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

Рисунок 1. Схема трехэтапной процедуры восстановления структуры ГТС.

2) Полный анализ. Последовательно применяются алгоритмы для опреде­ ления всех элементов модели формата кадра и определяются типы ММП (ме­ тод последовательного восстановления).

3) Уточнение. Осуществляется поиск в архиве ГТС схожих сигналов с учетом полученной структуры (метод комплексного поиска). Эксперт проверяет структуры найденных ГТС и уточняет изначально полученную структуру.

В основе методов поиска в архиве ГТС лежит тот факт, что в ракетно­ космической отрасли структуры ГТС, полученные от одного и того же объекта РКТ, одинаковы или имеют минимальные различия. Как следствие, сходство ГТС свидетельствует о сходстве их внутренних структур.

С целью формализации описания формата кадра как схемы коммутации датчиков в ГТС вводится модель формата кадра:

F = Lw, Lf, S ub, S up, (4) где Lw — длина информационного слова в битах, Lf — длина кадра в словах, S ub — множество субкоммутаций, S up — множество суперкоммутаций.

Множество суперкоммутаций есть множество пар S up = (i, f ), где 0...k i — индекс слова в кадре, f — кратность суперкоммутации, k — количество суперкоммутаций в кадре. Множество субкоммутаций есть множество пар — индекс слова в кадре и глубина субкоммутации S ub = ( j, d), где j — индекс 0...m слова в кадре, d — глубина субкоммутации, m — количество субкоммутаций в кадре.

Для того, чтобы учитывать при сравнении ГТС как информацию о пове­ дении ТМП, так и структуру ГТС, была разработана графовая модель ГТС.

Модель основана на атрибутированном графе отношений (attributed relational graph). Пусть MV, ME — это атрибуты вершин и ребер, соответственно, каждый атрибут имеет вид (, ), где — тип атрибута, = (1,..., n) — вектор ха­ рактеристик, ассоциированный с . Тогда атрибутированный граф отношений над множеством атрибутов M = MV ME есть:

G = V, E, µ, e, (5) где V — множество вершин, E V V — множество ребер, µ : V MV — функция назначения атрибутов вершинам, e : E ME — функция назначения атрибутов ребрам.

В случае описания ГТС атрибутированный граф — это схема соединений датчиков и коммутаторов в объекте РКТ, где узлами являются вершины, описы­ вающие субкоммутаторы, а конечные узлы — это параметры, измеряемые дат­ чиками. Выделяется три типа атрибутов вершин: TV = { f p, sp, com}, где f p — тип атрибута для БМП, sp — тип атрибута для ММП, com — тип атрибута ком­ мутатора.

Атрибутом для коммутаторов является кортеж имен вершин – потомков:

Pcom = nv,..., nv , где nv,..., nv — имена вершин v1,... vm, связанных с ком­ 1 m 1 m мутатором c: (c, vm) E, i = 1,... m. В зависимости от того, относится ли ТМП к классу БМП или ММП, атрибуты вершин задаются в спектральном или сим­ вольном представлении как Pf p = f1,..., fl и Psp = s1,..., sw соответствен­ но, где fi — величина i-го коэффициента преобразования Фурье, l — количество рассматриваемых коэффициентов, si — i-й элемент символьного представления ММП, w — длина символьного представления.

Множество атрибутов ребер определяется как TE = {l, r}, где l — атрибут ребер «непосредственно связан», r — атрибут ребер «элемент заменяется на», который используется для указания смены формата кадра. Указанные атрибуты ребер не имеют векторов характеристик.

Графовая модель ГТС есть кортеж:

G = V, E, V, E, Lw, (6) где V — датчики и коммутаторы, E — линии связей датчиков и коммутаторов, V — функция назначения вершинам соответствующих атрибутов (com, Pcom), ( f p, Pf p), (sp, Psp), V — функция назначения ребрам атрибутов {l, r}, Lw — дли­ на информационного слова.

В третьей главе приводится описание предлагаемых методов восстанов­ ления структуры ГТС.

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

Для текстов на естественном языке известен закон Ципфа – Мандельброта:

«произведение ранга некоторого слова и частоты его встречаемости в тексте является величиной постоянной, имеющей примерно одинаковое значение для любого слова из словаря рассматриваемого текста и характерной для данного языка». Дальнейшие исследования показали, что закону Ципфа – Мандельброта удовлетворяют не только слова из текстов на естественном языке, но и прак­ тически все объекты современного информационного пространства. Исходя из этого, в качестве вектора характеристик предлагается использовать коэффици­ енты C, , d аппроксимирующей функции частотно-рангового распределения значений слов:

(r) = C · r-·exp(d·r), (7) где (r) — относительная частота информационного значения слова с рангом r, — константа, определяемая свойствами анализируемого ГТС, C — константа, определяемая объемом выборки, d — параметр увеличения коэффициента ча­ стотно-рангового соотношения. Процесс подбора параметров C, , d является задачей оптимизации с целевой функцией:

N ( fr - (r))2 min, (8) C,,d r=где fr — частота встречаемости значения с рангом r.

Применение предложенного метода позволяет в сокращенные сроки полу­ чить приближенный набор потенциальных структур ГТС. Потенциальный недо­ статок метода связан с большим размером словаря, который в худшем случае w составляет 2L слов.

Метод последовательного восстановления направлен на автоматическое получение формата кадра за счет анализа бинарного представления ГТС B с использованием знаний о принципах формирования ГТС и осуществляет после­ дующее определение типов ТМП. В рамках метода выделяются два подэтапа:

восстановление формата кадра и определение типов ММП. Процесс восстанов­ ления формата кадра состоит из последовательного применения разработанных алгоритмов, осуществляющих определение одного из элементов модели фор­ мата кадра F в формуле (4).

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

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

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

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

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

Алгоритм построения символьного представления временного ряда явля­ ется модификацией существующего алгоритма SAX (Symbolic Aggregate appro­ Ximation). В алгоритме для исходного временного ряда C = (c1,..., cN) с целью сокращения размерности строится кусочно-константная аппроксимация (ККА) C = (c1,..., cW), где N — длина исходного временного ряда, а W — количе­ ство сегментов аппроксимации. Далее, осуществляется нормализация к виду:

ci [-1, 1], i = 1,..., W. Для уменьшения влияния выбросов осуществляется предварительная очистка и вычисление максимального (минимального) значе­ ние как медианы среди максимальных (минимальных) значений. Перевод из ККА в символьное представление производится на основании уровней, кото­ рые задаются как отсортированный список чисел B = (1,..., K-1), распре­ деленных в отличие от оригинального алгоритма SAX равномерно на множе­ стве [-1, 1], где K — размер алфавита. Каждому отсчету ci назначается бук­ ва алфавита: aj j-1 < ci j. В результате получается строка символов S = (s1,..., sW), где si {a0,..., aK}.

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

k d(S, S ) = min C(mi), (9) 1 (e1,...,ek)Y(S,S ) 1 i=где Y(S, S ) — множество путей редактирования для трансформации строки S 1 2 в S, и C(mi) — функция стоимости операции mi. Цены операций зависят как от вида операции, так и от участвующих в ней символов. В работе задачу для произвольных весов решает алгоритм Вагнера – Фишера.

Метод комплексного поиска осуществляет поиск ближайших ГТС в ар­ хиве с учетом предварительно определенной структуры и позволяет эксперту уточнить изначально полученную структуру. Сравнение ГТС осуществляется в рамках введенной ранее графовой модели ГТС. Для нахождения ближайших ГТС используется расстояние редактирования на графах (graph edit distance).

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

Ключевая идея расстояния редактирования на графах заключается в опре­ делении набора операций редактирования графов, которые могут быть приме­ нены, чтобы привести два графа к единому виду. Набор операций редактирова­ ния определен как: вставка, удаление и изменение, как узлов, так и ребер. Для каждой операции вводится стоимость, зависящая как от вида операции, так и от участвующих в ней элементов. Пусть G1 и G2 — это графовые модели ГТС, тогда расстояние редактирования между ними:

k d(G1, G2) = min H(mi), (10) (e1,...,ek)Y(G1,G2) i=где Y(G1, G2) — множество путей редактирования для трансформации G1 в G2, и H(mi) — функция стоимости операции mi.

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

Автором предлагается использовать особенность графовой модели ГТС, заклю­ чающуюся в «слоистой» структуре графа (один слой — это один формат кадра) для построения эффективного алгоритма сравнения. В предлагаемом алгорит­ ме происходит попарное сравнение всех форматов кадров, являющихся дере­ вьями, одной графовой модели с другой. После этого решается задача о на­ значении с целью минимизации суммы расстояний и идет подсчет итогового расстояния редактирования для оптимального назначения, включающего сто­ имости ребер для смен формата кадров. Сложность предлагаемого алгоритма O max(N1, N2)2 · Lf, где N1, N2 — количество смен кадров в первой графовой модели и во второй, соответственно.

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

Исследования проводились с использованием разработанного программно­ го комплекса [3], реализованном на языке высокого уровня JavaTM. Все замеры времени исполнения проводились на персональном компьютере с центральным R процессором IntelCoreTM i3-2310M с тактовой частотой 2.10 ГГц и объемом оперативной памяти 4096 Мбайт.

Для проведения экспериментальных исследований был выбран набор изме­ рений реальных параметров (свыше 10000 временных рядов), количество сбой­ ных участков не более 10%. Указанный набор содержал дискретные параметры (DP), медленноменяющиеся функциональные параметры, представленные ря­ дом целых чисел (SVP), быстро меняющиеся функциональные параметров, представленные рядом целых чисел (F SP), параметры, представленные числа­ ми с плавающей точкой (F PP), и прочие (OP). Обозначим данный набор как U = {U1,..., UN : Ui = (ui,..., ui )}, где ui — это j-ое измерение i-го времен­ m 1 j ного ряда, а N — это количество тестовых параметров. При этом для каждого временного ряда U определен T — тип передаваемого параметра: f : U T.

На основании набора U и генерации случайных структур, которые отвечают правилам формирования ГТС, был создан генератор модельных данных. В ка­ честве стандартных настроек генератора использовались типовые для РКТ ха­ рактеристики: Lw {8, 16}, Lf [256, 384], |S ub| = 20%, |S up| = 30%, DP = 5%, SVP = 55%, F VP = 20%, F PP = 10%, OP = 10%.

Время работы алгоритмов представлено в таблицах 1 и 2. Средний про­ цент правильно определенных элементов формата кадра представлен в табли­ це 3. Данные, полученные для предлагаемых алгоритмов, являются средними показателями по 50 экспериментов.

Сравнение предлагаемого алгоритма определения типов ММП проводи­ лось с алгоритмом SAX и алгоритмом, построенным на базе быстрого преоб­ Таблица Время работы в минутах алгоритмов определения длины кадра и слова.

Размер ГТС, Мбайт 50 100 200 4Существующий алгоритм (длина слова и кадра) 34 35,1 37,6 41,Предлагаемый алгоритм определения длины кадра 0,2 0,4 0,8 1,Предлагаемый алгоритм определения длины слова 0,3 0,7 1,3 2,Суммарное время определения длины кадра и слова 0,5 1,1 2,1 4,Таблица Время работы в минутах алгоритмов поиска суб- и суперкоммутаций.

Длина кадра, информационные слова 128 256 512 1024 20Существующий алгоритм поиска 9,66 18,20 35,26 69,40 137,субкоммутаций Существующий алгоритм поиска су­ 26,67 53,33 106,67 213,33 426,перкоммутаций Предлагаемый алгоритм определения 0,75 1,67 4,21 8,56 17,субкоммутаций Предлагаемый алгоритм определение 1,15 2,35 4,89 9,87 19,суперкоммутаций Таблица Средний процент правильно определенных элементов модели формата кадра.

Элемент модели Lf Lw S ub S up Типовые 98 80 91,3 90,|S ub| > 60% 92 40 90,2 92,|S up| > 60% 98 78 93,0 89,DP = 5%, SVP = 35%, F VP = 40%, F PP = 10%, 92 42 88,1 85,OP = 10% DP = 5%, SVP = 35%, F VP = 10%, F PP = 40%, 80 20 72,3 71,OP = 10% разования Фурье (БПФ) и меры Жаккара. Были выбраны 4 типа ММП, каждый представлен 20 реализациями: 16 использовалась для формирования эталона E, 4 для тестирования. В общей сложности с различными комбинациями пара­ метров было проведено: 6 · C20 экспериментов и получен средний процент правильно определенных типов: БПФ = 85,5 %, SAX = 93,75 %, Предлагаемый = 96,4%.

В таблице 4 представлены результаты экспериментальных исследований метода экспресс-поиска (МЭП) и метода комплексного поиска (МКП) структу­ ры ГТС. Строки соответствуют пяти экспериментам, проведенным с разными настройками генератора. Для каждого эксперимента был сгенерирован архив в 100 ГТС. Для экспресс-поиска приведен средний процент для 100 тестовых ГТС, для которых среди 10 найденных хотя бы один обладал правильной струк­ Таблица Процент корректных ближайших ГТС, определенных методами поиска.

Метод МЭП МКП Стандартные 80 |S ub| > 60% 82 |S up| > 60% 81 DP = 5%, SVP = 35%, F VP = 40%, F PP = 10%, OP = 10% 78 DP = 5%, SVP = 35%, F VP = 10%, F PP = 40%, OP = 10% 76 турой. Для комплексного поиска рассматривался только первый ближайший.

В рамках внедрения предлагаемые методы восстановления структуры ГТС проходили испытание на реальных данных. Общее число ГТС в архиве — 83, представлено 19 различных структур. Количество ГТС, для которых произво­ дилось восстановление структуры, составляло 60.

Для восстановления была применена прелагаемая процедура восстанов­ ления. После проведения этапа экспресс-анализа были подобраны структуры для 19 ГТС. Общее время этапа составило 1 час 12 минут. Применение мето­ да последовательного восстановления для оставшихся ГТС потребовало около 13 часов. В результате применения комплексного поиска для 28 ГТС были най­ дены ГТС со схожими или точно совпадающими структурами, что позволило уточнить для 16 ГТС изначальную структуру. Общее время, которое потребо­ валось на поиск и уточнение, составило 6 часов. Общее время анализа для 60 ГТС составил 20 часов. По оценкам экспертов на анализ аналогичного числа ГТС без использования предлагаемых автором методов потребовалось бы свыше 90 часов работы в идеализированных условиях.

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

Основные результаты работы 1) Разработана трехэтапная процедура восстановления структуры ГТС с неизвестной структурой, позволяющая для ускорения восстановления и уточне­ ния структуры ГТС задействовать информацию о ранее накопленных группо­ вых телеметрических сигналах с известной структурой. При эксперименталь­ ных исследованиях на реальных данных процедура позволила ускорить восста­ новление структуры ГТС в 4 раза.

2) Разработан метод экспресс-поиска структуры ГТС c неизвестной струк­ турой на базе аппроксимации распределения информационных слов группово­ го телеметрического сигнала. Метод позволяет для анализируемого ГТС при минимальном количестве априорной информации об его структуре определить набор потенциальных структур, представленных среди ранее накопленных ГТС с известными структурами.

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

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

4) На базе атрибутированного графа отношений разработана графовая мо­ дель ГТС, позволяющая учитывать как структуру, так и поведение составляю­ щих его параметров. Разработан метод комплексного поиска структуры ГТС с неизвестной структурой на базе сравнения графовых моделей ГТС с использо­ ванием редакционного расстояния. В соответствии с экспериментальными ис­ следованиями метод позволяет увеличить точность восстановления структуры в среднем до 90%.

5) Разработан программный комплекс, реализующий трехэтапную проце­ дуру восстановления структуры ГТС. Данный комплекс лег в основу внедрен­ ных программных комплексов.

Список публикаций В изданиях рекомендованных ВАК РФ:

1. Геппенер В.В., Горбачева И.В., Жукова Н.А., Соколов И.С. Идентификация телеметрических параметров с использованием нейронных сетей // Нейрокомпьютеры: разработка, применение. – 2009. – Т. 11. – С. 39–44.

2. Балтрашевич В.Э., Жукова Н.А., Соколов И.С. Графовая модель группового телеметрического сигнала со сменой кадра // Известия СПбГЭТУ “ЛЭТИ”. – 2010. – № 10. – С. 12–17.

Свидетельства о государственной регистрации программ для ЭВМ:

3. Свидетельство о государственной регистрации программы для ЭВМ № 2011616384. Соколов И.С. «Комплекс анализа структур данных (КАСД)».

Статьи и материалы конференций:

4. Жукова Н.А., Соколов И.С. Метод восстановления структуры группо­ вого телеметрического сигнала на основе графовой модели // Труды СПИИРАН. – 2010. – № 13. – С. 45–66.

5. Балтрашевич В.Э., Васильев А.В., Жукова Н.А., Соколов И.С. Ме­ тод идентификации групповых телеметрических сигналов на основе частотно рангового распределения // 14-я всероссийская конф. мат. ме­ тоды распознавания образов (ММРО-14): Сб. докл. – М.: МАКС Пресс, 2009. – С. 305–308.

6. Балтрашевич В.Э., Витол А.Д., Жукова Н.А., Соколов И.С. Интеллектуальный подход к анализу структуры и семантики ГТС // Труды 12-й нац.

конф. по искусственному интеллекту с междунар. участием (КИИ-2010).

– М.: Физматлит, 2010. – Т. 2. – С. 1-4.

7. Соколов И.C., Чех А.И. Метод формирования семантического описа­ ния структурированного потока измерений // Сб. докл. XIV междунар.

конф. по мягким вычислениям и измерениям (SCM‘2011). – СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2011. – Т. 2. – С. 25-27.

8. Балтрашевич В.Э., Соколов И.С. Применение графовой модели для представления структуры группового телеметрического сигнала // 62-й на­ уч.-техн. конф. проф.-преп. состава университета: Сб. докл. студентов, аспирантов и молодых ученых. – СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2010.

– С. 98-103.

9. Балтрашевич В.Э., Жукова Н.А., Соколов И.С. Определение структу­ ры циклического информационного потока применительно к группово­ му телеметрическому сигналу // Науч. сессия НИЯУ МИФИ-2010: Аннот.

докл. – М.: МИФИ, 2010. – Т. 3. – С. 75–76.

10. Соколов И.С. Метод построения графовой модели группового телеметри­ ческого сигнала // Науч. сессия НИЯУ МИФИ-2011: Аннот. докл. – М.:

МИФИ, 2011. – Т. 3. – С. 77-78.

11. Соколов И.С. Метод неточного сравнения медленноменяющихся телеметрических параметров с использованием символьного представления // На­ уч. сессия НИЯУ МИФИ-2012: Аннот. докл. – М.: МИФИ, 2012. – Т. 3. – С. 89-90.







© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.