AODV

AODV（Ad hoc On-Demand Distance Vector、アドホックオンデマンド距離ベクトル）は、モバイルアドホックネットワーク (MANET) と他の無線アドホックネットワークのためのルーティングプロトコルの1つ。ノキアの研究所の C. Perkins とカリフォルニア大学サンタバーバラ校の E. Belding-Royer とシンシナティ大学の S. Das が共同開発した。ユニキャストおよびマルチキャストのルーティングが可能である。反応型のルーティングプロトコルであり、要求があったときのみ（オンデマンドで）経路を確立する。これとは対照的にインターネットで一般的なルーティングプロトコルは能動型であり、経路の使用の有無とは無関係にルーティング経路を探す。その名が示す通り、AODVは距離ベクトル型ルーティングプロトコルの一種である。AODVは距離ベクトル型が抱える「無限カウント問題」を回避するため、DSDVで導入された経路更新でのシーケンス番号使用を採用している。

動作

AODVでは、ネットワークはコネクションを必要とするまでは静かである。あるネットワークノードがコネクションを確立しようとしたとき、直近のAODVノードが要求をブロードキャストする。他のAODVノードはこのメッセージを転送しつつ、そのメッセージがどのノードから届いたかを記録し、全体として発信源から放射状に広がる一時的経路群を形成する。既に目的ノードへの経路を知っているノードにそのようなメッセージが届くと、その一時的経路を逆にたどってメッセージを要求ノードまで届ける。要求元のノードはこのように返ってきたメッセージを調べ、ホップ数が最も少ない経路を使う。ルーティングテーブルの使わないエントリは一定時間後に再利用される。

リンクが切れると、ルーティングエラーが送信元ノードに返され、上記プロセスが繰り返される。

この通信プロトコルは、ネットワークの容量をなるべく維持するためメッセージ数を少なくするよう心がけている。例えば、経路要求にはそれぞれシーケンス番号が付与されている。ノードはこのシーケンス番号を使い、すでに処理した経路要求を繰り返し処理しないようにしている。また、経路要求には「寿命」を表す数があり、転送回数が制限されている。また、経路要求が失敗した場合、最初の経路要求のタイムアウト時間の2倍以上の時間が経過しないと、再度の経路要求が送信できない。

AODVの利点は、既存のリンクに沿った通信に余分なトラフィックを発生しない点である。また、距離ベクトル型ルーティングは単純であり、メモリや計算能力をそれほど必要としない。しかし、AODVはコネクション確立に時間がかかる傾向があり、経路確立時の通信量は他の方式よりも多い。

技術的解説

AODVルーティングプロトコルはオンデマンドで経路を探索する。すなわち、あるノードがデータパケットを送信しようとしたとき、経路確立要求が発生し、経路が確立される。AODVでは送信先シーケンス番号を使い、最近の経路を特定する。Dynamic Source Routing (DSR) との大きな違いは、DSRでは送信元ノードでのルーティングを採用しており、データパケットにたどるべき完全な経路情報が格納されている点である。一方、AODVでは送信元ノードや中間ノードはそのフローでの次のホップ（ノード）に関する情報だけを持っている。オンデマンド方式のルーティングプロトコルでは、送信元ノードが送信先への経路を知らない場合、RouteRequest パケットをネットワークにばらまく。1つの RouteRequest で異なる送信先への複数の経路が得られることもある。AODVと他のオンデマンド方式のルーティングプロトコルの主な違いは、AODVが「送信先シーケンス番号 (DestSeqNum)」を使い、その送信先への最新の経路を識別する点である。受信したパケットのDestSeqNumがノードの保持しているDestSeqNumより大きい場合のみ、そのノードは経路情報を更新する。

RouteRequest には「送信元識別子 (SrcID)」、「送信先識別子 (DestID)」、「送信元シーケンス番号 (SrcSeqNum)」、「送信先シーケンス番号 (DesSeqNum)」、「ブロードキャスト識別子 (BcastID)」、「寿命 (TTL)」というフィールドがある。DestSeqNum は送信元が受け入れた経路の新しさを示している。中間のノードが RouteRequestを受け取ると、単に次に転送するか、送信先への正しい経路を知っている場合はRouteReplyを返す。中間のノードでの経路情報が正しいかどうかは、そのノードの持つ送信先シーケンス番号とRouteRequestパケットにある送信先シーケンス番号を比較することで判断する。同じRouteRequestを複数回受け取ったことはBcastIDとSrcIDの組で識別でき、二度目以降の場合は単に捨てる。正しい経路情報を持つ中間ノードでも送信先ノード自身でも、RouteReplyパケットを送信元に送ることができる。RouteRequestを転送中の中間ノードでは、転送元ノードのアドレスとBcastIDを保持しておく。そして対応するRouteReplyが一定時間以内に戻ってこない場合、その情報を消去する。これにより、データパケットの送信元ルーティングを行わないAODVで、アクティブな経路を中間ノードが保持することでルーティングを助ける。あるノードがRouteReplyパケットを受け取ると、そのパケットの転送元ノードに関する情報を保持しておき、データパケットを対応する送信先へ転送する際の転送先の決定に利用する。

長所と短所

このプロトコルの主な長所は、経路をオンデマンドで確立でき、送信先シーケンス番号によってその送信先への最新経路の探索を容易にする点である。コネクション確立時の遅延は大きくない。このプロトコルの短所は、送信元シーケンス番号が非常に古く、中間ノードが大きいけれども最新ではない送信先シーケンス番号を持っている場合、その経路情報は古く、一貫性のない経路情報を形成することがある点である。また、1つのRouteRequestパケットに対して複数のRouteReplyパケットが返ってきた場合、制御負荷が大きくなる。別の短所として、一定間隔でビーコンのようなパケット送信を行うと、不要な帯域幅を消費してしまう点が挙げられる。

関連項目

• メッシュネットワーク
• ZigBee

外部リンク

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