Data compression in industrial automation systems. SwingingDoor algorithm
Hello, dear readers. I want to bring to your attention a description of the SwingingDoor data compression algorithm and tell you how we use it.
By the nature of my work, I develop solutions in the field of industrial automation, and more specifically, the development of production information systems. Their purpose is to provide information for people and other systems. They provide up-to-date, up-to-date data as well as past data. The data comes from numerous control systems (SC), the number of parameters is measured in tens of thousands.
')
Why use compression, why not store all the data?
The reasons are fairly obvious:
Of course, hard disks with large memory capacities are available now and communication channels are getting better and better, but, let's be realistic, these issues cannot be ignored. In addition, as will be discussed below, storing the entire amount of data does not always make sense.
By the way, instead of compression, thinned data can be used (the average value of the parameter for the period), but these values ​​will already differ from the “raw” data obtained from the monitoring systems. The averaged data will smooth the instantaneous maximum and minimum values ​​of the parameters. For part of the tasks it is permissible, but for the part not.
One of the objectives of our system is to consolidate data from various IC companies into a single database.
Some ICs, such as telemechanics, provide data every second, and the data itself may not change significantly.
For example, if you look at the graph below, we will see that the “Total generation by CHP” parameter varies from 11.5 to 12.5 MW, while in most cases the neighboring values ​​differ from each other by less than 0.1, and the general dynamics of changes has some regularity.
In order not to store “extra” data, we can skip some of the readings. Compression is precisely in the selection of "necessary" data from the input stream.
General requirements for compression:
• thinned data should not change the general idea of ​​the process;
• all local extremums of the graph with a certain accuracy must be present in the thinned data - in other words, if there was a sharp jump in the parameter value, then the algorithm should fix this.
These criteria can be formulated more strictly. For example (and this criterion will be used in the following algorithm), the thinning method must ensure that if we save two points and miss several points between them, then the straight line connecting the saved points will be no more than a given error from these points.
The green line graph below shows the points that will remain after the application of compression.
There is also another requirement for compression algorithms. Since they process a large amount of data, they must be fast. Ideally (and this is implemented in the following algorithm), they should work with the data stream and, without returning to the previously obtained points, make a decision on archiving the last point considered.
For data compression, we use the SwingingDoor algorithm. The algorithm was patented in the USA in May 1987. The main area of ​​application of the algorithm is the automated process control systems and production information systems.
The algorithm is called "revolving door". The name of the algorithm reflects the principle of operation.
Step # 1 - Get the first point. At a distance equal to the error E, we postpone two vertical points L and U vertically.
Step # 2 - Get the second point. Through the reference points L, U and the resulting point draw rays. Rays form a corridor door.
Step # 3 - Point 3 does not enter the corridor built in the second step. Rotate the beam L clockwise to point 3
Step # 4 - Point 4 does not enter the corridor built at the previous step. Rotate the beam U counterclockwise to point 4
Step # 5 - Point 5 enters the corridor, do nothing
Step # 6 - Point 6 does not enter the corridor. We begin to rotate the beam U counterclockwise to the intersection with point 6 and find that the corridor doors have opened
Step # 7 - Open a new corridor, starting from point 5. Save points 1 and 5
Total of the first 5 points will be saved only two. In the example, 3 points for us turned out to be “superfluous”, which allowed us to cut off 60% of the input data.
In the specification of the algorithm, it is proposed to start a new corridor from the point located between points 5 and 6 and located on the E / 2 from the beam U. But in our project we act differently - we start to build a new corridor from the last point that enters the corridor, i.e. from point 5, because with this behavior we guarantee that all the thinned data will have a time stamp and a value obtained from the control system.
The use of data compression allowed us to:
Before implementing the algorithm, we wrote an application that simulates the operation of the algorithm. Here you can download the source code (Delphi) of the demo application.
US-Patent-4669097 - Data compression for display and storage
By the nature of my work, I develop solutions in the field of industrial automation, and more specifically, the development of production information systems. Their purpose is to provide information for people and other systems. They provide up-to-date, up-to-date data as well as past data. The data comes from numerous control systems (SC), the number of parameters is measured in tens of thousands.
')
Why use compression, why not store all the data?
Data compression
The reasons are fairly obvious:
- to reduce disk space for storing data;
- to reduce the load of data channels.
Of course, hard disks with large memory capacities are available now and communication channels are getting better and better, but, let's be realistic, these issues cannot be ignored. In addition, as will be discussed below, storing the entire amount of data does not always make sense.
By the way, instead of compression, thinned data can be used (the average value of the parameter for the period), but these values ​​will already differ from the “raw” data obtained from the monitoring systems. The averaged data will smooth the instantaneous maximum and minimum values ​​of the parameters. For part of the tasks it is permissible, but for the part not.
How we use data compression
One of the objectives of our system is to consolidate data from various IC companies into a single database.
Some ICs, such as telemechanics, provide data every second, and the data itself may not change significantly.
For example, if you look at the graph below, we will see that the “Total generation by CHP” parameter varies from 11.5 to 12.5 MW, while in most cases the neighboring values ​​differ from each other by less than 0.1, and the general dynamics of changes has some regularity.
In order not to store “extra” data, we can skip some of the readings. Compression is precisely in the selection of "necessary" data from the input stream.
General requirements for compression:
• thinned data should not change the general idea of ​​the process;
• all local extremums of the graph with a certain accuracy must be present in the thinned data - in other words, if there was a sharp jump in the parameter value, then the algorithm should fix this.
These criteria can be formulated more strictly. For example (and this criterion will be used in the following algorithm), the thinning method must ensure that if we save two points and miss several points between them, then the straight line connecting the saved points will be no more than a given error from these points.
The green line graph below shows the points that will remain after the application of compression.
There is also another requirement for compression algorithms. Since they process a large amount of data, they must be fast. Ideally (and this is implemented in the following algorithm), they should work with the data stream and, without returning to the previously obtained points, make a decision on archiving the last point considered.
SwingingDoor algorithm
For data compression, we use the SwingingDoor algorithm. The algorithm was patented in the USA in May 1987. The main area of ​​application of the algorithm is the automated process control systems and production information systems.
Principle of operation
The algorithm is called "revolving door". The name of the algorithm reflects the principle of operation.
Step # 1 - Get the first point. At a distance equal to the error E, we postpone two vertical points L and U vertically.
Step # 2 - Get the second point. Through the reference points L, U and the resulting point draw rays. Rays form a corridor door.
Step # 3 - Point 3 does not enter the corridor built in the second step. Rotate the beam L clockwise to point 3
Step # 4 - Point 4 does not enter the corridor built at the previous step. Rotate the beam U counterclockwise to point 4
Step # 5 - Point 5 enters the corridor, do nothing
Step # 6 - Point 6 does not enter the corridor. We begin to rotate the beam U counterclockwise to the intersection with point 6 and find that the corridor doors have opened
Step # 7 - Open a new corridor, starting from point 5. Save points 1 and 5
Total of the first 5 points will be saved only two. In the example, 3 points for us turned out to be “superfluous”, which allowed us to cut off 60% of the input data.
In the specification of the algorithm, it is proposed to start a new corridor from the point located between points 5 and 6 and located on the E / 2 from the beam U. But in our project we act differently - we start to build a new corridor from the last point that enters the corridor, i.e. from point 5, because with this behavior we guarantee that all the thinned data will have a time stamp and a value obtained from the control system.
Algorithm Setup
- Error E - sets the maximum possible deviation of the corridor points from the resulting line (along the Y axis). In the picture above, this line between points 1 and 5. The error must be set for each parameter separately, based on its meaning. For example, generation jumps from 10 to 10.2 MW is permissible, but frequency jumps from 50 to 50.2 Hz is a serious violation. Therefore, to generate the error, you can set, for example, equal to 0.1, and for the frequency - 0.01.
- The corridor life time is the time during which at least one point should be maintained. Possible variants of the process flow, when the data may not change significantly (air temperature in the frosty winter night). In this case, they will fall into the current range of acceptable values ​​and the algorithm will not decide on their preservation. To avoid such cases, an appropriate parameter is introduced, which is responsible for how long the data within one corridor may not be saved. For example, for data with a refresh rate of 1 second, you can specify this parameter equal to 30 seconds, thereby ensuring at least one value in the thinned graph in 30 seconds.
Conclusion
The use of data compression allowed us to:
- to provide employees of the enterprise with “raw” trends of parameters that were obtained from the UK several months ago;
- reduce the amount of storage disk space;
- reduce the load of data transmission channels;
- optimize data collection services from the enterprise IC, thereby reducing the CPU load of the servers on which data collection services are installed.
Demo application
Before implementing the algorithm, we wrote an application that simulates the operation of the algorithm. Here you can download the source code (Delphi) of the demo application.
Materials
US-Patent-4669097 - Data compression for display and storage
Source: https://habr.com/ru/post/105652/
All Articles