地理的経路設定

地理的ルーティング（ジオルーティング^{[ 1 ]}または位置ベースルーティングとも呼ばれる）は、地理的位置情報に依存するルーティング原理です。これは主に無線ネットワーク向けに提案されており、送信元がネットワークアドレスを使用する代わりに宛先の地理的位置にメッセージを送信するという考えに基づいています。パケット無線ネットワークの分野では、ルーティングに位置情報を使用するという考えは、相互接続ネットワーク向けに1980年代に初めて提案されました^{[ 2 ]}。^{[ 3 ]}地理的ルーティングでは、各ノードが自身の位置を特定でき、送信元が宛先の位置を認識している必要があります。この情報があれば、ネットワークトポロジや事前の経路探索を知らなくても、メッセージを宛先にルーティングできます。

シングルパス、マルチパス、フラッディングベースの戦略など、さまざまなアプローチがあります（概要については^{[ 4 ]}を参照）。ほとんどのシングルパス戦略は、グリーディ転送とフェイスルーティングの2つの技術に依存しています。グリーディ転送は、ローカル情報のみを使用して、各ステップでメッセージを宛先に近づけようとします。したがって、各ノードは、ローカルの観点から最も適切な隣接ノードにメッセージを転送します。最も適切な隣接ノードは、各ステップで宛先までの距離を最小にするノードです（グリーディ）。あるいは、進捗の別の概念、つまり送信元-宛先線上の投影距離（MFR、NFP）、または隣接ノードと宛先の間の最小角度（コンパスルーティング）を考慮することもできます。これらの戦略のすべてがループフリーであるとは限りません。つまり、メッセージが特定のコンステレーション内のノード間を循環する可能性があります。基本的なグリーディ戦略とMFRはループフリーですが、NFPとコンパスルーティングはループフリーではないことが知られています。^{[ 5 ]}

貪欲転送方式：送信元ノード（S）は、メッセージを宛先（D）へ転送するための中継ノードを見つけるために、いくつかの選択肢があります。A = 転送進捗状況が最も近いノード（NFP）、B = 半径内で転送進捗状況が最も高いノード（MFR）、C = コンパスルーティング、E = 貪欲

面ルーティング：メッセージは通信グラフの面の内部に沿ってルーティングされ、SD線（赤色）を横切るエッジで面が切り替わります。最終的なルーティングパスは青色で示されています。

グリーディ転送は、宛先により近い隣接ノードがない行き止まりに陥る可能性があります。その場合、フェイスルーティングは、その状況から回復し、グリーディ転送を再開できる別のノードへのパスを見つけるのに役立ちます。フェイスルーティングなどの回復戦略は、メッセージが宛先に確実に配信されるようにするために必要です。グリーディ転送とフェイスルーティングの組み合わせは、1999 年に GFG (Greedy-Face-Greedy) という名前で初めて提案されました。^{[ 6 ]}これは、いわゆるユニットディスクグラフネットワークモデルでの配信を保証します。後に提案されたさまざまなバリアント ^{[ 7 ]} は、非ユニットディスクグラフにも適用され、GFG の原理に基づいています。^{[ 1 ]}

一般的に面ルーティングは平面サブグラフに依存しますが、分散平面化は実際の無線センサーネットワークでは難しく、3D 環境への拡張性も低いです。 ^{[ 8 ]}

地理的ルーティングアルゴリズムは、もともとは各ノードの物理的な位置を利用するルーティング方式として開発されましたが、各ノードが物理的な位置とは無関係な仮想空間内の点に関連付けられているネットワークにも適用されています。これらの位置を使用した地理的ルーティングが確実に成功するように、ネットワークのノードの仮想位置のセットを見つけるプロセスは、グリーディ埋め込みと呼ばれます。^{[ 9 ]}

• アドホックルーティングプロトコルの一覧
• バックプレッシャールーティング