Routing geograficzny
Routing geograficzny (zwany także georoutingiem lub routingiem opartym na położeniu ) to zasada wyznaczania tras , która opiera się na informacjach o położeniu geograficznym . Jest proponowany głównie dla sieci bezprzewodowych i opiera się na założeniu, że źródło wysyła wiadomość do lokalizacji geograficznej miejsca docelowego zamiast używać adresu sieciowego . W obszarze radia pakietowego sieci, pomysł wykorzystania informacji o położeniu do trasowania został po raz pierwszy zaproponowany w latach 80-tych dla sieci połączeń wzajemnych. Routing geograficzny wymaga, aby każdy węzeł mógł określić swoją własną lokalizację, a źródło wiedziało o lokalizacji miejsca docelowego. Dzięki tym informacjom wiadomość może zostać skierowana do miejsca docelowego bez znajomości topologii sieci lub wcześniejszego wykrycia trasy.
Podchodzi do
Istnieją różne podejścia, takie jak strategie jednościeżkowe, wielościeżkowe i oparte na powodziach (patrz ankieta). Większość strategii jednościeżkowych opiera się na dwóch technikach: zachłannym przekazywaniu i routingu twarzowym . Przekierowanie zachłanne próbuje na każdym kroku przybliżyć wiadomość do miejsca docelowego, korzystając tylko z informacji lokalnych. W ten sposób każdy węzeł przekazuje wiadomość do sąsiada, który jest najbardziej odpowiedni z lokalnego punktu widzenia. Najbardziej odpowiednim sąsiadem może być ten, który na każdym kroku minimalizuje odległość do celu (Chciwy). Alternatywnie można rozważyć inne pojęcie postępu, a mianowicie przewidywaną odległość na linii źródło-cel (MFR, NFP) lub minimalny kąt między sąsiadem a celem (wyznaczanie tras kompasowych). Nie wszystkie z tych strategii są wolne od pętli, tj. wiadomość może krążyć między węzłami w określonej konstelacji. Wiadomo, że podstawowa strategia chciwa i MFR są wolne od pętli, podczas gdy NFP i Compass Routing nie.
Chciwe spedycje mogą doprowadzić do ślepego zaułka, gdzie nie ma sąsiada bliżej miejsca docelowego. Następnie Face Routing pomaga wyjść z tej sytuacji i znaleźć ścieżkę do innego węzła, w którym można wznowić zachłanne przekazywanie. Strategia odzyskiwania, taka jak kierowanie twarzy, jest niezbędna, aby zapewnić, że wiadomość może zostać dostarczona do miejsca docelowego. Połączenie zachłannego przekazywania i wyznaczania tras zostało po raz pierwszy zaproponowane w 1999 roku pod nazwą GFG (Greedy-Face-Greedy). Gwarantuje dostarczanie w modelu sieciowym tzw. grafu jednostkowego dysku. Różne warianty, które zaproponowano później, również dla niejednostkowych grafów dyskowych, opierają się na zasadach GFG.
Trasowanie twarzy zależy ogólnie od planarnego podgrafu; jednak rozproszona planaryzacja jest trudna w przypadku prawdziwych bezprzewodowych sieci czujników i nie skaluje się dobrze w środowiskach 3D.
Chciwe osadzanie
Chociaż pierwotnie opracowano jako schemat trasowania, który wykorzystuje fizyczne położenie każdego węzła, algorytmy trasowania geograficznego zostały również zastosowane w sieciach, w których każdy węzeł jest powiązany z punktem w przestrzeni wirtualnej, niezwiązanym z jego położeniem fizycznym. Proces znajdowania zestawu wirtualnych pozycji dla węzłów sieci, tak aby trasowanie geograficzne przy użyciu tych pozycji było gwarantowane, nazywa się osadzaniem zachłannym .