HEURISTIC APPROACH TO OPTIMIZING THE STRUCTURE OF TELEMETRIC DATA FRAMES FOR THE TASK OF COMPRESSION
HEURISTIC APPROACH TO OPTIMIZING THE STRUCTURE OF TELEMETRIC DATA FRAMES FOR THE TASK OF COMPRESSION
Abstract
The article considers heuristic approach to optimization of the structure of telemetric data for the task of compression, on the basis of which an algorithm of reversible ordering of the structure composed of their difference-bit frame representation is developed, as well as ways to evaluate their homogeneity. It is shown that the developed solutions allow to significantly increase the efficiency of compression of frames, data in which have mainly non-stationary characteristics. It is justified that the proposed solutions can be used as part of the system of adaptive compression, which would be based not only on the selection of the optimal data compression algorithm for current frames, but also on the choice of methods of evaluation of frames' homogeneity.
1. Введение
После спада в середине-конце XX века, связанного с обоснованием принципиальной невозможности преодоления верхней теоретической границы коэффициента сжатия для существовавших на тот момент способов представления телеметрических данных, к данной проблеме вновь обратилось пристальное внимание научного сообщества, что подтверждают исследования как отечественных [1], [2], так и зарубежных [3], [4] авторов.
Такой интерес в первую очередь связан со сложившимися тенденциями в современной промышленности, аэрокосмической отрасли, медицине и т.д., но к ним оказались совершенно не готовы существующие подходы к сжатию телеметрических данных, большинство из которых основаны на рассмотрении множества источников независимо друг от друга, с учетом только линейной структуры каждого из них в отдельности [5], [6]. На основе такого подхода разработаны практически все современные алгоритмы сжатия [7], [8], но, несмотря на их многообразие, наибольшее применение и по сей день находит подход, при котором используется дельта-кодирование с последующим представлением данных с использованием кодов переменной длины.
Однако, озвученный выше подход, как и любые классические алгоритмы сжатия не позволяют в полной мере учитывать особенности телеметрических данных, поступающих в один и тот же момент времени от разных источников, для которых характерно наличие как одномерных, так и двумерных корреляционных связей [9], [10]. Учет таких корреляций стал возможен с использованием другого подхода [11], в основу которого легло представление данных единой информационной единицей путем объединения в кадры с определенной структурой. Такой подход показал свое принципиальное превосходство над классическими алгоритмами сжатия [12] с точки зрения эффективности, которая связана с тем, насколько сильно структура данных соответствует некоторой «идеальной» структуре [13], на которой алгоритмы показывают предельно возможный коэффициент сжатия.
Исходя из вышесказанного, становится очевидной необходимость в разработке подходов к преобразованию структуры телеметрических данных и их кадров, которые позволят учитывать особенности алгоритмов сжатия и оптимизировать данные таким образом, чтобы алгоритмы показывали на них максимальную эффективность.
2. Способы оценки однородности кадров данных
Потоки телеметрических данных на протяжении длительных временных интервалов обладают свойством стационарности [9], исходя из чего предлагается организовывать множество отсчетов в виде кадров, содержащих результат дельта-кодирования для каждого отсчета, представленный в битовом виде. Пример такого представления приведен на рис. 1, где приняты следующие обозначения: ΔДi – результат дельта-кодирования пары отсчетов, полученных от датчика Дi, n – число источников данных разрядности m, ΔДi,j – представление отсчета ΔДi в виде последовательности бит.
Рисунок 1 - Формы представления телеметрических данных
Рисунок 2 - Примеры выделения различных структур в кадре
Примечание: а – областей, б – сильно связанных групп, в – слабо связанных групп
В свою очередь, их свойства могут выступать как мера однородности данных и, следовательно, отражать то, насколько эффективно может быть сжать кадр. Так, чем больше в нем определяется групп или областей, тем менее однородна структура, а следовательно, и ниже потенциальный коэффициент сжатия.
Важно заметить, что данные характеристики могут иметь не только количественное, но и качественное значение, так, при большом числе включенных элементов и/или сложной геометрии группы будет образовано множество групп меньшего размера, что также окажет негативный эффект на дальнейшую эффективность сжатия. Аналогичная особенность характерна и для областей, так, чем больше областей небольшого размера, тем хуже кадр поддается сжатию.
Таким образом оценивать свойства кадров с позиции последующей эффективности их сжатия предлагается при помощи коэффициентов однородности и пропорциональности.
С точки зрения решения задачи увеличения эффективности сжатия, целью любого преобразования над кадром является повышение его однородности, что возможно сделать за счет сокращения количества обнаруживаемых в нем групп или областей, т.е. устанавливается обратная связь между двумя этими характеристиками и тогда оценка, выраженная коэффициентом однородности групп (kодн.гр) или областей (kодн.обл), будет иметь следующий вид: kодн.гр = 1 / Nгр и kодн.обл = 1 / Nобл, где Nгр и Nобл – число обнаруженных в кадре групп или областей соответственно.
Описанные выше характеристики оценивают кадр с количественной позиции, качественно же его оценить можно с использованием отношения числа областей к группам, введя коэффициент пропорциональности: kпр = Nгр / Nобл.
Рисунок 3 - Представление кадра в виде биграфа для элементов, принимающих значение единицы
3. Алгоритм структурного преобразования
В общем виде рассматриваемое структурное преобразование может быть описано с помощью следующей последовательности шагов:
1. Вычисляется характеристика для исходной структуры кадра, оценивающая его однородность;
2. Выполняется последовательная попарная перестановка строк кадра от первой к последней, на каждом шаге которой вычисляется характеризующая кадр характеристика. Если ее значение показывает увеличение однородности кадра, то перестановка прерывается и запоминается тип операции и номер перемещенной строки;
3. Фиксируется структура кадра с измененным порядком строк;
4. Происходит последовательная попарная перестановка столбцов кадра от первого к последнему, на каждом шаге которой вычисляется характеризующая кадр характеристика. Если ее значение показывает увеличение однородности кадра, то перестановка прерывается и запоминается тип операции и номер перемещенной строки;
5. Фиксируется структура кадра с измененным порядком столбцов;
6. Сравнивается исходная структура кадра с парой измененных, если они эквивалентны, то преобразование завершается, иначе выбирается та измененная структура, которая показала большую однородность и происходит переход к следующему шагу;
7. Для структур кадра с измененным порядком срок и столбцов вычисляется оценка, отражающая эффективность их преобразования;
8. Полученные оценки сравниваются между собой, и исходной становится та структура кадра, которая обладает наибольшей однородностью, после чего происходит переход к п. 1.
В качестве способов оценки эффективности преобразования, предлагается использовать следующие:
- отношение коэффициентов сжатия для исходного (kcж.исх) и преобразованного (kсж.пр) состояния кадра данных;
- отношение предложенных в работе характеристик оценки однородности для исходного и преобразованного представления кадра данных.
Для описания результатов работы алгоритма предлагается к кадру добавлять заголовок (Hф.пр), в котором проведенные манипуляции кодируются двоичным кодом следующим образом:
где Fэ.пр – флаг, указывающий на эффективность преобразования (в случае его неэффективности, происходит только его передача); Nпр – количество зафиксированных преобразований; Tстр/ст – флаг, указывающий на то, производилось преобразование над строкой или столбцом; Nстр и Nст – битовые поля, указывающее на номер перемещенной строки или столбца соответственно, размер которых (Lстр и Lст) рассчитывается согласно следующим формулам: Lстр = 1 + ⌊ log2(n − 1)⌋ и Lст = 1 + ⌊ log2(m − 1)⌋.
Важно отметить, что операции преобразования полагаются заранее известным и нет необходимости в их передачи.
4. Исследование предложенных решений
Тестирование разработанного алгоритма и способов оценки однородности кадров проводилось с использованием данных телемеханики, полученных от ряда объектов энергетики. В качестве тестовых использовались пять наиболее характерных наборов данных (НД), сформированных из отсчетов, полученных как в штатном режиме работы объекта (стационарные наборы НД1, НД3 и НД5), так и в режиме перевода энергосети из одного состояния в другое (нестационарные наборы НД2 и НД4). Следует отметить, что объем наборов варьировался от 11 до 19 тысяч кадров.
Для оценки эффективности предложенного в работе подхода, использовался универсальный алгоритм сжатия (АС), основанный на представлении кадра как таблицы истинности логической функции нескольких переменных (LC) [14].
Результат работы алгоритма сжатия над данными, для которых не применялось предварительное преобразование, приведен в табл. 1, при этом оценивались средний коэффициент (СКС) и среднее время (СВС) сжатия для каждого набора.
Таблица 1 - Результаты исследования эффективности алгоритмов сжатия
АС | Параметр | НД | ||||
НД1 | НД2 | НД3 | НД4 | НД5 | ||
LC | СКС, ед | 3,2055 | 1,7995 | 2,7288 | 2,1577 | 3,9509 |
СВС, мс | 0,3241 | 1,3058 | 1,3021 | 1,4457 | 1,1031 |
Представленный результат показывает, что рассмотренный алгоритм на нестационарных НД дает относительно низкий коэффициент сжатия, и одновременно с этим затрачивает значительное количество времени на сжатие по сравнению с результатами, полученными для стационарных наборов. Такое его поведение означает малую эффективность в случае работы с данными нестационарного и смешанного типа, а также принципиальную непригодность при условии работы в «жестком» реальном времени.
С целью определения эффективности алгоритма структурного преобразования (АСП) и способов оценки однородности структуры кадров было проведено исследование, где их комбинации применялись над каждым НД и при этом фиксировались следующие параметры:
- средний коэффициент и среднее время сжатия одного кадра для каждого НД с применением предварительного преобразования;
- процент прироста среднего коэффициента сжатия кадров, для которых преобразование оказалось эффективным (СКСПК);
- процент кадров от всего их числа в наборе, для которых преобразование оказалось эффективным (ЧПК).
Результаты проведенного исследования приведены в табл. 2, при этом важно отметить, что:
- для вычисления характеристики qп.р построение вершин шло только для элементов, принимающих значение единицы;
- производился поиск только сильно связанных групп.
Таблица 2 - Результаты исследования эффективности алгоритма структурного преобразования
АС | Хар-ка | Параметр | НД | ||||
НД1 | НД2 | НД3 | НД4 | НД5 | |||
LC | kодн.гр | СКС, ед | 3,2063 | 1,8499 | 2,7864 | 2,2160 | 3,9585 |
СВС, мс | 1,6925 | 7,6950 | 2,9986 | 9,0810 | 3,5006 | ||
СКСПК, % | 11,2600 | 7,1909 | 11,5487 | 6,9759 | 11,0058 | ||
ЧПК, % | 18,1540 | 47,1807 | 29,4790 | 46,9453 | 16,6145 | ||
kодн.обл | СКС, ед | 3,3314 | 1,8774 | 2,8421 | 2,2569 | 4,0503 | |
СВС, мс | 25,0475 | 146,3014 | 45,5110 | 145,4572 | 42,1941 | ||
СКСПК, % | 14,1813 | 8,3560 | 11,6385 | 8,1798 | 12,0895 | ||
ЧПК, % | 42,2590 | 57,4089 | 45,7672 | 61,2022 | 35,9284 | ||
kпр | СКС, ед | 3,1960 | 1,8449 | 2,7589 | 2,2041 | 3,9500 | |
СВС, мс | 21,6190 | 145,9080 | 33,2227 | 158,3708 | 36,0025 | ||
СКСПК, % | 9,4751 | 6,6896 | 9,2296 | 6,1637 | 10,1142 | ||
ЧПК, % | 17,8185 | 46,5338 | 25,4682 | 44,3886 | 15,7477 | ||
qп.р | СКС, ед | 3,1779 | 1,8630 | 2,7576 | 2,2231 | 3,9287 | |
СВС, мс | 1,2045 | 17,0180 | 2,3810 | 9,3843 | 2,5900 | ||
СКСПК, % | 6,9795 | 6,6397 | 5,1087 | 6,3862 | 5,4136 | ||
ЧПК, % | 14,7186 | 61,2379 | 44,4507 | 56,3323 | 18,6665 |
Полученные в ходе исследований результаты показывают, что в среднем удается достичь не особо значительного прироста коэффициента сжатия, при этом лучший результат показал учет коэффициента однородности областей.
Важно заметить, что несмотря на невысокие показатели эффективности в среднем для НД, наблюдается значительное увеличение коэффициента сжатия отдельных кадров, а также прослеживается тенденция к увеличению количества удачных преобразований на тех наборах, стационарные свойства в которых выражены наиболее слабо.
5. Заключение
Несмотря на в среднем невысокую эффективность предложенного в работе подхода к оптимизации структуры кадров телеметрических данных, его применение можно найти в составе системы адаптивного сжатия, в основу которой ляжет не только выбор оптимального для текущих кадров данных алгоритма сжатия, но и выбор способов оценки однородности кадров.
Помимо этого, следует отметить, что основным преимуществом предложенного подхода является его эффективность для данных, обладающих нестационарными свойствами, уменьшение избыточности в которых является одной из важнейших задач в области неискажающего сжатия, что также может стать одним из дальнейших путей для проведения исследований, заключающегося в определении зависимости качества преобразования от степени стационарности кадров.