固定ノード環境におけるMANETルーティングプロトコルの評価

全文

(1)「マルチメディア，分散，協調とモバイル(DICOMO2010)シンポジウム」平成22年7月. 固定ノード環境における MANET ルーティングプロトコルの評価遠藤零始†. 白石陽 ††. 高橋修††. 無線 LAN メッシュネットワークやセンサネットワークなど固定されたノード間で MANET のルーティングプロトコルを用いることがある．従来の研究からノードが高速移動時する場合にパケット到達率の低下や遅延時間の増加が発生し通信性能が低下するということは分かっているが，ノードが移動せずに固定されている環境における評価はほとんど行われていない．また，無線 LAN メッシュネットワークの規則的に配置することを前提に研究をしており，配置を条件とした研究は行われていない．筆者らは無線 LAN メッシュネットワークにおいてアクセスポイントが不規則に配置された環境を想定して研究を行い，規則的に配置された環境と比べ通信性能が低下することを認識していた．本稿では，ノードの配置条件を変えた環境のシミュレーション評価を行うことで，ノードが固定された環境で MANET ルーティングプロトコルを適用した際の発生する問題を明確にし，パケット到達率と遅延時間を基準として性能評価を行う．. Evaluation of the MANET Routing Protocol in the Fixed Node Environment REIJI ENDOH† YOH SHIRAISHI†† OSAMU TAKAHASHI†† Routing protocols of MANET are used in fixed nodes such as a wireless LAN mesh networks or a sensor networks. From a conventional study, it is known that communication performance (packet arrival rate and delay) falls at the node moving fast. But it is not evaluate in environment without a node moving. In addition, wireless LAN mesh network has been studied in the regular arranged access poi nts regardless of arrangement. We have studied a wireless LAN mesh network in the random arranged access points. And we show that the regular arrangement is better. In this paper, we have evaluated the performance of Routing protocol of MANET in using fixed nodes. †. 公立はこだて未来大学大学院 Graduate School of Future University Hakodate †† 公立はこだて未来大学 Future University Hakodate. 1. はじめに近年，無線通信技術の発達により通信モジュールの小型化・高性能化が進み，従来はノート PC や PDA といった一部の情報端末にしか搭載できなかった無線 LAN が，携帯電話やゲーム機，そしてセンサネットワークの端末にまで搭載されるようになり，無線 LAN が身近な通信手段として広く普及し始めている．また，既存の通信インフラに依存せずに端末（ノード）が自律分散型のネットワークを形成し通信を行うモバイルアドホックネットワーク（MANET）の研究も活発に行われている．そして，通信インフラとしての無線 LAN と MANET の両方の技術を用いる無線 LAN メッシュネットワーク（以下 WMN）[1][2]がある．従来の無線 LAN では，アクセスポイント（以下，AP）相互間を管理者が存在する有線ネットワークで形成し通信インフラを提供していたため，管理者が必要で有線ネットワークを構築するなどコストが掛かり容易とは言えなかったが，WMN では AP 相互間を MANET で使用される自律分散型ルーティングプロトコルで接続することにより，低コストで容易に通信インフラを提供することが可能となっている． WMN の AP 相互間ネットワークで利用される技術は ZigBee[3]などのセンサネットワークでも利用されており，固定されたノード間に MANET の技術を用いた環境であるといえる．WMN やセンサネットワークでは MANET ルーティングプロトコルとしてリアクティブ型プロトコルである AODV[4]を用いている．リアクティブ型ルーティングプロトコルは，あらかじめ経路構築を行い常時保守している OLSR[5]などのプロアクティブ型ルーティングプロトコルと比較して，データ送信時に経路構築を行うためルーティングオーバーヘッドが少なく，必要時以外は通信を行わないため省電力性に優れているという特徴を持っている． MANET ルーティングプロトコルにおける研究ではノードが高速で移動する環境に対処する方法などの検討が行われており[6]，移動速度が低い方がパケット到達率や遅延時間などの通信性能が良いと言われているが，WMN やセンサネットワークのようなノードは固定され移動しない環境における評価は行われていない． WMN では，隠れ端末に対応する方式の研究や AP 選択方式の研究，災害時への適用方法の検討など[7][8][9]が行われているが，AP を規則的に配置した環境を前提条件としており，不規則に配置された環境を想定している研究事例はない．また，AP の配置に関しては，1 つの密度のみで評価を行っており，密度を変化させて評価を行っている研究事例もない．そこで本稿では，固定ノード環境へ AODV を適用した際に起こりうる問題を明確にするために，複数のノード配置を計算機シミュレーションによって評価を行う．. ― 620 ―.

(2) 3.3 ノードの通信特性. 2. 研究の背景筆者らは，WMN の効率的な構築手法を提案した研究[10]を行った．この研究は，既存研究では AP を規則的に配置した環境で評価していたことに対して，実環境では AP が規則的に配置されることは考えにくいという点に着目したものである．具体的には， AP を不規則に配置した環境を想定し位置情報から規則的な配置のクラスタを形成してクラスタ内に存在する AP の機能制限によって不規則に配置された環境に規則性を持たせることで WMN を効率的に構築する手法の提案を行った．この研究では，ノードの配置がパケット到達率や遅延時間といった通信性能に影響を与えることを想定しシミュレーションを行い，影響を与えることを確認している．しかし，性能評価において，ノード配置が規則的な配置と不規則な配置の 2 種類のみであり，ネットワークサイズやノード密度も 1 種類であったため，十分なシミュレーション評価ができていたとは言えず，影響を与える仕組みを明らかにすることはできなかった．そこで，本稿では，ネットワークサイズやノード設置密度の異なる複数の固定ノード環境を設定し評価を行う．この結果を提案方式へ反映させることで，クラスタリングをより効果的に行うことが可能になると考えている．. ノードは通信インタフェースに無線 LAN を持っており，IEEE 802.11b を用いた通信が可能となっている．OPNET では自由空間減衰のみしかシミュレートできず，無線出力に対して通信半径が大きくなりすぎる問題があったためであり，無線出力を絞ることにより通信半径を 50m 程度として現実世界の無線通信に近い通信性能を持たせる．帯域幅は全ての送信ノードからのデータを 1 つの受信ノードが受信可能であるように設定する．全てのノードはルーティングプロトコルとして AODV を用いてネットワークを形成する．AODV のパラメータを表 1 に示す．. 3. シミュレーション評価環境本章ではシミュレーション環境について述べる． 3.1 シミュレータ. 計算機シミュレータとして OPNET15.0A PL3[11]を用いた．OPNET では大規模環境に対して電波損失も含めて物理層からアプリケーション層までをシミュレートすることができる．ルーティングプロトコルも標準で用意されており，ソースコードを書き換えることで独自のプロトコルを利用することも可能である．本研究では用意されている AODV の設定を RFC の標準設定に準拠させ，ルーティングに関係しない部分でノードの情報を出力するための機能追加を行う． 3.2 物理トポロジネットワークエリアの中心に受信ノードを設置し，ネットワークエリア全体に送信ノードを設置したトポロジを基本とする．本稿ではネットワークエリアの形状を正方形とする．送信ノードの設置数は設置密度に応じて決まっており，送信ノード設置密度をネットワークエリア全体の送信ノード数とサイズから node/10000 ㎡で表す．規則的な配置の場合は図 1 に示すような物理トポロジを形成し，不規則な配置の場合には図 2 に示すような物理トポロジを形成する．それぞれの白抜き四角は受信ノードを示し，黒丸は送信ノードを示している．不規則な配置は，配置により結果に大きな影響が出る可能性があるため，複数の異なる配置の物理トポロジを用意する．. 図 1 規則的な配置（400m×400m）. 図 2 不規則な配置（400m×400m）. 送信ノードは定期的に固定送信レートでデータ通信を行う．各送信ノードは，最初ランダムな秒数（0.0 秒～29.9 秒）の間データ送信しない状態を維持する．その後，表 2 に示したパラメータに従い 5 秒間の送信と， 30 秒間の無送信状態を 5 回繰り返す．ただし無送信状態において他の送信ノードからのデータを転送する処理は行う． 3.4 評価尺度 WMN やセンサネットワークでは，データを短時間に確実に届けることが求められている．そのため，本稿では，パケット到達率と遅延時間を評価の尺度として用いる．パケット到達率は送信ノードが生成したパケット数に対して受信ノードが受信できたパケット数の割合とする．遅延時間は送信ノードがパケットを生成した時刻と受信ノードがそのパケットを受信した時刻の差とする．制御パケット発生数はすべての送信ノードと受信ノードが生成した RREQ パケット・RREP パケット・RERR パケッ. ― 621 ―.

(3) ト・HELLO パケットの総数とする．ホップ数は受信ノードが受信したデータパケットのホップ数であり，1 回の転送を 1 ホップとする．数値をグラフで表した際に，規則的に配置した環境の結果は Grid とし，不規則に配置した環境の結果は 10 パターンの平均値を RandomAve，最小値を RandomMin，最大値を RandomMax とする． 3.5 環境設定表 3 に示した環境を設定しシミュレーションを行う．ネットワークサイズ毎に 2 つの送信ノード密度を基準として 3.2 節に従ったトポロジを形成し，送信ノード密度は 8node/10000 ㎡，16node/10000 ㎡とし，それぞれの送信ノード密度で，規則的な配置の環境が 1 パターン，不規則な配置のパターンが 10 パターンとして，合計 22 パターンの環境でシミュレーションを行う．表 1 AODV パラメータ一覧設定値. パラメータ名. ACTIVE_ROUTE_TIMEOUT. 3 秒. ALLOWED_HELLO_LOSS. 2. HELLO_INTERVAL. 1 秒. LOCAL_ADD_TTL. 2 ホップ. NET_DIAMETER. 35 ホップ. NODE_TRAVERSAL_TIME. 0.04 秒. RERR_RATELIMIT. 10 packet / sec. RREQ_RETRIES. 2. RREQ_RATELIMIT. 10 packet / sec. TIMEOUT_BUFFER. 2. TTL_START. 1. TTL_INCREMENT. 2. TTL_THRESHOLD. 7. 項目. 項目. 1024 bit. 送信レート. 3.2 packet / sec. 宛先. 受信ノード. シミュレーション時間. 300 秒. ネットワークサイズ. 200m×200m, 300m×300m, 400m×400m, 500m×500m, 600m×600m. 送信ノード密度. 8 node/10000 ㎡, 16 node/10000 ㎡. 4. シミュレーション結果本章では，8node/10000 ㎡と 16node/10000 ㎡の送信ノード密度ごとに，ネットワークサイズを変化させた時のパケット到達率，遅延時間，制御パケット数，ホップ数の結果について述べる． 4.1 送信ノード密度が 8node/10000 ㎡の場合図 3 にパケット到達率を示す．ネットワークサイズが大きくなるに従い到達率が減少する．また，不規則に配置した環境における到達率の最高値と最低値の差が増加している．ネットワークサイズが 200m×200m の場合に，最低値が 90％以下となった原因については 5.2 節で述べる．図 4 に遅延時間を示す．ネットワークサイズが大きくなるにつれて遅延時間は増加し，不規則に配置した環境における遅延時間の最高値と最低値の差も増加している．また，規則的な配置をした環境では，不規則に配置した環境と比べ遅延時間が比較的短くなった．図 5 に制御パケット発生数を示す．ネットワークサイズが大きくなるに従い急激に増加し，不規則に配置した環境における発生数の最高値と最低値の差が増加している図 6 に平均ホップ数を示す．ネットワークサイズが大きくなるに従い直線的に増加している．. 表 2 送信ノードの送信パラメータ値. パケットサイズ. 表 3 シミュレータの環境設定値. ― 622 ―.

(4) 図 3 ネットワークサイズに対するパケット到達率（8node/10000 ㎡）. 図 5 ネットワークサイズに対する制御パケット発生数（8node/10000 ㎡）. 図 4 ネットワークサイズに対する遅延時間（8node/10000 ㎡）. 図 6 ネットワークサイズに対する平均ホップ数（8node/10000 ㎡）. ― 623 ―.

(5) 図 7 ネットワークサイズに対するパケット到達率（16node/10000 ㎡）. 図 9 ネットワークサイズに対する制御パケット発生数（16node/10000 ㎡）. 図 8 ネットワークサイズに対する遅延時間（16node/10000 ㎡）. 図 10 ネットワークサイズに対する平均ホップ数（16node/10000 ㎡）. ― 624 ―.

(6) 4.2 送信ノード密度が 16node/10000 ㎡の場合. 図 7 にパケット到達率を示す．ネットワークサイズが大きくなるに従い到達率が大きく減少している．ネットワークサイズが 400m×400m になるまで，不規則に配置した環境における到達率の最高値と最低値の差は増加してゆくが，ネットワークサイズがそれより大きくなると差は減少している．図 8 に遅延時間を示す．ネットワークサイズが大きくなるに従い遅延時間は大きく増加し，不規則に配置した環境における遅延時間の最高値と最低値の差も大きく増加している．特にネットワークサイズが 600m×600m で不規則に配置した環境では遅延時間の最大値が 3 秒を超える結果が出ている．原因については 5.2 節で述べる．図 9 に制御パケット発生数を示す．ネットワークサイズが大きくなるに従い増加している．不規則に配置した環境における発生数の最高値と最低値の差は，ネットワークサイズが 600m×600m の場合を除き大きな差はない．600m×600m では最高値と最低値の差が 2 倍となっておりこの環境だけ大きな差が発生している．図 10 に平均ホップ数を示す．ネットワークサイズが大きくなるに従い直線的に増加している．4.1 節とは異なり，規則的に配置した環境のほうが不規則に配置した環境よりも大きい値となっている．. 到達率と関係していることが分かる．ホップ数と遅延時間の関係は，中継処理に時間がかかることが原因となっており，このことは図 4 と図 5 からも分かる．制御パケット発生数とパケット到達率の関係について，図 11 の制御パケット数の詳細を図 12 制御パケットの内訳に示す．. 5. 考察本章では 4 章で示した評価結果について考察を行う． 5.1 ノード密度と配置に関する一般的な傾向ネットワークサイズが大きくなる，または送信ノード密度が増加すると，送信ノードの配置に関わらずパケット到達率が低下し遅延時間が増加している傾向が分かる．これはノード数が増加すると通信性能が落ちるということを示している． 5.1.1 送信ノード密度が 8node/10000 ㎡の場合送信ノード密度が 8node/10000 ㎡と低い場合にはネットワークサイズが大きくなってもパケット到達率が大きく低下することがなく，遅延時間も 0.3 秒以下に抑えられるなど通信性能が良い結果を示している．送信ノードの配置方法の違いに着目した場合，ネットワークサイズが大きくなったときに規則的に配置した環境よりも不規則に配置した環境の方がパケット到達率・遅延時間ともに良い結果を示すことがある．これは必ずしも規則的な配置の環境が良い通信性能にならないということを示している．例として送信ノード密度が 8node/10000 ㎡でネットワークサイズが 600m×600m の場合に，不規則な配置の環境で最も良い結果であった配置（RG）と悪い結果であった配置（RB）と規則的な配置の環境（G）の 3 つを比較する．それぞれのパケット到達率・遅延時間・制御パケット発生数・ホップ数を図 11 に示す．図 11 から，ホップ数は遅延時間と関係しており，制御パケット発生数はパケット. 図 11 配置による結果の違いの比較. 図 12 制御パケットの内訳. ― 625 ―.

(7) 図 12 から，RG は HELLO パケットが多く RREQ パケットが少ないことが分かる． AODV は経路を構築するときに，経路構築を求める RREQ パケットを送信する．RREQ パケットを受け取ったノードは到達目標ノードが自分でない限り RREQ パケットの再送を行い，到達目標ノードであった場合には RREP パケットを返信する．そのとき RREP パケットが通ってきた経路を通信に用いており，その経路が使われている間は保守管理のために HELLO パケットを送信している．そして，経路を構成する中継ノードへ RREQ パケットが届いた場合には，保守管理している経路を使うようにそのノードが RREP を送信することで，制御パケット発生数を抑える仕組みが備わっている．つまり，HELLO パケットが多いということは長期間経路を管理していたことを表しており，RG では経路を有効に使うことが可能であったためにパケット到達率を高く保つことが可能となった．一方で，RB については RREQ パケットの発生数が多いにもかかわらず RREP パケットが少ないことが分かる．これは AODV には RREQ パケットを送信した時に一定時間返信がない場合に再び RREQ パケットを送信する機能があることが関わっている． RB では，まず RREQ パケットによる軽い輻輳が発生する．そのときに RREQ パケットが届かないノードが発生し RREQ パケットの再送信を行う．しかし軽い輻輳を起こしているネットワークにさらにパケットを送ることになってしまい輻輳が悪化するが，送信ノードは RREQ パケットが届かないことだけを確認してさらに RREQ パケットの再送信を行い，ネットワークの輻輳が悪化し続けてしまう．そのため，パケット到達率を下げてしまう結果となる． G については送信ノード密度と RERR パケットの多さから，ノード間の距離が均等に広くなってしまい無線通信が安定しないために RERR パケットが生成されて経路切断が発生していたことが原因であると考える．経路切断後に再び RREQ パケットの返信として RREP パケットを送信したため多くなったと考えると，無線通信が安定していなかったことは RREP パケットの発生数が多いことと関係づけられる． 5.1.2 送信ノード密度が 16node/10000 ㎡の場合送信ノード密度が 16node/10000 ㎡と高い場合には，ネットワークサイズが大きくなるとパケット到達率が大きく低下してしまい，遅延時間も最長で 3 秒になってしまうなど悪い結果になったと言える．配置方法の違いに着目すると，規則的に配置した環境では，パケット到達率・遅延時間・制御パケット発生数・ホップ数すべてのグラフがほぼ直線的な変化を見せるのに対して，不規則な配置をした環境では最大値と最小値にばらつきが生じ，遅延時間や制御パケット発生数のグラフは途中から大きな変化を見せている．送信ノード密度を高い場合には，送信ノード間の距離が短く無線通信が安定することから規則的に配置した環境が良い結果を出したと言える．また，不規則に配置した環境は，制御パケット発生数が多く遅延時間も大きいことから，ネットワークに輻輳. が発生してしまい通信性能が低下したと考えられる． 5.2 低密度で通信できない環境 4.1 節でネットワークサイズが 200m×200m の場合に，送信ノードを不規則に配置した環境で最低値となった配置の結果が非常に低くとなっていることを例外として扱った．この結果を示した環境のノード配置を図 13 に示す．中央にある白抜き四角は受信ノードを示し，黒い丸はデータを送信できた送信ノード，×印がデータを送信できなかった送信ノードを示している．また，背景の濃淡はノードの密度分布を示している．図 13 からネットワークサイズ 200m×200m で 40000 ㎡に対して送信ノードは合計で 32 ノードあり，送信ノード密度は 8node/10000 ㎡となっているが，×印のノードは通信半径内に受信ノードへ中継することが可能なノードが存在しないためデータの送信ができなかった．そのため，それらの送信ノードのパケット到達率が 0％になってしまい，環境全体のパケット到達率が大きく低下した結果となった．. ― 626 ―. 図 13 低密度で通信できない環境のノード配置.

(8) 5.1 制御パケットが大量に発生した環境. 4.2 節でネットワークサイズが 600m×600m の場合に，送信ノードを不規則に配置した環境で制御パケット発生数の最高値が非常に大きな値となった．この結果を示した環境のノード配置を図 14 で示す．中央にある白抜きの四角は受信ノードを示し，破線で区切られた 100m×100m 内で制御パケット発生数が基準値を超えていた送信ノードを黒い丸，基準値を下回っていた送信ノードを白い丸で示している．また，背景の濃淡はノードの密度分布を示している．基準値は，ネットワークサイズ 600m×600m を 100m×100m に区切ると 36 に分けることができ，全送信ノードが生成した制御パケット数は 20,055,788 パケットであったため， 1 つの 100m×100m のエリアでは平均で約 600,000 パケットとなるので，その値を 1.5 倍した 900,000 パケットを基準値とした．. 図 14 で基準値を超えていた送信ノードのあったエリアのうち，右側では全体の約 5％にあたる 945,263 パケットが発生し，左側では全体の約 8％にあたる 1,528,231 パケット発生していた．表 4 にそれぞれの制御パケットの内訳を示す．. RREQ. 表 4 制御パケットの内訳 RREP RERR HELLO. 合計. 右側. 914,841. 9,005. 19,746. 1,671. 945,263. 左側. 1,482,263. 11,660. 30,289. 4,019. 1,528,231. 制御パケットのほとんどを RREQ パケットとなっており，5.1.1 節の RB と同様に RREQ パケットの再送信による輻輳が起きていたと考えられる．上記の 2 つのエリアは送信ノード密度が高い部分が区切られたため制御パケット数が多く発生したことが分かった．この環境の配置では区切りで分割されているが他にも送信ノード密度が高い部分があり，同様に制御パケットによる輻輳が起きており，結果として全体の制御パケット数が非常に多くなる結果となった． 5.2 まとめ以上のことから，送信ノード密度が高い場合には 5.1 節で考察したように，制御パケットによる輻輳が原因で通信性能が低下してしまうが，送信ノード密度が低い場合には図 13 のように物理的に通信できないノードが存在してしまう可能性が高くなり，ネットワークの構築さえできない状況になってしまうことが分かる．送信ノードが高密度に設置された環境を想定する場合には，ネットワークエリアをなるべく小さくし，ノードの配置を規則的にすることで通信品質の低下を抑えることが可能になる．送信ノードが低密度に設置された環境を想定する場合には，ネットワークサイズが大きくなっても通信性能に大幅な低下は起こらず，通信経路の保守管理が上手く行われる環境を作れば，ノードを規則的に配置することは不要となる．しかし，物理的に通信できないノードが存在する可能性が大きくなることに注意しなければならない．本稿では通信半径を短めに設定してシミュレーションを行ったが，通信半径をより長く設定した場合には，本稿において低密度と判断していたノード密度において高密度で起きた問題が起こることが想定される．. 6. おわりに図 14 制御パケットが大量に発生する環境のノード配置. 本稿では，固定ノード環境に AODV を適用した際に，送信ノードの密度が通信性能に大きく関係しており，制御パケットが大量に生成されることが原因で輻輳が発生し，通信性能が低下することを明らかにした．筆者らが提案した WMN の最適化方法[10]. ― 627 ―.

(9) で用いるクラスタリングでは，有効な AP をクラスタ毎に規制することで MANET への負荷を減らす方針であったが，今回の結果を反映させることで，位置情報のみではなく，制御パケット発生数なども考慮してクラスタリングを行い，MANET に参加する AP を制限することで効率の良い WMN を形成できると考え，今後実装を行いたいと考えている．. 参考文献 [1] Y.Matsumoto, J.Hagiwara, A.Fujiwara, H.Aoki, A.Yamada, S.takeda, K.Yagyu, F.Nuno,: A Prospective Mesh Network based Platform for Universal Mobile Communication Service, 電子情報通信学会総合大会講演論文集, 2004 年_通信(1) , p.732 (2008). [2] 間瀬憲一, 阪田史郎: アドホック・メッシュネットワークユビキタスネットワーク社会の実現に向けて, 初版第 1 刷発行, コロナ社 [3] P.Kinney, "ZigBee Technology: Wireless Control that Simply Works", White Paper dated 2 Oct.2003 [4] AODV(Ad-hoc On-Demand Distance Vector):RFC3561, http://www.ietf.org/rfc/rfc3561.txt [5] OLSR(Optimized Link State Routing):RFC3626, http://www.ietf.org/rfc/rfc3626.txt [6] 鳴海寛之, 高橋修:MANET における Cluster-by-Cluster ルーティングアルゴリズムの提案と実装・評価, 情報処理学会研究報告, Vol2009, No.8, pp1-8（2009）. [7] 柳生健吾, サギャムウォンジャトゥロン: 無線 LAN メッシュネットワークにおける隠れ端末を考慮したマルチホップ通信向け適応変調方式の提案, 電子情報通信学会総合大会講演論文集, 2008 年_通信 2, p.628（2008）. [8] 大薮赳, 福田豊, 尾家祐二:無線 LAN メッシュネットワークにおける AP 選択手法の提案とその評価, 電子情報通信学会技術研究報告, IN2006-161, pp139-144 （2009）. [9] 山崎浩司, 伊藤将志, 渡邊晃:災害発生時に電子メール環境を再構築する方式の提案, 情報処理学会研究報告, Vol.2008, No.21, pp195-200（2008）. [10] 遠藤零始, 白石陽, 高橋修: 実環境を考慮した無線 LAN メッシュネットワーク構築法の提案, 第 17 回マルチメディア通信と分散処理ワークショップ論文集, pp.49-54（2009）. [11] OPNET, http://www.opnet.com. ― 628 ―.

(10)