GPS track transfer via SMS
You have a distributed and fault-tolerant backend warmed up, a cool mobile application written for all possible platforms, but, suddenly, it turns out that your users are so far from civilization that the only way to communicate with them is SMS? Then it will be interesting for you to read a story about how to transfer maximum information using this archaic channel for data transmission, using the example of a GPS track.
In our particular case, a track was a sequence of points defined by the coordinates at which the user was located, with reference to time and, possibly, some flags (for example, SOS, the beginning of the track).
Time could be determined in this way:
Coordinates are longitude and latitude. The Location object on Android uses double for longitude and latitude.
Thus, each point of the track should contain 64 + 2 * 64 + 2 = 194 bits of information.
Who used (uses) SMS remembers that you can type 70 characters in one Cyrillic alphabet in one SMS, and 160 in transliteration! That's where the injustice is, and you say sanctions.
How SMS is arranged can be read in RFC 5724 :
Thus, as a payload, you can use 140 bytes, which turn into those same 160 characters for 7-bit encoding (Latin, numbers and a few more characters ).
You can send a significantly larger amount of text, but then the original message will be broken into parts. Each part will be 6 bytes less, since the segment information is stored in a special UDH header at the beginning of each piece. In 7-bit characters, 153. remains.
In theory, splitting up to 255 segments is supported; in practice, I saw guaranteed support for only 6 segments.
To place the binary data of the track in SMS, a simple and compatible conversion with Base64 7-bit encoding should be used, which outputs four 7-bit characters for every three bytes of the source data. In total, there is not so much useful data left - just 160 * 3/4 = 120 bytes.
The application had a great future, so the format being developed should not be limited to one type of message or one version of the protocol, so the type short was assigned to messageType.
Since the data had to be received via SMS, where there are no certificates, passwords and authentications familiar to the classic web, it was necessary to learn how to bind the received message to the system user: an authenticationToken of type long, generated randomly, was introduced.
For integrity control, a checksum field of type short was added.
The total size of the header is 2 + 8 + 2 = 12 bytes.
We exclude the size of the header from the total amount of useful data: 120 - 12 = 108 bytes or
864 bits.
One track point occupies 194 bits. One SMS includes 864 bits of track data. Ahem, only 864/194 = 4 points will fit.
But what if you break the message into 6 segments? 1 segment = 153 7-bit characters; 6 segments = 153 * 6 = 818 7-bit characters. The useful data will be 818 * 3/4 = 613 bytes. Thus, 613 - 12 = 601 bytes or 4808 bits will remain under the track data. In total, it will be possible to put 4808/194 = 24 points into a fat SMS'ku and another 19 bytes will remain.
In addition to the obvious minus - you can put very few points in the message, the uncomfortable logic of working with a point that takes up a multiple of bytes in length crawls out.
Let us leave accuracy to 4 seconds.
Introduce our era :
Relative to the standard Unix (January 1, 1970 UTC). The date above corresponds to January 1, 2014 UTC.
Given the last assumption, it is enough for us to store 4 bytes for the time:
(60/4) * 60 * 24 * 365.25 * 50 = 394,470,000 <2 ^ 29. 3 more bits in reserve (for flags).
The earth is very close in shape to a ball, flattened from the poles, so the length of the equator (40 075 696 meters) is slightly longer than the length of the doubled meridian (40 008 552 meters).
Coordinates in Location are specified in degrees (± depending on the S / W and S / S).
In total, we have 360 degrees in a circle, or 21,600 minutes, or 1,296,000 seconds. Thus, in one meter of the equator or meridian, it is at least 0.032 seconds (1,296,000 / 40,075,696 = 0.0323388 ...). At a latitude of, say, 60 degrees in one meter, the parallel will be about 2 times as many seconds (about 0.064 seconds). What does it mean? The positioning error of 1 meter at the equator and at the 60th parallel differs in the error in degrees Location.getLongitude () by half. Moreover, the farther from the equator, the error in degrees when fixed in meters above. And vice versa: when moving away from the equator with a fixed error in degrees - in meters the error decreases, that is, rounding the equator to 32/1000 seconds near the equator will give the largest positioning error of not more than one meter.
Suppose we are satisfied with a positioning accuracy of 5 meters (in fact, the accuracy of the values received from the GPS module turns out to be much worse). Let's take the border lower: let the positioning accuracy be at least 3 meters in latitude and longitude (5> 3 * sqrt (2)).
Now, we can discard the coordinates in double and bring them to a non-negative integer value with an accuracy of 96/1000 seconds:
Obviously, the new values will not exceed 360 * 60 * 60 * 1000/96 = 13,500,000 <2 ^ 24, which fits into 3 bytes, and even the bit remains “in reserve” from the latitude conversion, since the maximum possible value will be 2 times less and 23 bits are enough to store the value.
The track point size was reduced to 4 + 3 + 3 = 10 bytes and a few more bits were left unused. A regular SMS began to include 864/80 = 10 points. In bold of 6 segments: 4808/80 = 60 points.
Prior to this, we did not use the fact that the points belong to one track; therefore, we can make assumptions about the distance between points and time intervals.
Thus, the absolute coordinates and time were fixed only for the first point, and all subsequent points stored in themselves an offset relative to the previous one in both coordinates and time. Such optimization made it possible to reduce the size of subsequent points by another 2 bytes to 8 bytes, increasing, as a result, the total number of points in one SMS'ke to 13, and in bold to 84.
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 are the field lengths in bits.
HEX-record of a binary message (30 bytes), consisting of a header (12 bytes) and two points (10 and 8 bytes, respectively): Decryption:
PS All with the upcoming! I hope someone will find this post useful / interesting.
A bit about the GPS track
In our particular case, a track was a sequence of points defined by the coordinates at which the user was located, with reference to time and, possibly, some flags (for example, SOS, the beginning of the track).
Time could be determined in this way:
long time= System.currentTimeMillis();
Coordinates are longitude and latitude. The Location object on Android uses double for longitude and latitude.
Thus, each point of the track should contain 64 + 2 * 64 + 2 = 194 bits of information.
A little about SMS
SMS bike
В нулевые в студенческие годы на базах отдыха за пределами города проходили всевозможные зимние выездные школы и молодёжные конференции. В ту пору надёжное покрытие сотовой связи за городом было редкостью, а своим родителям как-то надо было сообщить, что жив-здоров, не замёрз и шапку не забыл. Вот тогда-то и приходило понимание, что SMS'ки вещь нужная и полезная. Отправить SMS с земли не получалось, а вот на некоторой высоте — на второй-третий раз удавалось. Надёжнее всего было привязать телефон к длинной палке, набрать и отправить сообщение, поднять палку вверх, подержать её некоторое время вертикально, затем проверить — отправилось ли сообщение, в случае необходимости — повторить процедуру. Некоторые особо отчаянные подбрасывали телефоны вверх в надежде отправить таким образом SMS'ку — сообщения-то отправлялись, да только потом приходилось искать свою Nokia в сугробе. На моей памяти ни один телефон не потеряли, не разбили — Nokia же.
Who used (uses) SMS remembers that you can type 70 characters in one Cyrillic alphabet in one SMS, and 160 in transliteration! That's where the injustice is, and you say sanctions.
How SMS is arranged can be read 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 a payload, you can use 140 bytes, which turn into those same 160 characters for 7-bit encoding (Latin, numbers and a few more characters ).
You can send a significantly larger amount of text, but then the original message will be broken into parts. Each part will be 6 bytes less, since the segment information is stored in a special UDH header at the beginning of each piece. In 7-bit characters, 153. remains.
In theory, splitting up to 255 segments is supported; in practice, I saw guaranteed support for only 6 segments.
Binary format: Title
To place the binary data of the track in SMS, a simple and compatible conversion with Base64 7-bit encoding should be used, which outputs four 7-bit characters for every three bytes of the source data. In total, there is not so much useful data left - just 160 * 3/4 = 120 bytes.
The application had a great future, so the format being developed should not be limited to one type of message or one version of the protocol, so the type short was assigned to messageType.
Since the data had to be received via SMS, where there are no certificates, passwords and authentications familiar to the classic web, it was necessary to learn how to bind the received message to the system user: an authenticationToken of type long, generated randomly, was introduced.
For integrity control, a checksum field of type short was added.
The total size of the header is 2 + 8 + 2 = 12 bytes.
We exclude the size of the header from the total amount of useful data: 120 - 12 = 108 bytes or
864 bits.
Naive implementation
One track point occupies 194 bits. One SMS includes 864 bits of track data. Ahem, only 864/194 = 4 points will fit.
But what if you break the message into 6 segments? 1 segment = 153 7-bit characters; 6 segments = 153 * 6 = 818 7-bit characters. The useful data will be 818 * 3/4 = 613 bytes. Thus, 613 - 12 = 601 bytes or 4808 bits will remain under the track data. In total, it will be possible to put 4808/194 = 24 points into a fat SMS'ku and another 19 bytes will remain.
In addition to the obvious minus - you can put very few points in the message, the uncomfortable logic of working with a point that takes up a multiple of bytes in length crawls out.
Optimization
Time
- In fact, we don’t need millisecond accuracy
- The application will not send data for past decades
- The application is unlikely to last unchanged for 50 years
Let us leave accuracy to 4 seconds.
Introduce our era :
long ERA = 1388534400000L;
Relative to the standard Unix (January 1, 1970 UTC). The date above corresponds to January 1, 2014 UTC.
Given the last assumption, it is enough for us to store 4 bytes for the time:
(60/4) * 60 * 24 * 365.25 * 50 = 394,470,000 <2 ^ 29. 3 more bits in reserve (for flags).
long time= System.currentTimeMillis();
long newTime = (time - ERA) / (1000 * 4);
Geography
The earth is very close in shape to a ball, flattened from the poles, so the length of the equator (40 075 696 meters) is slightly longer than the length of the doubled meridian (40 008 552 meters).
Coordinates in Location are specified in degrees (± depending on the S / W and S / S).
In total, we have 360 degrees in a circle, or 21,600 minutes, or 1,296,000 seconds. Thus, in one meter of the equator or meridian, it is at least 0.032 seconds (1,296,000 / 40,075,696 = 0.0323388 ...). At a latitude of, say, 60 degrees in one meter, the parallel will be about 2 times as many seconds (about 0.064 seconds). What does it mean? The positioning error of 1 meter at the equator and at the 60th parallel differs in the error in degrees Location.getLongitude () by half. Moreover, the farther from the equator, the error in degrees when fixed in meters above. And vice versa: when moving away from the equator with a fixed error in degrees - in meters the error decreases, that is, rounding the equator to 32/1000 seconds near the equator will give the largest positioning error of not more than one meter.
Suppose we are satisfied with a positioning accuracy of 5 meters (in fact, the accuracy of the values received from the GPS module turns out to be much worse). Let's take the border lower: let the positioning accuracy be at least 3 meters in latitude and longitude (5> 3 * sqrt (2)).
Now, we can discard the coordinates in double and bring them to a non-negative integer value with an accuracy of 96/1000 seconds:
long newLatitude = (latitude + 90) * 60 * 60 * 1000 / 96;
long newLongitude = (longitude + 180) * 60 * 60 * 1000 / 96;
Obviously, the new values will not exceed 360 * 60 * 60 * 1000/96 = 13,500,000 <2 ^ 24, which fits into 3 bytes, and even the bit remains “in reserve” from the latitude conversion, since the maximum possible value will be 2 times less and 23 bits are enough to store the value.
Result
The track point size was reduced to 4 + 3 + 3 = 10 bytes and a few more bits were left unused. A regular SMS began to include 864/80 = 10 points. In bold of 6 segments: 4808/80 = 60 points.
More optimizations
Prior to this, we did not use the fact that the points belong to one track; therefore, we can make assumptions about the distance between points and time intervals.
Thus, the absolute coordinates and time were fixed only for the first point, and all subsequent points stored in themselves an offset relative to the previous one in both coordinates and time. Such optimization made it possible to reduce the size of subsequent points by another 2 bytes to 8 bytes, increasing, as a result, the total number of points in one SMS'ke to 13, and in bold to 84.
Format description
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 are the field lengths in bits.
Example
HEX-record of a binary message (30 bytes), consisting of a header (12 bytes) and two points (10 and 8 bytes, respectively): Decryption:
00 01 00 11 AA BB CC DD EE FF 00 90 80 00 24 09 54 04 9D 89 87 A0 09 B1 40 00 00 20 92 7C
short messageType = 1; // 00 01long authenticationToken = 4972798176784127L; // 00 11 AA BB CC DD EE FFshort checksum = 144; // 00 90boolean start = true; // [1]000 0000 00 24 09boolean sos = false; // 1[0]000 0000 00 24 09int dateTime = 9225; // 100[0 0000 00 24 09] // 1 января 2014 10:15:00 UTCint latitude = 5506205; // 0[101 0100 04 9D] // 56.83213333° с. ш. (исходные данные: 56.832139° с. ш.)int longitude = 9013152; // 89 87 A0 // 60.35072° в. д. (исходные данные: 60.350722° в. д.)int offset = 2481// 09 B1 // 1 января 2014 12:45:24 UTCboolean start2 = false; // [0]100 0000 00 00boolean sos2 = true; // 0[1]00 0000 00 00boolean north2 = false; // 01[0]0 0000 00 00int latitude2 = 0; // 010[0 0000 00 00] // 56.83213333° с. ш.boolean east2 = true; // 00[1]0 0000 92 7Cint longitude2 = 37500; // 001[0 0000 92 7C] // 61.35072° в. д.
PS All with the upcoming! I hope someone will find this post useful / interesting.