AODV

AODV（アドホックオンデマンド距離ベクトル）とは

AODV（Ad hoc On-Demand Distance Vector）は、モバイルアドホックネットワーク（MANET）をはじめとする無線アドホックネットワークで使用されるルーティングプロトコルの一つです。ノキア研究所のC. Perkins、カリフォルニア大学サンタバーバラ校のE. Belding-Royer、シンシナティ大学のS. Dasによって共同開発されました。このプロトコルは、ユニキャストとマルチキャストの両方のルーティングに対応しています。

反応型ルーティング

AODVは、要求があった時のみ（オンデマンドで）経路を確立する反応型ルーティングプロトコルです。これに対し、インターネットで一般的なルーティングプロトコルは能動型であり、経路の使用の有無にかかわらず常に経路を探索します。

距離ベクトル型ルーティング

その名の通り、AODVは距離ベクトル型ルーティングプロトコルの一種です。距離ベクトル型ルーティングプロトコルは、経路選択のために各ノードが持つルーティングテーブルに基づいて動作します。しかし、従来の距離ベクトル型ルーティングプロトコルには「無限カウント問題」という課題がありました。AODVでは、この問題を解決するために、DSDVで導入されたシーケンス番号を用いた経路更新を採用しています。

AODVの動作

AODVネットワークは、通信が必要になるまで静止しています。あるノードが通信を始めようとすると、まずそのノードが経路要求（Route Request）をブロードキャストします。この要求は、他のAODVノードによって転送され、各ノードはどのノードからメッセージが届いたかを記録します。こうして、発信元ノードから放射状に一時的な経路が形成されます。

経路の確立

目的のノードへの経路をすでに知っているノードが経路要求を受け取ると、そのノードは一時的な経路を逆にたどって、経路応答（Route Reply）を要求元のノードに送ります。要求元のノードは、受信した経路応答の中から、最もホップ数の少ない経路を選択します。

ルーティングテーブルの管理

ルーティングテーブルの中で使用されていないエントリは、一定時間が経過すると再利用されます。また、リンクが切断された場合には、ルーティングエラーが送信元ノードに返され、上記の経路確立プロセスが再度実行されます。

メッセージの最適化

AODVは、ネットワークの負荷を軽減するために、メッセージ数を少なくするよう設計されています。例えば、経路要求にはシーケンス番号が付与されており、ノードはこれを利用して、すでに処理した経路要求を繰り返し処理することを防ぎます。また、経路要求には「寿命」を表す数値が設定されており、転送回数が制限されています。さらに、経路要求が失敗した場合、一定時間経過するまで再度の経路要求は送信されません。

AODVの利点

AODVの大きな利点は、既存のリンクに沿った通信では余計なトラフィックが発生しないことです。また、距離ベクトル型ルーティングはシンプルであり、メモリや計算能力をそれほど必要としません。

AODVの欠点

一方で、AODVはコネクション確立に時間がかかる傾向があり、経路確立時の通信量が多くなる場合があります。

AODVの技術的解説

オンデマンド経路探索

AODVは、データパケットを送信しようとする際に、オンデマンドで経路を探索します。つまり、データ送信の必要が生じた時に初めて、経路確立要求が行われ、経路が確立されます。

シーケンス番号による経路特定

AODVでは、送信先シーケンス番号（DestSeqNum）を用いて、最新の経路を特定します。これは、Dynamic Source Routing（DSR）との大きな違いです。DSRでは送信元ノードでルーティングを行い、データパケットに完全な経路情報が格納されます。一方、AODVでは、送信元ノードや中間ノードは、フローにおける次のホップに関する情報だけを保持します。

Route RequestとRoute Reply

オンデマンドルーティングプロトコルでは、送信元ノードが送信先への経路を知らない場合、RouteRequestパケットをネットワークにブロードキャストします。1つのRouteRequestで、複数の送信先への経路が得られることもあります。AODVと他のオンデマンドルーティングプロトコルの主な違いは、AODVが送信先シーケンス番号を使用し、最も新しい経路を識別する点にあります。受信したパケットのDestSeqNumが、ノードが保持しているDestSeqNumよりも大きい場合のみ、そのノードは経路情報を更新します。

RouteRequestパケットの構造

RouteRequestパケットには、「送信元識別子（SrcID）」、「送信先識別子（DestID）」、「送信元シーケンス番号（SrcSeqNum）」、「送信先シーケンス番号（DesSeqNum）」、「ブロードキャスト識別子（BcastID）」、「寿命（TTL）」のフィールドが含まれます。DestSeqNumは、送信元が受け入れた経路の新しさを表します。

中間ノードの役割

中間ノードがRouteRequestを受け取ると、そのパケットを次に転送するか、送信先への正しい経路を知っている場合はRouteReplyを返します。中間ノードは、自身の保持する送信先シーケンス番号とRouteRequestパケットの送信先シーケンス番号を比較して、経路情報を更新するかどうかを判断します。同じRouteRequestを複数回受信した場合、BcastIDとSrcIDの組み合わせで識別し、二度目以降は破棄します。

RouteReplyの送信

正しい経路情報を持つ中間ノードや送信先ノード自身が、RouteReplyパケットを送信元に送ることができます。RouteRequestを転送中の中間ノードは、転送元ノードのアドレスとBcastIDを一時的に保持します。そして、対応するRouteReplyが一定時間内に戻ってこない場合、その情報を消去します。これにより、データパケットの送信元ルーティングを行わないAODVで、中間ノードがアクティブな経路を保持し、ルーティングを助けます。

データパケットの転送

あるノードがRouteReplyパケットを受け取ると、そのパケットの転送元ノードに関する情報を保持し、データパケットを対応する送信先へ転送する際に利用します。

長所と短所

長所

AODVの主な長所は、オンデマンドで経路を確立できること、そして送信先シーケンス番号によって最新の経路を容易に探索できることです。また、コネクション確立時の遅延も比較的少ないです。

短所

AODVの短所としては、送信元シーケンス番号が非常に古く、中間ノードが最新ではない送信先シーケンス番号を持っている場合に、一貫性のない経路情報を形成する可能性がある点が挙げられます。また、1つのRouteRequestパケットに対して複数のRouteReplyパケットが返ってきた場合、制御負荷が増大します。さらに、一定間隔でビーコンのようなパケットを送信すると、不要な帯域幅を消費してしまう可能性があります。

外部リンク

AODV カリフォルニア大学サンタバーバラ校
AODVプロトコル INTERNET Watch、「P2Pとワイヤレスの交差点」第7回

もう一度検索