18 LAN AP (AP, Access Point) LAN (STA, Station) (RSSI, Received Signal Strength Indicator) AP AP STA AP LAN AP STA LAN AP LAN LAN STA AP LAN (Local Ar

全文

(1)修士学位論文. 題目. 無線 LAN メッシュネットワークにおける AP 選択. – 情報共有と自律分散選択 –. 指導教官尾家祐二教授. 報告者大薮赳. 平成 19 年 2 月 16 日. 九州工業大学大学院情報工学研究科情報システム専攻.

(2) 平成 18 年度修士学位論文無線 LAN メッシュネットワークにおける AP 選択. – 情報共有と自律分散選択 – 大薮赳. 内容梗概通信容量の増強や設置の容易さなどの利点から，複数のアクセスポイント (AP, Access Point) を相互に無線で接続して構築する無線 LAN メッシュネットワークが注目されている．しかし，現在用いられている既存手法では各端末 (STA, Station) は受信電波強度 (RSSI, Received Signal Strength. Indicator) のみに基づいて接続先の AP を決定するため，無線資源の利用効率や公平性が低下するという問題が生じる．我々はこのような AP 選択問題について，自 STA のスループットを最大化するように AP を選択する手法を提案し，シングルホップ無線 LAN 環境で無線資源を有効かつ公平に利用できることを明らかにした．しかし，この提案手法では，AP と STA 間のみを無線リンクで接続するシングルホップ無線 LAN 環境を想定しており，AP 間も無線リンクで接続する無線 LAN メッシュネットワーク環境については考慮していない．そこで本稿では，無線 LAN メッシュネットワーク環境において STA が自律的に AP を選択する手法を提案し，その効果をシミュレーションにより明らかにする．. 主な用語無線 LAN (Local Area Network) ，メッシュネットワーク，AP (Access Point) 選択，自律分散，公平性，ボトルネック.

(3) 目次 1. はじめに. 1. 2. 無線 LAN の概要. 3. 2.1. プロトコル構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 3. 2.2. 無線 LAN 規格 (IEEE 802.11a/b/g) . . . . . . . . . . . . . . . . . . . . . . . . . . .. 4. 2.3. MAC 層 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 5. 2.3.1. CSMA/CA 方式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 5. 2.3.2. IFS による優先制御 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 6. 2.3.3. 隠れ端末問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 7. 2.3.4. RTS/CTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 8. 2.3.5. スキャニング機能 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9. ネットワークトポロジ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 9. 2.4.1. インフラストラクチャモード. . . . . . . . . . . . . . . . . . . . . . . . . . .. 9. 2.4.2. アドホックモード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 10. 2.4.3. 無線ディストリビューションシステム (WDS : Wireless Distribution System). 10. メッシュネットワーク . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 11. 2.5.1. . . . . . . . . . . . . . . . . . . . . . . . . . .. 11. 無線 LAN の現状とその問題点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 14. 2.4. 2.5. 2.6 3. 4. メッシュネットワークの特徴. 提案 AP 選択手法. 15. 3.1. MLT アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 15. 3.2. MLT-M アルゴリズム. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 16. 3.3. MLTAB アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 17. 3.4. リンク監視機構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 19. 評価方法. 21. 4.1. シミュレーションモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 21. 4.1.1. 21. MLT-M のシミュレーションモデル . . . . . . . . . . . . . . . . . . . . . . .. i.

(4) 4.1.2 4.2 5. 23. 評価指標 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 24. 結果と考察. 26. 5.1. MLT-M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 26. 5.1.1. 全体に分布する場合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 26. 5.1.2. 分布が偏った場合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 27. 5.1.3. 分布が極端に偏った場合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 28. 5.1.4. ホップ数が増加した場合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 31. MLTAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 32. 5.2.1. STA が 11b を用いる場合 . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 32. 5.2.2. STA が 11g を用いる場合. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 34. 5.2.3. ボトルネックリンクの影響が大きい場合 . . . . . . . . . . . . . . . . . . . .. 38. 5.2.4. STA 数を増やした場合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 40. 5.2. 6. MLTAB のシミュレーションモデル . . . . . . . . . . . . . . . . . . . . . . .. 43. まとめ. 謝辞. 44. 参考文献. 45. ii.

(5) 1. はじめに近年，場所にとらわれない柔軟な導入が可能で，かつ高速な通信を提供可能な IEEE802.11 に準拠. した無線 LAN [1] の普及が進んでいる．これに伴い，通信容量の増強や通信範囲の拡大のために大規模な無線ネットワークを構築したいという要求が高まっている．しかし，1 台の AP (Access Point) が提供する通信範囲は数 10 m 程度と狭く，その通信容量も限られるため，複数の AP を利用した大規模な無線 LAN の構築が行われている．このような無線ネットワークでは，AP 間を結ぶバックボーンネットワークは有線で接続することが多い．しかし，有線 LAN を新たに敷設するのは一般的にコストがかかり，また建物によってはイーサネットケーブルの敷設が困難な場合もある．そこで AP を相互に無線で接続しメッシュ状に配置した無線 LAN メッシュネットワークを構築することで，低コストかつ高速な通信を提供できると期待されている．無線 LAN メッシュネットワークは，国際標準化団体 IEEE (Institute of Electrical and. Electronic Engineers) の 802.11s ワーキンググループで標準化活動が行われており，既存の 802.11 の MAC (Media Access Control) 層，物理層をベースに機能の追加が検討されている [2] [3]．このようなネットワークでは，AP は端末 (STA，Station) から送信されたデータを中継することで，STA 間や外部ネットワークとの通信を提供する．一方で，このように AP が複数存在する無線 LAN で，各 STA が外部ネットワークもしくは他の. STA と通信を確立するためには，各 STA は接続する AP を適切に選択する必要がある．しかし，既存方式では各 STA は RSSI (Received Signal Strength Indicator : 受信電波強度) のみに基づいて接続先の AP を決定する [4]．よって，複数の AP が配置されてはいても，特定の AP の近くに STA が偏在するような場合は，それらの STA はすべて RSSI が強い近くの AP に接続してしまい，AP 間の接続 STA 数に偏りが生じる．その結果，端末が特定の場所に偏りやすいホテルのロビーや駅構内，展示会場といった実際の使用環境では，既存手法 (RSS, Received Signal Strength) では無線資源を有効かつ公平に利用できないことが報告されている [5] [6]．先行研究ではその解決手法として，STA にとって最も高いスループットを期待できる AP を選択する MLT(Maximizing Local Throughput) アルゴリズムと，そのアルゴリズムに従って動的に AP を選択する機構を提案し，無線資源を有効かつ公平に利用できることを明らかにした [7] [8]．しかし，この提案手法は，AP 同士が全て有線で接続される従来のシングルホップ無線 LAN を想. 1.

(6) 定しており，AP 同士が無線で接続された無線 LAN メッシュネットワークについては考慮していない．そのため，スループットが最大になると期待して接続した AP の無線 LAN メッシュネットワーク内の経路上に，パケットロスが頻繁に発生するリンクや，輻輳が発生しているリンクが存在すると，期待したスループットを獲得することができず，無線資源を有効かつ公平に利用することができない可能性がある．そこで本研究では AP と STA 間だけの情報を用いる従来の MLT を無線 LAN メッシュネットワークに対応する目的で拡張し，チェーントポロジの無線 LAN メッシュネットワークにおいて，AP-AP 間の PER(Packet Error Rate) 情報を利用した AP 選択手法を提案し，通信特性を改善できることを示す．また，さらに検討を進め，より一般的なトポロジの無線 LAN メッシュネットワークを対象として，AP 網に生じるボトルネックリンクの情報を利用した AP 選択アルゴリズムを提案し，その手法の有効性をシミュレーションにより明らかにする．本稿では，まず 2 章にて無線 LAN の概要を述べ，3 章で提案手法について説明する．次に 4 章では本研究で行った評価方法について述べ，5 章ではシミュレーション結果を示すとともに考察を行う．最後に 6 章で本稿をまとめる．. 2.

(7) 2. 無線 LAN の概要無線 LAN は，IEEE (Institute of Electrical and Electronics Engineers) によって，1997 年に. 「IEEE802.11」として規格化された．その後，物理レイヤの高速化が検討され，IEEE 802.11b (以降，802.11b)，IEEE 802.11a (以降，802.11a)，IEEE 802.11g (以降，802.11g) の仕様が標準化された．そこで，本章では，現在広く普及している 802.11a/b/g 無線 LAN の概要について述べる．. 2.1. プロトコル構成. 無線 LAN は，IEEE802 体系の中の 1 つである．IEEE802.11 では，標準化の対象を MAC (Medium. Access Control) 層以下としており，上位のサービスに依存する部分は全く規定されていない．また，通信媒体が無線であるため，MAC 層のフレームとは別に物理層にフレームを用いるサブレイヤが規定されている．図 2.1 にそのプロトコル体系を示す．.

(8)

(9)

(10)

(11)

(12) !#"$ %&& (' *) &+-,.. ' ,,,657

(13) 8:9;<32 => ? @ :' BA CEDF3*' G.

(14) / 01&2/. 3+ ' /4&- &+-,. f1 '.Ag g Cb0hi @. ' ,,,657

(15) 8:9 8H= C @ "$ DI

(16) /*G ' ,,,657

(17) 8:9;;J/ 01&K#/4& MNPOQBRR ST:U U V TW. ' ,,,657

(18) 8:9 L / 0!&K#/J%. MNPOQBRR M NPOQBRRZY M NOQBRR_^ XU UU [ SX]\ :X U`U U V TW V T(W. ;7ba & ,:cFd ;7ba & ,:c8 ;7ba & ,cI ;7ba & ,e, >

(19) I

(20). l m m m MNPOQBRR jk @ <&-. ;7Ea & ,e, >

(21) . 図 2.1: IEEE802 のプロトコル体系．. 3.

(22) 表 2.1: 802.11a/b/g 無線 LAN の比較．. 2.2. —. 802.11b. 802.11a. 802.11g. 標準化時期. 1999 年. 1999 年. 2003 年. 使用周波数帯. 2.4GHz. 5GHz. 2.4GHz. 同時使用可能チャネル数 (日本). 4. 8. 4. 最高通信速度. 11Mb/s. 54Mb/s. 54Mb/s. 無線 LAN 規格 (IEEE 802.11a/b/g). 802.11b は，2.4GHz 周波数帯で最大 11 Mb/s の通信速度を実現する無線 LAN 規格として 1999 年に標準化された．802.11b では，電子レンジや医療機器などでも利用される 2.4GHz 周波数帯を用いてスペクトラム拡散通信を行う．そのため，こうした機器との電波干渉が問題になることがある．また，802.11b で通信できるチャネルは国によって異なり，日本では 14 チャネル用意されている．ただし，同一の場所で使用する場合は，スペクトラムが重なることによって発生する電波干渉をチャネルを離して設定することで防ぐため，日本では最大で 4 チャネルしか同時に使用することができない．また，802.11b は CSMA/CA 方式による MAC 制御や無線フレームのオーバヘッドなどの影響により，実効スループットは約 5 Mb/s となる．これに対して，1999 年に同じく標準化された 802.11a は，5GHz 周波数帯で最大 54 Mb/s の通信速度を実現する無線 LAN 規格である．日本では 2005 年の法改正に伴って，802.11a で利用可能なチャネルは 8 チャネルとなっている．802.11a では，変調方式として OFDM（Orthogonal Frequency. Division Multiplexing：直交周波数分割多重）方式を採用している．また，802.11a も 802.11b 同様に CSMA/CA 方式による MAC 制御や無線フレームのオーバヘッドなどの影響により，実効スループットは約 25 Mb/s となる．. 802.11g は，2.4GHz 周波数帯で最大 54 Mb/s の通信速度を実現する無線 LAN 規格として 2003 年に標準化された．802.11g では，802.11b と同様に ISM バンドの 2.4GHz 周波数帯を用いるため，. 802.11b との互換性 (後方互換性) を保つことが可能である．さらに 802.11g では，802.11b のスペクトラム拡散で用いられている DSSS/CCK 方式に加え，802.11a で用いられている OFDM 方式が必須の変調方式として定義されているため，2.4GHz 周波数帯において最大 54 Mb/s で通信することが. 4.

(23) 可能である．しかし，802.11b と同様に，CSMA/CA 方式による MAC 制御や無線フレームのオーバヘッドなどが影響し，802.11g の実効スループットは約 20 Mb/s となる．なお，IEEE802.11a/b/g 無線 LAN の比較を表 2.1 にまとめる．. 2.3. MAC 層. MAC 層では，フレームの断片化，暗号化，電力管理，メディアアクセス制御，およびローミング機能などの管理を行っている．本節では，本研究に特に関連するメディアアクセス制御について説明する．以下では，まず無線 LAN におけるメディアアクセス制御である CSMA/CA (Carrier Sense. Multiple Access with Collision Avoidance) 方式とその中で用いられている IFS による優先制御機構について述べる．さらに，この方式固有の問題である隠れ端末問題とその解決方法として用いられている RTS/CTS (Request to Send/Clear to Send) 機能について説明し，最後に無線 LAN に参加する際に用いるスキャニング機能についても説明する．. 2.3.1. CSMA/CA 方式. 802.11 無線 LAN で用いられているアクセス制御は自律分散制御 (DCF : Distributed Coordination Function) による無線チャネルアクセス制御である．この自律分散制御には，フレームの衝突をできるだけ回避するために，無線チャネルの使用状況を見てからフレームを送信するかどうかを決定する. CSMA/CA 方式が採用されている．この CSMA/CA 方式では，STA が送信を試みる時，まずキャリアセンス (搬送波の検出) を行い，無線チャネルの使用状況を調査する．もし，無線チャネルがアイドル状態であれば，規定された IFS (Inter Frame Space) の時間だけ待機する．しかし，このとき STA は一斉に送信しようとするため，送信を待つパケット衝突の確率が高くなる．そのため，各. STA は設定されているバックオフ時間と呼ばれるランダムな時間だけ待機し，その間継続してアイドル状態であることを確認して初めて無線リンクへのフレーム送信権を獲得できる．このバックオフ時間は，規定の CW (Contention Window) 範囲内で乱数を発生させ，その値をもとに決定される．このような制御によって CSMA/CA 方式ではできるだけフレームの衝突が発生しないように制御を行っている．このため，周辺に同一チャネルを利用する STA が複数存在したとしても，それら複数の STA 間で同一チャネルを共有して通信できる．しかし，このようなバックオフ制御を用いても，STA 数が増加した時，バックオフに用いられる. 5.

(24) .

(25) . . 図 2.2: IFS による優先制御．. 乱数値が同じ値となる確率が増加するため，フレームが同じタイミングで送出され衝突してしまうことがある．このように，衝突によってフレームが正常に受信されなかった場合，端末は規定回数に達するまでフレームを再送する．しかし，この再送はスループットの低下を招く．. 2.3.2. IFS による優先制御. 2.3.1 節で述べたように，IEEE802.11 では IFS と CW を用いてアクセス制御を行っている．また，この IFS を長さを変更し複数定義することにより，送信フレームに優先権を与えている．以下に主な IFS の種類を挙げ，それそれの IFS の関係を図 2.2 に示す．. • SIFS (Short Interframe Space) – 最小のフレーム間隔で，最優先のフレームである ACK フレームや CTS フレームを送信する際に用いるフレーム送信間隔として使用される．. • PIFS (PCF Interframe Space) – 802.11 規格でオプションとして定義している集中制御の PCF (Point Coordination Function) において，キャリアセンスを行う際にアイドル状態と判断するまでに必要なチャネルの連続未使用時間として用いられる．. • DIFS (DCF Interframe Space) – DIFS は IFS の中で最も長いフレーム間隔である．DCF (Distributed Coordination Function) に用いられ，RTS フレームやデータフレームを送信する際に用いるフレーム送信間隔である．. 6.

(26) .

(27) . . . 図 2.3: 隠れ端末問題．. 2.3.3. 隠れ端末問題. 無線通信では，STA 間の距離や電波を通さない障害物などの影響により，同じセル中に存在しても互いの無線信号が到達しない状態，つまりキャリアセンスが機能しない伝搬環境が起こり得る．このような問題は隠れ端末問題 (Hidden Terminal Problem) と呼ばれる．この隠れ端末問題が存在する環境下では，2.3.1 節で説明したキャリアセンスが有効に機能しないため，CSMA/CA 方式ではフレームの衝突頻度が増す．その結果，スループット特性は悪化してしまう．図 2.3 に隠れ端末問題の例を示す．STA1 と STA2 は互いにキャリアセンス可能である．一方，STA3 は STA1，STA2 のどちらともキャリアセンスはできない．この場合，STA1 は STA2 がデータを送信していないことを確認すると，STA1 は AP へデータの送信を行う．しかし，このとき STA3 も. AP へデータを送信を行いたい場合，STA3 は STA1 がデータの送信を行っていることを知らないため，STA3 もデータの送信を行う．その結果，STA1 と STA3 の送信データは衝突してしまい，隠れ端末問題により通信性能が劣化してしまう．. 7.

(28) /. ! " #$&%('*)(+ + . . ! . ! . ! . , . 2 , 0

(29) , 1 図 2.4: RTS/CTS の動作. 2.3.4. RTS/CTS. 2.3.3 節で述べた隠れ端末問題を解決するため，802.11 規格では，RTS/CTS と呼ばれる対策機能が定義されている．RTS/CTS を用いることで無線リンクをフレームの送信に必要な期間を予約できるため，他の STA の送信を禁止することができる．図 2.3 の環境において，RTS/CTS を用いた際の動作手順を図 2.4 に示す．STA1 はデータ・フレーム送信前に DIFS (Distributed Inter Frame Spacing) に加えてバックオフ時間だけ待機して，RTS をデータフレームの宛先である AP 宛に送信する．このとき，STA1 と STA2 は互いにキャリアセンスできる環境下にあるため，STA1 送信の RTS を STA2 も受信することができる．STA2 は RTS フレームに記載されている送信禁止期間 (NAV : NetworkAllocation Vector) を設定することにより衝突を回避する．一方，RTS を受信した AP は，SIFS (Short Inter Frame Spacing) 後，STA1 に CTS を返す．AP が送信した CTS は STA3 も受信することができるため，STA3 は他の端末が通信していることを知ることができる．そして，STA3 は CTS フレームに記載されている期間だけ NAV をセットすることにより衝突を防止する．一方，CTS を受信した STA1 は，SIFS 時間後にデータフレームを送信す. 8.

(30) る．データフレームを受信した AP は ACK フレームを STA1 に返し通信を終了する．RTS/CTS では NAV 期間に ACK フレームの受信が完了するまでの時間が設定されているため，この間他の端末はデータフレーム及び RTS/CTS を送信することができないため，衝突を防ぐことができる．. 2.3.5. スキャニング機能. STA が無線 LAN に参加する際に，AP を検出する機能をスキャニングという．スキャニングの手法にはアクティブスキャンとパッシブスキャンの 2 つの方法が規定されている．アクティブスキャンでは，移動中に AP からの受信電波状況が悪くなった STA が自ら Probe Request フレームと呼ばれるフレームを送信し，接続可能な AP からのレスポンス (Probe Response) を待機する．その後，複数の AP から Probe Response フレームを受信した STA は，電波状況から最適な AP を選択し，無線 LAN へ参加要求を意味する Reassociation Request フレームをその AP に対して送信する．一方，パッシブスキャンでは Probe Request フレームを送信せずに，AP から送信される Beacon メッセージを一定期間受信する．その後，その情報をもとに STA が選んだ AP に対して Reassociation. Request フレームを送信する．どちらの場合も，STA が AP からのレスポンスである Reassociation Response フレームを受信するとスキャニングが完了する．. 2.4. ネットワークトポロジ. 802.11 無線 LAN のネットワーク構成には，インフラストラクチャモード，アドホックモード，無線ディストリビューションシステム (WDS，Wireless Distribution System) の 3 つがある．ここでは，それぞれのネットワーク構成について説明する．. 2.4.1. インフラストラクチャモード. インフラストラクチャモードは AP と，その電波到達範囲 (無線セル) 内に存在する STA で構成される．インフラストラクチャモードでは，基本となる１つの AP とその配下の複数の STA で構成されるネットワークを BSS (Basic Service Set) と呼ぶ．一般に，STA は他の無線セル (BSS) へ移動した場合，受信電波強度から移動を検出して移動先の AP へ接続関係を切替えるハンドオフ機能 (ローミング) を備えており，これによって無線環境での移動性が確保される．また，図 2.5 に示すように，. BSS の集合で構成されるネットワークを ESS (Extended Service Set) と呼ぶ． 9.

(31) .

(32) .

(33).

(34) .

(35).

(36).

(37). .

(38).

(39). 図 2.5: インフラストラクチャーモード．. 2.4.2. アドホックモード. 図 2.6 に示すように，アドホックモードは AP を必要とせず，STA のみで構成され STA 間で直接通信を行うネットワーク構成である．そのため，インフラストラクチャモードの BSS と区別して IBSS. (Independent BSS) と呼ばれる．また，STA はパケットを中継する機能をもたず，直接お互いに無線リンクを使用してパケットのやり取りをすることで通信を行う．. 2.4.3. 無線ディストリビューションシステム (WDS : Wireless Distribution. System) WDS は図 2.7 に示すように，アクセスポイントのみによって構成されるネットワークである．AP はネットワーク間のパケットを中継する機能を持っている．また，インフラストラクチャモードと組み合わせてネットワークを構成することで，異なる ESS ネットワーク (BSS) 間で無線通信で接続することが可能となる．つまり，この WDS を利用することで，ケーブルを敷設することなく各ネットワークをワイヤレスで接続できる．ただし，802.11 規格ではパケットの中継方法については規定されておらず，各ベンダーが独自でパケット中継方法を実装しているのが現状である．. 10.

(40) . . . .

(41) . .

(42) .

(43) .

(44) . 図 2.6: アドホックモード．図 2.7: 無線ディストリビューションシステム．. 2.5. メッシュネットワーク. 無線 LAN で用いられる AP の電波到達範囲は，携帯電話や PHS の電波到達範囲と比べ数 10 m と狭い．そのため，広範囲な無線 LAN を構築する場合，複数の AP を設置する必要がある．通常，. AP 間の接続には，有線ネットワークの敷設が必要なため，AP 追加時やレイアウト変更時の柔軟性や拡張性が乏しくなってしまう．このため，AP 間を無線により接続することでこれらの課題を解決しようという取り組みがある．このような通信形態は図 2.8 に示すように複数の AP や STA が無線リンクでメッシュ状に接続されるため，メッシュネットワークと呼ばれる．図 2.9 に示すように，従来の無線 LAN では STA と AP 間は無線で接続し，AP 間は有線ネットワークで接続されていた．この場合，無線リンクで接続されている部分は AP と STA 間の 1 箇所であるため，このような接続形態はシングルホップ接続と呼ばれており，このような形態の無線 LAN をシングルホップ無線 LAN と呼ぶ．一方，メッシュネットワークでは，図 2.10 に示すように AP 間の接続や STA 間の接続も無線リンクで行うことで実現する．このような接続形態は，複数の無線リンクをパケットが中継されていく様子から，マルチホップ接続と呼ばれ，このような形態の無線 LAN をマルチホップ無線 LAN と呼ぶ．. 2.5.1. メッシュネットワークの特徴. メッシュネットワークは，マルチホップ接続を用いることで実現される．マルチホップ接続によるネットワークの構築は，以前よりアドホックネットワークとして研究されてきたため，メッシュネッ. 11.

(45) . . . .

(46).

(47). . . . . 図 2.8: メッシュネットワーク．. .

(48). .

(49). . . . 図 2.9: シングルホップ接続．. 12.

(50) . . .

(51) . . . . . . . 図 2.10: マルチホップ接続．. トワークは，アドホックネットワークの概念を多く含んでいる．このメッシュネットワークという用語は，実際のアプリケーションを意識して現実を見据えたネットワークとされている [9]．また，概念のみが規定されていた WDS の拡張や用語の定義などが現在検討されており，IEEE802.11s では，. AP 間をマルチホップ接続する形態のネットワークの名称をメッシュネットワークとして標準化が進められている [2] [3]．このメッシュネットワークには，シングルホップ無線 LAN と比較して以下のような利点がある．. 設置の容易性：メッシュネットワークでは，各 AP が自律的に隣接ノードを検出しネットワークを構築する．このため，複数の AP を設置するだけで広範囲をカバーした無線 LAN を構築できる．したがって，これまでカバーできなかった地域でも無線 LAN が使用できるようになる．. 高い堅牢性：メッシュネットワークでは，最も近い AP が故障したり，局所的な干渉が発生しても別の経路を使ってデータを転送できるため，耐故障性が高い．このため，メッシュネットワークはシングルホップ無線 LAN よりも高い堅牢性を保つことが可能となる．さらに，メッシュネットワークの実現環境を想定した場合，大きく次の２つに分類できる．. 1. マルチホップ機能を持つ無線機器が移動端末を含むすべての AP や無線機器である形態. 13.

(52) . . 図 2.11: AP 間の接続 STA に偏りが生じる例．. 2. マルチホップ機能を持つ無線機器が定常的な AP のような基本的に移動しない無線機器である形態実現の容易性などの観点から，2 がまず実現するものと予想されるため，本研究では以降，2 の形態を無線 LAN メッシュネットワークと呼ぶ．. 2.6. 無線 LAN の現状とその問題点. 2.5 節でも述べたように，無線 LAN の通信可能範囲は数 10 m と狭いため，広いエリアを無線 LAN でカバーするためには複数の AP を設置する必要がある．加えて，無線 LAN ではその無線資源を同じ無線セル内の全 STA で共有するため，STA の増加とともに各 STA のスループットは低下する．そのため，1 台の AP の最大収容 STA 数は 10 ∼ 20 台程度と制限され，これを越える数の STA を収容するためには AP を複数設置する必要がある．このように，AP が複数設置された無線 LAN においては，各 STA が接続する AP を適切に選択することが非常に重要となる．しかし，現在の多くの STA は接続先 AP を RSSI (Received Signal. Strength Indicator : 受信電波強度) のみを指標として決定しているため，STA は RSSI が最も強い AP を選択する [4]．このため，図 2.11 のように STA の分布が椅子や机の配置に影響されるような実環境を想定すると，AP 間の接続 STA 数は偏り，無線資源を有効かつ公平に利用できなくなる [5] [6]．. 14.

(53) 3. 提案 AP 選択手法本章では，2.6 節で述べた問題を解決するため，無線 LAN メッシュネットワークにおける AP 選. 択手法を提案する．まず先行研究で，シングルホップ無線 LAN 環境を想定した AP 選択手法として提案された MLT (Maximizing Local Throughput) アルゴリズム [7] [8] について説明する．次に，. MLT アルゴリズムを改良し，チェーントポロジの無線 LAN メッシュネットワークにも対応可能な AP 選択手法として提案する MLT-M (MLT extention for Multihop environment) アルゴリズムについて述べる．そして，さらに検討を進め，より一般的なトポロジの無線 LAN メッシュネットワークに対応するために提案する AP 選択手法である MLTAB (MLT with Avoiding Bottleneck) アルゴリズムについて説明する．. 3.1. MLT アルゴリズム. まず，シングルホップ無線 LAN を想定した AP 選択手法である MLT アルゴリズムについて説明する．MLT では各 STA は接続候補である全 AP に対して期待できるスループットを求め，それが最大となる AP を選択する．RTS/CTS を用いた CSMA/CA の通信手順にしたがってパケットが送受信されるとき，期待スループットを次のように計算する．まず，衝突と伝送誤りがない理想的な場合に，データサイズ Data[bits] のフレームを送受信するのに要する時間 tT は式 (3.1) で求まる．. tT = RT S + CT S +. Data(bits) + ACK + DIF S + 3SIF S + overhead Rate(b/s). (3.1). ここで，無線リンクの PER (Packet Error Rate) が P であるとき，正しく送受信されるのに要する時間 Tw は，式 (3.2) で求めることができる．. Tw = tT +. ∞ X. P i · (1 − P ) · i · tT =. i=1. tT 1−P. (3.2). したがって，N 台の STA が接続している AP に自 STA が接続した場合 (N + 1) に，期待できるスループットは式 (3.3) で求まる．. Φ=. Data Data · (1 − P ) = (N + 1) · Tw (N + 1) · tT. 15. (3.3).

(54) ここで，各 STA へ N の情報を通知するため AP は Probe Response および Beacon フレームに接続. STA 数の情報を追加する必要がある．各 STA が送受信するパケットサイズは同じであるとすると，期待できるスループットは式 (3.4) に示す重み関数で表すことができるため，MLT ではこの重み関数を各 AP 毎に計算する [7]．. WM LT =. 1−P N +1. (3.4). 式 (3.4) の P で表される PER は，受信電波強度から求めることができる．MLT アルゴリズムでは，. STA はこの重み関数が最大となる AP を自律分散的に選択する．. 3.2. MLT-M アルゴリズム. 前節で述べた MLT アルゴリズムはシングルホップ無線 LAN を想定しており，AP 間もデータが無線で中継される無線 LAN メッシュネットワークを想定していない．そこで，無線 LAN メッシュネットワーク環境においてデータが AP 間を無線で中継される際の PER を考慮した MLT-M (MLT. extension for Multihop Environment) アルゴリズムを提案する．図 3.1 に示すトポロジを例に挙げ提案 AP 選択手法について説明する．ここで，図 3.1 において AP0 は有線ネットワークへのゲートウェイ (GW, Gateway) とする．また，無線リンクで接続されたある 2 つの AP のうち，有線ネットワークに近い AP を上位 AP，他方を下位 AP と呼ぶ．ここで，有線ネットワークに近いとは，データが無線で伝達される回数 (ホップ数) が少ないことを指す．すなわち，図 3.1 では下位 AP が AP1，上位 AP が AP0 となる．さらに，Pup は上位 AP と STA 間の PER，Plow は下位 AP と STA 間の. PER，Pm は下位 AP と上位 AP 間の無線リンクにおける PER である．提案手法では AP 間の PER を考慮するためこの Pm を用いて，式 (3.4) を式 (3.5) に拡張する．. W1 =. (1 − Plow ) · (1 − Pm ) Nlow + 1. (3.5). ここで，Nlow は下位 AP の接続 STA 数である．AP は Probe Response および Beacon フレームに接続 STA 数と AP 間の PER(Pm )，上位 AP を特定するために上位 AP の MAC アドレスの情報を追加する必要がある．STA は式 (3.5) より重み関数を計算した後 (a)，上位 AP に対しては従来の MLT. 16.

(55) 6 7 8 9 8 : : 9 6 ;" <! 5 . 3 4. = # ;" >%$ 8& 7' ;( 8& >$ *- ). . / 0 1. .

(56) 2. ?) @,* A+. 図 3.1: トポロジ (2hop)．. と同様の式 (3.6) を用いて計算する (b)．. W0 =. 1 − Pup Nup + 1. (3.6). ここで，Nup は上位 AP の接続 STA 数である．提案手法では，STA はこの (a), (b) の計算を全 AP に対して行い，求められた重み関数 W をそれぞれ比較し最も値が大きい AP を接続先 AP として選択する．. 3.3. MLTAB アルゴリズム. 前節で述べたように，MLT-M アルゴリズムでは，STA は接続候補 AP の隣接無線リンクの情報を用い AP 選択を行う．しかし，より一般的な無線 LAN メッシュネットワークのように中継する経路が複数存在し，STA の通信範囲にない中継 AP の隣接無線リンクが頻繁にパケットロスや輻輳している場合，その影響を考慮できず，無線資源を有効かつ公平に利用できないと考えられる．そこで本研究では，さらに検討を進め，無線 LAN メッシュネットワークにおいて生じるボトルネックに着目した MLTAB (MLT with Avoiding Bottleneck) アルゴリズムを提案する．提案アルゴリズムでは式 (3.7) で表される重み関数を計算する．. 17.

(57) W =. 1 (N + 1) · B. (3.7). ここで，B はボトルネックリンクの負荷を表す値であり，この値が大きいとボトルネックリンクでの遅延が大きいことを表す．各 AP は隣接 AP 間の無線リンクに対して B を計算する．そして，その情報を AP 間で共有し，最も高い B の値を保持する (STEP1)．STA はこの情報を接続 STA 数 N と共に受け取る．STA は AP-STA 間についても B を求め，もし，AP から受け取った B の値よりも大きければ B の値を更新し，重み関数 W を求める (STEP2)．本稿では Greedy なファイル転送を行い，GW (有線 GateWay) 外のホストと STA 間で通信を行うアウトバウンドトラヒックを想定する．ここで，AP 間にボトルネックがあるとき，ボトルネックリンク以下に接続している全ての AP は ACK パケットを受信するまで次のパケットが送出できず，ボトルネックリンクの帯域に合わせた送信レートで通信を行う TCP セルフクロッキングが発生する．その結果，ボトルネックリンク以下の AP が獲得するスループットはほぼ等しくなることが報告されている [10]．そこで，本稿ではボトルネックリンクの負荷を表す値を B として，無線リンクの. PER である Pm ，ボトルネックリンク以下の全 AP 数 L と無線規格固有のオーバヘッド tT を用いる． STEP1 として，図 3.2 に示すトポロジの場合，AP2 は AP1-AP2 間の無線リンク負荷を求める．このときボトルネックリンク以下の AP の数 L は 3 台である．同様に AP1 は L = 10 とし GW-AP 間の無線リンク負荷を求め，求められた無線リンク負荷の値は AP 間で共有し，各 AP から受け取った無線リンク負荷のうち最大値を B として STA に通知する．STEP2 として，STA は AP から B と接続. STA 数 N の情報を受け取り，重み関数を式 (3.8) のように計算する．ただし，各 STA は AP-STA 間の無線リンク負荷の値を，下位 AP は自 STA のみであるとして L = 1 で計算を行う．そして，STA はその値と AP から受け取った B を比較し大きい方の値に B を更新して重み関数を求める．. W =. 1 1 = (N + 1) · B (N + 1) ·. L·tT 1−Pm. (3.8). 提案アルゴリズムでは，STA はこの計算を接続可能な全 AP に対して行い，求められた重み関数 W をそれぞれ比較し最も値が大きい AP を接続先 AP として選択する．. 18.

(58) "!$##%&A)(*,+

(59) 32. > ?, . 01 . ,36. C<. ,B7. /. /

(60) . 4. 32. > )?@ . 58 59. . : 5;. 01. "!$##%&')(*,+- .. <&=. ) . . 56. 37. 54 38 39 : 3; <&=. . 図 3.2: ボトルネックリンク負荷の計算．. +*" !".

(61) . )*" $&%" $#%".

(62) . '(". 図 3.3: リンク監視機構の状態遷移図．. 3.4. リンク監視機構. STA が提案 AP 選択アルゴリズムを無線 LAN に参加する時のみしか実行しない場合，その後の環境変化に伴い，STA にとって最適な AP は変化している可能性がある．環境が変化しても最適な. AP を各 STA が選択するためには，定期的に AP 選択アルゴリズムを実行する必要がある．そこで今回のシミュレーションでは， [7]， [8] で提案されているリンク監視機構を用いた．このリンク監視機構の状態遷移図を図 3.3 に示し，その概要を図 3.3 中の番号と対応させて説明する．まず，STA は Search Interval (SI) 間隔で各 AP に対する重み関数を計算する (1)．現在接続して. 19.

(63) いる AP よりも APnew の重み関数が高い場合，re-search 状態に遷移し，STA は Backoff Time (BT) 後に再度重み関数を計算する (2)．再計算の結果，再度 APnew が最適な AP として選択された場合，. STA は APnew へローミングを実行し，idle 状態へ遷移する (3)．再計算の結果，接続中の AP が最適な AP として選択された場合，STA は search 状態へ遷移する (4)．再計算の結果，別の新たな AP が最適な AP として選択された場合，その AP を APnew としSTA は re-search 状態にとどまり，BT 後に再度重み関数を求める (5)．ローミングを実行した STA は Idle Time (IT) 時間待機し，search 状態へ遷移する (6)．. 20.

(64) 4. 評価方法本章では，本研究で用いたシミュレーションモデルとシミュレーション環境について説明し，次に. 性能評価に用いた指標について説明する．. 4.1 4.1.1. シミュレーションモデル. MLT-M のシミュレーションモデル. 本稿では，MLT-M のシミュレーションモデルとして，Network Simulator 2 をマルチホップや. Static Routing に対応するよう拡張した TeNs (The Enhanced Network Simulator) [11] を用いてシミュレーションを行った．20 台の STA を図 4.1 に示すような 40 m × 80 m のエリア (AREA 1-4) または図 4.2 に示すような 40 m × 120 m のエリア (AREA 5) に 10 秒間でランダムに配置し，配置後は移動しないものとした．ここで，AREA 1 はエリア全体に STA が分布した場合を想定している．しかし，実際の使用環境は机や椅子の配置などの影響を受けるため，AREA 2 では AP 側へ STA の分布が偏った場合を想定した．AREA 3 および AREA 4 では STA の分布がさらに偏り，特定の AP 近傍に STA が集中した場合も想定しシミュレーションを行った．加えて，ホップ数の増加に対応できるか調査するために，AREA 5 で示す範囲に STA を配置した場合についても評価を行った．なお，各 STA は最も近い 2 つの AP のみと通信を確立できると想定している．また，ルーティングプロトコルには Static Routing を用いた．本稿では，アプリケーションとして FTP のようなファイル転送を想定し，送信側 (Source) である AP0 は TCP 通信を行うものとし，そのパケットサイズは 1500. Byte とした．従って，図 4.1 において AP1 へ接続した STA へのデータは，AP0 → AP1 → STA と転送される．ここで，図 4.1 のトポロジにおいて最大ホップ数は 2 ホップである一方で，図 4.2 のトポロジにおける最大ホップ数は 3 ホップである．また，無線 LAN 網は 802.11b によって構成されるものとし，無線区間のエラーモデルとして shadowing モデルを採用した．その PER 特性を図 4.5 に示す．さらに，各 AP は STA 用と中継用にそれぞれ無線 LAN インターフェースを持つとし，利用するチャネル間で干渉は生じないとした．また，リンク監視機構におけるパラメータは， [7] で推奨されている表 4.1 に示すパラメータを用いた．. 21.

(65) .

(66) .

(67) . . . #. . . $&% . .

(68) . .

(69) . . #. "!. . . $&'. 図 4.1: STA 分布 (MLT-M, 2hop)． .

(70) . . . . !. 図 4.2: STA 分布 (MLT-M, 3hop)．. 100. PER(%). 80 表 4.1: 状態遷移パラメータ. 60 40 20 0 0 10 20 30 40 50 60 70 80 90 100 Distance(m) 図 4.3: 距離-PER 特性 (MLT-M)．. 22. パラメータ. 値. SI. 3.0 sec. BT. 0 ∼ 1.0 sec. IT. 3.0 sec.

(71) -/.01

(72) . . . . . -/.0 . . . . . . . . . . . . . . .

(73) . . . .

(74) . -/.032 !#"$%'& ( ) *$&%,+ . . . . . . . . . -/.04. 図 4.4: STA 分布範囲 (MLTAB)．. 4.1.2. MLTAB のシミュレーションモデル. MLTAB のシミュレーションモデルには，QualNet3.9.5 を用いた．シミュレーションモデルとして，STA を図 4.4 に示す 60 m×60 m，120 m×120 m のエリア内にランダムに 80 台配置し，配置後は移動しないものとした．AREA1 では STA をエリア全体に配置し評価を行うが，実際の使用環境は机や椅子の配置などの影響を受けるため，AREA2，AREA3 のように STA の分布を偏らせた場合についても評価を行った．さらに，AP が増えて AP 網のボトルネックリンクの負荷が高くなる場合を想定し，AREA4 に示すエリアに STA を配置した場合についても評価を行った．なお，配置された STA は配置後 10 秒以内にランダムに AP との接続を開始するとした．. 23.

(75) 100 90 80. 11a 11b 11g. PER(%). 70 60 50 40 30 20 10 0 0. 20. 40 60 Distance(m). 80. 100. 図 4.5: 距離-PER 特性 (MLTAB)．. また，本シミュレーションでは，AP 間の経路については Static Routing で既に経路が確立済みであり，変更は生じないとした．アプリケーションとしては FTP のようなファイル転送を想定し，送信側である GW は各 STA と TCP 通信を行うものとし，そのパケットサイズは 1,500 Byte とした．また，使用する無線規格として STA は 802.11b (11 Mb/s) または 802.11g (54 Mb/s) を用い，AP 網は 802.11a (54 Mb/s) によって構成されるものとした．これらの無線区間の PER 特性を図 4.5 に示す．さらに，各 AP は STA 用と中継用にそれぞれ無線 LAN インターフェースを持つとし，利用するチャネル間で干渉は生じないとした．また，リンク監視機構におけるパラメータは，MLT-M 同様 [7] で推奨されている表 4.1 に示すパラメータを用いた．. 4.2. 評価指標. 提案手法の有効性は，全 STA 中の最大，平均，最小スループットや無線 LAN 網内の総スループットに加え，全シミュレーションを通じて得られたスループット確率分布を用いて検証した．さらに，. STA 間のスループットの公平性を示す指標として Balance Index (BI) [12] を用いて評価を行った． BI とは式 (4.1) で表される β の値であり，1 に近付くほど均衡を表し，1/N に近付くほど不均衡を. 24.

(76) 表す．. β=. P ( Bi )2 P N × (Bi2 ). (4.1). ただし，Bi は ST Ai の平均スループット，N は STA 数を表す．さらに，動的な AP 選択は接続先の AP を頻繁に変更するピンポン効果を引き起こす可能性があり，その結果ローミング中にパケットロスが発生するなど，通信に悪影響を与えることが考えられる．そこで，全 STA が最適な接続先 AP を最終的に決定し安定するまでの収束時間を用いて評価を行う．. 25.

(77) 5. 結果と考察. 5.1. MLT-M. まず本節では，無線メッシュネットワークにおいて，データが AP 間を無線で中継される影響を考慮した提案 AP 選択手法である MLT-M のシミュレーション結果について述べ，考察する．. 5.1.1. 全体に分布する場合. まず，図 4.1 に示すように，STA が均一に分布している AREA1 について評価を行った．図 5.1 に示す各 STA の平均スループット確率分布より，スループットの分布は RSS では約 100 ∼ 500 Kb/s に，MLT では約 100 ∼ 400 Kb/s に分散している一方で，MLT-M では約 150 ∼ 300 Kb/s と分散を抑制できていることが分かる．さらに，表 5.1 に示すスループット特性から，RSS において最大スループットと最小スループットとの差は約 220 Kb/s であったが，MLT-M ではその差を約 80 Kb/s まで短縮できていることが分かる．一方，MLT-M の総スループットは RSS や MLT より低いもの. 0.1. RSS MLT MLT-M. 0.09. Probability. 0.08 0.07 0.06 0.05 0.04 0.03 0.02 0.01 0 0. 100. 200 300 400 Throughput[Kb/s]. 図 5.1: スループット確率分布 (AREA1)．. 26. 500. 600.

(78) 表 5.1: スループット特性と公平特性 (AREA1)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 138.34. 240.05. 359.26. 4801.09. 0.8349. MLT. 133.56. 238.62. 340.77. 4772.37. 0.8558. MLT-M. 176.96. 228.41. 260.34. 4568.19. 0.9700. の，公平性を示す BI は高い．それに加え，表 5.1 から，MLT-M は RSS や MLT よりも最小スループットを約 40 Kb/s 改善できていることが分かる．したがって，STA が均一に分布している環境. (AREA1) において，MLT-M は最小・最大スループットの差を縮め，最小スループットを改善できるため，STA 間の公平性を向上可能であることが分かった．. 5.1.2. 分布が偏った場合. 次に，図 4.1 に示すように，STA が偏在している AREA2 について評価を行った．図 5.2 に示すスループット確率分布から，RSS では STA の獲得スループットが約 80 Kb/s に集中しているが，約. 600 Kb/s を越えるスループットを獲得している STA も存在していることが分かる．また，MLT ではスループットの分布が約 100 ∼ 400 Kb/s に分散していることが分かる．一方，MLT-M を用いた場合，スループットの分布が約 100 ∼ 250 Kb/s と分散を抑制できていることが分かる．さらに，表. 5.2 のスループット特性より，最大スループットと最小スループットの差が RSS では約 880 Kb/s， MLT では約 270 Kb/s と大きかったが，MLT-M を用いることで約 100 Kb/s と大幅に改善できることが分かる．加えて，最小スループットも RSS より約 60 Kb/s，MLT より約 40 Kb/s 改善できている．この結果から，MLT-M は RSS において一部の STA が独占的に獲得していた高いスループットを抑え，通信条件の悪い STA を保護できることが分かった．また，表 5.2 より MLT-M の総スループットは RSS や MLT-M より低いものの，公平性を示す BI は高い．以上から，STA が偏在している環境 (AREA2) においても，MLT-M は RSS や MLT と比較して公平性を改善可能な AP 選択手法であることが分かった．. 27.

(79) 0.18. RSS MLT MLT-M. 0.16. Probability. 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 0. 100. 200 300 400 Throughput[Kb/s]. 500. 600. 図 5.2: スループット確率分布 (AREA2)．. 表 5.2: スループット特性と公平特性 (AREA2)．スループット (Kb/s). 5.1.3. 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 81.08. 235.66. 963.52. 4713.19. 0.4116. MLT. 104.64. 212.56. 375.43. 4251.15. 0.7393. MLT-M. 142.64. 196.15. 239.40. 3923.03. 0.9545. 分布が極端に偏った場合. さらに，図 4.1 に示すように，STA が極端に偏在している AREA3，AREA4 について，図 5.3，図. 5.4 に示すスループット確率分布より，RSS はスループットの分布が低い値で集中していることが分かる．これは RSS が受信電波強度によって AP 選択を行った結果，全 STA が AP0 または AP1 に接続し，1 台の AP が提供する無線資源を全 STA で共有したためである．このように，既存手法であ. 28.

(80) 0.6. RSS MLT MLT-M. Probability. 0.5 0.4 0.3 0.2 0.1 0 0. 100. 200 300 400 Throughput[Kb/s]. 500. 600. 図 5.3: スループット確率分布 (AREA3)．. 0.7. RSS MLT MLT-M. Probability. 0.6 0.5 0.4 0.3 0.2 0.1 0 0. 100. 200 300 400 Throughput[Kb/s]. 図 5.4: スループット確率分布 (AREA4)．. 29. 500. 600.

(81) 表 5.3: スループット特性と公平特性 (AREA3)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 59.70. 70.46. 73.80. 1409.27. 0.9683. MLT. 94.02. 183.20. 349.67. 3664.09. 0.7066. MLT-M. 125.85. 168.73. 209.15. 3374.65. 0.9284. 表 5.4: スループット特性と公平特性 (AREA4)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 166.93. 167.90. 168.98. 3358.00. 1.0000. MLT. 199.74. 240.66. 259.07. 4813.23. 0.9903. MLT-M. 211.58. 240.45. 368.73. 4809.09. 0.9419. る RSS では，無線 LAN メッシュネットワークにおいて STA 分布が極端に偏ると，無線資源を有効に利用できないことが分かる．一方，図 5.3，図 5.4 から MLT や MLT-M により STA が自律的に最大スループットを期待できる AP を選択することで他の AP へ STA の接続が分散し，STA のスループットは RSS と比較して全体的に向上していることが分かる．さらに，表 5.3，表 5.4 に示すスループット特性から，最小，平均，最大スループットともに RSS より MLT-M や MLT の方が高い．加えて，総スループットに関しても RSS と比較して MLT-M や MLT の方が AREA3 では約 2000 Kb/s，. AREA4 では約 1500 Kb/s 高いことが分かる．よって，STA が極端に偏在している場合，MLT や MLT-M は RSS と比較して無線資源をより有効に利用できると言える．しかし，表 5.3，表 5.4 より RSS の BI はどちらの場合も他の手法より高い．これは先ほど述べたように，全 STA が AP0 または AP1 に集中した結果，全 STA で帯域を共有し，スループット差がほとんど無くなったためである．一方で，MLT-M は RSS と遜色ない BI の値をとっていることが分かる．また，MLT は AREA4 では MLT-M とほぼ同等のスループット特性や公平性を示しているものの，AREA3 では MLT-M よりも公平性が劣化している．したがって，STA が極端に偏在している環境 (AREA3，AREA4) において，MLT-M は公平性を充分高く維持しつつ，スループット特性を改善できることが分かった．. 30.

(82) 0.09. RSS MLT MLT-M. 0.08. Probability. 0.07 0.06 0.05 0.04 0.03 0.02 0.01 0 0. 100. 200 300 400 Throughput[Kb/s]. 500. 600. 図 5.5: 平均スループット確率分布 (AREA5)．. 5.1.4. ホップ数が増加した場合. 前節までは最大ホップ数は 2 であった．そこで，本節ではホップ数が増えた場合にも MLT-M が有効な AP 選択手法であるかを調査するために，図 4.2 に示す最大ホップ数が 3 である場合について評価を行った．図 4.2 に示すように，STA がエリア全体に分布する AREA5 について，図 5.5 に示すスループット確率分布より，RSS や MLT ではスループットの分布が約 100 ∼ 600 Kb/s を越える範囲に広く分散している．さらに，表 5.5 より最大スループットと最小スループットの差は RSS では約 450 Kb/s，. MLT では約 410 Kb/s であり，600 Kb/s を越えるスループットを獲得している STA も存在していることが分かる．これは，パケットが AP 間も無線で中継される影響を考慮しない手法である RSS や MLT では，ゲートウェイである AP0 へ接続している少数の STA が独占的に無線資源を利用しているためである．一方，MLT-M ではスループット分布が約 100 ∼ 400 Kb/s に集中しており，表 5.5 より最大スループットと最小スループットの差は約 230 Kb/s に縮まっている．さらに，MLT-M における最小スループット特性は RSS や MLT と比べて約 20 Kb/s 改善していることが分かる．また，. 31.

(83) 表 5.5: スループット特性と公平特性 (AREA5)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 84.35. 228.72. 537.01. 4574.36. 0.5846. MLT. 81.94. 224.37. 491.13. 4487.35. 0.5900. MLT-M. 100.41. 210.35. 330.45. 4207.10. 0.7719. MLT-M では少数の STA による AP の独占とそれによる総スループットの増大がないため，平均スループットは RSS や MLT よりも約 20 Kb/s ほど低いが，表 5.5 より STA 間の BI は約 0.2 改善していることが分かる．以上の結果より，最大ホップ数の増加に関わらず，MLT-M は最小スループットと公平性を改善できることが分かる．以上のすべてのシミュレーション結果から，無線 LAN メッシュネットワークにおける AP 間の PER を考慮した AP 選択手法である MLT-M は最小スループット及び STA 間の公平性を RSS や MLT よりも改善できることが分かった．特に，STA が遍在するような場合は，平均スループット特性も大きく向上できることも分かった．. 5.2. MLTAB. 次に本節では，MLT-M よりさらに検討を進め，より一般的な無線メッシュネットワークに適応可能な AP 選択手法である MLTAB のシミュレーション結果について述べ，考察する．. 5.2.1. STA が 11b を用いる場合. まず，STA が図 4.4 に示す AREA1 に均一に分布しており，AP と 11b を用いて通信を行う場合について評価を行った．このとき，11a と 11b では通信速度に 4∼5 倍の差があり，AP-STA 間がボトルネックとなる．図 5.6 に示す各 STA の平均スループット確率分布より，スループットの分布は. RSS では約 200 ∼ 1,000 Kb/s に分散しているが，MLT，MLTAB では約 300 Kb/s∼ 500 Kb/s に集中していることが分かる．さらに，表 5.6 に示すスループット特性から，RSS において最大スループットと最小スループットとの差は約 800 Kb/s であるが，MLTAB ではその差を約 160 Kb/s まで. 32.

(84) 0.16. RSS MLT MLTAB. 0.14. Probability. 0.12 0.1 0.08 0.06 0.04 0.02 0 0. 200. 400 600 Throughput[Kb/s]. 800. 1000. 図 5.6: スループット確率分布 (AP-11a/STA-11b, AREA1)．. 縮めていることが分かる．一方，表 5.6 より MLT，MLTAB の総スループットは RSS と比較してもほぼ同じであり，公平特性を示す BI は RSS より高いことが分かる．それに加え，表 5.6 から，MLT，. MLTAB は RSS よりも最小スループットを約 100 Kb/s 改善できていることが分かる．ここで，MLT と MLTAB 間にスループット特性の差が生じないのは，STA が 11b を使用し，AP-STA 間がボトルネックとなっているためである．そのため，AP-STA 間にボトルネックリンクがあるとして AP を選択する MLT は MLTAB と同程度の改善効果が得られる．したがって，STA が均一に分布している環境 (AREA1) について，AP-STA 間にあるボトルネックリンクの情報をもとに AP 選択を行う. MLT と MLTAB は最小・最大スループットの差を縮め，最小スループットを改善し，STA 間の公平性を改善可能であることが分かった．また，表 5.7 に示すように MLTAB によって最適な AP を決定するまでに要する時間は平均で 5.72 秒であり，最大でも 17.82 秒であることが分かる．したがって，STA が均一に分布している環境. (AREA1) について，MLTAB はピンポン効果を抑え高い収束性を持つと言える．. 33.

(85) 表 5.6: スループット特性と公平特性 (AP-11a/STA-11b, AREA1)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 207.20. 395.92. 1082.81. 31673.88. 0.84. MLT. 319.10. 388.67. 472.21. 31093.34. 0.99. MLTAB. 311.40. 387.49. 470.41. 30999.25. 0.99. 表 5.7: 収束に要する時間 (AP-11a/STA-11b, AREA1)．収束までの時間 (sec). 5.2.2. AP 選択手法. 最小. 平均. 最大. MLTAB. 1.86. 5.72. 17.82. STA が 11g を用いる場合. 次に，ネットワークトポロジを変えずに，STA が 11g を使用し，ボトルネックリンクが AP 網の. GW 付近に発生する場合について評価を行った．図 5.7 に示すスループット確率分布から，スループットの分布は RSS では約 200 ∼ 2,500 Kb/s，MLT では約 200 ∼ 2,500 Kb/s と広く分散している．加えて，RSS では 2,500 Kb/s 以上のスループットを獲得している STA も多く存在していることが分かる．このことから，RSS や MLT では AP-STA 間の情報しか持たないため，AP 網にボトルネックがある場合，適切な AP を選択できないことが分かる．一方，AP 網のボトルネックリンクの情報を用いる MLTAB では，スループットの分布範囲が約 600 Kb/s∼ 2,000 Kb/s と RSS や MLT と比較して狭くなっていることが分かる．さらに，表 5.8 のスループット特性より，RSS や MLT を用いた場合，最大スループットと最小スループットの差はそれぞれ約 2,800，1,800 Kb/s と大きいが，MLTAB を用いることで約 1,500 Kb/s と最も改善できることが分かる．これは，RSS や MLT で一部の STA が独占的にスループットを獲得していた AP に，MLTAB により他の AP に接続していた STA が接続したためである．加えて，最小スループットも RSS や MLT と比較して約 450 Kb/s 改善していることが分かる．これらの結果より，ボトルネックリンクの情報を利用した自律分散型. AP 選択手法である MLTAB では，一部の STA による AP の独占を抑制し，通信条件の悪い STA. 34.

(86) 0.2. RSS MLT MLTAB. 0.18. Probability. 0.16 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 0. 500. 1000 1500 2000 Throughput[Kb/s]. 2500. 図 5.7: スループット確率分布 (AP-11a/STA-11g, AREA1)．. 表 5.8: スループット特性と公平特性 (AP-11a/STA-11g, AREA1)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 185.78. 841.68. 3024.04. 67334.15. 0.58. MLT. 183.43. 836.78. 2292.23. 66942.69. 0.71. MLTAB. 645.87. 865.88. 2157.32. 69270.83. 0.88. のスループットを改善できることが分かった．また，表 5.8 より MLTAB の総スループットは RSS や MLT より高く，公平性を示す BI も RSS や MLT より高い．以上から，STA が偏在している環境. (AREA2) では，MLTAB は RSS と MLT と比較して平均スループットを向上させつつ，最小スループットと最大スループットの差を抑えることで公平性を改善可能であることが分かった．また，表 5.9 に示すように MLTAB によって最適な AP を決定するまでに要する時間は平均で 4.73 秒であり，最大でも 14.19 秒であることが分かる．さらに，全 STA を配置し終える 10 秒以内に AP. 35.

(87) 表 5.9: 収束に要する時間 (AP-11a/STA-11g, AREA1)．収束までの時間 (sec). AP 選択手法. 最小. 平均. 最大. MLTAB. 0.00. 4.73. 14.19. 選択が完了している場合もあることが分かる．したがって，ボトルネックが AP 網に発生する場合についても，MLTAB はピンポン効果を抑え高い収束性を持つと言える．さらに，図 4.4 に示すように，STA が偏在している AREA3，AREA4 について，図 5.8，図 5.9 に示すスループット確率分布より，RSS では他の手法と比較して低いスループットを獲得している STA が多く存在していることが分かる．これは RSS が受信電波強度によって AP 選択を行った結果，全. STA が受信電波強度の強い近くの AP に接続し，少数の AP によって提供される無線資源を全 STA で共有したためである．このように，既存手法である RSS では，無線 LAN メッシュネットワークにおいて STA 分布が偏ると，無線資源を有効に利用できない．加えて，MLT でも AP 網のボトルネックリンクを考慮しないため，ボトルネックリンクを経路に持つ AP を選択した STA は比較的低いスループットを獲得している．一方，図 5.8，図 5.9 からボトルネックリンクの情報を考慮し STA が自律的に AP を選択する MLTAB では STA の接続が他の AP へ分散し，STA の最小スループットは RSS と MLT と比較して向上していることが分かる．さらに，表 5.10，表 5.11 に示すスループット特性から，最小，平均，最大スループットともに RSS より MLTAB の方が高い．加えて，総スループットも RSS や MLT と比較して MLTAB の方が大きく改善されていることが分かる．よって，STA が偏在している場合，MLTAB は他の 2 つの方式と比較して無線資源をより有効に利用できると言える．また，表 5.12，表 5.13 に示すように MLTAB によって最適な AP を決定するまでに要する時間は. AREA2，AREA3 についてそれぞれ平均 6.80，5.12 秒であり，最大でも 10.15 秒，11.04 秒であることが分かる．このことから，STA が偏在している AREA3，AREA4 について，配置後 10 秒間のうちランダムに AP と接続を開始することを考慮すると，MLTAB は比較的短い時間で最適な AP を選択でき，その収束性は良好であることが分かる．. 36.

(88) 0.25. RSS MLT MLTAB. Probability. 0.2. 0.15. 0.1. 0.05. 0 0. 500. 1000 1500 2000 Throughput[Kb/s]. 2500. 図 5.8: スループット確率分布 (AP-11a/STA-11g, AREA2)．. 0.25. RSS MLT MLTAB. Probability. 0.2. 0.15. 0.1. 0.05. 0 0. 500. 1000 1500 2000 Throughput[Kb/s]. 図 5.9: スループット確率分布 (AP-11a/STA-11g, AREA3)．. 37. 2500.

(89) 表 5.10: スループット特性と公平特性 (AP-11a/STA-11g, AREA2)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 29.37. 493.53. 1889.18. 39482.48. 0.54. MLT. 207.74. 811.79. 2238.99. 64943.55. 0.70. MLTAB. 608.51. 835.08. 2094.73. 66806.52. 0.87. 表 5.11: スループット特性と公平特性 (AP-11a/STA-11g, AREA3)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 162.65. 604.60. 1580.92. 48367.63. 0.72. MLT. 180.44. 836.57. 2262.06. 66925.59. 0.71. MLTAB. 641.07. 867.27. 2099.88. 69381.77. 0.88. 表 5.12: 収束に要する時間 (AP-11a/STA-11g, AREA2)．収束までの時間 (sec). AP 選択手法. 最小. 平均. 最大. MLTAB. 2.57. 6.80. 10.15. 表 5.13: 収束に要する時間 (AP-11a/STA-11g, AREA3)．収束までの時間 (sec). 5.2.3. AP 選択手法. 最小. 平均. 最大. MLTAB. 0.54. 5.12. 11.04. ボトルネックリンクの影響が大きい場合. 次に，図 4.4 の AREA4 に示すように，5.2.1，5.2.2 節よりもボトルネックリンク以下の AP の数を増やし，ボトルネックリンクの影響をより大きくした場合について評価を行った．この場合，AREA4 の左側の AP に比べ，右側の AP には多くの AP が一つのボトルネックリンク以下に存在するため，. STA は右側の AP へ接続すると期待したスループットが得られない可能性がある．図 5.10 に示すス. 38.

(90) 0.16. RSS MLT MLTAB. 0.14. Probability. 0.12 0.1 0.08 0.06 0.04 0.02 0 0. 500. 1000 1500 2000 Throughput[Kb/s]. 2500. 3000. 図 5.10: スループット確率分布 (AP-11a/STA-11g, AREA4)．. ループット確率分布から，スループットの分布は AP-STA 間の情報だけで AP 選択を行う RSS や. MLT では約 100 ∼ 3,000 Kb/s に広く分散しており，3,000 Kb/s を越えるスループットを獲得している STA が多く存在していることが分かる．一方，AP 網のボトルネックリンクの情報を用いる. MLTAB では，スループットの分布が約 600 Kb/s ∼ 1,500 Kb/s に集中していることが分かる．さらに，表 5.14 のスループット特性より，RSS や MLT を用いた場合，最大スループットと最小スループットの差はそれぞれ約 11,100，3,900 Kb/s と大きいが，MLTAB を用いることでその差を約 900. Kb/s まで抑えることができた．加えて，最小スループットも約 600 Kb/s 改善していることが分かる．このことから，MLTAB では RSS で一部の STA が独占的に獲得していた高いスループットを抑え，通信条件の悪い STA のスループットを改善できることが分かった．また，表 5.14 より MLTAB の総スループットは RSS や MLT よりも高く，BI も RSS や MLT より大きく改善されている．したがって，ボトルネックリンクの影響をより大きくした場合 (AREA4) でも，MLTAB は他の 2 つの方式と比較してスループット特性と公平性を改善可能であることが分かった．また，表 5.15 に示すように MLTAB によって最適な AP を決定するまでに要する時間は平均で. 39.

(91) 表 5.14: スループット特性と公平特性 (AP-11a/STA-11g, AREA4)．スループット (Kb/s). 公平性. AP 選択手法. 最小. 平均. 最大. 合計. BI. RSS. 88.13. 846.63. 11240.97. 67730.14. 0.31. MLT. 51.40. 857.37. 3939.47. 68589.44. 0.52. MLTAB. 653.96. 917.19. 1523.91. 73375.00. 0.94. 表 5.15: 収束に要する時間 (AP-11a/STA-11g, AREA4)．収束までの時間 (sec). AP 選択手法. 最小. 平均. 最大. MLTAB. 1.25. 4.75. 11.68. 4.75 秒であり，最大でも 11.68 秒であることが分かる．このことから，ボトルネックリンクの影響をより大きくした場合についても，MLTAB はピンポン効果を抑えながら AP を選択できる手法であると言える．. 5.2.4. STA 数を増やした場合. 最後に，図 4.4 の AREA4 に示すエリアに，STA の数を 80 台から 120 台に増やして，ボトルネックリンクの影響をさらに大きくした場合について評価を行った．この場合，AREA4 の左側の AP に比べ，右側の AP には多くの AP が一つのボトルネックリンク以下に存在するため，STA は右側の. AP へ接続すると期待したスループットが得られない可能性がある．図 5.11 に示すスループット確率分布から，スループットの分布は AP-STA 間の情報だけで AP 選択を行う RSS や MLT では約. 10 ∼ 1,000 Kb/s に分散していることが分かる．一方，AP 網のボトルネックリンクの情報を用いる MLTAB では，スループットの分布が約 100 Kb/s ∼ 1,200 Kb/s に集中していることが分かる．さらに，表 5.16 のスループット特性より，RSS や MLT を用いた場合，最小スループットがそれぞれ約 4 Kb/s，約 2 Kb/s と極端に小さくなっていることが分かる．これは，ボトルネックリンクが継続的に輻輳することによってバッファ溢れが発生し，パケットロスした TCP フローのウィンドウサ. 40.