Lokalizace v sítích WLAN Semestrální práce
Vypracoval: Tomáš Ječný
Vedoucí práce: Doc. Ing Pavel Pechač, Ph.D.
1 Lokalizace v bezdrátových sítích 1.1 Úvod S rostoucím rozšířením mobilních bezdrátových zařízení stále roste význam přesného určení pozice mobilní stanice (MS – Mobile station) v bezdrátové síti. Znalost této pozice může být využita mnoha způsoby, jako je přizpůsobení aplikace konkrétnímu uživateli a jeho pohybu, navigace, ale i komerční využití v reklamě. Nezanedbatelné je také využití v oblasti veřejné bezpečnosti. Vláda ČR má v úmyslu varovat v případě veřejného ohrožení obyvatelstvo v dané lokalitě prostřednictvím sítě GSM. Zajistit lokalizaci mobilní stanice je obecně možné dvěma způsoby. Lze vybudovat speciální infrastrukturu pro tuto službu, jako jsou systémy družicové navigace GPS, Galileo nebo Glonnas, nebo pro lokalizaci využít už existující struktury. Nejrozšířenějším způsobem radiové komunikace s mobilními stanicemi je sytém mobilních telefonů druhé generace GSM. V budovách je v současnosti bezdrátová komunikace založena především na wi-fi (WLAN) sítích, rozšířený je standard IEEE 802.11b. V současnosti existují tři základní metody, jak určit pozici uživatele v bezdrátové síti: a) Metoda triangulace, která vyžaduje nejméně tři jednoznačné odhady vzdálenosti mobilní stanice od známých pevných bodů. Tyto odhady mohou být získány z časů nebo z časových rozdílů příchodu signálu nebo ze síly přijatého signálu, pokud předpokládáme, že výkonová úroveň přijatého signálu (dále jen RSS – Received signal strengh) klesá úměrně vzdálenosti. b) Použití směru nebo úhlu příchodu signálu (dále jen AOA – Angle of arrival) nejméně dvou různých signálů ze známých bodů. c) Metoda „otisku signálu“ (location fingerprint). Ta spočívá ve vytvoření databáze otisků určité charakteristiky signálu, která je závislá na poloze mobilní stanice. Touto charakteristikou bývá nejčastěji RSS. Další možnou charakteristikou poskytovanou sítěmi WLAN je poměr SNR (Signal to Noise Ratio – odstup signálu od šumu). Ten má ovšem nižší míru korelace se vzdáleností od AP (Acces Point – přístupový bod sítě WLAN). Tato databáze je pak porovnána s konkrétním otiskem MS, jejíž polohu chceme získat. Lze se setkat i s jinými charakteristikami signálu, například zpoždění signálu způsobené vícecestným šířením [1]. Taková technika ovšem vyžaduje specializovaný hardware na každé základnové stanici (BS – Base station) nebo přístupovém bodu (AP – Access point). Naproti tomu RSS je v sítích WLAN snadno získatelnou veličinou, kterou už AP stejně měří. Nejpoužívanější metodou pro lokalizaci v sítích WLAN je metoda otisků signálu, a to především pro svou snadnou implementaci. Základním problémem této metody je vytvoření databáze otisků. Možnosti existují v zásadě dvě a) Vytvoření databáze měřením. Tento způsob je považován za spolehlivější a přináší větší přesnost [2]. Její nevýhodou je náročnost tohoto měření a nutnost jeho opakování při změně dispozic sledovaného prostoru. b) Získání databáze pomocí empirického modelu šíření. Toto řešení vyžaduje poměrně přesná vstupní data pro vytvoření modelu a přesto přináší horší výsledky, než když databázi získáme měřením. To je způsobeno velice komplikovaným šířením radiového signálu v budovách – odrazy, vícecestné šíření. V této práci bude nejprve uveden přehled metod lokalizace v bezdrátových sítích obecně a poté konkrétně v sítích WLAN. Cílem simulace je pak ověřit možnost vytvoření databáze otisků pomocí empirického modelu šíření. [1], [2]
1.2 Přehled metod lokalizace v bezdrátových sítích 1.2.1 Satelitní navigační systém GPS Satelitní navigační sytém GPS (Global position system) je navigační služba vyvíjená ministerstvem obrany Spojených států amerických od roku 1973. V průběhu let se systém dále vyvíjel a rozšiřoval a začátkem 90. let se stal plně funkčním a dostupným po celém světě. Potenciál a možnosti systému GPS ukázaly na rozšíření využití systému v mnoha oborech lidské činnosti. Kongres Spojených států schválil výnos o využití systému GPS i v civilní sféře. Pro omezení zneužitelnosti systému na minimální úroveň (např. pro teroristické účely) a zabezpečení prvořadosti vojenských aplikací bylo až do 1. 5. 2000 provozováno několik opatření, mimo jiné selektivní dostupnost (Selected Availibility) – záměrné zhoršování přesnosti určení polohy nebo zavedení tzv. přesného P/Y – kódu, kterým je šířen signál pouze pro vojenské aplikace. V součastné době je již záměrné zhoršování polohy vypnuté. Díky tomu se pro civilní uživatele téměř 10-ti násobně zvýšila přesnost určení polohy. Celý systém GPS lze rozdělit do 3 podsystémů: kosmický, kontrolní a uživatelský. Kosmický podsystém je v současné době tvořen 24 družicemi, z čehož 3 slouží jako záložní. Ty krouží kolem Země ve výšce přibližně 20 000 km na 6 oběžných drahách skloněných vždy o 60 stupňů. Každá družice je vybavena přijímačem, vysílačem, atomovými hodinami a řadou přístrojů, které slouží pro navigaci nebo jiné speciální úkoly (kupř. pro detekci výbuchu jaderných náloží). Družice přijímá, zpracovává a uchovává informace předávané z pozemního řídícího centra, na základě kterých koriguje svoji dráhu raketovými motorky, dále sleduje stav vlastních systémů a podává o těchto skutečnostech informace zpět do řídícího centra. Samotný princip určování polohy systémem GPS je následující: družice vysílá signály pro uživatele v podobě složitého signálu. Každá družice vysílá zprávy o své poloze a přibližné polohy ostatních družic systému. K určení aktuální polohy váš přijímač počítá tzv. pseudovzdálenosti, což jsou vzdálenosti mezi vaším přijímačem a viditelnými družicemi (nad obzorem). Výpočet pseudovzdálenosti vychází ze znalosti rychlosti šíření družicového signálu a rozdílu času mezi vysláním a příjmem signálu. Termín pseudovzdálenost se zavádí proto, že je nutné zavádět další doplňující výpočty, které určení výsledné polohy dále zpřesňují. Pro určení dvojrozměrné polohy (nejčasněji zeměpisná délka a šířka) postačí příjem signálu ze tří družic (výpočet tří pseudovzdáleností), pro určení trojrozměrné polohy (navíc výška) minimálně ze čtyř družic. Příjem menšího počtu družic znemožňuje výpočet polohy, vyšší počet družic naopak určení polohy dále zpřesňuje. Řídící podsystém monitoruje funkce družic a získané údaje předává zpět družicím. Řídící podsystém tvoří hlavní řídící stanice v Colorado Springs, 5 monitorovacích stanic a 3 pozemní řídící stanice, které spolupracují s hlavní řídící stanicí. Cílem celého řídícího podsystému je monitoring funkcí každé družice, sledování a výpočet dráhy družice, komunikace a zajištění přesného chodu atomových hodin na družicích. V současné době existuje několik nezávislých monitorovacích sítí, které umožňují další přesnější určování polohy, především pro velmi přesné aplikace (geodézie, geodynamika). Tyto sítě se nepodílejí na řízení a činnosti systému GPS. Uživatelský podsystém: pro příjem a zpracování GPS signálů byly vyvinuty speciální přijímače. Kromě speciálních přijímačů určených pro vojenské aplikace, existuje dnes řada dalších typů GPS přijímačů. Na podobném principu jako GPS jsou založeny i systémy vyvinuté v Evropské unii Galileo a ruský Glonnas, nejsou však zdaleka tolik rozšířené. Satelitní navigační systémy obecně vykazují vysokou přesnost v přírodě a otevřených prostorech, a to až do 10 metrů. Jsou však nepoužitelné v městské zástavbě a přímo ve vnitřních prostorách, protože jakékoliv zastínění již tak slabého satelitního signálu vede k jeho výpadku. [3]
Obr. 1 – umístění monitorovacích a pozemních řídících stanic
1.2.2 Lokalizace v sítích GSM Prakticky všechny systémy mobilních sítí včetně systému GSM rozdělují území na buňky obsluhované jednotlivými základnovými stanicemi (BTS). Nejhruběji můžeme polohu mobilního telefonu určit, pokud víme, ke které základnové stanici je připojen. Existuje však i přesnější lokalizační metoda CGI+TA (cell global identity + timing advance). Ta využívá faktu, že základnové stanice vysílají v sektorech (mají podobu kruhové výseče). Pokud víme, se kterou sektorovou anténou mobilní telefon komunikuje, známe zhruba směr, ve kterém se od BTS nachází. Na jednotlivých kanálech sítě GSM se ve vysílání rychle periodicky střídá více telefonů. Jednotlivé telefony musí vysílat s proměnlivým předstihem, aby jejich vysílání nedorazilo na základnovou stanici pozdě a nekolidovalo s vysíláním dalšího telefonu v řadě. Pro každý mobil v síti GSM se proto průběžně kalibruje hodnota TA (timing advance, časový předstih). Z hodnoty TA a rychlosti šíření radiového signálu můžeme změřit vzdálenost telefonu od základnové stanice s přesností 550 metrů. Pokud tedy známe polohu základnové stanice, směr osy sektoru a vzdálenost mobilu od BTS, pomocí metody CGI+TA určíme jeho podobu. Méně často jsou využívány náročnější metody UL-TOA a E-OTD, které vyžadují speciální aplikaci SIM Toolkit a její podporu ze strany telefonu. Aplikace se dotazuje okolních BTS na jejich polohu a vzdálenost telefonu a získané informace zašle do vyhodnocovacího centra, které mu obratem poskytne informaci o vypočítané poloze. Zjednodušeně si tyto pokročilejší metody lze představit, jako bychom se nacházeli uprostřed "překřížení" dvou či více pásem, kde se podle údajů jednotlivých BTS nacházíme. Přesnost metod UL-TOA a E-OTD kolísá mezi 60 až 200 metry podle hustoty zástavby. [4]
Obr. 2 – Sektorizace sítě GSM
1.2.3 Active Badge system Active Badge system je jeden z prvních systémů pro lokalizaci v budovách, založený na infračerveném světle. Mobilní stanice vysílá periodicky nebo na vyžádání unikátní infračervený signál.
Ten je snímán senzory rozmístěnými po budově a poté předáván do hlavní stanice, kde je dále zpracován. Tento systém poskytuje poměrně přesnou informaci o poloze, ale je limitován použitím na přímou viditelnost, poskytuje špatné výsledky při přímém slunečním světle. [5]
Obr.3 – Olliveti Active Badge (vlevo) a základnová stanice (vpravo)
1.2.4 Active Bat location system Active Bat location system byl vyvinut na univerzitě v Cambridgi v AT&T Laboratories a používá kombinaci radiového a ultrazvukového signálu pro odhad vzdálenosti. Přes řídící PC se vyšle na frekvenci 433 MHz požadavek na mobilní přístroj – Active Bat, ten pak reaguje vysláním ultrazvukových pulsů vyslaných na matrici senzorů umístěných na stropě místnosti. V ten samý okamžik PC pošle synchronizační signál k detektorům přes datovou síť. Senzory tak mohou pomocí doby letu signálu na známé ultrazvukové frekvenci spočítat vzdálenosti Active Bat - senzor, ze kterých lze pak triangulací určit umístění přístroje. Tato metoda vyžaduje umístění masivní infrastruktury na stropě místnosti a přesnost lokalizace, která může dosáhnout až 9 cm (a to třírozměrně), je velice citlivá na precizní umístění senzorů. [6]
Obr. 4 – Mobilní zařízení systému Active Bat
1.2.5 Cricket Je založen na podobném principu jako Active Bat location systém, používá kombinaci kontrolního radiového a meřícího ultrazvukového signálu. Rozdílem je, že veškeré operace nutné pro lokalizaci probíhají přímo na straně mobilní stanice, nejedná se tedy o systém, který by sledoval polohu uživatele a tuto informaci ukládal v nějaké centrální databázi. V každé místnosti budovy se nachází malé signální zařízení (beacon), které při každém cyklu vyšle radiový a ultrazvukový puls. Přijímač umístěný na mobilní stanici při příjmu radiového signálu zapne svůj ultrazvukový přijímač, kterým přijme následný ultrazvukový puls. Na základě časového rozdílu mezi prvními bity radiového signálu a příchodu ultrazvukového pulzu přijímač vyhodnotí vzdálenost od signálního zařízení.
Vlastnostmi sítě Cricket jsou soukromí uživatele, decentralizované řízení, heterogenita sítě a rozlišení přibližně 1.25 m.
2 Lokalizace v sítích standardu IEEE 802.11 2.1.1 Microsoft Research RADAR location system Tento systém využívá již existující struktury standardu 802.11 pro lokalizaci mobilní stanice. V [2] je popsán systém nazvaný RADAR. Skládá se ze tří stolních počítačů sloužících jako AP a laptopu, který funguje jako mobilní stanice, jejíž pozice se určuje. Tři AP měří RSS od klientské MS. Jedná se o systém vzdálené lokalizace, kde pozici MS určuje centrální počítač. Získaná data jsou pak porovnávána s databází, která je naplněna podobným měřením provedeným MS v pevně stanovených známých bodech. Pro lepší přesnost jsou hodnoty v databázi získané průměrováním z několika měření. Ve výsledku jsou hodnoty RSS od tří AP použity jako otisk signálu. V tomto systému může být problémem soukromí klienta, protože informace o poloze jsou získávány, i když o tom klient neví nebo si to dokonce nepřeje. Střední hodnota (medián) chyby určení polohy byla 2.94 metru Autoři systému RADAR ukázali, že pro vytvoření databáze otisků je možné použít i empirického modelu šíření. K vytvoření databáze byl použit Wall Attenuation Factor model popsaný následujícími rovnicemi:
⎛ d ⎞ ⎧nW ⋅WAF nW < C P ( d ) [ dBm ] = P ( d 0 ) [ dBm] − 10n log ⎜ ⎟ − ⎨ ⎝ d 0 ⎠ ⎩C ⋅WAF nW ≥ C
P ( d0 ) je výkon ve známé referenční vzdálenosti, d je vzdálenost vysílač – přijímač, C je maximální počet zdí, pro který je ještě rozdíl v útlumu významný, nW je počet zdí mezi vysílačem a přijímačem a WAF je útlum zdi. Hodnoty proměnných závisí na prostředí, autoři volili C = 4 , WAF = 3dB , n = 1.76 a P ( d 0 ) = 64.94dB . Bylo dosaženo horších výsledků než při použití databáze získané měřením, se střední chybou 4.3 metru ve stejném testovacím prostoru. Experimenty v systému RADAR proběhly pouze v relativně otevřených prostorách na jednom patře, kde je RSS poměrně stabilní a silná. Problémem ve trojrozměrném prostředí (myšleno více pater) je, že dva nebo více bodů s velice odlišnou polohou mohou mít stejný otisk signálu. V některých pracích proto byly jako otisk signálu použity jeho pravděpodobnostní charakteristiky. Tento přístup vede k podobným výsledkům jako použití RSS. [7]
2.1.2 Základní problémy lokalizace v sítích WLAN Jak už bylo řečeno, lokalizace v sítích WLAN se skládá ze dvou fází. Prvním krokem je vytvoření databáze otisků signálu – offline fáze, druhým krokem pak porovnávání měřeného signálu se získanou databází – online fáze. V literatuře lze nalézt tři základní používané způsoby vytvoření databáze a následné vyhledávání v ní. Nejjednodušší a nejpoužívanější metodou je M nearest neighbors metod, která pracuje s euklidovskou vzdáleností v signálovém prostoru. V offline fázi se získají otisky signálu pro databázi, a to buď měřením nebo použitím modelu šíření. Při samotné lokalizaci pak porovnáváme s databází změřený bod. Vzdálenost vektorů ρ a r je 1
⎡N 2 ⎤2 Z = ⎢ ∑ ( ρi − ri ) ⎥ ⎣ i =1 ⎦
V online fázi hledáme mezi vektory databáze ρ ten, který má nejmenší vzdálenost Z od změřeného vektoru r . Ten je pak hledanou pozicí mobilní stanice. Nebo je možné vybrat M bodů s nejmenší vzdáleností a z nich pak průměrováním odhadnout pozici MS. Je nutné zdůraznit, že vzdálenost v signálovém prostoru není to samé, co fyzická vzdálenost bodů, kterým tyto vektory odpovídají.
Dalším přístupem je vyhledávání vycházející ze znalosti pravděpodobnostních charakteristik signálu. Pro jejich získání je nutné buď opakované měření v každém z bodů databáze nebo vhodný empirický model. Pokud máme k dispozici tyto charakteristiky, můžeme pracovat s pravděpodobnostními funkcemi a získat tak polohu MS. Podrobněji je tento postup popsán v [8]. Perspektivním přístupem je použití neuronových sítí v lokalizaci. Tyto sítě se učí jednak na základě určitého počtu trénovacích bodů, které je nutno zadat při nastartování systému, ale také dále při samotném provozu. Bylo dosaženo velice dobrých výsledků se střední hodnotou chyby určení polohy 2.3 metru [9]. Ve své práci se dále zaměřím na metodu hledání minimální vzdálenosti v signálovém prostoru. Pokud se rozhodneme získat databázi pro tuto metodu, první otázkou na kterou narazíme bude hustota sítě. Musíme najít optimální rozteč mezi jednotlivými body databáze (většinou se jedná o ekvidistantní pravoúhlou síť). Příliš malá rozteč jednak drasticky zvyšuje dobu vyhledávání při získávání databáze i samotné lokalizaci, ale rozhodně nemusí vést k výraznému zlepšení přesnosti. Blízké body totiž mají velmi podobné otisky signálu a může dojít k jejich snadné záměně. Naopak při příliš velké rozteči sítě může dojít ke zhoršení přesnosti. Používané rozteče se pohybují mezi 1.5 až 5 metry. Při vyhodnocování pozice MS narazíme především na problém kolísání signálu. To je způsobeno komplikovanou povahou šíření radiového signálu, měnícím se prostředím – především pohybem osob a různým natočením antény MS. Zvláště v oblastech relativně vzdálených od AP je rozdíl RSS na několika metrech jen jednotky dB, což je méně než útlum způsobený lidským tělem. Kolísání signálu lze částečně eliminovat opakovaným měřením, pokud se nejedná o pohybující se objekt, vliv natočení antény AP však představuje vážný problém.
3 Simulace Pomocí simulace v Matlabu jsem se pokusil analyzovat vlastnosti databáze otisků signálu vytvořené pomocí empirického modelu šíření. Pro vyhodnocení vlastností tohoto modelu je nutno získat skutečná data ve studovaném prostoru. Provést měření síly signálu je poměrně náročné na přesnost provedení, navíc je vhodné mít jako testovací lokalitu poněkud rozlehlejší prostory, než je například 6. patro budovy ČVUT FEL. Proto bylo původním záměrem pro získání „naměřených“ dat použít program XY. Tento program využívající pro model šíření elektromagnetických vln metodu ray tracingu byl vyvinut Ing. Martinem Klepalem. Při přesném zadání vstupních dat do programu se úroveň signálu získaná tímto modelem odlišuje od skutečnosti pouze nepatrně. Konkrétně v šestém patře ČVUT FEL o jednotky decibel. Na začátku práce jsem ovšem narazil na nutnost přesně analyzovat základní příčiny chyb v lokalizaci. To lze provést i při modelování v otevřeném prostoru. Výstupem práce je tedy analýza metody lokalizace M-Nearest Neighbor provedená za pomoci empirického modelu šíření.
3.1 Matematický model Pro výpočet útlumu signálu ve vzdálenosti d byl použit empirický one-slope model.
⎛d ⎞ L ( d ) = L0 ( d 0 ) + 10 ⋅ n ⋅ log ⎜ ⎟ ⎝ d0 ⎠ Kde L0 ( d0 ) je útlum v referenční vzdálenosti od vysílače a n spádový koeficient. Ten je pro volný prostor roven 2, uvnitř budov mimo přímou viditelnost pak 4 – 6. Volil jsem testovací prostor o rozměrech 100x100 metrů, ve kterém jsem umístil AP, vytvořil databázi otisků signálu a poté zkusil lokalizovat určitý počet bodů rozmístěných v testovacím prostoru. Při tomto postupu jsem měl několik stupňů volnosti. •
Počet a rozmístění AP. Použil jsem 4 přístupové body sítě WLAN a analyzoval jsem dvě rozmístění – v rozích prostoru a uprostřed stran. Při volbě souřadnicového systému <x,y> s počátkem v levém spodním rohu byla umístění AP následující: <1,1>, <1,99>, <99,1>, <99,99> při rozmístění AP v rozích a <1,50>, <50,1>, <50,99>, <99,50> při umístění podél stran. Předpokládal jsem, že antény AP jsou všesměrové.
Obr. 5 – rozmístění AP v testovacím prostoru • • •
•
Rozteč sítě databáze. Volil jsem rozteč pohybující se mezi 1 a 20 metry s krokem jeden metr. Vliv rozteče sítě na chybu lokalizace byl předmětem zkoumání. Hodnota spádového koeficientu n. Volil jsem dvě hodnoty 2 a 4, které odpovídají šíření ve volném prostoru a v budově (mimo přímou viditelnost) Algoritmus vyhledávání v databázi. Použil jsem metodu M-nearest neighbor pracující s euklidovskou vzdáleností v signálovém prostoru. Volil jsem M 1 (1 bod) a 4 (průměrování) a sledoval, zda dochází ke zmenšení chyby při použití průměrování ze 4 bodů. Fluktuace výkonové úrovně signálu. Při vyhledávání pozice mobilní stanice jsem přičetl k otisku signálu náhodný signál s gaussovským rozložením s parametry střední hodnota 0 a variance 1,3 a 5 dB.
• •
Výkonové kalibrace modelu databáze. Analyzoval jsem situaci, kdy dojde ke změně úrovně vysílaného výkonu, se kterou databáze nepočítá. K RSS v hledaném bodě jsem přičetl konstanty 1,3,5 a 10 dB. Frekvence. V celé práci jsem předpokládal lokalizaci na frekvenci 2,44 GHz, na které jsou provozovány systémy standardu IEEE 802.11b.
3.2 Získané hodnoty Pro dané parametry jsem vždy provedl lokalizaci u 500 testovacích bodů. Jak pro otisk signálu bodů databáze, tak pro výpočet RSS testovacích bodů jsem použil popsaný one slope model. Testovací body byly náhodně generovány vždy znovu pro nové uspořádání. U každého z bodů jsem vyhodnotil chybu – odchylku odhadnuté odhody od přesné hodnoty. Pro daný soubor 500 bodů jsem pak vyhodnotil statistické parametry průměrná chyba, medián a maximální chyba. Pro určitá nastavení jsem vyhodnotil polohu 20 bodů s největší chybou.
3.2.1 Výsledky bez vlivu fluktuací Uvádím pouze tabulku v jedné konfiguraci tvorby databáze, kompletní výsledky jsou uvedeny v příloze. V ostatních konfiguracích nedochází k významným odchylkám výsledků. delta L mean median max
1 0,43 0,4 2,63
2 0,88 0,81 4,6
3 1,33 1,2 7,86
4 1,83 1,7 7,92
5 6 7 8 9 10 11 12 13 14 15 2,24 2,83 3,14 3,57 4,1 4,38 4,8 5,08 5,92 6,1 6,55 2,06 2,6 2,86 3,3 3,77 4,22 4,57 4,76 5,61 5,65 6,24 7,68 10,02 11,62 13,79 14,31 12,16 15,88 18,33 19,89 19,47 21,49
Tab. 1 – AP podél stran, n = 2, 1 bod Dle intuitivního očekávání roste chyba s roztečí sítě, její střední hodnota se pohybuje kolem hodnoty L / 2 , při vyšších hodnotách rozteče je pak ještě o něco menší. Zajímavé je spíše to, že se vyskytují chyby, jejichž hodnota přesahuje více jak dvakrát rozteč sítě. Proč tomu tak je? RSS se dle použitého modelu velmi silně mění v blízkém okolí AP, ve větší vzdálenosti už není útlum tolik výrazný. Při hledání minimální vzdálenosti v signálovém prostoru procházíme databázi, která má konečnou hustotu. Pokud hledaný bod bude v těsné blízkosti jednoho AP, a tedy velmi daleko od ostatních AP, vzdálenost v signálovém prostoru bude záviset především na vzdálenosti RSS od blízkého AP, protože RSS od vzdálených AP budou v rozmezí několika metrů okolo testovaného bodu velmi podobné. Při poloze testovaného bodu relativně daleko od bodů sítě (ve vzdálenosti okolo L / 2 ) může být rozdíl RSS od blízkého AP v testovaném bodě a nejbližším bodě databáze i 10 dB. To pak vede k naprosto chybnému vyhodnocení. Je to dokumentováno v Obr. 6.
Obr. 6 – Poloha 20 bodů s největší chybou, AP v rozích
3.2.2 Zanesení fluktuací do signálu Zásadní otázkou při lokalizaci je, jak je systém citlivý na fluktuace signálu, ke kterým musí nutně docházet, a zda je možné určitým uspořádáním chybu zanesenou těmito fluktuacemi minimalizovat. Jak je ukázáno v následujících grafech (Obr. 7 a Obr. 8), při fluktuacích s variancí 1 dB lze ještě dosáhnout velice dobrých výsledků, při hodnotě variance 3 a zvláště 5 dB už jsou výsledky dosti špatné. Především už hodnota průměrné chyby neroste s roztečí sítě. Dalším důležitým poznatkem je skutečnost, že na fluktuace signálu je citlivější prostředí se spádovým koeficientem n = 2. To je způsobeno velmi pomalu klesající úrovní RSS ve větších vzdálenostech od AP. Rozdíl RSS v bodech vzdálených několik metrů pak je menší, než může být velikost fluktuace. V případě spádového koeficientu n = 4 je tato chyba menší. To vede k domněnce, že při vytvoření dostatečně přesného modelu je lokalizace v hustých prostorách paradoxně snadnější, než v otevřeném prostoru. Problémem a výzvou pro další práci samozřejmě zůstává získání takového modelu a jeho aplikace v daném prostoru. Použití metody jednoho bodu nebo průměrování a poloha AP nemá tak zásadní vliv na chybovost lokalizace při zanesení fluktuací do signálu. Přesto lze říci, že průměrování mírně zlepší funkci systému oproti použití nejbližšího bodu, řádově podobné zlepšení pak pro lokalizaci přinese rozmístění AP podél stran oproti umístění v rozích. Rozdíl v hodnotě střední chyby mezi konfiguracemi <AP podél stran, průměrování> a <AP v rozích, 1 bod> při hodnotě variance 3 dB je přibližně 1,5-2 metry. Podrobnější údaje lze vysledovat z přílohy. 30
25
Chyba[m]
20 Noise=0 Noise=1
15
Noise=3 Noise=5
10
5
0 0
2
4
6
8
10
12
14
16
18
20
Rozteč[m]
Obr. 7 – závislost průměrné chyby na varianci přidaného signálu, n = 2, AP v rozích, průměrování
20
Chyba[m]
15
Noise=0 Noise=1
10
Noise=3 Noise=5
5
0 0
2
4
6
8
10
12
14
16
18
20
Rozteč[m]
Obr. 8 – závislost průměrné chyby na varianci přidaného signálu, n = 4, AP v rozích, průměrování
3.2.3 Výkonová kalibrace systému Posunutí výkonové úrovně v systému má podobně jako fluktuace signálu špatný vliv na chybovost lokalizace, a to výrazněji při hodnotě spádového koeficientu n = 2. Oproti přičtení náhodného signálu se přičtení konstanty projeví velmi výrazně už při malých hodnotách této konstanty. Při reálné implementaci bude nutné se s tímto problémem vyrovnat formou jisté kalibrace. Tu bude možné provést například z hodnot RSS mezi jednotlivými AP. Přidání aditivní konstanty 30
25
Chyba[m]
20 AD = 1 dB AD = 3dB
15
AD = 5 dB AD = 10 dB
10
5
0 0
2
4
6
8
10
12
14
16
18
20
Rozteč[m]
Obr. 9 – závislost průměrné chyby hodnotě přičtené chyby, n = 2, AP podél stran, průměrování
Přidání aditivní konstanty 20 18 16
Chyba[m]
14 AD = 1 dB
12
AD = 3dB
10
AD = 5 dB
8
AD = 10 dB
6 4 2 0 0
2
4
6
8
10
12
14
16
18
20
Rozteč[m]
Obr. 10 – závislost průměrné chyby hodnotě přičtené chyby, n = 4 AP podél stran, průměrování
3.2.4 Vliv rozteče databáze V optimálním případě skutečně platí intuitivní předpoklad, čím hustší síť, tím přesnější lokalizace. Při zanesení reálných chyb (fluktuace, posun) do měřeného signálu však toto již neplatí. Při hodnotách L mezi 1 a 5 metry dostáváme velmi podobné výsledky chyby určení polohy. Za roztečí 5 metrů již nastává zlom. Samozřejmě záleží na aplikaci, v níž budeme lokalizaci používat, na základě této práce bych však volil jako optimální pro poměr přesnost/ náročnost vyhledávání rozteč 4 nebo 5 metrů.
3.3 Implementace v Matlabu Program použitý v semestrální práci lze rozdělit do čtyř fází. V první části jsou definovány všechny proměnné. Těmi jsou frekvence, velikost prostoru, rozteč sítě, pozice a počet jednotlivých AP, vysílaný výkon, spádový koeficient, počet testovaných bodů, počet bodů pro algoritmus vyhledávání (M), variance přidaného šumu, velikost aditivní konstanty. V druhé části je byla vytvořena databáze otisků signálu na základě zvoleného modelu, parametry této databáze jsou rozteč databáze, pozice AP, frekvence, spádový koeficient a vysílaný výkon. A dále si je nutno získat databázi „skutečně změřených“ signálů ve zvoleném počtu testovacích bodů. Ta je vytvořena také na základě empirického modelu, dále je ke každému bodu přičten šum a aditivní konstanta. Následuje porovnání „změřených“ bodů s body v databázi. Pro každý z testovacích bodů je vyhodnocena vzdálenost v signálovém prostoru od všech bodů databáze. Určená poloha testovacího bodu pak odpovídá v závislosti na algoritmu vyhledávání bodu databáze s nejmenší vzdáleností v signálovém prostoru, případně geometrickému středu M bodů s nejmenší vzdáleností v signálovém prostoru. V závěru jsou spočteny kvalitativní parametry provedené simulace, hledá se chyba určení polohy (tedy vzdálenost mezi skutečnou a určenou polohou testovacího bodu) pro každý z testovacích bodů a dále se určují statistické parametry na souboru všech testovacích bodů – průměrná hodnota, medián a maximální chyba. Je možné nechat si vykreslit některé grafy, například polohu dvaceti bodů s největší chybou a velikost této chyby. Pro rychlejší práci jsou body dva až čtyři opakovány v cyklu, při každém opakování se zvyšuje hodnota rozteče databáze.
4 Závěr V semestrální práci jsem se seznámil se současnými metodami lokalizace v bezdrátových sítích obecně a poté podrobně v sítích standardu IEEE 802.11. Zanalyzoval jsem metodu lokalizace metodou otisku signálu, přičemž databázi jsem vytvořil pomocí empirického one slope modelu šíření. Oproti původnímu očekávání a zadání jsem simulaci lokalizace provedl pouze ve volném, prostoru, protože bylo nutné podrobně prozkoumat mechanismy vzniku chyb při lokalizaci. Z analýzy vyplývají následující závěry: Zjistil jsem, že i v naprosto optimálním případě, kdy máme vytvořenou databázi shodující se se skutečnými daty, dochází v některých případech k relativně velké chybě určení polohy. To je způsobeno značně odlišným průběhem útlumu signálu v blízkosti AP a daleko od něj. Při konečné rozteči sítě pak může při lokalizaci bodu nacházejícího se blízko AP dojít k chybě určení polohy. Fluktuace signálu mají značný vliv na chybu určení polohy. Uvažoval jsem fluktuace s charakterem náhodného signálu s gaussovským rozložením. Už při hodnotě variance 3 dB dochází k zásadnímu znehodnocení výsledků. Větší vliv mají fluktuace v prostředí s nízkým útlumem, protože zde i relativně vzdálené body mají podobnou hodnotu RSS. Při reálné aplikaci bude patrně možné se s fluktuacemi částečně vyrovnat opakovaným měřením, pokud budeme chtít určit polohu dočasně se nepohybující mobilní stanice. Typickým příkladem takové lokalizace může být například určení polohy „pirátsky“ napojené mobilní stanice v podnikové WLAN síti. Celkové posunutí výkonové úrovně signálu oproti databázi má na lokalizaci velmi negativní vliv. Už při posunutí o 1 dB dojde ke zhoršení chyby určení o jednotky metrů. V reálné aplikaci bude nutné provádět kalibraci celého systému. Optimální rozteč databáze záleží na konkrétní aplikaci a na výpočetních možnostech centrální stanice, která provádí vyhledávání. Na základě této práce se jeví jako optimální rozteč okolo 4 metrů. Pro mou další práci je nutné ověřit fungování lokalizace při použití empirických modelů v reálném prostředí. Zde bude jistě nutné brát v úvahu chybu, která vzniká posunutím výkonové úrovně signálu. Dále pak vyvstává několik problémů, na které je možné se zaměřit. Jedním je lokalizace v prostředí s více patry. Realizaci této lokalizace jsem zatím v literatuře nenalezl. Další možností je vytváření databáze otisků signálu pomocí empirických modelů se zaměřením na hledání vhodného modelu, který nebude příliš náročný na přesnost zadání vstupních dat.
5 Literatura [1] [2] [3] [4] [5] [6] [7] [8]
[9] [10]
P. Prasithsangaree, P. Krishnamurthy, and P. K. Chrysanthis; „On Indoor Position Location With Wireless LANs“; The 13th IEEE International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC 2002), Lisbon, Portugal, September 2002 Paramvir Bahl, Venkata N. Padmanabhan; „RADAR: An In-Building RF-based User Location and Tracking System”; IEEE Infocom 2000, volume 2, pages 775-784, March 2000. P. Svatoš; „GPS – stránka o satelitní navigaci“; http://gps.slansko.cz/ Použití GSM lokalizace v logistice, http://www.systemonline.cz/site/bez/04_09tieto.htm Roy Want, Andy Hopper, Veronica Falcão, Jonathan Gibbons; “The Active Badge Location System”; ACM Transactions on Information Systems, Vol. 10, No. 1, January 1992, pp 91102 Andy Ward, Alan Jones, Andy Hopper; „A New Location Technique for the Active Office“; IEEE Personal Communications Vol. 4, No. 5, October 1997, pp. 42-47 P. Myllymaki, T. Roos, H. Tirri, P. Misikangas, J. Sievanen; „A Probabilistic Approach to WLAN User Location Estimation“; The Third IEEE Workshop on Wireless LANs, 2001 Andrew M. Ladd, Kostas E. Bekris, Algis Rudys, Guillaume Marceau, Lydia E. Kavraki, Dan S.; „Robotics-Based Location Sensing using Wireless Ethernet“; The Eighth ACM International Conference on Mobile Computing and Networking (MOBICOM) (Atlanta, GA), September 2002 Roberto Battiti, Thang Lee Nhat, Alessandro Villani; „ Location-aware computing: a neural network model for determining location in wireless LANs“; Technical Report DIT-02-0083, 2002 M. Klepal, P. Pechač; „Wide-band indoor propagation prediction by Motif model“; In: 10th Aachen Symposium on Signal Theory - Algorithms and Software for Mobile Communications - September 2001, Aachen, Germany