Пользователь: это невозможно, GPS съест батарейку
Джуниор: это возможно, используй Geofences
Сеньор: есть варианты и получше

image
На картинке сначала в одну, а потом в другую сторону одновременно с одним человеком «прогулялись» 6 одинаковых телефонов. Но какой разный результат!

Геолокация используется в самых разных задачах. Возьмем нередкий сценарий, когда сами по себе координаты пользователя неинтересны, но крайне важно знать когда он входит в определенные географические радиусы. Спектр приложений, где это нужно, очень широк — от магазинных списков и гео-игр до логистики и безопасности.

В нашем случае этот сценарий осложняется тремя абсолютно взаимоисключающими вещами:
  1. Малый радиус. Требуется определять факт вхождения пользователя в достаточно небольшой радиус местности — 500 метров.
  2. Высокая вероятность. Необходима сильно отличная от нуля вероятность того, что пользователь не проскочит радиус. Учитывая что сейчас может быть «безпробочное» время суток и он едет на авто, то всё становится достаточно печально.
  3. Минимальное энергопотребление. Важный момент для любого приложения, но что хуже всего — мы разрабатываем не приложение, а SDK, который должен встраиваться в другие приложения. Другие разработчики доверяют нам, и в случае проблем пострадают в первую очередь они, именно их приложения будут заминусованы пользователями или удалены. Поэтому требования к энергопотреблению самые высокие.

Вообще сам по себе сценарий, конечно, чудовищный с технической точки зрения. Ведь в большинстве приложений геолокация или используется кратковременно (чекин, посмотреть где сейчас нахожусь, сохранить в exif место фотосъемки) и не требует большого энергопотребления, или ожидаемо для пользователя сжирает батарейку (навигаторы) и потому заставляет психологически подготовиться к этому или воткнуться в зарядку. Здесь же во многих случаях придется висеть в фоне (если так захочет разработчик родительского приложения) и потому обычные рекомендации Google по использованию локации по сути бесполезны.

Итак, проблема есть. Но есть ли решение?


Стоит отметить, что в этом материале речь идет не про оторванные размышления или просто некий набор опытов, который не выдержал бы реального использования, а про технологию, которая была реализована на основе полученных данных и используется в деле.

Как и в формуле «время-цена-ресурсы разработки» можно уменьшить только два параметра, так и мы должны чем-то пожервовать. Учитывая, что 500 метров в принципе константа, немного «отпустим» вниз от 1.0 вероятность определения вхождения в радиус.


Без включенного GPS узнать, когда пользователь будет проезжать красный радиус. Реально?

Изначально базовых вариантов по сути три — коробочное решение от Google с использованием Geofences, использование встроенных в Андроид Google Services с собственным алгоритмом или использование открытого гео-API опять же с собственным алгоритмом.
Очевидно, нужно это всё обкатать в условиях, приближенным к боевым. И раз все равно потребуются значительные временные затраты, то заодно протестируем и некие маргинальные варианты.

Участники гонки на выживание


1. Google Services Passive mode — получение только закешированных системой обращений к GEO-данным от других приложений. Это могут быть как обращения Network location — Wi-Fi в пассивном и активном режиме, мониторинг сотовых вышек, так и использование GPS.
2. Google Services GPS — старый добрый всепожирающий GPS
3. Mylnikov Provider — реализация с использованием открытого API по Wi-Fi сетям от mylnikov (сразу хочу сказать огромное спасибо за многочисленные консультации и полезные статьи). Использует API, работающий на базе, агрегированной из нескольких геобаз по Wi-Fi. Особенно интересен в тех случаях, когда хочется избежать использования пермиссий ACCESS_FINE_LOCATION и ACCESS_COARSE_LOCATION (достаточно только ACCESS_WIFI_STATE), так как напрямую использует списки Wi-Fi сетей. Правда для Android 6.0 это уже не очень актуально, так для скана сетей теперь тоже требуется ACCESS_COARSE_LOCATION.
4. Google Services Geofencesзакрытая реализация Google по определению вхождения пользователя в радиус; позволяет определять географические области, при вхождении в которые приложение поймает соответствующее событие. Из явных минусов — позволяет делать только 100 радиусов, что для некоторых задач может быть недостаточно и потребует программирования вложенных (или «расхлопывающихся») радиусов. На большинстве устройств использует только Network location (Wi-Fi + сотовые вышки).
5. Google Services Combined mode — сбалансированный режим работы Google Services Passive mode + принудительный запрос координат по Wi-Fi и вышкам сотовой связи, если мы видим что актуальность закешированных данных нас уже не устраивает.
6. i402 — реализация 402 Targeting Rus: Google Services Combined mode + адаптивный режим подстройки частоты проверки (от 1 минуты до 24 часов) в зависимости от удаленности пользователя от ближайшего радиуса

Калибруем


Для тестирования нужны комплекты из 7 одинаковых моделей телефонов. Все телефоны взяты новые, без дополнительно установленного программного обеспечения. Для более реалистичного тестирования Google Services Passive mode было бы правильно, наоборот, поставить дополнительный софт, но это внесло бы непрогнозируемые наводки и серьезно усложнило бы тестирование.
Каждый цикл и калибровки, и тестирования начинается с полной зарядки телефонов. Все измерения производятся при температуре не ниже +15.
Калибровка занимает неделю, что опять же позволяет получить уверенность в том, что батареи всех телефонов «раскачались» и пришли в стабильное состояние.

Процесс калибровки выполняется в два этапа

Этап №1
1. Настройки и софт всех экземпляров приведены в одинаковое состояние, телефоны заряжены и помещены в одинаковые условия.
2. Ожидание 24 часа.
3. Снятие данных по остаточному заряду.

Этап №2
1. Настройки и софт всех экземпляров приведены в одинаковое состояние, телефоны заряжены и помещены в одинаковые условия.
2. Во все телефоны вставлены SIM-карты одного сотового оператора.
3. Ожидание 24 часа.
4. Снятие данных по остаточному заряду.

Этапы №1 и №2 в общей сложности выполнены в пяти циклах на всех экземплярах.
По результатам выявлен телефон с ненормальным энергопотреблением, он выносится за пределы тестирования.

Помощь в работе с устройствами оказывает то, что у одного из руководителей команды в свое время был опыт участия в одновременно и одиозном и в погруженном в технические детали проекте, где делались краш-тесты как кнопочных мобильных, так и смартфонов-айфонов. Там как раз делались и замеры энергоэффективности смарфтонов — пусть и при экстремальных температурах.

6 приложений за 2 дня


Всегда приятно писать что-то небольшое, что сразу же начинает жить. Подготовлены 6 сборок одного простейшего Android-приложения, использующих разные алгоритмы сбора геоданных. Каждая сборка включает в себя реализацию варианта алгоритма, кнопки старт/стоп, полное пошаговое логирование и индикатор работоспособности экземпляра и сборки.
Индикатор — это короткий звуковой сигнал раз в минуту, по сути писк. Из-за этого тестовая сумка, наполненная тестовыми экземплярами, непрерывно издает странные звуки. К счастью для нашего непростого и опасного времени, звуки улицы и транспорта полностью глушат для окружающих непрерывный писк наших подопечных. При этом писк хорошо помогает как на начальном этапе отладки для понимания того, не зависла ли сборка, так и на последующих — для определения, не села ли еще батарейка в конкретном экземпляре и не решила ли система усыпить конкретное приложение. Ведь включение прожорливого экрана для выяснения ситуации при выполнении тестирования — непозволительная роскошь и огромная наводка.

Все сборки, кроме #4 и #5, запрашивают координаты раз в 10 минут. С одной стороны, это большое допущение, ведь радиус в 500 метров пользователь на транспорте может спокойно пересечь и за гораздо меньшее время. С другой стороны, и как подтвердит будущее, даже проверка раз в 10 минут приведет к катастрофическому энергопотреблению у «маргиналов» и вся надежда будет исключительно на умные алгоритмы.

Testing dance!


На каждом экземпляре комплекта устанавливается своя сборка тестового приложения. Один экземпляр в комплекте входит в контрольную группу и поэтому принимает плацебо. То есть на него ничего не устанавливается.

Входные данные для всех экземпляров остаются общими: общий сотовый оператор, общий маршрут, общая тряпичная сумка тестировщика. Тряпичная выбрана специально для отсутствия возможных наводок на принимаемые сигналы.

Маршруты строятся по разным рельефам как городской местности, так и за городом. Есть маршруты на авто, на транспорте, в метро, пешие маршруты. Есть даже маршрут на местности с отсутствующим по определению Wi-Fi и сотовой связью на пределе — удаленной от берегов глади Ладожского озера.

image
В этом цикле самым сложным было не утопить во время начавшегося шторма сумку тестировщика.

Результаты?


Выполнение полевых исследований занимает больше двух недель. Выходные данные каждого алгоритма оцениваются с точки зрения двух параметров:

ТОЧНОСТЬ — экспертная оценка по 5-бальной шкале в сравнении с эталоном (чем больше тем лучше).
Как определяется точность
После каждого цикла тестирования логи каждого экземпляра выгружаются, геоданные преобразовываются и отображаются на Google Maps. Базируясь на эталоне, т.е. реальном задокументированном маршруте, эксперт вручную оценивает величину отклонения от него, проставляет оценку, а также выдает текстовое обоснование. Экспертная оценка проверяется и подтверждается вторым экспертом.
Рассчитать величину отклонения в автоматизированном режиме невозможно из-за недетерминированности срабатывания таймера просыпания в Android и последующей рассинхронизации устройств, а также сложности многих маршрутов — например, поворот два раза налево за относительно небольшой для алгоритма промежуток времени или «телепортация при помощи метро».

ЭНЕРГОЭФФЕКТИВНОСТЬ — процент заряда батареи устройства после завершения цикла тестирования приводится к общей 10-бальной шкале (чем больше тем лучше) от 0 (худший уровень заряда из экземпляров комплекта в цикле) до 10 (лучший уровень из экземпляров комплекта в цикле).
Почему для определения энергоэффективности не используется профайлер?
Из-за недоверия к ним. Энергопотребление конкретного приложения, показываемое в настройках телефона, или показания специализированного софта так или иначе включают в себя набор погрешностей и допущений. Так как нас интересовали сырые данные, то мы старались ориентироваться на базовые параметры. Учитывая полную идентичность экземпляров в комплекте, отсутствие стороннего софта и предварительную калибровку, допускаемая погрешность не превысила требуемую точность измерений.

Ниже представлены средние значения параметров. Медианные значения не приводятся, так как из-за повторяемости тестов близки к средним.

1. Google Services Passive mode

ТОЧНОСТЬ: 3.4 (4-е место)
ЭНЕРГОЭФФ.: 4.3 (5-е место)

Средний по точности. Позволяет определить общую траекторию маршрута. По энергоэффективности предпоследний, но далеко оторвался от последнего участника — GPS (4.3 против 2.1). Точность сильно зависит от того, стоит на смартфоне сторонний софт, или кешировать системе почти нечего. Если второе — то система может кэшировать только собственные периодические системные запросы. Мы же помним что корпорация добра сохраняет каждый наш шаг?
К сожалению, в большинстве случаев в ТЗ собственной программы нельзя прописать «делаем расчет на то, что на телефоне будет стоять много разных программ и они будут часто обращаться к геоданным».

2. Google Services GPS

ТОЧНОСТЬ: 4.6 (2-е место)
ЭНЕРГОЭФФ.: 2.1 (6-е место)

Показывает предсказуемо отличную точность (кроме метро), но и предсказуемо затратен: во всех тестах показал наихудшую энергоэффективность.

3. Mylnikov Provider (Wi-Fi only)

ТОЧНОСТЬ: 2.2 (6-е место)
ЭНЕРГОЭФФ.: 6.2 (3-е место)

Низкий результат по точности объясняется наличием маршрутов за городом, где Wi-Fi сетей нет. Одновременно с использованием API по сотовым вышкам может показать хорошую точность и низкое энергопотребление.

4. Google Services Geofences

ТОЧНОСТЬ: 5.0 (1-е место)
ЭНЕРГОЭФФ.: 6.8 (2-е место)

Стабильная статистика качественного определения фенсов радиусом в 500 метров. Стоит предупредить, что на фенсах меньшего радиуса тестирование не проводилось. Судя по некоторым экспериментам иностранных коллег, да и по самой документации, на фенсах меньше 150 могут возникать проблемы с точностью и/или сильно вырастет энергопотребление.
Но и при 500 метрах энергопотребление могло быть и ниже, учитывая что это системная функция.

5. Google Services Combined mode

ТОЧНОСТЬ: 3.6 (3-е место)
ЭНЕРГОЭФФ.: 5.5 (4-е место)

Имел погрешности относительно эталонного GPS, но в целом стабилен. Энергопотребление хотелось бы и получше.

6. i402

ТОЧНОСТЬ: 3.1 (5-е место)
ЭНЕРГОЭФФ.: 8.5 (1-е место)

Показал предсказуемо плохую аппроксимацию в районах, далеких от места расположения радиусов, так как в далеких от радиусов местах снижал частоту проверок — за что и получил низкую оценку. При этом превосходил конкурентов по энергоэффективности, в 2-х затяжных тестах (более суток) показал экономию на более чем 5-7% заряда батареи от ближайшего конкурента. При решении базовой задачи — проверки вхождения в радиус — почти всегда ловит идущих и с достаточной вероятностью — едущих.

Итого


На первом месте по сочетанию ТОЧНОСТЬ/ЭНЕРГОЭФФЕКТИВНОСТЬ оказались все-таки Google Services Geofences. Но пусть они и стали призерами по энергоэффективности, но то, что заняли второе место исходя из требуемого нам сценария — неприемлемо. Решения из коробки помогут только для стандартных сценариев, потому что в случае продвинутых вариантов только вы сами можете учитывать нюансы требований и специфику своего приложения.
Дальше расположился основой пелотон участников, по энергоэффективности далеко оставивший позади GPS и обеспечивший достаточную точность. Обратите внимание — один из участников в принципе отказался от допинга GPS (Mylnikov Provider), а другие четверо, не считая самого GPS, воспользуются его данными, только если на смартфоне какое-то другое приложение потребует высокоточные координаты.

GPS, прощай?


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

Попробуйте отключить в настройках телефона GPS и откройте Яндекс.Карты — они определят ваше местоположение достаточно точно. Причем даже при выключенном Wi-Fi — только если в настройках не отключен скан Wi-Fi сетей (появился начиная с Android 4.3). Но у большинства пользователей он включен.
Откройте Google Maps — и ваше местоположение будет определено еще точнее. Поставьте себе какой-нибудь трекер Wi-Fi сетей и пройдитесь или проедьте по городу — ваш смартфон зацепит тысячи Wi-Fi сетей.

image
Попросили коммерческого директора поставить себе трекер Wi-Fi сетей на денек.

В зависимости от качества источника (Гугл или открытые базы) и рельефа города точность Wi-Fi составляет около 30-50 метров. Согласитесь, что это на порядок лучше, чем сотовые сети, у которых в городе точность не более 300-400 метров.
Для большинства приложений точность в 30-50 метров достаточна, и поэтому дергать всё сжирающий GPS совершенно не нужно. Когда по результатам некоторых длительных тестов на GPS-экземпляре оставалось 15% заряда, лучший соперник имел 57% заряда — почувствуйте разницу!

Так что с решением-то?


Конкретно для промышленной реализации выбран i402 — сейчас он используется в одной из мобильных рекламных сетей 3-го поколения (Хабр: Рекламные сети 3.0).
i402 — это, напомню, сочетание следующего:
  • получение закешированных системой обращений к GEO-данным от других приложений (в том числе и данные GPS, если какое-то другое приложение его включало)
  • явный запрос координат по Wi-Fi и/или по вышкам сотовой связи, если закешированные данные устарели
  • плавающая частота явного запроса в зависимости от удаленности пользователя от ближайшего радиуса

При стандартном использовании приложение со встроенным SDK, содержащим реализацию i402 и работающим непрерывно в режиме сервиса, отъедает за день в пределах 5% заряда батареи.
Для реализации адаптивности и интеллектуальности пришлось решить множество других интересных задач, таких как борьба с «телепортационностью» метро или «телепортационностью» аэропортов (ведь предсказать, где окажется через 30 минут вошедший в метро сложнее, чем сделать то же самое для автомобилиста, обычного зажатого пробками) и, скажем, придумать множитель значения периода актуализации координат в состоянии покоя. А также научиться без помощи прожорливых датчиков определять, идет человек пешком, едет на транспорте или на собственном авто. Но про это — в отдельном материале.

Комментарии (11)


  1. za90
    25.01.2016 21:01
    +1

    предсказать, где окажется через 30 минут вошедший в метро
    Не скажу за все метро (да вообще ни за какое не скажу), но во многих местах знаю уже есть покрытие сотовой связью. Не говоря уж о точках доступа Wi-Fi. Интересно возможно ли хоть какое-то позиционирование по таким данным? Там конечно не антенна+БС, а некий антенный кабель, но тем интересней!


    1. Randl
      25.01.2016 23:47

      За полчаса в Москве можно проехать примерно 10-12 станций, то есть оказаться практически где угодно. Значит повышаем частоту запросов. С другой стороны быстро из метро не выберешься. Если ты сейчас в поезде, то в ближайшие пару минут ты на поверхности не окажешься. Если ты только спустился, то у тебя есть минимум минут 5. Плюс, если ближайший радиус в другом конце города, то быстро до него на метро не доберешься.
      Я бы хранил примерное время от станции до станции и считал бы время t, за которое можно добраться до ближайшего радиуса. И делал бы явный запрос раз в max(t/2, 5) минут.


      1. 100chuk
        26.01.2016 12:22

        Я бы хранил примерное время от станции до станции и считал бы время t, за которое можно добраться до ближайшего радиуса. И делал бы явный запрос раз в max(t/2, 5) минут.

        Огрублено примерно так всё и работает, что-то принципиально новое сложно придумать. Но max(t/2, 5) — это слишком часто, батарея начнет ощутимо просаживаться. В базовом варианте нам удалось добиться всего нескольких десятков проверок координат в день для среднестатистического пользователя.


      1. Disasm
        26.01.2016 21:07
        +1

        На самом деле станции и пересадки можно отлично детектировать по изменению магнитного поля, для этого даже дополнительных прав не нужно.


    1. justmara
      26.01.2016 12:29

      … и по этому самому «антенному кабелю» меня вечно на перегоне Проспект Мира — Новослободская телепортирует в Питер. А Новослободская-Белорусская вечно говорит мне, что я проезжаю Нагатинский метромост. А где-то в районе Нагатинской, емнип, ещё недавно была смешная БС, которая считала, что она в Карелии… Ну, т.е. базы геолокации считали, что она там. Что у гугла, что у here maps.
      Позиционирование по бс в метро — оно такое.


    1. unwrecker
      26.01.2016 15:12
      +2

      А слабо распознавать названия станций, которые объявляют в поезде? :)


      1. 100chuk
        26.01.2016 15:24

        Это можно. А еще есть схожая технология по локации внутри ТЦ по записи на микрофон неслышимых человеческому уху звуков из динамиков. Насколько помню где-то в Азии такое внедряли.


  1. 100chuk
    26.01.2016 12:21

    Интересно возможно ли хоть какое-то позиционирование по таким данным?

    Да, возможно. Собственно тот же Яндекс.Метро нормально определяет текущую станцию. В открытых базах можно найти даже конкретные идентификаторы точек, установленных в метро.


  1. AndrewTishkin
    26.01.2016 14:19

    А у iOS по части навигации как, всё печально?


    1. 100chuk
      28.01.2016 13:09
      +1

      Да, ограничений больше — но Андроид тоже движется в направлении ужесточения правил игры. В наших планах есть аналогичные тесты и на комплектах iPhone.