Transfer the GPS tracks by SMS

you Have warmed-up a distributed and fault-tolerant backend written cool mobile application for all possible platforms, but, suddenly, it appears that your users are so far from civilization that the only way of contact is SMS? Then you will be interested to read a story about how to convey maximum information using this channel for data transmission, for example of the GPS track.

the

a Bit about GPS-track

In our particular case, under the track meant a sequence of points set coordinates, which was the user, with reference to time and maybe some flags (for example, SOS, the beginning of the track).

Time could be defined this way:

the

long time= System.currentTimeMillis();

Coordinates is the longitude and latitude. The object Location Android uses a double for longitude and latitude.

Thus, each track point was supposed to contain 64 + 2 * 64 + 2 = 194 bits of information.

the

a Little about SMS

stories about SMS

zero as a student in recreation outside the city took all kinds of winter visiting schools and youth conference. At that time reliable cellular coverage outside the city was a rarity, and my parents once had to report that is alive and healthy, not frozen and the cap is not forgotten. Then came the understanding that SMS key thing necessary and useful. Send SMS from earth did not work, but at a certain height on the second or third time succeeded. It is safest to tie the phone to a long stick, to type and send a message, raise stick up, hold it some time vertically, then test — did the message, if necessary — repeat the procedure. Some particularly desperate threw the phone up in hopes to send so SMS ku — messages-that were sent, but only then had to find my Nokia in the snow. In my memory none of the phone is not lost, not broken Nokia.

Who used (uses) SMS remember that the Cyrillic alphabet, you can score 70 characters in one SMS, and translit — as many as 160! That's where the injustice, and you say sanctions.

How is SMS ka can be found in RFC 5724:

GSM SMS messages are alphanumeric paging messages that can be sent to
and from SMS clients. SMS messages have a maximum length of 160
characters (7-bit characters from the GSM character set [SMS-CHAR])
or 140 octets. Other character sets (such as UCS-2 16-bit
characters, resulting in 70-character messages) MAY also be supported
[SMS-CHAR], but are defined as being optional by the SMS
specification. Consequently, applications handling SMS messages as
part of a chain of character-processing applications MUST make sure
that character sets are correctly mapped to and from the character
set used for SMS messages.

Thus, as the payloads you can use 140 bytes, which are converted into those 160 characters for 7-bit encoding (Latin, digits and some number of characters).

Allowed to send a much larger amount of text, but then the original message will be broken into pieces. Each part will be less than 6 bytes as the information about segments is stored in a special header UDH at the beginning of each piece. In the 7-bit characters remains 153.

In theory supports partitioning up to 255 segments, in practice, seen the guaranteed support of only 6 segments.

the

Binary format: Header

To place binary data of the track in the SMS was to be used simple and compatible with 7-bit Base64 conversion, which is output for every three bytes of the original data displays four 7-bit symbols. Total payload remains not so much — just something 160 * 3 / 4 = 120 bytes.

Application ago prophesied a great future, therefore, the developed format is not supposed to be limited as one message type and one version of the Protocol, therefore, under the messageType has been assigned the type short.
Because the data were to enter by SMS, where there is the usual for the classical web-a certificates, passwords and identity, need to learn how to bind the received message to the system user, was introduced authenticationToken long, randomly generated.

Integrity were added to the checksum the checksum of type short.

The total size of the header was equal 2 + 8 + 2 = 12 bytes.

Exclude from the total payload header size: 120 — 12 = 108 bytes, or
864 bits.

the

the Naive implementation

One point of the track is 194 bits long. One SMS ku includes 864 bits of the track. Ahem, fit only 864 / 194 = 4 points.

But what if you break up the message into 6 segments? 1 segment = 153 7-bit character; 6 segments = 153 * 6 = 818 7-bit character. The payload will be 818 * 3 / 4 = 613 bytes. Thus, under the data of the track will remain 613 — 12 = 601 4808 bytes or bits. Total fat SMS ku can be put 4808 / 194 = 24 points and 19 bytes left.

Besides the obvious downside in the message you can put very few points out uncomfortable the logic behind point, does not occupy a multiple of the byte length.

the

Optimization

the

Time

the
1. In fact we don't need precision in milliseconds
the
2. the Application will not send the data over the past decade
the
3. the Application is unlikely to survive intact for 50 years

May we leave the accuracy to 4 seconds.

Will enter its era:

the

long ERA = 1388534400000L;

Relative to the standard uniksboy (January 1, 1970 UTC). The above date corresponds to January 1, 2014 UTC.

Taking into account the latest assumptions, we just need 4 bytes for time:

(60 / 4) * 60 * 24 * 365.25 * 50 = 394 470 000 < 2^29. 3 more bits (flags).

the

long time= System.currentTimeMillis();
long newTime = (time - ERA) / (1000 * 4);

the

Geography

The land is very close to form a ball, flattened from the poles, so the length of the equator (40 075 696 metres) slightly more than twice the length of a Meridian (40 008 552 meters).

Location coordinates are given in degrees (± depending on S/b and C/Yu).

All in the circle we have 360 degrees, or 21 600 minutes or 1 296 000 seconds. Thus, in one meter at the equator or a Meridian of not less than 0.032 seconds (1 296 000 / 40 075 696 = 0.0323388...). At latitude, say 60 degrees in one meter parallel will be approximately 2 times more seconds (about 0.064 seconds). What does it mean? The positioning error of 1 meter at the equator and the 60th parallel is different in the error in degrees Location.getLongitude() twice. Thus, the farther from the equator, the error in degrees when fixed in the meters above. And Vice versa: when you remove from the equator at a fixed error in degrees in meters error is reduced, that is, near the equator round to 32/1000 of a second will give the greatest positioning error of not more than one meter.

Let's say we are satisfied with the positioning accuracy to 5 meters (in fact, the precision of the values received from the GPS module is significantly worse). Take the border down: let at the latitude and longitude positioning accuracy at least 3 meters (5 > 3 * sqrt(2)).

Now, we can abandon the coordinate to double, and lead them to a nonnegative integer value with a precision of 96/1000 seconds:

the

long newLatitude = (latitude + 90) * 60 * 60 * 1000 / 96;
long newLongitude = (longitude + 180) * 60 * 60 * 1000 / 96;

It is obvious that the new values will not exceed 360 * 60 * 60 * 1000 / 96 = 13 500 000 < 2^24, which fits into 3 bytes, but still a bit left in reserve from conversion of latitude, since the maximum possible value will be less than 2 times and to store the value 23 bits will be enough.

the

Result

The point size of the track was reduced to 4 + 3 + 3 = 10 bytes and a few bits left unused. In normal SMS was included 864 / 80 = 10 points. In the fat of the 6 segments: 4808 / 80 = 60 points.

the

More optimization

Before that we never used the fact that the points belong to one track, therefore you can make assumptions about the distance between points and time intervals.
Thus, the absolute coordinates and the time were recorded only for the first point and all subsequent points to keep the offset relative to the previous and to the coordinates and time. This optimization allowed to reduce the size of subsequent points is still 2 bytes to 8 bytes, increasing, in the end, the total number of points in one SMS ke to 13, and in fat — up to 84.

the

Description format

HEADER (96) + BODY (variable):
|| Message Type (16) | Authentication Token (64) | Checksum (16) || Data (variable) ||

FIRST TRACKPOINT INFO (80):
|| Start (1) | SOS (1) | Reserved (1) | DateTime (29) | Reserved (1) | Latitude (23) | Longitude (24) ||

NTH TRACKPOINT INFO (64):
|| Offset (16) | Start (1) | SOS (1) | North (1) | Latitude (21) | Reserved (1) | Reserved (1) | East (1) | Longitude (21) ||

In parentheses indicate field length in bits.

the

Example

HEX record binary message (30 bytes) consisting of a header (12 bytes) and two points (10 and 8 bytes respectively):

00 00 01 11 AA BB CC DD EE FF 00 90 80 00 09 54 24 04 89 87 9D A0 09 40 B1 00 00 20 92 7C

Transcript:

the

short messageType = 1; // 00 01
long authenticationToken = 4972798176784127L; // 00 11 AA BB CC DD EE FF
short checksum = 144; // 90 00
boolean start = true; // [1]000 0000 00 24 09
boolean sos = false; // 1[0]000 0000 00 24 09
int dateTime = 9225; // 100[0 0000 00 24 09] // 1 Jan 2014 10:15:00 UTC
int latitude = 5506205; // 0[101 0100 04 9D] // 56.83213333° N. lat. (source: 56.832139° N. lat.)
int longitude = 9013152; // 89 87 A0 // 60.35072° E. (source: 60.350722° e)
int offset = 2481 // 09 B1 // 1 Jan 2014 12:45:24 UTC
boolean start2 = false; // [0]100 0000 00 00
sos2 boolean = true; // 0[1]00 0000 00 00
boolean north2 = false; // 01[0]0 0000 00 00
int latitude2 = 0; // 010[0 0000 00 00] // 56.83213333° S. sh.
east2 boolean = true; // 00[1]0 0000 92 7C
int longitude2 = 37500; // 001[0 0000 92 7C] // 61.35072° e

PS thank you! I hope the post will be useful to someone/interesting.

Article based on information from habrahabr.ru