Algorithms for eliminating false and redundant data in the GPS stream

Development of electronics based on GPS / GLONASS technologies is one of our favorite topics on Habré. We have already written a review article on this topic, talked about the ERA-GLONASS system and even determined our location via cellular networks.

This time, our post is designed to answer the specific practical question: "How to reduce the amount of data flow from navigation and communication terminals without losing information?". This topic is very relevant, because wireless services make up a significant part of the financial costs of servicing transport monitoring systems.
')
To begin, let's see what is the path of preparation and collection of information on the terminals before sending data to the server.

The figure below shows a flowchart of this process:



The stage of the point formation, from the moment of receiving the coordinates from the GPS receiver to the moment of transfer to the server, can be divided into three preparatory parts: stabilization, filtering and thinning.

Stabilization and filtering are optional steps, they are needed to correct the imperfect reception quality of the GPS signal. Often, the stabilization problem can be solved by the accelerometer installed on the device, as well as by the algorithm for averaging points. In this way, we get rid of the so-called "stars" in the vehicle stops and can become attached to a static position when the vehicle is at rest.

Filtering is designed to track physically impossible coordinate throws. Such a situation arises in short-term critical reception conditions (for example, under power lines).

And, finally, decimation of points or decimation is the most common and logical stage in the task of reducing the amount of transmitted data, we will consider it in this article.

1. Thinning points or decimation in navigation systems

Suppose that each navigation point contains information about the location of the vehicle, information obtained from sensors installed on board and any statuses characterizing the state of the system. Usually, information from the GPS receiver arrives every second, i.e. every second we have a generated data set, which without the decimation algorithm would have to be transmitted completely. This information is for the most part redundant.

If the vehicle was moving relatively evenly along some part of the road, then we will not lose important data if we drop intermediate points. At the same time, we will save points in areas where there were dramatic changes in navigation parameters. Below is an example of thinning points on this principle:



In this example, we saved 72% of the data in the case of an average degree of thinning and as much as 96% in the case of severe conditions of thinning! As you can see, this simple method gives a huge advantage in saving memory.

But in real conditions, when the navigation data is supplemented with information from the onboard sensors, the algorithm is a bit more complicated, as it becomes necessary to transmit data also on system events. Therefore, all the thinning criteria can be divided into groups according to priorities: system events (“interruptions”) and information on the vehicle navigation characteristics.

System events include the following: power on / off, connection establishment / loss with satellites, etc. Obviously, system interrupts take precedence over general information. The relationship between priority and importance of information can be represented by the following flowchart:



When one of the conditions is met, the packet is passed on to check the remaining conditions or is sent to a non-linear buffer. If none of the conditions are met, then the packet is dropped from the stream.

An example implementation of the thinning algorithm in the C language may be as follows:

#define TIME_LIMIT 60 //sec #define HDOP_LIMIT 400 #define DISTANCE_LIMIT 300 //m #define SPEED_LIMIT 4000//km/h #define COURSE_LIMIT 9000 //deg GPS_DATA previous_sample; int GPS_decimator(GPS_DATA * sample) { if (sample->time.sec + sample->time.min*60 + sample->time.hour*3600 - previous_sample.time.sec - previous_sample.time.min*60 - previous_sample.time.hour*3600 > TIME_LIMIT) { return 1; } if (sample->hdop > HDOP_LIMIT) { return 0; } double UTMNorthing; double UTMEasting; double GPS_passed_northing; double GPS_passed_easting; char UTMZone[4]; double la; modf(sample->la/100,&la); la += ((sample->la)-la*100)/60; double lo; modf(sample->lo/100,&lo); lo += ((sample->lo)-lo*100)/60; //convert coordinates to UTM LLtoUTM(la, lo, &UTMNorthing, &UTMEasting, UTMZone); double pla; modf(previous_sample.la/100,&pla); pla += ((previous_sample.la)-pla*100)/60; double plo; modf(previous_sample.lo/100,&plo); plo += ((previous_sample.lo)-plo*100)/60; //convert coordinates to UTM LLtoUTM(pla, plo, &GPS_passed_northing, &GPS_passed_easting, UTMZone); if (sqrt(pow(UTMNorthing-GPS_passed_northing,2)+pow(UTMEasting-GPS_passed_easting,2)) >= DISTANCE_LIMIT) { return 1; } if ((previous_sample.speed - sample->speed)*(previous_sample.speed - sample->speed) >= SPEED_LIMIT*SPEED_LIMIT) { return 1; } if ((previous_sample.course - sample->course)*(previous_sample.course - sample->course) >= COURSE_LIMIT*COURSE_LIMIT) { return 1; } return 0; } 

The application contains a full listing of the program (cpp-file, 17 KB). The example of the program is purely demonstrative in nature and has not been used in real projects.

2. Using the optimal data transfer protocol

The second way to reduce the amount of transmitted data is to use the optimal data transfer protocol. To begin with, we distinguish two main types of protocols: text and binary or binary.

The text protocol , for example, is NMEA, which is used in GPS receivers. In the simplest case, the transfer of an RMC string of this protocol may be sufficient to transmit navigation information.

The main features of the text protocol:

• convenient for visual perception;
• one package contains one waypoint;
• integrity is guaranteed by checksum;
• has a fixed number of fields in the package;
• data is transmitted in the clear;
• all numerical data must be converted to text and back;
• the protocol does not imply saving the number of bytes in the packet.

An example of using a text protocol:

In the photo: a personal GPS navigator with an electronic compass - a long-standing project of the Promwad engineering team, one of the first experiences in the field of navigation. This simple device returns the user to the starting point or pre-marked place on the coordinate system.

The project used the text protocol NMEA. The hardware platform of the navigator was built on the basis of electronic components with optimal parameters in order to ensure a low cost price of the device (at the level of 30 USD for a batch of 10,000 pieces). As a result, we had to solve interesting problems of optimizing algorithms for calculating distances and directions.

The GPS module of the navigator sent the coordinates in NMEA format to the Freescale MC9S08QE8 microcontroller, using them to determine the distance and motion vector to a given point. Since The memory size of the microcontroller was extremely limited, we implemented the transformation of coordinates into integer form, while the calculation error remained within acceptable limits. More information about this development can be found in the PDF file with the technical description of the project .

The second type, the binary protocol , has only one drawback - it is inconvenient for visual perception without the use of special tools. Its use with the same number of parameters as in the text version allows saving more than twice the amount of data from one package.

Using the binary protocol, you can transfer several waypoints at once, and in this way we speed up the process of transferring data from the buffer memory and save additional bytes for the transport packet headers.

The binary protocol also allows you to authenticate devices on the data collection server and transmit various service information bilaterally. Of course, some of these things can be transmitted using a text protocol, but this is not appropriate.

Another great feature that a binary protocol gives is variable packet lengths. Due to this, devices with different configurations of peripheral sensors can operate in one system. Each packet has an indivisible part consisting of a header and navigation information — the part that is the identification part, and additional fields with information received from the sensors. Moreover, at any time moment only necessary data can be added.

At first glance it may seem that with this approach problems may arise with the method of storing these packets in a non-volatile buffer, but this is easily solved by the information storage algorithm, more precisely, by choosing the structure of the stored data. So different models of the device can work in one system, without violating the general concept.

Total

Field tests and years of operation of transport monitoring systems have shown that the thinning method is a very successful approach to reducing traffic volumes and does not distort the original track with a proper selection of thinning parameters.

Regarding protocols, both text and binary are widely used in the development of monitoring systems. As a rule, text protocols are used on simpler monitoring devices with a minimal fixed set of interface sensors. These protocols are easy to recognize and recognize their data.

More professional models are supplied with binary protocols, which allows to increase the security and reliability of data, and most importantly - to reduce the amount of data transfer and save money on system maintenance. Also, the use of a binary data transfer protocol provides greater opportunities for interaction between mobile navigation and mobile terminals with a monitoring center (for example, you can organize interactive remote work with the device).

We will continue to publish navigation articles, so join the Promwad blog subscribers.