Передача GPS-трека по SMS30.12.2016 12:49

У вас прогрет распределённый и отказоустойчивый бэкенд, написано крутое мобильное приложение под все возможные платформы, но, внезапно, выясняется, что ваши пользователи так далеки от цивилизации, что единственный способ связи с ними — это 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 байт останется.

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

Оптимизация

Время

В действительности нам не нужна точность в миллисекунду
Приложение не будет отсылать данные за прошедшие десятилетия
Приложение вряд ли просуществует в неизменном виде 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-код для работы с заголовком и телом, но там кроме работы с байтовыми массивами и битовой логикой — ничего нет.