解説}}}}}}
解説}}}}}}

Wireless LAN におけるアクセスポイント 選択方式の提案とその評価
福田 豊 1

1 はじめに無線 LAN を利用したインターネット接続が増加しています．1997 年に登場した無線 LAN の最初の規格である 802.11 では最大通信速度が 2 Mb/s と十分ではありませんでしたが，その後 1999 年に登場した 802.11b では最大通信速度が 11 Mb/s に，また 2003 年に登場した 802.11g では最大通信速度が 54

Mb/s まで向上し，高速でケーブルに縛られない柔軟なインターネット接続が可能となっています．そのため，これまで有線 LAN を利用していた家やオフィス等の無線 LAN 化だけでなく，ホテルや空港のラウンジ，駅やカフェ等での無線 LAN を通したインターネット接続サービスも始まっています．このように広く普及が進む無線 LAN は，次世代通信ネットワークを構成するための重要な基盤となると考えられています．
本学飯塚キャンパスにおいても，昨年度情報コンセントサービスが開始され，ケーブルや情報端末数の制約に関係なく，無線 LAN の AP (Access Point) の電波が到達する範囲内でインターネット接続が可能となっています．ただし電波が届く範囲は屋外で 150m，障害物が少ない屋内で 50m 程度といわれ，大学のキャンパスのような広い範囲をカバーするためには複数の AP を設置する必要があります．またAP が提供する無線通信資源は，その AP に接続する STA (Station, 端末) によって共有されるため，接続する STA 数が増加するにつれ，STA1 台当たりのスループットは低下していきます．一般には 1 台のAP につき STA20 台程度が限度といわれています．講義室や国際会議等での無線 LAN 利用を考えると，100 人かそれ以上の人が無線 LAN を利用することになり，1 台の AP では十分な通信速度を提供することが困難です．よって必要に応じて複数台の AP を設置した無線 LAN 網を構築し，通信容量を拡充していく必要があります．
このように通信範囲を広げ収容 STA 数を増やすために複数の AP によって構築された無線 LAN 網では，STA の AP 選択が非常に重要な問題となります．現在市販されている無線 LAN カードでは，受信電波強度のみを指標として接続先の AP を選択するため，AP 間の接続 STA 数が偏り，無線帯域を有効かつ公平に利用できなくなります [3][4]．また現在の無線 LAN 製品には負荷分散機能を有するものがあ
りますが，これらの製品はベンダー独自の負荷分散ポリシーにより AP 側で STA を再分配するもので，異なるベンダーの機器間に互換性が無いほか，導入コストが非常に高くなってしまいます [5]．そこで
本稿では，無線 LAN 網から得られる様々な情報をもとに，STA 自身が自律的に AP を選択するアルゴ
リズムを提案し，その効果をシミュレーションによって明らかにします．そのシミュレーションについ1

情報科学センター, fukuda@isc.kyutech.ac.jp

50

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説て述べる前に，まず無線 LAN の技術的な概要を 2 章で示します．3 章では提案するアルゴ リズムについて詳細を説明します．4 章ではシミュレーションモデルについて説明し，5 章でその結果を示します．
最後に 6 章でまとめます．

2 IEEE 802.11 無線 LAN
IEEE 802.11 無線 LAN 規格は 1997 年 IEEE によって標準化され，その後 1999 年 11 月に最大通信速度が 2 Mb/s から 11 Mb/s まで高速化された IEEE802.11b，および，最大 54Mb/s の通信速度を実現する IEEE802.11a が標準化されました．さらには IEEE802.11b との互換性を保ちながら高速化を実現する IEEE802.11g が 2003 年 6 月に標準化されました．本章ではこのように広く普及している IEEE
802.11 ファミリーについて技術的な概要を述べ，その現状と問題点について説明します．また提案手法で利用する，各 STA が期待できるスループットについての簡単な解析を示します．
2.1 IEEE 802.11 無線 LAN の規格
現在利用されている無線 LAN の規格を表 1 に示します．
表 1: 無線 LAN 規格
無線 LAN 規格

周波数帯

伝送速度

IEEE 802.11b
IEEE 802.11a
IEEE 802.11g

2.4GHz
5GHz
2.4GHz

1〜11Mb/s 14(※干渉有)6〜54Mb/s
4
1〜54Mb/s 14(※干渉有)

チャネル数

IEEE 802.11b/g が利用する 2.4GHz 帯は，国内では 2.400〜2.497GHz を使用することができます．
規格では，2.400〜2.4835GHz を 5MHz 間隔で区切った 13 個のチャンネルと，2.484GHz 帯の計 14 個のチャンネルを規定しています．実際の通信には，チャネル同士で重ならない 4 チャンネル分を使用する
ので，1〜13 の間に最大 3 個のチャンネルと第 14 チャンネルの計 4 チャンネルが，互いに干渉しない完全に独立した通信チャンネルとなります．2.4GHz 帯は ISM(ISM band, Industrial Science and Medicalband) 帯であり，コードレス電話，無線を使う液晶テレビ，アマチュア無線等多くの機器がこの周波数帯を利用しているため，電波干渉が問題となります．特に電子レンジにより大きな干渉を受けてしまう
ことが知られています．一方の IEEE 802.11a では，5GHz を利用します．日本国内では，気象レーダーなどに使われている帯域と重複するため，無免許の特定小電力無線で利用できるのは 5.15〜5.25GHz の100MHz のみとなっています．また空中線電力は 10mW 以下と規定されており，屋内での使用に限定されています．

IEEE 802.11b では，フレーム送信前に共通情報を 1Mb/s の DBPSK(Di erential Binary Phase Shift
Keying) 変調で送信します．転送速度や変調方式などの情報もここに含まれます．転送速度としては，
1，2，5.5，11Mb/s が，変調方式としては，従来からの DSSS(Direct Sequence Spectrum Spread) 方51

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説
式に加えて 802.11b で拡張された 5.5，11Mb/s 用の CCK(Complementary Code Keying) が規定されています．そして共通情報の後に続くデータフレーム本体を指定された方式に切り換えて復調します．

IEEE 802.11a では，狭帯域の搬送波を複数使って伝送する OFDM(Orthogonal FrequencyDivision
Multiplex〜直交周波数分割多重) という変調方式を用いています．1 チャンネルあたりの占有周波数帯
幅は 16.6MHz で、国内で使用できる 5.2GHz 帯には，ガードバンド 含む 20MHz の帯域が 4 チャンネル用意されています．この帯域はデータ用の 48 本と，パイロット信号用 4 本の計 52 本の狭い帯域に分割され (1 本辺り 0.3125MHz)，それぞれの帯域で搬送波 (サブキャリア) が立てられます．そして個々のサブキャリアを 0.25MHz の変調速度で個別に変調し，全体を使ってデータを伝送します．
IEEE 802.11g は，IEEE 802.11b をベースに，20Mbps を越える高速伝送モード をサポートする拡張規格です．基本仕様は従来の 802.11b に 5GHz 帯を使う 802.11a の技術を合体させた規格になっています．IEEE 802.11g では新しい変調方式である 802.11a の OFDM モード を追加しています．そしてデータパケットの先頭に OFDM モード 用の情報などを入れ，6〜54Mbps の OFDM モードに移行しています．IEEE 802.11b の方式がそのまま継承されているので，既存の無線 LAN カードや AP とはこれまで通りの 802.11b モードで通信できます．また 802.11g をサポートする無線 LAN カードや AP とはIEEE 802.11a と同じ OFDM モードで高速な通信を行うことができます．ただし，6Mbps で送信が始
まる 802.11a に比べると，低速な手順が余分に加わるために，オーバーヘッドが若干増えてしまいます．
このような無線 LAN の標準化を行う代表的な国際機関は，IEEE の 802 委員会配下にあるワーキン
グループ 11 です．そのワーキンググループ下のタスクグループとその活動内容を表 2 に示します．
表 2: 無線 LAN 規格
グループ名

検討内容

TGa
TGb
TGc
TGd
TGe
TGf
TGg
TGh
TGi
TGj
TGk
TGm
TGn
WNG SCHT SG

5GHz 無線 LAN 検討 (OFDM 変調)
2.4GHz 無線 LAN 検討 (CCK 変調)
MAC レ イヤ補足検討
電波規則更新QoS のための MAC 層プロトコル強化
AP 間プロトコル仕様の策定
802.11b の高速化拡張仕様
欧州対応 802.11a
セキュリティのための MAC 層プロトコル強化
日本向け 4.9 〜 5GHz 利用 (屋外の仕様策定
無線資源の有効活用

802.11a/g などの仕様修正
次世代無線 LAN
次世代無線 LAN 検討委員会
高速スループット研究

現状
標準化済み
標準化済み
活動終了
標準化済み
審議中
審議中
標準化済み
審議中
審議中
審議中
審議中
審議中
審議中
審議中
審議中

すでに標準化を終え活動を終了させているタスクグループもありますが，さらなる高速化等を目指した新たなタスクグループが承認されるなど ，活発な標準化活動が現在でも続いています．

52

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

2.2 IEEE 802.11 ネット ワーク形態

IEEE 802.11 無線 LAN を構成する最も基本的な構成要素は，複数の STA によって構成される BSS(Basic
Service Set) です．BSS にはアドホックネットワークとインフラストラクチャネットワークの 2 つの種類があります．アド ホックネットワークでは，図 1 に示すように STA は互いに直接通信します．一方
インフラストラクチャネットワークでは，図 2 に示すように STA は他の STA や無線 LAN 外のネット
ワークと AP を経由して通信します．この点で AP は携帯電話網の基地局と類似しています．現在の無線 LAN 網は殆ど インフラストラクチャネットワークによって構築されており，本稿ではこのインフラストラクチャネットワークを対象としています．

図 1: アド ホックネットワーク

AP

図 2: インフラストラクチャネットワーク
冒頭でも述べたように，1 つの AP によってカバーできる通信距離や通信速度は限られています．よって通信距離と通信容量を拡充するためには，複数の BSS を組み合わせた無線 LAN 網を構築する必要があります．この複数の BSS によって構成される無線 LAN 網のことを ESS (Extended Service Set) と呼びます．ESS を図 3 に示します．同じ ESS 内の STA は互いに通信することができ，1 つの BSS から他の BSS に透過的に移動することが出来ます．ESS は複数の BSS によって構成されますが，この BSS 間は DS (Distribution System) によって接続されます．DS は 1 つの AP が他の AP に所属している STA
や無線 LAN 外部のネットワークまでフレームを送信できる機構を有しています．そのため DS は異なる BSS 間をつなぐバックボーンだと考えることも出来ます．この DS には大抵の場合イーサネットが利用されています．

53

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説
Extended Service Sets (ESS)
Basic Service Sets (BSA) 1

BSA 2

AP1

AP2

Distribution System (DS)

AP3

AP4

BSA3

BSA4

図 3: Extended Service Set

2.3 無線 LAN における Medium Access Control
無線 LAN においては，STA や AP がどのようなタイミングで相手にデータを送信するかや，通信媒体である無線をどのように利用するかなどを規定する MAC (Medium Access Control) は非常に重要な基本機能です．IEEE 802.11 無線 LAN における MAC としては，PCF(Point Coordination Function)と DCF(Distributed Coordination Function) という 2 つのモードがあります．前者の PCF は，AP がSTA に対して送信を許可するポーリングを行う集中制御型です．そのためフレームの衝突や STA 間の競合が発生しません．一方後者の DCF は，各 STA が衝突を前提として CSMA/CA (Carrier Sense
Multiple Access with Collision Avoidance) により自律分散的に通信し合う分散制御型です．同じような通信方式としてイーサネットが利用している CSMA/CD (Carrier Sense Multiple Access with Collision
Detection) がありますが，無線 LAN では自 STA がフレームを送信中の場合，そのフレームと他のフレーム間の衝突を検知することが不可能であるため，CSMA/CD ではなく，CSMA/CA を用いています．また衝突無く正しく相手に到達しているかを判断するために，誤りのないフレームを受け取った受信側は MAC 層の ACK(Acknowledgement) を返します．IEEE 802.11 無線 LAN ではこの DCF を必須の機能とし，PCF をオプションとして定義しています [1]．よって本稿では DCF を対象とします．
無線 LAN ではパケットの種別毎に異なる優先度が与えられています．例えば，MAC 層の ACK フレー
ムにはデータフレームよりも高い優先度が与えられています．この優先度を与えるために，3 つの異なった IFS(Inter Frame Space) が定義されています．図 4 に示すとおり最も優先度が高いのは SIFS(Short

IFS), 次が PIFS (PCF IFS), 最後に DIFS (DCF IFS) となっています．SIFS は MAC 層の ACK フレー
ムなどに用いられます．PIFS は PCF モードで用いられ，AP が STA に送信権を与える時に使用します．DCF はデータフレームを送信するときに用いられます．
次にデータの送信に用いられる CSMA/CA の動作について説明します．図 5 に CSMA/CA を用いた
基本的なデータ送信を示します．最初に STA は無線チャネルがビジーかどうかをチェックします．もし無線チャネルがビジーであれば，STA はチャネルがアイドル状態に戻るまで待ち，その後さらに DIFS
期間待った後，ランダムなバックオフ時間を計算します．この DIFS 後に STA が計算するランダムな時
間を CW (Contention Windows) と呼びます．CW の初期値の範囲は 0 0 31 です．そしてこのランダムに決めたバックオフタイマーを，無線チャネルが再びビジーになるか，バックオフタイマーが 0 にな
54

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

DIFS
PIFS
SIFS

Frame

t
図 4: Some IFS relationships
るまで減らしていきます．もしバックオフタイマーが 0 になる前に無線チャネルが再びビジーになった
場合は，STA は現在のバックタイマー時間を保持し，無線チャネルがアイドル状態になった後に保存しておいたバックオフタイマーを減らしていきます．バックオフタイマーが 0 になると，STA はフレームを送信します．2 台以上の STA が同時にフレームを送信すると衝突が発生してしまいます．この衝突をMAC 層の ACK が帰ってこなかったことによって検出した各 STA は，下記の式に従って新しいバック
オフタイマーを計算します．

Backoff time = b24+ 2 rand() 0 1c 2 Slot Timei

ランダムバックオフタイムは整数値をとります．rand は [0; 1] の範囲の一様ランダム変数で，Slot Timeは物理層のパラメータです．STA は衝突が発生するたびに i を 1 つずつ増加させ，そのフレームの送信に成功すると i を 1 にリセットします．この CSMA/CA により，すべての STA は平等に無線チャネルにアクセスする権限を得ることが出来，その無線資源も平等に共有することになります．
DIFS

CW
Data

Source
SIFS
Destination

ACK

DIFS
CW
Other
Backoff started

図 5: Transmission of DATA Packet

2.4 隠れ端末問題
ここまでで CSMA/CA を用いたデータ送信について説明しました．しかし無線 LAN では，距離や壁などの障害物により，ある STA が他の STA の通信を検出できない場合，隠れ端末問題 [10] が発生します．図 6 を用いて隠れ端末問題を説明します．図 6 に示すように，STA1 と STA2 の 2 台の STA と 1台の AP があり，STA1 と STA2 の間に障害物がある (または，距離が離れている) とします．このとき

AP と STA1，AP と STA2 は通信することができますが，STA1 と STA2 の間では電波が到達できず，互いの通信を検知することが出来ません．もし STA1 から AP へデータを送信中に，STA1 の存在を検55

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説
知出来ない STA2 がデータの送信を始めると，AP においてフレームの衝突が発生してしまいます．隠れ端末が存在すると，キャリアセンス機能が有効に機能しないため，CSMA/CA 方式ではフレームの衝突の頻度が増し，スループット特性が悪化してしまいます．

AP

STA 1

STA 2
図 6: 隠れ端末問題

この隠れ端末問題を解決するために，RTS/CTS (Request to Send/Clear To Send) が用いられます．
送信側の STA はバックオフタイマーが 0 になった後，RTS フレームを投げることで無線チャネルを予約します．受信側の STA は RTS フレームを受け取ると CTS フレームを送信側に返します．この CTS
フレームを送信側の STA が受け取ると，STA はデータフレームの送信を始めます．インフラストラク
チャネットワークの場合，すべての STA は AP と接続しているため，AP が送信する RTS または CTS
フレームを検出することが出来ます．RTS または CTS フレームの中にはどのくらいの時間無線チャネ
ルを占有するかが書かれており，各 STA はそれに応じて NAV (Network Allocation Vector) と呼ばれる無線チャネル用のタイマーを設定します．これにより他の STA はいつ無線チャネルがビジー状態からアイドル状態に戻るかを知ることが出来ます．図 7 にこの RTS/CTS を用いたデータ送信を示します．
SIFS

DIFS
Source

Data

RTS
SIFS

Destination

SIFS
ACK

CTS

DIFS
Other

NAV (RTS)
NAV (CTS)CW
Backoff started

NAV (DATA)
Defer Access

図 7: Transmission of DATA Packet using RTS/CTS

2.5 無線 LAN の現状とその問題点

IEEE 802.11a の製品がリリースされ始めた 2001 年当時は，11b と 11a の普及が進むと考えられていました．しかし現在では 2003 年に最終的な標準化を待たずに続々と登場した 11g の普及が急速に進みつつあります．ある調査では各規格毎のシェアについて，2002 年度は 11b が 80%，11a が 18%，11a/g
56

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説が各 1%，2003 年度は 11b が 15%，11a が 5%，11g が 34%，11a/g が 46%としており，今後の主役は

11b から 11g，または 11a と 11g のコンボタイプになると報告しています．
最近ではノート PC に無線 LAN が標準で装備されるようになり，無線 LAN を利用できる端末は急速に増えています．また PC だけでなく，携帯端末に無線 LAN を搭載し，VoIP(Voice over IP) のような音声通信が可能な製品も登場しています．オフィスにおいては PBX から VoIP への移行が進みつつあり，その携帯用端末として無線 LAN による VoIP 通信が可能な携帯端末が注目を浴びています．さらには携帯電話に無線 LAN を搭載する製品も参考ながら展示会等で出展されるようになってきました．このように無線 LAN はその高速なデータ通信を生かして，様々な場所で様々な用途で広く利用され始めています．
このような多様なサービスを無線 LAN で行っていくためには，品質保証を無線 LAN においても行っていく必要があります．しかし無線 LAN の DCF モードでは，STA 間で優先制御を行うことはできず，異なる品質要求を満たすことは出来ません．そこで，IEEE 802.11 の タスクグループ TGe(表 2) がIEEE 802.11e [9] と呼ばれる無線 LAN における通信品質制御に関する標準化を進めています．802.11e
では PCF に似たポーリング機構と，各要求に応じて異なるアクセスクラスを設けることで品質保証を行います．
無線 LAN における品質保証とともに大きな問題となるのは，複数の AP により構築された無線 LAN
網において，STA がどのように AP を選択すればよいかという点です．この点については次節で説明します．

2.6 AP 選択問題

IEEE802.11b では，CSMA/CA による MAC 制御や，最下層の無線フレームによるオーバーヘッドの影響により，実効スループットは 45Mb/s 程度となります．また無線リソースを全 STA で共有する
ため，STA の増加とともに STA ごとのスループットはさらに劣化してしまいます．そのため，1AP 当たりの最大 STA 収容数は 1020 台程度であり，収容可能な STA 数を増加させるためには AP を複数設置する必要があります．IEEE802.11b の場合，混信せずに近傍に設置できる AP 数は最大で 4 つとなります．現在多くの場所で複数の AP を用いた無線 LAN 網構築が進んでいます．
このように AP が複数存在する無線 LAN 網においては，STA が接続する AP を適切に選択することが非常に重要です．図 8 を用いてこの AP 選択問題を説明します．図 8 に示すように，AP が 2 台，STAが 7 台あるとします．AP-1 の近くには 5 台の STA があり，既存の手法では受信電波強度を指標とする
ため，それらの STA は AP-1 に接続し通信を行います．AP-2 の近くにある STA も同様に AP-2 に接続します．結果として AP-1 には 5 台の STA が，AP-2 には 2 台の STA が接続することになります．本章で説明したように，STA は AP が提供する無線資源を平等に共有します．そのため AP-1 に接続する各STA は AP-1 の無線資源の 1=5，AP-2 に接続する各 STA は AP-2 の無線資源の 1=2 を利用することになり，接続先が異なる STA 間で利用できる無線資源が不均衡になってしまいます．このように，STAが AP 間との無線状況のみを指標として接続する AP を選択すると，AP 間の接続 STA 数が偏り，無線リソースを有効かつ公平に利用できなくなってしまいます．

57

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

AP-2

AP-1
STA
STA

STA

STA

STA

STA

STA

図 8: AP 選択問題
SIFS
Sender

RTS

Frame

SIFS
Receiver

SIFS
CTS

ACK

DIFS

NAV(RTS)NAV

NAV(CTS)
Access to medium deferredContention
window

図 9: IEEE802.11b におけるパケット送信シーケンス．
この問題を解決するために AP ごとに異なる ESSID(Extended Service Set-IDenti er) を設定し，静的に接続 STA 数を分配する方法がありますが，これでは STA が AP 間をローミングできなくなり，無線状況が悪くても同じ AP と接続し続けることになってしまいます．そこで本稿では複数の AP が存在する無線 LAN 網において，無線 LAN 資源を公平かつ有効に利用できるように，STA が接続先 AP を自律的に選択する機構を提案します．次の節ではその提案方式で利用した簡単な無線 LAN のスループッ
ト解析を示します．

2.7 スループット 解析

AP が複数存在する無線 LAN 網において，無線リソースを有効かつ公平に利用するためには，STA
は AP ごとに期待できるスループット 8 を事前に予測する必要があります．簡単なスループット 8 は，IEEE802.11b のメディアアクセス方法から以下のように求めることができます．
IEEE802.11b におけるパケット送信シーケンスは図 9 のようになっています [6]． よってデータサイ
ズが Data[bits] のパケットが送受信されるのに要する時間 tT は，式 (1) で表すことができます．
(bits)
tT = RTS +CTS + Data
Rate(b=s)+ ACK +DIFS + 3SIFS + overhead(1)
ここで STA と AP 間の電波状況として，PER(Packet Error Rate) が P であった場合を考えます．この時，一つのパケットが正しく送受信されるのに要する平均時間 Tw は，式 (2) で求めることができます．

T

w

=

t +
T

X1 P 1 (1 0 P ) 1 i 1 t
i

T

i=1

58

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

=

t
10P

(2)

T

よって，スループット 8 は式 (3) となります．

8=

Data = Data 1 (1 0 P )
T
t

(3)

Data 1 (1 0 P )
t 1N

(4)

w

T

また，AP に N 台の STA が接続が接続し，パケットの衝突が発生しないと仮定した場合，スループッ

トは式 (4) となります．

8=

3 AP 選択アルゴリズム機構

T

本章では，前章で述べた問題点を解決するために，複数の AP が存在する無線 LAN 網において，STAが接続する AP を自律的に選択する機構を提案します．
提案機構は，1) 自 STA が最も高いスループットを期待できる AP を最適と判断する throughput-oriented 機構と，2) 他 STA に与える影響を考慮しながら AP を選択する fairness-oriented 機構の 2 種類
です．両提案機構は STA が無線 LAN 網に参加する際と，AP と接続中において定期的に実行されます．
3.1 throughput-oriented 機構

throughput-oriented 機構では，自 STA が最も高いスループットを期待できる AP を最適とします．
そのため事前に全 AP に対してスループットを予測しなければなりません．前章の式 (4) で AP の接続
STA 数が N ，AP との PER が P である場合，期待できるスループット 8 を求めました．このうち STA
がどの AP を選択したとしても tT および Data は同じとすると，式 (5) で表される重み関数の値が最も高くなる AP が STA にとって最適となります．

W = 1 0N P
th

(5)

IEEE802.11b の場合，フレーム中に 1bit でもエラーがあると再送処理が行われるので，BER(Bit Error
Rate) を Pe とした時，P = 1 0 (1 0 Pe)P acketS ize で表わすことができます．この BER は受信電力によって求めることができるので，AP から送信される Probe Response および Beacon フレームに接続
STA 数情報を追加することで，STA は PER と接続 STA 数を得ることができます．
3.2 fairness-oriented 機構

fairness-oriented 機構では，STA は他の STA の通信状況を考慮して最適な AP を選択します．ここでは，無線 LAN 網内において通信状況が最も悪い STA(最悪 STA) に着目し，この特性が更に劣化することを防ぐようにします．すなわち STA は最悪 STA が接続している AP をなるべく選択しないようにします．この機構の重み関数を式 (6)，(7) で定義します． ただし，Pmax は計算対象の AP に接続している STA のうちの最大 P 値です．
59

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

0  1 0 Pmax  0:5 の場合，

W

f air

= (

q

1
2(1 0 Pmax ) + 0:5) 2 Wth
2

(6)

W

(7)

0:5 < 1 0 Pmax  1 の場合，
f air

=

W

th

式 (6) は，Pmax が 1 に近いほど Wf air は小さくなり，STA がその AP と接続しにくくなることを意味します．また式 (7) は最悪 STA を過度に保護するあまり，自 STA にとって条件の悪い AP を選択す
ることのないように，Pmax が 0.5 より小さいときは，fairness-oriented 機構を適用しないことを意図しています．
この機構を実装するためには，PER，接続 STA 数に加えて，Pmax (最悪 STA の PER) が必要となるので，AP から送信される Probe Response および Beacon フレームにはこの情報も付加する必要があります．

4 評価方法
本章では，提案 AP 選択機構の評価方法として，まずシミュレーションモデルについて説明します．
次に有効性を示すための評価指標について説明します．

4.1 シミュレーションモデル
本稿では，シミュレータとして NS-2.1b9a[8] を用いました．また，無線区間のエラーモデルには shad-owing モデルを採用しました．シミュレーションは図 10 に示すネットワーク構成，および表 3 に示すパラメータを用いて行いました．AP 間で干渉することが無いようにチャネルを設定し，合計 4 台の APを図 11 に示すように配置しました．はじめに 40 台の STA を 10 秒間で任意に配置しました．このとき
各 STA は AP 選択アルゴ リズムに従って接続する AP を選択します．最後の STA が配置されてから 3
分後，さらに 10 台の STA を追加しました．STA は常に TCP 通信を行い，配置後は位置を移動しない
ものとします．

250m 内また STA が配置されるエリアを 3 種類用意しました．図 11 で示すように，Area-1 は 50mを表し，STA はこのエリア内に均等に配置されることになります．Area-2，Area-3 においても同様に

STA は均等に配置されますが，エリアの広さがそれぞれ，40m240m，30m230m となります．Area-1
では各 AP の周りに均等に STA が配置されますが，Area-2 では AP-3，4 の周りに配置される STA が少なくなります．Area-3 になるとその効果はより顕著になります．以上を理由に，本稿では Area-1 にSTA が配置される環境を偏りレベル 1 とし，Area-2 ではレベル 2，Area-3 ではレベル 3 と設定しました．偏りレベルが高いほど ，AP 周りの STA 数の偏りが大きくなります．
AP 選択機構には，1)throughput-oriented 機構，2)fairness-oriented 機構に加え，既存の手法である単に無線状況の最も良好な AP を選択する 3)radio-condition-oriented(radio-oriented) 機構を用いました．
60

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

表 3: シミュレーションパラメータ
パラメータ値

TCP/Sack
1500Byte
AP → STA
11Mb/s xed

トラヒックタイプ
パケットサイズ
フローの向き通信速度

Access Point
Flow : from Source to Station
Traffic type : TCP/Sack
Packet size : 1,500 Byte

SourceStationSwitch
10Mb/s10us

100Mb/s
1us

Wired

Wireless

図 10: シミュレーションモデル．
AP-4

Area1:50m*50m

Area2:40m*40m

Area3:30m*30m
AP-2

AP-3

AP-1

10m

図 11: AP の配置図．

4.2 評価指標
提案方式の有効性は，無線 LAN 網内の総スループット，全 STA 中の最小および最大スループット，
全 STA の平均スループット分布に加え，STA 間の公平性を示す指標として，balance index[7] を用いて評価を行いました．balance index とは式 (8) で表されるの値で，1 に近いほど均衡を表し，不均衡になればなるほど 1=N に近づきます．ただし Bi は STAi の平均スループット，N は STA 数を表します．

X B ) =(N 2 X B )

=(

i

2

61

2

i

(8)

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

5 結果および考察
本章では前章で述べたシミュレーションモデルより得られた結果及びその考察を示します．結果については，STA のスループット特性，平均スループット確率分布特性，公平性について評価を行います．

5.1 スループット 特性

6 は 10 台の STA を追加する前における，計 40 台の STA による 3 分間のスループット特性で

表4

す．まず全 STA 中の最低スループットについて考察します．

どの機構においても偏りレベルが高くなるほど ，最低スループットが小さくなっています．radio-

oriented 機構は無線状況が最も良好な AP を選択するという性質上，偏りレベルが高くなると AP 間の接続 STA 数の偏りが大きくなります．よって，radio-oriented 機構は偏りレベル 3 で約 0.15Mb/s まで劣化しています．一方，throughput-oriented および fairness-oriented 機構は AP を選択する際に接続 STA数を考慮しています．このため，偏りレベル 3 でも大きな劣化はみられません．また，fairness-oriented
機構はどの偏りレベルでも他の機構より最小スループットが高くなります．この機構の目的は「最悪STA を保護し，最小スループットを下げない」ことですので，充分に目的を達成しているといえます．
次に全 STA 中の最大スループットについて考察します．radio-oriented 機構は偏りレベルが高くなる
につれ，最大スループットが増大しています．特に偏りレベル 3 でのスループットは約 2.75Mb/s とな
り，他の機構と比較して非常に高くなります．この原因は，接続 STA 数に偏りが生じた時に，接続 STA
数の少ない AP と接続できた STA が無線リソースを独占したためです．しかし，スループットが高い
STA はごく僅かで，大半の STA は接続 STA 数の大きい AP に属すると予測できます．この予測については平均スループット別 STA 数確率分布を 5.2 章で考察する際に確認します．
次に無線 LAN 網の総スループット特性について考察します．どの機構も偏りレベルが高くなると，
総スループットは減少しています．特に偏りレベル 3 において radio-oriented 機構を使用した場合には，著しく性能が劣化しています．このように AP 間の接続 STA 数が偏ると，ネットワーク全体に対して悪影響を与えることがわかります．また偏りレベルが 2 および 3 の場合，fairness-oriented 機構はthroughput-oriented 機構より総スループットが高くなっています．よって偏りレベルが高いときは，総スループットの面で fairness-oriented 機構が有効であるといえます．
以上の結果および考察から，throughput-oriented および fairness-oriented 機構は，偏りレベルが高くなっても AP 間の接続 STA 数が偏る影響を最小限に抑えることが可能であり，有効な機構であることがわかりました．特に fairness-oriented 機構は最小スループットの劣化を抑制し，偏りレベルが高くなると総スループットを改善することができました．

5.2 平均スループット 確率分布特性
図 12

14 は 10 台の STA を追加する前における，計 40 台の STA による 3 分間の平均スループット別

STA 数確率分布です．
まず図 12 の偏りレベルが 1 の場合について考察します．radio-oriented 機構は右裾が長く，他の機構
62

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

表 4: 偏りレベル 1 のスループット特性．
スループットAP 選択機構 最小 (Kb/s) 最大 (Kb/s) 合計 (Mb/s)

radiothroughput
fairness271.47265.71278.80828.87599.72595.26

17.59
17.08
17.03

表 5: 偏りレベル 2 のスループット特性．
スループットAP 選択機構 最小 (Kb/s) 最大 (Kb/s) 合計 (Mb/s)

radiothroughput
fairness

206.52258.74275.791505.56
636.05618.36

17.38
16.56
16.65

表 6: 偏りレベル 3 のスループット特性．
スループットAP 選択機構 最小 (Kb/s) 最大 (Kb/s) 合計 (Mb/s)

radiothroughput
fairness

154.73230.16245.022757.99639.13626.58

13.07
14.48
14.80

と比較して最頻値の小さい確率分布になっています．よって各 AP の接続 STA 数が偏らない環境においても，radio-oriented 機構は他の機構よりも劣っていることがわかります．
同様に図 13，14 から，偏りレベルが 2，3 の場合においても，radio-oriented 機構は最頻値が他の機構と比べて非常に低くなっています．つまり radio-oriented 機構を用いるとスループットが高い STA は
ごく僅かになり，大半の STA は接続 STA 数の大きい AP に属し，スループットが低く抑えられていることがわかります．
また図 14 より， fairness-oriented 機構は最頻値が最も高い確率分布になっています．その効果を図15 で平均スループットに対する生存関数として示します．図 15 より，平均スループットが 350Kb/s の場合 throughput-oriented 機構の生存確率は約 40% であるのに対し，fairness-oriented 機構では約 50%となっており，約 10% 改善されています．
以上の結果から，偏りレベルが 1 の場合であっても throughput-oriented および fairness-oriented 機構が有効であることがわかりました．また偏りレベルが高くなるにつれ，fairness-oriented 機構は throughputoriented 機構よりも高いスループットを得られる STA の割合が多く，有効であることがわかりました．
5.3 公平性特性

18 に平均スループットに対する balance index を次に，STA 間の公平性について評価します．図 16

時系列で示します．どの機構も時刻 180 秒で値が急激に減少しているのは，新たに 10 台の STA が追加されたためであり，その後回復が緩やかであるのは，追加された STA が定常状態に入るまでにある程63

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

probability distribution

0.1

radio-oriented
throughput-oriented
fairness-oriented

0.08
0.06
0.04
0.02
0
0

100 200 300 400 500 600 700 800 900 1000
average throughput [Kb/s]

図 12: 偏りレベル 1 における平均スループット別 STA 数確率分布．

probability distribution

0.1

radio-oriented
throughput-oriented
fairness-oriented

0.08
0.06
0.04
0.02
0
0

100 200 300 400 500 600 700 800 900 1000
average throughput [Kb/s]

図 13: 偏りレベル 2 における平均スループット別 STA 数確率分布．

probability distribution

0.1

radio-oriented
throughput-oriented
fairness-oriented

0.08
0.06
0.04
0.02
0
0

100 200 300 400 500 600 700 800 900 1000
average throughput [Kb/s]

図 14: 偏りレベル 3 における平均スループット別 STA 数確率分布．
1radio-oriented
throughput-oriented
fairness-oriented

0.9

survival function

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
200

250

300 350 400 450 500
average throughput [Kb/s]

550

600

図 15: 偏りレベル 3 での平均スループットに対する生存関数．

64

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説
度の時間を要するためです．radio-oriented 機構は偏りレベルが高くなるにつれ公平性は劣化していますが，その他の機構は高い balance index を維持しています．また 10 台の STA を追加することで無線環境が急変した場合でも，両提案手法の公平性は高い水準を維持しています．よって公平性の面からもthroughput-oriented および fairness-oriented 機構が有効であり，偏りレベルが高くなるほどその有効性が増すことがわかりました．
1balance index

0.8
0.6
0.4
0.2

radio-oriented
throughput-oriented
fairness-oriented

0
0

50

100

150
200
time [sec]

250

300

350

図 16: 偏りレベル 1 での STA 間平均スループットの balance index．
1

balance index

0.8
0.6
0.4
0.2

radio-oriented
throughput-oriented
fairness-oriented

0
0

50

100

150

200

250

300

350

time [sec]図 17: 偏りレベル 2 での STA 間平均スループットの balance index．
1

balance index

0.8
0.6
0.4
0.2

radio-oriented
throughput-oriented
fairness-oriented

0
0

50

100

150
200
time [sec]

250

300

350

図 18: 偏りレベル 3 での STA 間平均スループットの balance index．

65

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

6 まとめ
本稿では，IEEE 802.11 無線 LAN の現状と課題を中心に述べてきました．最初は 2 Mb/s という通信速度からスタートした無線 LAN は，現在では 54Mb/s まで通信速度が向上し，実用的になったことで普及が急速に進んでいます．これまでの有線 LAN を置き換えるだけでなく，無線通信の利点を生かして，ホテルや空港のラウンジ，駅やカフェ等でも無線 LAN の構築が進んでおり，新たに公衆無線 LAN
サービスの提供が始まっています．
この無線 LAN について，現在までに標準化されている各規格や，その基本的な通信方式である CSMA/CAについて 2 章で説明しました．さらには無線 LAN で問題となる隠れ端末問題について説明し，どのように解決しているかについても説明しました．また無線 LAN の現状と課題についても触れ，品質保証と AP 選択が今後の大きな課題であることを示しました．
本稿では触れませんでしたが，上記の 2 つだけでなくセキュリティの確保も重要な課題となっていま
す．現在の無線 LAN で利用されている WEP は固定鍵が短いためその脆弱性が指摘されています．無線は誰でも傍受が可能であるため，通信の暗号化は今後の無線 LAN の発展のために必須の技術であると言えます．さらに暗号化だけでなく，認証も大きな課題です．この点については IEEE 802.1X による RADIUS サーバを利用した認証が考えられています．
無線 LAN のセキュリティについては，無線 LAN を検出できるソフトウェアを用いて山手線を 1 週
し，無線 LAN の利用形態を調査した興味深い報告があります．その報告によれば，山手線を 1 周し終えた時点で全部で 106 カ所の無線 LAN が検出され，このうち、WEP 暗号化が行われていたものはわ
ずかに 37 カ所しかなく，残りの 69 カ所は暗号化を行わない状態で運用されていたとのことです．しかも SSID がメーカー出荷時設定のままになっているケースや，会社名，部署名，設置されている階数といった情報が SSID として使われているケースが多く，情報の漏洩を招きやすい運用を行っている所が多いようです．無線 LAN は誰でも傍受可能な無線を利用して通信を行うため，運用する側も利用する側もセキュリティ対策をとり，通信の安全性を高めていく必要があります．

3 章では複数の AP が設置されている無線 LAN 網において，無線リソースを有効かつ公平に利用するために，STA が自律的に AP を選択する機構を提案しました．ここでは，1) 自 STA のスループットが最大となる AP を選択する throuthput-oriented 機構と，2) スループットが最小である STA が接続している AP をできるだけ選択しないようにする fairness-oriented 機構の 2 つを提案しました．続く 4 章
でそのシミュレーションモデルを示し，5 章でシミュレーション結果より提案方式の評価を行いました．
その結果，STA が無線 LAN 網参加時に提案 AP 選択機構を実行した場合，偏りレベルが高い環境において，両機構とも TCP 総スループットと STA 間の公平性を大きく改善できることを示しました．また fairness-oriented 機構は throughput-oriented 機構と比較して最小スループット特性，公平性のどちらも優れていることがわかりました．
次の課題としては，実機に実装しその効果を確認する必要があります．特に本学は情報コンセントの整備により無線 LAN 網が構築されており，本稿で提案した AP 選択手法の実験環境として適しています．可能であれば実機への実装を進め，本学において提案方式の有効性の確認および評価を進めたいと考えています．

66

九州工業大学 情報科学センター
広報 第 16 号 2004.1

解説

参考文献
[1] IEEE, \Information technology - Telecommunications and information exchange between systems- Local and metropolitan area networks-Speci c requirements - Part 11: Wireless LAN Medium
Access Control (MAC) and Physical Layer (PHY) Speci cations," IEEE Standard 802.11, September 1999.
[2] B. O'Hara and A. Petrick, \802.11 Handbook -A Designer's Companion," IEEE Press, 1999.
[3] I. Papanikos and M. Logothetis, \A Study on Dynamic Load Balance for IEEE 802.11b Wireless
LAN," Proc. 8th International Conference on Advances in Communication & Control, COMCON
8, Rethymna, Crete/Greece, June, 2001.
[4] A. Balachandran, G. M. Voelker, and P. Bahl, \Hot-Spot Congestion Relief in Public-area Wireless
Networks," Proceedings of WMCSA'02, Callicoon, NY, pp. 70{82, June 2002.
[5] Cisco Systems Web Site,\Cisco Aironet Series 製品機能紹介,"
http://www.cisco.com/japanese/warp/public/3/jp/solution smbiz/aironet/solutions/solution1.html[6] Gast and Matthew，\802.11 Wireless Networks:The De nitive Guide," O'REILLY, 2002.
[7] Dah-Ming Chiu and Raj Jain, \Analysis of the Increase and Decrease Algorithms for Congestion
Avoidance in Computer Networks," Computer Networks and ISDN Systems, vol. 17, pp. 1{14,1989.
[8] The VINT Project, Network Simulator NS,
http://www.isi.edu/nsnam/ns/.
[9] IEEE, \Draft Supplement to STANDARD for information technology - Telecommunications andinformation exchange between systems - Local and metropolitan area networks - Speci c requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY)
Speci cations: Medium Access Control (MAC) Enhancement for Quality of Service (QoS)," IEEE
Standard 802.11e/D3.3, October 2002.
[10] A. S. Tanenbaum Ed., \Computer Networks - Third Edition," Prentice-Hall International 1999.

67

九州工業大学 情報科学センター
広報 第 16 号 2004.1