要求条件および方式概要

高密度アドホックネットワークにおいて、オンデマンド型のAODVルーチングプロトコ ルの制御メッセージのオーバヘッドを削減するためにあたっては、以下のような要求条件 を考慮する必要がある。

・ 無線伝播範囲に複数のノードが存在するため、無線通信可能でなるべく離れたノード を用いて、マルチホップのための経路を確立する必要がある（図 5.1）。その際、経路 に参加するノードのみに RREQ メッセージのブロードキャストを行わせることにより、

S

D

S

D

(b) 提案手法 (a) 通常のAODV

図5.1: 方式の概念図

フラッディングされるRREQメッセージの総数の抑制を実現する。

・ 中継するノードを制限することにより、マルチホップ通信が不可能なノードが生じな いようにする必要がある。特に、ノードの起動や移動により、新たなノードが発生し た場合にも、そのノードとの通信を保証する必要がある。

・ 中継するノードを選択するために、すべてのノードが定期的なメッセージを交換する というオーバヘッドを導入しないようにする必要がある。

・ 起動直後や移動直後のように、自分自身の隣接ノードの状況が不明な場合でも、速や かに通信が開始可能である必要がある。

2章で述べたように、本来のAODVでは、あるノードが送信したRREQメッセージはそ のノードのすべての隣接ノードにより再ブロードキャストされ、その動作が繰り返される。

このため、各ノードは自身が送出したRREQメッセージが再ブロードキャストされたもの を受信することにより、自分の隣接ノードの情報を入手できることになる。このため、

RREQ メッセージが送信されれば、各ノードで Hello メッセージを送信したことと同等に なると考えられる[37]。一方、AODVにも Helloメッセージが定義されているが(TTLを 1 にしたRREPメッセージ)、そのメッセージはアクティブな経路の情報を持つノードのみが 送信するもので、さらに必ずしも送信される必要はないと定められている。このため、

AODVのHelloメッセージを用いて隣接ノードの情報を交換することはできない。

5.1.1 RREQ メッセージの転送手順

以上のような要求条件および背景を考慮し、RREQ メッセージの処理に関して、次のよ うな方式を採用することとした[38,39,40]。

(1) あるノードの無線伝播範囲にあるノードのうち、離れて存在するノードをバウンダリ ノードとして選択し、そのバウンダリノードのみに RREQ メッセージの再ブロードキ ャストを行わせることを基本とする。RREPメッセージおよび経路情報の転送はRREQ メッセージのフラッディングで決定された経路に従う。

(2) バウンダリノードの選択は、OLSRで採用されている方法と同様に、各ノードの隣接ノ ードのリストを交換することにより、自分の 2 ホップ先のノード (2 ホップノード)の 集合を入手し、自分自身の隣接ノード集合となるべく異なった隣接ノード集合を持つ ノードを選択することにより行う。これにより、電波伝播範囲で、なるべく離れて存 在するノードがバウンダリノートとして選ばれることが期待される。

(3) 隣接ノードのリストの通知は、RREQメッセージにより行わせる。このため、RREQメ ッセージにその送信ノードの隣接ノード IP アドレスのリストを持たせる。さらに RREQ メッセージにおいては、その RREQを再ブロードキャストすべきバウンダリノ

ードもあわせて通知する。ここで、RREQ における隣接ノードとバウンダリノードの リストは、再ブロードキャストされるごとに送信ノードのものに更新されることに注 意する必要がある。

(4) バウンダリノードは、RREQ メッセージを送信する直前に、その時点での最新の隣接 ノード情報を用いて決定する。また、ノードが起動直後などで所有する隣接ノードの 情報が不十分な場合に対処するために、計算されたバウンダリノードが一定数以下の 場合は、十分に隣接ノード情報が集まっていないと判断し、送信する RREQ メッセー ジをすべての隣接ノードにより再ブロードキャストさせるようにする。これはバウン ダリノードの指定にブロードキャストアドレスを指定することにより行う。

(5) RREQ メッセージを受信したノードは、隣接ノードリストを解析するとともに、本来 のAODVと同様にそのRREQメッセージを送信した隣接ノードへのルーチングテーブ ルをセットする。次に、RREQメッセージのOriginator IP AddressとRREQ IDから重複 して受信されたメッセージであることが判明した場合は無視する。そうでなければ、

Originator IP Addressで指定される発信元ノードへのリバースパスに関するルーチング

テーブルをセットする。さらに、(7)に示すような、RREQ メッセージに応答できる場 合以外の場合は、以下のようにして、その RREQ メッセージを再ブロードキャストす る。

• バウンダリノードリストに自分自身が指定されている場合(ブロードキャストア ドレスの場合も含む)に、そのRREQメッセージを再ブロードキャストする。

• さらに、新たなノードが起動された場合など、ネットワークの動的な変化に対応 するために、次のような手順を追加する。

− 受信したノードが隣接ノードリストに含まれない場合は、送信ノードが自分 の存在を認識していないと判断し、送信ノードに通知するために、RREQ メ ッセージを再ブロードキャストする。

− 自身が先にRREQメッセージを送信した時点以降に、自分自身の隣接ノード 集合が変更されている場合は、バウンダリノードに指定されていない場合で も、RREQメッセージを再ブロードキャストする。

(6) 隣接ノードが無線伝播範囲外に移動した場合を考慮し、以下のように対応する。

• RREQメッセージ送信後、一定時間内に指定したバウンダリノードからRREQメ ッセージが受信できない場合、次のRREQメッセージは受信した全てのノードが 再ブロードキャストを行うこととする。

• TTL最大で RREQをブロードキャストした後、RREP が受信できない場合は、全 てのノードが再ブロードキャストを行うRREQを送信する。

(7) RREQメッセージを受信したノードが、Destination IP Addressで指定された宛先ノード 自身である場合は、無条件に RREP メッセージを返送する。また、宛先ノードへの経 路情報を有している場合は、以下のように対応する。

• RREQ メッセージにブロードキャストアドレスではないバウンダリノードが指定 されている場合は、自分自身がバウンダリリストに含まれていれば RREP メッセ ージを返送するが、含まれていない場合は返送しない。

• RREQ メッセージのバウンダリノードの指定が、ブロードキャストアドレスであ る場合は、無条件に返送する。

(8) これまで述べた手順以外については、根拠のないRREPメッセージの送出、RERR (Route

Error)メッセージの処理、Helloメッセージの処理などを含め、本来のAODVと同一の

手順に従うこととする。なお、Helloメッセージの未達により隣接ノードとの間のリン ク切断が検出された場合は、併せて隣接ノード集合の変更を行うこととする。

5.1.2 Helloメッセージの転送手順

(1) RREPメッセージを送信もしくは受信したノードのみが、その発信元ノードと宛先ノー ドに対する有効な経路を保持するために Hello メッセージを送信することを基本とす る。

(2) RREQ メッセージを受信したノードは、その RREQ メッセージを送信した隣接ノード への経路と、発信元ノードに対する経路を、「RREP メッセージのみ転送可能な状態」

にセットする。

(3) RREPメッセージを受信したノードは、宛先ノードに対して「有効な状態」の経路を作 成し、また発信元ノードに対する経路が「RREPメッセージのみ転送可能な状態」であ れば、その経路を「有効な状態」に更新し、RREPメッセージを転送する。また、この 時に発信元ノードと宛先ノードへのネクストホップに対する経路も「有効な状態」に 更新する。

(4) 「有効な状態」である経路のみに対してHelloメッセージを転送することとする。

5.2