稠密環境における最適化衝突回避アクセス制御方式を用いた高効率伝送の研
究開発
代表研究者
共同研究者

松田 崇弘
平栗 健史
梅原 大祐

大阪大学 大学大学院工学研究科 准教授
日本工業大学 工学部 教授
京都工芸繊維大学 情報工学・人間科学系教授

1 研究開発の概要
無線 LAN の伝送において，ユーザ数およびトラヒック増加に伴うパケット衝突は，伝送効率を低下させる大きな課題の一つである．これまでに，無線 LAN のアクセス制御である CSMA/CA (Carrier Sense Multiple
Access with Collision Avoidance) 方式において，バックオフ（Backoff）アルゴリズムに用いられる CW（Contention Window）サイズのパラメータを接続端末数に応じて最適に選定する衝突回避（CollisionAvoidance）制御方式を提案し，計算機シミュレーションおよび Markov chain[1][2]型の確率モデルに基づく理論解析によってその効果を評価してきた．この衝突回避制御方式に対し，先行研究では計算機シミュレーションと理論解析の結果を比較し，ほぼ一致した結果が得られている．提案方式は，一つの基地局の通信範囲内に最大 80 台程度の無線端末が存在する稠密環境において，従来方式の CSMA/CA では伝送容量の 55％程度のスループットしか達成できないのに対し，90％以上のスループットを実現できる．
本研究では，提案方式を無線デバイスに実装し，実験による評価をおこなった．無線デバイスは，RaspberryPi[*]に無線のアダプタを装着する．Raspberry Pi 内臓のソフトウェアによりアクセス制御を改造し，提案方式が実装された基地局および端末を試作することによって，ネットワークを構築した．当該ネットワークを用いて実験の結果，全体的なスループットは処理能力の影響により低下するものの，提案方式と傾向はほぼ一致し，高い伝送効率が得られることを確認した．

2 背景
IEEE802.11[3]で標準規格化された無線 LAN システムは，スマートフォン，音楽プレーヤー，ゲーム機などの様々な通信機器に使用され，利用ユーザ数が急速に増えるとともに，トラヒック量も増加している．
無線 LAN は，複数のユーザで帯域をシェアするために，アクセス制御技術として CSMA/CA(Carrier Sense
Multiple Access with Collision Avoidance)方式が採用されている．この CSMA/CA 方式ではパケットを送信する際，各端末でランダム時間のキャリアセンスを行うバックオフ手順を用いることにより，パケット同士の衝突を回避する制御が行なわれる．しかし，多数の端末が同じタイミングでパケットを送信する場合に，ランダム時間であるキャリアセンスが偶然同じ時間に設定される可能性があり，この場合には衝突が生じる．
特に，端末数が多い高密度環境で，さらにトラヒック量が増加した場合には衝突確率も増加し，伝送効率が急激に低下する課題がある[4][5]．
無線 LAN の伝送効率を低下させる主な要因として，MAC（Medium Access Control）層におけるパケットヘッダや，パケット衝突とそれに伴う再送制御によるオーバヘッドが挙げられる．CSMA/CA 方式では，衝突が頻繁に発生すると，無用なパケット送信と ACK（確認応答）の待ち時間がオーバヘッドとなる．参考文献[4][5]では，再送制御によるオーバヘッドを削減するために，衝突検知（Collision Detection）機能をもつアクセス制御方式が提案されており，パケットのデータ部分（ペイロード）を送信する前に，衝突を検出することにより ACK 待ち時間などを省き，即座に再送制御を行うことを実現している．この提案方式は，輻輳時にも高いスループットが得られることが確認されている．しかし，そもそも再送制御によるオーバヘッドが発生する原因は，パケットが衝突することである．さらに伝送効率を改善するためには，パケットの衝突確率を軽減することが有効であると考えられる．従来の無線 LAN では，標準規格で定められた CSMA/CA 方式のバックオフ手順を用いているが，このバックオフで設定されるパラメータは，端末数やトラヒック量などのネットワーク環境を考慮した最適なパラメータが設定されているわけではないため，十分な伝送効率を得られない課題がある．
この課題を解決するために，先行研究 [6]では，従来の CSMA/CA 方式のバックオフアルゴリズムに用いられる CW（Contention Window）サイズのパラメータを接続端末数に応じて選定することにより，輻輳時にお1（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

いてもパケット衝突を軽減する衝突回避制御方式を提案し，計算機シミュレーションを用いて，提案方式の性能評価を行った．これらの評価結果から，良好な伝送効率が得られることを確認した．さらに，確率モデ
ルの Markov chain を用い，提案方式の効果を理論解析により確認を行い，計算機シミュレーションの結果と比較し，ほぼ一致した結果が得られた．
本報告では，提案方式を，無線デバイスに実装し，実験による評価をおこなった．無線デバイスは，Raspberry Pi[7]に無線のアダプタを装着する．Raspberry Pi のソフトウェアによりアクセス制御を改造し，提案方式が実装された基地局および端末を試作することによって，ネットワークを構築した．実験に得られた結果は，計算機シミュレーションの結果とほぼ一致したことから，提案方式の妥当性が確認できた

3 従来方式の課題と提案方式の効果
CSMA/CA 方式では，各端末はチャネルが Busy の場合に送信を待機し，チャネルが Idle 状態になったとき，キャリアセンスを行い，パケットを送信する．チャネルが Idle となると，各端末は，DIFS（Distributed Inter-FrameSpace）と呼ばれる一定時間のキャリアセンスの後，乱数を発生させ，発生させた乱数に応じたランダム時間のキャリアセンスを実施する．これをバックオフアルゴリズムと呼んでいる．乱数の範囲は 0 から CW の範囲で生成されるランダムの整数である．CW の値は可変の正数値で，最小範囲のサイズ CWmin から，最大範囲のサイズ CWmax から選ばれる．この CW サイズは，例えば 5GHz 帯を用いる IEEE802.11a 規格では，CWmin＝15，CWmax＝1023であり，初送信では CWmin＝15 の範囲から始まり，パケットが衝突や干渉により，再送信を行う毎に 2 倍ずつ増加していく．CW の上限値が CWmax となった場合には，再送回数オーバの制限に達するまで，CWmax＝1023 が用いられる．複数の端末が送信前に，この CW サイズの範囲で乱数を引き，複数の端末の中で最も小さい値を引いた端末が最初にパケットを送信することができる．その他の送信端末は，引いた値の残った時間を次のパケット送信に持ち越す．すなわち，もし CW サイズから引いた値が，送信端末数と同じであった場合には，パケットを同時送信する端末が必ず存在するので衝突が発生することとなる．衝突が発生すると，再送制御に移り， CW サイズは再送の度に 2倍ずつ増えていくため，バックオフアルゴリズムを用いた再送制御は衝突確率を減らす効果がある．また，CW サイズが 2 倍ずつ増加していくことから，この制御方法は 2 進数バックオフとも呼ばれている．
このように，従来の CSMA/CA 方式には，衝突が発生した場合に 2 進数バックオフにより再送信の衝突確率を下げることで，伝送効率を上げる効果がある．IEEE802.11a 規格では，CWmin は 15 と定められているので，接続端末数が 15 台未満の場合は，送信が成功可能性はあるが，端末数が 15 台以上に増加すると，同じ CW の乱数を選択する端末が急増するので，頻繁に衝突が発生することになる．衝突が生じた場合には，端末自身では衝突を検知できないため，パケットのペイロード（データ）を全て送信し，宛先の無線局から ACK（Acknowledgement）の返信が無いことで，衝突が発生したことを判定する．その後，再送制御に移行する．この衝突を認知するまでの時間はオーバヘッドとなり，伝送効率の低下が生じる課題となる．
この課題を解決するために，最適化衝突回避アクセス制御方式を提案する．この提案方式は，接続端末数が多い場合でも衝突する確率を減らすために，接続端末数に応じた最適な CW サイズを選択する．この最適な CW サイズは，送信端末数に応じた固定値で，再送時にも 2 進数バックオフを行わない固定 CW サイズである．提案方式の評価は，先行研究において，計算機シミュレーションによってその効果を確認した．
固定 CW サイズは，従来の CSMA/CA 方式と比較評価を行っている．伝送レートは 24Mbps とし，接続端末数は，1～80 台まで変化させた．その他のパラメータは，IEEE802.11a 準拠である．トラヒックはアップリンクのみ UDP(User Datagram Protocol)で発生させ，衝突が頻繁に生じる無線環境とするため，パケットが常にバッファに存在するよう設定している．また，パケットサイズは Ethernet フレーム最大サイズの 1500byte とした．スループット特性の評価結果を図 1 に，シミュレーションの諸元を表 1 に示す．横軸は端末数，縦軸は全端末からの総スループットである．
従来の CSMA/CA 方式では，端末数が増加するとスループットは低下する． 一方，提案方式の固定 CW サイズの場合は，接続端末数が増えるとスループットは高くなるが，ある端末台数をピークに減少する結果が得られている．例
えば，CW サイズが 127 の場合には，接続端末数が 20 台以上になるとスループットは低下するが，接続端末数 10台のときには CSMA/CA 方式よりスループットが高いことが確認できる．これは，CW サイズを固定とした場合，CW サイズが大きくなるとバックオフに費やす時間が増大するため，接続端末数が少ない場合にはスループットが低下するが，一方で衝突確率が低くなるため接続端末数の増加によりスループットが向上したと考えられる．ただし，接続端末増加に伴い衝突確率も増加していくため，ある接続端末数をピークにスループットが減少する．したがって，固定 CWサイズ毎に最適な接続端末数が存在すると考えられる．これらの結果により，接続端末数に対応した最大のスループットが得られる CW を，最適固定 CW とし，これらを表 2 にまとめた．端末台数：10 台では CW：127，20～30 台ではCW：255，40～50 台では CW：511，それ以上は CW：1023 とし，10 台以下は従来の CSMA/CA の CW パラメータ2（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

を用いることとする，すなわち，衝突/再送によって CW の範囲を変更すること無く，接続端末数に応じて，表 1 の最適固定 CW を設定する．

図 1 固定 CW に対するスループット特性
表 1 シミュレーション諸元
パラメータ

設定値

伝送速度
パケットサイズ
CW サイズ

24 Mbit/s
1500 byte
15,31,63,127,255,1023

表 2 最適固定 CW パラメータ

4 実験条件および実験結果
これまでのシミュレーション結果の妥当性を確認するため，提案方式をハードウェアに実装し，実験による評価をおこなった．本実験のハードウェアは，Raspberry Pi3 Model B を使用する．Raspberry Pi3 Model B のスペックは表 3 に示す．OS は，Debian ベースの Raspberry Pi 用 OS であり，バージョンは Raspbian 8.0 を使用した．
実験機器の無線デバイスとして子機端末（STA）に Raspberry の 内蔵無線 LAN チップを使用し，親機の端末（AP）には，USB 接続の外付け Wi-Fi ドングルを使用した．また，Raspberry を無線 LAN アクセスポイントとして動作させるため，hostapd 2.3 を導入した．CW サイズの変更はこの hostapd を利用する．表 4 に実験の諸元を示す．使用周波数帯は 2.4GHz 帯を使用し，チャネルは 4ch.を使用した．物理層の伝送レートは 24Mbit/sec の固定値とし，帯域幅は 20MHz である．また，トラヒックの生成には，iperf 2.0.5 [8]を使用し，STA 数は，1 台から18 台まで増加させた際に，1470 byte のパケットサイズを UDP により連続的に 30 秒間発生させた．全 STA で，帯域を飽和トラヒック状態にし，無線 LAN システム全体のスループット特性を評価した．図 2 に本実験の端末配置を示す．図 4 に示すように，実験は電波暗室内で行い，各 STA 間の距離は最低 50 cm 以上とし，AP と最も近いSTA 間との距離も 50cm 以上とした．また，AP から STA 間の距離が最も遠いもので 3m 以内とした．実験においてリモート SSH（Secure Shell）のトラフィックと干渉が発生しないよう，Raspberry Pi 3 の操作は別途接続したイーサネットを介して行う．なお，イーサネット接続には無線接続と異なる IP を使用する．

3（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

実験結果を図 5 に示す．横軸が端末台数，縦軸が無線システム全体のスループットである．実線の緑が提案方式のシミュレーション結果，紫が従来方式のシミュレーション結果である．また，プロットを繋いだ青線は，提案方式の実験結果，赤線が従来方式の実験結果である．実験結果とシミュレーション結果と比較し，実験結果は全体的にスループットが低下しているものの，概ねスループット特性の傾向が一致している．また端末台数が増加するに従って，提案方式と従来方式ではスループット特性に差がみられることから，実験結果においても提案方式の有効性を確認できた．実験結果がシミュレーション結果より低下している理由は，Raspberry Pi のハードウェアに，トラヒック生成およびスループット特性評価のためのソフトウェア iperf を実装しており，これらの処理能力が十分でなかったため，計算機シミュレーションと同等のパフォーマンスが得られなかったと考えられる．
表3

Raspberry Pi3 Model B スペック

CPU

1.2 GHz Quad Cortex-A53

Memory1GB DDR2 450MHzOS

RaspbianSize

85 × 56 × 17mm

Ethernet

10/100 Base-T

WLAN

IEEE 802.11 b/g/n 2.4GHz

USB

USB 2.0600cm

240cm

STA 50cm~50cm~
AP

図 2 実験構成

4（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

図４ 伝搬暗室内での配置例
表 4 実験条件諸元
WLAN Band

2.4 GHzWLAN Channel

4 CH

PHY rate

24 Mbit/s

Number of STAs

1-18

Band width

20 MHzData size

1470 byte

Measurement time

30 sec

図 5 端末台数に対するスループット特性の比較

5（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

5 まとめ先行研究では，トラヒックを発生する端末数が増加するとパケットの衝突が頻繁に生じ，伝送効率が低下する課題を解決するために，最適な CW サイズのパラメータを端末数に応じて選定し，衝突確率を低減する衝突回避 制御方式を提案してきた．また先行研究で求められた計算機シミュレーションによる最適な CW サイズを用い，確率モデルの Markov chain によって，提案方式の理論解析による確認を行った．理論解析は計算機シミュレーションとほぼ一致した結果が得られることで，提案方式の有効性を確認した．
本研究では，最適な CW サイズのパラメータを実機（Raspberry Pi）に設定し，実験による評価を行い，提案方式の効果を確認した．実験結果では，提案方式の計算機シミュレータによるスループット特性と傾向がほぼ同じ結果が得られたが，全体のスループットが低下してしまった．この原因としては， Raspberry Piの処理能力が十分で無かったことが考えられるため，今後は，ノート PC などの処理能力が高いハードウェアに実装し，確認を行う予定である．また，最適な CW サイズは，実験の簡易化のため，シミュレーションで得られたパラメータを端末に応じて固定で使用したが，提案方式の実用化を目指し，今後は，接続端末台数や伝搬チャネル状況（Busy 情報）を取得する機能を追加し，動的に提案方式が動作するよう検討を進めていく予定である．

【参考文献】[1] G. Bianchi, “Performance analysis of the IEEE802.11 distributed coordination function, ”
IEEE Journal on Selected Areas in Communications, vol. 18, no. 3, pp. 535-547, Mar. 2000.
[2] G Bianchi, I Tinnirello, “Remarks on IEEE 802.11 DCF performance analysis, ” IEEE Commun.
Letters vol. 9, no. 8, pp. 765-767, Aug. 2005.
[3] IEEE802.11 Standard for Local and Metropolitan Area Networks Part 11: Wireless LAN Medium AccessControl (MAC) and Physical Layer (PHY) Specifications, Mar. 2012.
[4] 森野善明, 平栗健史，小川知将，西森健太郎，吉野秀明,“MIMO 伝送を用いた Collision Detection ア
クセス制御方式の理論解析, ” 信学技報, vol. 113, no. 361, RCS2013-219, pp. 77-81,2013 年 12 月.
[5] T. Hiraguri，K. Nishimori，T. Ogawa，R. Kataoka，H. Yoshino and H. Makino，"Access control
scheme for collision detection utilizing MIMO transmission," IEICE Communications Express，
Vol.2，No.4，pp.129-134，April 2013．
[6] Y. Morino, T. Hiraguri, H. Yoshino, and K. Nishimori，”Theoretical analysis of collision detection
scheme utilizing MIMO frame structure, ” IEICE Communications Express，Vol.4, No.2, 61-66，
Feb. 2015．
[7] Raspberry Pi, https://www.raspberrypi.org/.
[8] A. Tirumala, F. Qin, J. Dugan, J. Ferguson, K. Gibbs, Iperf - The TCP/UDP bandwidth
measurement tool, available: https://iperf.fr/.

〈発題名表資料〉

掲載誌・学会名等

A Novel Collision Avoidance
IEICE Transactions on
Scheme Using Optimized Contention
Communications, vol. E99-B,
Window in Dense Wireless LAN
no. 11, pp. 2426-2434,
Environments
無 線 LAN に お け る Collision
電子情報通信学会技術報告,
Avoidance 制御方式の実験評価
vol.
116,
no.
497,
CQ2016-127, pp. 93-96

発表年月2016 年 11 月

2017 年 3 月

6（公財）電気通信普及財団 研究調査助成報告書 No.32 2017