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.

    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


    1. In fact, we don’t need millisecond accuracy
    2. The application will not send data for past decades
    3. 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.

    Also popular now: