Comments
Description
Transcript
修士学位論文 マルチホップ無線 LANにおける動的なトラヒック制御
修士学位論文 題目 マルチホップ無線 LAN における動的なトラヒック制御 指導教官 尾家 祐二 教授 報告者 福田淳平 平成 18 年 2 月 14 日 九州工業大学大学院 情報工学研究科 情報システム専攻 平成 17 年度 修士学位論文 マルチホップ無線 LAN における動的なトラヒック制御 福田淳平 内容梗概 近年，携帯型無線端末の技術発展と接続場所に束縛されないインターネットアクセスの需要が高ま り，無線 LAN (LAN，Local Area Network) の普及が進んでいる．この無線 LAN は，無線と有線 ネットワークを接続する基地局 (AP, Access Point) が，無線端末 (STA, Station) のデータを中継す ることで通信行う．現在では，コスト面や地理的な理由から有線ネットワークを敷設できない場所で もインターネットアクセスを可能とするマルチホップ無線 LAN が注目を集めている．マルチホップ 無線 LAN は，これまで有線ネットワークを介して接続していた AP を無線で相互に接続することで， 通信エリアを容易に拡大できる．このため，マルチホップ無線 LAN により既存の有線ネットワーク をバックボーンとした大規模な無線 LAN 基盤の実現が期待される．しかし，従来のマルチホップ無 線 LAN の経路制御では，最短経路上にある単一のゲートウェイまでの経路しか把握できない上に， ゲートウェイを動的に選択することができない．このため，有線バックボーンとのゲートウェイ AP に負荷が集中し，ゲートウェイ AP の無線リンクがネットワーク全体のボトルネック・リンクとな る可能性がある．そこで本研究では，この負荷の集中が TCP スループット特性に及ぼす影響につい て調査する．続いて複数ゲートウェイ環境下で，負荷が集中していないゲートウェイ AP へ経路が 切り替わるようにトラヒックを動的に制御する手法を提案し，シミュレーションによってその有効性 を明らかにする． 主な用語 マルチホップ，無線 LAN (Wireless LAN， Local Area Network)，ゲートウェイ，負荷集中，複数 経路表，TCP，トラヒック制御 目次 1 はじめに 1 2 無線 LAN の概要 3 2.1 無線 LAN の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 プロトコル構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 ネットワークトポロジ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 無線 LAN の使用周波数帯 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5 MAC 層のメディアアクセス制御 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.5.2 CSMA/CA 方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5.3 IFS 間隔による制御 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5.4 バックオフ制御 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5.5 隠れ端末問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5.6 RTC/CTS による解決 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.5.7 PCF アクセス制御方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 DCF アクセス制御 マルチホップ無線 LAN の概要 15 3.1 チャネル環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 マルチホップ無線 LAN の現状と問題点 . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.1 アドホック・ネットワークのルーティングアルゴリズム . . . . . . . . . . . . 17 3.2.2 シングルチャネルを想定した MAC 層の研究 . . . . . . . . . . . . . . . . . . 20 3.2.3 マルチチャネル環境を想定した MAC 層の研究 . . . . . . . . . . . . . . . . 22 3.2.4 マルチホップ無線 LAN の問題点 . . . . . . . . . . . . . . . . . . . . . . . . 23 4 マルチホップ無線 LAN における負荷の集中 26 5 提案手法 36 5.1 低負荷ゲートウェイ選択手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 フロー分割手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 i 6 提案手法の有効性 39 6.1 シミュレーション環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2 結果・考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2.1 パターン 1 の結果と考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2.2 パターン 2 の結果と考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7 まとめ 52 8 謝辞 53 参考文献 54 ii 1 はじめに 近年，接続場所に束縛されないインターネットアクセスへの需要が高まり，無線 LAN (LAN，Local Area Network) の普及が進んでいる．この無線 LAN は，無線と有線ネットワークを接続する基地 局 (AP, Access Point) が，無線端末 (STA, Station) のデータを中継することで通信を行う．この無 線 LAN の普及に伴い，現在ではコスト面や地理的な理由から有線ネットワークを敷設できない場所 でもインターネットアクセスを導入したいという要求が高まっている．このため，これまで有線ネッ トワークを介して接続していた AP を無線で相互に接続し，通信エリアを制限なく拡大できるマル チホップ無線 LAN が注目を集めている．このマルチホップ無線 LAN は，既存の有線ネットワーク をバックボーンとした大規模な無線 LAN 基盤を実現し，これまでネットワークを敷設できなかった 場所にもインターネットアクセスを提供できると考えられている．しかし，マルチホップ無線 LAN により構築された大規模 LAN では，有線バックボーンネットワークと接続されるゲートウェイでの 負荷集中が問題となる．これはマルチホップ無線 LAN 内にあるサーバからのサービスよりも，有線 ネットワーク内にあるサービスを利用するユーザの方が多いためである．このようなゲートウェイ AP の負荷集中を回避するためには複数個のゲートウェイの設置が必要となる．しかし，既存のマル チホップ無線 LAN に対する研究や製品は，アドホック・ネットワークのルーティングプロトコルで ある OLSR (Optimized Link State Routing) や AODV (Ad hoc On-Demand Distance Vector) 等 の従来の経路制御しか想定していないため，最短経路上にある単一のゲートウェイ AP までの経路 しか把握できない上に，ゲートウェイ AP を動的に切替えることができない．これにより，有線バッ クボーンとのゲートウェイ AP に負荷が集中し，ゲートウェイ AP の無線リンクがネットワーク全 体のボトルネック・リンクとなる可能性がある． そこで，我々はゲートウェイ AP が複数個ある環境下で，負荷が集中していないゲートウェイ AP へ経路が切り替わるようにトラヒックを動的に制御する手法を提案し，シミュレーションによる評 価を行った．このトラヒック制御手法は，各 AP がマルチホップ無線 LAN 内の全てのゲートウェイ AP に対する経路を持ち，ゲートウェイ AP の負荷状況に合わせて動的に経路を切替えるアルゴリズ ムである．そのアルゴリズムとしては，以下の 2 つの手法を提案する． (1) ゲートウェイの負荷状況を指標とし，トラヒックの経路を切替える低負荷ゲートウェイ選 択手法 1 (2) ゲートウェイからの情報を基に，経路の切替えを行うトラヒックの量を制御し，緩やかに 負荷を分散させるフロー分割手法 そして，既存手法である最短経路長によるゲートウェイ選択手法と提案手法をシミュレーションによ り比較し，総スループット及び公平特性の点で改善できることを示す． まず以下 2 章において，マルチホップ無線 LAN の基本となる無線 LAN の概要を説明し，3 章で マルチホップ無線 LAN の概要について述べる．その後，4 章においてマルチホップ無線 LAN の問 題点が通信性能に与える影響についての調査結果を述べる．続いて 5 章で提案手法である，負荷が 集中していないゲートウェイ AP へ経路を切り替えるトラヒック制御手法を述べる．そして 6 章で 実験に使用したシミュレーション環境とその結果を示す．最後に 7 章で結論を述べる． 2 2 無線 LAN の概要 本章では，まず無線 LAN の概要を述べ，次章でマルチホップ無線 LAN の概要を述べる． 2.1 無線 LAN の概要 無線 LAN は， IEEE (Institute of Electric and Electronics Engine) によって 1997 年に 802.11 として初めて規格化され，現在も新しい規格の検討が進んでいる．以下にその通信規格の一部を簡潔 に示す． • IEEE 802.11a – 変調方式は OFDM( Orthogonal Frequency Division Multiplexing ) を用い，5 GHz 帯を 利用する通信規格．通信速度は最大 54 Mbps． • IEEE 802.11b – 2.4GHz 帯を利用し，変調方式として CCK( Complementary Code Keying ) を用いる通 信規格．通信速度は最大 11Mbps． • IEEE 802.11c – 有線 LAN と無線 LAN を接続するために追加された MAC 層の通信規格． • IEEE 802.11d – 2.4GHz 帯，5GHz 帯が利用できない国のための通信規格． • IEEE 802.11e – 品質保証のための物理仕様の拡張．MAC 層での QoS ( Quality of Service) を実現． • IEEE 802.11f – アクセスポイント間のローミングに用いられる通信規格． • IEEE 802.11g 3 – 2.4GHz 帯を利用し，IEEE 802.11b との互換性を保ちつつ，変調方式として OFDM を用 いる通信規格．通信速度は最大 54Mbps． • IEEE 802.11h – 欧州で 5GHz 帯 ( IEEE 802.11a ) を利用するための無線 LAN 通信規格． • IEEE 802.11i – セキュリティのための暗号化通信とユーザ認証に関する通信規格． • IEEE 802.11k – 使用する周波数帯をどのように割り当てるかなどの資源管理に用いる通信規格．実際は， 主に高周波信号の計測で位置情報など各種の情報をセンシングするために使用． • IEEE 802.11m – 既に規格化された 802.11a，802.11b 規格を修正するために用いられる通信規格． • IEEE 802.11n – 100Mbps 以上の高速通信を実現する無線 LAN のための仕様．次世代の無線 LAN 通信 規格． • IEEE 802.11p – 車々間，路車間などの高速移動体のための通信規格． • IEEE 802.11r – 高速ローミングのための通信規格．AP 間で STA の認証情報を共有することが可能． • IEEE 802.11s – メッシュネットワーク，マルチホップ無線 LAN のための通信規格． 本章では，上記の 802.11 規格の内，現在最も一般的な規格とされている IEEE 802.11b 無線 LAN (以後無線 LAN とする) の概要について述べる. 4 2.2 プロトコル構成 無線 LAN は, IEEE 802 の体系の中に組み込まれており, IEEE 802.11 の標準では MAC(Media Access Control) 層以下が規定されている. なお, MAC 層より上位のサービスに関する部分は有線 LAN と同様である. また, 通信媒体が無線であるため, MAC 層のフレームとは別に物理層にフレー ムを用いるサブレイヤが規定されている. 図 2.2 にそのプロトコル体系を示す. presentation layer session layer transport layer network layer DATA LINK LAYER IEEE802.1 Higher Level Layer Interface (HLLI) LLC IEEE802.2 Logical Linkn Layer (LLC) MAC IEEE802.11 CSMA/CA PHYSICAL LAYER IrDA OSI Reference model DS-SS FH-SS 802.11b DS-SS Wireless LAN IEEE802.3 CSMA/CD 10BASE Ethernet 100BASE Ethernet 1000BASE Ethernet Ethernet 図 2.1: IEEE 802 プロトコル体系 2.3 ネットワークトポロジ 無線 LAN のネットワークトポロジには，アドホック・モードとインフラストラクチャー・モード の 2 つがある．まず，アドホック・モードは STA のみにより構成されており，一般的に STA 間で の直接通信に用いられる．このため，容易にネットワークを構築できるが，ネットワーク規模は通信 を行う端末同士の電波が互いに届く範囲に限られるため, 小規模となる．図 2.2 はアドホック・モー ドのネットワークトポロジを示している． 一方，インフラストラクチャー・モードは，AP とその配下の複数の STA で構成される．このよ 5 STA STA STA 図 2.2: アドホック・モードのネットワークトポロジ うに構成されるネットワークを BSS(Basic Service Set) と呼ぶ．この BSS 内では，STA は一つの AP と論理的な接続関係 (Association) を確立する．一方の AP は，Ethernet などのバックボーン・ ネットワークに接続されており，接続関係が確立している配下の STA とバックボーン・ネットワー ク間のパケットの中継を行い，配下の STA 同士の通信を管理する．これにより，無線端末のユーザ は，ネットワーク上の各種サーバと無線環境で通信を行うことができる．図 2.3 にインフラストラク チャー・モードのネットワーク構成の一例を示す． また，以下に図 2.2 及び 図 2.3 中の用語についての説明を行う． STA(Station) : 無線ネットワーク・インタフェースを持つ計算機もしくは装置． AP(Access Point) : 無線ネットワークと有線ネットワークの間でフレームを転送するためのブ リッジもしくは無線ネットワークによってフレームの到達距離を延長するためのリピータ． BSS(Basic Service Set) : 一つの AP を基にし，同じ無線チャネルを利用して通信する STA で 構成されるセル． ESS(Extended Service Set) : 複数の BSS と有線 LAN ，及び複数の AP で構成されるドメイ ン．論理的に一つの BSS とみなせる． 6 Server Printer Ethernet (Backborn network) AP AP STA STA STA STA STA BSS ( BSSID = 2 ) BSS ( BSSID = 1 ) ESS 図 2.3: インフラストラクチャー・モードのネットワークトポロジ BSSID，ESSID : BSS ，ESS を区別するため，STA と AP に用いる固有の識別子 2.4 無線 LAN の使用周波数帯 無線 LAN では，STA から送信されるデジタル・データをアナログ・データに変調し，電波として 特定の周波数帯 (チャネル) を使用することにより搬送する．IEEE 802.11b および 11g では 2.4GHz 帯の周波数を使用する．この周波数帯は ISM (Industrial Science and Medical band) と呼ばれ，利 用のための免許を必要としないことから様々な機器に使用されている．このような ISM 帯を利用す る機器からの電波は，全て無線 LAN に対する妨害波になる．また他の IEEE 802.11 製品が近傍で 使用されている場合，その電波も妨害波となる．このため，無線 LAN では，使用する周波数帯域を 複数のチャネルに分割し，隣接するエリア内では相互に干渉しないチャネルを選択することが推奨 されている．日本国内の場合，2.4 GHz 帯で利用できるチャネル数は 14 と規定されており，隣接す る AP 間で干渉が発生しないようにチャネルを選択すると，2.412(1ch)，2.437(6ch)，2.462(11ch)， 2.484(14ch) GHz 帯 の 4 つを同時に使用することが可能である．これにより，互いに電波が届く範 7 囲で AP を複数設置する場合，最大 4 台の AP を設置することができる． IEEE 802.11 の使用する周波数帯には，2.4 GHz 帯の他に 5 GHz 帯を用いる IEEE 802.11a が存 在する．現在，この IEEE 802.11a は気象レーダ，航空機の自動着陸誘導システム，衛星通信，海上 での無線通信などのレーダー機器に物理的な電波干渉を及ぼすため，屋内の利用のみに限定されて いる [1]．しかし，将来的には IEEE 802.11a が屋外での利用も可能となり，無線 LAN を大幅に拡大 できると期待されている．現在，日本国内では 5.18(36ch)，5.20(40ch)，5.22(44ch)，5.24(48ch) ∼ 5.32(64ch) GHz 帯の 8 チャネルが利用できる． 2.5 MAC 層のメディアアクセス制御 IEEE 802.11 で規定されている MAC 層では，フレームの断片化，暗号化，電力管理，メディア アクセス制御，及びローミング機能などの管理を行っている．その中でも無線通信の多重化を行うメ ディアアクセス制御は，効率の良い無線通信を行う上で最も重要となる．IEEE 802.11 ではこのメ ディアアクセス制御に DCF (Distributed Coordination Function) と呼ばれる CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) 方式を採用した MAC 制御を用い， オプション として DCF とは異なるアクセス制御を行う PCF(Point Coordination Function) を策定している． これらのメディアアクセス技術を用いることで，複数の STA が同一の無線チャネルを使用しても， 送信データの衝突を抑えた効率の良い通信を行うことができる．本節ではこのメディアアクセス制御 技術の詳細について述べる． 2.5.1 DCF アクセス制御 複数の STA で同じチャネルを共有すると，フレームを送信した際に衝突が発生してしまう．そ こで送信を行う STA には，チャネルの使用状況を把握してフレームの衝突を回避するようなアク セス制御が必要となる．有線 LAN の場合，複数の端末が同一の通信媒体上でデータ通信を行うた めに CSMA/CD (Carrier Sense Multiple Access with Collision Detection ) 方式を用いる．この CSMA/CD 方式は，ネットワークに送信した信号と他のデータ送信信号との衝突による信号の変化 を検出することで衝突を検知する．しかし無線 LAN では，電波を伝送媒体として利用するため信号 の減衰が大きく，衝突を検知することは容易でないため，CSMA/CD 方式のような衝突検知による 通信の多重化は困難である．そこで無線 LAN では，各送信端末でデータの衝突を回避するように， 8 送信側で通信を制御を行うメディアアクセス制御方式が用いられている．IEEE 802.11 は，このよう なメディアアクセス制御方式として DCF と呼ばれる機能を採用している．この DCF により，送信 データの衝突確率が減少し，周辺に同一チャネルを利用する STA が存在した場合でも，各 STA は同 じチャネルを共有することができる．この DCF を実現するための制御方式として，CSMA/CA 方式 と呼ばれるメディアアクセス制御方式が用いられている．以降，2.5.2 ∼2.5.4 節では，CSMA/CA 方式の概要と DCF の基本となる IFS 間隔及びバックオフ制御について説明し，2.5.5 節で無線 LAN 特有の問題を述べ，その解決手段として DCF で用いられる機能を 2.5.6 節で述べる． 2.5.2 CSMA/CA 方式 IEEE 802.11 では，複数の STA が同一の使用チャネルで通信媒体を共有するためのアクセス制 御方式として，CSMA/CA 方式を用いる．この CSMA/CA 方式では，まず，フレームを送信する STA が衝突検知 (キャリア・センス) を行い，無線チャネルの使用状況を確認する．その後，一定期 間無線チャネルが未使用 (アイドル状態) であれば送信を開始する．逆に無線チャネルが他の STA の フレーム送信などにより使用中 (ビジー状態) であれば，アイドル状態を確認するまで送信を延期し， データの衝突を回避する．このときの送信延期の期間については 2.5.3 ∼ 2.5.4 節で説明する．そ して送信延期期間の後，STA は再度キャリア・センスを行い，他に送信する STA が存在しなければ 送信を開始できる．その後，フレームの受信を行った受信側では，受信確認に ACK 信号を送信側へ 送出する．送信側ではこの ACK 信号を受信できなかった場合，通信障害があったとみなしてフレー ムの再送を行う． 2.5.3 IFS 間隔による制御 IEEE 802.11 には，信号を送信する前に最低限の送出信号間隔として IFS (Inter Frame Space) が 定義されている．IFS 時間は固定長の送出間隔で，複数の種類が定義されており，それらを使い分け ることで送信を延期する時間を制御できる．IFS の短いフレームほど先に送信権を獲得でき，送信フ レームに複数の優先権を設定することが可能となる． IFS には図 2.4 に示すような種類が存在する． 9 Priority High Priority Low DIFS PIFS Send frame SIFS Time 図 2.4: IFS による優先制御の仕組み ・ SIFS(Short IFS) - 最優先のフレーム間隔． - IEEE 802.11 で定義されているフレーム送信間隔で最小のものである．ACK フレームや 後述の RTS(Request to Send) に対する CTS(Clear to Send) フレームなどを送信する際 に用いる． ・ PIFS(PCF IFS) - ポーリング (各 STA に順次，送信機会を与える送信制御) 用フレーム間隔. - 2.5.7 節で述べる PCF による集中制御の際に使用される．キャリア・センスを行う際に， 使用チャネルがビジー状態からアイドル状態へと変化したことを判断するまでに必要な 期間． - SIFS より優先度が低い． ・ DIFS(DCF IFS) - 分散制御用フレーム間隔． - DCF において衝突検知を行う際に, PIFS 同様にビジー状態のチャンネルからアイドル状 態へと変化したことを判断するまでに必要な期間． - PIFS より優先度が低い． IFS を用いた例として，DCF 制御では送信側のフレーム送信に DIFS 時間を使用する．一方，受 信側では，正しくデータ・フレームを受取り次第，送信側に正常受信したことを伝えるための確認応 10 答フレーム ( ACK フレーム ) を SIFS 時間待機した後に送信する．このように ACK フレームに対 して，DIFS 時間より短い SIFS 時間を用いることで，フレームを送信する他の STA に通信を割り 込まれることなく ACK フレームを受信でき，通信を完了することができる． 2.5.4 バックオフ制御 DCF でフレームを送信する場合，全ての STA が同じ DIFS 間隔で送信を行うため，フレームの 衝突をあらかじめ回避するための MAC 制御が必要になる．このため DCF ではフレーム送信する 際に，DIFS 間隔で送信を延期した後，更にランダムに送信時間を延期させるバックオフ制御が用 いられる．バックオフ制御は，キャリア・センスと同じく，衝突を回避するための方法として IEEE 802.11 で規定されている．バックオフ制御では，送信側の STA は送信を DIFS 時間待機した後，規 定の CW(Contention Window) 範囲内で乱数を発生させ，その値を基にランダムな送信延期時間と なるバックオフ時間を決定する．このバックオフ時間は一定時間のスロット・タイムの倍数であり， アイドル状態であれば乱数値をスロット・タイムごとに減算していき，最後に 0 となった時に STA は送信を開始することができる．これにより，各 STA は公平な送信機会が得られる．また，フレー ムが衝突した場合には，再送ごとにバックオフ制御の CW の範囲を 2 倍に増加した 2 進数指数バッ クオフを用いるため，フレームの再衝突する確率を低減することができる． 2.5.5 隠れ端末問題 無線 LAN の STA 間では，同じ BSS 内に属していながら，互いの存在を認識できないという状 況が起こり得る．これは， STA 間の距離や電波を通さない障害物などの影響により，互いの無線信 号が到達しないためである．このような現象を隠れ端末問題と呼ぶ． 図 2.5 は，隠れ端末が存在する場合の無線通信の状態を示している．図 2.5 中の STA1 と STA3， STA2 と STA3 は障害物により無線信号が到達しない状況にあるため， キャリア・センスができず， チャネルの使用状態を正確に把握できない．そのため，STA1 は AP にフレームを送信しているの にも関わらず，STA3 も AP へフレームを送信するため，STA1 と STA3 の送信フレームの衝突が 生じる．このように隠れ端末が存在すると衝突検知が有効に機能しないため，フレーム衝突頻度が増 し，スループット特性を悪化させる原因となる． 11 : Carrier sense is possible : Carrier sense is impossible AP : Sending frame Collision STA 1 STA 3 STA 2 barrier 図 2.5: 隠れ端末問題 2.5.6 RTC/CTS による解決 前節 2.5.5 で述べた隠れ端末問題を解決するため，IEEE 802.11 規格では RTS(Request to Send) / CTS(Clear to Send) フレームを使用する．RTS/CTS フレームは，デュレーション・フィールド と呼ばれるフィールドに記載されている期間の通信時間を予約できるため，この期間中は他の STA の送信を禁止することができる．つまり，送信元以外の各 STA は RTS/CTS フレームにより送信 元 STA の通信期間を通知され，この間は送信できない．この通信期間を NAV(Network Allocation Vector) 期間と呼ぶ．RTS と CTS の NAV 期間は異なり，送信 STA から電波の届く STA には RTS の NAV 期間が設定され，電波の届かない隠れ端末には CTS の NAV 期間が AP から通知される． RTS の NAV 期間には，送信する STA が送信を開始してから完了するまでの期間，CTS の NAV 期間には，CTS の通知から送信する STA の送信が完了するまでの期間を使用する． このように RTS/CTS フレームと NAV 期間を利用することで仮想的なキャリア・センスを行うた め，送信を行う STA の存在を認知し，隠れ端末問題を回避できる．RTS/CTS を用いた CSMA/CA 方式の手順を図 2.6 に示す． 12 AP CTS STA 1 SIFS DIFS Back off ACK SIFS SIFS send data frame RTS STA 2 STA１のキャリア センス可能な STA NAV (RTS) STA 3 STA１からの隠れ STA NAV (CTS) 図 2.6: RTS/CTS を用いた CSMA/CA の手順 • 図 2.6 に示す通信手順 1. 送信元 STA1 はデータ・フレーム送信前に DIFS +バックオフ時間待機し，その後，キャ リア・センスを行い，RTS データ・フレームを AP 宛に送信する． 2. ここで， RTS フレームは電波の届く全てのノードに通知されるため，互いに衝突検知可 能な伝搬環境にある STA2 も RTS を受け取る. 3. RTS を受け取った STA2 では NAV 期間をセットし，フレームの衝突を防止する． 4. STA1 からのデータ・フレームを受け取る AP では, RTS 受信後に SIFS 時間待機し， STA1 に CTS フレームを返す． 5. AP が送信する CTS フレームは衝突検知できない隠れ端末 STA3 であっても受信できる ため，送信元以外の STA には NAV がセットされ，フレームの衝突を防ぐ． 6. STA1 は CTS フレームを受信すると，SIFS 後にデータ・フレームの送信を開始する． 7. データ・フレームを受信した AP は，ACK フレームを STA1 に返して通信を終了する． 13 2.5.7 PCF アクセス制御方式 CSMA/CA 方式では偶発的にフレームが無線上で衝突する可能性がある．このフレーム衝突確率 は STA とトラヒックの増加に比例する．よって，BSS 内の STA 台数が増加すれば，スループット の低下を招くことになる．この問題点を解決するため IEEE 802.11 では，オプションとして PCF を 用意している．DCF は送信するフレームが衝突することを前提にしているのに対し，PCF は衝突 の発生を防ぐことを目的としたアクセス制御方式である．PCF は BSS 内で AP の配下にある STA へのポーリングを行うことで，順番に STA がフレームを送信し，衝突を回避できるアクセス方式で ある．ポーリングを行う AP は Point Coordinator と定義されており，所属する BSS 配下の STA に対してアクセス制御を行う．以下に基本的な動作を示す． • PCF 制御の基本動作 1. STA は AP と接続環境を確立させる際に，PCF に参加することを要請する アソシエー ション要求フレームを AP に送信する． 2. AP は，STA からの要請に基づきポーリングを行う STA のリスト (ポーリング・リスト) を作成し，その管理を行う．また，STA との接続関係を解除したいときはこのポーリン グ・リストから該当端末を削除することで接続解除できる． 3. AP はこのポーリング・リストに基づき，STA を順番にポーリングする．ポーリングは ポーリング・リストが終るまで，もしくはあらかじめ定められた PCF 制御の最大継続時 間が経過するまで繰り返される． 4. STA ではポーリングで自局が指定されたときのみパケットを送信し，指定がなければ送 信を行わない． 上記のような動作のため， DCF のように送信パケットが衝突することはない． 14 3 マルチホップ無線 LAN の概要 マルチホップ無線 LAN は 2 章で述べた無線 LAN の通信方式を基に，中継端末となる AP を無線 で相互に接続することで，通信範囲を拡大するネットワークである．このマルチホップ無線 LAN で は，無線での通信範囲が広がることで電波干渉による影響が大きくなる．このため，データを中継す る各ノードが使用するチャネルをどのように割り当てるかが重要になる． 本章では，このマルチホップ無線 LAN を構築する上で必要となるチャネル環境について述べ，続 いてマルチホップ無線 LAN の現状と問題点について述べる． 3.1 チャネル環境 マルチホップ無線 LAN では，送信データが中継ノードを経由する数 (ホップ数) の増加に伴い，他 の送信データとの送信権の競合や電波干渉などの問題点が増加する．このため，単純に一つのチャネ ルのみで構築されたネットワーク環境 (シングルチャネル環境) では，CSMA/CA 方式の MAC 制 御による送信権の競合などがホップ数の増加に従い増大し，通信性能が著しく減少する． Destination Node AP1’s DATA Collision : AP1 vs AP2 AP4 vs AP3 vs AP4 vs AP5 AP5 vs AP6 AP6 AP1’s DATA Collision : AP1 vs AP2 vs AP3 vs AP4 vs AP5 vs AP1’s DATA AP1 AP2 AP3 図 3.1: シングルチャネル環境 15 AP6 Destination Node AP4’s DATA AP6’s DATA AP1’s DATA AP2’s DATA AP3’s DATA AP5’s DATA 48ch 56ch 52ch AP4’s DATA AP6’s DATA AP4 AP1’s DATA AP5 AP3’s DATA AP6 AP2’s DATA 36ch AP1’s DATA AP1 40ch 44ch AP2’s DATA AP2 AP3’s DATA AP3 図 3.2: マルチチャネル環境 この様子を図 3.1 に示すトポロジを例にして述べる．AP1 のデータは AP5 を経由し，Destination N ode に向けて送信する．このとき，他の AP も同様にデータを Destination N ode に向けて送信してい るものとする．まず AP1 の送信データは CSMA/CA 方式の MAC 制御により，同じチャネルを使 用する AP2，AP3，AP4，AP5，AP6 と送信権を競合する．そして送信権を獲得できた AP1 の送信 データが，更に 1 ホップ先の中継ノードとなる AP5 に到達する．しかし AP1 の送信データは AP5 から転送される際，再び全送信ノードと送信権を競合する． このようにシングルチャネル環境では，送信されたデータは無線端末を中継する度に送信権を競 √ 合するため通信性能が減少し，その減少度合はホップ数 n とした O(1/ n) に従う急激な特性とさ れている [2]．またシングルチャネル環境では，各 AP は電波の届く範囲にある全ての通信ノードの RTS/CTS パケットを傍受してしまうため，NAV 期間による非通信時間が増大する晒し端末問題を 引き起こす [3]．よって，実際の通信性能は電波の到達範囲やトポロジ等に依存して更に劣化する． この問題を改善するため，現在のマルチホップ無線 LAN は他ノードの送信権の競合や，電波干渉 等を物理的に回避する方法を用いている．例えば，図 3.2 のように使用するチャネルを複数用いるマ ルチチャネル環境を利用し，各チャネルに対応した数だけ無線インタフェースを用いることにより， 16 送信権を競合することなく，送受信を効率的に行うことができる [4]． 3.2 マルチホップ無線 LAN の現状と問題点 マルチホップ無線 LAN は AP を無線で相互に接続できるため，コスト面や地理的な理由から有線 ネットワークを敷設できない場所でも無線 LAN を導入することができる．このため，通信エリアを 容易に拡大できるネットワークとして注目を集めている．このマルチホップ無線 LAN では，前節で 述べた送信権の競合などの無線特有の問題が通信端末を中継する度に増加するため，実現に向けた 新たな規格が必要になる．よって，これまでのマルチホップ無線 LAN の研究では，新しいルーティ ング・アルゴリズムや MAC 層の機能などが提案されてきた [5]．そこで，3.2.1 ∼ 3.2.3 節では提 案されている代表的なルーティングアルゴリズムと MAC 層の機能の一部を述べ， 3.2.4 節でマル チホップ無線 LAN の問題点を述べる． 3.2.1 アドホック・ネットワークのルーティングアルゴリズム 現在のマルチホップ無線 LAN で使用するルーティング・アルゴリズムは，アドホック・ネットワー クで用いられるルーティング・プロトコルが一般的である．本節ではその中でも代表的なルーティン グプロトコルである AODV (Adhoc On-Demand Distance Vector) と OLSR (Optimized Link State Routing) について説明する． • AODV (Adhoc On-Demand Distance Vector) AODV は，データを送受信しようとしたときに経路を探索するアルゴリズムである．経 路の探索には RREQ (Route Request)，RREP (Route Reply) という制御メッセージを 使用する．図 3.3 に AODV の経路作成の様子を示し，各メッセージの内容については以 下に示す． – RREQ メッセージ ∗ 送信元ノードは目的ノードへの経路が必要になったとき，その経路を見つけるた めの RREQ メッセージを周辺ノードに対してブロードキャストする (図 3.3 中の (1) )．このように，特定のノードが制御メッセージ等をネットワーク上にブロー 17 Destination Node Forward Node RREQ RREQ (3) RREQ RREQ RREQ RREP RREP (2) RREQ (1) Source Node 図 3.3: AODV による経路探索 ドキャストし，中継ノードが受信メッセージを転送することで，制御メッセージ 等がネットワーク全体に伝搬することをフラッディングという． – RREP メッセージ ∗ 目的ノードに RREQ メッセージが届くと，目的ノードは RREP メッセージ を 送信元へ向けてユニキャストで送り返す (図 3.3 中の (2) )．ここで，RREQ メッ セージが中継ノードに届いた場合，要求される目的ノードまでの経路を保持して いれば，目的ノードの代わりに RREP を返す．逆に，経路を保持していなけれ ば，再びフラッディングを行う ( 図 3.3 中の (3))． 以上のような RREQ メッセージと RREP メッセージのやり取りによって，送信元と目的 ノード以外の中継ノードにも，送信元と目的ノードへの双方向の経路が作成される．従っ て，AODV プロトコルはネットワーク全体の経路を除々に作成することが可能である．ま た AODV では， RREQ メッセージをネットワーク全体にフラッディングしないように 設計されている．これはフラッディングによるネットワーク負荷を，ネットワーク全体に 与えないようにするためである．AODV のフラッディング方法は，まず RREQ メッセー ジを転送するホップ数を制限し，目的ノードが見つかるまで徐々に転送を行うホップ数を 大きくし，探索する範囲を広げていくという手法である．この他に AODV では RERR 18 Node A 図 3.4: 一般的なフラッディングの様子 (Route Error) メッセージを用いた無効経路を通知する機能も存在する． • OLSR (Optimized Link State Routing) OLSR は，各ノードが経路情報等を記載した HELLO メッセージと呼ばれるパケットを 定期的にネットワーク上にフラッディングすることで，各ノードでネットワークのトポロ ジ情報を把握するアルゴリズムである．このためパケットを送信する前に，得られたト ポロジ情報を基にメトリックを計算し経路を決定することができる．よって OLSR では AODV と異なり，あらかじめ送信元が経路表を保持している．ここで OLSR は，経路探 索のための HELLO メッセージを定期的にフラッディングするため，ネットワーク全体 に負荷を与えないような効率的なフラッディング手法が必要となる． これは，図 3.4 に示すように，たった一台の Node A のフラッディングによって，ネット ワーク全体のノードでパケット転送が行われるためである．OLSR では，このようなフ ラッディングによるネットワーク全体への影響を回避するため，MPR (Multipoint relay) と呼ばれるノードのみがフラッディングを行うように設計されている．この MPR は， 「隣 接ノードの集合から，1 ホップ先に存在する全てのパケットを転送できるようなノード」 である．図 3.5 は，この MPR の例である． 図 3.5 中のフラッディングノード Node A は，Node A の MPR である Node B に対し てのみ Hello メッセージを送出する．これを受けた Node B は 1 ホップ以内に存在する 19 Node A Node B Node C 図 3.5: MPR 集合によるフラッディングの様子 ノードに対してフラッディングを行う．このとき，Hello メッセージを受けた Node B の MPR である Node C も，1 ホップ以内に存在するノードに対してフラッディングを行う． これにより，ネットワーク全体に Node A の Hello メッセージが到着する．このように MPR によって図 3.4 の場合よりも，ネットワーク全体にフラッディングされるパケット 量が減少したことが分かる．なお MPR の選択方法は，Hello メッセージ上に記載された 「 フラッディングによるパケットをどの程度の頻度で転送できるか」の値を基に，転送で きる可能性が最も高いノードを MPR とする． 以上のようなアドホック・ルーティングプロトコルがマルチホップ無線 LAN に使用されている． 3.2.2 シングルチャネルを想定した MAC 層の研究 3.2.2 節と 3.2.3 節では，これまで行われてきた MAC 層に関する研究の概要について述べる． まず，シングルチャネル環境を想定した MAC 層の研究は，以下の 3 つに分類される [5]． - CSMA/CA の拡張 [6] トラヒックの種類やネットワークの状況に応じて CW や バックオフ時間を制御し，最適 値を設定することで通信性能を向上させる研究．この研究により，1 ホップの区間であれ ば，スループット性能の改善が得られることが分かった．しかし，大規模なマルチホップ 20 無線 LAN では，ホップする度に送信権の競合の影響が大きくなるため，end-to-end の スループット特性までは改善できない． - MAC 層と物理層との連携 [3] 主に指向性アンテナを用いる手法と送信電力を制御する手法に分かれる． • 指向性アンテナを用いる手法は，自身の通信に関係のない RTS/CTS を傍受しない ように，アンテナを制御する研究である．これにより，晒し端末問題を軽減すること ができる．但し，新たな隠れ端末が増加するため，後続の研究では隠れ端末を減少さ せることが求められている． • 送信電力を制御する手法は，送信電力を制御することで電波の到達範囲を調整し，通 信の干渉を抑える．これにより，密度の高いネットワークのスループットの改善や， 送信帯域の利用率向上，晒し端末の減少などが可能となる．しかし，電波の到達範囲 を減少させたことで，隠れ端末を探知する範囲も減り，隠れ端末問題が依然として解 決できない． - MAC 層の根本的な仕様変更 [7] 狭い通信範囲を前提とした CSMA/CA 方式は，end-to-end のスループットを低下させ るため，マルチホップ無線 LAN には適していない．このため，TDMA (Time Dvision Multiple Access) や CDMA (Code Division Multiple Access) を基にした MAC 層の再 設計が研究されている．これまでの研究は以下の 2 通りの考え方に基づく． • 各無線 LAN 中継機が分散かつ協調して動作するような MAC 制御を設計する研究． 実際に，IEEE 802.16 では分散型の TDMA 方式が検討されている．但し，低コスト による手法の実現や互換性の向上が必要とされる． • 既存の MAC 層と互換性を保ちながら，TDMA や CDMA を実現する MAC 制御を 設計する研究．IEEE 802.11 で検討されている． しかし，一般的にはシングルチャネル環境よりもマルチチャネル環境を想定したマルチホップ無 線 LAN の方が多い．これは，マルチチャネル環境の方が end-to-end の通信性能が良いとされてい るためである [4]．従って次節では，マルチチャネル環境での MAC 層の研究を述べる． 21 3.2.3 マルチチャネル環境を想定した MAC 層の研究 マルチチャネル環境を実現するハードウェアについては，大別して 3 つ存在する．どのハードウェ アの使用を前提とするかによって，MAC 層の研究対象は大きく異なる [5]．以下にその内容を記す． a) 複数のチャネルを実装し，必要に応じてチャネルを切替え可能なハードウェアを用いる場合． b) 複数のチャネルを実装し，使用するチャネルを同時に利用可能なハードウェアを用いる場合． c) シングルチャネル環境で用いるハードウェアである無線 NIC(Network Interface Card) を複数 個用いる場合． 現在は，それぞれのハードウェアの使用を前提とした研究が行われている．まず，a)，b) を使用 した環境では，以下に示す研究が行われている [8]． • 各ノードで全てのチャネルの利用状況を把握する研究 – 大規模なマルチホップ無線 LAN で，全体の使用チャネルの利用状況を同期させる研究． 但し，チャネルの利用状況を伝える制御メッセージの伝搬方法などが確立されていないた め実現が難しいとされている． • 各ノードにチャネルの確立を伝える研究 – RTS/CTS を拡張し，チャネルの利用状況を伝える手法などが提案されている．但し， RTS/CTS をサポートしない場合については検討が必要である． • チャネルをどのような基準で選択し，切替えるかに関する研究． – 使用可能なチャネルの内，ソースとデスティネーションペアの数が最小となっているチャ ネルを選択する手法などが提案されている．また，パケットを転送していないチャネルを 選択する手法もあり，こちらの手法ではいくつかの性能が改善さている．但し，チャネル の切替え時間は 224 usec 以上かかるため，切替えの際の性能低下は避けられない． これら a)，b) はハードウェアへの実装が容易でない上に，隠れ端末問題の解決ための RTS/CTS やチャネル確立を知らせるメッセージの使用により，新たな晒し端末が発生する．これにより，本研 究では，上記 c) によるマルチホップ無線 LAN を想定している．なお，c) によるマルチホップ無線 22 LAN について，各ノードが使用するチャネルを動的に割り当てる手法も提案されている．チャネル の動的な割り当ての提案につていは，以下に示す研究を中心に行われている [9]． • 隣接ノードの探索と発見に関する研究． • 使用チャネル (NIC) の選択に関する研究 – 使用するチャネルで，1 ホップ先にあるノードの RTT (Round Trip Time) を計測し，最 小となるチャネルを選択する手法などがある． しかし，チャネルを動的に割り当てるために以下のような問題点が挙げられている [5]． • 隠れ端末問題は依然として存在している． • チャネルの割り当てと切替えには，物理層の特徴や隣接ノードの電波干渉を考慮しなくてはな らない． • マルチホップ無線 LAN では，end-to-end のスループットを高めるために，TCP の挙動を考 慮する必要がある． • 各 NIC に固定チャネルを割り当てるのは，コスト面，使用できるチャネル数の制限などから 限界がある． 以上の使用チャネルを動的割り当てるための問題を改善することは難しく，まだ効果的な提案手法 は考えられていない．しかし，無線 LAN 基盤として都市部に設置される AP に関しては，各 AP を設置するプロバイダが，電波の干渉を考慮し，チャネルを静的に割り当てることで，電波の干渉が 少ないマルチホップ無線 LAN を実現できる． 3.2.4 マルチホップ無線 LAN の問題点 現在では，前節までの提案を基に，無線規格の標準化を進める IEEE 802.11 のタスク・グループ 802.11s が詳細な仕様を検討している [10, 11]．また，無線製品ベンダでも独自に研究開発を行い，マ ルチホップ無線 LAN の実用化に取り組んでいる．例えば FireTied 社 [12] は，アドホック型のネット ワークに利用されるルーティング・プロトコルと独自のプロトコルを組み合わせた製品を開発してい る．一方で，マルチホップ無線 LAN については研究開発だけではなく，その利用についても様々な 23 検討がなされている．実際に，IEEE 802.16 では，都市部のブロードバンド・ネットワークを，ネッ トワーク環境を導入できない地域へと拡大させるための手段としてマルチホップ無線 LAN を利用す ることを検討している [13]．また，マルチホップ無線 LAN は，Wireless Mesh Netowrk とも呼ば れ，次世代 PAN (Personal Area Network) や，センサネットワーク等への利用など様々な応用が可 能である． 以上のようなマルチホップ無線 LAN の導入例の中でも，特に既存の有線ネットワークをバック ボーンとし，AP 間を無線で接続した大規模な無線 LAN 基盤の実現が期待されている．これは図 3.6 で示すように，有線ネットワークに接続された少数の AP と多数の AP を設置するだけでインター ネットへのアクセスを容易に拡大できるためである． Internet AP AP AP AP AP AP STA STA AP AP AP AP STA Multi Hop Wireless Network 図 3.6: 大規模なマルチホップ無線 LAN このようなマルチホップ無線 LAN による大規模 LAN を構築したとき，有線バックボーンネット ワークと接続されるゲートウェイでの負荷集中が問題となる．これはマルチホップ無線 LAN 内にあ るサーバからのサービスよりも，有線ネットワーク内にあるサービスを利用するユーザの方が多いた めである．このようなゲートウェイへの負荷集中を回避するためには複数のゲートウェイの設置が必 要である．しかし，既存のマルチホップ無線 LAN に対する研究や製品は，アドホック・ネットワー クのルーティングプロトコルである OLSR や AODV 等の従来の経路制御を想定しており，最短経 路上にある単一のゲートウェイまでの経路しか把握できない．これにより，通信ノードは選択する 24 ゲートウェイが輻輳した場合でも，ゲートウェイを動的に切替えることができず，一部のゲートウェ イに負荷を集中させてしまう．このような負荷集中が，通信性能にどのような影響を及ぼすかについ ては，次章の実験より明かにする． 25 4 マルチホップ無線 LAN における負荷の集中 hop link2 hop link1 host1 AP 2 hop link3 hop link4 AP3 AP8 AP13 AP18 AP4 AP9 AP14 AP19 AP5 AP10 AP15 AP20 AP6 AP11 AP16 AP21 AP7 AP12 AP17 AP22 Gateway AP TCP flow Wired Wireless Wired link Wireless link : Wired link Rate : 100 Mb/s Delay : 0.001 msec Protocol : 802.3 : 5.18 GHz (36ch) : 5.24 GHz (48ch) : 5.30 GHz (60ch) : 5.22 GHz (44ch) Rate : 54 Mb/s Protocol : 802.11a 図 4.1: 負荷が集中したマルチホップ無線 LAN 本章は，マルチホップ無線 LAN での負荷の集中が及ぼす影響について，シミュレーションによる 調査を行った．実験で使用したトポロジは 図 4.1 に示す．図 4.1 で，host1 は無線と有線ネットワー クのゲートウェイ AP である AP2 と有線で接続されている．ここでは，ゲートウェイ AP へ負荷が 集中した場合の問題点を明確にするため，図 4.1 のような AP2 へ負荷が集中するツリートポロジを 想定した．なお本実験は，図 4.1 中の各 hop link 毎で異なるチャネルを使用するマルチ・チャネル環 境を想定した．また，トラヒックモデルは，高負荷時の通信性能を調査するため Greedy なファイル 転送を想定した．トランスポートプロトコルは TCP/Sack オプションとし，各 AP は host1 へ向け て 1500 Byte の TCP パケットを 3 分間送信するとした．なお，本稿のシミュレータには Qualnet 3.9 を用いている． 26 表 4.1: TCP 通信の調査結果 ソースノード Throughput [Kb/s] ソースノード Throughput [Kb/s] AP3 1515 AP8 329 AP4 1517 AP9 427 AP5 326 AP10 538 AP6 1517 AP11 385 AP7 1521 AP12 408 AP13 316 AP18 340 AP14 331 AP19 350 AP15 370 AP20 378 AP16 353 AP21 346 AP17 407 AP22 367 12046 総スループット量 表 4.1 にシミュレーションで得られたスループット特性を示す．まず，表 4.1 中の AP3 ∼ AP7 に 注目する．表 4.1 より，AP3，AP4，AP6，AP7 のスループットは約 1.5 Mb/s とほぼ等しい．こ れは同じホップ数の AP が CSMA/CA 方式の MAC 制御により送信権を競合し，無線リンクの帯 域を共有するためである．一方，これら AP3，AP4，AP6，AP7 に対し，配下に多くの AP を抱え る AP5 のスループットは約 300 Kb/s と低い．これは AP5 が，自身に接続する AP から到着する パケットも送信しなければならないためである．従って，AP5 自体のスループットは AP3，AP4， AP6，AP7 よりも低くなる．しかし表 4.1 より，AP5 の転送量となる AP5 以下に所属する AP の 総獲得スループットは約 6.0 Mb/s で，AP3，AP4，AP6，AP7 がそれぞれ獲得した約 1.5 Mb/s の スループット量よりも大きい．このことから，AP5 は hop link1 内での送信機会を最も多く獲得し ていることが分かり，hop link1 内の送信機会は公平ではないことが分かる． 27 Window Size [KBytes] 200 AP3 AP4 AP6 AP7 AP5 AP8 AP9 AP10 AP11 AP12 AP13 AP14 AP15 AP16 150 100 AP17 AP18 AP19 AP20 AP21 AP22 500 0 0 20 40 60 80 100 120 140 160 180 Simulation Time [sec] 図 4.2: 各 AP のウィンドウサイズの変化 この理由を各 AP のウィンドウサイズの変化を示した図 4.2 より説明する．まず図 4.2 より，AP3， AP4，AP6，AP7 の送信量は 150 KBytes 以上増加していないことが分かる．これは，今回の実験で 使用する TCP のバッファサイズを 150 KBytes としたためである．即ち AP3，AP4，AP6，AP7 は，広告ウィンドウサイズの上限値となる 150 KBytes よりも送信量を増加させることができないた めである．一方，AP5 での送信量は，AP8 ∼ AP22 から到着するパケットも転送するため，図 4.2 に示す AP5 と AP8 ∼ AP22 のウィンドウサイズの総和が hop link1 における AP5 の転送量とな る．従って，AP5 の hop link1 内での送信機会は AP3，AP4，AP6，AP7 よりも多く，hop link1 内で各 AP が獲得する送信機会は公平ではない． ここで，hop link1 内の各 AP の送信機会は，広告ウィンドウサイズの上限値となる TCP のバッ ファサイズを増強することで等しくなると予測される．そこで TCP のバッファサイズを 1.5 MBytes としたときのスループット特性を調査し，その結果を表 4.2 に示す．表 4.2 より，AP3，AP4，AP6， AP7 のスループットは，それぞれ約 1.9 Mb/s に対し，AP5 以下の AP の総獲得スループットは約 2.0 Mb/s とほぼ等しくなり，hop link1 での送信機会は公平になることが分かった．しかし表 4.2 28 表 4.2: バッファサイズ 1.5 MBytes の場合の TCP 通信の調査結果 ソースノード Throughput [Kb/s] ソースノード Throughput [Kb/s] AP3 1864 AP8 32 AP4 1889 AP9 33 AP5 79 AP10 133 AP6 1872 AP11 157 AP7 1915 AP12 129 AP13 89 AP18 184 AP14 152 AP19 212 AP15 162 AP20 157 AP16 145 AP21 346 AP17 152 AP22 42 9574 総スループット量 の総スループットは，表 4.1 の約 12 Mb/s から約 9.5 Mb/s と低下していることが分かる．これは， 広告ウィンドウサイズの上限を 1.5 Mb/s としたことで，hop link1 内にある AP はゲートウェイ AP への通信帯域を占有し，AP5 から転送されるパケットの転送量を減少させたためである．よっ て，hop link1 の獲得機会を公平にするために，TCP のバッファサイズを増強することは，総獲得 スループットの減少を引き起こす．また，参考文献 [14] では，マルチホップ無線 LAN の TCP 性能 はウィンドウサイズを固定した場合の方が良いとしている．更に，実際に TCP フローを生成するの は STA であり，STA が使用する一般的なオペレーティングシステムのウィンドウサイズの上限値 は約 64KBytes であることから，TCP のバッファサイズを 1.5 MBytes とするのは現実的ではない． また，一般的な無線 LAN の AP の TCP バッファサイズは，バッファサイズを公開している製品で は 64 ∼ 150 KBytes であった．よって，本研究では 150 KBytes を TCP バッファサイズとして使 用している． 29 これまで説明したきた表 4.1，表 4.2 より，AP5 以下に属する AP のスループットはほぼ等しいこ とが分かる．これは，ボトルネック・リンクの発生とそれに伴う ACK パケットの遅延，そして TCP セルフクロッキングの発生が原因である．まず，ボトルネック・リンクの発生について，各 AP の 待ち行列での遅延の状態を示した表 4.3 より説明する．表 4.3 は，平均待ち行列長と最大待ち行列 長，及びバッファ内にパケットが滞在した平均時間を示している．なお，表中の “APx-> APy” は， “APx の APy への無線リンクのバッファ” を示す． 30 表 4.3: バッファの平均待ち行列長，最大待ち行列長，平均滞在時間 Link 平均 最大 平均滞在時間 [Bytes] [Bytes] [msec] 21748 42824 770 AP3 -> AP2 529 32340 2.70 AP4 -> AP2 465 21560 2.37 AP5 -> AP2 45555 149380 58.9 AP6 -> AP2 450 32340 2.29 AP7 -> AP2 530 33880 2.69 0.285 240 0.02 AP8 -> AP5 13 10780 0.31 AP9 -> AP5 17 6160 0.31 AP10 -> AP5 52 12320 0.09 AP11 -> AP5 15 10780 0.31 AP12 -> AP5 16 6160 0.31 0.08 160 0.01 AP13 -> AP10 12 10780 0.31 AP14 -> AP10 12 7700 0.29 AP15 -> AP10 23 10780 0.08 AP16 -> AP10 13 6160 0.30 AP17 -> AP10 15 9240 0.30 0.018 208 0.003 AP18 -> AP15 12 6160 0.28 AP19 -> AP15 12 4620 0.28 AP20 -> AP15 13 6160 0.28 AP21 -> AP15 12 6160 0.28 AP22 -> AP15 14 6160 0.28 AP2 -> AP3,4,5,6,7 hop link1 AP5 -> AP8,9,10,11,12 hop link2 AP10 -> AP13,14,15,16,17 hop link3 AP15 -> AP18,19,20,21,22 hop link4 31 表 4.3 より，図 4.1 中の hop link1 に接続している AP2 ∼ AP7 の平均待ち行列長，最大待ち行 列長，平均滞在時間が他の AP よりも大きいことから，hop link1 はボトルネック・リンクであるこ とが分かる (表 4.3 中の太枠部分)．特に，AP5 から AP2 へのリンクの平均待ち行列長，最大待ち行 列長は共に他の AP よりも大きい．これは，AP5 以下の AP のデータパケットが AP5 のバッファ で送信待機のために蓄積されるからである．従って，平均滞在時間も約 58 msec と大きく，AP5 の 待ち行列での遅延が AP5 以下の AP にとってのボトルネックとなる． 次にこのボトルネック・リンクによってパケットの遅延が増大する現象について説明する．図 4.3 に各 AP から host1 へのデータパケットの遅延時間を示す．図 4.3 より，AP3，AP4，AP6，AP7 からのデータパケットの遅延時間と，その他の AP からのデータパケットの遅延時間を比較すると， AP5 のバッファ内で長く滞在するため，AP5 以下の AP からのデータパケットの遅延は大きいこと が分かる．一方，ACK パケットについては，シミュレーション時間別に各 AP の ACK パケット の遅延時間を示した図 4.4 のように，AP2 以下の全 AP の遅延時間はほぼ等しい．これは表 4.3 よ り， 大量の ACK パケットを抱える AP2 の hop link1 へ向かうバッファの平均滞在時間は 770 msec と全バッファ中で最も長いのに対し，AP5，AP10，AP15 (hop link2 ∼hop link4) のバッファでは 0.02 msec と小さいことが原因である．従って，ACK パケットの遅延時間の大半はゲートウェイ AP2 のバッファ内での滞在時間で占められ，ACK パケットの遅延時間がほぼ等しくなる． 32 400 AP3 AP4 AP5 AP6 AP7 Data delay time [msec] 350 300 AP8 AP9 AP10 AP11 AP12 AP18 AP19 AP20 AP21 AP22 AP13 AP14 AP15 AP16 AP17 250 200 150 AP3, AP4, AP6, AP7 100 50 0 0 20 40 60 80 100 120 140 160 180 Simulation Time [sec] 図 4.3: データパケットの遅延時間 1200 ACK delay time [msec] 1000 800 600 AP3 AP4 AP5 AP6 AP7 400 AP8 AP9 AP10 AP11 AP12 AP18 AP19 AP20 AP21 AP22 AP13 AP14 AP15 AP16 AP17 200 0 0 20 40 60 80 100 120 Simulation Time [sec] 図 4.4: ACK パケットの遅延時間 33 140 160 180 ACK received interval time [msec] 500 AP3 AP4 AP5 AP6 AP7 400 AP8 AP9 AP10 AP11 AP12 AP18 AP19 AP20 AP21 AP22 AP13 AP14 AP15 AP16 AP17 (1) 300 200 AP3, AP4, AP6, AP7 100 0 0 20 40 60 80 100 120 140 160 180 Simulation Time [sec] 図 4.5: ACK の受信間隔 以上のことから，各 AP のトラヒックが集中することで，hop link1 がボトルネックとなり，ACK パケット，データパケットの到着が遅れることが分かった．これにより，AP5 以下に接続された AP は ACK パケットを受信するまで次のパケットが送出できなくなり，ボトルネック・リンクの帯域に 合わせた送信レートで通信を行う TCP セルフクロッキングが発生する．これにより，AP5 以下の AP のスループットはほぼ等しくなる．この TCP セルフクロッキングの発生の様子をシミュレーショ ン時間別の ACK パケットの受信間隔時間を示した図 4.5 より説明する．図 4.5 中の (1) の部分では， TCP がスロースタートにより通信を開始した結果，輻輳が発生し，ACK の到着が遅れ，ACK の受 信間隔時間が大きくなっている．そして (1) 以降では，ボトルネック・リンクの帯域まで送信レート を下げた結果，輻輳が回避でき，ACK の受信間隔も輻輳発生時よりも短くなる．しかし，図 4.3 よ り確認できたようにデータパケットの遅延が少ない AP3，AP4，AP6，AP7 は，パケットの往復遅 延時間が短く送信レートを下げないため，頻繁にデータを送り ACK パケットを受信する．これによ り，ACK の受信間隔は AP5 以下の AP に比べて小さい． 以上の結果より，有線バックボーンと接続されたゲートウェイの無線リンクがネットワーク全体の 34 ボトルネック・リンクとなり，AP5 以下に接続する AP とそれ以外の AP 間とのスループットに隔 たりが生じることが分かる．よって，ゲートウェイの負荷集中はネットワーク全体の性能に影響を 与えることが分かった．このような現象は，マルチホップ無線 LAN から有線バックボーンへと接続 されるゲートウェイ AP に最も発生しやすいため，ゲートウェイを複数個設置し，使用するゲート ウェイを状況に応じて動的に変更することで改善できると考えられる．よって，有線バックボーンに 接続されるゲートウェイの負荷を軽減するためには，他のゲートウェイに切替えるための指標とアル ゴリズムが必要になる． 35 5 提案手法 本研究では前章の問題点を解決するため，図 5.1 に示すように AP がゲートウェイを動的に切替 えるためのトラヒック制御アルゴリズムを提案する．我々の提案するアルゴリズムでは，各 AP は ネットワーク内にある全てのゲートウェイに対する経路を持ち，状況に応じてゲートウェイを変更す る．このような場合，各 AP が選択しているゲートウェイの状況をどのように判断し，いつ，どれ だけのトラヒック量を切替えるかが重要となる．そこで本研究では，ゲートウェイ AP の負荷を切 替え指標として用い，負荷の算出方法には，過去の送信量と現在の送信量を基に使用帯域を推定する TSW(Time Sliding Window)[15] アルゴリズムを用いた．この切替え指標を基に経路を切替え，ト ラヒックを制御する手法としては，以下に示す 2 つのアルゴリズムを提案する． Destination node Wired Network Multi Hop Wireless Network Gateway 2 Gateway 1 AP STA 図 5.1: 最適なゲートウェイの選択 5.1 低負荷ゲートウェイ選択手法 低負荷ゲートウェイ選択手法は，各 AP が通知されるゲートウェイ AP の負荷のみを指標として 全トラヒックの経路を切替える手法である．パケットを送出する AP は，デフォルト経路を使用した 場合と異なる経路表を使用した場合のそれぞれについて，ゲートウェイ AP の負荷を比較し，ゲート 36 ウェイの負荷が低い方の経路を使用する．これにより，負荷の変化に応じた経路 (ゲートウェイ) の 切替えが可能となる．なお，ゲートウェイ AP が負荷情報を Probe Response 及び Beacon フレー ムに追加し，各 AP がそれらの制御フレームにこの情報を付加することで，各 AP はゲートウェイ AP の負荷を知ることが出来る． 5.2 フロー分割手法 フロー分割手法は，低負荷ゲートウェイ選択手法のように AP から送出される全トラヒックの経 路を切替えるアプローチではなく，ゲートウェイからの情報を基にフロー単位で段階的に経路を切替 え，トラヒック負荷を緩やかに分散することを目的としている．ゲートウェイ GWi からの情報とし ては，1) 到達までのホップ数 hi ，2) ゲートウェイ AP の負荷 li の 2 つである．なお，1) の情報に ついては通信を行う前に得られ，2) の情報は定期的に更新されるものとする．今回はこの更新間隔 を T とし，40 msec とした．各 AP では情報が更新される度に，経路表の切替え (ゲートウェイ AP の変更) を行うかどうかを判断する．また 1) の情報については，通常使用する経路と輻輳時使用す る経路との間で，hi の差が大きい場合がある．一般的に経験ホップ数が多い程，送信権を競合する 機会が多いと考えられるため，本提案手法では経路表の切替え前後のホップ数に差が少ない AP か ら順次経路を切替え，輻輳を緩和していく方法を採用した．このため，各 AP の経路切替えの判断 間隔は n × T とし，変数 n は式 (5.1) に従う． n = (h2 − h1 )2 (但し，h2 > h1 ) (5.1) そして，経路の切替えを判断する AP は，選択可能なゲートウェイの負荷を比較する．このとき， 通常使用するゲートウェイ GW1 の負荷 l1 と輻輳時使用するゲートウェイ GW2 の負荷 l2 の比率 α = l1 /l2 が β 以上に達していれば，経路を切替える．但し，全てのトラヒックの経路を切替えるの ではなく，現在送出しているフローの ρ % を GW2 に送出し，残りのフローは引続き GW1 を使用す る．そして再びゲートウェイの情報が更新されたとき，ゲートウェイ負荷の比率 α が依然として β 倍以上であれば，GW1 を使用しているフローの割合を δ % 減らし，GW2 に送出するフローの割合 を δ % 増やす．逆に，負荷の比率が β 倍以下に抑えられていれば，GW2 へ送出するフローの数を δ % 減らし，デフォルト経路の使用率を増加させていく．但し，GW2 が逆に輻輳するような負荷比 率 α < 1/β の場合は全フローを GW1 に変更する．以上のゲートウェイの負荷の比率と経路を変更 37 するフロー数の割合の関係を式 (5.2) に示す．なお，本稿では β = 2.0，ρ = 50，δ = 10 とした． Initially : 全フロー中のデフォルト経路使用率，Dr0 = 1.0 情報更新数，i = 0 Stationary : i= i+1 ρ Dr(i−1) − δ % D ri = 1.0 Dr(i−1) + δ % if ( α > β && Dr(i−1) == 1.0) if ( α > β) (5.2) if ( α < 1 ) β if ( α < β && Dr(i−1) <= 1.0) 38 6 提案手法の有効性 本章では，シミュレーションによる提案手法と既存手法の比較を行い，提案手法の有効性を示す． 6.1 シミュレーション環境 Wired link : Wired link Rate : 100 Mb/s Delay : 0.001 msec Protocol : 802.3 dst 1 Wireless link Rate : 54 Mb/s Protocol : 802.11a : 5.18 GHz (36ch) : 5.30 GHz (60ch) : 5.28 GHz (56ch) host1 dst 1 next 2 : 5.24 GHz (48ch) : 5.22 GHz (44ch) : 5.20 GHz (40ch) next 3 AP7 AP4 dst 1 dst 1 AP 2 next 4 next 1 AP 3 AP6 dst 1 next 1 dst 1 AP8 next 2 dst 1 next 3 AP5 default route : secondary route : AP4 : AP5 : AP6 : AP7 : AP8 : dst x AP4 AP5 AP6 AP7 AP8 x : destination node y : next hop to destination next y -> -> -> -> -> AP7 AP6 AP8 AP4 AP6 -> -> -> -> -> AP3 AP8 AP3 AP2 AP5 -> -> -> -> -> host1 AP3 -> host1 host1 host1 AP2 -> host1 図 6.1: 実験トポロジ 図 6.1 に今回の実験に使用したトポロジを示す．なお，本研究では，チャネル割り当てとルーティ ングは事前のサイトサーベイ等によって構成済みであると想定する．各 AP が使用する経路とチャ ネルは図 6.1 中に示す．図 6.1 中の矢印で示した default route(デフォルト経路) とは通常利用する経 路で，secondary route(セカンダリ経路) とは輻輳時に使用する経路である．デフォルト経路は送信 39 先までのホップ数を基に決定された最短経路とした．セカンダリ経路で選択するゲートウェイは，デ フォルト経路で選択されたゲートウェイ以外とし，その経路はゲートウェイまでの最短経路とした． 図 6.1 中の各 AP の使用チャネルについては，各チャネル毎に無線 LAN インタフェースを一つ持つ ものとした．また，図 6.1 中の各 AP には STA が接続しており，全ての STA は host1 に向かって TCP/Sack オプションで通信を行うものとした．但し，ゲートウェイ AP である AP2，AP3 は中継 専用の AP と仮定し，STA は接続しないものとした．なお，各 STA が送出するパケットサイズは 1500 Byte とし，シミュレーション時間は 3 分間とした．また，AP と STA 間のエラーは考えず， 1 フローにつき 1 台の STA が通信中であると仮定し，1 フローあたりのトラヒックモデルとしては 実際のトラヒック量をモデルとした非 Greedy なファイル転送 [16] を想定した．なお，本研究では 非 Greedy 転送の通信モデルの通信期間と非通信期間は参考文献 [16] より以下のように定義する． • 通信期間 – ランダムなサイズのファイル転送が完了するまでとする．ここでのランダムサイズとは， パレート分布に従うものとし，その平均ファイル長を UNIX の TCP 通信で用いられる 平均ファイル長が 47 KBytes とした． • 非通信期間 – 指数関数に従うランダムな時間とする．平均非通信期間は 3.2 sec とする． また，STA の配置については，STA が各 AP に均一に配置されるパターン 1，STA が一部の AP に集中するパターン 2 の 2 つの状況を想定した． パターン 1 : STA が各 AP に均一に配置 ・ STA が各 AP に 20 台ずつ配置された場合について評価した． パターン 2 : STA が一部の AP に集中 ・ ゲートウェイ AP2 へ 接続する AP に STA が集中した場合 (パターン 2 (i) ) と，ゲート ウェイ AP3 へ 接続する AP に STA が集中した場合 (パターン 2 (ii) ) のそれぞれにつ いて評価を行った．合計 100 台の STA を負荷が集中しているゲートウェイ AP を選択 している AP に 90 台，集中していないゲートウェイ AP を選択している AP に 10 台， それぞれランダムに配置した場合を評価した． 40 なお，各実験パターンの試行回数は 20 回とし，各評価指標の平均値を算出した． 評価指標としては，全 AP の総獲得スループット，全 AP 中の最小スループット，AP 間の BI (Blance Index)，AP ごとのデフォルト経路の使用率を用いる．ここで BI とは，式 (6.1) で表され る β の値であり，1 に近づくほど均衡を，1/N に近づくほど不均衡を表す指標である． β= ( X Bi )2 /(N × X Bi2 ) (6.1) 但し，Bi は APi の平均スループット，N は AP 数を表す. 以上の環境において，既存手法である デフォルト経路のみを使用した場合と，提案手法となる低負荷ゲートウェイ選択手法とフロー分割手 法とを比較し評価を行った． 6.2 結果・考察 以下に，前節で述べたシミュレーション環境を基に得られたパターン 1 とパターン 2 の結果を示す． 6.2.1 パターン 1 の結果と考察 まず，パターン 1 における各ゲートウェイ AP (AP2，AP3) の負荷の変動を示した図 6.2 と 図 6.3 より，各手法の経路切替えの特徴を述べる．図 6.2 と図 6.3 は，シミュレーション時間別の負荷変 動を示し，各図中の “flow dvision” はフロー分割手法，“select lower gateway” は低負荷ゲートウェ イ選択手法，“default” はデフォルト経路のみ使用した場合を示している． 41 Network Load [ MBytes/sec ] 6.0 flow dvision select lower load default 5.0 4.0 3.0 2.0 1.0 0 0 20 40 60 80 100 120 140 160 180 Simulation Time [sec] 図 6.2: ゲートウェイ AP2 での負荷の変動 (パターン 1) Network Load [ MBytes/sec ] 6.0 flow division select lower gateway default 5.0 4.0 3.0 2.0 1.0 0 0 20 40 60 80 100 120 140 Simulation Time [sec] 図 6.3: ゲートウェイ AP3 での負荷の変動 (パターン 1) 42 160 180 30 Number of TCP Flow 25 20 15 10 5 0 0 20 40 60 80 100 120 140 160 180 Simulation Time [sec] 図 6.4: パターン 1 のフロー数の変動 まず，図 6.2 と 図 6.3 について，シミュレーション時間に応じて負荷が上下に変動していること が分かる．これは，ネットワーク内の TCP フロー数が定義したトラヒックモデルに応じて図 6.4 の ように変動するため，フロー数が多く発生するシミュレーション時間帯 (40 ∼60 sec の間など) に 各ゲートウェイの負荷が高まるためである．また，図 6.2 と図 6.3 を比較したとき，図 6.3 の方が負 荷の変動が少ない．これは，ゲートウェイ AP2 には AP が 3 台 (AP4，AP5，AP6) 接続されてい るのに対し，ゲートウェイ AP3 には AP が 2 台 (AP7，AP8) 接続されているため，ゲートウェイ AP3 のトラヒック量は AP 1 台分少なくなり，図 6.3 の負荷変動が小さくなるためである． 以上の結果を踏まえ，既存手法であるデフォルト経路のみを使用した場合について述べる．デフォ ルト経路のみを使用した場合，トラヒックを制御できないため，図 6.2 のゲートウェイ AP2 に及ぼ す負荷については，他の 2 つの手法と比較して常に大きく，一方，図 6.3 のゲートウェイ AP3 に及 ぼす負荷については常に小さい．このように，デフォルト経路のみを使用した場合は，ゲートウェイ AP2 と AP3 の負荷が均一にならないことが分かる． 次に，低負荷ゲートウェイ選択手法について，図 6.2 と 図 6.3 の負荷の変動に差は殆どなくほぼ 同一であることが分かる．また，接続 AP 数が多い図 6.2 では，デフォルト経路のみの場合よりも負 43 荷を低く抑えていることから，低負荷ゲートウェイ選択手法はゲートウェイ負荷を効率良く分散して いるように見える．しかし，低負荷ゲートウェイ選択手法はゲートウェイ負荷のみを指標としている ため，ゲートウェイの負荷が比較的低い場合でも，他方のゲートウェイの負荷がそれより低ければ経 路を切替え，常に負荷分散を行おうとする．この結果，図 6.2 については，負荷の集中していない時 間帯でフロー分割手法よりも負荷が高い場合が多く，接続 AP 数の少ない図 6.3 については，他の 手法と比較して負荷が最も高い場合が多い．このように，低負荷切替え手法では，頻繁に経路を切替 えることで切替え先となるゲートウェイ AP の負荷を過度に高めることが分かる． 最後にフロー分割手法については，これまで述べたデフォルト経路のみを使用した場合と，低負 荷切替え手法の両方の特徴を持つ．例えば，図 6.2 でのシミュレーション時間が 40 ∼ 60 sec の場合 のように，負荷の集中する時間帯ではトラヒックをフロー単位で制御することができるため，デフォ ルト経路のみの場合より負荷を軽減することができる．ここで，フロー分割手法は切替え先となる AP に負荷を与えないように緩やかに TCP フローを切替えるため，図 6.2 に示す負荷の集中する時 間帯 (40 ∼ 60 sec など) では，負荷の分散度合が一時的に低負荷ゲートウェイ選択手法よりも低く なるが，図 6.3 より，低負荷ゲートウェイ選択手法のように切替え先 AP の負荷を大きく高めること はない．従ってフロー分割手法は，図 6.2，図 6.3 より，低負荷ゲートウェイ選択手法よりも負荷が 低い場合が多い． 以上のことから，提案手法はトラヒックを制御することでゲートウェイ負荷を分散させることが可 能であり，特に，フロー分割手法は効果的に負荷を分散させることが分かった． 44 ここで，パターン 1 についてのスループット特性を示した表 6.1 より，各手法の性能を評価する． 表 6.1 より，デフォルト経路のみ使用した場合と低負荷ゲートウェイ選択手法とを比較したとき，改 善は見られなかった．これより，低負荷ゲートウェイ選択手法では，ゲートウェイの負荷分散は達成 できるが，STA ごとの個別の TCP スループット特性は改善できないことが分かる．実際に，図 6.2， 図 6.3 を比較したときにゲートウェイの負荷変動はほぼ等しく，ゲートウェイ間の負荷分散は達成さ れている．更に，各実験パターンにおける AP ごとのデフォルト経路使用率を示した表 6.2 より，各 AP のデフォルト経路使用率がそれぞれ約 50 % であることからも，ゲートウェイの負荷分散が確認 できる．しかし低負荷ゲートウェイ選択手法は，現在利用しているゲートウェイまで 1 ホップに位 置する AP でも，常に負荷の低いゲートウェイを選択する．このような場合の AP からの TCP フ ローは，マルチホップ無線 LAN 特有の問題であるホップ数に伴う送信権競合の増加により，通信性 能が劣化する．このように，低負荷ゲートウェイ選択手法では，単純にゲートウェイの負荷のみを指 標としてゲートウェイを切替えるため，個別の TCP スループット特性を改善することはできない． 一方，フロー分割手法では，既存手法と比較して，総スループットを約 2.0 Mb/s，最小スループッ トを約 400 Kb/s 改善している．これは，フロー分割手法ではホップ数による通信性能低下を考慮し， デフォルト経路とセカンダリ経路のホップ数の差が少ない AP から順に切替えることで，ホップ数の 影響を受けにくい AP の TCP から切替えることができるためである．これにより，切替えた TCP フローの性能低下を防ぎつつ改善をはかることができる．また，これらの TCP フローがゲートウェ イを切替えたことで，負荷が分散され，デフォルト経路を利用している TCP フローの性能も改善さ れる．従って，フロー分割手法では個別の TCP スループット性能を改善することができる．また負 荷分散の度合については，図 6.2，図 6.3 より，一時的に低負荷ゲートウェイ選択手法よりも低いが， 経験ホップ数を考慮してトラヒックをフロー単位で緩やかに制御するため，切替え先となるゲート ウェイの負荷を大きく高めることはない．これは，表 6.2 より，各 AP はデフォルト経路を低負荷 ゲートウェイ選択手法よりも約 30 ∼ 40 %多く使用することになるが，協調してゲートウェイを使 用できるため，各 AP 間の使用率の隔たりが少ないことからも分かる．従って，フロー分割手法で は，各 AP が効率良く経路を選択することでネットワーク全体の資源を有効に利用できることが分 かった． 45 表 6.1: STA を各 AP に均一に配置した場合 (パターン 1) 手法 Blance Index 総スループット 最小スループット [Mb/s] [Mb/s] デフォルト経路 15.88 2.65 0.983 低負荷ゲートウェイ選択 15.46 2.44 0.979 フロー分割 17.79 3.02 0.962 表 6.2: 各実験パターンにおける AP ごとのデフォルト経路使用率 低負荷ゲートウェイ選択手法でのデフォルト経路使用率 [%] AP パターン 1 の場合 パターン 2 の場合 AP2 に負荷が集中 AP3 に負荷が集中 AP4 51.26 50.23 55.99 AP5 55.03 55.44 63.92 AP6 54.05 51.83 64.20 AP7 52.88 57.31 49.45 AP8 54.97 59.65 49.08 フロー分割手法でのデフォルト経路使用率 [%] AP4 84.72 63.35 99.75 AP5 88.15 75.99 100 AP6 88.80 65.84 100 AP7 97.31 100 62.07 AP8 96.88 100 72.26 46 6.2.2 パターン 2 の結果と考察 まず，パターン 2 (i)，(ii) における各ゲートウェイ AP の負荷の変動を示した図 6.5 ∼ 図 6.8 よ り，各手法の経路切替えの特徴を述べる はじめにパターン 2 (i) で，負荷の集中しているゲートウェイ AP2 の負荷を示す図 6.5 と，負荷 の集中していないゲートウェイ AP3 の負荷を示す図 6.6 について述べる． 既存手法のデフォルト経路のみの場合について，図 6.5 と図 6.6 を比較すると，既存手法ではゲー トウェイを動的に切替えて負荷を分散することができないため，ゲートウェイ負荷に大きな差がある ことが分かる．一方，図 6.5 での各提案手法は，負荷を分散することができるため，デフォルト経路 のみ使用した場合よりも負荷が低いことが分かる． ここで，低負荷ゲートウェイ選択手法については，図 6.5 と図 6.6 の変動がほぼ同じであることが 分かる．これは，常に負荷の低いゲートウェイを選択することで，両ゲートウェイの負荷を均一にす るためである．しかしその結果，図 6.6 より，切替え先である負荷の集中していない AP3 の負荷を 過度に高めるため，他の手法と比較して最も負荷が高い．一方，フロー分割手法については緩やか に負荷を分散するため，図 6.5 より，トラヒック量が多くなる時間帯では一時的に低負荷ゲートウェ イよりも負荷分散の度合が低くなるが，切替え先の AP を過度に輻輳させることがないため，図 6.6 では，低負荷ゲートウェイ手法よりも負荷を低く抑えることができる． 次に，パターン 2 (ii) の結果を示した図 6.7，図 6.8 について述べる．デフォルト経路のみ使用し た場合については，パターン 2 (i) と同様に負荷の集中していないゲートウェイ AP 2 と負荷の集中 しているゲートウェイ AP3 との負荷の差が大きいことが分かる．ここで，上述のパターン 2 (i) で は，STA の集中する AP が AP4，AP5，AP6 の 3 台であったのに対し，パターン 2 (ii) では AP7， AP8 の 2 台になるため，各提案手法の経路を切替えるトラヒックの制御量が，負荷の低い切替え先 ゲートウェイ AP2 の負荷に及ぼす影響は大きい．このため，経路を切替えるトラヒック量を考慮し ない低負荷ゲートウェイ選択手法は，図 6.8 より，負荷の集中するゲートウェイ AP3 の負荷を軽減 することができるが，図 6.7 では逆に負荷の低いゲートウェイ AP2 の負荷を大きく高める結果とな る．一方，フロー分割手法では経路を切替えるトラヒック量を制御できるため，図 6.7，図 6.8 より， 負荷の低いゲートウェイ AP2 の負荷を大きく高めることはなく，負荷分散を達成することができる． 47 Network Load [ MBytes/sec ] 6.0 flow dvision select lower load default 5.0 4.0 3.0 2.0 1.0 0 0 20 40 60 80 100 120 140 160 180 Simulation Time [sec] 図 6.5: ゲートウェイ AP2 での負荷の変動 ( パターン 2 (i) ) Network Load [ MBytes/sec ] 6.0 flow dvision select lower load default 5.0 4.0 3.0 2.0 1.0 0 0 20 40 60 80 100 120 140 160 Simulation Time [sec] 図 6.6: ゲートウェイ AP3 での負荷の変動 ( パターン 2 (i) ) 48 180 Network Load [ MBytes/sec ] 6.0 flow dvision select lower load default 5.0 4.0 3.0 2.0 1.0 0 0 20 40 60 80 100 120 140 160 180 Simulation Time [sec] 図 6.7: ゲートウェイ AP2 での負荷の変動 ( パターン 2 (ii) ) Network Load [ MBytes/sec ] 6.0 flow dvision select lower load default 5.0 4.0 3.0 2.0 1.0 0 0 20 40 60 80 100 120 140 160 Simulation Time [sec] 図 6.8: ゲートウェイ AP3 での負荷の変動 ( パターン 2 (ii) ) 49 180 表 6.3: STA が一部の AP に集中した場合 (パターン 2) (i) ゲートウェイ AP2 に集中した場合 手法 Blance Index 総スループット 最小スループット [Mb/s] [Mb/s] デフォルト経路 14.38 1.00 0.759 低負荷ゲートウェイ選択 15.46 2.44 0.962 フロー分割 18.05 2.89 0.976 (ii) ゲートウェイ AP3 に集中した場合 デフォルト経路 18.10 1.77 0.907 低負荷ゲートウェイ選択 12.06 1.24 0.725 フロー分割 18.32 2.88 0.980 次に，パターン 2 についてのスループット特性を示した表 6.3 より，各手法の性能を評価する．ま ず，表 6.3 中の (i) ゲートウェイ AP 2 を選択している AP (AP4，AP5，AP6) に負荷が集中した場 合について述べる．デフォルト経路のみ使用した場合に比べ，低負荷ゲートウェイ選択手法は総獲 得スループットを約 1.0 Mb/s，BI を約 0.2，最小スループットを約 1.4 Mb/s，パターン 1 の場合 よりも改善できた．これは図 6.5 より，負荷が一部の AP に集中したことで，セカンダリ経路の利 用による負荷分散の効果がパターン 1 の場合よりも顕著に現れたためである．しかし，図 6.6 より， 負荷の集中していないゲートウェイ AP3 の負荷が他の手法と比べて最も高いことが分かる． 一方，フロー分割手法でも同様に総獲得スループットを約 3.0 Mb/s，BI を約 0.2，最小スルー プットを約 1.8 Mb/s，改善できた．これは，フロー分割手法では，負荷の集中していない AP (AP7， AP8) での経路切替えや，デフォルト経路よりも経験ホップ数が増加する AP5 での経路切替えなど を避け，効率的な経路制御を実現しているためである．実際に表 6.2 より，負荷が集中していない AP7，AP8 が全くセカンダリ経路を使用していないことと，負荷が集中している AP4，AP5，AP6 の内，セカンダリ経路へのホップ数が他よりも多い AP5 のセカンダリ経路の使用率が AP4，AP5 と比べて低いことが分かる．このためフロー分割手法は，図 6.6 より，大半のトラヒックの切替え先 となるゲートウェイ AP3 の負荷を低負荷ゲートウェイ選択手法よりも軽減することができる．この 50 ように，フロー分割手法は負荷を緩やかに分散することができ，低負荷ゲートウェイ選択手法よりも 改善効果が大きい． 次に，表 6.3 の (ii)AP3 に接続する AP7，AP8 に負荷が集中した場合について述べる．ここで， デフォルト経路のみ利用した場合の結果は，接続 STA 台数が偏っているにも関わらず，パターン 1 よりも総スループットが約 3.0 Mb/s 高いことが分かる．これは，STA が集中していない AP4， AP5，AP6 が少数のフローでゲートウェイ AP2 の資源を独占したため，AP4，AP5，AP6 の獲得ス ループットが増加し，全体の総獲得スループット量を押し上げたためである．一方，STA が集中する AP7，AP8 ではスループット特性が劣化するため，スループット差は大きくなり，最小スループッ ト，BI はパターン 1 より小さくなった．従って，今回の実験パターンでは，負荷が集中する AP7， AP8 のトラヒックをどのように制御するかが，ネットワーク全体での負荷分散を達成する上で重要 となる．しかし，低負荷ゲートウェイ選択手法では，AP から送出される全トラヒックの経路を切替 えてしまうため，AP7，AP8 から送出される大量のトラヒックをそのまま負荷の低いゲートウェイ に集中させてしまう．その結果，選択した先のゲートウェイ AP の負荷を過度に高めるという特徴が 顕著に現れ，ゲートウェイ AP への負荷集中が頻繁に起こり，性能改善が得られなかった．この様 子は，図 6.7，図 6.8 より，ゲートウェイ AP3 の負荷を軽減する代わりにゲートウェイ AP2 の負荷 を高めたため，既存手法とは逆にゲートウェイ AP2 の負荷が高くなることより確認できる．一方， フロー分割手法では，総スループットを約 200 Kb/s，最小スループットを約 1.0 Mb/s，改善するこ とができた．ここで，表 6.3 中 (i) の場合よりも改善が小さいのは，負荷が集中する AP7，AP8 が デフォルト経路よりも経験ホップ数の増加するセカンダリ経路の使用を控えたためである．しかしそ の結果，図 6.7 より，大半のトラヒックの切替え先となるゲートウェイ AP2 の負荷を，低負荷ゲー トウェイ選択手法よりも高めることなく負荷分散を達成することができるため，既存手法，低負荷 ゲートウェイ選択手法と比べてスループット特性を改善することができた． 51 7 まとめ 本研究では，まず，有線ネットワークをバックボーンとした大規模なマルチホップ無線 LAN にお いて，バックボーンと接続するゲートウェイへの負荷集中が TCP スループット特性に及ぼす影響を 調査した．その結果，負荷が集中するゲートウェイにネットワーク全体のボトルネック・リンクが発 生し，接続する端末の TCP 通信性能を著しく劣化させることが分かった．この問題を改善するため には，ゲートウェイを複数個設置し，ゲートウェイを動的に切替える手法が必要となる．しかし既存 の経路制御機構では，最短経路上にある単一のゲートウェまでの経路しか把握できない上に，ゲー トウェイを動的に切替えることができない．そこで，我々は複数ゲートウェイ環境下で，負荷が集中 していないゲートウェイへ経路が切り替わるようにトラヒックを動的に制御する手法を提案し，シ ミュレーションによる評価を行った．このトラヒック制御手法は，各 AP がマルチホップ無線 LAN 内の全てのゲートウェイに対する経路を持ち，ゲートウェイの負荷状況に合わせて動的に経路を切替 えるアルゴリズムである．そのアルゴリズムとしては，ゲートウェイの負荷状況を指標として全フ ローの経路を切替える「低負荷ゲートウェイ選択手法」とゲートウェイからの情報を基に，経路の切 替えを行うトラヒックの量を制御し，緩やかに負荷を分散させる「フロー分割手法」の 2 つを提案 し，シミュレーションによる評価を行った．その結果，提案手法である低負荷ゲートウェイ手法，フ ロー分割手法により，ゲートウェイの負荷を分散できることが分かった．しかし，低負荷ゲートウェ イ選択手法ではゲートウェイの負荷のみを指標とし，ホップ数の増加に伴う送信権競合回数の増加を 考慮しないため，TCP スループット特性を改善することができなかった．一方，フロー分割手法に ついては，ゲートウェイのホップ数を考慮しながら緩やかに負荷を分散させるため，低負荷ゲート ウェイ選択手法よりも負荷分散の度合は低いが，切替え先のゲートウェイを輻輳させることなく効率 の良い経路切替えを実現できる．このため，フロー分割手法は既存手法である最短経路長によるゲー トウェイ選択手法よりも総スループット及び公平特性の点で改善できることが分かった． 以上より，本研究で提案したゲートウェイ選択手法は，複数ゲートウェイを持つマルチホップ無線 LAN で，既存手法の通信性能を著しく改善できることが分かった． 52 8 謝辞 本研究を進めるにあたり適宜，適切な御指導をくださいました尾家 祐二教授に心より感謝を申し上 げます．また，ゼミや論文に対して有益な御意見を頂きました川原 憲治助教授，鶴 正人助教授，池 永 全志助教授に厚く御礼申し上げます．さらに，本研究に対して熱心に御指導下さいました福田 豊 助手に厚く御礼申し上げます．また，様々な面で御協力くださいました尾家研究室，川原研究室，鶴 研究室の皆様，並びに竹村 眞奈美事務補佐員，吉木 智絵事務補佐員に心から御礼申し上げます． 53 参考文献 [1] 松江 英明 守倉 正博，802.11 高速無線 LAN 教科書，株式会社 IDG ジャパン, 初版第 2 刷，2003 年 7 月 29 日 [2] J. Jun, and M.L. Sichitiu: “The Nominal Capacity of Wireless Mesh Networks,” IEEE Wireless Communications, vol.10, Oct. 2003. [3] C-K. Toh，アドホックモバイル ワイヤレスネットワーク - プロトコルとシステム-，共立出版， 初版第 1 刷．2003 年 5 月 31 日 [4] A. Raniwala, and T. Chiueh: “Architecture and Algorithm for an IEEE 802.11-Based MultiChannel Wireless Mesh Network,” IEEE INFOCOM, March. 2005. [5] I.F. Akylidiz, X. Wang, and W. Wang:“Wireless mesh networks: a survey,” Computer Networks Journal (Elsevier), vol. 47, March. 2005. [6] F. Cail, M. Conti, and E. Gregori: “Dynamic tuning of the IEEE 802.11 protocol to acheive a theoretical throughput limit,” IEEE/ACM Transcations on Networking, August. 2000. [7] B. Raman, and K. Chebrolu: “Revisiting MAC Design for an 802.11-based Mesh Network,” HotNets-III, Nov. 2004. [8] J. So, and N. Vaidya: “Multi-channel MAC for ad hoc network: handling multi-channel hidden terminals using a single transceiver,” ACM MOBI-HOC, May. 2004. [9] A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhou: “A multi-radio unification protocol for IEEE 802.11 wireless network,” BroadNets, 2004. [10] Status of Project IEEE 802.11s ESS Mesh Networking. Available from: http://grouper.ieee.org/groups/802/11/Reports/tgs_update.htm [11] J.Hauser, Draft PAR for IEEE 802.11 ESS Mesh, IEEE Document Number: IEEE 802.1103/759r2 [12] Firetied Netowrks. Available from: www.firetied.com 54 [13] Y. Kishi, K. Tabata, T. Kitahara, Y. Noishiki, A. Idoue, and S. Nomoto: “Wireless Node Architecture and Its Implementation for Multi-Hop Mesh Networks in IP-Based Broadband Fixed Wireless Access System,” IEICE TRANS.COMMUN, vol. E88-B, no. 3, March. 2005. [14] V. Kawadia, and P.R. Kumar: “Experimental Investigations into TCP Performance over Wireless Multihop Networks,” ACM SIGCOMM, August. 2005. [15] D.D. Clark and W. Fang : “Explicit Allocation of Best-effort Packet Delivery Service,” IEEE/ACM Transactions on Networking, vol.6, no.4, August. 1998. [16] Y. Sumida, H. Ohsaki, M. Murata, H. Miyahara : “Effects of Upper-Layer Protocols on SelfSimilarity of Network Traffic,” The IEICE Transactions on Communications, B-I vol. J81-B-I No. 8 pp. 1-9 August. 1998. 55