Multilateracja

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Multilateracja – technika nawigacji oparta na pomiarze różnicy pomiędzy odległościami do dwóch lub więcej stacji położonych w znanych lokalizacjach, które nadają sygnał rozsiewczo w określonych momentach czasu. W odróżnieniu od pomiarów odległości absolutnej lub kąta, pomiar różnicy odległości daje nieskończoną ilość możliwych położeń. Jeśli wykreślić krzywą wszystkich możliwych położeń stworzą one krzywą hiperboliczną. Aby wyznaczyć dokładne położenie na tej krzywej należy wykonać drugi pomiar do innej pary stacji w celu otrzymania drugiej krzywej, która przecinać się będzie z pierwszą krzywą. Po ich porównaniu otrzymuje się ograniczoną liczbę możliwych położeń, co nazywane jest fixem.

Multilateracja jest powszechną techniką w systemach radionawigacyjnych znaną jako nawigacja hiperboliczna. Systemy takie są stosunkowo proste w budowie, ponieważ nie wymagają wspólnego zegara (oscylatora), a różnica w czasach sygnałów może być zmierzona wizualnie na oscyloskopie. Multilateracja stanowiła podstawę wielu szeroko wykorzystywanych systemów nawigacyjnych poczynając od brytyjskiego systemu Gee z czasów Drugiej Wojny Światowej oraz paru podobnych systemów wprowadzonych w następnych dekadach. Wprowadzenie mikroprocesora bardzo uprościło działanie, znacznie zwiększając popularność w latach osiemdziesiątych. Najbardziej popularnym hiperbolicznym systemem nawigacyjnym był LORAN-C, który był wykorzystywany aż do zamknięcia w roku 2010. Inne podobne systemy nadal są używane, jednak coraz popularniejsze systemy nawigacji satelitarnej takich jak GPS spowodowały, że systemy hiperboliczne stały się nadmiarowe.

Multilateracja nie powinna być mylona z trilateracją, która wykorzystuje odległości, bądź bezwzględne pomiary czasu przelotu z trzech lub więcej lokalizacji, jak również z triangulacją, która wykorzystuje pomiar kąta bezwzględnego. Oba te systemy są jednak również powszechnie używane przez systemy radionawigacyjne; system GPS opiera się na trilateracji.

Zasady[edytuj | edytuj kod]

Multilateracja jest powszechnie wykorzystywana w cywilnych oraz wojskowych zastosowaniach nadzoru dla dokładnego określenia położenia samolotów, pojazdów lub nadajników stacjonarnych przez pomiar różnicy czasowej nadejścia sygnału (TDoA) z nadajnika do trzech lub więcej lokalizacji odbiorczych.

Jeśli impuls wysłany jest z pewnego punktu w przestrzeni, nadejdzie on do dwóch oddalonych od siebie lokalizacji odbiorczych w różnych momentach czasu, różnica czasowa wynika więc z różnicy odległości pomiędzy odbiornikami a nadajnikiem. Mając dane dwie lokalizacje oraz znane TDoA otrzymamy miejsce geometryczne możliwych położeń nadajnika, będące połową hiperboloidy dwupowłokowej.

Rys. 1. Hiperboloida dwupowłokowa

Ujmując to prościej, znając położenie obu odbiorników można zlokalizować nadajnik na powierzchni hiperboloidy[1].

Można zauważyć, że odbiorniki nie muszą znać bezwzględnego czasu, w którym impuls został nadany - wymagana jest jedynie różnica czasowa.

Rozważmy teraz trzeci odbiornik w trzeciej lokalizacji. Zapewni to drugi pomiar TDoA i stąd zlokalizowanie nadajnika na drugiej hiperboloidzie. Przecięcie tych dwóch hiperboloid opisuje krzywą na której położony jest nadajnik.

Jeśli wprowadzimy teraz czwarty odbiornik dokonać można będzie trzeciego pomiaru TDoA, a przecięcie wynikowej trzeciej hiperboloidy z krzywą już wykreśloną z poprzednich pomiarów określi jedyny punkt w przestrzeni. Lokalizacja nadajnika jest wówczas w pełni określona w trzech wymiarach.

W praktyce, błędy w pomiarach czasu nadejścia impulsów oznaczają, że lepsza dokładność może być uzyskana przy ilości odbiorników większej niż cztery. Zasadniczo, N odbiorników zapewnia N − 1 hiperboloid. Gdy jest N > 4 odbiorników, N − 1 hiperboloid powinno się przeciąć na jednym punkcie (zakładając doskonały model i pomiary). W rzeczywistości powierzchnie rzadko przecinają się z powodu różnych błędów. W takim przypadku problem lokalizacji może stanowić problem optymalizacji i być rozwiązany wykorzystując na przykład metodę najmniejszych kwadratów lub rozszerzony filtr Kalmana.

Dodatkowo, TDoA z wielu nadanych impulsów mogą być uśrednione w celu poprawienia dokładności.

Przypadek wzajemny: lokalizowanie odbiornika w oparciu o wiele lokalizacji nadawczych[edytuj | edytuj kod]

Multilateracja może być wykorzystywana także przez pojedynczy odbiornik do ustalenia własnego położenia przez pomiar TDoA sygnałów nadanych z trzech lub więcej zsynchronizowanych nadajników znajdujących się w znanych lokalizacjach. Taka metoda jest wykorzystywana przez systemy nawigacyjne, czego przykładem jest brytyjski system nawigacyjny DECCA opracowany podczas Drugiej Wojny Światowej, który wykorzystywał raczej różnicę fazową dwóch nadajników niż TDoA impulsu do zdefiniowania hiperboloid. Pozwoliło to nadajnikom nadawać rozsiewczo sygnał fali ciągłej. Różnica fazowa oraz różnica czasowa mogą być rozważane jako tożsame dla nadajników wąskopasmowych.

Geometria TDOA[edytuj | edytuj kod]

Geometria fali sferycznej wypromieniowanej z nadajnika i przechodzącej przez wiele odbiorników
Rys. 2. Geometria TDOA.

Rozważmy nadajnik (E na rysunku 2) o nieznanej pozycji wektora

E = (x, y, z)

który chcemy zlokalizować. Źródło jest w zasięgu N+1 odbiorników o znanych pozycjach

P0, P1, ..., Pm, ..., PN.

Indeks dolny m odnosi się do każdego z odbiorników:

Pm = (xm, ym, zm)
0 ≤ m ≤ N

Odległość (R) od nadajnika do jednego z nadajników pod względem współrzędnych to:

 
R_m = \left | \vec P_{m} - \vec E \right | = \sqrt{(x_m-x)^2+(y_m-y)^2+(z_m-z)^2}

(1)

Obliczenia można uprościć umiejscawiając początek w punkcie jednego z odbiorników (P0), co daje jego odległość do nadajnika:


R_0 = \sqrt{(x)^2+(y)^2+(z)^2}

(2)

Pomiar różnicy czasowej w systemach TDoA[edytuj | edytuj kod]

Rys. 3. Sygnał impulsowy - pomiar TDoA oraz korelacja krzyżowa
Rys 4. Sygnał szerokopasmowy - pomiar TDoA oraz korelacja krzyżowa
Rys 5. Sygnał wąskopasmowy - pomiar TDoA oraz korelacja krzyżowa

Odległość  R_m we wzorze (1) jest prędkością fali (v) pomnożoną przez czas transmisji (T_m). System TDoA mierzy różnicę czasową ( \tau_m) czoła fali mijającej każdy odbiornik. Równianie TDoA dla odbiorników m oraz 0 to:

\begin{align}
    v \tau_m  & = v T_m - v T_0 \\
    v \tau_m  & = R_m - R_0 
\end{align}

(3)

Rysunek 4 pokazuje symulację fali impulsowej zarejestrowanej przez odbiorniki P_0 oraz P_1. Odległość pomiędzy punktami E, P_1 oraz P_0 jest taka, że impuls potrzebuje 5 razy dłuższego czasu aby osiągnąć punkt P_1 niż P_0. Jednostki czasu na rysunku są umowne. Poniższa tabela daje przybliżone jednostki skali czasu dla rejestrowania różnych typów fal. The units of time in Figure 3 are arbitrary. The following table gives approximate time scale units for recording different types of waves.

Rodzaj fali Materiał Jednostki czasu
Akustyczna Powietrze 1 milisekunda
Akustyczna Woda 1/2 milisekundy
Akustyczna skała 1/10 milisekundy
Elektromagnetyczna Próżnia, powietrze 1 nanosekunda

Czerwona krzywa na rysunku 3 jest korelacją krzyżową funkcji (P_1 \star P_0). Funkcja korelacji krzyżowej przesuwa jedną krzywą w czasie przez drugą krzywą i zwraca wartość szczytową, gdy kształty krzywych są zgodne. Wartość szczytowa w czasie = 5 jest miarą przesunięcia czasowego pomiędzy zarejestrowanymi falami, będąc również wartością \tau potrzebną do równania (3).

Na rysunku 4 pokazany jest ten sam rodzaj symulacji dla fali szerokopasmowej. Przesunięcie czasowe jest równe 5 jednostek, ponieważ geometria i prędkość fali są takie same jak w przykładzie na rysunku 3. Ponownie, szczyt korelacji krzyżowej wychodzi w \tau_1 = 5.

Rysunek 5 jest przykładem ciągłej fali wąskopasmowej. Funkcja korelacji krzyżowej pokazuje ważną rzecz przy dobieraniu geometrii odbiornika. Wartość szczytowa występuje znów przy czasie = 5, ale także przy każdym przyroście okresu fali. Aby uzyskać jedno rozwiązanie dla zmierzonej różnicy czasowej, największa odległość pomiędzy dowolnymi dwoma odbiornikami musi być mniejsza niż długość fali wyemitowanej przez nadajnik. Niektóre systemy, takie jak wspomniany już wcześniej LORAN-C czy Decca, wykorzystują odstępy większe niż jedna długość fali i stosują urządzenia, takie jak detektor fazy, aby zliczać ilość cykli, które mijają w czasie ruchu nadajnika. Działa to tylko dla ciągłej fali wąskopasmowej, ze względu na relację pomiędzy fazą (\theta), częstotliwością (f) a czasem (T): \theta = 2 \pi f \cdot T.

Detektor fazy widzi zmiany częstotliwości jako zmierzony szum fazowy, który jest niepewnością, która przenosi się do obliczeń lokalizacji. Jeśli szum fazowy jest zbyt duży, detektor fazy może stać się niestabilny.

Rozwiązanie 3-D[edytuj | edytuj kod]

Równanie(3) jest hiperboloidą opisaną w poprzednim dziale, gdzie cztery odbiorniki (0 ≤ m ≤ 3) doprowadzają do trzech nieliniowych równań z trzema nieznanymi wartościami (x,y,z). System musi więc obliczyć położenie nieznanego nadajnika w czasie rzeczywistym.

Cywilne multilateralne systemy kontroli lotów wykorzystują Tryb C transpondera powrotnego SRR, aby otrzymać wysokość (z). Trzy lub więcej odbiorników w znanych lokalizacjach jest wykorzystywanych do otrzymania pozostałych dwóch wymiarów (x, y).

R. Bucher i D. Misra przedstawiają dokładne obliczenia algebraiczne do wyznaczenia jednego odbiornika z TDoA pomiędzy trzema nadajnikami. [2]. Ich rozwiązanie jest zestawem równań liniowych dla wyznaczenia współrzędnych (x, y) oraz równania kwadratowego dla współrzędnej (z).

Poprawianie dokładności poprzez zwiększenie liczby odbiorników może być problematyczne dla urządzeń z małymi procesorami wbudowanymi, ze względu na czas wymagany do rozwiązania paru równoległych nieliniowych równań ((1), (2) & (3)). Problem TDoA może być przekształcony w system równań liniowych, jeśli liczba odbiorników jest większa lub równa 5, co może zmniejszyć czas obliczeń. Weźmy równanie (3), szukając rozwiązania dla Rm, podnieśmy obie strony do kwadratu, przenieśmy wszystkie człony równania na jedną stronę i podzielmy je przez  v \tau_m :


\begin{align}
R_{m}^2 & = (v \tau_{m} + R_{0} )^2  \\
R_{m}^2 & = (v \tau_{m})^2 + 2 v \tau_{m} R_{0} + R_{0}^2 \\
0       & = (v \tau_{m})^2 + 2 v \tau_{m} R_{0} + R_{0}^2 - R_{m}^2 \\
0       & = (v \tau_{m}) + 2 R_{0} + \frac {(R_{0}^2 - R_{m}^2)} {v \tau_{m}}.  \\
\end{align}

(4)

Usuwając człon 2 R0 pozbędziemy się wszystkich członów pierwiastkowych. Dokonuje się tego przez odjęcie równania TDoA odbiornika m = 1 od każdego z pozostałych (2 ≤ m ≤ N):


 \begin{align} 
     & 0 =  v \tau_{m} + 2 R_{0}  + \frac {(R_{0}^2 - R_{m}^2)} {v \tau_{m}} \\
     & 0 = -v \tau_{1} - 2 R_{0}  - \frac {(R_{0}^2 - R_{1}^2)} {v \tau_{1}} \\

\hline \\

     & 0 = v \tau_{m} - v \tau_{1} + \frac {(R_{0}^2 - R_{m}^2)} {v \tau_{m}}
                                   - \frac {(R_{0}^2 - R_{1}^2)} {v \tau_{1}}. 
\end{align}

(5)

Skupmy się przez chwilę na równaniu (1). Podnieśmy do kwadratu Rm, pogrupujmy podobne człony równania i wykorzystajmy równanie (2) aby zamienić niektóre człony na R0.

 \begin{align}
R_m^2         & =  x_m^2+y_m^2+z_m^2 -x\ 2x_m - y\ 2y_m - z\ 2z_m +x^2 + y^2 + z^2 \\
              & =  x_m^2+y_m^2+z_m^2 -x\ 2x_m - y\ 2y_m - z\ 2z_m + R_0^2  \\
R_0^2 - R_m^2 & = -x_m^2-y_m^2-z_m^2 +x\ 2x_m + y\ 2y_m + z\ 2z_m. 
\end{align}

(6)

Połączmy równania (5) oraz (6) i zapiszmy jako zestaw równań liniowych nieznanej lokalizacji nadajnika x,y,z:

 \begin{align} 
     0 & =  xA_m + yB_m + zC_m + D_m         \\
       & A_m = \frac {2x_m} {v \tau_m} - \frac {2x_1} {v \tau_1} \\
       & B_m = \frac {2y_m} {v \tau_m} - \frac {2y_1} {v \tau_1} \\
       & C_m = \frac {2z_m} {v \tau_m} - \frac {2z_1} {v \tau_1} \\

       & D_m = v \tau_m - v \tau_1 - \frac {x_m^2 + y_m^2 + z_m^2} {v \tau_m}
                                 + \frac {x_1^2 + y_1^2 + z_1^2} {v \tau_1}. 
\end{align}

(7)

Weźmy równanie (7) aby wygenerować cztery stałe A_m,B_m,C_m,D_m z pomierzonych odległości i czasów dla każdego odbiornika 2 ≤ m ≤ N. Będzie to zestaw N jednorodnych równań liniowych.

Jest wiele mocnych metod algebry liniowej, które pozwalają rozwiązać wartości (x,y,z), takich jakRozkład według wartości osobliwych czy Metoda Gaussa. Rozdział 15 w Metodach numerycznych [3] opisuje parę metod rozwiązywania równań liniowych i oceniania niepewności wartości wynikowych.

Rozwiązanie 2-D[edytuj | edytuj kod]

Przy poszukiwaniu lokalizacji nadajnika w geometrii dwuwymiarowej można wykorzystać dowolną metodę wykorzystywaną w geometrii trójwymiarowej. Układ współrzędnych jest typowo zdefiniowany tak, aby wymiar z był zerem, lub stałą. Przykładami multilateracji 2-D są systemy komunikacji dalekosiężnej fal krótkich, propagacja fal akustycznych w kanale głębokiego dźwięku SOFAR, oraz system nawigacyjny Loran C.

Dokładność[edytuj | edytuj kod]

Dla trilateracji lub multilateracji, obliczenia są wykonywane w oparciu o odległości, co wymaga liczenia częstotliwości oraz fali odebranej transmisji. Dla triangulacji lub multiangulacji, obliczenia są wykonywane w oparciu o kąty, co wymaga liczenia faz oraz fali odebranej transmisji.

Porównując laterację z angulacją, numeryczne problemy są podobne, ale problemy techniczne stanowią znacznie większe wyzwanie przy pomiarach kątów, ponieważ kąty wymagają dwóch pomiarów na pozycję przy wykorzystaniu optycznych lub elektronicznych srodków do mierzenia różnicy faz, zamiast zliczania cykli fal.

Trilateracja jest zasadniczo kalkulacją kątów znanych odległości/rozmiarów, z matematycznego punktu widzenia zdrowym systemem. W trójkącie, kąty mogą zostać wyznaczone jeśli znane są wszystkie długości boków, za to długości boku nie da się wyznaczyć znając wszystkie kąty, nie bez znajomości długości przynajmniej jednego boku.

W 3D, gdy mamy do czynienia z przynajmniej czterema kątami, lokalizacje mogą być obliczane z n + 1 = 4 zmierzonych kątów, plus jednej znanej podstawy, lub po prostu z n + 1 = 4 zmierzonych boków.

Multilateracja jest ogólnie znacznie bardziej dokładna do pozycjonowania obiektów niż rzadko spotykane podejścia, takie jak trilateracja. Multilateracja służy paru aspektom:

  • nadokreślenie problemu kwadratowego o n zmiennych z (n + 1) + m równaniami kwadratowymi,
  • błędy stochastyczne uniemożliwiające podejście deterministyczne do rozwiązywania równań,
  • wymagania grupowania co do segregowania członków różnych grup, przyczyniając się do różnych modeli rozwiązań, tj. stałych lokalizacji, lokalizacji oscylujących, lub lokalizacji w ruchu.

Dokładność multilateracji jest funkcją paru zmiennych, włącznie z:

  • geometrią anteny lub sensora odbiornika(-ów) i nadajnika (-ów) do transmisji radiowej lub optycznej,
  • dokładnością czasową systemu odbiorczego, tj. stabilnością temperaturową oscylatorów,
  • dokładnością synchronizacji częstotliwości oscylatorów nadajników z oscylatorami odbiorników,
  • synchronizacją fazy nadanego sygnału z sygnałem odebranym, ponieważ efekty propagacyjne, np. dyfrakcja lub odbicia zmieniają fazę sygnału
  • niedokładności w lokalizacji nadajników lub odbiorników, w przypadku gdy zakłada się że lokalizacje są znane.

Dokładność może być obliczona z wykorzystaniem ograniczenia Cramera-Rao i biorąc pod uwagę powyższe czynniki podczas budowania równania.

Przykładowe zastosowania[edytuj | edytuj kod]

  • Echolokacja - wykorzystanie fal dźwiękowych do lokalizowania artylerii przeciwnika.
  • System nawigacyjny Decca – System wykorzystywany od Drugiej Wojny Światowej aż do roku 2000, stosujący różnicę fazową wielu nadajników w celu zlokalizowania przecięcia hiperboloid.
  • System nawigacyjny OMEGA – System podobny do Decca, stosowany w swoim czasie na całym świecie, zamknięty w roku 1997.
  • System GEE – brytyjska technika lokalizacji statków powietrznych z czasów II Wojny Światowej wykorzystująca dokładne nadajniki referencyjne.
  • LORAN-C – system nawigacyjny wykorzystujący TDoA sygnałów z wielu zsynchronizowanych nadajników
  • Pasywne systemy multilateracyjne ESM, wykorzystujące wiele nadajników do lokalizacji nadajnika.
  • Namierzanie telefonów komórkowych np Mobile Tracker, wykorzystujące wiele stacji bazowych w celu oszacowania lokalizacji telefonu komórkowego przez sam telefon lub przez sieć.
  • Monitorowanie RVSM wykorzystujące transponder z trybem C/S radaru SRR, który odpowiada na sygnał wywołania w celu obliczenia położenia statku powietrznego.

Uproszczenia[edytuj | edytuj kod]

W zastosowaniach, gdzie nie jest wymagane bardzo precyzyjne określenie położenia korzystne może być zaimplementowanie prostszego rozwiązania. Porównując koncepcję multilateracji jako "lokalizowania ostrego", druga opcja jest czymś w rodzaju "lokalizowania rozmytego", gdzie tylko jedna odległość daje powiązanie pomiędzy detektorem, a obiektem wykrywanym. Tym najprostszym podejściem jest unilateracja. Niestety takie podejście nigdy nie daje pozycji kątowej względem detektora. W obecnych czasach dostępnych jest wiele rozwiązań [4][5][6][7][8]. Niektóre z nich oferują oszacowanie pozycji oparte na łączeniu paru lateracji. Takie podejście jest nie zawsze stabilne, gdy na przestrzeń radiową mają wpływ obiekty metalowe bądź duże masy wody. Inne rozwiązania oferują dyskryminację przestrzenną z pobudzeniem przestrzennym.

Zobacz też[edytuj | edytuj kod]

Piśmiennictwo[edytuj | edytuj kod]

Przypisy

  1. Innymi słowy, na takiej trójwymiarowej powierzchni każde dwa punkty do niej należące będą miały taką samą odległość różnicową od danych odbiorników, tj. sygnał wysłany z dowolnego punktu na tej powierzchni będzie miał takie samo TDoA zmierzone przez odbiorniki jak sygnał nadany z innego dowolnego punktu na tej powierzchni.
    Dlatego w praktyce, TDoA dla (poruszającego się) nadajnika jest mierzona, następnie określana jest związana z tym TDoA powierzchnia hiperboliczna i nadajnik jest lokalizowany gdzieś na tej powierzchni.
  2. A Synthesizable VHDL Model of the Exact Solution for Three-dimensional Hyperbolic Positioning System, Ralph Bucher and D. Misra, VLSI Design, Tom 15 (2002), Wydanie 2, Strony 507-520.
  3. Numerical Recipes official website
  4. Sonitor Technologies, NO-0314 Oslo, Norway: SONITOR Ultra sound proprietary approach
  5. RF Code, Austin, TX 78758, USA: RF Code 433 MHz proprietary approach
  6. ReadPost Bremerhaven Germany: TokLoc®, the Bluetooth® LowEnergy based approach
  7. Albis Zurich Switzerland: ZOMOFI Microwave proprietary approach
  8. Location estimation in wireless telecommunication networks: Ekahau proprietary modified WLAN fuzzy locating approach