Loading article…
地理ルーティング（ジオルーティング[1]または位置ベースルーティングとも呼ばれる）は、地理的な位置情報に依存するルーティング原理です。これは主に無線ネットワーク向けに提案されており、送信元がネットワークアドレスを使用する代わりに宛先の地理的位置にメッセージを送信するという考えに基づいています。パケット無線ネットワークの分野では、ルーティングに位置情報を使用するという考え方は、1980年代に相互接続ネットワーク向けに初めて提案されました[2]。[3]地理ルーティングでは、各ノードが自分の位置を決定でき、送信元が宛先の位置を認識している必要があります。この情報があれば、ネットワークトポロジーの知識や事前の経路検出がなくても、メッセージを宛先にルーティングできます。
アプローチ
シングルパス、マルチパス、フラッディングベースの戦略など、さまざまなアプローチがあります（概要については[4]を参照）。ほとんどのシングルパス戦略は、貪欲転送とフェイスルーティングという2つの手法に依存しています。貪欲転送は、ローカル情報のみを使用して、各ステップでメッセージを宛先に近づけようとします。したがって、各ノードは、ローカルな観点から最も適切な隣接ノードにメッセージを転送します。最も適切な隣接ノードは、各ステップで宛先までの距離を最小化するノードです（貪欲）。または、別の進行の概念、つまり送信元-宛先ライン上の投影距離（MFR、NFP）または隣接ノードと宛先間の最小角度（コンパスルーティング）を考慮することもできます。これらの戦略のすべてがループフリーであるわけではありません。つまり、メッセージは特定の星座内のノード間を循環できます。基本的な貪欲戦略とMFRはループフリーですが、NFPとコンパスルーティングはそうではないことが知られています。[5]
貪欲転送は行き止まりに陥る可能性があり、宛先に近い隣接ノードは存在しません。その場合、フェイス ルーティングはそのような状況から回復し、貪欲転送を再開できる別のノードへのパスを見つけるのに役立ちます。フェイス ルーティングなどの回復戦略は、メッセージが宛先に確実に届けられるようにするために必要です。貪欲転送とフェイス ルーティングの組み合わせは、1999 年に GFG (Greedy-Face-Greedy) という名前で初めて提案されました。[6]これは、いわゆるユニット ディスク グラフ ネットワーク モデルでの配信を保証します。後に提案されたさまざまなバリエーション [7]は 、非ユニット ディスク グラフ用でもあり、GFG の原理に基づいています。[1]
フェイスルーティングは一般に平面サブグラフに依存しますが、分散平面化は実際の無線センサーネットワークでは困難であり、3D環境にうまく適応できません。 [8]
貪欲埋め込み
もともとは各ノードの物理的な位置を使用するルーティング方式として開発されたが、地理ルーティングアルゴリズムは、各ノードが物理的な位置とは関係なく仮想空間内の点に関連付けられているネットワークにも適用されている。ネットワークのノードの仮想位置のセットを見つけ、これらの位置を使用した地理ルーティングが成功することを保証するプロセスは、貪欲埋め込みと呼ばれる。[9]
参照
参考文献
- ^ ab Ruehrup, Stefan (2009). Liu; Chu; Leung (編). 地理ルーティングの理論と実践(PDF) . アドホックおよびセンサーワイヤレスネットワーク: アーキテクチャ、アルゴリズム、プロトコル。 Bentham Science.
- ^ Takagi, H.; Kleinrock, L. (1984 年 3 月). 「ランダムに分散されたパケット無線端末の最適伝送範囲」. IEEE Transactions on Communications . 32 (3): 246–257. CiteSeerX 10.1.1.64.9747 . doi :10.1109/TCOM.1984.1096061.
- ^ Finn, Gregory G. (1987 年 3 月)。「大都市規模のインターネットワークにおけるルーティングとアドレス指定の問題」(PDF)。南カリフォルニア大学、ISI/RR-87-180。
- ^ イワン・ストイメノビッチ (2002)。 「アドホックネットワークにおける位置ベースのルーティング」。IEEE コミュニケーション マガジン。40 (7): 128–134。CiteSeerX 10.1.1.6.6012。土井：10.1109/MCOM.2002.1018018。
- ^ Stojmenovic, Ivan; Lin, Xu (2001). 「ワイヤレスネットワーク向けの保証された配信を備えたループフリーハイブリッドシングルパス/フラッディングルーティングアルゴリズム」IEEE Transactions on Parallel and Distributed Systems . 12 (10): 1023–1032. CiteSeerX 10.1.1.67.7527 . doi :10.1109/71.963415.
- ^ Bose, P. ; Morin, P. ; Stojmenovic, I.; Urrutia, J. (1999). 「アドホック無線ネットワークにおける保証された配信によるルーティング」。モバイルコンピューティングおよび通信のための離散アルゴリズムと方法に関する第3回国際ワークショップ (DIALM '99) の議事録。pp . 48–55。doi : 10.1145/313239.313282。
- ^ Djenouri, Djamel; Balasingham, Ilangko (2011). 「ワイヤレスセンサーネットワーク向けのトラフィック差別化ベースのモジュラー QoS ローカライズルーティング」. IEEE Transactions on Mobile Computing . 10 (6): 797–809. doi :10.1109/TMC.2010.212. S2CID 11139687.
- ^ Kim, Y; Ramesh Govindan ; Karp, Brad.; Scott Shenker (2005). 「地理的なフェイスルーティングの落とし穴について」。モバイルコンピューティングの基礎に関する 2005 年共同ワークショップの議事録。pp. 34–43。doi : 10.1145 /1080810.1080818。
- ^ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H .; Shenker, Scott ; Stoica, Ion (2003)、「位置情報なしの地理ルーティング」、Proc. 9th ACM Mobile Computing and Networking (MobiCom)、pp. 96–108。