連想性に基づくルーティング

連想ベースルーティング^{[1] [2] [3] [4]} (一般にABRと呼ばれる)は、ワイヤレスアドホックネットワーク(モバイルアドホックネットワーク(MANET)やワイヤレスメッシュネットワークとも呼ばれる)向けに発明されたモバイルルーティングプロトコルです。ABRは1993年に発明され、 1996年に米国特許を申請し、1999年に特許を取得しました。ABRは、ケンブリッジ大学で博士号取得中だったChai Keong Tohによって発明されました。

ABR には 3 つのフェーズがあります。最初のフェーズはルート検出フェーズです。ユーザーがデータの送信を開始すると、プロトコルは要求を傍受し、ワイヤレス インターフェイスを介して検索パケットをブロードキャストします。検索パケットがノードからノードに伝播すると、ノード ID と安​​定性の情報がパケットに追加されます。パケットが最終的に宛先ノードに到達すると、送信元から宛先までのパスを記述するすべての情報が受信されます。その場合、宛先は最適なルートを選択し (送信元から宛先までのパスが複数ある場合があるため)、選択したパスを介して送信元ノードに REPLY を返します。

パケットが宛先から送信元へ逆方向に転送されるとき、各中間ノードはルーティング テーブルを更新し、上流ノードからデータを受信したときにルーティング方法を知っていることを示します。送信元ノードが REPLY を受信すると、ルートが正常に検出され、確立されます。このプロセスはリアルタイムで実行され、数ミリ秒しかかかりません。

ABR は、長期間存続するルートまたはアソシエティビティが安定したルートを確立するため、確立されたルートのほとんどでリンクが切断されることはほとんどありません。ただし、1 つ以上のリンクが切断されると、ABR は直ちに RRC (ルート再構築フェーズ) を呼び出します。RRC は基本的に、上流ノード (リンク切断を感知) にローカル ルート修復を実行させることで、切断されたリンクを修復します。ローカル ルート修復は、宛先への代替の長期間存続する部分ルートを検索するローカル ブロードキャスト クエリを実行することによって実行されます。

ABR ルート メンテナンスは、次の要素で構成されます。

• （a）部分的な経路探索、
• （b）無効な経路の消去、
• （ｃ）有効な経路更新、および
• （d）新しいルートの発見（最悪の場合）。

検出されたルートが必要なくなると、ソース ノードによって RD (ルート削除) パケットが開始され、ルート内のすべての中間ノードがルーティング テーブル エントリを更新し、この削除されたルートに関連付けられたデータ パケットのリレーを停止します。

RD を使用してルートを削除するだけでなく、ABR は、一定期間にわたってルートに関連するトラフィック アクティビティがない場合に、ルート エントリがタイムアウト後に期限切れになるか無効になるソフト ステート アプローチを実装することもできます。

1998年、ABRはLinuxカーネルに実装され、WaveLAN 802.11a PCMCIAワイヤレスアダプタを搭載したさまざまなブランドのラップトップ（IBM Thinkpad、COMPAQ、Toshibaなど）に搭載されました^。600メートル^{を超える距離にまたがる6}ノードのワイヤレスアドホックネットワークが動作し、その成功は1999年のMobile Computing Magazineに掲載されました。ネットワークではさまざまなテストが実行されました。

1. 3 ホップ ルートを介して送信元から送信先まで最大 500 MBytes のデータを転送します。
2. リンク切れと自動リンク修復が機能していることが証明されました
3. 自動ルート検出
4. ルート削除
5. アドホック モードの Web サーバー - ソースがクライアント、宛先が Web サーバー
6. マルチメディア情報の伝送（音声^[9]およびビデオ）
7. アドホック経由のTELNET
8. FTP経由のアドホック
9. アドホック経由のHTTP

また、以下のネットワーク パフォーマンス測定も行いました。

1. エンドツーエンドの遅延
2. TCPスループット
3. パケット損失率
4. ルート発見遅延
5. ルート修復遅延
6. パケットサイズがスループットに与える影響
7. ビーコン間隔がスループットとバッテリー残量に与える影響

このプロトコルの拡張バージョンは、2002年に防衛請負業者TRW社によって現場で実装されました^[10]。プロトコルに行われた拡張には、(a)ネットワーク層QoSの追加と(b)ルート優先順位機能が含まれます。

ABRは米国特許5987011 ^[11]を取得しており、譲受人は英国 ケンブリッジのキングスカレッジです。

他のいくつかのモバイル アドホック ルーティング プロトコルでは、ABR の安定性の概念が組み込まれているか、ABR プロトコルの拡張が行われています。以下に例を示します。

• 信号安定性に基づく適応ルーティングプロトコル（SSA）^[12]
• 拡張連想ベースルーティングプロトコル ( EABR ) ^{[引用が必要]}
• 連想性ベースルーティングの代替拡張（AEABR）^[13]
• 最適化された連想閾値ルーティング（OABTR）^[14]
• 連想性に基づくクラスタリングプロトコル（ABCP）^[15]
• ファジーベースの信頼連想性に基づくルーティング (ファジー ABR )
• 連想ティック平均連想ベースルーティング（ATA-AR）^[16]
• 自己適応型Q学習に基づく信頼ABR（QTABR）^[17]
• ABRへのサービス品質拡張（QoSE-ABR）^[18]
• 連想ベースマルチキャストルーティング（ABAM）^[19]
• マルチパスアソシエティビティベースルーティング（MABR）^[20]
• 無線センサーネットワークのための連想ルーティング^[21]
• 連想型車両アドホックネットワーク（VANET）^[22]