TETRA 060106
Locatie Afhankelijke Diensten - Wireless Technology for Positioning Applications (LADI WITEPA)
Case study: Nauwkeurigheid van dynamische RSS-based indoor plaatsbepalingssystemen Technieken en technologie¨ en voor plaatsbepaling
DraMCo
[email protected] 10 juli 2008
1
1
Inleiding
Er bestaan verschillende methoden om aan plaatsbepaling te doen[1]. Een onderscheid kan gemaakt worden tussen enerzijds de grootheden die gemeten worden (de technologie¨en) en anderzijds de manier waarop die grootheden aangewend worden om een locatie te berekenen (de technieken). Tabel 1 toont een overzicht van de verschillende technologie¨en en de technieken die daarbij kunnen gebruikt worden. De voornaamste ervan worden in de volgende paragrafen kort besproken. De mogelijke plaatsbepalingstechnieken kunnen niet enkel verschillen in de technologie die gebruikt wordt, maar ook in de manier waarop de gegevens verwerkt worden. Zo kan het onderscheid gemaakt worden tussen gecentraliseerde en gedecentraliseerde technieken. T echnieken Fingerprinting/radiomap Signpost Trilateratie/multilateratie Statistische technieken vb. MLE1
T echnologie¨ een RSS RSS RSS TOA AOA RSS TOA AOA
P laatsbepaling centraal centraal of distributed centraal of distributed centraal
Tabel 1: Overzicht technieken en technologie¨ en Bij de gecentraliseerde technieken worden alle gegevens op ´e´en centraal punt verwerkt. Een passend voorbeeld hierbij is fingerprinting: op een centraal punt wordt een database bijgehouden met de signaalsterkte op verschillende punten. Daartegenover staan de gedecentraliseerde technieken, waarbij meerdere componenten in een netwerk zullen samenwerken. De blinde node bepaalt in dit geval zijn eigen locatie. Wegens de beperkte rekenkracht van de nodes worden hier meestal eenvoudigere technieken zoals multilateratie gebruikt. De meest gebruikte technologie¨en zijn RSS, TOA en AOA of een combinatie. Bij RSS maakt men gebruik van de ontvangen signaalsterkte om een afstand te berekenen. Bij TOA baseert men zich op het tijdsverschil tussen zenden en ontvangen. Bij AOA gebruikt men de hoek waaronder een signaal ontvangen wordt. In de volgende paragrafen wordt de werking van de belangrijkste technologie¨en en technieken uitgelegd. Eveneens worden de voor- en nadelen verduidelijkt.
2
Technologie¨ en
2.1
Received Signal Strength - Ontvangen signaalsterkte
Received signal strength (RSS) is defined as the voltage measured by a receiver’s received signal strength indicator (RSSI) circuit. Often, RSS is equivalently reported as measured power, i.e., the squared magnitude of the signal strength.2 Bij draadloze gegevensoverdracht, voert de ontvanger dus een (al dan niet ruwe) meting uit van het ontvangen vermogen. Dit ontvangen vermogen is voor een groot deel afhankelijk van de afstand tussen zender en ontvanger. 1 2
Maximum Likelihood Estimation N. Patwari, “Location Estimation in Sensor Networks”, p. 22
2
Bij de meeste hardware is zo een RSSI circuit standaard aanwezig en gebeurt de meting van het ontvangen vermogen dus elke keer wanneer er een boodschap ontvangen wordt. Het voordeel is dat hiervoor geen extra bandbreedte moet gereserveerd worden. Het grote nadeel is echter de onnauwkeurigheid van de resultaten. Deze onnauwkeurigheid wordt enerzijds veroorzaakt door het meetsysteem zelf. Dit is namelijk niet expliciet ontwikkeld om accurate vermogenmetingen uit te voeren. Anderzijds zijn er bij indoor radiopropagatie allerhande effecten die het verwachte verband tussen RSS en afstand verstoren. De voor- en nadelen op een rijtje: + snel + geen overhead − onnauwkeurig
2.2
Time-Of-Arrival
Time-Of-Arrival (TOA) is the measured time at which a signal (RF, acoustic, or other) first arrives at a receiver 3 Bij plaatsbepaling op basis van tijd (eigenlijk tijdsverschillen) maakt men gebruik van de eindige propagatiesnelheid van radiogolven4 . De tijd die een signaal nodig heeft om zich voort te planten van een zender naar een ontvanger is immers gerelateerd aan de afstand die het signaal aflegt. Een eerste nadeel wordt onmiddellijk duidelijk. We weten immers dat een tijd van 1 ns overeenkomt met een weglengteverschil van 30 cm. Om een nauwkeurige afstandsbepaling te bekomen, zullen dus klokken met een zeer fijne resolutie moeten gebruikt worden. In praktijk maakt men nog eens onderscheid tussen Time-Of-Arrival, Time-Difference-OfArrival (TDOA) en Two Way Ranging (TWR)5 . Bij TOA meet men het verschil in tijd tussen zenden en ontvangen van een signaal. Deze techniek heeft als bijkomend nadeel dat de klokken perfect gesynchroniseerd moeten zijn. Wanneer een zender dan de zendtijd doorstuurt, kan de ontvanger het tijdsverschil berekenen op basis van de ontvangsttijd. Bij TDOA gaat men iets anders te werk dan bij TOA. Bij TDOA omzeilt men al de nood aan synchronisatie tussen zender en ontvanger. E´en node zal een bericht uitsturen. (Minstens) twee verschillende nodes zullen dit bericht ontvangen. De TDOA is het verschil in aankomsttijd bij de ontvangende nodes. De zender en de ontvanger(s) moeten nu niet meer gesynchroniseerd zijn, want het verschil in aankomsttijd bij de nodes is onafhankelijk van de tijdsbasis van de zender. Enkel de ontvangende nodes (meestal de referentienodes) dienen nu nog gesynchroniseerd te zijn. Bij TWR lost men het synchronisatieprobleem als volgt op: een node (1) stuurt een bericht naar de ontvanger (2) en slaat de zendtijd op. De node 2 stuurt bij ontvangst een antwoord naar node 1. Door de tijd in rekening te brengen, die nodig is om na ontvangst van een bericht een antwoord terug te sturen, kan node 1 dan de afstand tussen beide nodes bepalen. Het is dus belangrijk dat deze “antwoordtijd” nauwkeurig gekend en constant is. Synchronisatie is niet meer nodig omdat alle tijdsmetingen in ´e´en en dezelfde node gebeuren. 3
N. Patwari, “Location Esitimation in Sensor Networks”, p. 26 In vacu¨ um is c = 299.792.458 m/s. Voor de eenvoud gebruiken we c = 3 · 108 m/s 5 Dit wordt soms ook Round-Trip genoemd. 4
3
Een laatste nadeel is dat wanneer er geen Line-Of-Sight (LOS) component ontvangen wordt, de afstandsmeting foutief zal zijn (Figuur 1). Bij het LOS geval zullen 2 versies van hetzelfde signaal in de ontvanger aankomen. De kleinste aankomsttijd (t1 ) wordt genomen voor de afstandsberekening. Deze komt immers overeen met het directe pad tussen zender en ontvanger. In het NLOS geval is er geen LOS component en wordt t2 gebruikt. Dit zal een foutieve afstandsberekening als gevolg hebben. De voor- en nadelen op een rijtje: + nauwkeurig (bij LOS) − klokken met hoge resolutie nodig − synchronisatie (TOA)
2
2
t1
t1
1
1
t2
t2
LOS
NLOS
Figuur 1: LOS en NLOS situatie
2.3
Angle Of Arrival
Wanneer de nodes in een netwerk uitgerust zijn met directieve ontvangstantennes, kan door gebruik te maken van de ontvangsthoek van het signaal (AOA of Angle-Of-Arrival), een positie van de zendende node bepaald worden. Zoals te zien is in Figuur 2 volstaan 2 referentienodes om een eenduidig locatiegebied (p) aan te duiden. Naarmate de ontvangstantenne kleinere hoeken kan onderscheiden, wordt dit gebied (p) kleiner. In combinatie met andere systemen zoals TOA of RSS, volstaat zelfs 1 referentienode om aan vrij precieze plaatsbepaling te doen. Ook deze technologie geeft foutieve resultaten indien er geen line-of-sight bestaat tussen de nodes. Voor- en nadelen op een rijtje: + nauwkeurig (bij LOS) − complexe hardware nodig (directieve ontvangstantennes)
4
p
δ2
δ1 α1
α2
Figuur 2: AOA
3 3.1
Technieken Fingerprinting
Fingerprinting maakt gebruik van een databank met signaalwaarden, opgemeten op verscheidene plaatsen binnen het netwerk, een zogenaamde radio map van het gebouw (Figuur 3). Voor elke referentienode kan zo’n radiomap opgesteld worden. Om de positie van een blinde node te bepalen, vergelijkt men de ontvangen signaalwaarden met deze opgeslagen in de databank. De beste overeenkomst (met alle referentienodes) levert de positie. De grootte van de databank houdt rechtstreeks verband met de nauwkeurigheid van de plaatsbepaling en het aantal referentienodes. Het grootste nadeel van deze methode is het arbeidsintensieve opmeten van de signaalwaarden, die bovendien een momentopname zijn van het netwerk en dus geen rekening houden met mogelijke wijzigingen in het netwerk op het moment van de plaatsbepaling. Andere nadelen zijn de nood aan grotere opslagruimte en zoektijd voor de databank bij een stijgende hoeveelheid metingen en dus nauwkeurigheid. Voor een zeer groot netwerk, met metingen met grote dichtheid zal reeds complexe apparatuur nodig zijn voor (real-time) plaatsbepaling. Deze methode is zowel voor 2 als voor 3 dimensionele plaatsbepaling bruikbaar, waarbij het laatste geval uiteraard een veel grotere databank zal vereisen. Voordeel is dan weer dat, tot op heden, met deze methode de beste nauwkeurigheid voor plaatsbepaling wordt bereikt. K-nearest-neighbour algorithm Deze techniek[2, 3, 4] wordt gebruikt om op basis van de gemeten RSS waarden en de waarden uit de database, een positie te bepalen. Veronderstel dat we de RSS waarden kennen van 3 referentienodes (RSS1 , RSS2 en RSS3 ). Het totale verschil tussen alle waarden uit de database (respectievelijk RSS1′ , RSS2′ en RSS3′ ) kan als volgt berekend worden[5] (euclidische afstand): q ∆RSS = (RSS1 − RSS1′ )2 + (RSS2 − RSS2′ )2 + (RSS3 − RSS3′ )2 5
(1)
∆RSS wordt uitgerekend voor elke entry in de database. De co¨ordinaten van de k dichtste entries uit de database (kleinste ∆RSS) worden gebruikt om de locatie van de blinde node te berekenen (bv. gemiddelde).
Figuur 3: RSS radio map Voor- en nadelen op een rijtje: + nauwkeurigste werkwijze bij RSS − setupfase neemt tijd in beslag − grootte van de database − statisch systeem
3.2
Signpost
Signpost is de eenvoudigste techniek voor plaatsbepaling, maar meteen ook het minst nauwkeurige. Bij deze techniek kijkt men welke referentie node het sterkst ontvangen wordt door de blinde node. De positie van die referentienode wordt eenvoudigweg als positie voor de blinde node genomen. Dit is met andere woorden een sterk vereenvoudigde vorm van fingerprinting. In het voordeel van deze techniek spreekt het zeer lage aantal berekeningen dat dient uitgevoerd te worden, nadeel is de lage precisie van de plaatsbepaling. Wil men een preciezere plaatsbepaling bekomen, dan is men genoodzaakt het aantal referentienodes uit te breiden. Aangezien deze aanpassing enkel het aantal te vergelijken signaalwaarden verhoogt, gaat een verhoogde precisie slechts met een beperkt toegenomen nood aan rekenkracht samen. Een mogelijke toepassing van signpost is lokaalbepaling[6], plaatst men in elk lokaal een referentienode, dan kan men vrij eenvoudig de aanwezigheid van een blinde node in een lokaal vaststellen. Wel dient men rekening te houden met de plaatsing van referentienodes 6
in naburige lokalen, daar een gewone muur de radiosignalen wel zal verzwakken, maar niet volledig absorberen of reflecteren. Het achterliggende principe is zowel bruikbaar voor twee- als voor driedimensionale plaatsbepaling. Voor- en nadelen op een rijtje: + zeer snel + weinig rekenkracht nodig − onnauwkeurig
3.3
Triangulatie/trilateratie
Multilateratie of trilateratie[7], afhankelijk van het aantal gebruikte referentiepunten, is zowat de klassieke manier van plaatsbepaling. Met behulp van de signaalsterktes, omgezet naar afstanden tot ten minste 3 referentienodes, wordt via klassieke driehoeksmeting de positie van de blinde node bepaald. Daar deze berekeningen zelden een eenduidige locatie opleveren, dient via interpolatietechnieken, zoals de kleinste kwadraten methode, de meest waarschijnlijke positie bepaald te worden. Voor tweedimensionale plaatsbepaling is de werkwijze als volgt: Alle afstanden van de blinde node tot de referentienodes worden uitgedrukt in functie van de co¨ordinaten van de blinde node (xb , yb ) en de respectievelijke referentienode. Men gaat er ook van uit dat de eerste referentienode in het punt (0,0) ligt. Voor n referentienodes krijgen we dan het volgende stelsel: r12 = x2b + yb2 r22
(2) 2
2
= (x2 − xb ) + (y2 − yb ) .. .
(3)
rn2 = (xn − xb )2 + (yn − yb )2
(4)
Wanneer men nu van elke vergelijkingen (2) af trekt, bekomt men het volgende stelsel van n-1 vergelijkingen: r22 − r12 = x22 − 2x2 xb + y22 − 2y2 yb .. .
(5)
rn2 − r12 = x2n − 2xn xb + yn2 − 2yn yb
(6)
Na herschikken van de termen kan dit stelsel door deze matrixvergelijking voorgesteld worden: Hp = b Met:
2 x2 y2 K2 − r22 + r12 .. , p = xb , b = 1 .. H = ... . . yb 2 2 2 2 xn yn Kn − rn + r1
7
(7)
en Ki2 = x2i + yi2 . De kleinste kwadraten oplossing (ˆ p) wordt dan gegeven door: pˆ = H T H
−1
HT b
(8)
y
r1 (0,0)
c1
x
r2 p
c2
c3 r3
Figuur 4: Trilateratie Wil men driedimensionale multilateratie toepassen, dan heeft men nood aan ten minste 4 referentienodes. De cirkels worden dan immers bollen en 3 elkaar snijdende bollen hebben 2 gemeenschappelijke punten (in de veronderstelling dat alle afstanden correct berekend zijn). Voor een eenduidige plaatsbepaling is dus een extra bol, dus referentienode nodig. Er dient ook opgemerkt worden dat de 3, respectievelijk 4 referentienodes niet op 1 lijn, respectievelijk in 1 vlak mogen liggen. Voor- en nadelen op een rijtje: + snel en weinig rekenkracht nodig + meest straight-forward techniek − nauwkeurigheid van de plaatsbepaling is afhankelijk van de nauwkeurigheid van de gebruikte afstanden
3.4
Maximum likelihood estimation
Bij maximum likelihood wordt rekening gehouden met de waarschijnlijkheid van de afstandsmetingen door de berekende afstanden te beschouwen als uitkomsten van een kansexperiment. Daar de slow fading kan gekarakteriseerd worden door een normaal verdeelde stochastische variabele6 , zal dit kansexperiment zich eveneens zo gedragen. De normaalverdeling zal verschillen voor elke referentienode 6
Zie tekst over radiopropagatie.
8
3.4.1
Cooperative maximum likelihood
Bij deze techniek wordt uitgegaan van een groot aantal blinde nodes. Deze bepalen hun positie niet enkel t.o.v. de referentienodes, maar ook t.o.v. elkaar. Daar de posities van deze blinde nodes met de nodige onzekerheid gepaard gaan, dient men deze constant aan te passen, tot men een systeem verkrijgt waarbij de posities van elke blinde node met een zo groot mogelijke waarschijnlijkheid overeenkomen met hun re¨ele posities. Het systeem is eveneens bruikbaar voor driedimensionale plaatsbepaling. Het is duidelijk dat deze werkwijze veel rekenkracht vergt. 3.4.2
Massa-veren-systeem
Er bestaat een analogie met een fysisch systeem van massa’s en veren, waarbij elke node wordt voorgesteld door een massa en de gemeten afstanden door een veer met overeenkomstige lengte. Afhankelijk of het een referentienode of een blinde node betreft, zijn de posities van de massa’s gefixeerd of beweeglijk. De massa van een blinde node zal groter zijn naargelang de onzekerheid op zijn metingen kleiner is. Voor- en nadelen op een rijtje: + dynamisch systeem − veel rekenkracht nodig
Figuur 5: Massa veren systeem De veren zullen de massa’s verplaatsen tot het hele systeem in evenwicht is. In het netwerk zullen alle nodes hun meest waarschijnlijke positie bepaald hebben.
3.5
Hop terrein algoritme
Bij deze techniek[8] zendt de blinde node een pakket naar een referentienodes (of omgekeerd). Het aantal hops dat dit pakket aflegt voordat het bij de bestemming aankomt, wordt dan vermenigvuldigd met een zogenaamde “hop metric” om de afstand tussen beide te komen. Vervolgens kan door multilateratie de positie van de blinde node bepaald worden. Deze werkwijze is voorgesteld in Figuur 6. De rode nodes zijn de referentienodes, de groene node is de blinde node. Deze hop metric kan gezien worden als de gemiddelde afstand tussen 2 nodes in het netwerk. De waarde is dus sterk afhankelijk van de topologie van het netwerk. Een topologie waarbij de nodes gelijkmatig verdeeld zijn, zal betere resultaten opleveren dan netwerk met ongelijkmatige spreiding. 9
Voor en nadelen op een rijtje: + bruikbaar bij zeer grote netwerken + geen accumulatie van fouten bij toenemend aantal hops − nauwkeurigheid is afhankelijk van de keuze van de “hop metric”
1 · hop metric
1
3 · hop metric
1 2 3 1
2
2 · hop metric
Figuur 6: Hop terrein localisatie techniek
4
Besluit
In dit hoofdstuk is een overzicht gegeven van de verschillende technieken en technologie¨en die bruikbaar zijn voor plaatsbepaling. Deze case study spitst zich verder toe op dynamische technieken voor plaatsbepaling binnen een vooraf gedefinieerde ruimte. Wegens de beperkte grootte van het netwerk is het hop terrein algoritme niet bruikbaar. Statische technieken zoals fingerprinting en signpost worden niet bestudeerd. De technieken die wel onderzocht zijn (triangulatie en MLE), zijn ontwikkeld voor gecentraliseerde werking. In de rest van deze case study, zal verder gewerkt worden met RSS als technologie. Voor het gebruik van TOA verwijs ik naar de case study over TOA. In het volgende deel (Indoor Radiopropagatie) worden de verschillende effecten bestudeerd die de ontvangen signaalsterkte be¨ınvloeden.
10
Referenties [1] N. Patwari, Location Estimation in Sensor Networks, The University of Michigan, 2005. 1 [2] M. Emmery and M. K. Denko, IEEE 802.11 WLAN based Real-time Location Tracking in Indoor and Outdoor Environments, IEEE, 2007. 3.1 [3] iMPACT, Localization in sensor networking, http://impact.asu.edu/cse534-2004/Sensor Loc.pdf 3.1
[Online]
[4] Wikipedia, K-nearest-neighbour algorithm wikipedia, [Online] http://en.wikipedia.org/wiki/K-nearest neighbor algorithm, 2008. 3.1
Available: Available:
[5] M. Weyn and F. Schrooyen, A wifi assisted gps positioning concept, ECUMICT 2008. 3.1 [6] K. Dhoe and G. Ottoy, Indoor Room Location Estimation, DAS conference, 2008. 3.2 [7] A. T. Ali H. Sayed and N. Khajehnouri, Network-based wireless location, IEEE, 2005. 3.3 [8] S. Adair and B. Sharifi, WSN’s, Positioning Algorithms and Energy Management, [Online] Available: cs.uccs.edu/cs526/studentproj/projS2005/bpsharif/doc/WSN.ppt, 2005. 3.5
11
