У вас прогрет распределённый и отказоустойчивый бэкенд, написано крутое мобильное приложение под все возможные платформы, но, внезапно, выясняется, что ваши пользователи так далеки от цивилизации, что единственный способ связи с ними — это SMS? Тогда вам будет интересно прочитать историю о том, как передать максимум информации, используя этот архаичный канал для передачи данных, на примере GPS-трека.
Немного про GPS-трек
В нашем конкретном случае под треком подразумевалась последовательность точек, задаваемых координатами, в которых находился пользователь, с привязкой ко времени и, возможно, некоторыми флагами (например, SOS, начало трека).
Время можно было определять таким способом:
long time= System.currentTimeMillis();Координаты — это долгота и широта. В объекте Location в Android используется double для longitude и latitude.
Таким образом, каждая точка трека должна была содержать в себе 64 + 2 * 64 + 2 = 194 бита информации.
Немного про SMS
Кто пользовался (пользуется) 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-код для работы с заголовком и телом, но там кроме работы с байтовыми массивами и битовой логикой — ничего нет.
Автор: gnkoshelev
