A helymeghatározás a gps nélkül, ahogyan az op
Most több mobilalkalmazás válik földrajzilag függővé. Egyesek egyszerűen nincs értelme a felhasználó helyének ismerete nélkül, mások kényelmesebbé teszik. Ez az úgynevezett Location Based Services (LBS): navigátorok Foursquare, instagramy geotagged fotókat, sőt alkalmazása emlékeztetők kiváltó néhány konkrét helyen, például közel az irodában vagy boltban.
A Yandex szolgáltatások és alkalmazások esetében létrehoztuk a helymeghatározás módjának saját megvalósítását GPS nélkül - Yandex.Locator. A felhasználó időt takarít meg, és alkalmazásaink egy kicsit okosabbak. A Navigátorban és a Térképben elkerülheti az útvonal kiindulási pontjának megadását, még akkor is, ha egy fedett parkolóban tartózkodik. És ha kiválasztja a filmet a filmes poszterben vagy egy terméket a mobil piacon, segít rögtön megmutatni, hol találhatja őket a város területén. Nos, persze, ha kávézókat és ATM-ket keresel - lehetővé teszi, hogy azonnal mutasd meg, amikor a metróban vagy.
Régóta felfedeztük a technológiát szabad API formájában. Ma szeretnénk elmondani, hogyan működik.
Miért nincs GPS és hogyan
A világban számos megvalósítás létezik egy ilyen kombinált földmérési módszerről. És úgy tűnik, az első kérdés, amellyel minden fejlesztő találkozott, hol szerezhet információt a Wi-Fi hálózatok és a mobil tornyok helyéről?
Hálózati helyadatbázis
A "vásárlás vagy létrehozás" dilemmáján végül az utóbbi választottuk. A fő oka az, hogy sokkal könnyebb az eredmény minőségének ellenőrzését a saját adataival és algoritmusainkkal. Az információgyűjtésben a mobil Yandex.Maps felhasználók segítettek.
A személy, hogy részt vegyen ilyen crowdsourcing semmi különös csinálni nem szükséges - csak használja az alkalmazást. A koordináták mellett a környező Wi-Fi hálózatok és a GSM állomások adatai is személytelenek. Gyakorlatilag nem "súlyoznak" semmit, és az átvitelükből származó akkumulátor tehát nem ül le gyorsabban.
Az adatbázis gyűjtése és rendszeres frissítése. És itt van a következő probléma.
A hálózatok "mozgatása"
A tapasztalat azt mutatja, hogy a mobil tornyok identitása folyamatosan változik - a város központjában tegnapi szám, holnap a külvárosban lehet. A Wi-Fi routerek is mozoghatnak - a tulajdonosokkal együtt. És kiderül, hogy minden lépésnél jelentős mennyiségű adatot kell letiltani.
Így sikerült egyszerre megoldanunk a mozdulattal és tornyokkal, valamint a routerekkel kapcsolatos problémákat. A felhasználó megkapja a kérést, hogy meghatározza a helyet és az általa látott hálózatot. Ha a hálózatok listája a város különböző részein látható, akkor az algoritmus figyelembe veszi, hogy hány jelet gyűjtenek össze az egyes régiókban és az utóbbi korában. A Wi-Fi hálózatok vagy a mobil torony minden sűrű klaszterét "felhőnek" nevezik. Minél több jel van a felhőben és annál frissek, annál megbízhatóbb. A válasz a legnagyobb és a legfrissebb. Olyan felhő, amely több mint egy hónapig nem jelzi a jeleket, elavultnak tekintjük - még akkor is, ha erre a hálózatra nincs friss felhő egy másik területen.
Felhő sugár
Mivel a pozíciót megközelítőleg határozzák meg, nem mutathatja meg a pontot - kör kell rajzolni (mert a rádiójelet az interferencia hiányában minden irányban egyenletesen osztják el). Bár a jelek tényleges képét tekintve, leggyakrabban ellipszis. Végül is a mobil autók használják a legtöbb mobil kártyát. A GPS nyomok továbbra is az utakon maradnak, és az udvarokból, sőt, a jelek épületéből gyakorlatilag nem érkeznek meg.
Ahhoz, hogy a válasz rendkívül pontos legyen, a kör sugarának minimálisnak kell lennie. Ha csak egy adott hálózat jelpontjait körbejárja, akkor a sugár túl nagy lesz. Csökkentése segített mat. Statisztika. A jelzések sűrűsége normális eloszlásnak van kitéve, vagyis a három sigma szabálya alkalmazható. E sugár közelében a pontok 99,7% -a csökken.
Úgy döntöttünk, hogy továbbmegyünk és kísérletileg kiválasztjuk a sigma-együtthatót, amely minimalizálja a sugarat, de megtartotta az elfogadható pontosságot. Ez sikerült, mert a legtöbb esetben a felhasználó több hálózatot lát. Vagyis a "területek", amelyek "nyitottak" a régió együtthatójának csökkentésével, valószínűleg átfedik más felhők.
Nem helyi jelek
Sajnos nem minden GPS-jelet használnak a felhőkben. Kiderült, hogy ha az egyes hálózatok összes jelét leképezi, akkor az "ellipszisek" mellett pontok és vonalak lesznek. Ezek egy jelek, amelyek távol vannak az ugyanazon hálózatból származó jelek felhalmozásától és nagyon hosszú GPS-sávoktól (azaz a GPS-jelek láncaitól).
Egyszeri jelek, kis felhők és hosszú sávok "zajnak" minősülnek. Ha egy felhasználó egyetlen hálózatot lát, amelyre csak ilyen jeleket ismerünk, akkor válasz érkezik arra, hogy a helyszínt nem lehetett meghatározni. Úgy véljük, hogy ez helyesebb, mint szándékosan rossz, becsléseink szerint.
Amikor az adatok kicsit felhalmozódtak, még egy nehézséget jelentett az összes jel egyetlen felhővé való kombinálásával. Ez történt, hogy a város tornyából érkező jelek is a másikból érkeztek. Segítettek nekünk a LAC (Location Area Code) kódnak a GSM hálózati azonosítóban. Mivel ugyanazzal a kóddal rendelkező tornyok közelednek a szabványhoz, a felhők, amelyek "nem a városukban" voltak (azaz a felhők között egy másik LAC-val), a Latitude kezdett alulbecsülni a súlyt.
A meghatározás pontosságának javítása ...
... GSM hálózatokon keresztül
... Wi-Fi hálózatokon keresztül
Az így kapott minőség
Először néhány szót arról, hogyan értékeljük megoldásunk minőségét. Mint korábban már említettük, azok a felhasználók, akik GPS-moduljukat használják eszközeikben, a Koordináták mind a koordinátákat, mind az olyan hálózatok listáját fogadja, amelyek az eszközöket látják. A minőség felméréséhez először egy közelítő helyet határoz meg, amely kizárólag ezekre a hálózatokra összpontosít. Ezután ellenőrizni fogja, hogy az igazi koordináták a felhasználótól a Locator által javasolt körhöz érkeztek-e.
Ezzel a technikával a következő adatokat kaptuk:
- a kérések 83% -a naponta, a hely helyes - az eszköz GPS-koordinátái elérik a Latitude nevű területet
- A jelek 14% -a - hibával:
- 7% - hiba kevesebb, mint 100 méter
- 5,6% - 100 méterről néhány kilométerre
- 1,4% - A kereső hibázik a városban
- a lekérdezések fennmaradó 3% -a megkapja a "Hely nem található" választ
Lehetőség van a jobb minőség elérésére? Igen. A módszer előnye, hogy az algoritmusok bizonyos érettségével elegendő több adatot gyűjteni a hely pontosabb meghatározásához. És ez elég egyszerű, mert a Wi-Fi hálózatok száma és alkalmazásaink száma növekszik.
De vannak technológiai korlátok:
Számítási volumen
A felhasználó gyors megválaszolásához előzetesen fel kell készülnie az egész válaszra, vagy legalábbis egy lényeges részre. Minden éjszaka egy elosztott számítástechnikai rendszerünkön alapuló klaszter összesíti a tegnap érkezett jeleket, felkészülve a "felhők" készítésére. A kérelem idején a Google Koordináták csak a megfelelő módon kombinálhatók. Így a "nyers jelek" terabájtja 1,5-2 GB készre válaszolt, amelyek könnyen beilleszthetők a memóriába. És a válaszkészítés szinte mindig 1 ms-ban illeszkedik, és a klaszterben lévő minden szerver képes ellenállni a 10 ezer RPS-nek.
És hogy a napi számítás időtartama nem nő lineárisan a GPS-jelek történetének növekedésével, a felhők "additivitását" értük el. Most elegendő csupán néhány mutatót tárolni minden egyes felhő esetében, és nem kell minden nap feldolgozni az egész régi történelmet.
A teljesebb válasz elkészítése kiderül, hogy hatástalan. Ha a hálózatok egyes kombinációit egy külön felhőbe csoportosítja, kombinációs robbanást kap. A kész válaszok mennyisége több megrendeléssel nő, és a hálózatok részleges egybeesése esetén még több számításra van szükség a válasz előkészítéséhez.
Szolgáltatások helyzete GPS nélkül, ahogy mondtuk, nem csak a Yandex. A fejlesztők kapcsolatba léphetnek egy kereskedelmi céggel (például az oroszországi Altergeo-val és a Skyhook Wireless-tel a világon), vagy használhatják a mobil platform vagy böngésző API-ját.
Általában háromféle módon gyűjthet ilyen adatbázist:
- megkerülni az érdekes városokat az autókon, letapogatni a hálózatokat, majd rendszeresen újra körbejárni az alap frissítését
- hozzon létre tömeges mobilalkalmazást (például Yandex.Maps)
- hozzon létre egy mobil platformot (például iOS vagy Android)
De a különböző megoldások közötti választás csak a georefüggő alkalmazás fejlesztőjétől függ, és a felhasználó "él" ezzel a választással. Egyetlen összehasonlítási módszer hiányában figyelmet kell fordítani a meghatározás pontosságára (a "tűrés" sugara és a hibák százalékos aránya) az érintett régiókban.
Igaz, a fejlesztõ nem mindig választhat. Az iOS és WindowsMobile rendszereken az alkalmazás csak az operációs rendszerbe beépített földrajzi definíciókat tudja használni. Az alkalmazás nem rendelkezik hozzáféréssel az aktuális bázisállomáshoz és / vagy az aktuálisan kívüli WiFi hálózatok listájához.
A webes szolgáltatások másik helyzete. Minden modern böngésző beépített georeferencia API-val rendelkezik. A böngésző módosításával a felhasználó megváltoztatja a földrajzi meghatározót. A Firefox és a Google Chrome, a végrehajtás a Google, a Safari - az Apple, az IE - a Microsoft. A keresőnk a Yandex böngészőben működik.