1. ВведениеGPS обладает высокой точностью позиционирования и уже давно является стандартом для мобильных устройств, но у GPS есть и некоторые непреодолимые недостатки, в том числе:
-
Долгий холодный пуск. Когда GPS запускается, ему необходимо найти спутники, зафиксировать спутниковые сигналы, а затем выполнить технологию определения местоположения.Этот процесс может занять десятки секунд.Даже если используются такие технологии, как AGPS, все еще есть секунды, которые не могут быть определены.
-
В помещении или закрытых сценах. Сигнал GPS слабый и не может быть эффективно позиционирован.
Пользователям необходимо непрерывное и эффективное позиционирование, поэтому в дополнение к GPS необходима еще одна технология — технология сетевого позиционирования.
Сетевое позиционирование заключается в отправке сигнала (в основном базовой станции, Wi-Fi, Bluetooth), полученного мобильным телефоном, на сетевой сервер для определения местоположения. Причина, по которой данные сигнала отправляются в сеть, заключается в том, что сетевое позиционирование использует отпечатки сигналов для позиционирования, что требует огромной и постоянно обновляемой базы данных отпечатков пальцев, которую сложно синхронизировать с мобильными устройствами. Чтобы выполнить позиционирование, необходимо заранее установить характеристики отпечатков пальцев каждой позиции, а затем использовать отпечатки пальцев в реальном времени для сравнения исторических отпечатков пальцев каждой позиции во время позиционирования, чтобы определить положение.
Сетевое позиционирование AutoNavi не только выполняет запросы позиционирования пользователей карт AutoNavi, но также предоставляет услуги всем основным производителям мобильных телефонов в Китае, а также более 300 000 внутренних приложений со средним ежедневным запросом на обработку 100 миллиардов раз и пиковым числом запросов в секунду. из одного миллиона.
За последние несколько лет алгоритм сетевого позиционирования AutoNavi претерпел эволюцию от неконтролируемого алгоритма к контролируемому алгоритму и значительно улучшился с точки зрения точности позиционирования и возможностей позиционирования.
Примечание: сетевое позиционирование AutoNavi существует только на платформе Android.На iOS, поскольку Apple не публикует никаких данных об отпечатках пальцев, связанных с позиционированием (Wi-Fi, список базовых станций и т. д.), все результаты позиционирования берутся из самой iOS.
2. Алгоритм без учителя, основанный на кластеризацииКлассический алгоритм позиционирования отпечатков пальцев — это неконтролируемый алгоритм, ядром которого является вычисление сходства отпечатков пальцев и использование отпечатков пальцев для определения местоположения. На рисунке ниже приведен пример.Точка доступа представляет номер базовой станции и устройства Wi-Fi, отсканированный мобильным телефоном.Вертикальная ось представляет различные положения.Значение пересечения двух точек представляет мощность сигнала точки доступа,отсканированного в этом положении. Если оно пустое, значит, позиция не сканировалась.
Чтобы найти новый периодический запрос (например, AP1:-30, AP2:-50, AP3:-90), самый простой метод — использовать KNN для вычисления сходства между отпечатком пальца и историческим отпечатком один за другим (например, L2). расстояние или косинусное сходство), возьмите историческое местоположение с наибольшим сходством в качестве местоположения пользователя.
Есть две проблемы: во-первых, объем вычислений слишком велик (AP порядка 1 миллиарда, а loc порядка 100 миллиардов), что не может удовлетворить требованиям позиционирования в реальном времени. заключается в том, что исторические отпечатки пальцев могут быть относительно редкими локально. Для отпечатков пальцев пользователя точное совпадение невозможно.
Следовательно, необходимо предварительно обработать исторические данные, чтобы извлечь общие отпечатки точек доступа и сетей, чтобы при позиционировании требовалось только одно сравнение. На следующем рисунке показан процесс использования исторического местоположения сбора точек доступа для кластеризации для получения фактического местоположения и радиуса покрытия точки доступа. Точки доступа во время позиционирования.
Одна из проблем, которую должен решить этот метод, заключается в том, как выбрать, когда есть несколько позиций-кандидатов, как показано на рисунке ниже, есть две позиции-кандидаты.
В настоящее время необходимо разработать стратегию выбора кластера, оценить на основе характеристик каждого кластера и найти наиболее вероятный кластер в качестве местоположения пользователя.
Позиционирование на основе средневзвешенного очень быстрое, но точность относительно низкая.Причина в том, что пространственное распределение отпечатков пальцев не является непрерывным и может зависеть от зданий, местности и дорог, показывая неравномерное распределение, поэтому выше. На основе метода позиционирования разработан алгоритм, основанный на сортировке по сетке, который позволяет более точно определять местоположение.
Сначала земля делится на сетки 25*25, затем подсчитываются особенности отпечатков пальцев в каждой сетке и, наконец, сетка сортируется. Пусть сетка-кандидат равна l, а вектор сигнала равен S, процесс позиционирования заключается в вычислении
По формуле Байеса имеем
Согласно 1-1, поскольку все сетки-кандидаты имеют одинаковый знаменатель, необходимо вычислить только числитель, а именно:
Среди них P(l) — это вероятность появления определенной позиции во всех пользовательских позициях, которая может быть выражена позиционированием PV, а P(S=S0|l) необходимо вычислить вероятность появления определенного сигнального вектора в каждой позиции пользователя. сетки, Из-за большой размерности вектора вероятность трудно вычислить, поэтому делаются независимые предположения для разных размерностей, а вероятность каждого сигнала считается независимой. имеют:
Таким образом, мощность сигнала каждой точки доступа в каждой сетке может быть подсчитана на гистограмме на основе исторического отпечатка пальца, и может быть рассчитана вероятность Наконец, вероятность всех сеток может быть отсортирована, чтобы получить ту, которая имеет наибольшую вероятность , как показано на следующем рисунке:
3. Контролируемые алгоритмы, основанные на иерархической сортировкеОдна из проблем неконтролируемых алгоритмов заключается в том, что их трудно повторять, и они не могут быть эффективно оптимизированы для плохих случаев.Как только стратегия будет скорректирована, она повлияет на другие случаи и не может обеспечить глобальный оптимум.
Таким образом, обучение с учителем стало очень необходимым. AutoNavi обратилась к обучению с учителем за последние два года и продолжила разработку функций и моделей для улучшения эффекта. Это добилось хороших результатов и устранило более 50% крупных ошибок. Проблема (более 5 километров), точность распознавания более 99% была получена при распознавании мобильного Wi-Fi.
В обучении с учителем необходимо использовать большое количество функций, а расчет функций должен потреблять больше ресурсов.Учитывая, что служба позиционирования должна выдерживать более 100 000 запросов в секунду, сложность модели так же важна, как и эффект.Поэтому мы первый слой службы позиционирования. Верхние слои предназначены для больших сеток, вычисляя приблизительные положения, а нижние слои — для малых сеток, постепенно уточняя положения. Это может значительно сократить ненужные вычисления и найти баланс между производительностью и эффективностью.
Для каждого отдельного модуля алгоритма модель нейронной сети, подобная следующей, используется для оценки каждой сетки-кандидата, а затем функция потерь LTR используется в качестве цели для обучения для получения параметров нейронной сети. С точки зрения характеристик рассмотрим одновременно следующие три категории:
-
Динамические характеристики точки доступа, такие как мощность сигнала
-
Характеристики сетки, такие как PV, UV, номер точки доступа, окружающие номера сетки-кандидата и т. д.
-
Особенности AP на сетке, такие как распределение интенсивности сигнала, PV, UV и т. д.
Этот метод может решить проблему неточного выбора большинства сеток.Одна из оставшихся проблем заключается в том, что когда баз позиционирования очень мало, например, есть только одна базовая станция и один Wifi, а два расположены в двух сетки, которые находятся далеко.На данный момент, независимо от того, какой из них вы выберете, существует 50% вероятность ошибиться. Чтобы решить эту проблему, мы вводим пользовательские исторические точки позиционирования, чтобы облегчить их выбор.
Добавьте последовательность исторических точек позиционирования в часть объекта, выведите объект исторического положения (который можно рассматривать как предсказанное новое положение) и позвольте этому предсказанному положению участвовать в оценке сетки. Взвешивание по прогнозируемому положению, когда есть две сетки, которые находятся далеко друг от друга, но близки по количеству очков. Таким образом, модель должна научиться такому правилу: если сетка находится далеко от предсказанного положения, то оценка будет ниже, а если ближе, то оценка будет выше. Благодаря этому методу доля случаев больших ошибок может быть уменьшена на 20%.
4. Сценарное позиционированиеУ пользователей разные требования к позиционированию в разных сценариях.Например, пользователям может потребоваться знать только приблизительное положение во время путешествия и не нужно быть очень точным, но при навигации им нужно точно знать, на какой дороге они находятся и расстояние до выхода.
Таким образом, в дополнение к оптимизации общей архитектуры алгоритма, AutoNavi также проводит целевую оптимизацию в различных конкретных сценариях для удовлетворения потребностей пользователей в позиционировании в различных сценариях.
внутренняя сцена
Одним из ограничений позиционирования отпечатков пальцев является то, что для обучения необходимо собирать образцы с помощью GPS.Поскольку GPS можно собирать только на открытом воздухе, даже если пользователь находится в помещении, результат позиционирования с высокой неудобство для пользователя Меньше проблем, особенно когда пользователь готов к поездке, дрейф точки позиционирования приведет к отклонению начальной точки от реального положения.
Чтобы решить эту проблему, есть два решения.Одно из них состоит в том, чтобы собрать реальную стоимость в помещении, но этот метод требует много ручной работы по сбору данных, а рабочая нагрузка огромна.В настоящее время AutoNavi проводит ручной сбор отпечатков пальцев в некоторых популярных торговых точках. торговые центры и транспортные узлы (кроме базовой станции Wi-Fi. Также поддерживает Bluetooth, датчик позиционирования). Второй метод заключается в использовании больших данных без ручного вмешательства для выполнения ассоциации здания/POI в сети Wi-Fi и использования местоположения здания/POI для корректировки результата позиционирования.
Существует множество методов сопоставления Wifi и POI. Простой метод — использовать сходство между названием POI и именем Wi-Fi, чтобы определить, существует ли взаимосвязь. Например, название сети Wi-Fi сети McDonald's — McDonald's. , китайский и английский, прописные и строчные буквы, а также сокращения на китайском и английском языках. Подождите. Ведь мало найдется Вифи, которые могут анализировать отношения по имени. Другой метод с более сильным покрытием — использовать закон распределения сигналов Wi-Fi для определения реального местоположения Wi-Fi, ведь большая часть Wi-Fi развернута в помещении.
Здесь мы используем метод CNN, чтобы нарисовать данные о строительных блоках, данные POI и собранные наземные данные в двумерное изображение, а затем выполнить многоуровневые сверточные вычисления.Метка — это реальная область строительных блоков, где находится Wi-Fi. . Синий блок на рисунке ниже — это строительный блок, зеленый — это точка сбора, чем ярче цвет, тем выше уровень сигнала, а красная точка представляет реальное местоположение Wi-Fi.
В настоящее время алгоритм может раскопать реальное местоположение, соответствующее 30% Wi-Fi.В конечном эффекте позиционирования, когда пользователь находится в помещении, доля образцов, которые могут быть правильно расположены в помещении, увеличилась на 15%.
Сцена высокоскоростной железной дороги
Судя по отчетам пользователей об ошибках, сообщается о большом количестве ошибок из-за неправильного позиционирования, когда пользователи садятся на высокоскоростную железную дорогу. За последние два года высокоскоростная железная дорога открыла бортовой Wi-Fi. Эти Wi-Fi являются мобильными Wi-Fi, поэтому эти точки доступа не имеют фиксированного местоположения. Если обработка не выполняется, Wi-Fi местоположение, полученное при обучении алгоритма, должно быть неверным, и есть большая вероятность, что оно будет расположено по пути Определенная станция (концентрация пользователей, большой объем сбора).
Для этого сценария необходимо удалить все мобильные Wi-Fi перед позиционированием. Мы разработали алгоритм майнинга мобильного Wi-Fi для высокоскоростных железных дорог и обычных сценариев, используя такие функции, как пространственно-временное распределение точек сбора, чтобы определить, движется ли Wi-Fi.Точность майнинга и скорость отзыва превышают 99%, что может решить большинство ошибок позиционирования высокоскоростных рельсов.
сцена в метро
Сцена в метро чем-то похожа на высокоскоростную железную дорогу.Wi-Fi, который сканируют пользователи, в основном является мобильным Wi-Fi (несколько станций имеют фиксированный Wi-Fi), поэтому их можно позиционировать только с помощью базовых станций. Однако базовая станция находится глубоко под землей, и данные о ней отсутствуют.Как узнать реальное местоположение базовой станции? Мы приняли две стратегии, первая стратегия заключается в использовании информации о соседних базовых станциях, когда пользователь сканирует как базовые станции метро (без сбора данных GPS), так и базовые станции других городов (с сбором данных GPS) за один запрос или за короткий период времени. time , мы можем использовать последнее положение для расчета первого положения, конечно, положение базовой станции, полученное таким образом, не очень точное. Поэтому мы провели дальнейшую оптимизацию, используя траекторию пользователя, чтобы точно откопать станцию метро, соответствующую каждому запросу, чтобы построить истинное значение, соответствующее отпечатку пальца.
Основываясь на вышеуказанных методах, точность позиционирования в метро может достигать более 90%, а также могут быть реализованы объявления станций метро и напоминания о пересадке.
5. Будущая эволюцияВ будущем технологии позиционирования, особенно технологии позиционирования мобильных устройств, будут развиваться быстрыми темпами.Основные прорывы могут произойти в следующих аспектах:
Позиционирование изображения: Google выпустила позиционирование AR на основе просмотра улиц, которое может решить точное позиционирование в городских районах каньона. Это позиционирование использует более богатые источники данных и значительно улучшит взаимодействие с пользователем.
Позиционирование 5G: по сравнению с 4G, 5G имеет более высокую частоту, более широкую полосу частот и более высокую точность при использовании для измерения дальности (например, использование разности фаз для расчета времени передачи). Отраслевые ассоциации также разрабатывают стандарты, связанные с позиционированием 5G. Он может поддерживать позиционирование на основе сети 5G, и эффект позиционирования будет аналогичен точности GPS в зоне покрытия 5G.
Позиционирование IoT: с ростом популярности Интернета вещей технология позиционирования, основанная на NB-IOT, также будет появляться, как того требует время.Он может использовать методы, аналогичные позиционированию базовой станции, или использовать методы позиционирования P2P для обнаружения устройств IoT.