ノードが移動しない場合の性能評価

5.5.1.1 シミュレーション条件

筆者らの提案する高密度アドホックネットワーク用の AODV プロトコルの評価を行う ために、ノードが高密度に分布している状況を想定し性能評価を行った。シミュレータに

ns2 [42]を用いた。まずシミュレーションの実行中にノードが移動しない場合の性能評価を

行う。ノードの分布としては、1000 メートル×1000メートルの領域に、250 ノード、500 ノード、750ノード、1000ノードがランダムに配置された特定の状況を想定した。無線の 伝 播 範 囲 は 半 径 100 メ ー ト ル 、 伝 送 速 度 は 11Mbps と し 、 メ デ ィ ア ア ク セ ス 方 式 は

IEEE802.11に準拠することとした。

また、バウンダリノードが 2 つ以上検出された場合に、バウンダリノードを指定した RREQ メッセージを送信することとした。さらに、経路が確立された後は、500 バイトの パケットを1秒間に10回転送する40Kbpsの固定速度通信を行わせた。

5.5.1.2 特定のノードペアによる通信の性能評価

ネットワーク内のノード総数を 1000 個とし、20個のノードペアをランダムに選択し、

それらの間で通信を行わせることとした。測定時間を30秒間とし、シミュレーション開始 から 10 秒以内にノードペアがランダムに通信を開始するという形でシミュレーションを 行った。このとき送信された経路制御メッセージの総数と、受信されたデータパケットの 総数を、図5.7と図5.8にそれぞれ示す。図5.7より提案方式では従来のAODVに比べHello メッセージとRREQメッセージの数がとも減少していることがわかる。シミュレーション 開始後約3秒から次第に従来のAODVと比べて、送信されたRREQメッセージの総数の増 加の割合が減少しており、最終的には従来のAODVで45756個、提案方式で11762個と4 分の1程度まで減少している。一方Helloメッセージにおいては、従来のAODVではシミ ュレーション開始からほぼ全てのノードが送信しているため30秒間で約30000個のHello メッセージが確認されている。これに対し、提案方式では約4000個のHelloメッセージが 送信されているのみである。

また、図 5.8 に示したすべての宛先ノードで受信されたデータパケットの総数を示すグ ラフから以下の事柄がわかる。受信された最終的なデータパケット数は、従来のAODVで 4647個、提案方式では4883個となった。また、ログファイルより5120個のデータパケッ トが 30秒間で送信されたことがわかっている。提案方式は 95％のデータパケットが到達 できているのに対して、従来の AODV ではデータの到達率が 90％しかないという結果で あった。このように、従来のAODVを高密度なアドホックネットワークで使用すると、制 御メッセージの増加によりパケットロスが発生するのに対し、提案方法ではその問題を解 決しているということがわかる。

0 10000 20000 30000 40000 50000

0 5 10 15 20 25 30

時間 [sec]

制御メ ッセージ 数

Hello (original) Hello (proposed) RREQ (original) RREQ (proposed)

図5.7: ネットワーク内で送信された制御メッセージの総数の時間的変化、

ノード数：1000個、通信ノードペア数：20、移動なし

0 1000 2000 3000 4000 5000 6000

0 5 10 15 20 25 30

時間 [sec]

受信データパケッ ト 数 original

proposed 送信パケット

図5.8: 宛先ノードで受信されたデータパケットの総数の時間的変化、

5.5.1.3 RREQ メッセージに関する性能評価

ここで、提案方式の処理手順を詳細に評価するために、特にRREQメッセージに着目し て評価を行った。

ネットワーク内のノード数を250個、500個、1000個の場合でそれぞれ実験を行った。

図 5.9はノード数が500 個の場合の配置例である。ネットワーク内のノードから複数のノ ードペアを固定的に選択し、それらの間で通信を行わせることとした。ノードペア数は最 大 6とし、発信元ノードと宛先ノードのペアは、250ノード、500 ノード、1000 ノードの いずれにおいても、領域中の座標表示で、(100、100)と(900、900)、(100、500)と(900、100)、 (250、750)と(500、500)、(900、500)と(100、250)、(500、100)と(500、900)、(500、500)と (900、750)を用いることとした。

まず、バウンダリノードを選択した場合、RREQ メッセージを再ブロードキャストする ノードがどの程度減少するかについて、評価を行った。上記の発信元のノードに対して、

それぞれのノード数に対して、隣接ノード数とバウンダリノード数を計算したところ、表 2 に示すような結果となった。この結果から分かるように、隣接ノード数に比べると、必要 なバウンダリノードの数は 1/2 から 1/6 程度に減少している。このため、バウンダリノー ドのみにRREQメッセージを転送させることにより、RREQのフラッディングのオーバヘ ッドが減少することが期待される。

図5.9: ノード配置例

次に、ネットワーク全体にわたって転送されたRREQメッセージの総量を求めることに より、RREQメッセージ転送のオーバヘッドを評価した。まず、通信ペアを１として、RREQ メッセージの転送総量の変化を詳細に調べることにした。ノード総数を500とし、発信元 ノードを(100、100)、宛先ノードを(900、900)として、シミュレーション開始から2秒後に データを転送しようとした場合の、転送されたRREQメッセージの累積数を測定した。こ こで、累積数は、あるノードが再ブロードキャストするごとに1ずつ増加するとする。横 軸を時間、縦軸をその時間までにネットワーク全体で送信されたRREQメッセージの累積 数としたグラフを図5.10に示す。

2.0秒後に発信元ノードから送信されるRREQメッセージはTTL=3で送信される。その 後2.2、2.5、3.0秒に、拡大リングサーチにより、それぞれ、TTL=5、7、30でRREQメッ セージが送信されている。最終的に宛先ノードを発見するまでに送信されるRREQメッセ ージ数は提案方式の方が少なくなっているのがわかる。2.0秒、2.2秒に送信されたRREQ メッセージでは、発信元ノードがバウンダリノードを決定していないため、AODVと同数 のRREQメッセージが送信されている。一方、2.5秒、3.0秒に送信されたRREQメッセー ジについては、提案方式の方が少なくなっている。これは、それまで受信したRREQメッ セージにより、各ノードがバウンダリノードを決定し、バウンダリノードのみがRREQメ ッセージのフラッディングを行ったためであると考えられる。

ノード総数を500のまま、通信ペア数を6として、シミュレーション開始から2、4、6、 8、10、12秒後に、それぞれ1つずつのペアが通信を開始するという形で、転送されたRREQ メッセージの総数を計測した。その結果を図5.11に示す。横軸は時間、縦軸はその時間ま でに送信されたRREQメッセージの総数である。この結果の2秒から4秒の間は、図5.10 に示したものと同一の結果である。

この図からわかるように、最初の通信ペアが送信を開始した2秒後の後半から、次第に 表 2: バウンダリノードの選択結果

全ノード数

隣接 ノード数

バウンダリ ノード位置 ノード数

[100, 100]

[100, 500]

[250, 750]

[900, 500]

[500, 100]

[500, 500]

250

9 2

8 4

13 5

8 4

13 4

8 4

隣接 ノード数

バウンダリ ノード数 500

17 3

17 4

19 6

12 4

20 7

17 5

隣接 ノード数

バウンダリ ノード数 1000

30 7

32 7

34 8

24 5

38 6

37 6

本来のAODVと比べて、送信されたRREQメッセージの総数の増加の割合が減少しており、

最終的に6つのペアが送信を開始した12秒以降では、RREQのメッセージ総数が1/2以下 に減少している。

ノードの密度を変えるために、1000メートル×1000メートルの領域のノード総数を250 および1000とした場合の、6ノードペアによる通信におけるRREQメッセージの総数を計 測した。その結果をそれぞれ図5.12と図5.13に示す。

ノード総数が250の場合は、ノードの密度が小さくなり、従って表 2の隣接ノード数に 対するバウンダリノード数の割合もそれほど小さくない。このため、本来のAODVに対す る RREQメッセージの総数の減少率は、500ノードの場合に比べると小さい。逆に、ノー ド総数が1000の場合は、ノードの密度が大きく隣接ノード数が増大しており、バウンダリ ノードのみを用いたRREQメッセージの転送の効果が大きくなっている。最終的には本来 のAODVに比べて1/4近くのメッセージで経路が確立されていることになる。いずれにし ろ本方式は、ノードの密度が変わったときでも、本来のAODVに比べてRREQメッセージ のフラッディングを効率的に行っているといえる。

0 100 200 300 400 500 600 700 800

0 1 2 3 4

時間[sec]

# RREQs

提案手法 AODV

図5.10: ネットワーク内で送信されたRREQメッセージの総数の時間的変化、

ノード数：500個、通信ノードペア数：1個、移動なし

0 1000 2000 3000 4000 5000 6000 7000

0 2 4 6 8 10 12 14

時間[sec]

# RREQs

提案方式 AODV

図5.11: ネットワーク内で送信されたRREQメッセージの総数の時間的変化、

0 500 1000 1500 2000 2500 3000 3500 4000

0 2 4 6 8 10 12 14

時間[sec]

# RREQs

提案方式 AODV

図5.12: ネットワーク内で送信されたRREQメッセージの総数の時間的変化、

ノード数：250個、通信ノードペア数：6個、移動なし

0 2000 4000 6000 8000 10000 12000 14000 16000 18000

0 2 4 6 8 10 12 14

時間[sec]

# RREQs

提案方式 AODV

図5.13: ネットワーク内で送信されたRREQメッセージの総数の時間的変化、

5.5.1.5 ノードが移動しない場合に、通信ノードペアを変化させたときの性能評 価

次にノード総数を1000としたときに、通信ノードペア数を10個、20個、30個、40個 とし、それぞれのペア数で異なるノード配置を10種類ずつランダムに選び、シミュレーシ ョンを行った[43]。また、従来の AODV と提案方式では同じノード配置で 10 回シミュレ ーションを行った。その結果の平均を図5.14から図5.17に示す。図5.14から図5.17では、

横軸が通信ノードペア数を示し、縦軸がそれぞれ30秒間で測定された送信制御メッセージ 総数、受信データパケット総数、発信元ノードから宛先ノードまでのホップカウント、経 路確立時間を示している。これらの値は10種類のノード配置に対する結果の平均をとって いる。ここで、ホップカウントと経路確立時間は通信ノードペアが最初に確立した経路に 関するもののみを測定し、経路切断後に再確立した経路や未確立の経路に関しては測定し ていない。

図5.14よりネットワーク全体で送信されたRREQメッセージ数とHelloメッセージ数が 提案方式の方が従来のAODVに比べて減少していることがわかる。特にRREQメッセージ 数においては、通信ノードペア数が10個の時は従来のAODVの3分の1程度だが、40個 になるとその割合は約 5分の1になっていることがわかる。一方Helloメッセージにおい ては、通信ノードペア数が増えるとその割合は減少している。これは従来のAODVでは通 信ノードペア数に関係なくほぼ全てのノードがHelloメッセージを送信しているのに対し、

提案方式ではデータパケットを送信しているノードのみが Hello メッセージを送信するた め、その数は通信ノード数に比例しているためと考えられる。

図 5.15 に示した全ての宛先ノードで受信されたデータパケットの総数の結果において も、通信ノードペア数が増えることによって経路制御メッセージが増加し、それによりパ ケットロスが増加していることがわかると考えられる。パケットロスの割合は従来の AODV、提案方式でそれぞれ通信ノードペア数が30個のときで13%、7%程度、40個のと きで25%、18%となっており、提案方式の方が少なくなっている。

上述のように、図5.16はデータの送信ノードから宛先ノードまでのホップカウントを示 している。従来のAODVでは提案方式に比べてホップカウントが大きいことがわかる。こ れは従来のAODVではブロードキャストされたRREQメッセージは受信した全てのノード が再ブロードキャストするため、送信ノードのすぐ隣接にいるノードも再ブロードキャス トを行う。そのため、1 ホップの距離が短くなる可能性が考えられる。一方、提案方式を 用いると、RREQメッセージの送信ノードの遠くにいるノードのみがその再ブロードキャ ストを行うため、1 ホップの距離が長くなり、ホップカウントが大きくなったと考えられ