起動直後のノードの通信例

次に、ノードSがアドホックネットワーク内でシステムを起動した直後、ノードDへIP パケットを送信しようとした場合の経路の確立手順を示す。なお、他のノードは互いに隣 接ノード情報を有していると想定する。

まず、Sは自分のルーチングテーブルにDへの経路情報がないことを確認するとRREQ を作成する。この際、S は隣接ノードの情報を有していないため、RREQ の Neighbor IP

Addressフィールドは空で、Boundary IP Addressフィールドにはブロードキャストアドレス

がセットされる。またAODVでは、不必要なRREQの拡散を防ぐために、RREQメッセー

ジのIPヘッダのTTLの値を徐々に増加させる拡大リングサーチという手法を用いている。

ここではTTL=3から始めて、2ずつ増加させたと仮定して手順を示す。

Sが送信したRREQメッセージは、Sのすべての隣接ノードが受信する。ここでバウン ダリノードがブロードキャストアドレスに指定されているため、図5.3(a)のように、Sのす べての隣接ノードが再ブロードキャストを行う。例えばノード 1'は、Sを新たに隣接ノー ド集合に加え、S へのルーチングテーブルエントリを作成し、隣接ノードとバウンダリノ ードのリストをRREQメッセージにセットし、TTLを1減らして送信する。このようにS のすべての隣接ノードが自分自身の隣接ノードをセットしてRREQメッセージを再ブロー ドキャストし、Sがそれらを受信することができるため、その段階で Sは自分自身の隣接 ノードの情報を入手することができる。またこの際、RREQを受信した各ノードはSに対 する経路情報を保持するが、そのステータスを「RREP のみ転送可能な状態」にセットす る。この状態ではHelloメッセージを送信することはない。

次に、1'が送信したRREQメッセージは、図5.3(b)のように、1'のバウンダリノードでか つこれまでにそのRREQメッセージを受信していないノードにより、さらに再ブロードキ ャストされる。またそのようなノードの1つであるノード2により同様な再ブロードキャ ストが行われた様子を図5.3(c)に示す。

Sからの最初のRREQメッセージはTTL=3で送信されているため、ここでフラッディン グが終了する。この間に宛先ノードDも、Dへの経路を所有するノードも存在しないため、

RREPメッセージは送信されず、発信元ノードSは、タイムアウト後、TTL=5として新た なRREQメッセージを送信する。その転送のようすを図5.4に示す。

まず、その前のRREQメッセージのフラッディングにより、Sは隣接ノード集合を所有 しているため、それを用いてバウンダリノードを計算する。そのノード数が一定数あるた

め(図5.4(a)では8つのバウンダリノードがあるとしている)、隣接ノードとバウンダリノー

ドを指定して、RREQメッセージを送出する(図5.4 (a)参照)。ここで、図5.3で例に使用し たノード1'は、バウンダリノードに指定されておらず、代わりにノード1がバウンダリノ ードとして指定されていると想定する。

同様にして、RREQメッセージが、ノード1、ノード2、ノード3と再ブロードキャスト された状況を図5.4 (b)に示す。ここで、ノード2はノード1とノード1'の双方のバウンダ リノードに選択されている。このため、2つの RREQメッセージの双方を受信して、Sへ のリバースパスの経路情報を保持することになる。しかし、2回目の RREQメッセージの 方がSに対応するシーケンス番号として大きな値を含んでいるため、2回目のRREQメッ セージの受信により、Sへのリバースパスの経路はノード 1経由となる。この時のリバー スパスを「RREPのみ転送可能な状態」にセットする。

ここで、ノード4および4'がノードDへの経路を保持していたと仮定する。そこで、ノ ード4がRREQメッセージを受信すると、Sへ向けてリバースルートのための経路情報を 基にRREPメッセージを送信し、さらにノードDへ向けて根拠のないRREPメッセージを 送信する。また、ノード4'がノードDへの経路を知っていても、ノード3のバウンダリノ

(a)1ホップ目

(b)2ホップ目

S

(c)3ホップ目

再ブロードキャ ストを行うノード

D 1

2 S

D 1

S

D 1

2 1'

1'

1'

RREQ

図5.3: 起動直後のノードの最初のRREQメッセージの配信

ードでないため、RREP メッセージを送信することはない。ノード 4から送られた RREP メッセージを受信したノード3は、ノードDへのフォワードパスのための経路情報を記録 する。さらにノードSへのリバースパスの情報から、ノード2にRREPメッセージが転送 される。このときノード4はRREPメッセージの送信時に、ノード1、2、3はRREPメッ セージの受信時にリバースパスのステータスを「有効な状態」に更新する。また、フォワ ードパスに対する経路情報は「有効な状態」で作成されていく。これらの手順によりノー ドSからノードDまでの経路が確立される（図5.4(c)）。このような方法により、すべての ノードにRREQメッセージの再ブロードキャストを行わせる本来のAODVに比べて、効率 的な経路の確立が可能になると考えられる。

(a)1ホップ目

(b)4ホップ目

S

3

(c)RREP送信

再ブロードキャ ストを行うノード

4 5

D 1

2 S

D 1

S

3 4

D 1

2

RREQ

RREP

1'

1' 4'

図5.4: 起動直後のノードの2回目のRREQメッセージの配信と

RREPメッセージの転送