Sending a GPS track via SMS
You have a distributed and fault-tolerant backend, a cool mobile application is 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 to you to read the story of how to transfer maximum information using this archaic data transmission channel, using the example of a GPS track.
In our particular case, a track meant a sequence of points defined by the coordinates in 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 in Android uses double for longitude and latitude.
')
Thus, each track point should have contained 64 + 2 * 64 + 2 = 194 bits of information.
Who used (uses) SMS remembers that Cyrillic can dial 70 characters in one SMS, and translit - as many as 160! That's where injustice is, and you say sanctions.
About how SMS'ka is arranged can be read in RFC 5724 :
Thus, as a payload, you can use 140 bytes, which are transformed into those same 160 characters for 7-bit encoding (Latin, numbers, and some more characters ).
It is allowed to send a much larger amount of text, but then the original message will be divided into parts. Each part will be less than 6 bytes, since information about the segments is stored in a special UDH header at the beginning of each piece. In 7-bit characters, 153 remains.
The theory supports splitting up to 255 segments, but in practice, it saw guaranteed support for only 6 segments.
To put the track's binary data into SMS, a simple and compatible with 7-bit Base64 coding had to be used, which at the output for every three bytes of the source data gives four 7-bit characters. Total, there are not so many payloads left - only 160 * 3/4 ​​= 120 bytes.
A great future was predicted to the application, so the developed format should not be limited to one type of message or one version of the protocol, therefore the short type was assigned to messageType.
Since the data had to come via SMS, where there are no certificates, passwords and authentication that are familiar to the classic web-a, it was necessary to learn how to bind the received message to the user of the system: a random authenticationToken of a long type was entered.
For integrity control, a short checksum field has been added.
The total size of the header has become equal to 2 + 8 + 2 = 12 bytes.
Exclude from the total amount of useful data header size: 120 - 12 = 108 bytes or
864 bits.
One point of the track is 194 bits. One SMS'ku includes 864 bits of track data. Ahem, fit only 864/194 = 4 points.
And what if you break the message into 6 segments? 1 segment = 153 7-bit characters; 6 segments = 153 * 6 = 818 7-bit characters. The payload will be 818 * 3/4 ​​= 613 bytes. Thus, 613 - 12 = 601 bytes or 4808 bits will remain under the track data. So, you will be able to shove 4808/194 = 24 points into a fat SMS, and 19 more bytes will remain.
In addition to the obvious minus - very few points can be placed in the message, the inconvenient logic of working with a point that does not occupy a multiple of a byte gets out.
Let we leave accuracy to 4 seconds.
Let's enter our era :
Regarding the standard Unix (1 January 1970 UTC). The date above is January 1, 2014 UTC.
Given the last assumption, we only need to store 4 bytes for the time:
(60/4) * 60 * 24 * 365.25 * 50 = 394 470 000 <2 ^ 29. 3 more bits in stock (on flags).
The earth is very close in shape to the ball oblate from the side of the poles, thus the length of the equator (40,075,696 meters) is slightly longer than the length of twice the meridian (40,008,552 meters).
The coordinates in the Location are specified in degrees (± depending on the C / B and C / S).
In total, we have 360 ​​degrees around, or 21,600 minutes or 1,296,000 seconds. Thus, in one meter of the equator or meridian of at least 0.032 seconds (1,296,000 / 40,075,696 = 0.0323388 ...). At latitude, say, 60 degrees in one meter of parallel will be approximately 2 times more seconds (about 0.064 seconds). What does it mean? A 1 meter positioning error at the equator and at the 60th parallel differs in error in degrees Location.getLongitude () twice. In this case, the farther from the equator, the error in degrees with a fixed in meters above. And vice versa: when moving away from the equator with a fixed error in degrees - the error decreases in meters, that is, near the equator, rounding to 32/1000 seconds will give the greatest positioning error of no more than one meter.
Suppose we are satisfied with the positioning accuracy of 5 meters (in fact, the accuracy of the values ​​obtained from the GPS module turns out to be several times worse). Let's take the border lower: let the latitude and longitude positioning accuracy of at least 3 meters (5> 3 * sqrt (2)).
Now, we can drop 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 the bit is still “in reserve” from the latitude conversion, since the maximum possible value will be 2 times less and 23 bits will be enough to store the value.
The size of the track point was reduced to 4 + 3 + 3 = 10 bytes and a few more bits remained unused. The usual SMS began to enter 864/80 = 10 points. Fat out of 6 segments: 4808/80 = 60 points.
Before that, we didn’t use the fact that the points belong to the same track;
Thus, the absolute coordinates and time were recorded only for the first point, and all subsequent points kept an offset relative to the previous one both in coordinates and in time. Such optimization allowed reducing the size of subsequent points by another 2 bytes to 8 bytes, increasing, as a result, the total number of points in one SMS'k to 13, and in fat, 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) ||
The brackets indicate the length of the fields in bits.
HEX-record of a binary message (30 bytes), consisting of a header (12 bytes) and two dots (10 and 8 bytes, respectively):
Decryption:
PS Happy New Year! I hope the post will be someone useful / interesting.
A little bit about the GPS track
In our particular case, a track meant a sequence of points defined by the coordinates in 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 in Android uses double for longitude and latitude.
')
Thus, each track point should have contained 64 + 2 * 64 + 2 = 194 bits of information.
About SMS
Bike about SMS
In the zero years in student years, various winter visiting schools and youth conferences were held at recreation centers outside the city. At that time, reliable cellular coverage outside the city was rare, and I had to somehow tell my parents that I was alive and well, I did not freeze, and I did not forget my hat. It was then that the understanding came that SMS'ki is a necessary and useful thing. It was not possible to send an SMS from the ground, but at some height it was possible for the second or third time. The most reliable thing was to tie the phone to a long stick, type and send a message, lift the stick up, hold it vertically for some time, then check whether the message was sent, if necessary, repeat the procedure. Some particularly desperate phones were thrown up in the hope of sending SMS in this way — messages were sent, and only then they had to look for their Nokia in a snowdrift. In my memory, no phone is lost, not broken - Nokia is the same.
Who used (uses) SMS remembers that Cyrillic can dial 70 characters in one SMS, and translit - as many as 160! That's where injustice is, and you say sanctions.
About how SMS'ka is arranged can be read in RFC 5724 :
GSM SMS messages are alphanumeric paging messages
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 are transformed into those same 160 characters for 7-bit encoding (Latin, numbers, and some more characters ).
It is allowed to send a much larger amount of text, but then the original message will be divided into parts. Each part will be less than 6 bytes, since information about the segments is stored in a special UDH header at the beginning of each piece. In 7-bit characters, 153 remains.
The theory supports splitting up to 255 segments, but in practice, it saw guaranteed support for only 6 segments.
Binary format: Title
To put the track's binary data into SMS, a simple and compatible with 7-bit Base64 coding had to be used, which at the output for every three bytes of the source data gives four 7-bit characters. Total, there are not so many payloads left - only 160 * 3/4 ​​= 120 bytes.
A great future was predicted to the application, so the developed format should not be limited to one type of message or one version of the protocol, therefore the short type was assigned to messageType.
Since the data had to come via SMS, where there are no certificates, passwords and authentication that are familiar to the classic web-a, it was necessary to learn how to bind the received message to the user of the system: a random authenticationToken of a long type was entered.
For integrity control, a short checksum field has been added.
The total size of the header has become equal to 2 + 8 + 2 = 12 bytes.
Exclude from the total amount of useful data header size: 120 - 12 = 108 bytes or
864 bits.
Naive implementation
One point of the track is 194 bits. One SMS'ku includes 864 bits of track data. Ahem, fit only 864/194 = 4 points.
And what if you break the message into 6 segments? 1 segment = 153 7-bit characters; 6 segments = 153 * 6 = 818 7-bit characters. The payload will be 818 * 3/4 ​​= 613 bytes. Thus, 613 - 12 = 601 bytes or 4808 bits will remain under the track data. So, you will be able to shove 4808/194 = 24 points into a fat SMS, and 19 more bytes will remain.
In addition to the obvious minus - very few points can be placed in the message, the inconvenient logic of working with a point that does not occupy a multiple of a byte gets out.
Optimization
Time
- In fact, we don't need accuracy in milliseconds.
- The application will not send data for the past decades
- The application is unlikely to exist unchanged for 50 years
Let we leave accuracy to 4 seconds.
Let's enter our era :
long ERA = 1388534400000L; Regarding the standard Unix (1 January 1970 UTC). The date above is January 1, 2014 UTC.
Given the last assumption, we only need to store 4 bytes for the time:
(60/4) * 60 * 24 * 365.25 * 50 = 394 470 000 <2 ^ 29. 3 more bits in stock (on flags).
long time= System.currentTimeMillis(); long newTime = (time - ERA) / (1000 * 4); Geography
The earth is very close in shape to the ball oblate from the side of the poles, thus the length of the equator (40,075,696 meters) is slightly longer than the length of twice the meridian (40,008,552 meters).
The coordinates in the Location are specified in degrees (± depending on the C / B and C / S).
In total, we have 360 ​​degrees around, or 21,600 minutes or 1,296,000 seconds. Thus, in one meter of the equator or meridian of at least 0.032 seconds (1,296,000 / 40,075,696 = 0.0323388 ...). At latitude, say, 60 degrees in one meter of parallel will be approximately 2 times more seconds (about 0.064 seconds). What does it mean? A 1 meter positioning error at the equator and at the 60th parallel differs in error in degrees Location.getLongitude () twice. In this case, the farther from the equator, the error in degrees with a fixed in meters above. And vice versa: when moving away from the equator with a fixed error in degrees - the error decreases in meters, that is, near the equator, rounding to 32/1000 seconds will give the greatest positioning error of no more than one meter.
Suppose we are satisfied with the positioning accuracy of 5 meters (in fact, the accuracy of the values ​​obtained from the GPS module turns out to be several times worse). Let's take the border lower: let the latitude and longitude positioning accuracy of at least 3 meters (5> 3 * sqrt (2)).
Now, we can drop 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 the bit is still “in reserve” from the latitude conversion, since the maximum possible value will be 2 times less and 23 bits will be enough to store the value.
Result
The size of the track point was reduced to 4 + 3 + 3 = 10 bytes and a few more bits remained unused. The usual SMS began to enter 864/80 = 10 points. Fat out of 6 segments: 4808/80 = 60 points.
More optimizations
Before that, we didn’t use the fact that the points belong to the same track;
Thus, the absolute coordinates and time were recorded only for the first point, and all subsequent points kept an offset relative to the previous one both in coordinates and in time. Such optimization allowed reducing the size of subsequent points by another 2 bytes to 8 bytes, increasing, as a result, the total number of points in one SMS'k to 13, and in fat, 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) ||
The brackets indicate the length of the fields in bits.
Example
HEX-record of a binary message (30 bytes), consisting of a header (12 bytes) and two dots (10 and 8 bytes, respectively):
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
Decryption:
short messageType = 1; // 00 01 long authenticationToken = 4972798176784127L; // 00 11 AA BB CC DD EE FF short checksum = 144; // 00 90 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 2014 10:15:00 UTC int 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 UTC boolean start2 = false; // [0]100 0000 00 00 boolean sos2 = 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° . . boolean east2 = true; // 00[1]0 0000 92 7C int longitude2 = 37500; // 001[0 0000 92 7C] // 61.35072° . . PS Happy New Year! I hope the post will be someone useful / interesting.
Source: https://habr.com/ru/post/318796/
All Articles