Trilaterace

TrilateraceTrilaterace 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

Trilaterace 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ů. +more 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ě. +more Místo toho se využívá kruhů a poloha bodu D se určí jako střed průniku kruhů.

Podle toho zda se poloha určuje ve dvou nebo třírozměrném prostoru, rozlišujeme 2D a 3D trilateraci.

2D Trilaterace

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

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. +more 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

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. +more 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.

(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.

x = \frac{\begin{vmatrix} (r_1^2 - r_2^2) - (x _1^2 - x_2^2) - (y_1^2 - y_2^2)& 2(y_2 - y_1)\\ (r_1^2 - r_3^2) - (x _1^2 - x_3^2) - (y_1^2 - y_3^2) & 2(y_3 - y_1) \end{vmatrix}}{\begin{vmatrix} 2(x_2 - x_1) & 2(y _2 - y_1) \\ 2(x_3 - x_1) & 2(y_3 - y_1) \end{vmatrix}} \qquad

y = \frac{\begin{vmatrix} 2(x_2 - x_1) & (r _1^2 - r_2^2) - (x_1^2 - x_2^2) - (y_1^2 - y_2^2)\\ 2(x_3 - x_1) & (r _1^2 - r_3^2) - (x_1^2 - x_3^2) - (y_1^2 - y_3^2) \end{vmatrix}}{\begin{vmatrix} 2(x_2 - x_1) & 2(y _2 - y_1) \\ 2(x_3 - x_1) & 2(y_3 - y_1) \end{vmatrix}}

3D Trilaterace

Používá se pro výpočet polohy hledaného bodu v trojrozměrném prostoru.

Princip

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

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. +more Znovu bude hledán průsečík.

\begin{alignat}{2} (x - x_1)^2 + (y - y_1)^2 + (z - z_1)^2 & = r_1^2 \\ (x - x_2)^2 + (y - y_2)^2 + (z - z_2)^2 & = r_2^2 \\ (x - x_3)^2 + (y - y_3)^2 + (z - z_ 3)^2 & = r_3^2 \\ (x - x_4)^2 + (y - y_4)^2 + (z - z_4)^2 & = r_4^2 \\ \end{alignat}

Tato soustava kvadratických rovnic se dá zjednodušit na soustavu rovnic lineárních

\begin{alignat}{2} 2(x_2 - x_1)x + 2(y_2 - y_1)y + 2(z_2 - z_1)z & = (r_1^2 - r_2^2) - (x_1^2 - x_2^2) - (y_1^2 - y_2^2) - (z_1^2 - z_2^2) \\ 2(x_3 - x_1)x + 2(y_3 - y_1)y + 2(z_3 - z_1)z & = (r_1^2 - r_3^2) - (x_1^2 - x_3^2) - (y_1^2 - y_3^2) - (z_1^2 - z_3^2) \\ 2(x_4 - x_1)x + 2(y_4 - y_1)y + 2(z_4 - z_1)z & = (r_1^2 - r_4^2) - (x_1^2 - x_4^2) - (y_1^2 - y_4^2) - (z_1^2 - z_4^2) \\ \end{alignat}

Opět pomocí Cramerova pravidla se nalezne obecné řešení soustavy a jsou vypočteny souřadnice x, y, z

x = \frac{\begin{vmatrix} (r_1^2 - r_2^2) - (x _1^2 - x_2^2) - (y_1^2 - y_2^2) - (z_1^2 - z_2^2) & 2(y_2 - y_1) & 2(z_2 - z_1) \\ (r_1^2 - r_3^2) - (x _1^2 - x_3^2) - (y_1^2 - y_3^2) - (z_1^2 - z_3^2) & 2(y_3 - y_1) & 2(z_3 - z_1) \\ (r_1^2 - r_4^2) - (x _1^2 - x_4^2) - (y_1^2 - y_4^2) - (z_1^2 - z_4^2) & 2(y_4 - y_1) & 2(z_4 - z_1) \end{vmatrix}}{\begin{vmatrix} 2(x_2 - x_1) & 2(y _2 - y_1) & 2(z _2 - z_1) \\ 2(x_3 - x_1) & 2(y_3 - y_1) & 2(z_3 - z_1) \\ 2(x_4 - z_1) & 2(y_4 - y_1) & 2(z_4 - z_1) \end{vmatrix}} \qquad

y = \frac{\begin{vmatrix} 2(x_2 - x_1) & (r _1^2 - r_2^2) - (x_1^2 - x_2^2) - (y_1^2 - y_2^2) - (z_1^2 - z _2^2) & 2(z_2 - z_1) \\ 2(x_3 - x_1) & (r _1^2 - r_3^2) - (x_1^2 - x_3^2) - (y_1^2 - y_3^2) - (z _1^2 - z_3^2) & 2(z_3 - z_1) \\ 2(x_4 - x_1) & (r _1^2 - r_4^2) - (x_1^2 - x_4^2) - (y_1^2 - y_4^2) - (z _1^2 - z_4^2) & 2(z_4 - z_1) \end{vmatrix}}{\begin{vmatrix} 2(x_2 - x_1) & 2(y _2 - y_1) & 2(z _2 - z_1) \\ 2(x_3 - x_1) & 2(y_3 - y_1) & 2(z_3 - z_1) \\ 2(x_4 - z_1) & 2(y_4 - y_1) & 2(z_4 - z_1) \end{vmatrix}} \qquad

z = \frac{\begin{vmatrix} 2(x_2 - x_1) & 2(y_2 - y_1) & (r _1^2 - r_2^2) - (x_1^2 - x_2^2) - (y_1^2 - y_2^2) - (z_1^2 - z _2^2) \\ 2(x_3 - x_1) & 2(y_3 - y_1) & (r _1^2 - r_3^2) - (x_1^2 - x_3^2) - (y_1^2 - y_3^2) - (z _1^2 - z_3^2) \\ 2(x_4 - x_1) & 2(y_4 - y _1) & (r _1^2 - r_4^2) - (x_1^2 - x_4^2) - (y_1^2 - y_4^2) - (z _1^2 - z_4^2) \end{vmatrix}}{\begin{vmatrix} 2(x_2 - x_1) & 2(y _2 - y_1) & 2(z _2 - z_1) \\ 2(x_3 - x_1) & 2(y_3 - y_1) & 2(z_3 - z_1) \\ 2(x_4 - z_1) & 2(y_4 - y_1) & 2(z_4 - z_1) \end{vmatrix}}

Trilaterační algoritmy

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í

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. +more kružnice) v jediném bodě. Předpoklad nulové chyby.

Geometrické metody

Tyto metody 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. +more Počítá se tedy s chybou, díky které se kruhy překrývají, a průnikem tedy není jeden bod, ale plocha.

Geometrické metody mají výhodu ve své jednoduchosti. Jejich slabinou je ovšem předpoklad dostatečného počtu průsečíků. +morePrůnikem je plocha.

Clusterové metody

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ů. +more 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.

* 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ů

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. +more Má své místo pro porovnávací účely, případně pro nouzové situace, kdy budou dostupné pouze dva známé body.

Optimalizační metody

Č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ů. +more Na základě vstupních dat hledají takovou pozici, v níž bude součet chyb minimální.

Nelineární nejmenší čtverce

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. +more 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í.

Nelder-Mead simplexová metoda

Simplexová metoda je další iterativní optimalizační metodou. Tato metoda, na rozdíl od nejmenších čtverců, nevyžaduje derivování. +more Místo toho postupně zmenšuje polygon popisující prostor řešení.

Trilaterace pomocí signálů

GSM trilaterace

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). +more 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čů.

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í. +more 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.

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ř. +more 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.

WiFi trilaterace

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 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. +more 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.

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í. +more 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.

Další možností je běžnou trilateraci spojit s dalšími metodami, které eliminují nedokonalosti WiFi signálu jako je např. multipath efekt. +more 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.

Možným budoucím řešením jsou technologie jako SpotFi, Chronos nebo Widar. 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.

Bluetooth trilaterace

Nasazení Bluetooth pro trilateraci se v mnohém shoduje s WiFi. Dokonce operuje i ve stejném pásmu 2. +more4 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ší.

Starší verze Bluetooth (1, 2. 1, 3) fungují na principu komunikace master - slave, tedy jeden řídící uzel a ostatní uzly vedlejší. +more 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.

Díky Bluetooth LE (Low Energy) se ovšem situace změnila. Tento standard mj. +more 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ů.

Menší dosah zařízení je svým způsobem výhodou. Není zde snaha o pokrytí prostoru minimem vysílačů, ba naopak. +more Díky nižší ceně a dlouhé výdrži baterií lze použít desítky takových vysílačů pro jediné patro budovy.

Bluetooth LE se tedy jeví jako vhodná technologie pro trilateraci.

Zvuková trilaterace

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.

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. +more 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.

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. +more 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.

Použití

==== Systémy založené na trilateraci ==== 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.

==== Aktivní dálkoměrné systémy ==== 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. +more 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.

==== Pasivní dálkoměrné systémy ==== 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.

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. +more Tato metoda se nazývá Multilaterace.

Reference

Literatura

Pradhan, Sajina; Hwang, Suk-seung; Lee, Dongbin. 2021. +more "Mathematical Analysis of Line Intersection and Shortest Distance Algorithms" Energies 14, no. 5: 1492. https://doi. org/10. 3390/en14051492 *[url=https://otik. uk. zcu. cz/bitstream/11025/27946/1/DP_Jan_Sprisl_TracNav. pdf]GPS navigace pro zemědělské stroje založená na platformě Arduino[/url] - diplomová práce Západočeská univerzita v Plzni * [url=https://docplayer. cz/23436035-Univerzita-pardubice-fakulta-elektrotechniky-a-informatiky-lokalizace-mobilniho-robota-v-neznamem-terenu-bc-jiri-kral. html]Lokalizace mobilního robota v neznámém terénu[/url] - diplomová práce Univerzita Pardubice.

Související články

Triangulace *Multilaterace *GPS *Galileo (navigační systém) *GLONASS *Systém základnových stanic

Kategorie:Geodézie