Trilateratie in 2D met RSSI signaalsterktes

[Verwijderd]

Ik ben op zoek naar een vergelijking of een algoritme om het middelpunt van drie of meer verschillende punten op een 2D vlak te vinden. Het middelpunt wordt vastgelegd ten opzichte van de andere punten door RSSI waarden of signaalsterktes. Deze signaalsterktes hebben dezelfde schaal en zijn een verhouding ten opzichte van elkaar. Als twee signaalsterktes bv 10 zijn en een derde 20. Dan weet je dat de zenders met signaalsterkte 10 dubbel zo ver staan als deze met 20.

Het probleem is nu dat de signaalsterktes niet uit te drukken zijn in afstand maar enkel en alleen een indicatie geven over de afstand. Dus de formules hier zijn niet juist:
Wikipedia: Trilateration
Hier een excel bestand met wat ik geprobeerd heb: http://dl.dropbox.com/u/246058/trilateration.xlsx

Het zou ook zo moeten kunnen zijn dat de ontvanger buiten de driehoek met zenders ligt. De bedoeling is om met 3 of meerdere wifi accesspoints de locatie van een laptop te bepalen in ideale omstandigheden.

Praktisch heb ik dus drie of meerdere zenders waarvan de x en y coordinaten telkens vastliggen. Met een ontvanger meet ik de signaalsterkte van die drie zenders en wil aan de hand daarvan zijn positie bepalen (x,y).

Hier enkele voorbeeldwaarden:
Zender1: x=10 y=10 Signaalsterkte bij ontvanger=123
Zender2: x=150 y= 50 Signaalsterkte bij ontvanger=65
Zender3: x=60 y = 100 Signaalsterkte bij ontvanger=30

Dit is dus een wiskundig probleem waar ik mijn hoofd al zwaar over gebroken heb maar niet echt weet hoe eraan te beginnen.

Ik weet niet zeker of dit topic hier in het juiste forum staat. Indien dit niet zo is mag deze gerust verplaatst worden. Alvast bedankt voor alle hulp.

[ Voor 8% gewijzigd door Verwijderd op 24-03-2011 09:24 ]

[tonyisgaaf]

Je kan toch dezelfde formules uitdrukken (op je Wikipedia artikel) met een lineaire factor "a" (arbitrair) die een signaalsterkte omzet naar een afstand?

Dus:
r₁ = signaal₁ * a
r₂ = signaal₂ * a
r₃ = signaal₃ * a

Aangezien de signaalsterktes al lineair zijn t.o.v. elkaar en de afstand tot de bron.

En vergeet ook niet dat je de formules op de Wikipedia pagina sterk kunt vereenvoudigen door aan te nemen dat zenders en ontvanger allen in hetzelfde vlak liggen, waardoor z=0 in de vergelijkingen (reduceren tot een 2D i.p.v. een 3D probleem).

[ Voor 24% gewijzigd door tonyisgaaf op 24-03-2011 10:59 ]

[Verwijderd]

Dat zal niet zo goed werken aangezien je met een andere netwerkkaart heel andere signaalsterktes kan meten en dus ook een andere a factor.
In principe moet het doenbaar zijn om zonder die a factor de positie ook te bepalen door te werken met verhoudingen. De vraag is wel hoe.

[.oisyn]

Bedenk dat alle punten die N keer zo ver van punt P afliggen dan dat ze van punt Q afliggen nog steeds een cirkel beschrijven (tenzij N=1, dan is het een rechte lijn precies door het midden van P en Q, loodrecht op lijn PQ).

Het midden van die cirkel ligt op de lijn door PQ. De twee snijpunten van de cirkel met die lijn zijn vrij gemakkelijk te berekenen. Als hij 2 keer zo ver van P af ligt dan van Q dan heeft Q natuurlijk een 2x zo zware weging. De meest voordehandliggende oplossing is dus 1/3P + 2/3Q. In generiekere termen van N wordt dat dus 1/(1+N)P + N/(1+N)Q. De andere oplossing ligt op 1/(1-N)P + N/(1-N)Q. Hier wordt ook meteen duidelijk dat als N=1 er maar 1 oplossing is, aangezien je een deling door nul krijgt voor de 2e oplossing. Het middelpunt van de cirkel ligt natuurlijk precies tussen de twee oplossing in.

Nu je voor een tweetal punten de cirkel (of lijn) kunt bepalen waar je mogelijk bent, kun je trilateratie toepassen op de cirkels van de 3 mogelijke paren PQ, QR en PR. Mocht een van de oplossing een lijn zijn, dan kun je de snijpunten van een lijn met een cirkel uitrekenen.

[ Voor 70% gewijzigd door .oisyn op 25-03-2011 11:24 ]

[.oisyn]

Hoe zit 't hier nou mee?

[Marcj]

Hierover heb ik ooit voor mijn bachelor een paper over geschreven. Hier omschrijf ik ook een algoritme waarin juist de factor tussen signaalsterkte en afstand niet nodig is. Helaas blijkt in de praktijk dat de signaalsterkte veel meer afhankelijk is van de omgeving (bijv. deuren die wel of niet open staan). Daarnaast kun je nog wel andere verbeterslagen toepassen of een getraind algoritme als RADAR gebruiken.

Benchmarking various untrained localization algorithms

ps. Let niet op de kwaliteit, het was mijn eerste paper ooit geschreven. Wel staan er een aantal interessante bronnen in.

[Woy]

Idd, zonder enige extra informatie over de omgeving is locatie bepaling aan de hand van signalen erg onbetrouwbaar. In een open veld gaat het dan nog wel, maar ook daar ben je erg afhankelijk van het type antenne. Een antenne heeft namelijk niet een mooi uniform verdeeld stralingsveld. Het kan dus best voorkomen dat je op 2 meter afstand een beter signaal hebt dan op 1 meter afstand.

[Verwijderd]

Inderdaad ik weet dat het vrij onnauwkeurig kan zijn maar dit maakt nu niet uit.
Is er niemand die een codevoorbeeld of excel heeft staan van trilateratie zonder echte afstanden?

[.oisyn]

Wat is er mis met mijn methode?

[Verwijderd]

Ik heb uw uitleg proberen te begrijpen maar het is mij niet gelukt omdat het zodanig abstract is. Kan je mss snel even een tekening maken van hoe de punten P Q en R juist liggen?
Een cijfervoorbeeld zou ook veel helpen.

[ Voor 10% gewijzigd door Verwijderd op 30-03-2011 15:07 ]

[tonyisgaaf]

Marcj schreef op zondag 27 maart 2011 @ 23:01:
Hierover heb ik ooit voor mijn bachelor een paper over geschreven. Hier omschrijf ik ook een algoritme waarin juist de factor tussen signaalsterkte en afstand niet nodig is. Helaas blijkt in de praktijk dat de signaalsterkte veel meer afhankelijk is van de omgeving (bijv. deuren die wel of niet open staan). Daarnaast kun je nog wel andere verbeterslagen toepassen of een getraind algoritme als RADAR gebruiken.

Benchmarking various untrained localization algorithms

Ik heb je paper gelezen/gescand, maar zie juist dat je daar wél een factor introduceert (f) (§3.4) welke naar mijn idee exáct hetzelfde is als de "a" die ik voorstelde. Nu heb ik absoluut geen wiskundige achtergrond anders dan de standaard calculus/analyse van een opleiding aan een TU, maar zou je me misschien kunnen/willen uitleggen waarin jou oplossing afwijkt van de mijne (anders dan het uitwerken van de vergelijkingen).

Edit: interessante uitkomst trouwens, totaal onverwacht! Ik snap alleen je grafieken niet (figuur 2 t/m 4), naarmate de "error distance" oploopt, neemt de "probability" toe, moet dat niet omgekeerd invers (is dat een Nederlands woord?) zijn?

[ Voor 9% gewijzigd door tonyisgaaf op 30-03-2011 15:23 ]

[Verwijderd]

De oplossing met de factor a lijkt mij inderdaad het beste.
Ik heb dit nu even uitgewerkt (zonder normalisatie met a) en het lijkt te kloppen zolang dat de cirkels groot genoeg zijn zodat ze elkaar snijden.
Als ik nu twee cirkels neem die 100 maal groter zijn dan de derde cirkel, maar de cirkels zijn zeer klein. Dan blijft het gemiddelde van de zogezegde snijpunten nog steeds in het midden van de driehoek.

Is er wiskundig een manier om die a te bepalen zodanig dat je net 1 snijpunt hebt van cirkels?

[.oisyn]

Verwijderd schreef op woensdag 30 maart 2011 @ 15:03:
Ik heb uw uitleg proberen te begrijpen maar het is mij niet gelukt omdat het zodanig abstract is. Kan je mss snel even een tekening maken van hoe de punten P Q en R juist liggen?
Een cijfervoorbeeld zou ook veel helpen.

Ik heb een plot gemaakt met punt P op (0, 0) en Q op (2, 1), dit zijn je zendmasten. Met uitzondering van de lichtgroene lijn zie je alle punten die N keer zover van Q afliggen dan dat ze van P afliggen. N is in de plot van links naar rechts 8 (de rode cirkel), 4, 2, 1 (rechte lijn loodrecht op PQ), 1/2, 1/4 en 1/8. De groene lijn is de lijn door PQ. Je ziet dat het midden van alle cirkels op die lijn liggen. De twee snijpunten van een cirkel kun je berekenen aan de hand van de informatie in m'n vorige post.



Ik heb momenteel niet echt tijd om uitgebreid in detail te treden.

[Marcj]

tonyisgaaf schreef op woensdag 30 maart 2011 @ 15:15:
[...]

Ik heb je paper gelezen/gescand, maar zie juist dat je daar wél een factor introduceert (f) (§3.4) welke naar mijn idee exáct hetzelfde is als de "a" die ik voorstelde. Nu heb ik absoluut geen wiskundige achtergrond anders dan de standaard calculus/analyse van een opleiding aan een TU, maar zou je me misschien kunnen/willen uitleggen waarin jou oplossing afwijkt van de mijne (anders dan het uitwerken van de vergelijkingen).

Edit: interessante uitkomst trouwens, totaal onverwacht! Ik snap alleen je grafieken niet (figuur 2 t/m 4), naarmate de "error distance" oploopt, neemt de "probability" toe, moet dat niet omgekeerd invers (is dat een Nederlands woord?) zijn?

Als je goed leest zie je dat deze f de verhouding is tussen x₂ en x₁ (de afstand tot AP₂ en AP₁). Hierbij introduceer ik een nieuw punt C, welke links ligt van het dichtstbijzijnde access point (AP₁) op dezelfe lijn als AP₁ en AP₂, op een afstand ε = δ/(f²-1). Hierbij is δ de afstand tussen de twee access points (welke bekend zou moeten zijn). Nu kun je een cirkel trekken met radius ε = fδ/(f²-1). Op deze cirkel moet jouw ontvanger staan, en bij het bepalen van deze cirkel heb je alleen de locatie van de access points nodig en de verhouding in de afstand, welke direct af te leiden is uit de verhouding van de signaalsterktes. Hierbij wordt dus geen aanname gemaakt over de factor tussen de afstand en de signaalsterkte.

Doe ditzelfde met een derde punt en je zou in theorie jouw locatie bepaald kunnen hebben. Zoals je in de paper leest zit er nog meer achter (zoals het uitmiddelen van de signaalsterktes e.d.). En helaas blijkt deze methode dus nog gevoeliger voor storingen van andere aard...