В настоящее время все больше мобильных приложений становятся геозависимыми.
Некоторые просто не имеют смысла без знания местоположения пользователя, а другим становится удобнее.
Это так называемые Location Based Services (LBS): навигаторы, четыре квадрата, инстаграмы с геотегированными фотографиями и даже приложения-напоминалки, которые срабатывают возле определенной локации, например, рядом с офисом или магазином.
Для сервисов и приложений Яндекса мы создали собственную реализацию метода определения местоположения без GPS — Яндекс.
Локатор .
Это экономит время пользователя и делает наши приложения немного умнее.
В «Навигаторе» и «Картах» это избавляет от необходимости вводить начальную точку маршрута, даже если вы находитесь в гараже.
А при выборе фильма в Кинотеатре Афиша или товара в мобильном Маркете помогает сразу показать, где их найти именно в вашем районе города.
И, конечно же, при поиске кафе и банкоматов позволяет сразу показать ближайшие, даже когда вы находитесь в метро.
Мы технологии открылся давным-давно как бесплатный API. Сегодня мы хотим рассказать вам, как это работает.
Почему без GPS и как еще
Системы спутниковой навигации ( ГНСС ), в нашем случае это GPS и ГЛОНАСС, самый точный на сегодняшний день метод геоопределения.Соответствующие модули есть практически во всех современных смартфонах.
Но не всегда и не везде он может решить проблемы LBS. Во-первых, поиск спутников иногда занимает несколько минут, а бывают ситуации, в которых важна скорость определения даже с потерей точности.
Например, когда вам нужно построить предварительный маршрут в навигаторе или регистрироваться .
Во-вторых, спутники обычно не «видны» в помещении или под землей.
В-третьих, не в каждом мобильном телефоне или планшете есть модули GPS, а в ноутбуках их почти нет. То есть LBS нужны альтернативы.
И, конечно, есть альтернативы — определить свое местоположение можно по близлежащим вышкам GSM, сетям Wi-Fi и даже по IP-адресу.
Точность каждого из этих методов намного хуже, чем у GPS. Но если их объединить, они вместе дают приемлемое качество.
При этом некоторые недостатки одного нивелируются возможностями другого.
Вышки GSM есть почти везде, но сетей Wi-Fi нет. При этом по Wi-Fi точность определения лучше.
Поэтому комбинированный метод по полноте и точности лучше, чем каждый метод в отдельности.
Менее известный факт: два маршрутизатора в разных частях города могут иметь один и тот же MAC-адрес.
Объединение GSM и Wi-Fi решает такие коллизии.
У этих роутеров рядом скорее всего будут стоять вышки с разными идентификаторами — ведь вероятность совпадения внутри квартала гораздо меньше, чем по всему городу.
В мире существует несколько реализаций этого комбинированного метода геоопределения.
И кажется, первый вопрос, с которым сталкиваются все разработчики, — где взять информацию о местонахождении сетей Wi-Fi и вышек сотовой связи?
База данных сетевых расположений
В дилемме «покупать или строить» мы в конечном итоге выбрали последнее.Основная причина в том, что имея собственные данные и алгоритмы, гораздо проще контролировать качество результата.
Собирать информацию нам помогали пользователи мобильных Яндекс.
Карт. Когда мы начали развивать «Локатор», на улицах города уже были сотни тысяч людей с включенными «Яндекс.
Картами» на телефонах.
С согласия пользователя приложение постоянно передает его GPS-координаты — на основе этой информации строится Яндекс.
Трафик.
Мы подумали, что при этом приложение могло бы отметить, какая базовая станция обслуживает телефон по этим координатам, какие сети Wi-Fi видны (при этом, конечно, не подключаясь к самим сетям - чтобы не создавать риски конфиденциальности).
).
Чтобы участвовать в таком краудсорсинге, человеку не нужно делать ничего особенного – достаточно воспользоваться приложением.
Как и координаты, данные об окружающих сетях 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 метров
Объемы вычислений
Чтобы быстро ответить пользователю, нужно заранее подготовить весь ответ или хотя бы значительную его часть.Каждую ночь кластер на базе нашей распределенной вычислительной системы ЯМР агрегирует сигналы, полученные до вчерашнего дня, получая «облака», готовые к ответу.
На момент запроса Локатору остаётся только правильно их объединить.
Таким образом, терабайты «сырых сигналов» сжимались в 1,5-2 ГБ готовых ответов, которые легко помещаются в память.
А подготовка ответа почти всегда занимает 1 мс, а каждый сервер в кластере может обрабатывать 10 тысяч RPS. А чтобы продолжительность суточного расчета не росла линейно с ростом истории сигналов GPS, мы добились «аддитивности» облаков.
Теперь достаточно хранить всего несколько индикаторов для каждого облака, и нет необходимости каждый день переобрабатывать всю старую историю.
Подготовка более полного ответа оказывается неэффективной.
Если сгруппировать каждую комбинацию сетей в отдельное облако, получится комбинаторный взрыв.
Объем готовых ответов вырастает на несколько порядков, а при частичном совпадении сетей подготовка ответа требует еще больше вычислений.
Аналоги
Сервисы определения местоположения без GPS, как мы уже говорили, доступны не только у Яндекс.Разработчики могут обратиться к коммерческому поставщику (например, к Альтергео в России Скайхук Беспроводной в мире) или использовать мобильную платформу или API браузера.
В целом собрать такую базу данных можно тремя способами:
- разъезжать по интересующим городам на машинах, сканируя сети, а потом периодически снова разъезжать для обновления базы
- создать массовое мобильное приложение (например, Яндекс.
Карты)
- создать мобильную платформу (например, iOS или Android)
При отсутствии единой методики сравнения необходимо обращать внимание на точность определения (радиус «допуска» и процент ошибок) в интересующих регионах.
Правда, разработчик не всегда может выбирать.
На iOS и Windows Mobile приложение может использовать только встроенные в операционную систему функции геоопределения.
Приложение там не имеет доступа к текущей базовой станции и/или списку сетей Wi-Fi, кроме текущей.
В веб-сервисах ситуация иная.
Встроенный во все современные браузеры API геоопределения .
А сменив браузер, пользователь меняет геоидентификатор.
Firefox и Google Chrome используют реализацию Google, Safari использует реализацию Apple, а IE использует реализацию Microsoft. Наш Локатор работает в яндекс браузер .
Теги: #Разработка мобильных приложений #GNSS #Геоинформационные услуги #GPS #геолокация #lbs
-
Лицензирование Программного Обеспечения
19 Oct, 24 -
Как Часто Вы Пользуетесь Такси?
19 Oct, 24 -
Opera 9.5 – Официальный Релиз
19 Oct, 24 -
О Бесполезности Компьютерных Игрушек
19 Oct, 24 -
Думать По-Другому!
19 Oct, 24
