極限的オポチュニスティックルーティング（ExOR）は、MIT人工知能研究所のサンジット・ビスワスとロバート・モリスによって発明され、2005年の論文で説明された、無線アドホックネットワーク用のルーティングプロトコルとメディアアクセス制御の組み合わせです。[1]
このアルゴリズムで使用されるブロードキャストと再送信戦略については、すでに文献で説明されている。[2] [3] [4] [5] [6] [7] ExORは、利用可能なデジタル無線を操作して、これまでは非現実的だったアルゴリズムの最適化を行うことができるため、価値がある。
以前はオープンソースであった[8] ExORは2005年には利用可能でしたが、現在は入手できません。[独自の研究? ]
歴史
このアルゴリズムは、インターネットプロトコル（IP）のパケットを伝送するように設計されており、他のサービスを最大限に利用できるようにします。発明当時、携帯機器向けのインターネットサービスは、デジタル無線が有線インターネットサービスに広く取って代わっていました。専用の集積回路は、低コストで広く入手可能でした。
当時 (2005 年) MIT はOne Laptop per Childプロジェクトに携わっていました。これは、貧困層の子供の教育を支援するために安価な低消費電力コンピュータを作成する試みでした。その利点は、書籍や紙などの消耗品のデジタルコピーのコストが削減され、双方向性と柔軟性によって教育が改善される可能性があると考えられていました。ラップトップの重要な機能の 1 つは、ラップトップが協力して 1 台のコンピュータでは賄えないリソースを提供するワイヤレス アドホック ネットワークでした。実用的でありながら優れたネットワーク アルゴリズムは、ラップトップに必要なコストと電力を削減することで、より多くの子供の教育に直接役立ちます。ワイヤレス アドホック ネットワークでは、標準的な無線 (つまり、802.11用の集積回路を使用) を使用し、中間無線を少なくして長距離にわたってより多くのデータを転送すれば、コストと電力消費を抑えることができます。
このプロトコルはRoofNetでプロトタイプ化されました。[引用が必要]
アルゴリズム
送信元となる無線機は、パケットのバッチをブロードキャストします。中間の無線機のタイマーが切れると、宛先から遠い無線機は、近い無線機がまだ再送信していないパケットを再送信します。
複雑さの大部分は、この基本方式をサポートすることです。中間無線機のタイマーは、より近い無線機がパケットを送信するために必要な送信時間の推定値に設定されます。推定値は、バッチ内のパケット数と、各中間無線機からの正しい送信確率に基づいて計算されます。
ExOR は、従来のルーティング プロトコル「RRTc」を使用して、ネットワーク内のデジタル無線の各ペア間の送信が成功する確率に関する情報を収集します。
著者らは、パケットの再送によって利用可能な無線時間が過度に消費される可能性があることを懸念していました。そのため、ExORはパケットの再送を可能な限り最小限に抑えるよう努めています。これがExORの高い効率の理由です。
まず、送信無線はルーティング情報から、送信無線から宛先へデータを転送できる可能性のある無線のリストを作成します。無線の番号は、宛先までの距離が近いものから遠いものの順に並べられたリスト に配置されます。宛先無線はリストの先頭に配置されます。また、送信元無線は、パケットの進行状況を測定するために、バッチ内のパケットのリストを作成します。この「バッチマップ」は、パケットごとに1つの無線番号を持つ配列です。各無線番号は、そのパケットを送信した無線であり、宛先無線に最も近い無線です。各データパケットには無線のリストがあり、パケットは先頭に配置されます。このリストは、IPアドレスではなく無線番号を使用することで、各パケットのスペースを節約します。次に、送信無線は最初のデータパケットのバッチをブロードキャストします。これによりタイマーが開始されます。パケットを受信したが、パケット内のリストに含まれていない無線は、データパケットを無視します。これらの無線は、パケットを受信するとすぐにパケットを破棄します。パケット内の無線のリストに含まれる無線は、受信したデータパケットを保存します。また、バッチマップを更新します。無線機がタイムアウトすると、宛先に近い無線機が再送信していないパケットが送信されます。これらのパケットには、バッチ内のパケットの進行状況に関する無線機の入手可能な最良の情報 (バッチ マップ) が含まれます。特に、各パケットのバッチ マップには、再送信するパケットごとに再送信機の無線番号が含まれます。無線機が宛先に近い無線機から送信されたパケットを受信すると、そのパケットのコピーを消去します。そのパケットを再送信する必要はありません。ただし、バッチ内のパケットの進行状況に関するバッチ マップも更新します。このように、宛先から遠い無線機が再送信を盗聴してバッチ マップを更新するため、パケットの進行状況に関する情報は送信元に向かって逆方向に流れます。
送信元無線に近い場所での再送信は後から行われるため、確認応答パケットが送信されない場合でも、パケットの進捗情報は送信元無線に返送されます。最終的に、どこにも送られなかったパケットがいくつか残るのが一般的です。これらのパケットは、信頼性の低い経路に頼ることなく、最も信頼性の高い経路で送信されます。
ExORは大きなデータブロックでより効率的に動作します。これにより、バッチが代替ルートを見つける機会が増えます。ただし、バッチマップも大きくなります。そのため、100,000バイトを超えるデータブロックは、バッチと呼ばれるデータパケットのグループに分割されます。それより小さなメッセージは、最も信頼性の高いルートで送信されます。主要なインターネットプロトコルであるTCPはデータストリームを送信するため、ExORはローカルプロキシデータサーバーを使用してデータブロックを蓄積します。
各パケットは最小限の回数で再送され、各送信で可能な限り長い距離をカバーします。受信側がパケット情報をブロードキャストすることで多少の時間は浪費されますが、これは確認応答メッセージが失われた場合に再送する通常のルーティング方式よりもはるかに短い時間です。確認応答パケットは存在せず、衝突もありません。これにより無線時間が節約されます。著者らは、このプロトコルは固定の「最適な」ルーティングを持つ通常のルーティングプロトコルに比べて約2倍の効率であると述べています。配信時間の変動は他のアドホックネットワークの4分の1であり、これはアルゴリズムが利用可能な最良の配信時間を使用しているためだと述べています。著者らは、プロトコルが送信用に大量のデータブロックを蓄積するようにテストを設定しました。データは、ネットワークの応答速度と無線システムの効率の間にトレードオフがあることを示しています。一部のゲームでは、高効率ネットワークにおけるバッファリング量の増加が応答時間の影響を受ける可能性があります。
テスト
ExORの効率推定は、clickと呼ばれるLinuxルーティングツールキットを用いた実際の実装に基づいています。ソフトウェアの実験版は、マサチューセッツ州ケンブリッジにある「RoofNet」と呼ばれる屋上ネットワーク上でシミュレーションとインストールの両方で実施されました。このデータは、同様のネットワークの公開データと比較されました。[9]
代替案
非常によく似た日和見ルーティング方式は、カリフォルニア大学リバーサイド校のZhenzhen YeとYingbo Huaによっても独立して提案され、2005年に論文で発表されました。[10]
参照
- AODV – 無線ルーティングプロトコルPages displaying short descriptions of redirect targets
- バックプレッシャールーティング - 待ち行列理論におけるアルゴリズム
- ダイナミックソースルーティング – 無線メッシュネットワークのルーティングプロトコル
- Hazy Sighted リンクステートルーティングプロトコル – 無線ネットワークルーティングアルゴリズム
- アドホックルーティングプロトコルのリスト
- OLSR – モバイルアドホックネットワーク向けに最適化されたIPルーティングプロトコルPages displaying short descriptions of redirect targets
参考文献
- ^ ExOR: 無線ネットワーク向けオプチュニスティックマルチホップルーティング Sanjit Biswas、Robert Morris、SIGCOMM '05 発表、2005 年、Copyright ACM、ペンシルバニア州フィラデルフィア、ACM No. 1-59593-009-4/05/0008
- ^ 「ネットワークにおける分散空間ダイバーシティの活用」JN Laneman、G. Wornell; 情報理論的協力ダイバーシティ方式をいくつか分析しているが、無線機はスペクトルを共有するために特殊な技術を使用している。ExORは、タイムスロット方式をより長い時間スケールに適応させ、市販の無線機を用いてソフトウェアで実装できる。
- ^ 「フェージングチャネルとキャプチャを考慮したマルチホップパケット無線ネットワークにおける選択ダイバーシティ転送」P. Larsson、SIGMOBIL Mob. Comm. Rev. 5(4):47-564、2001
- ^ 「OAR、マルチレートネットワークのためのオポチュニスティックメディアアクセス」、B. Sadeghi、V. Kanodia、A. Sabharwal、E. Knightly; ACM Mobicom 2002の議事録、2002年9月
- ^ 「リンクレイヤリング無線アドホックネットワークにおけるパスダイバーシティの活用」第6回IEEE WoWMoMシンポジウム論文集、2005年6月
- ^ 「無線ネットワークにおけるMAC層エニーキャスト」、R. Roy ChowdhuryとN. Vaidya、ネットワークのホットトピックに関する第2回ワークショップ（HotNets II）、2003年11月
- ^ 「Geographic Random Forwarding (GeRaf)」、M. Zorzi、R. Rao、IEEE Transactions on Mobile Computing、2(4)、2003年10月
- ^ [1] [永久リンク切れ]
- ^ 「802.11b メッシュネットワークのリンクレベル測定」、D. Aguayo、J. Bicket、S. Biswas、G. Judd、R. Morris、ACM SIGCOMM 2004、2004年8月
- ^ 無線中継器を介したデータ転送のリンク層ポリシーについて Zhenzhen Ye、Yingbo Hua、IEEE MILCOM '05 発表、2005 年、Copyright IEEE、アトランティックシティ、ニュージャージー州、2005 年 10 月
