Determinarea locației fără GPS așa cum este aranjată de op

Acum, mai multe aplicații mobile devin geo-dependente. Unii pur și simplu nu au sens fără cunoașterea locului utilizatorului, alții devin mai confortabili cu acesta. Acestea sunt așa-numitele servicii bazate pe locație (LBS): navigatoare, forgheri, instagrame cu fotografii geografice și chiar aplicații de memento care funcționează în jurul unei anumite locații, de exemplu, lângă un birou sau un magazin.







Pentru serviciile și aplicațiile Yandex, am creat propria noastră implementare a metodei de determinare a locației fără GPS - Yandex.Locator. Salvează timpul utilizatorului și face aplicațiile noastre un pic mai inteligente. În Navigator și în Hărți Google evită intrarea în punctul de plecare al traseului, chiar dacă vă aflați într-o parcare interioară. Și atunci când alegeți un film în filmul poster sau un produs de pe piața mobilă, acesta vă arată imediat unde să-i găsiți în zona dvs. din oraș. Bineînțeles, când căutați cafenele și bancomate, vă permite să vă arătați imediat când vă aflați în metrou.

Determinarea locației fără GPS așa cum este aranjată de op

Am descoperit mult timp tehnologia sub forma unui API gratuit. Astăzi vrem să vă spunem cum funcționează.

De ce fără GPS și cum altceva

În lume există mai multe realizări ale unei astfel de metode combinate de determinare geografică. Și se pare că prima întrebare, cu care s-au confruntat toți dezvoltatorii, este locul unde puteți obține informații despre locația rețelelor Wi-Fi și a turnurilor mobile?

Baza de date pentru localizarea rețelei

În dilema "cumpărați sau creați", am ales ultima. Principalul motiv este că este mult mai ușor să controlați calitatea rezultatului cu propriile date și algoritmi. În colecția de informații am fost ajutați de utilizatorii de Yandex.Maps mobili.

Persoana care participa la astfel de aglomeratii nu are nevoie de nimic special pentru a face - foloseste doar aplicatia. Pe lângă coordonate, datele despre rețelele Wi-Fi înconjurătoare și stațiile GSM sunt impersonale. Practic, acestea nu "cântăresc" nimic, iar bateria din transmisia lor, în consecință, nu se așează mai repede.

Baza de date este colectată și actualizată periodic. Și aici ne confruntăm cu următoarea problemă.

"Mutarea" rețelelor

Experiența arată că identitatea turnurilor mobile se schimbă în mod constant - numărul care a fost ieri în centrul orașului, mâine poate fi la periferie. Routerele Wi-Fi se pot deplasa, de asemenea, împreună cu proprietarii lor. Și se dovedește că cu fiecare mutare trebuie să dezactivați o cantitate semnificativă de date.

Așa am reușit să rezolvăm simultan problemele cu mișcarea, turnurile și routerele. De la utilizator primește o solicitare de a determina locația împreună cu datele privind ce rețea vede. Dacă lista de rețele are una care a fost văzută în diferite părți ale orașului, algoritmul ia în considerare câte semnale din acesta sunt acumulate în fiecare regiune și vârsta acesteia. Fiecare cluster dens de semnale de la o rețea Wi-Fi sau un turn mobil este numit "nor". Cu cât mai multe semnale din nor și cu cât sunt mai proaspete, cu atât este mai de încredere. Răspunsul va fi cel mai mare și cel mai proaspăt. Un nor, în care nu există semnale mai mult de o lună, considerăm că este depășită - chiar dacă pentru această rețea nu mai există nori proaspeți într-o altă zonă.

Rază de raze

Deoarece poziția este determinată aproximativ, nu puteți arăta punctul - trebuie să desenați un cerc (deoarece semnalul radio în absența interferențelor este distribuit în mod egal în toate direcțiile). Deși, dacă vă uitați la imaginea reală a semnalelor, cel mai adesea este o elipsă. La urma urmei, mașinile mobile utilizează cele mai mobile carduri. Traseele lor GPS rămân pe drumuri, iar din curți și, mai mult, din clădirile semnalelor, practic nu ajung.

Pentru ca răspunsul să fie extrem de precis, raza cercului ar trebui să fie minimă. Dacă purtați cercuri în jurul tuturor punctelor de semnal dintr-o anumită rețea, raza va deveni prea mare. Reduceți-l ajutat mat. Statistici. Densitatea semnalelor este supusă unei distribuții normale, adică se aplică regula de trei sigma. În vecinătatea acestei raze, 99,7% dintre puncte se încadrează.

Determinarea locației fără GPS așa cum este aranjată de op






Determinarea locației fără GPS așa cum este aranjată de op

Am decis să mergem mai departe și să selectăm experimental coeficientul sigma, care a minimizat raza, dar a păstrat acuratețea acceptabilă. Acest lucru a reușit, deoarece în majoritatea cazurilor utilizatorul vede mai multe rețele. Adică, "zonele" care sunt "deschise" prin scăderea coeficientului regiunii sunt probabil suprapuse de alți nori.

Semnale non-locale

Din păcate, nu toate semnalele GPS de la utilizatori sunt aranjate pur și simplu în nori. Sa dovedit că, dacă cartografiați toate semnalele unei rețele individuale, în plus față de "elipse" pe ea vor fi puncte și linii. Acestea sunt, respectiv, semnale unice departe de acumularea de semnale din aceeași rețea și de piste GPS foarte lungi (de exemplu, lanțuri de semnale GPS).

Semnalele unice, norii mici și piste lungi sunt considerate "zgomote". Atunci când un utilizator vede o singură rețea pentru care știm doar astfel de semnale, el primește un răspuns că locația nu a putut fi determinată. Considerăm că acest lucru este mai corect decât să dăm un rezultat greșit în mod deliberat, conform estimărilor noastre.

Când datele s-au acumulat puțin, a existat încă o dificultate în combinarea tuturor semnalelor într-un singur nor. Sa întâmplat ca semnalele de la turnul dintr-un oraș să vină și din cealaltă. Prezența codului LAC (Code Area Area) în identificatorii rețelei GSM ne-a ajutat. Deoarece turnurile cu același cod ar trebui să fie aproape de standard, norii care s-au dovedit a fi "nu în orașul lor" (de exemplu, printre nori cu un alt LAC), Latitude a început să dea o greutate subevaluată.

Îmbunătățirea acurateței definiției ...

... prin rețelele GSM
... prin rețele Wi-Fi

Determinarea locației fără GPS așa cum este aranjată de op

Calitatea rezultată

În primul rând câteva cuvinte despre modul în care evaluăm calitatea soluției noastre. După cum sa menționat deja, de la utilizatorii care au un modul GPS în dispozitivele lor, Latitude primește ambele coordonate și o listă de rețele care văd dispozitivele. Pentru a evalua calitatea, aceasta determină mai întâi o locație aproximativă, concentrându-se doar pe aceste rețele. Apoi verifică dacă coordonatele reale au venit de la utilizator la cercul sugerat de Locator.

Determinarea locației fără GPS așa cum este aranjată de op

Folosind această tehnică, am obținut următoarele cifre:

  • pentru 83% din cererile pe zi, locația este corectă - coordonatele GPS ale dispozitivului au lovit zona numită Latitude
  • 14% dintre semnale - cu o eroare:
    • 7% - eroare mai mică de 100 de metri
    • 5.6% - de la 100 metri până la câțiva kilometri
    • 1,4% - Locatorul face o greșeală cu orașul
  • restul de 3% din interogări primesc răspunsul "Locația nu a fost găsită"

Este posibil să se obțină o calitate mai bună? Da. Avantajul metodei este că, cu o anumită maturitate a algoritmilor, este suficient să se colecteze mai multe date pentru a se determina locația mai precis. Și acest lucru este destul de ușor, deoarece numărul rețelelor Wi-Fi și numărul de utilizatori ai aplicațiilor noastre este în creștere.

Dar există limite tehnologice:

Numerele de calcul

Pentru a răspunde rapid la utilizator, trebuie să pregătiți în prealabil întregul răspuns sau, cel puțin, o parte esențială. În fiecare noapte, un cluster bazat pe sistemul nostru distribuit de calcul YAMR agregă semnale primite până ieri, pregătindu-se să răspundă la "nori". La momentul solicitării, Latitude rămâne numai în modul corect de a le combina. Astfel, terabiți de "semnale brute" s-au redus la 1,5-2 GB de răspunsuri gata, care se potrivesc cu ușurință în memorie. Iar pregătirea răspunsului se potrivește aproape întotdeauna în 1 ms, iar fiecare server din cluster poate rezista la 10 mii RPS.

Și că durata calculului zilnic nu crește liniar odată cu creșterea istoricului semnalelor GPS, am obținut "aditivitatea" norii. Acum este suficient să stocați doar câțiva indicatori pentru fiecare nor și nu aveți nevoie să procesați întreaga istorie veche în fiecare zi.

Pregătirea unui răspuns mai complet se dovedește a fi ineficientă. Dacă grupați fiecare combinație de rețele într-un nor separat, veți obține o explozie combinatorică. Volumul răspunsurilor rapide crește cu mai multe ordine, iar cu o coincidență parțială a rețelelor sunt necesare mai multe calcule pentru a pregăti un răspuns.

Locația serviciilor fără GPS, așa cum am spus, nu există numai Yandex. Dezvoltatorii pot contacta un furnizor comercial (cum ar fi Altergeo în Rusia și Skyhook Wireless din lume) sau pot utiliza API-ul unei platforme mobile sau al unui browser.

În general, puteți colecta o astfel de bază de date în trei moduri:

  • pentru a merge în jurul orașelor interesante pe mașini, scanarea rețelelor și apoi periodic pentru a merge din nou pentru a actualiza baza
  • creați o aplicație mobilă în masă (de exemplu, Yandex.Maps)
  • creați o platformă mobilă (de exemplu, iOS sau Android)

Dar alegerea între soluții diferite este necesară numai pentru dezvoltatorul aplicației geo-dependente, iar utilizatorul "trăiește" cu această alegere. În absența unei metodologii de comparare unice, trebuie acordată atenție exactității determinării (raza "toleranței" și procentului de erori) în regiunile de interes.

Este adevărat că un dezvoltator nu poate alege întotdeauna. În aplicațiile iOS și WindowsMobile, aplicația poate utiliza numai funcțiile de definire a geo-definiției încorporate în sistemul de operare. Aplicația nu are acces la stația de bază curentă și / sau la lista de rețele WiFi, altele decât cele actuale.

O altă situație în serviciile web. Toate browserele moderne au un API georeferențial încorporat. Și schimbând browserul, utilizatorul schimbă geo-determinantul. În Firefox și Google Chrome, implementarea Google, în Safari - Apple, în IE - Microsoft. Locatorul nostru funcționează în browser-ul Yandex.







Trimiteți-le prietenilor: