Передача GPS-треку по SMS

У вас прогріте розподілений і відмовостійкий бекенд, написано круте мобільний додаток під всі можливі платформи, але несподівано з'ясовується, що ваші користувачі так далекі від цивілізації, що єдиний спосіб спілкування з ними — це SMS? Тоді вам буде цікаво прочитати історію про те, як передати максимум інформації, використовуючи цей архаїчний канал для передачі даних, на прикладі GPS-треку.


Трохи про GPS-трек

У нашому конкретному випадку під треком малася на увазі послідовність точок, що задаються координатами, в яких знаходився користувач, з прив'язкою до час і, можливо, деякими прапорами (наприклад, SOS, початок треку).

можна було визначати в такий спосіб:
long time= System.currentTimeMillis();


Координати — це довгота і широта. В об'єкті Location в Android використовується double для longitude і latitude.

Таким чином, кожна точка треку повинна була містити в собі 64 + 2 * 64 + 2 = 194 біта інформації.

Трохи про SMS

Байка про SMSнульові у студентські роки на базах відпочинку за межами міста проходили всілякі зимові виїзні школи та молодіжні конференції. В ту пору надійне покриття стільникового зв'язку за містом було рідкістю, а своїм батькам треба було повідомити, що живий-здоровий, не замерз і шапку не забув. Ось тоді-то і приходило розуміння, що sms'ки річ потрібна і корисна. Відправити SMS з землі не виходило, а от на деякій висоті — на другий-третій раз вдавалося. Надійніше всього було прив'язати телефон до довгої палиці, набрати і відправити повідомлення, підняти палицю вгору, потримати його якийсь час вертикально, потім перевірити — вирушило сполучення, у разі необхідності — повторити процедуру. Деякі особливо відчайдушні підкидали телефони вгору в надії відправити таким чином SMS ку — повідомлення відправлялися, та тільки потім доводилося шукати свою Nokia в заметі. На моїй пам'яті жоден телефон не втратили, не розбили — Nokia ж.


Хто користувався (користується) SMS пам'ятає, що кирилицею можна набирати 70 символів в одну SMS, а транслітом — цілих 160! Ось де несправедливість, а ви говорите санкції.

Про те, як же влаштована SMS ка можна почитати в 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.


Таким чином, в якості корисного навантаження можна використовувати 140 байт, які перетворюються в ті самі 160 символів для 7-бітового кодування (латиниця, цифри і ще деяку кількість символів).

Допускається відправляти значно більшу кількість тексту, але тоді вихідне повідомлення буде розбито на частини. Кожна частина буде менше на 6 байт, так як інформація про сегменти зберігається в спеціальному заголовку UDH на початку кожного шматочка. У 7-бітних символів залишається 153.

В теорії підтримується розбиття до 255 сегментів, на практиці ж бачив гарантовану підтримку тільки 6 сегментів.

Бінарний формат: Заголовок

Для приміщення бінарних даних треку в SMS повинно було бути використано просте і сумісний з 7-бітної кодуванням Base64 перетворення, яке на виході на кожні три байти вихідних даних видає чотири 7-бітних символу. Отже, корисних даних залишається вже не так багато — всього 160 * 3 / 4 = 120 байт.

Додатком пророкували велике майбутнє, тому що розробляється формат не повинен обмежуватися одним типом повідомлення, так і однією версією протоколу, тому під messageType був відведений тип short.

Оскільки дані повинні були надходити по SMS, де немає звичних для класичного web-а сертифікатів, паролів і аутентифікації, потрібно було навчитися прив'язувати отримується повідомлення користувачу системи: був введений authenticationToken типу long, який генерується випадковим чином.

Для контролю цілісності було додано поле з контрольною сумою checksum типу short.

Загальний розмір заголовка став дорівнює 2 + 8 + 2 = 12 байтах.

Виключимо із загального обсягу корисних даних розмір заголовка: 120 — 12 = 108 байт або
864 біта.

Наївна реалізація

Одна точка треку займає 194 біта. В одну SMS ку входить 864 біта даних треку. Кхм, влізе лише 864 / 194 = 4 точки.

А якщо розбити повідомлення на 6 сегментів?
1 сегмент = 153 7-бітних символу; 6 сегментів = 153 * 6 = 818 7-бітних символу.
Корисних даних виявиться 818 * 3 / 4 = 613 байт.
Таким чином, під дані треку залишиться 613 — 12 = 601 байт або 4808 біта. Разом жирну SMS ку можна буде засунути 4808 / 194 = 24 точки і ще 19 байт залишиться.

Крім очевидного мінуса — повідомлення можна помістити дуже мало точок, вилазить незручна логіка роботи з крапкою, що займає не кратну байту довжину.

Оптимізація



  1. насправді нам не потрібна точність в мілісекунду
  2. Додаток не буде відсилати дані за минулі десятиліття
  3. Додаток навряд чи проіснує в незмінному вигляді 50 років


Нехай ми залишимо точність до 4 секунд.

Введемо свою еру:
long ERA = 1388534400000L;

щодо стандартної юниксовой (1 січня 1970 року UTC). Дата вище відповідає 1 січня 2014 року UTC.

З урахуванням останнього припущення нам достатньо зберігати 4 байти для часу:
(60 / 4) * 60 * 24 * 365.25 * 50 = 394 470 000 < 2^29. Ще 3 біта в запасі (на прапори).
long time= System.currentTimeMillis();
long newTime = (time - ERA) / (1000 * 4);


Географія

Земля дуже близька по формі кулі, сплюснутому з боку полюсів, таким чином довжина екватора (40 075 696 метрів) трохи більше, ніж довжина подвоєного меридіана (40 008 552 метрів).

Координати Location задаються в градусах (± залежно З/В та З/У).

Всього ж в окружності у нас 360 градусів, або 21 600 хвилин або 1 296 000 секунд. Таким чином, в одному метрі екватора або меридіана не менш 0.032 секунди (1 296 000 / 40 075 696 = 0.0323388...). На широті, скажімо, 60 градусів в одному метрі паралелі буде приблизно в 2 рази більше секунд (близько 0.064 секунд). Що це означає? Помилка позиціювання в 1 метр на екваторі і на 60-ій паралелі відрізняється помилку в градусах Location.getLongitude() в два рази. При цьому, чим далі від екватора, тим помилка в градусах за фіксованою в метрах вище. І, навпаки: при віддаленні від екватора при фіксованій помилку в градусах — в метрах помилка зменшується, тобто поблизу екватора округлення до 32/1000 секунди дасть найбільшу помилку позиціонування не більше одного метра.

Припустимо, нас влаштовує точність позиціонування в 5 метрів (насправді, точність значень, одержуваного від GPS-модуля виявляється в рази гірше). Візьмемо кордон нижче: нехай по широті і довготі точність позиціонування не менше 3 метрів (5 > 3 * sqrt(2)).

Тепер, ми може відмовитися від координат в double і привести їх до неотрицательному целочисленному значення з точністю до 96/1000 секунди:
long newLatitude = (latitude + 90) * 60 * 60 * 1000 / 96;
long newLongitude = (longitude + 180) * 60 * 60 * 1000 / 96;

Очевидно, що нові значення не перевищать 360 * 60 * 60 * 1000 / 96 = 13 500 000 < 2^24, що укладається в 3 байти, та ще й біт залишився «про запас» від перетворення latitude, так як максимально можливе значення буде менше в 2 рази і для зберігання значення буде достатньо 23 біта.

Результат

Розмір точки треку скоротився до 4 + 3 + 3 = 10 байт і ще кілька бітів залишилося не використаних.
У звичайну SMS стало входити 864 / 80 = 10 точок. В жирну з 6 сегментів: 4808 / 80 = 60 точок.

Ще оптимізації

До цього ми ніяк не використали те, що точки належать одному треку, отже можна робити припущення про відстані між точками і часових проміжках.

Таким чином, абсолютні координати і час фіксувалися тільки для першої точки, а всі наступні точки зберігали в собі зсув щодо попередньої та за координатами, і за часом. Така оптимізація дозволила скоротити розмір наступних точок ще на 2 байти до 8 байт, збільшивши, в результаті, загальна кількість точок в одній SMS ке до 13, а в жирній — до 84.

p.s. Всіх з наступаючим! Сподіваюся, пост виявиться кому-небудь корисним/цікавим. Якщо цікаво/потрібно/корисно — викладу java-код для роботи з заголовком і тілом, але там крім роботи з байтовими масивами і бітової логікою — нічого немає.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.