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.

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.

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

Mějme tři body Bod1, Bod2, Bod3 na souřadnicích (x₁,y₁), (x₂,y₂) a (x₃,y₃). Kolem každého bodu je kružnice s poloměry r₁, r₂, r₃. 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 - x₁)² + (y - y₁)² = r₁²

(x - x₂)² + (y - y₂)² = r₂²

(x - x₃)² + (y - y₃)² = r₃²

Pomocí substituce lze kvadratickou soustavu zjednodušit na soustavu dvou lineárních rovnic

2(x₂ - x₁)x + 2(y₂ - y₁)y = (r₁² - r₂²) - (x₁² - x₂²) - (y₁² - y₂²)

2(x₃ - x₁)x + 2(y₃ - y₁)y = (r₁² - r₃²) - (x₁² - x₃²) - (y₁² - y₃²)

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]

${\textstyle 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}}}}$

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

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 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]

${\textstyle {\begin{alignedat}{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{alignedat}}}$

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

${\displaystyle {\begin{alignedat}{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{alignedat}}}$

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

${\textstyle 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}}}}$

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.

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

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]

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é)

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]

Č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]

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]

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]

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 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]

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]

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]

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]

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]

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.

• 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

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