HEURISTIC APPROACH TO OPTIMIZING THE STRUCTURE OF TELEMETRIC DATA FRAMES FOR THE TASK OF COMPRESSION

После спада в середине-конце XX века, связанного с обоснованием принципиальной невозможности преодоления верхней теоретической границы коэффициента сжатия для существовавших на тот момент способов представления телеметрических данных, к данной проблеме вновь обратилось пристальное внимание научного сообщества, что подтверждают исследования как отечественных [1], [2], так и зарубежных [3], [4] авторов.

Такой интерес в первую очередь связан со сложившимися тенденциями в современной промышленности, аэрокосмической отрасли, медицине и т.д., но к ним оказались совершенно не готовы существующие подходы к сжатию телеметрических данных, большинство из которых основаны на рассмотрении множества источников независимо друг от друга, с учетом только линейной структуры каждого из них в отдельности [5], [6]. На основе такого подхода разработаны практически все современные алгоритмы сжатия [7], [8], но, несмотря на их многообразие, наибольшее применение и по сей день находит подход, при котором используется дельта-кодирование с последующим представлением данных с использованием кодов переменной длины.

Однако, озвученный выше подход, как и любые классические алгоритмы сжатия не позволяют в полной мере учитывать особенности телеметрических данных, поступающих в один и тот же момент времени от разных источников, для которых характерно наличие как одномерных, так и двумерных корреляционных связей [9], [10]. Учет таких корреляций стал возможен с использованием другого подхода [11], в основу которого легло представление данных единой информационной единицей путем объединения в кадры с определенной структурой. Такой подход показал свое принципиальное превосходство над классическими алгоритмами сжатия [12] с точки зрения эффективности, которая связана с тем, насколько сильно структура данных соответствует некоторой «идеальной» структуре [13], на которой алгоритмы показывают предельно возможный коэффициент сжатия.

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

Потоки телеметрических данных на протяжении длительных временных интервалов обладают свойством стационарности [9], исходя из чего предлагается организовывать множество отсчетов в виде кадров, содержащих результат дельта-кодирования для каждого отсчета, представленный в битовом виде. Пример такого представления приведен на рис. 1, где приняты следующие обозначения: ΔДi – результат дельта-кодирования пары отсчетов, полученных от датчика Дi, n – число источников данных разрядности m, ΔДi,j – представление отсчета ΔДi в виде последовательности бит.

Рисунок 1 - Формы представления телеметрических данных

DOI:10.23670/IRJ.2022.122.29.1

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

Рисунок 2 - Примеры выделения различных структур в кадре

Примечание: а – областей, б – сильно связанных групп, в – слабо связанных групп

DOI:10.23670/IRJ.2022.122.29.2

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

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

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

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

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

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

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

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

DOI:10.23670/IRJ.2022.122.29.3

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

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

1. Вычисляется характеристика для исходной структуры кадра, оценивающая его однородность;

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

3. Фиксируется структура кадра с измененным порядком строк;

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

5. Фиксируется структура кадра с измененным порядком столбцов;

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

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

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

В качестве способов оценки эффективности преобразования, предлагается использовать следующие:

- отношение коэффициентов сжатия для исходного (kcж.исх) и преобразованного (kсж.пр) состояния кадра данных;

- отношение предложенных в работе характеристик оценки однородности для исходного и преобразованного представления кадра данных.

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

(1)

где Fэ.пр – флаг, указывающий на эффективность преобразования (в случае его неэффективности, происходит только его передача); Nпр – количество зафиксированных преобразований; Tстр/ст – флаг, указывающий на то, производилось преобразование над строкой или столбцом; Nстр и Nст – битовые поля, указывающее на номер перемещенной строки или столбца соответственно, размер которых (Lстр и Lст) рассчитывается согласно следующим формулам: Lстр = 1 + ⌊ log2(n − 1)⌋ и Lст = 1 + ⌊ log2(m − 1)⌋.

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

Тестирование разработанного алгоритма и способов оценки однородности кадров проводилось с использованием данных телемеханики, полученных от ряда объектов энергетики. В качестве тестовых использовались пять наиболее характерных наборов данных (НД), сформированных из отсчетов, полученных как в штатном режиме работы объекта (стационарные наборы НД1, НД3 и НД5), так и в режиме перевода энергосети из одного состояния в другое (нестационарные наборы НД2 и НД4). Следует отметить, что объем наборов варьировался от 11 до 19 тысяч кадров.

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

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

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

С целью определения эффективности алгоритма структурного преобразования (АСП) и способов оценки однородности структуры кадров было проведено исследование, где их комбинации применялись над каждым НД и при этом фиксировались следующие параметры:

- средний коэффициент и среднее время сжатия одного кадра для каждого НД с применением предварительного преобразования;

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

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

Результаты проведенного исследования приведены в табл. 2, при этом важно отметить, что:

- для вычисления характеристики qп.р построение вершин шло только для элементов, принимающих значение единицы;

- производился поиск только сильно связанных групп.

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

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

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

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