У вас прогрет распределённый и отказоустойчивый бэкенд, написано крутое мобильное приложение под все возможные платформы, но, внезапно, выясняется, что ваши пользователи так далеки от цивилизации, что единственный способ связи с ними — это SMS? Тогда вам будет интересно прочитать историю о том, как передать максимум информации, используя этот архаичный канал для передачи данных, на примере GPS-трека.
В нашем конкретном случае под треком подразумевалась последовательность точек, задаваемых координатами, в которых находился пользователь, с привязкой ко времени и, возможно, некоторыми флагами (например, SOS, начало трека).
Время можно было определять таким способом:
Координаты — это долгота и широта. В объекте Location в Android используется double для longitude и latitude.
Таким образом, каждая точка трека должна была содержать в себе 64 + 2 * 64 + 2 = 194 бита информации.
Кто пользовался (пользуется) SMS помнит, что кириллицей можно набирать 70 символов в одну SMS, а транслитом — целых 160! Вот где несправедливость, а вы говорите санкции.
О том, как же устроена SMS'ка можно почитать в RFC 5724:
Таким образом, в качестве полезной нагрузки можно использовать 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 байт останется.
Кроме очевидного минуса — в сообщение можно поместить очень мало точек, вылезает неудобная логика работы с точкой, занимающей не кратную байту длину.
Пусть мы оставим точность до 4 секунд.
Введём свою эру:
Относительно стандартной юниксовой (1 января 1970 года UTC). Дата выше соответствует 1 января 2014 года UTC.
С учётом последнего допущения нам достаточно хранить 4 байта для времени:
(60 / 4) * 60 * 24 * 365.25 * 50 = 394 470 000 < 2^29. Ещё 3 бита в запасе (на флаги).
Земля очень близка по форме шару, сплюснутому со стороны полюсов, таким образом длина экватора (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 секунды:
Очевидно, что новые значения не превысят 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.
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) ||
В скобках указаны длины полей в битах.
HEX-запись бинарного сообщения (30 байт), состоящего из заголовка (12 байт) и двух точек (10 и 8 байт, соответственно):
Расшифровка:
P.S. Всех с наступающим! Надеюсь, пост окажется кому-нибудь полезным/интересным.
Немного про 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.
Описание формата
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) ||
В скобках указаны длины полей в битах.
Пример
HEX-запись бинарного сообщения (30 байт), состоящего из заголовка (12 байт) и двух точек (10 и 8 байт, соответственно):
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 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° в. д.P.S. Всех с наступающим! Надеюсь, пост окажется кому-нибудь полезным/интересным.
