Platforma průmyslové spolupráce
CZ.1.07/2.4.00/17.0041
Název
WiFi lokalizace pro Android
Popis a využití
• use case využití WiFi
• výuka: programování pro Android
Jazyk textu
• český
Autor (autoři)
• Michael Rais
Oficiální stránka projektu:
• http://lasaris.fi.muni.cz/pps
Dostupnost výukových materiálů a nástrojů online:
• http://lasaris.fi.muni.cz/pps/study-materials-and-tools
Obsah
1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Metody lokalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1 GNSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 INS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 WiFi lokalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1 Radar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Horus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Compass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 Srovnání systémů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Implementace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1 ScanningEngine (Offline fáze) . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 SearchingEngine (Online fáze) . . . . . . . . . . . . . . . . . . . . . . 21
5 Testování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1 Průběh testování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Výsledky testování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6 Závěr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
vi
Kapitola 1
Úvod
Již od pradávna pociťuje lidstvo potřebu nalezení cesty z bodu A do bodu B. Prvními
milníky lidstva bylo plné objevení celé planety a zavedení obchodních cest do map. Ještě
před pár desítkami let jsme se řídili pomocí map, kompasu, buzoly či slunce. K tomu bylo
třeba mít jistou dávku smyslu pro orientaci. S příchodem informačních technologií tuto
úlohu částečně přebraly počítače, kdy se spuštěním internetu v 70. letech minulého století
byly mapy dostupné prakticky kdykoliv a kdekoliv. Dalším důležitým milníkem byl rok
1973, kdy byl započat vývoj systému GPS (Global Positioning System). Od jeho uvedení
do provozu (80. léta) [13] navigaci plně převzaly počítače, a to od distribuce (aktualizace)
map po samotné vypočítávání trasy.
Roku 2007 byly představeny první tzv. chytré telefony (smartphones). Jejich příchod
znamenal velký posun ve světě mobilních zářízení. Do této doby bylo nemyslitelné, aby lidé
mohli být 24 hodin denně připojeni na internet, využívat jeho možnosti a protokoly (např.
SMTP, FTP a další) a přitom být mobilní. Díky výbavě, kterou dostaly chytré telefony
(GPS modul, senzory pro inerciální navigaci), je můžeme používat i k navigaci.
S dnešním rozrůstajícím se světem roste potřeba navigace pro interiéry (např. pro nalezení
cesty na úřadech, kampusech, nemocnicích atd). Nicméně systém GPS lze efektivně
využívat pouze v exteriérech, jak bude popsáno v kapitole 2.1. Proto byly navrženy systémy
jiné, využívající signálů (WiFi, Bluetooth atd.), nebo využívající samotného telefonu
a jeho senzorů tj. inerciální navigace. Zde se budeme zabývat využitím WiFi pro navigaci.
Cílem práce je využít potenciálu mobilních telefonů a jejich senzorů pro lokalizační systém,
vybrat nejvhodnější a implementovat jej. Tento vybraný systém následně testovat
a porovnat výsledky měření. Tato práce je rozdělena do 4 kapitol. V první kapitole se
krátce podíváme na systémy mimo WiFi. V druhé kapitole pak rozebereme existující WiFi
systémy, porovnáme a vybereme nejvhodnější pro implementaci. Třetí kapitola je věnována
vlastní implementaci vybraného systému. V poslední kapitole se podíváme na výsledky implementace,
reps. přesnost měření.
1
Kapitola 2
Metody lokalizace
V této kapitole si krátce představíme některé metody lokalizace mimo WiFi a srovnáme jejich
použitelnost se systémy využívajících právě WiFi. V současné době je nejpoužívanějším
systémem pro navigaci systém GPS, řadící se do GNSS.
2.1 GNSS
GNSS (Global Navigation Satellite Systems) jsou systémy, mezi které se řadí už zmiňovaný
GPS spravovaný vládou USA, ruský systém GLONASS nebo evropský projekt GALILEO.
GNNS využívají ke své činnosti specifický hardware - satelity, které krouží po oběžné dráze,
a díky nim jsou tyto systémy schopny lokalizace.
V současné době obíhá planetu Zemi minimálně dvacet čtyři funkčních satelitů systému
GPS [13]. Zprávy, které satelity vysílají, se dělí na kategorie L1,...,L5, podle frekvence
a určení[15].
Kategorie Frekvence(MHz) Použití
L1 1575.42 Civilní a vojenské
L2 1227.60 Civilní a vojenské
L3 1381.05 Sledování balistických střel
L4 1379.05 Ionosferická korekce
L5 1176.45 Signály SoS (Safety-of-Life signal)
Tabulka 2.1: Kategorie GPS signálů
Každý satelit periodicky vysílá zprávu, tzv. NAV Message, která se skládá ze tří částí.
První část obsahuje datum, čas a status satelitu, druhá část orbitální data, ze kterých
je schopen příjemce zprávy získat polohu satelitu, a poslední část obsahuje identifikátory
všech satelitů, tzv. PRN čísla[13]. Pro výpočet fyzických souřadnic entity je potřeba alespoň
čtyř jedinečných signálů pro určení délky, šířky a výšky, kdy se porovnávají časy
odeslání a doručení. Trilaterací pak zjistíme naši pozici, která je průsečíkem funkcí signálu
vysílaných družicemi [15], viz obrázek 2.1.
2
2. Metody lokalizace
Obrázek 2.1: Určení polohy trilaterací 4 satelitů [10]
K dosažení co nejrelevantnějších výsledků je žádoucí, aby 𝑇 = 𝑡 𝑟𝑒𝑐𝑖𝑒𝑣𝑒 − 𝑡 𝑠𝑒𝑛𝑑, kdy 𝑇 je
rozdíl času doručení NAV Message a času odeslání NAV Message, byl co nejmenší. Ideální
případ je zachytávat přímý signál ze všech (minimálně tří) družic. Na volném prostranství,
kde není prostor pro odraz signálu, se tohoto minimálního času dá spolehlivě dosáhnout.
V tomto řípadě je chybová vzdálenost rovna řádově na metry [15]. S přibývajícím množstvím
odrazu se tento čas zvětšuje, což zvětšuje i chybovou vzdálenost. V interiérech je
použití GPS zcela nemyslitelné. Velký počet odrazů i blokování signálu střechami či zdmi
budov buď zcela znemožňuje použití GPS, nebo je chybová vzdálenost tak velká, že nejsme
schopni určit přesnou polohu.
2.2 INS
INS (Inertial Navigation Systems) jsou systémy, kde je veškerý potřebný hardware obsažen
v tzv. IMU (Inertial Measurement Unit). Jeho součástí jsou senzory, 3-ortogonální
gyroskop a 3-ortogonální akcelerometr, poskytující úhlovou rychlost, respektive lineární
zrychlení [14]. Na základě znalosti těchto dat a počáteční pozice entity jsou tyto systémy
schopny určovat naši polohu. Dříve byla inerciální navigace vzhledem k rozměrům gyroskopu
a akcelerometru využívána převážně v letadlech, ponorkách, lodích apod. [14].
S příchodem MEMS (Micro-Electrical Mechanical Systems) se tyto senzory dostaly i do
menších zařízení, jako jsou právě mobilní telefony, tablety atd., a díky nim jsou MZ schopny
inerciální navigace.
Inerciální navigaci lze používat spolu s dalším lokalizačním systémem. Tímto spojením
zvýšíme celkovou přesnost lokalizace.
3
Kapitola 3
WiFi lokalizace
V této kapitole se budeme již věnovat WiFi-based lokalizačním systémům. Systémy, kterými
se budeme zabývat detailněji, potřebují ke své činnosti již vybudovanou infrastrukturu
sestavenou z jednotlivých přístupových bodů (access point, AP). Tato nutná podmínka je
v dnešní době splněna v téměř všech objektech, ve kterých má smysl využívat navigaci
(zmiňované úřady, nemocnice atd.). Důvod, proč má smysl tyto systémy implementovat,
je popsán v kapitole o GPS, kdy tuto navigaci nejsme schopni efektivně využívat v interiérech.
Do budoucna je možné upravit GNSS systémy tak, aby jejich signály překonaly
současné překážky, ale v dnešní době nelze tyto systémy v interiérech použít.
Nyní se budeme věnovat samotnému WLAN a WiFi principu, poté si představíme Ad-hoc
topologii a nakonec se zaměříme na lokalizace nad infrastrukturovanými sítěmi.
WiFi je označení standardů postavených nad IEEE 802.11, popisující bezdrátovou komunikaci
v počítačové síti. Standard 802.11 má čtyři rozšíření, která se liší parametry sítě,
jako je frekvence, přenosová rychlost a vlnová délka, jež hraje roli při odchylkách WLAN
kanálů, které budou popsány dále [19][1].
802.11 Protokol Frekvence (GHz) Vlnová délka (mm)
a 5 59
b 2.4 125
g 2.4 125
n 2.4/5 125
Tabulka 3.1: Rodina standardů 802.11
Variace 802.11b se časem stala primárním standardem pro WLAN (Wireless Local Area
Network) namísto původního 802.11. Rozšíření 802.11b používá k přenosu dat rádiové vlny
(RF). RF je část spektra elektromagnetického záření. K modulaci a šíření RF používá
mechanismus DSSS (Direct Sequence Spread Spectrum), kdy nosný signál pokrývá plnou
šířku pásma (spektra) přenosové frekvence vysílače[19].
Název Wi-Fi je ochrannou značkou organizace Wireless Ethernet Compability Alliance,
WECA, která mimo jiné certifikuje zařízení splňující rodinu standardů 802.11.
Těm zařízením splňujícím 802.11x, kde 𝑥 ∈ {𝑎, 𝑏, 𝑔, 𝑛}, uděluje WECA příznak Wi-Fi.
4
3. WiFi lokalizace
Podle toho, jak tyto zařízení zapojíme do WiFi sítě a jak celou síť nastavíme, rozlišujeme
dvě hlavní topologie. Liší se implementovanými protokoly, způsobem komunikace atd.
Vzhledem ke značným rozdílům jsou systémy navigací pro jednotlivé topologie principiálně
velmi rozdílné.
∙ Ad-hoc sítě
∙ Client/Server (infrastrukturované) sítě
Ad-hoc sítě
Topologie
Ad-hoc sítě jsou sítě, jejichž základním kamenem je radio client, uzel (node). Uzly spolu
komunikují přímo, není potřeba žádný AP, žádný centralizovaný server[8].
Obrázek 3.1: Topologie Ad-hoc sítě [11]
Navigace
Navigační systémy pro ad-hoc sítě pracují např. na principu využití empirické propagace
rádiových modelů k triangulaci lokalizace MZ, jak je popsáno v [5].
Infrastrukturované sítě
Topologie
Základem této sítě je soubor APs, přes které komunikujeme se sítí. Všehny APs musí mít
stejné SSID (identifikátor) sítě. V síti je hlavní (jeden, či více) směrovač (router), který
zajišťuje směrování a tok dat po své LAN (Local Area Network). Jednotlivé APs pak slouží
jako přístupové body k síti.
Navigace
Systémy navigace v infrastrukturovaných sítích se dělí do tří kategorií podle způsobu využití
signálu vysílaného jednotlivými APs:
5
3. WiFi lokalizace
Obrázek 3.2: Topologie infrastrukturované sítě [12]
∙ Cell of Origin - Deadalus
∙ Signal Strength - Radar, Horus, Compass
∙ Time of Arrival - LI00
V této práci se budeme zabývat systémy využívající sílu signálu (SS). Než se dostaneme
k samotným systémům, zaměříme se nejprve na specifické vlastnosti WLAN kanálu,
způsobující odchylky RF signálu..
Vlastnosti WLAN kanálu
Propagace RF signálu prostorem způsobuje dva typy odchylek:
∙ dočasné odchylky měření signálu (odchylky při statickém měření SS)
∙ prostorové odchylky měření signálu (odchylky při měření SS v pohybu)
Dočasné odchylky
Tyto odchylky se projevují během času, pokud je MZ zafixované na jednom místě. Při snímání
síly signálu z jednoho AP se histogramy se zaznamenanými daty během času lišily
o hodnotu 10 dBm a víc. Je žádoucí, aby systémy využívaly k určení pozice více APs než
jen jeden. Tuto hodnotu SS je však možno korelovat, nicméně vysoké korelace mohou celý
systém s přibývajícím množstvím APs degradovat[1].
Odchylka při detekování síly signálu z více APs je znázorněna v grafu 3.3, kde je vidět monotónně
rostoucí funkci vyjadřující počet zachycených signálů vzhledem k jejich průměrné
SS. Vzhledem ke konstantnímu šumu kanálu platí, že čím větší SS, tím větší poměr signál/šum.
Z toho vyplývá, že pravděpodobnost zachycení signálu síťovou kartou je větší
[1].
6
3. WiFi lokalizace
Obrázek 3.3: Vztah mezi průměrnou hodnotou SS a procentem zachycených signálů [1]
Prostorové odchylky
Tyto odchylky se projevují, pokud je MZ v pohybu. Při pohybu na delší vzdálenost vzniká
odchylka díky útlumu RF signálu, na druhou stranu při pohybu na malé vzdálenosti vznikají
odchylky díky fyzikálním vlastnostem RF signálu. Pro 802.11b sítě pracující na frekvenci
2,4 GHz je vlnová délka 12,5 cm, kdy při měření průměrných SS můžeme dostávat
odchylku až do 10 dBm [1], ve vzdálenosti je to pak 7,6 cm.
3.1 Radar
Úvod
Systém Radar, je prvním ze systémů využívajících bezdrátovou WiFi síť, který bude v této
práci představen. Radar je postaven na RF bezdrátových LAN síťích nad protokolem IEEE
802.11 [2].
Princip lokalizace
Základní myšlenkou systému Radar je detekování síly signálu (SS) jednotlivých APs. Tato
hodnota pak vyjadřuje vzdálenost příjemce signálu vzhledem k AP. Jinými slovy, tato
hodnota je funkcí relativní polohy příjemce signálu. Tato hodnota přirozeně roste s bližší
vzdáleností příjemce vůči AP a naopak. Hodnoty SS jednotlivých s jsou na sobě nezávislé.
Tuto znalost využívá Radar pro lokalizaci MZ.
V první fázi je potřeba vytvořit mapu otisků (radio map, RM) jednotlivých APs. RM je
databáze otisků snímaných na různých místech budovy, resp. místnosti. Záznam v RM je ktice
(𝑥, 𝑦, 𝑧, 𝑠𝑠𝑖(𝑖=1...𝑛)), kde (𝑥, 𝑦, 𝑧) jsou fyzické souřadnice místa snímání otisku a 𝑠𝑠𝑖(𝑖=1...𝑛)
je síla signálu vysílaná 𝑖𝑡ℎ
AP. Samotné vytváření RM spočívá ve snímání otisků na vybraných
bodech (referecence point, RP) rozprostřených po budově, reps. místnosti, které
7
3. WiFi lokalizace
se následně uloží v daném tvaru do RM. Body, na kterých se provede snímání otisků, mohou
být vybrány náhodně, avšak preferované jsou body, které mají konstatní vzdálenost
od sebe, abychom systematicky pokryli detekovaný prostor měřenými body, viz 3.4.
Obrázek 3.4: Ideální pokrytí místnosti RP
Jakmile máme neprázdnou RM, Radar je schopen detekovat naši pozici za předpokladu,
že se nacházíme v prostoru RPs. Tato detekce probíhá v reálném čase. MZ sejme otisky
všech APs, které jsou v dosahu. Tyto otisky se pak porovnají se záznamy v RM, vybere se
nejlepší shoda a Radar vrátí jako naši pozici (𝑥, 𝑦, 𝑧) referenčního bodu. Samotné porovnávání
a výběr nejvhodnějšího kandidáta se provádí NNSS algoritmem (Nearest Neighbor in
Signal Space), který vypočítá Eukleidovskou vzdálenost mezi jednotlivými záznamy v RM
a aktuálními otisky.
NNSS-AVG je variací NNSS. Občas je vhodných kandidátů na náš RP více, proto se
jako výsledek tohoto algoritmu vypočítá jako aritmetický průměr vzdáleností vybraných
kandidátů. Přesná pozice RP se vypočítá analogicky[2].
Sledování pohybu mobilního zařízení
NNSS algoritmus pracuje deterministicky. Při každém požadavku na aktuální polohu se
s aktuálními otisky porovává celá RM. V případě malé RM procházení každého záznamu
moc nevadí, ale při zvyšujícím se počtu záznamů roste výpočetní doba. Proto systém Radar
sleduje pohyb MZ a tato data posléze využívá k urychlení celého algoritmu i k zpřesnění
odhadu aktuální polohy. Myšlenkou je, že se člověk za normálních okolností nepřesouvá
8
3. WiFi lokalizace
po místnosti o např. 5 metrů za sekundu, ani nepřeskakuje jednotlivé RPs. Systém Radar
proto implementuje algoritmus založený na Viterbiho algoritmu.
Viterbi algoritmus (VA)
VA je algoritmus dynamického programování, který hledá nejpravděpodobnější posloupnosti
skrytých stavů, tzv. Viterbiho cestu. Tento algoritmus představil Andrew Viterbi
roku 1967 pro dekódování konvolučních kódů na digitálních komunikačních linkách se
šumem[9]. Algoritmus pracuje se skrytými Markovovými procesy[7], kde je stavový prostor
S, počáteční pravděpodobnosti 𝜋𝑖 začátku ve stavu i a přechodové pravděpodobnosti
𝑎𝑖,𝑗pro přechod ze stavu i do stavu j. Pro danou výstupní posloupnost 𝑦1, . . . , 𝑦 𝑇 je nejpravděpodobnější
stavová sekvence 𝑦1, . . . , 𝑦 𝑇 splňující rekuretní vztahy[20]:
𝑉1,𝑘 = 𝑃(𝑦1|𝑘).𝜋 𝑘
𝑉( 𝑡, 𝑘) = 𝑃(𝑦𝑡|𝑘).𝑚𝑎𝑥 𝑥∈𝑆(𝑎 𝑥,𝑘.𝑉𝑡−1,𝑥)
Kde 𝑉𝑡,𝑘 je pravděpodobnost nejpravděpodobnější sekvenci stavů 𝑡 → 𝑘, 𝑘 je koncový
stav.
Viterbi-like algoritmus
Systém Radar implementuje obměnu Viterbiho algoritmu. Při každém získání SS n-tice se
provede NNSS vyhledávání k nejbližších sousedů (k-NNSS), tj.k nejlepších shod pro výběr
RP jako místa, kde se nachází MZ. V současné době se udržuje historie o hloubce
h takových k-NNSS vyhledávání. Kolekce takových h k-NNSS množin je vidět na grafu,
kde vrcholy reprezentují jednotlivé RPs a hrana, která je ohodnocena metrikou, tj. Eukleidovská
vzdálenost mezi fyzickými souřadnicemi daných RPs, vyjadřuje trajektorii MZ.
Čím větší je váha hrany, tím klesá pravděpodobnost. Každým aktualizováním této historie
k-NNSS (kde se uloží nejnovější záznam a nejstarší se vymaže) se spočítá nejkratší
cesta mezi nejstarším a nejnovějším záznamem. Tato nejkratší cesta je reprezentována jako
nejpravděpodobnější trajektorie MZ[2].
Obrázek 3.5: Ukázka stavu Viterbi-like algoritmu [2]
9
3. WiFi lokalizace
3.2 Horus
Horus je systém založený na RF, implementovaný na 802.11 bezdrátových LAN (WiFi).
Využívá síly signálů vysílaných APs pro určení polohy MZ. Tak jako Radar, tak i systém
Horus pracuje ve dvou fázích:
∙ Offline fáze, sestává se ze snímání SS APs v daných RPs a budování RM
∙ Online fáze, spočívá v samotném vypočítání polohy MZ na základě získaných SS
Zatímco Radar používá deterministické techniky pro určení polohy MZ (algoritmem
NNSS), Horus pracuje s pravděpodobnostmi, kdy ukládá distribuční funkce signálu do RM
a pak využívá pravděpodobnostních technik pro určení polohy MZ. Nyní si přiblížíme
jednotlivé prvky systému Horus viz 3.6.
Obrázek 3.6: Části systému Horus [1]
Matematický model
Horus stanovuje dvou-rozměrný fyzický prostor X, kde v každé pozici 𝑥 ∈ X můžeme
snímat síly signálu k APs. Takový k-rozměrný prostor sil signálů značíme jako S. Každý
10
3. WiFi lokalizace
prvek tohoto prostoru 𝑠 ∈ S je pak k-rozměrný vektor, jehož záznamy reprezentují síly
signálu jednotlivých APs. Po získání vektorů 𝑠 = (𝑠1, . . . , 𝑠 𝑘) je cílem systému Horus najít
takovou pozici 𝑥 ∈ X, která má největší pravděpodobnost 𝑃(𝑥/𝑠), tzn.
𝑎𝑟𝑔𝑚𝑎𝑥 𝑥[𝑃(𝑥/𝑠)].
Díky Bayesově teorému můžeme vztah vyjádřit jako:
𝑎𝑟𝑔𝑚𝑎𝑥 𝑥[𝑃(𝑥/𝑠)] = 𝑎𝑟𝑔𝑚𝑎𝑥 𝑥[𝑃(𝑠/𝑥)]
𝑃(𝑥/𝑠) je pak vyčíslitelná s využitím RM jako:
𝑃(𝑥/𝑠) =
𝑘∏︁
𝑖=1
𝑃(𝑠𝑖/𝑥).
Tímto postupem získáme jedinečný záznam z RM, pro zvýšení přesnosti využívá Horus
dvě techniky pro určení pozice v kontinuálním prostoru.
První technika se nazývá Center of Mass of the Top Candidate Locations. Každá
pozice v RM je reprezentována jako objekt ve fyzickém prostoru, jehož váha je rovna přiřazené
pravděpodobnosti získané rozhodovacím algoritmem. Poté jsme schnopni získat těžiště
takovýchto N objektů s největší váhou, kde N je systémový parametr 1 <= 𝑁 <= ‖𝑋‖.
Formálně, nechť 𝑝(𝑥) je pravděpodobnost pozice 𝑥 ∈ X a ¯X je seznam pozic z RM v sestupném
pořadí podle pravděpodobnosti. Výše uvedená technika pak určí aktuální pozici
x jako:
𝑥 =
∑︀ 𝑁
𝑖=1 𝑝(𝑖)¯X
∑︀ 𝑁
𝑖=1 𝑝(𝑖)
Druhá technika Time-Averaging in the Physical Space (TAPS) je založena na použití
průměrného času k doladění výsledných odhadů pozice. Tato technika získává výslednou
pozici na základě zprůměrování posledních W odhadů z minulosti. Formálně, z minulosti
získaných odhadů pozice 𝑥1, 𝑥2, . . . , 𝑥𝑡, TAPS určuje aktuální pozici ¯𝑥𝑡 v čase t jako:
¯𝑥𝑡 =
1
𝑚𝑖𝑛(𝑊, 𝑡)
𝑡∑︁
𝑡−𝑚𝑖𝑛(𝑊,𝑡)+1
𝑥𝑖
Clustering
Systém Horus si klade dva cíle: lokalizovat MZ a snížit výpočetní nároky pro určení polohy.
Dosažení prvního cíle je popsáno výše. Pro snížení náročnosti rozhodovacího algoritmu
používá systém Horus Incremental Triangulation clustering technique (IT).
11
3. WiFi lokalizace
Horus definuje tzv. clusters (shluky, klastry), kdy cluster je množina pozic, ve kterých se
vyskytují známé APs. Množina známých APs je pak cluster key. Pro dané x chceme určit,
do kterého shluku patří. Myšlenka IT spočívá v tom, že každý AP definuje podmnožinu
z RM, která je pokryta daným AP. Tyto pozice z RM jsou shlukem pozic, jehož klíč (key)
je AP pokrývající pozice v tomto shluku. Při určování polohy MZ pak postupujeme od
jednoho AP k dalšímu. Tzn. první AP vybere podmnožinu záznamů RM obsahující ty
záznamy, jejichž pozice jsou pokryty právě prvním AP. Při vybírání shody druhého AP
pak bereme jako vstupní RM vybranou podmnožinu získanou v předchozím kroku. Tento
druhý AP opět vybere podmnožinu krytou druhým AP atd. Pozice x pak patří do shluku
s klíčem AP a pouze tehdy, jestliže v pozici x detekujeme signál z AP a.
IT dále pracuje následovně. Na vstupu je sekvence APs s jejich SS uspořádána sestupně.
IT následně vezme jednotlivé seřazené APs a postupně vybírá podmožinu pozic v RM.
Pokud je pravděpodobnost daného AP, např. 𝑎1, prokazatelně větší (na základě odchylky)
než pravděpodobnost následujícího AP 𝑎2, vrací IT jako výsledek 𝑎1. V opačném případě
pokračuje IT ve vybírání podmožiny na základě 𝑎2, 𝑎3 atd. Tímto postupným vybíráním
podmnožiny Horus pracuje rychleji, než kdyby se při každém dotazu na shodu AP musela
procházet celá RM[1].
Prostorové odchylky
Jelikož RM obsahuje RPs, které jsou typicky ve vzdálenosti ≥ metr od sebe, nepokrývá RM
odchylky na malém prostoru. Proto systém Horus využívá Perturbation technique, která je
založena na rozpoznání těchto odchylek a jejich kompenzování.
Pro detekci využívá heuristik, člověk s MZ se pohybuje jen určitou rychlostí mezi RPs.
Systém určí pozici s klasickou RM a rozhodovacím algoritmem. Poté se vypočítá vzdálenost
mezi nalezenou pozicí a předchozí pozicí MZ. Pokud je tato vzdálenost větší než odchylka
(daná v závislosti na rychlosti pohybu MZ mezi RPs), systém detekuje odchylku.
Jako kompenzaci takových odchylek systém rozebere přijaté SS vektory, znovu odhadne
pozici a vybere tu, která je nejblíže k předchozí pozici MZ[1].
3.3 Compass
Systém Compass pracuje stejně jako jeho předchůdci ve dvou fázích. Offline fáze slouží pro
sběr SS na daných RPs a budování RM a online fáze, ve které se hledá aktuální pozice MZ.
Stejně jako Horus používá k určení pozice probabilistic technique. Liší se však v selektování
podmnožiny z RM pro výběr nejvhodnějšího kandidáta[4].
Uživatel v typickém případě nese svoje MZ před sebou, aby viděl na displej, případně
mohl s MZ interagovat. Lidské tělo je tvořeno z cca 70% vodou, čili s velké části blokuje
802.11 RF. Tzn. detekovaná SS z daného AP závisí na orientaci našeho těla vůči AP. Tato
skutečnost pak degraduje systémy založené na snímání SS.
12
3. WiFi lokalizace
Na základě [4] byl proveden experiment o vlivu lidského těla na blokování 802.11 RF
signálu. Výsledky jsou vidět na grafech 3.7.
Obrázek 3.7: Rozdíl v SS na základě orientace uživatele[4]
V tomto experimentu autoři [4] měřili SS, kdy záměrně blokovali RF signál z AP, čili postavení
bylo AP → Uživatel → MZ. Průměrné výsledky jsou v levém grafu, kde se měřená
průměrná síla signálu pohybuje stabilně mezi -80 a -83 dBm. V druhém kroku experimentu
se již uživatel otáčel vždy o 45 ∘
, výsledky jsou v druhém grafu. Rozdíl je oproti statickému
uživateli až o 15 dBm (orientace 135 ∘
při rozestavení AP → MZ → Uživatel). I v případě
částečeného blokování signálu jsou rozdíly stále větší než 5 dBm.
Na základě tohoto experimentu přidává systém Compass k základní myšlence další komponentu,
a to kompas[4]. Dnešní MZ jsou již vybaveny potřebnými senzory, jako je gyroskop
spolu s magnetometrem, čili jsou schopny určit orientaci uživatele.
Matematický model
Mějme fyzický prostor pokryt mřížkou q referenčních bodů (RPs) vzdálených metr od sebe.
Na každém RP provedeme sběr SS APs v 8 směrech. Formálně, nechť 𝑆 = {𝑠1, . . . , 𝑠 𝑛} je
stavový prostor q referenčních bodů 𝑅 = {𝑟1, . . . , 𝑟 𝑞} a orientací 𝑂 = {0 ∘
, 45 ∘
, . . . , 315 ∘
}.
Každý stav 𝑠 ∈ 𝑆 je pak definován jako 𝑆 = 𝑅 × 𝑂, tj. souřadnicemi kartézského prostoru
a orientací.
Distribuce SS AP získaná měřením je agregací několika měření. Každé měření 𝑀 =
{𝑚1, . . . , 𝑚 𝑘} obsahuje sílu k přítomných APs. Dále 𝑚𝑖 = (𝑝𝑖, 𝑖𝑑𝑖), 𝑖 ∈ {1, . . . , 𝑘} je ntice
obsahující sílu AP 𝑝𝑖(𝑝𝑖 ∈ {0, 1, . . . , 255}) a unikátní MAC adresu 𝑖𝑑𝑖.
Dále definujeme podobnost stavů. Dva stavy a a b reprezentované souřadnicemi a orientacemi
𝑜 𝑎 a 𝑜 𝑏 jsou podobné vzhledem k 𝛼 odchylce právě tehdy, když |𝑜 𝑎 − 𝑜 𝑏| ≤ 𝛼.
Tato podobnost stavů se využívá v online fázi pro výběr podmnožiny z RM. Dle [4] je 𝛼
pro dosažení minimální chybové vzdálenosti rovna 𝛼 = 69∘
.
13
3. WiFi lokalizace
Online Fáze
V online fázi uživatel získá měření M SS okolních APs a orientaci O. Na základě dané
odchylky 𝛼 získáme podmožinu z RM. Tyto podobné stavy následně spojíme dohromady
zkombinováním jejich histogramů, kdy pro každý referenční bod 𝑖 a AP 𝑗 těchto podobných
stavů vypočítáme průměr 𝜇𝑖,𝑗 a standardní ochylku 𝜎𝑖,𝑗.
Pravděpodobnost získání množiny měření 𝑀 v referenčním bodě 𝑖 je vyjádřena podmíněnou
pravděpodobností:
𝑃(𝑀|𝑟𝑖) =
𝑘∏︁
𝑎=1
𝑃(𝑚 𝑎|𝑟𝑖)
kde
𝑃(𝑚 𝑎|𝑟𝑖) = 𝑃((𝑝 𝑎, 𝑖𝑑 𝑎)|𝑟𝑖)
=
𝐺𝑖,𝑖𝑑 𝑎 (𝑝 𝑎) + 𝛽
∑︀2
𝑚=0 55𝐺𝑖,𝑖𝑑 𝑎 (𝑚) + 𝛽
a
𝐺𝑖,𝑖𝑑 𝑎 (𝑝 𝑎) =
∫︁ 𝑝 𝑎+1/2
𝑝 𝑎−1/2
𝑒−(𝑥−𝜇 𝑖,𝑖𝑑 𝑎 )2/(2𝜎2
𝑖,𝑖𝑑 𝑎
)
𝜎𝑖,𝑖𝑑 𝑎
√
2𝜋
d𝑥
𝐺𝑖,𝑖𝑑 𝑎 (𝑝 𝑎) reprezentuje pravděpodobnost, že v referenčním bodě 𝑖 naměříme sílu signálu
𝑝 𝑎 AP 𝑖𝑑 𝑎. 𝛽 pak reprezentuje hodnotu šumu, kterou přidáváme do výpočtu pravděpodobnosti,
a která nám vyvažuje odchylky WLAN kanálu.
V posledním kroku se tyto hodnoty použijí k výpočtu 𝜋
′
𝑖 vektoru:
𝜋
′
𝑖 =
𝜋𝑖 * 𝑃(𝑀|𝑟𝑖)
∑︀
𝑗 = 1 𝑛 𝜋𝑗 * 𝑃(𝑀|𝑟𝑗)
pro každý RP 𝑖. Na začátku algortimu je 𝜋𝑖 = 1/𝑞, kde 𝑞 je počet RPs[4].
3.4 Srovnání systémů
Všechny systémy pracují ve dvou fázích. V první fázi, offline, pokrývají daný prostor sítí
referenčních bodů, ve kterých následně provedou měření okolních APs. Tato data následně
zpracují a uloží do databáze, tj. RM. V druhé fázi, online, na základě aktuálních měření
okolních APs dokážou tyto systémy určit naši aktuální pozici vůči síti RPs uložených v RM.
∙ Radar: k určování aktuální pozice používá deterministické techniky, jako je výpočet
Eukleidovské vzdálenosti algoritmem NNSS. Pro sledování MZ v kontinuálním prosotru
používá obměnu Viterbiho algoritmu. Tyto techniky však nepočítájí s odchylkami
WLAN kanálů, které jsou popsány v 3.
14
3. WiFi lokalizace
∙ Horus: tento systém určuje aktuální pozici pravděpodobnostními technikami. K ošetření
WLAN odchylek používá Petrubačních technik. Dále pro snížení výpočetní doby
je implementován Incremental Triangulation clustering technique
∙ Compass: lokalizační technika stejná jako v případě Horus, doplňuje ošetření blokování
signálu lidským tělem. Tato skutečnost má největší dopad na výsledné srovnání.
Orientace MZ vůci AP má zásadní význam pro výsledný výstup rozhodovacího algo-
ritmu.
Z výše uvedených informací spolu s [6] se budeme v této práci dále zabývat systémem
Compass. Rozhodujícím aspektem je zohlednění orientace při určení pozice.
15
Kapitola 4
Implementace
Pracovní název aplikace je WifiIndoorNavigation (WIT), která je implementována na platformu
Android. Vzhledem k tomu, že systém Compass vyžaduje informaci o orientaci MZ,
je třeba mít v mobilním zařízení senzory (magnetometr nebo magnetometr s gyroskopem
pro větší přesnost) a Android API ve verzi minimálně 11. Dřívější Android verze neposkytují
potřebné API pro práci s těmito senzory.
V této práci budeme pracovat s metodami a třídami ze dvou balíků:
∙ android.hardware
∙ android.net.wifi
android.hardware
Tento balík slouží k práci se senzory. Jedná se konkrétně o tři třídy [16]:
∙ SensorManager, poskytuje rozhraní a přístup k jednotlivým senzorům ze třídy
Sensor
∙ SensorEvent
∙ Sensor, obsahuje všechny dostupné hardwarové senzory a poskytuje z nich získaná
data
android.net.wifi
V tomto balíku budeme využívat dvě třídy [17]:
∙ WifiManager, rozhraní obsahující veškeré konstanty ke konfiguraci okolních WiFi
a metody pro práci s WiFi senzorem
∙ ScanResult, třída, která popisuje aktuální konfiguraci detekované WiFi sítě, jako je
BSSID (MAC adresa AP), SSID (identifikátor sítě), frekvenci, sílu signálu, informace
o autentizaci, klíče a čas skenování AP
Stejně, jako je systém Compass rozdělen do dvou fází, tak i WIT obsahuje dvě hlavní
části, tj. třídy:
16
4. Implementace
∙ ScanningEngine, pokrývá veškeré dotazy na snímání otisků a detekci orientace
MZ
∙ SearchingEngine, rozhodovací algoritmus
4.1 ScanningEngine (Offline fáze)
Orientace
Orientaci uživatele s MZ získáme ze senzorů MZ. Senzory potřebné ke zjištění orientace
jsou popsány v sekci android.hardware. Konstanty přidělené senzorům magnetometru
a gyroskopu jsou TYPE MAGNETIC FIELD resp. TYPE GYROSCOPE. Data ze senzoru
obsahující informaci o orientaci nám poskytují třídy z Android API. Tuto informaci převedeme
na stupně pomocí vzorce: ℎ𝑒𝑎𝑑𝑖𝑛𝑔 = 𝜋*𝑑𝑎𝑡𝑎
180
.
Jelikož podle [4] potřebujeme orientaci 𝑂 = {0 ∘
, 45 ∘
, . . . , 315 ∘
} a ℎ𝑒𝑎𝑑𝑖𝑛𝑔 nabývá hodnot
< 0, . . . , 360), přepočítáme ℎ𝑒𝑎𝑑𝑖𝑛𝑔 funkcí ℎ𝑒𝑎𝑑𝑖𝑛𝑔 → 𝑂, kdy mezní hranice je 22, 5∘
.
Tzn.:
function getOrientation() {
if (22,5 >= heading && heading < 67,5) {
return 45
}
fi
if (67,5 >= heading && heading < 112,5) {
return 90
}
fi
.
.
.
}
Výstupem je pak orientace MZ 𝑜 ∈ 𝑂.
Data z těchto senzorů jsou vizualizována ve ScanningActivity, viz obr.4.1, kde černá
šipka ukazuje naši orientaci ve stupních (tj. ℎ𝑒𝑎𝑑𝑖𝑛𝑔), a také je uvedena vlevo nahoře jako
textové pole.
Sběr otisků
Ke zpracování dat z AP používáme třídy z android.net.wifi:
∙ ScanResult
∙ WifiManager
17
4. Implementace
Obrázek 4.1: ScanningActivity
A to konkrétně dvě metody z třídy WifiManager. Metoda startScan zahájí skenování
okolních APs a metoda getScanResults vrací výsledky skenování jako seznam
ScanResult.
Tento seznam dále převádíme na základní model WIN RssFingeprint.
RssFingerprint obsahuje proměnné pro uložení konfiguračních informací daného AP:
∙ BSSID
∙ orientation, 𝑜𝑟𝑖𝑒𝑛𝑡𝑎𝑡𝑖𝑜𝑛 ∈ 𝑂
∙ RP, referenční bod, ze kterého bylo prováděno měření
∙ average, průměrná síla signálu AP
∙ deviation, odchylka při měření SS AP
Po převedení ScanResult → RssFingerprint se seznam ukládá do databáze.
Databázový model
WIT používá nativní SQLite databázi z balíku android.database.sqlite. Vlastní
implementovaná databáze obsahuje dvě tabulky:
18
4. Implementace
∙ TABLE RSSFINGEPRINT, obsahuje snímané otisky
∙ TABLE MERGE, tabulka pro uchování otisků podobných stavů, jak bylo popsáno
v 3.3
Offline fáze
Obrázek 4.2: Úvodní obrazovka WIT
Pro testovací účely uvažujeme testovací prostor rozdělený do mřížky, která se skládá
z 4×4 tlačítek, jak je vidět na obrázku 4.2. Označení tlačítek odpovídá označení bodů
v kartézské soustavě souřadnic.
Offline fáze spočívá v budování RM. Jakmile máme testovací prostor pokrytý sítí z šestnácti
referenčních bodů, na každém z nich provedeme měření. Po stisknutí daného tlačítka, reprezentující
RP, kde právě stojíme, se zobrazí skenovací obrazovka, viz obr. 4.1. V této části
aplikace provádíme měření. Dle [4] měříme v osmi směrech, vždy po 45∘
. Textové pole vlevo
19
4. Implementace
nahoře i střelka označuje náš aktuální úhel. Měření spouštíme tlačítkem SCANN! umístěném
v horní liště.
Pro pokrytí odchylek WLAN při statickém měření snímáme okolní APs po dobu 5 sekund.
Všechna data se uloží do mezipaměti MZ a dále se zpracovávají. Spočítá se aritmetický
průměr SS APs a jejich odchylka. Vypočítaná odchylka není nutností pro další činnost algoritmu,
ale slouží pro pozorovací a testovací účely. Po zprůměrování hodnot se data uloží
do tabulky TABLE RSSFINGEPRINT. Po naměření hodnot v osmi směrech se vrátíme
zpět na hlavní obrazovku tlačítkem Zpět a pokračujeme na další RP. Tímto způsobem
naskenujeme hodnoty u všech šestnácti bodů v osmi směrech.
Jakmile máme naměřeny hodnoty ve všech RPs, vrátíme se na základní obrazovku a použijeme
tlačítko Možnosti (4.3) a stiskneme Do merge.
Obrázek 4.3: Možnosti
Do merge spouští spojování podobných stavů, jak je popsáno v 3.3. Dle [4] je odchylka
𝛼 rovna 69∘
. Za podobné stavy jsou považovány ty, jejichž rozdíl orientací je ±45∘
, tj. např.
pro stav s 𝑜 = 0∘
jsou podobné stavy s 𝑜 = 45∘
a 𝑜 = 315∘
. Jednotlivé hodnoty se opět
průměrují a počítá se nová odchylka, která je již součástí rozhodovacího algoritmu.
Spojené stavy se uloží do tabulky TABLE MERGE.
20
4. Implementace
4.2 SearchingEngine (Online fáze)
Dotazy na aktuální pozici MZ zpracovává třída SearchingEngine. Prvním krokem je
získání aktuálních otisků okolních APs v dané orientaci 𝑜. Poté se vybere podmnožina
RM na základě 𝑜. Vstupem algoritmu je seznam aktuálních otisků okolních APs a mapa
databázových dat. Klíčem jsou RPs a hodnotou pak jejich naměřená data.
Nyní se již počítají pravděpodobnosti jednotlivých RPs, kdy se prochází jejich data a porovnávájí
se s aktuálními měřeními. Při nalezené shodě (tj. shodují se BSSID aktuálního
otisku s databázovým otiskem) se počítá dílčí pravděpodobnost pomocí vzorce:
𝑃(𝑚 𝑎|𝑟𝑖) = 𝐺𝑖,𝑖𝑑 𝑎 (𝑝 𝑎)
𝐺𝑖,𝑖𝑑 𝑎 (𝑝 𝑎) se dále počítá intergrálem, viz 3.3. Výpočet integrálu ovšem není Androidem
nativně podporován, proto je potřeba použít knihovnu nebo dále vzorec vhodně upravit.
Použití knihovny jsme zavrhli vzhledem k výpočetní náročnosti.
Rozholdi jsme se tedy pro ekvivalentní úpravu integrálu. Každý určitý integrál lze vyjádřit
jako:
∫︁ 𝑏
𝑎
𝑓(𝑥) = 𝑔(𝑏) − 𝑔(𝑎)
kde
𝑔′
(𝑥) = 𝑓(𝑥)
Integrál 𝐺𝑖,𝑖𝑑 𝑎 (𝑝 𝑎) můžeme vyjádřit pomoci Gaussovy erf(x). K vyjádření integrálu jsme
použili program Maple.
𝐺𝑖,𝑖𝑑 𝑎 (𝑝 𝑎) =
1
2
𝑒𝑟𝑓
(︃
1
4
√
2(−2𝑝 𝑎 + 1 + 2𝜇𝑖,𝑖𝑑 𝑎 )
𝜎𝑖,𝑖𝑑 𝑎
)︃
−
1
2
𝑒𝑟𝑓
(︃
1
4
√
2(−2𝑝 𝑎 − 1 + 2𝜇𝑖,𝑖𝑑 𝑎 )
𝜎𝑖,𝑖𝑑 𝑎
)︃
Erf(x) lze dále vyjádřit např. Taylorovým polynomem, nebo inverzní funkce 𝑒𝑟𝑓−1
(𝑥) je
vyjádřitelná Maclaurinovou řadou. Všechny tyto způsoby nicméně neřeší původní problém
schnopnosti výpočtu mobilním zařízením.
Pro účely určení pozice však není potřeba přesné vyčíslení, proto jsme se rozhodli erf(x)
aproximovat. Využili jsme aproiximace S.Winitzkiho [18], kdy
𝑒𝑟𝑓(𝑥) ≈ [1 − 𝑒
−𝑥2
4
𝜋 +𝑎𝑥2
1+𝑎𝑥2
]1/2
kde 𝑎 je konstanta
𝑎 ≡ 0, 14
Tuto aproximaci již MZ dokáže jednoduše vypočítat. Výstupem algoritmu je pak mapa,
kde klíčem je RP a hodnota je pak vypočítaná pravděpodobnost. Další krok je nalezení RP
21
4. Implementace
s největší hodnotou, která se zobrazí na hlavní obrazovce. Relevantnější jsou však data,
která program ukládá do souboru na externím úložišti. Zde vidíme jednotlivé mezikroky
a hlavně kompletní výstup algoritmu.
22
Kapitola 5
Testování
5.1 Průběh testování
Testování WIN probíhalo na FI MU, Botanická 68a, Brno, v budově D (před vstupem
do posluchárny D2) na zařízení LG Galaxy Nexus s verzí Android API 18. Jako podklad
pro RM byla stanovena mřížka 4 × 4 RPs vzdálených metr od sebe, viz obr. 5.1
Obrázek 5.1: Testování, síť RP
Dále byly rozmístněny okolo RP-sítě další 4 APs (např. jeden z nich je vidět na obrázku
5.1 vlevo nahoře, nalevo od oranžového kuželu, v podstavci nástěnky).
V každém RP bylo provedeno snímání otisků okolních APs v osmi směrech, tj. budování
RM. Jednotlivé názvy RPs odpovídají názvům RPs aplikace, tzn. (0,0), (1,0) atd.
Při online fázi jsme pak na každém RP provedli čtyři dotazy na aktuální polohu ve
čtyřech směrech po 45∘
. Data, která se uložila do logů, jsme následně převedli do tabulky
23
5. Testování
pro lepší vizualizaci výsledků. Dalším krokem testování bylo postupné vypínání jednotlivých
APs a sledování dopadů na výsledná data. Tabulky reprezentují naši síť, kdy buňka
vlevo dole odpovídá RP 0,0 a analogicky vpravo nahoře 3,3. Zeleně jsou vybarvené ty buňky,
kdy pravděpodobnost daného RP byla maximální. Naopak červěně jsou vybarveny ty
buňky s minimální pravděpodobností daného RP.
1. Zapnuty všechny APs
V tomto testu byly všechny APs zapnuty. Na obrázcích jsou výsledky měření v bodě
0,0 ve čtyřech směrech.
Obrázek 5.2: Všechny APs, orientace 𝑜 𝑎
Obrázek 5.3: Všechny APs, orientace 𝑜 𝑏
Obrázek 5.4: Všechny APs, orientace 𝑜 𝑐
Z naměřených dat byl RP 3,3 vybrán jako aktuální bod s maximální pravděpodobností.Z
kompletních dat, která jsou v příloze, je vidět, že bod 3,3 se nachází
v naprosté většině případů jako výsledek vyhledávacího algoritmu. Při výběru
pouze jednoho RP s maximální pravděpodobností se tato vzdálenost rovná
𝑒𝑟𝑟𝑜𝑟𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 2, 17𝑚. Při agregování RPs s podobnou největší hodnotou je tato
vzdálenost rovna 𝑒𝑟𝑟𝑜𝑟𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 2, 09𝑚.
24
5. Testování
Obrázek 5.5: Všechny APs, orientace 𝑜 𝑑
Obrázek 5.6: Výskyt RP
2. Zapnuty dílčí 4 APs
Při zjišťování aktuální polohy byly brány v potaz pouze MAC adresy našich 4 APs,
které byly rozmístěny v rozích sítě RPs. Hodnoty byly opět v bodě 0,0 pro čtyři
orientace:
Obrázek 5.7: Dílčí APs, orientace 𝑜 𝑎
Obrázek 5.8: Dílčí APs, orientace 𝑜 𝑏
25
5. Testování
Obrázek 5.9: Dílčí APs, orientace 𝑜 𝑐
Obrázek 5.10: Dílčí APs, orientace 𝑜 𝑑
Zde kromě RP 3,3 vystupují i další RPs. Z celkových dat je vidět mnohem šiřší
rozmístění RPs při dotazování na aktuální polohu, viz graf 5.11:
Obrázek 5.11: Výskyt RP
Chybová vzdálenost je pak pro neagregované hodnoty rovna 𝑒𝑟𝑟𝑜𝑟𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 2, 33𝑚
a pro agregované činí 𝑒𝑟𝑟𝑜𝑟𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 2, 45𝑚. I když je tato hodnota vyšší, než u
předchozího případu, je relevantnější z důvodu širšího rozptylu výsledných RPs. V
předchozím testu byl v 75% případů vrácen RP 3,3 jako výsledek. V případě použití
dílčích 4 APs byl nejčastější výsledek vrácen ve ∼ 22% případů.
Pro lepší představu zde uvádíme příklad měření v orientaci 𝑜 𝑎 uprostřed RM, v bodě
2,2 v případě všech APs a v případě dílčích 4 APs, viz obr. 5.12, 5.13.
3. Vypínání dílčích APs
Posledním krokem testování bylo vypínání dílčích APs. V příloze jsou data z dalších
měření při vypínání dílčích APs. Výsledky jsou téměř totožné. Uvádíme zde dva grafy
rozložení výsledných RPs při vypínání dvou APs.:
26
5. Testování
Obrázek 5.12: Výsledky měření v 𝑜 𝑏 v bodě 2,2 při všech APs
Obrázek 5.13: Výsledky měření v 𝑜 𝑏 v bodě 2,2 při dílčích 4 APs
Obrázek 5.14: Vypnutý 1.AP
Obrázek 5.15: Vypnutý 2.AP
27
5. Testování
5.2 Výsledky testování
Výběr APs pro měření
Intuitivně se nabízí, že čím více APs pro měření, tím vetší přesnost. Tuto informaci potvrzují
i autoři [3]. Z našich výsledků vyplývá, že pro měření je důležitý i vhodný výběr
APs. Při měření všech APs byl výstupem algoritmu ve většině případů jeden určitý RP, viz
5.6. V měření dílčích 4 APs vhodně rozmístněných okolo sítě RPs nebyl výstup algoritmu
tak jednoznačný ve prospěch jednoho RP, jako v předchozím případě, viz 5.11. Po vypnutí
jednotlivých APs byly výsledky totožné s případem zapnutých všech APs. Testováním jsme
zjistili, že i vhodný výběr APs pro měření je podstatný vedle celkového počtu APs.
Agregované vs. neagregované výsledky
Níže na grafech jsou celkové odchylky při dílčích měřeních:
Obrázek 5.16: Neagregované výsledky
Obrázek 5.17: Agregované výsledky
Odchylky jsou téměř totožné. Při srovnání výsledků na obr. 5.12 a 5.13 jsme zjistili,
že při agregování výsledků a zohlednění postavení APs (tj. při měření 4 APs vs. při měření
všech APs) je výsledná chybová vzdálenost menší. Z toho vyplývá, že výsledné hodnoty je
třeba agregovat.
28
Kapitola 6
Závěr
Cílem této práce bylo využít potenciál MZ a jejich sonzorů pro lokalizační systém. Našim
úkolem bylo prostudovat existující WiFi lokalizační systémy, vybrat nejvhodnější a
implementovat jej na platformu Android. Postupně jsme si představili v dnešní době nejpoužívanější
systémy mimo WiFi. Ukázali jsme si jejich přednosti, ale hlavně nedostatky,
díky kterým má smysl vyvíjet jiné systémy, založené např. na WiFi. Dále jsme se již
zameřili na tři WiFi systémy: Radar, Horus a Compass. Porovnali jsme je a vybrali nejvhodnější
pro implementaci. Z těchto systému jsme vybrali Compass, protože jako jediný
bere při určení polohy v potaz orientaci MZ. Po implementaci jsme tento systém testovali
a porovnávali výsledky měření.
Při porovnávání našich výsledků se systémem Compass jme zjistili zásadní rozdíl ve výběru
APs pro měření. Z našeho testování vyplývá, že vedle počtu APs je důležitý i jejich
výběr pro měření. Na rozdíl od výsledků systému Compass, který zohledňuje pouze počet
APs [4]. Chybové vzdálenosti pro systém Compass jsou 1,62m při použití přenosného počítače
a externí WiFi antény [4]. Naše výsledky jsou ∼2m při použití MZ a výběru vhodného
rozestavení APs.
Domníváme se, že tyto rozdíly v odchylkách jsou způsobeny nestabilními daty získanými
WiFi senzorem MZ ve srovnání s WiFi senzorem, který používali v [4]. Experimentálně bylo
ověřeno, že signál kolísá o jednotky dBm při měření na statické poloze v průběhu času. Toto
kolísání může mít rozhodující dopad na chybovou vzdálenost. Testování na citlivějším WiFi
senzoru (např. v přenosném počítači) nebylo možné, protože dnešní Android emulátory
nepodporují emulaci hardware senzorů.
Pro budoucí rozšíření této implementace přichází v úvahu částečné propojení systémů
Compass a Horus. Horus lépe pokrývá WLAN odchylky, jak při statickém měření, tak i pro
měření v kontinuálním prostoru.
29
Literatura
[1] YOUSSEF M. a AGRAWALA A. The horus wlan location determinition system.
Dostupné z: http://www.cs.umd.edu/˜moustafa/papers/horus_usenix.
pdf, 2005.
[2] BAHL P. a BALACHANDRAN A. a PADMANABHAN V. Enhancements to the
RADAR User Location and Tracking System. Dostupné z: http://citeseer.
ist.psu.edu/bahl00enhancements.html, 2000.
[3] KING T. a HAENSELMANN T. a EFFELSBERG W. Deployment, calibration, and
measurement factors for position errors in 802.11-based indoor positioning systems,
2007.
[4] KING T. a KOPF S. a HAENSELMANN T. a LUBBERGER Ch. a EFFELSBER
W. Compass: A probabilistic indoor positioning system based on
802.11 and digital compasses. Dostupné z: http://www.researchgate.
net/publication/220926437_COMPASS_A_probabilistic_indoor_
positioning_system_based_on_802.11_and_digital_compasses/
file/9c9605282124fe2a07.pdf, September 2006.
[5] LUNDGREN R.H. a LUNDBERG D. a NORDSTROM E. a TSCHUDIN C. a NIELSEN
J. A large-scale testbed for reproducible ad hoc protocol evaluation, March
2002.
[6] ELADIO M. a ORIOL V. a GERALD F. a RUZENA B. Precise indoor
localization using smart phones. Dostupné z: https://www.
google.cz/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&
uact=8&ved=0CDQQFjAA&url=http%3A%2F%2Fwww.icsi.berkeley.
edu%2Fpubs%2Fspeech%2Fpreciseindoor10.pdf&ei=qNN1U9T_
LafD7Abdm4DIDw&usg=AFQjCNGKf9XT-KghV2Ceh25hJGcSBFg22g&sig2=
DxmkLicMepNqyhJUxNLPGA&bvm=bv.66699033,d.ZGU.
[7] BAUM E.L. a PETRIE T. Statistical inference for probabilistic functions of finite
state markov chains. The Annals of Mathematical Statistics, 1966.
[8] TOUMPIS S. a TOUMPAKARIS D. Wireless ad hoc networks and related topologies:
applications and research challenges. Elektrotechnik und Informationstechnik, 2006.
30
6. Závěr
[9] VITERBI A.J. Error bounds for convolutional codes and an asymptotically optimum
decoding algorithm. Information Theory, IEEE Transactions on, April 1967.
[10] Figure. Dostupné z: http://answers.oreilly.com/topic/
\discretionary{-}{}{}2815-how-devices-gather-location-information/.
[11] Figure. Dostupné z: http://www.globalspec.com/reference/81338/
203279/\discretionary{-}{}{}chapter-12-mobile-ad-hoc-networks.
[12] Figure. Dostupné z: http://www.h3c.com/portal/res/200812/26/
\discretionary{-}{}{}20081226_709524_image005_624021_57_0.
png.
[13] Global positioning system, standard positioning service, performance
standard. Dostupné z: http://www.gps.gov/technical/ps/
2008-SPS-performance-standard.pdf, September 2008.
[14] WOODMAN J.O. An introduction to inertial navigation. Technical report, University
of Cambridge, August 2007.
[15] ENGE Petr MISHRA Pratap. Global Positioning System: Signals, Measurement and
Performance Second Edition. Ganga-Jamuna Press, Massachusetts, 2006.
[16] Android API Reference. android.hardware. Dostupné z: http://developer.
android.com/reference/android/hardware/package-summary.html.
[17] Android API Reference. android.net.wifi. Dostupné z: http://developer.
android.com/reference/android/net/wifi/package-summary.html.
[18] WINITZKI S. Approximation to error function. Dostupné z: http://www.scribd.
com/doc/82414963/Winitzki-Approximation-to-Error-Function, February
2008.
[19] Understanding wi-fi. Dostupné z: https://cs.uwaterloo.ca/˜brecht/
courses/856/readings/background-intro/understandingWiFi.pdf,
January 2002.
[20] Wikipedia. Viterbi algorithm. Dostupné z: http://en.wikipedia.org/w/
index.php?title=Viterbi_algorithm&oldid=604736226, 2014. [Online,
cit. 18.3.2014].
31
Přílohy
Součástí příloh jsou:
∙ Instalační balíček WifiIndoorNavigation.apk
∙ Data z testování. Jednotlivé logy obsahují kompletní data v původní podobě, data v
čitelné podobě a MS Excel soubor, kde jsou data vizualizována
32