アドホックネットワークルーティングにおけるグレーゾーン問題の検討

全文

(1)2005−EVA−12（1） 2005／3／23. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report. アドホックネットワークルーティングにおけるグレーゾーン問題の検討溝中. 口西. 和恒. 寛Ý 北須賀 ÝÝ ÝÝÝ 夫福田. 輝明ÝÝ 晃ÝÝ. 無線 . ネットワークではパケット到着率が急激に低下するグレーゾーンが存在する．グレーゾーンはマルチホップでネットワークを構成するアドホックネットワークに，より大きな悪影響を与える．アドホックネットワークルーティングで得られた経路にグレーゾーンが含まれると，

(2) による通信がほとんどできないといった問題が起こる．本研究では実環境でのグレーゾーンの影響を測定した．その結果を元にアドホックネットワークでのグレーゾーン問題を，経路制御パケットのパケットサイズと伝送速度を変化させることで軽減することを提案する．.

(3)

(4)

(5) Ý. ÝÝ ÝÝÝ. ÝÝ. ÝÝ. .

(6) ! "

(7) # $ # % & ! " ' ( % (! ! " (!( #

(8) ! )$ $( $ # ! " ( $ * ( # )$ $$ ! " % # (! ( & # ! " . め，各無線通信機器はルーターとしての役割も担わな. はじめに. ければならない．. 現在，情報通信技術の発達により大容量のデータを. アドホックネットワークでは主に無線通信でネット. 素早く送信できるようになり，通信媒体も有線から無. ワークを形成する．無線ネットワークではノード間の. 線へと変化している．しかし，現在の無線通信技術は. 距離が近い場合には通常通りの通信ができるが，ノー. 携帯電話の基地局や無線のアクセスポイントな. ド間の距離が離れるにつれてパケット到着率が下がり，. ど，既存のインフラストラクチャがないと様々なサー. 最後には全く通信できなくなる．このパケット到着率. ビスを受けることができない．そこで，これらのイン. が下がる範囲を本研究ではグレーゾーンと定義する．. フラがない場所でも無線携帯機器で動的にネットワー. このグレーゾーンでは，既存のアドホックネットワー. クを形成する，アドホックネットワーク½µ が研究され. クのルーティングプロトコルはうまく対応できずに，. ている．各無線通信機器の通信範囲は限られているの. 通信に大きな悪影響を与える．そのため，アプリケー. で，直接通信できない端末には間にいる他の端末にパ. ションは想定された動作をしない場合がある．. ケットを中継してもらうことにより通信する．そのた. 本研究ではこのグレーゾーンの実環境での範囲と影響を計測し，その対策について検討する．そして，グ. Ý 九州大学大学院システム情報科学府.

(9)

(10)

(11) . ÝÝ 九州大学大学院システム情報科学研究院.

(12)

(13)

(14) ÝÝÝ 九州大学システム研究センター . レーゾーンを軽減するための手法を提案する．. 章では関連研究を述べ，章でグレーゾーンとその問題について述べる．章で実験結果を述べ，章でグレーゾーンの軽減手法を提案し，章でまとめる．. −1−.

(15) . 関連研究ほぼ100%通信可能なエリア. 本節ではグレーゾーン問題に関する先行研究として，参考文献. ¾µ. の概要を述べる．この文献では通信グ. レーゾーン

(16)

(17)

(18) として，本. グレーゾーン. 研究のグレーゾーンと同じ問題についての原因，解決方法を述べている．無線リンクは無線 . A. B. C. D. ¿µ. 通信不可能なエリア. で形成されることを前提としている．アドホックネットワークルーティングプロトコルの . では，定. 期的に !" メッセージをブロードキャストする. 図. グレーゾーン. ことで，隣接ノードに存在を通知する．しかし，この. !" メッセージを受信できる範囲には通信グレーゾーンが存在する．そこでは，!" メッセージは. 部分がグレーゾーンである．ノードのパケット送. 受信できるがデータパケットを交換することはできな. ゾーン問題を解決するためにつの手法を提案，評価. ほぼ％の範囲，外側の円はパケット到着率がほぼ％になる地点を表している．この内側の円と外側の円の間の範囲がグレーゾーンである．ノード ) は内側の円の範囲におり，ノードは外側の円の外にいる．このとき，ノードはノード ) と正常に通信できる．逆に，ノードとは全く通信することができ. している．順につの手法を述べる．つ目の手法は. ず，ノードＤの存在を知ることもできない．. い．そのため，アドホックネットワークのルーティングプロトコルが提供する経路とデータ通信できる経路とは一致しない．参考文献¾µ では . において，この通信グレー. 信可能範囲の円のうち，内側の円はパケット到着率が. ブロードキャストされる !" メッセージに隣接情. 一方，ノードは内側の円と外側の円の間，つまり. 報を付加する方法である．これにより，双方向のリン. グレーゾーンにいる．このため，ノードが送信し. クを判別しそのリンクのみを使用する．つ目の手法. たパケットは全てノードに届くとは限らない．パ. は !" メッセージを連続して複数回受信したリン. ケット到着率が％∼ ％の間なので，ノードＡが. クのみを使用する手法である．この手法は. つ目の手. ノードＣにパケットを送信してもパケットが届く場合. 法と違い，!" メッセージに情報を付加する必要. と届かない場合がある．また，ノードＣが周囲にいる. はない．つ目の手法は #$ #%&

(19)

(20) ' $

(21) . かどうかも，正確に判断できない．このグレーゾーン. を用いて，#$ の小さいリンクを排除する #$ が. は通信に様々な悪影響を与える．例えば，通信速度の. 小さいならば，そのリンクがグレーゾーンである確率. 劣化などである．さらに，このグレーゾーンの境界は. が上がるからである．. 刻々と変化する．例えば，無線では周囲の環境. 論文中の実験により，これらの手法の中ではつ目の #$ を用いる手法が一番性能がよい．. により，通信を行うことができる範囲が動的に変化するからである．そのため，図. のノード ) やノード. もグレーゾーンに入る可能性がある．. グレーゾーン問題. アドホックネットワークへの影響. グレーゾーン. このグレーゾーンは特にアドホックネットワークで. アドホックネットワークは主に無線通信でネットワークを構成する．本研究では無線 (""" . . より大きな影響を与える．シングルホップの無線ネットワークでは，通信性能劣化などの悪影響は基本的に. でアドホックネットワークを形成した場合を考える．. グレーゾーンにいるノードのみに影響する．一方，ア. 無線では送信したパケットが届いたり届かなかっ. ドホックネットワークではマルチホップで通信を行う. たりする範囲がある．無線通信ではノード間の距離が. ため，グレーゾーンが他のノードにも深い影響を与え. 近い場合は通信できるが，距離が離れていくにした. ることがある．グレーゾーンのリンクが経路上にある. がって通信性能が劣化し，最後には全く通信できなく. 場合，そのリンクを使用して通信を行っている全ノー. なる．この無線パケットのパケット到着率が急激に落. ドに影響を与えるからである．. ちる範囲を，本研究ではグレーゾーンと定義する．図. を用いてグレーゾーンを説明する．図. また，ルーティングプロトコルにも悪影響を与える．. はノー. ドのパケット送信可能範囲を示し，ドーナツ型の. アドホックネットワークのルーティングではブロードキャストで経路を発見，維持することが多い．しかし，. −2−.

(22) グレーゾーンがあるため経路制御によって得られた経. イトのデータを 2+ でミリごとに送信する．こ. 路が実際の通信に使用できるとは断言できない．もし，. れを. パケット到着率が％のリンクの場合，ブロードキャ. を計測する．. ストされた経路制御パケットは回に. になる．しかし，そのようなリンクでは期待されるよ. * +，2+ どちらの実験中もノート + で無線のパケットキャプチャを行う．また，ザウルス. うな通信は行うことができず，通信品質は著しく低下. で受信パケット毎の受信シグナル強度を記録する．. 回は届くこと. 分間双方向で行い，パケット到着率とジッター. 度でも届けばいいわけではない．特に * + では送信. 実験結果スループット. パケットに対する , が必要なのでより通信品質の. 図は距離と * + スループットの関係を示すグ. 低下が激しい．さらに経路制御パケットの方がデータ. ラフである．横軸は距離，縦軸はスループット. パケットよりも送信可能範囲が広いと考える．それはパケットサイズと，無線の伝送速度によるもの. 31' である．グラフの

(23) ， 31'，31' はそれぞれ伝送速度を自動切替， 31'，31'. である．このつについては項で述べる．. にした場合である．自動切替の場合，伝送速度は無線. する．データパケットは経路制御パケットのように一. 前章まででグレーゾーン問題のアドホックネット. カード内のアルゴリズムに従って 31' から 31' まで自動的に変更される．伝送速度を

(24) にした場合，では約 31' のスループットが出ているが，から徐々に下がりはじめ，でほぼ 31' になる．一方，伝送速度を 31'，31' に固定すると. ワークに与える影響について述べた．本章ではこのグ. 通信できる距離がかなり短くなっていることがわか. このように，アドホックネットワークのルーティングプロトコルで使用されるルート探索で得られた経路で実際の通信ができるとは限らない．. 実環境でのグレーゾーンの調査. る．また，0 ，で

(25) よりも 31' の方. レーゾーンが与える影響を，実環境で調査する．. 実験環境. がスループットが高いのは，無線で伝送速度を. 本実験では携帯端末にザウルス #-) を使用す. 変更するアルゴリズム $5

(26) $ 5&&/ と. る．# は . カーネル - /0-1. である．それに無線 (""" . カードを挿して通信を行う．実験中ザウルスは三脚に高さで固. * + の組み合わせによる影響であると考える．この実験により，伝送速度を 31' や 31' に固定した場合よりも，伝送速度を

(27) で変更した. 定する．. 場合の方が遠くまで通信をすることができることが確. 実験の目的は実環境でのグレーゾーンの範囲を測定することと，グレーゾーンでのパケット到着率などの. 認できた．しかし，低速通信の範囲も広がっていることが分かる．. 変化を測定することである．そのために台の携帯端. パケット到着率. 末ザウルスを用意し，この台の間で通信を行い，パ. 図は距離と 2+ パケット到着率を表したグラフである．横軸は距離，縦軸はパケット到着率％. ケット到着率などの変化を測定する．次に各実験の詳細を述べる．行った実験は，* + パケットの送信と 2+ パケットの送信である．それぞれ，伝送速度を

(28) ，. 31'，31' は. 図と同様にしたものである．. 31' に固定，31' に. 固定した場合の通りで計測を行う．. * + スループットと違い，伝送速度を

(29) にした場合が常に最も高いパケット到着率を出している．. * + パケットの送信では * + スループットを測定する．送信側の携帯端末ザウルスから受信側のザウルスに. を表している．図中の

(30) ，. 分間パケットを送信し，その間の平均スルー. 次に 31'，そして. 31' が一番パケット到着. 率が低い結果となった．図と同様，伝送速度を固定すると，通信範囲は狭くなる．また，図と図を比較すると，* + スループッ. プットを算出する．. 2+ でのパケット送信では，(+ 電話を通信モデルとする．(+ 電話ではコーデックとして 04 を使用した場合，ミリ秒間にバイトの音声データを圧縮し，それをミリ秒ごとにパケットバイトを送信する．また，$*+ ヘッダがパケットあたりバイト付加されている．そのため本研究では，バ. トと 2+ パケット到着率の距離による通信劣化の速度が明らかに違う．2+ よりも * + の方がより近距離で性能が劣化する．この理由は以下のように考えられる．. −3−. ¯ * + のフロー制御 3 層でのエラーが増加しパケット損失率が上.

(31) 4.5. 100 TCPAuto TCP11Mbps TCP5.5Mbps. 3.5. TCPAuto UDPAuto 80 パケット到着率(%). スループット(Mbps). 4. 3 2.5 2 1.5 1. 60. 40. 20. 0.5 0. 0 40. 60. 80. 図. . 100. 120. 140. 40. 距離(m). . 80. 100. 120. 距離(m). 図. スループット. 100. . "# 層パケット到着率 $. と. !. の比較. 140. %. 100 TCPAuto TCP11Mbps TCP5.5Mbps. 80 パケット到着率(%). 80 パケット到着率(%). 60. 60. 40. 20. 60. 40. 20. UDPAuto UDP11Mbps UDP5.5Mbps. 0. 0 40. 60. 図. 80. . !. 100. 120. 140. 40. 距離(m). 60. 80. 100. 120. 140. 距離(m). 図. パケット到着率. . "# 層パケット到着率 $伝送速度による違い%. がるにつれて，* + は自動的にスループットを. 図は * + 通信と 2+ 通信を比較したグラフで. 下げていく．本来はネットワークを公平に使用す. ある．同じ距離では常に * + パケットの方が 2+. るための機能である．. パケットよりもパケット到着率が低い結果となった．. ¯ パケットサイズ 3 層での * + パケットはバイト，2+ パケットは 4 バイトである．無線では，同. は * + パケットはバイト，2+ パケットは 4. じ伝送速度でパケットを送信してもパケットサ. バイトである．無線では伝送速度，距離によっ. イズが大きいほうがエラーになる確率が高くなる. て誤り率が異なる．ビットあたりの誤り率が等しい場. 項．そのため，* + パケットの方が 2+ パケットよりも 3 層でのパケット到着率が低. 合，パケットサイズが大きい方がパケットあたりのエ. くなる．. 方が 2+ パケットよりもパケット到着率が低いと考. .

(32) 層パケット到着率. この理由は両者のパケットサイズの違いによるものと思われる．今回の実験の 3 層でのパケットサイズ. ラー確率が大きくなる．そのため，* + パケットのえる．仮に，2+ で今回の * + パケットと同じ大. 本項では 3 層でのパケット到着率について述べる．図，図は 3 層のパケット到着率のグラフ. きさのパケットを送信した場合，パケット到着率はほとんど同じになると推測する．. である．横軸，縦軸は図と同様である．3 層の. 図は * + の伝送速度による 3 層でのパ. パケット到着率は次のように定義する．3 層で送. ケット到着率の変化を示すグラフである．伝送速度. 31'，31' に固定した場合の方が到着率が. 信したパケットが届いた割合であり，パケットの再送. を. は考慮しない．つまり，度目で届かず再送によって. 短い距離で急激に落ちていく．これは伝送方式の違い. 届いた場合，3 層でのパケット到着率は％と. が理由である．無線 (""" . なる．. を. −4−. で伝送速度. 31' にした場合，高速に通信できる反面，距離.

(33) . 本章では，グレーゾーンの定義を，アドホックネッ. 0 ,1' になる．の場合は，計測不可能であった．一方，通常のルーティングパケットはで約 0 ％の到着率である．そして，の地点で約％である．仮に * + で通信できる範囲を，オリジナルルーティングパケット相当 4 )7

(34) のパケット到着率がで％になると仮定すると，グレーゾーンは ∼ の範囲となる．この範囲. トワークのルーティングパケットが届くが，* + 通. では通常のルーティングパケットが届くことがあり，. 信が全く行えない範囲と改めて定義する．. リンクが発見される場合があるが，* + での通信は. が離れるとすぐに誤り率が上昇し，パケットのエラー率が上がる．. グレーゾーン軽減手法の提案本章ではアドホックネットワークでのグレーゾーンの影響を軽減するための手法を提案する．. グレーゾーンの原因. 全くできない．. グレーゾーンの軽減手法. 前章よりパケットサイズと伝送速度によるパケット. 差ができ，グレーゾーン問題が起こる．つまり，グレー. 節をふまえて，次の通りの手法を提案する．. 伝送速度を 31'，31' に変更. パケットサイズと，伝送速度を変更. ゾーン問題を軽減するにはルーティングプロトコルが. 以降で提案手法の有効性を議論する際に用いるパケッ. 到着率に差があることが確認できた．これによりルーティングパケットとデータパケットの送信可能距離に. 提供する経路と，実際の通信可能な経路が一致すれば. ト到着率は章の実験で与えられた 3 層パケット. よい．そのためには，ルーティングパケットとデータ. 到着率を利用する．ルーティングパケットサイズが 4. パケットの送信可能範囲の差をなくす，もしくは減少. バイトの場合は 2+ 実験の結果を利用し，バ. させる必要がある．送信可能範囲に差ができる原因で. イトの場合は * + 実験の結果を利用する．. 伝送速度を変更. あるパケットサイズと伝送方式を，実際の通信で使用. つ目の手法は伝送速度を変更する手法である．通常. する場合に近づけることでグレーゾーンを軽減する．無線は (""" . を想定するなお，今. のルーティングパケットは基本伝送速度である 31'. 回アドホックネットワークのルーティングパケットは. でブロードキャストされる．本手法ではルーティング. の $$"6 パケットなどのブロードキャストされるパケットをモデルとする．の $$"6 パケットの場合，3 層でのパケットサイズはバイトである．本実験で計測した 2+ パケットがこのモデルに非常に近く，3 層でのパケットサイズ 4 バイト，伝送速度

(35) の場合がこのモデルに該当するものとする．3 層でのパケット到着率を使用する. パケットを. 31' または 31' でブロードキャ. ストすることにする．図に，ルーティングパケットの伝送速度を変更した場合のグラフを示す．改良ルーティングパケット相. 伝送速度の 31' 以外でも通信するが，グレーゾー. 31'，改良ルーティングパケット相当. 4 )731' は，それぞれルーティングパケットの伝送速度を 31'，31' にした場合である．通常のグレーゾーンは節で仮定したように ∼ とする．ルーティングパケットの伝送速度を 31' に固定した場合，から徐々にパケット到着率が下がり始め，でほぼ％になる．つまり，ルーティングパケットが届く範囲全てで，実際の * + 通信ができ. ンが関係する遠距離ではほとんど 31' で通信して. るということである．よって，グレーゾーンはないと. いるのでそのまま採用する．また，データ通信は * +. 言える．. 理由は，ルーティングパケットがブロードキャストされることが多いからである．無線ではユニキャストされた場合と違い，ブロードキャストされた場合はパケットの再送がない．よって 3 層でのパケット到着率を使用する．伝送速度が

(36) の場合，基本. 当 4 )7. 通信で伝送速度は

(37) の場合をモデルとする．. ルーティングパケットの伝送速度を 31' に固. 図に通常のルーティングパケットと * + の性能. 定した場合，でパケット到着率がほぼ％にな. のグラフを示す．横軸は距離，縦軸左は * + ス. る．よって，グレーゾーンは. ループット 31'，縦軸右はルーティングパケットの. なりグレーゾーンを軽減できる．. ∼ の範囲と. パケットサイズと伝送速度を変更. 到着率％である．オリジナルルーティングパケット相当 4 )7

(38) のグラフが通常のアドホックネッ. つ目の手法はルーティングパケットのパケットサ. トワークのルーティングパケットの到着率にあたる．. イズ，伝送速度を共に変更する手法である．ルーティ. グラフを見ると * + スループットは. で約. ングパケットのパケットサイズをバイトにし，. −5−.

(39) 4.5. 100. 4.5. 100. 3 60. 2.5 2. 40. 1.5 1. 20. 0.5. 80. 3.5 3. 60. 2.5 2. 40. 1.5 1. パケット到着率(%). 80. 3.5. スループット(Mbps). 4 パケット到着率(%). スループット(Mbps). 4. 20. 0.5. 0 40. 60. 80. 100. 120. 0 140. 0 40. 60. 80. 距離(m). 伝送速度を. . 120. 0 140. 距離(m). TCPスループット(Auto) オリジナルルーティングパケット相当(96Byte,Auto) 改良ルーティングパケット相当(96Byte,11Mbps) 改良ルーティングパケット相当(96Byte,5.5Mbps). 図. 100. TCPスループット(Auto) オリジナルルーティングパケット相当(96Byte,Auto) 改良ルーティングパケット相当(1536Byte,11Mbps) 改良ルーティングパケット相当(1536Byte,5.5Mbps). 図. 伝送速度を変更. 31'，31' のいずれかでブロード. キャストする．. . パケットサイズ，伝送速度を共に変更. ただし，伝送速度やパケットサイズを変更するルーティングパケットの選定には注意が必要である．他ノー. 図 0 にグラフを示す．横軸，縦軸は図と同じである．改良ルーティングパケット相当 )7. ドとのリンクを発見，維持するルーティングパケット. 31'，改良ルーティングパケット相当 )731' はルーティングパケットのパケットサイズをバイトにしてそれぞれ伝送速度を 31'，31' に. には提案手法を使うことが非常に効果的といえる．一. 固定した場合である．両者ともにパケット到着率が. トワーク全体の性能向上になり，届かなかった場合は. ％の地点が計測できなかったため， 31' の改良ルーティングパケットは，31' の改良ルーティングパケットはでパケット到着率が％に. 性能劣化となるからである．. 方，ノードやルートの切断を周囲に通知するルーティングパケットには提案手法を使用するべきではない．これらのパケットは多くのノードへ届いたほうがネッ. 今後の課題として以下のものが考えられる．. ¯ 実環境でアドホックネットワークを構築し，本手. なると仮定する．. 法の性能評価を行う．. 通常のルーティングパケットの場合，グレーゾーン. ¯ シミュレータに実環境のグレーゾーンを計測でき. ∼ の範囲である．本項で提案している種類のルーティングパケットは両方とも以前にパケット到着率が％になるため，グレーゾーン問. るような改良を施し，シミュレーションによる性. は. 能評価を行う．. ¯ (""" . 題は完全に回避できたといえる．しかし，ここで通信可能範囲が狭くなるという問題が発生する．例えば，での * + スループットは約 431' であるが，. や. を用いて提案手法の評価，. 更なる改良を行う．. 31' の改良ルーティング. パケットはでは全く届かない．そのためデータ通信できるリンクが利用できない．. 謝辞本研究の一部は，総務省戦略的情報通信研究開発推進制度，および文部科学省科研費萌芽研究. ，若手研究 ) 0 による助成を受けている．. 参考. 終わりに本研究では無線ネットワークにおけるグレーゾーン，およびアドホックネットワークのグレーゾーン問題に取り組んだ．グレーゾーン問題とは，経路制御によって得られた経路で実際のデータ通信ができない可能性があることである．このグレーゾーンが通信に与える影響を実環境にて測定した．そして，グレーゾーン問題を軽減，回避する手法として，ルーティングパケットのパケットサイズと伝送速度を変更する手法を提案し，測定結果に基づいて提案手法の有効性を示した．. −6−. 文. 献. " +/' 7 8

(40) 79 ::'

(41) -;'&7 ! :%7 "

(42) :'

(43) 7 : *'<:7 8

(44) 1% =<

(45)

(46)

(47) ' (""" ': : <

(48) =

(49) /'79 3 ;

(50) ;3

(51) 3>7 114?7 #17 #(@(""" #: 7 444 ":7 8+ A ;&'' 3: ''

(52) & 3 : +<'& +!B #1C

(53) '79 444.

(54)