ESA has developed an algorithm for the compression and decompression of time series data generated for status monitoring. It was originally developed for communicating housekeeping telemetry data from spacecraft down to earth, observing limitations in resources and bandwidth. Interesting applications on earth are asset monitoring in remote areas, e.g. in the oil and gas industries, and monitoring and control of mobile devices, e.g. UAV. The method is fast enough to be used in RT-data streams, is easily configurable and robust to data losses. The Agency is looking for partners who would be interested in licensing and implementing this design.
The patent concerns an efficient, packet based, robust software algorithm designed for real-time compression of time series data, and consecutive real-time decompression of the data packets generated, with improved error detection/correction and data recovery. The algorithm described in the following takes a patented invention from 2011 one step further.
In a first step, a mechanism is used to separate the bits of a fixed length time-series-data-packet into those bits that are expected to be in the same state as a reference packet (predictable bits) and those that are not. In chain mode the reference packet is the previous packet of that type. Any predictable bit value that is not the same as the reference data value is immediately classed as non predictable (Negative Mask Update). And any non-predictable that has the same value as the reference data value over a tracking period will be classed as predictable in the next tracking period (Positive Mask Update). A tracking period is typically twenty packets, so if a non-predictable bit does not change state for at least twenty successive packets it can be re-classed as predictable.
The positive and negative mask updates are sent to the receiver in the form of counters, followed by the corresponding non-predictable bit values sent in the clear. The mask is updated at every iteration and thus the data redundancy is constantly tracked. Unexpected changes are dealt with immediately but it takes at least one tracking period of consistent positive results to declare a bit predictable again. Thus the robustness of the system is increased while the performance and stability are kept.
For decompression, the receiver has a model of the mask and updates it with the counters arriving in every packet. These can be positive updates and/or negative updates and/or absolute values. This mask is then used to indicate which bits in the non-predictable field of the compressed packet should be inserted into a copy of the reference packet. Thanks to the update rules, the reference packet can be any packet of that type successfully received in the present or last tracking period. The decompression algorithm applies the changes to the ground mask “blindly” i.e. it does not matter if the changes have been made before or if packets have been lost in the meantime (as long as the protection level is not exceeded). This makes recovery from a certain number of sequential packet losses automatic. Also the decompression algorithm is agnostic to the setup of the compression algorithm, so protection level and tracking period can be changed unilaterally either by the receiver or sender software.
Innovations and advantages:
The main benefits of this invention are:
Reactivity: The algorithm constantly tracks the data redundancy in the packets at bit level. This fast reaction reduces CPU usage and increases speed.
Efficiency: Testing on space telemetry data showed compression performance is better than using Winzip even on raw data files that contain days or weeks of stored packets
Robustness: The system is insensitive to multiple sequential packet losses in both compression and decompression operations. It has the ability to recover information in the majority of packets that have been previous lost by reconstructing it from mask evolution history
Fast enough for use on real time data stream: The C based algorithm uses (almost exclusively) bitwise operations e.g. ORs, XORs and bit shifts. It therefore runs so fast that compressed packets will not interrupting the real-time data stream or packet store writing process.
Decompression is compression configuration agnostic: The compression system can unilaterally decide to change the compression parameters (robustness, tracking rate and sending uncompressed packets) without the need to synchronize with the decompression algorithm.
Applications and Markets
This invention may be used for reducing bandwidth and CPU usage when transmitting time series data. In space, the invention is used for housekeeping telemetry data. Current applications on earth include data transfer from oil-rigs and other sites in the oil and gas industry and UAV data transmission. Similarly, the intervention could be useful for traffic monitoring, energy grids, remotely controlled systems such as robots and autonomous driving, and in data analytics.
Intellectual property status
An international patent application has been filed.