Зараз все більше мобільних додатків стають геозалежні. Одні просто не мають сенсу без знань про місцезнаходження користувача, інші стають з ним зручніше. Це так звані Location Based Services (LBS): навігатори, Форсквер, інстаграми з геотеги фотографій і навіть програми-нагадування, які спрацьовують близько конкретного місця, наприклад, поруч з офісом або магазином.
Для сервісів і додатків Яндекса ми створили власну реалізацію методу позиціонування без GPS - Яндекс.Локатор. Він економить час користувача і робить наші програми трішки розумнішими. У Навігаторі і Картах вона позбавляє від введення початкової точки маршруту, навіть якщо ви на критій парковці. А при виборі фільму в кіноафіша або товару в мобільному Маркеті допомагає відразу показати, де їх знайти саме в вашому районі міста. Ну і, зрозуміло, при пошуку кафе і банкоматів - дозволяє показувати вам відразу найближчі, навіть коли ви в метро.
Технологію ми давно відкрили у вигляді безкоштовного API. Сьогодні хочемо розповісти, як вона влаштована.
Чому без GPS і як інакше
У світі є кілька реалізацій такого комбінованого способу геоопределенія. І здається, перше питання, з яким стикалися все розробники, - де ж взяти інформацію про місцезнаходження мереж Wi-Fi і стільникових веж?
База розташування мереж
У дилемі «купити або створити» ми в кінцевому рахунку віддали перевагу другому. Основна причина - що з власними даними і алгоритмами набагато легше контролювати якість результату. У зборі інформації нам допомогли користувачі мобільних Яндекс.Карт.
Людині для участі в такому Краудсорсінг нічого спеціально робити не потрібно - просто користуватися додатком. Як і про координати, дані про оточуючих Wi-Fi мережах і станціях GSM знеособлені. Вони практично нічого не «важать», і батарейка від їх передачі, відповідно, швидше не сідає.
База зібрана і регулярно оновлюється. І тут ми стикаємося з наступною проблемою.
«Переїзд» мереж
Досвід показує, що ідентифікатори стільникових веж постійно змінюються - номер, який вчора був в центрі міста, завтра може виявитися на околиці. Переїжджати можуть і Wi-Fi-роутери - разом зі своїми власниками. І виходить, що з кожним переїздом потрібно інвалідіровать помітну частину даних.
Ось як нам вдалося вирішити одночасно проблеми з переїздом і вишок, і роутерів. Від користувача надходить запит на визначення місцеположення разом з даними про те, які мережі він бачить. Якщо в списку мереж є та, що була помічена в різних частинах міста, алгоритм враховує, скільки сигналів від неї накопичено в кожному районі і вік останнього. Кожне щільне скупчення сигналів від Wi-Fi мережі або стільникового вишки ми називаємо «хмарою». Чим більше сигналів в хмарі і чим вони свіже, тим більше воно заслуговує на довіру. Відповіддю буде, відповідно, найбільше і свіже. А хмара, в якому немає сигналів більше місяця, ми вважаємо застарілим - навіть якщо для цієї мережі не з'явилося більше свіжого хмари в іншому районі.
радіус хмари
Оскільки положення визначається приблизно, можна показати точку - потрібно намалювати коло (адже радіосигнал за відсутності перешкод розподіляється на всі боки рівномірно). Хоча, якщо подивитися на фактичну картину сигналів, найчастіше це еліпс. Адже найбільше користуються мобільними Картами автомобілісти. Їх GPS-сліди залишаються на дорогах, а з дворів і, тим більше, з будівель сигналів практично не надходить.
Щоб відповідь була гранично точним, радіус кола повинен бути мінімальним. Якщо просто обвести коло навколо всіх точок сигналів конкретної мережі, радіус вийде занадто великим. Зменшити його допомогла мат. статистика. Щільність сигналів схильна до нормальному розподілу, тобто може бути застосовано правило трьох сигм. В околиця такого радіуса потрапляє 99,7% точок.
Ми вирішили піти далі і експериментально підібрали сигмі такий коефіцієнт, який максимально зменшив радіус, але зберіг прийнятну точність. Вдалося це, тому що в більшості випадків користувач бачить кілька мереж. Тобто «відкриті» зменшенням коефіцієнта області, швидше за все, перекриваються іншими хмарами.
Необлачние сигнали
На жаль, не всі GPS-сигнали від користувачів просто скомпонувати в хмари. Виявилося, що, якщо накласти на карту все сигнали окремо взятої мережі, крім «еліпсів» на ній виявляться точки і лінії. Це, відповідно, поодинокі сигнали, сильно віддалені від скупчення сигналів тієї ж мережі, і дуже довгі GPS-треки (тобто ланцюжка GPS-сигналів).
Сигнали-одинаки, маленькі хмари і довгі треки ми вважаємо «шумом». Коли користувач бачить одну єдину мережу, для якої нам відомі тільки такі сигнали, він отримує відповідь, що місце розташування визначити не вдалося. Ми вважаємо це більш правильним, ніж давати завідомо неправильний, за нашими оцінками, результат.
Коли даних було накопичено мало, була ще одна трудність з об'єднанням всіх сигналів в одне хмара. Траплялося що сигнали від вишки з одного міста приходили також з іншого. Допомогло нам наявність в ідентифікаторах GSM-мереж коду зони розташування - LAC (Location Area Code). Оскільки вишки з однаковим кодом повинні за стандартом перебувати поруч, хмарам, які виявилися «не в своєму місті» (тобто серед хмар з іншим LAC), Локатор став надавати занижений вагу.
Поліпшення точності визначення ...
... по GSM-мереж
... по Wi-Fi-мереж
вийшло якість
Спочатку кілька слів про те, як ми оцінюємо якість нашого рішення. Як вже говорилося, від користувачів, у яких є в пристроях GPS-модуль, Локатор отримує і координати, і список мереж, які бачать пристрою. Для оцінки якості він спочатку визначає зразкове місце розташування, орієнтуючись тільки на ці мережі. А потім перевіряє, чи потрапили справжні координати від користувача в припущенні локатор окружність.
Використовуючи цю методику, ми отримали наступні цифри:
- для 83% запитів на добу розташування визначено правильно - GPS-координати пристрою потрапили в область, названу локатор
- 14% сигналів - з помилкою:
- 7% - помилка менше 100 метрів
- 5,6% - від 100 метрів до кількох кілометрів
- 1,4% - Локатор помиляється містом
- залишилися 3% запитів отримують відповідь «Місцезнаходження, не знайдено»
Чи можна добитися кращої якості? Так. Перевага методу в тому, що при певній зрілості алгоритмів досить лише збирати більше даних, щоб визначати місцеположення точніше. А це досить легко, тому що зростає і кількість Wi-Fi мереж, і кількість користувачів наших додатків.
Але є технологічні межі:
обсяги обчислень
Щоб швидко відповідати користувачеві, потрібно заздалегідь підготувати весь відповідь або, хоча б, істотну частину. Щоночі кластер на базі нашої системи розподілених обчислень 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.