Сейчас всё больше мобильных приложений становятся геозависимыми. Одни просто не имеют смысла без знаний о местоположении пользователя, другие становятся с ним удобнее. Это так называемые Location Based Services (LBS): навигаторы, форскверы, инстаграмы с геотегами фотографий и даже приложения-напоминалки, которые срабатывают около конкретного места, например, рядом с офисом или магазином.
Для сервисов и приложений Яндекса мы создали собственную реализацию метода определения местоположения без GPS — Яндекс.Локатор. Он экономит время пользователя и делает наши приложения чуточку умнее. В Навигаторе и Картах она избавляет от ввода начальной точки маршрута, даже если вы на крытой парковке. А при выборе фильма в Киноафише или товара в мобильном Маркете помогает сразу показать, где их найти именно в вашем районе города. Ну и, разумеется, при поиске кафе и банкоматов — позволяет показывать вам сразу ближайшие, даже когда вы в метро.
Технологию мы давно открыли в виде бесплатного API. Сегодня хотим рассказать, как она устроена.
Почему без GPS и как иначе
Спутниковые системы навигации (GNSS), в нашем случае это GPS и ГЛОНАСС, — самый точный на сегодняшний день метод геоопределения. Соответствующие модули есть практически во всех современных смартфонах. Но не всегда и не везде он может решить задачи LBS.
Во-первых, поиск спутников иногда занимает несколько минут, а бывают ситуации, в которых скорость определения важна даже с потерей точности. Например, когда нужно построить предварительный маршрут в навигаторе или зачекиниться. Во-вторых, спутники обычно не «видны» в помещениях или под землёй. В-третьих, GPS-модули есть не в каждом мобильном телефоне или планшете, и их почти нет в ноутбуках. То есть для LBS нужны альтернативы.
И альтернативы, конечно, есть — определять местоположение можно по ближайшим GSM-вышкам, сетям Wi-Fi и даже по IP-адресу. Точность определения у каждого из этих способов гораздо хуже, чем у GPS. Но если их скомбинировать, они вместе дадут приемлемое качество. При этом какие-то недостатки одного нейтрализуются возможностями другого. GSM-вышки есть практически везде, а Wi-Fi сети — нет. При этом по Wi-Fi точность определения лучше. Поэтому комбинированный способ по полноте и точности лучше, чем каждый в отдельности. Менее известен факт, что у двух роутеров в разных частях города может оказаться одинаковый MAC-адрес. Совмещение GSM и Wi-Fi решает такие коллизии. У этих роутеров, скорее всего, рядом будут находиться вышки с разными идентификаторами — ведь вероятность совпадения в пределах квартала гораздо меньше, чем в масштабах всего города.
В мире есть несколько реализаций такого комбинированного способа геоопределения. И кажется, первый вопрос, с которым сталкивались все разработчики, — где же взять информацию о местоположении сетей Wi-Fi и сотовых вышек?
База местоположений сетей
В дилемме «купить или создать» мы в конечном счёте предпочли второе. Основная причина — что с собственными данными и алгоритмами гораздо легче контролировать качество результата. В сборе информации нам помогли пользователи мобильных Яндекс.Карт.
Когда мы начинали разрабатывать Локатор, на улицах городов были уже сотни тысяч людей с включёнными в телефонах Яндекс.Картами. С согласия пользователя приложение постоянно передаёт его GPS-координаты — на основе этой информации строятся Яндекс.Пробки. Мы подумали, что вместе с этим приложение может отмечать, какой базовой станцией обслуживается телефон в этих координатах, какие видны сети Wi-Fi (при этом, конечно, к самим сетям не подключаясь — чтобы не создавать privacy-рисков).
Человеку для участия в таком краудсорсинге ничего специально делать не нужно — просто пользоваться приложением. Как и о координатах, данные об окружающих Wi-Fi сетях и станциях GSM обезличены. Они практически ничего не «весят», и батарейка от их передачи, соответственно, быстрее не садится.
Таким образом, пользователи стали помогать друг другу:
Одни, с GPS-приёмником в телефоне, узнают точное расположение сетей и передают информацию в Яндекс. Другие, у которых GPS-модулей нет, присылают список сетей, которые видят в данный момент, и получают в ответ своё примерное местоположение на карте.
База собрана и регулярно обновляется. И тут мы сталкиваемся со следующей проблемой.
«Переезд» сетей
Опыт показывает, что идентификаторы сотовых вышек постоянно меняются — номер, который вчера был в центре города, завтра может оказаться на окраине. Переезжать могут и Wi-Fi-роутеры — вместе со своими владельцами. И получается, что с каждым переездом нужно инвалидировать заметную часть данных.
Вот как нам удалось решить одновременно проблемы с переездом и вышек, и роутеров. От пользователя поступает запрос на определение местоположения вместе с данными о том, какие сети он видит. Если в списке сетей есть та, что была замечена в разных частях города, алгоритм учитывает, сколько сигналов от неё накоплено в каждом районе и возраст последнего. Каждое плотное скопление сигналов от Wi-Fi сети или сотовой вышки мы называем «облаком». Чем больше сигналов в облаке и чем они свежее, тем больше оно заслуживает доверия. Ответом будет, соответственно, самое большое и свежее. А облако, в котором нет сигналов больше месяца, мы считаем устаревшим — даже если для этой сети не появилось более свежего облака в другом районе.
Радиус облака
Поскольку положение определяется примерно, нельзя показать точку — нужно нарисовать круг (ведь радиосигнал в отсутствие помех распределяется во все стороны равномерно). Хотя, если посмотреть на фактическую картину сигналов, чаще всего это эллипс. Ведь больше всего пользуются мобильными Картами автомобилисты. Их GPS-следы остаются на дорогах, а из дворов и, тем более, из зданий сигналов практически не поступает.
Чтобы ответ был предельно точным, радиус круга должен быть минимальным. Если просто обвести окружность вокруг всех точек сигналов конкретной сети, радиус получится слишком большим. Уменьшить его помогла мат. статистика. Плотность сигналов подвержена нормальному распределению, то есть применимо правило трёх сигм. В окрестность такого радиуса попадает 99,7% точек.
Мы решили пойти дальше и экспериментально подобрали сигме такой коэффициент, который максимально уменьшил радиус, но сохранил приемлемую точность. Удалось это, потому что в большинстве случаев пользователь видит несколько сетей. То есть «открытые» уменьшением коэффициента области, скорее всего, перекрываются другими облаками.
Необлачные сигналы
К сожалению, не все GPS-сигналы от пользователей просто скомпоновать в облака. Оказалось, что, если наложить на карту все сигналы отдельно взятой сети, помимо «эллипсов» на ней окажутся точки и линии. Это, соответственно, одиночные сигналы, сильно удалённые от скопления сигналов той же сети, и очень длинные GPS-треки (т.е. цепочки GPS-сигналов).
«Одиночки» появляются, например, когда человек передвигается на метро. Телефон теряет связь с сотой на одной станции, а при выходе на другой всё ещё считает, что обслуживается той сотой. Такие сигналы Локатор отфильтровывает. Кроме того, мы установили минимальный порог для облаков, чтобы не полагаться на слишком малочисленные скопления сигналов.
Длинные GPS-треки появляются, например, когда человек едет на машине через весь город. Телефон «тащит» за собой идентификатор вышки с начала маршрута и передаёт, что якобы видит её на всём пути. Известно, что у базовых станций ограниченный радиус действия, так что такие GPS-треки Локатор тоже отфильтровывает. Треки, длина которой укладывается в радиус действия вышки, остаются. Как правило, они заметны в районах, где мало данных. Там они становятся цепочкой небольших облаков.
Сигналы-одиночки, маленькие облака и длинные треки мы считаем «шумом». Когда пользователь видит одну единственную сеть, для которой нам известны только такие сигналы, он получает ответ, что местоположение определить не удалось. Мы считаем это более правильным, чем давать заведомо неверный, по нашим оценкам, результат.
Когда данных было накоплено мало, была ещё одна трудность с объединением всех сигналов в одно облако. Случалось что сигналы от вышки из одного города приходили также из другого. Помогло нам наличие в идентификаторах GSM-сетей кода зоны местоположения — LAC (Location Area Code). Поскольку вышки с одинаковым кодом должны по стандарту находиться рядом, облакам, которые оказались «не в своём городе» (т.е. среди облаков с другим LAC), Локатор стал придавать заниженный вес.
Улучшение точности определения…
…по GSM-сетям
Когда-то приложениям была доступна информация лишь об одной базовой станции, хоть телефон видит чаще всего несколько. После появления платформы Android приложения смогли научиться видеть их все (кроме подключения в стандарте 3G, который позволяет узнать только одну сотовую вышку). Местоположение стало определяться точнее — уже не по одному облаку, а по совокупности нескольких. Оказалось, что для множества облаков можно использовать тот же подход, что и для одного. Радиус считается по среднеквадратичному отклонению сигналов, входящих в совокупность облаков, а центр вычисляется по среднему их координат.
…по Wi-Fi-сетям
Когда смартфон находится в радиусе действия нескольких Wi-Fi-сетей, он может сообщить не только их список, но и мощность сигнала каждой. Знание об этой мощности мы и использовали для уточнения центра окружности, в которой находится пользователь. К центрам наблюдаемых облаков мы начали подвешивать воображаемые пружинки — тем туже, чем сильнее сигнал. А их свободные концы — соединять. Точка, в которой эти пружинки уравновешиваются, и есть уточнённый центр.
Получившееся качество
Сначала несколько слов о том, как мы оцениваем качество нашего решения. Как уже говорилось, от пользователей, у которых есть в устройствах GPS-модуль, Локатор получает и координаты, и список сетей, которые видят устройства. Для оценки качества он сначала определяет примерное местоположение, ориентируясь только на эти сети. А затем проверяет, попали ли истинные координаты от пользователя в предположенную Локатором окружность.
Используя эту методику, мы получили следующие цифры:
- для 83% запросов в сутки местоположение определено правильно — GPS-координаты устройства попали в область, названную Локатором
- 14% сигналов — с ошибкой:
- 7% — ошибка меньше 100 метров
- 5,6% — от 100 метров до нескольких километров
- 1,4% — Локатор ошибается городом
- оставшиеся 3% запросов получают ответ «Местоположение не найдено»
Можно ли добиться лучшего качества? Да. Преимущество метода в том, что при определённой зрелости алгоритмов достаточно лишь собирать больше данных, чтобы определять местоположение точнее. А это достаточно легко, потому что растёт и количество Wi-Fi сетей, и количество пользователей наших приложений.
Но есть технологические пределы:
- если телефон сообщает только об одной GSM-вышке — минимальный радиус составит несколько сотен метров в городе, и несколько километров за городом
- если телефон видит несколько вышек — центр можно определить точнее, но радиус уменьшить вряд ли получится
- если видна Wi-Fi сеть — минимальный радиус будет 10 метров
Объёмы вычислений
Чтобы быстро отвечать пользователю, нужно заранее подготовить весь ответ или, хотя бы, существенную часть. Каждую ночь кластер на базе нашей системы распределённых вычислений YAMR агрегирует сигналы, полученные вплоть до вчерашнего дня, получая готовые для ответа «облака». В момент запроса Локатору остаётся только правильным образом их скомбинировать. Так терабайты «сырых сигналов» сжались до 1.5-2 ГБ готовых ответов, которые запросто помещаются в память. И подготовка ответа почти всегда укладывается в 1 мс, а каждый сервер в кластере выдерживает 10 тыс. RPS.
А чтобы продолжительность ежесуточного расчёта не росла линейно с ростом истории GPS-сигналов, мы добились «аддитивности» облаков. Теперь достаточно хранить лишь несколько показателей на каждое облако, и не нужно каждые сутки заново обрабатывать всю старую историю.
Готовить более полный ответ оказывается неэффективно. Если кластеризовать каждую комбинацию сетей в отдельное облако, получается комбинаторный взрыв. Объём готовых ответов растёт на несколько порядков, а при частичном совпадении сетей на подготовку ответа нужно даже больше расчётов.
Аналоги
Сервисы определения местоположения без GPS, как мы уже говорили, есть не только у Яндекса. Разработчики могут обратиться к коммерческому поставщику (как, например, Altergeo в России и Skyhook Wireless в мире), либо использовать API мобильной платформы или браузера.
Вообще собрать такую базу можно тремя способами:
- объехать интересующие города на автомобилях, сканируя сети, а потом периодически объезжать заново, чтобы обновлять базу
- создать массовое мобильное приложение (например, Яндекс.Карты)
- создать мобильную платформу (например, iOS или Android)
Но выбирать между разными решениями приходится только разработчику геозависимого приложения, а пользователь «живёт» с этим выбором. В отсутствие единой методики сравнения нужно обращать внимания на точность определения (радиус «допуска» и процент ошибок) в интересующих регионах.
Правда, и разработчик может выбирать не всегда. На iOS и WindowsMobile приложение может пользоваться только встроенными в операционную систему функциями геоопределения. Приложению там недоступны текущая базовая станция и/или список WiFi-сетей, кроме текущей.
Другая ситуация в веб-сервисах. Во всех современных браузерах встроен API геоопределения. И меняя браузер, пользователь меняет геоопределитель. В Firefox и Google Chrome используется реализация Google, в Safari — Apple, в IE — Microsoft. Наш Локатор работает в браузере Yandex.
Автор: yurkennis
