Trilaterace
Trilaterace je pojem z oboru geodézie. Jde o analogii triangulace, která nepracuje s úhly, ale s délkami (-later-). Zatímco při triangulaci se měří ve všech trojúhelnících tři úhly (které bývají vyrovnány na teoretický součet), při trilateraci se měří tři délky. Triangulace byla popsána a úspěšně používána od 18. století. Trilaterace vstoupila do měřické praxe teprve ve 20. století, neboť nejdříve musela být vyvinuta technika pro elektronické měření vzdálenosti. Čili použitelné světelné dálkoměry (na elektronické bázi). Společně s triangulací a multilaterací jde o základní metodu, která slouží k určení polohy hledaného bodu.
Princip
[editovat | editovat zdroj]Trilaterace[1] je založená na znalosti vzdálenosti od alespoň tří referenčních bodů. Známe-li pozice tří bodů (A, B, C ) v prostoru, potřebujeme pro zaměření pozice (D) znát vzdálenosti bodu D od známých tří bodů. Tyto vzdálenosti poslouží jako poloměry kružnic se středy v bodech A, B a C. Tyto kružnice se protnou v jediném bodě D.
To by byl ovšem ideální scénář. K měření vzdálenosti se využívají bezdrátové technologie (WiFi, Bluetooth nebo telefonní signál), což znamená, že měření vzdálenosti od referenčních bodů není tak precizní, aby se kružnice protnuly v jediném bodě. Místo toho se využívá kruhů a poloha bodu D se určí jako střed průniku kruhů.[2]
Podle toho zda se poloha určuje ve dvou nebo třírozměrném prostoru, rozlišujeme 2D a 3D trilateraci.
2D Trilaterace
[editovat | editovat zdroj]Poloha hledaného bodu se určuje ve dvourozměrném prostotu, proto nám známé body a hledaný bod musí být umístěny v jedné rovině.
Princip
[editovat | editovat zdroj]Princip spočívá ve vytvoření kružnic kolem známých bodů s poloměry o velikostech vzdáleností k hledanému bodu. Pokud jsou známé pouze dva body, dochází k průniku kružnic ve dvou místech. Z toho vyplývá, že k přesnému určení polohy hledaného bodu je za potřebí minimálně tří známých bodů.
Výpočet
[editovat | editovat zdroj]Mějme tři body Bod1, Bod2, Bod3 na souřadnicích (x1,y1), (x2,y2) a (x3,y3). Kolem každého bodu je kružnice s poloměry r1, r2, r3. Poloměr je dán naměřenou nebo vypočítanou vzdáleností od hledaného bodu. Hledaný bod má souřadnice (x,y).
Pro každou kružnici je určena rovnice a řešením soustavy tří kvadratických rovnic o dvou neznámých se hledá průsečík těchto rovnic.[3]
(x - x1)2 + (y - y1)2 = r12
(x - x2)2 + (y - y2)2 = r22
(x - x3)2 + (y - y3)2 = r32
Pomocí substituce lze kvadratickou soustavu zjednodušit na soustavu dvou lineárních rovnic
2(x2 - x1)x + 2(y2 - y1)y = (r12 - r22) - (x12 - x22) - (y12 - y22)
2(x3 - x1)x + 2(y3 - y1)y = (r12 - r32) - (x12 - x32) - (y12 - y32)
Pomocí Cramerova pravidla se následně nalezne obecné řešení soustavy. Řešením soustavy jsou souřadnice x a y hledaného průsečíku kružnic.[3]
3D Trilaterace
[editovat | editovat zdroj]Používá se pro výpočet polohy hledaného bodu v trojrozměrném prostoru.
Princip
[editovat | editovat zdroj]Princip je stejný jako u 2D trilaterace, jen výpočet a zobrazení je složitější na představu. Body mají souřadnice (x, y, z) a kolem námi známých bodů jsou vytvořeny koule s poloměry o velikostech vzdáleností k hledanému bodu.
Výpočet
[editovat | editovat zdroj]Výpočet probíhá velmi podobně jako u 2D trilaterace, s tím rozdílem, že každý nám známý bod může být v rozdílné výšce. Proto pro výpočet není využíváno rovnic pro kruh, ale rovnic pro kouli. Znovu bude hledán průsečík.[3]
Tato soustava kvadratických rovnic se dá zjednodušit na soustavu rovnic lineárních
Opět pomocí Cramerova pravidla se nalezne obecné řešení soustavy a jsou vypočteny souřadnice x, y, z
Trilaterační algoritmy
[editovat | editovat zdroj]Pojem trilaterace zastřešuje metody, které jako vstup využívají pevně dané referenční body v prostoru a vzdálenosti od nich. Referenční body jsou využity jako středy kruhů, jejichž poloměr je právě vzdálenost mezi referenčním bodem a hledanou polohou.
Trilaterace je princip, který nijak nevymezuje způsob, jakým ze vstupních dat získat hledanou polohu. Tento problém řeší konkrétní algoritmy.
Exaktní řešení
[editovat | editovat zdroj]Vychází z předpokladu nulové chyby při měření vzdáleností od referenčních bodů. V takovém případě se musí protnout veškeré kruhy (resp. kružnice) v jediném bodě.
Geometrické metody
[editovat | editovat zdroj]Tyto metody[4] také využívají analytické geometrie. Ovšem již nevyužívají rovnice kružnic, ale nerovnice kruhů a vychází z předpokladu, že získaná vzdálenost obsahuje chybu. Počítá se tedy s chybou, díky které se kruhy překrývají, a průnikem tedy není jeden bod, ale plocha.[2]
Geometrické metody mají výhodu ve své jednoduchosti. Jejich slabinou je ovšem předpoklad dostatečného počtu průsečíků.[2]
Clusterové metody
[editovat | editovat zdroj]V ideálním případě se všechny kruhy překrývají. Ze tří bodů můžeme tedy získat až šest průsečíků. Pouhým okem je jasné, které tři průsečíky lemují kritickou oblast. Bohužel náhled pouhým okem nemáme při výpočtu k dispozici. Místo toho se využívá metoda clusteru.[2]
- Centroid clusteru
- Vážený centroid clusteru
- Body trojúhelníkového clusteru (Fermatův bod, Lemoinův bod, Střed kružnice opsané)
Průnik dvou kruhů
[editovat | editovat zdroj]Jde o jednoduchou metodu spočívající v nalezení průniku dvojice kružnic a následně nalezení průniku spojnice středů kružnic se spojnicí průsečíků. K výpočtu postačí pouze dva kruhy. Má své místo pro porovnávací účely, případně pro nouzové situace, kdy budou dostupné pouze dva známé body.[2]
Optimalizační metody
[editovat | editovat zdroj]Často může nastat situace, kdy nedojde vůbec k žádnému protnutí signálů díky multipath efektu, který signály zesílí. V takové situaci je vhodné použít optimalizační algoritmy, které počítají s chybou výpočtu vzdálenosti od majáků. Na základě vstupních dat hledají takovou pozici, v níž bude součet chyb minimální.[2]
Nelineární nejmenší čtverce
[editovat | editovat zdroj]Metoda nejmenších čtverců se využívá v případech jako je prokládání polynomu zadanými body. Využívá se v situacích, kdy by bylo náročné najít exaktní řešení, nebo pokud máme zadanou přeurčenou soustavu rovnic, tedy rovnic je více než proměnných. Cílem metody je nalezení takového řešení, pro které platí, že součet kvadrátů odchylek od zadaných bodů je minimální.[2]
Nelder-Mead simplexová metoda
[editovat | editovat zdroj]Simplexová metoda je další iterativní optimalizační metodou.[5] Tato metoda, na rozdíl od nejmenších čtverců, nevyžaduje derivování. Místo toho postupně zmenšuje polygon popisující prostor řešení.[2]
Trilaterace pomocí signálů
[editovat | editovat zdroj]GSM trilaterace
[editovat | editovat zdroj]Nejjednodušší a nejméně přesné určení pozice telefonu je pomocí telefonních vysílačů (BTS – base transceiver station). Každý vysílač má svou unikátní identifikaci (ID). Pokud tedy telefon komunikuje s konkrétním vysílačem, je v kruhu, jehož středem je vysílač a poloměr kruhu tvoří dosah vysílače. Zpřesnění metody lze dosáhnout díky znalosti poklesu intenzity signálu s rostoucí vzdáleností (klesá s rostoucím kvadrátem vzdálenosti). Další zpřesnění poskytuje dostupnost dalších vysílačů.[2]
V GSM (z fr. Global Spécial Mobile) mobilních sítích funguje časový multiplex, který umožňuje aby na jedné frekvenci komunikovalo více zařízení. Každé zařízení má svůj časový slot na dané frekvenci. Aby toto mohlo fungovat, musí telefon i vysílač vysílat data s předstihem. Kvůli tomu musejí znát vzdálenost mezi sebou. Ta se v GSM určuje pomocí Timing Advice (TA), která rozděluje dosah vysílače na 64 pásem po 550 metrech.[2]
I při možnosti využít informace z více dostupných vysílačů, se budeme stále pohybovat s přesností v řádech desítek nebo stovek metrů. Navíc např. u OS Android existuje v API metoda pro získání všech dostupných vysílačů, ovšem nemusí být podporována hardwarem. Díky tomu dostaneme často informaci pouze o vysílači, se kterým aktuálně komunikujeme a tím pádem i pouze jeho TA hodnotu.[2]
WiFi trilaterace
[editovat | editovat zdroj]WiFi je technologie pro bezdrátový přesnost internetu skrze přístupové body (AP – access points). Funguje v nelicencovaných pásmech 2.4 a 5 GHz.
Firmy jako Google[6][7] mají rozsáhlé databáze MAC adres jednotlivých AP a k nim přiřazená zeměpisné souřadnice. Díky tomu, pokud je na telefonu zapnutá WiFi, stačí když zjistí MAC adresy zařízení v dosahu a pošle dotaz prostřednictvím internetu. Polohu lze ještě zpřesnit pomocí intenzity signálu. Ovšem tímto způsobem se pohybujeme na granularitě budov, protože WiFi má dosah až desítky metrů a MAC adresa AP umístěného v kavárně nám pouze napoví, že se nacházíme v kavárně nebo její těsné blízkosti.[2]
WiFi pokrytí je poměrně běžné, ovšem signál je ovlivněn zdmi, nábytkem, osobami a dokonce natočením telefonu vůči vysílači. S pomocí nynějšího vybavení WiFi v budovách získáme pro běžnou trilateraci přesnost při nejlepším na úrovni místností. WiFi trilaterace by tedy byla použitelná, ale vyžadovala by daleko více AP v budově, což by bylo náročné finančně i energeticky.[2]
Další možností je běžnou trilateraci spojit s dalšími metodami, které eliminují nedokonalosti WiFi signálu jako je např. multipath efekt. Což je jev, kdy se do zařízení dostane signál z vysílače nejen přímou cestou, ale také odrazem o stěny. Díky tomu na zařízení dorazí několik kopií stejné informace nebo spolu mohou tyto odrazy dokonce interferovat. Výsledkem je např. zkreslená síla signálu a tím i vzdálenost od vysílače.[2]
Možným budoucím řešením jsou technologie jako SpotFi,[8] Chronos[9] nebo Widar.[10] Ty využívají stávající WiFi standard a snaží se zvýšit jeho přesnost až na desítky centimetrů využitím dalších metod.[2]
Bluetooth trilaterace
[editovat | editovat zdroj]Nasazení Bluetooth pro trilateraci se v mnohém shoduje s WiFi. Dokonce operuje i ve stejném pásmu 2.4 GHz. Technologie Bluetooth byla vytvořena pro bezdrátovou komunikaci na krátké vzdálenosti (cca 10 metrů bez překážek). Hardware potřebný ke komunikaci je tak menší a levnější.[2]
Starší verze Bluetooth (1, 2.1, 3) fungují na principu komunikace master – slave,[11][12] tedy jeden řídící uzel a ostatní uzly vedlejší. Vyhledávání Bluetooth zařízení v okolí navíc trvá dlouho (jednotky až desítky sekund). Tyto verze nejsou vhodné pro časté dotazy na intenzitu signálu.[2]
Díky Bluetooth Low Energy (Bluetooth LE)[12] se ovšem situace změnila. Tento standard mj. umožňuje rozesílání krátkých periodických broadcastových zpráv, které může zachytit kterékoliv naslouchající zařízení v okolí. Díky těmto zprávám lze zjistit i intenzitu signálu a tím i vzdálenost. Při návrhu standardu bylo dbáno i na energetickou náročnost. Díky tomu tyto vysílače mohou rozesílat své zprávy a k napájení stačí běžné baterie, které postačí po dobu několika měsíců.[2]
Menší dosah zařízení je svým způsobem výhodou. Není zde snaha o pokrytí prostoru minimem vysílačů, ba naopak. Díky nižší ceně a dlouhé výdrži baterií lze použít desítky takových vysílačů pro jediné patro budovy.[2]
Bluetooth LE se tedy jeví jako vhodná technologie pro trilateraci.[2]
Zvuková trilaterace
[editovat | editovat zdroj]Stejně jako u Bluetooth nebo WiFi lze využít dobu cesty signálu k výpočtu vzdálenosti. V tomto případě neputuje signál rychlostí světla, ale jedná se o zvukové signály šířící se rychlostí zvuku.[2]
Tato metoda je možná snadnější pro pochopení komplikací spjatých s rušením signálu, které se týká i Bluetooth a WiFi. I zde dochází k rušení prostřednictvím 17 útlumu zvuku kvůli interiéru a lidem v místnosti. Stejně tak se zde můžeme setkat s efektem multipath díky odrazům zvuku od stěn. Komplikací je i fyzické omezení zvukového rozsahu mikrofonu a reproduktoru telefonu.[2]
Jejich rozsah je navíc omezen tím, že zvukové signály systému musejí být mimo slyšitelné spektrum lidského ucha. Výhodou je, že mikrofon pro zachycení zvuku mají všechny telefony. V praxi ovšem můžeme narazit na využití zvuku pouze pro měření vzdálenosti pomocí ultrasonických senzorů u autonomních zařízení jako jsou inteligentní vysavače.[2]
Použití
[editovat | editovat zdroj]Systémy založené na trilateraci
[editovat | editovat zdroj]GPS (USA), GLONASS (Rusko), Beidou (Čína), GALILEO (EU)
Referenčními body jsou zde družice kroužící po orbitálních drahách kolem planety (výjimku tvoří několik geostacionárních družic Beidou). Vzdálenost je získávána z časového rozdílu mezi odesláním a přijetím signálu, za předpokladu znalosti rychlosti šíření signálu.[2]
Aktivní dálkoměrné systémy
[editovat | editovat zdroj]Trilaterace se jeví jako vhodná pro určování pozice pomocí satelitních systémů. Pro použití této metody je zapotřebí znát přesnou pozici daných bodů a od nich vzdálenost k hledanému. Na tomto principu pracují tzv. aktivní dálkoměrné systémy. Jedná se o systémy pracující na způsobu dotaz-odpověď. V místě v němž je zapotřebí určit polohu se musí nacházet zařízení zvané odpovídač. Pomocí satelitů pozemní řídící stanice vyšle dotaz a odpovídač v neznámém místě vyšle zpět pomocí signálu přes družice odpověď. Na základě zpoždění od satelitů tohoto signálu pozemní řídící stanice určí polohu odpovídače.[13]
Pasivní dálkoměrné systémy
[editovat | editovat zdroj]Tyto systémy spočívají ve vysílání synchronizovaného signálu z družic a přijímač na neznámé poloze vyhodnocuje dobu šíření elektromagnetické vlny a zároveň s daty o aktuální poloze satelitů nebo jejich aktuálních drahách, vypočítává svoji pozici.[14]
Nicméně není možné přímo zjistit dobu šíření signálu mezi satelitem a přijímačem, jelikož není znám absolutní čas vysílání signálu od družice. Je proto zapotřebí využít takovou metodu, která zjistí tento údaj nepřímo. Tato metoda se nazývá Multilaterace.
Reference
[editovat | editovat zdroj]- ↑ GPS.gov: Trilateration Exercise. www.gps.gov [online]. [cit. 2021-06-06]. Dostupné online.
- ↑ a b c d e f g h i j k l m n o p q r s t u v w x VAŠINA, Viktor. Možnosti indoor geolokace mobilních zařízení. core.ac.uk [online]. 2017 [cit. 2021-06-05]. Dostupné online.
- ↑ a b c UNIVERZITA PARDUBICE Fakulta elektrotechniky a informatiky LOKALIZACE MOBILNÍHO ROBOTA V NEZNÁMÉM TERÉNU. Bc. Jiří Král - PDF Stažení zdarma. docplayer.cz [online]. [cit. 2021-06-05]. Dostupné online.
- ↑ HUANG, Ming-Shih. TRILATERATION-BASED LOCALIZATION ALGORITHM FOR ADSB RADAR SYSTEMS. etda.libraries.psu.edu [online]. 2013 [cit. 2021-06-06]. Dostupné online.
- ↑ Nelder-Mead Method. www.jasoncantarella.com [online]. 2004 [cit. 2021-06-06]. Dostupné online.
- ↑ MEYER, Jeanine. Where am I: Using Geolocation, the Google Maps API, and PHP. Berkeley, CA: Apress Dostupné online. ISBN 978-1-4302-4032-7, ISBN 978-1-4302-4033-4. S. 183–224.
- ↑ The Google Maps Geolocation API. developers.google.com [online]. [cit. 2021-06-05]. Dostupné online.
- ↑ SpotFi: Decimeter Level Localization Using WiFi. conferences.sigcomm.org [online]. [cit. 2021-06-06]. Dostupné online.
- ↑ Decimeter-Level Localization with a Single WiFi Access Point. www.usenix.org [online]. 2016 [cit. 2021-06-06]. Dostupné online.
- ↑ WIDAR: bistatic WI-fi Detection And Ranging for off-the-shelf devices. www.semanticscholar.org [online]. 2013 [cit. 2021-06-06]. Dostupné online.
- ↑ Bluetooth Core Specification. www.bluetooth.com [online]. [cit. 2021-06-06]. Dostupné v archivu pořízeném z originálu dne 2021-06-06.
- ↑ a b Bluetooth Basics. learn.sparkfun.com [online]. 2013 [cit. 2021-06-06]. Dostupné online.
- ↑ HRDINA, Zdeněk; VEJRAŽKA, František; PÁNEK, Petr. Rádiové určování polohy: (družicový systém GPS). Dot. 1. vyd.. vyd. Praha: České vysoké učení technické, 1996. ISBN 80-01-01386-3.
- ↑ KAPLAN, Elliot D.; HEGARTY, Christopher J. Understanding GPS: principles and Applications. 2nd Edit. vyd. Boston: Artech House, 2006. ISBN 1-58053-894-0.
Literatura
[editovat | editovat zdroj]- Pradhan, Sajina; Hwang, Suk-seung; Lee, Dongbin. 2021. "Mathematical Analysis of Line Intersection and Shortest Distance Algorithms" Energies 14, no. 5: 1492. https://doi.org/10.3390/en14051492
- GPS navigace pro zemědělské stroje založená na platformě Arduino - diplomová práce Západočeská univerzita v Plzni
- Lokalizace mobilního robota v neznámém terénu - diplomová práce Univerzita Pardubice