無線通信ネットワークにおける結合スケジューリングによる遅延評価
M2012MM048 山本裕哉
指導教員：河野浩之

1

はじめにが低くなってしまうことに問題がある．

無線通信網においてマルチユーザダイバーシチを利用 2.2 Knopp and Humblet(KH) スケジューリング
することでチャネル容量を増加させることができること
KH スケジューリングは，現時点で最も SNR 値が高いが知られている．そのため近年，無線ネットワークにおMS にサービスを行うスケジューリング方式である．KH
いてマルチユーザダイバーシチを使用したパケットスケスケジューリングは RR スケジューリングとは正反対でマジューリングの研究が盛んに行われている [1]．
ルチユーザダイバーシチを最大限に利用したスケジュー
マルチユーザダイバーシチは，チャネル変動が独立なリング方式となる．KH スケジューリングでは，常に MS複数のユーザが存在する中で，任意の時間で一部のユーの中で最高のチャネル容量を持つ MS にサービスを行う
ザがほかのユーザに比べて良好なチャネル利得を持つこので，システム全体のチャネル容量は大きくなる．しかとから発生するダイバーシチである．しかし，帯域の効しながら，無線リンク状態の悪いユーザが選ばれる確率率的利用だけでは，各ユーザの要求する要求するサービが非常に低くなってしまうためユーザ間の公平性に深刻
ス品質 (Quality of Service，QoS) を満足させるとは言えな問題がある．
ない．マルチユーザダイバーシチを利用したスケジューリングには，システム全体のチャネル容量と各ユーザへ 2.3 Proportional Fair(PF) スケジューリングの公平性の間にトレードオフがあり，その両立が非常にPF スケジューリングは，各 MS の SNR 値をその MS重要となってくる [2]．の平均 SNR 値で正規化し，正規化された SNR 値の最も本研究では無線通信ネットワークにおけるマルチユーザ 高い MS をサービスのために選択する方法である．各 MS
ダイバーシチを利用したパケットスケジューリングに焦点 の SNR 値は独立同一分布 (independent and identicallyをあてる．特に Adaptive Modulation and Coding(AMC) distributed) に従うので, 各ユーザに公平にサービスを提が実装されている結合スケジューリングが行われている 供することが可能になり，かつチャネル容量もマルチユーセルラ無線通信ネットワークを想定し，パケットの待ち ザダイバーシチを全く利用していない RR スケジューリ
行列遅延に関するシミュレーションを行う．本研究では， ングと比べると大きくなることが知られている．しかしRound Robin スケジューリングと One-bit Feedback Fair PF スケジューリングでは各 MS が Base Station(BS) にスケジューリングを組み合わせたものを結合スケジュー 正規化 SNR 値を報告することが必要であり，そのためにリングと呼ぶ [4]．シミュレーション結果を元に結合スケ 帯域と MS の電力を消費するという問題がある．
ジューリング下のパケットの遅延確率を求めテイル分布
2.4 Quantized Proportional Fair(QPF) スケジの性質を調査する．
ューリング
本稿の第 2 節では先行研究として行われているスケジQPF スケジューリングは，PF スケジューリングの問題ューリングについてのスケジューリング方式，利点，欠点について記述する．第 3 節では本研究で使用するシステ を解決するために考えられたスケジューリングである．正ムモデルについて述べる．結合スケジューリング，AMC 規化した SNR 値を BS に報告するのではなく，量子化さモデル，到着プロセス，マルコフ連鎖モデルについて記 れた正規化 SNR 値を表すビットを BS に報告すればよい
述する．第 4 節ではシミュレーションについて述べる．パ ので帯域の消費を抑えることが出来る．正規化した SNR
ケット遅延確率を求めるシミュレーションモデルを記述 値を量子化することによって平均チャネル容量に大きくし性能評価を行う．第 5 節ではまとめについて述べる． 影響する可能性が考えられるが，適切な量子化を行うことによって遜色のないチャネル容量を達成できることが2 先行研究知られている．
2.1 Round-Robin(RR) スケジューリング
2.5 One-bit Feedback Fair(1FF) スケジューリング
RR スケジューリングは，マルチユーザダイバーシチを1FF スケジューリングは，QPF スケジューリングの量まったく利用せず Mobile Station(MS) の Signal-to-Noise
子化を 2 状態にしたスケジューリング方式である [5]．MS
Ratio(SNR) 値に関係なく各 MS を順番にサービスを行は 2 状態に量子化した正規化 SNR 値が任意の閾値を越うスケジューリング方式である．RR スケジューリング
えていれば BS に通知し，BS は閾値を越えた MS をラン
では，各 MS を順番にサービスするため公平性は優れてダムに選択しサービスを行い，さらに各 MS が送信するいるがが，マルチユーザダイバーシチをまったく利用せ情報は 1bit のみに限られるので帯域の消費を減らすことず, 各ユーザの無線チャネル状態の良し悪しも考慮せずにができる．1FF スケジューリングは長期間で見ると非常サービスを提供するため，システム全体のチャネル容量に優れているが短期間で見た場合同じ MS ばかり選んでしまい公平性に欠ける恐れがある．

3モデル

3.1

結合スケジューリング

本研究では 1FF スケジューリングと RR スケジューリン
グを組み合わせたスケジューリング方式を結合スケジューリングと呼ぶ．結合スケジューリングの内容を特定するためには，フレーム中の何番目のスロットが 1FF スケジューリングであるか，または RR スケジューリングであるのかを特定する必要がある．また RR スケジューリングの場合，何番目の MS へのサービスを行うのか決定する必要がある．このときフレーム中の n 番目のスロットでどのようなスケジューリング方式が行われるかを表したも−1のがサービス列 {mn }Tn=0である．条件として限状態マルコフ連鎖モデルの状態空間を {0,. . . , L − 1} とし，pi,j (0,. . .,L − 1) を有限マルコフ連鎖の状態 i から状態 j への遷移確率とする．このときタイムスロット Tf はかなり短い時間で設定されるものとして扱うので２つ以上先の状態に遷移することがないことが言える．これにより式 (1) を定義することができる．

pi,j = 0,|i − j| ≥ 2(1)を得る．次に隣接した状態の遷移確率について定める．状態が 1 つ上の状態に遷移する確率は，式 (2) と定義される．

pi,i+1 =χ(γi+1 )Tf,
πii = 0, . . . , L − 2(2)状態が隣接した 1 つ下の状態に遷移する確率は，式 (3) と定義される．

• mn = 0 のときは 1FF スケジューリングが行わる．

χ(γi )Tf
pi,i−1 =,i = 1, . . . , L − 1(3)• mn > 0 のときは RR スケジューリングが行われる．
πi
また mn > 0 のときは，mn 番目の MS へのサービ
ここでの χ(γ) は Nakagami-m モデルでのタイムスロットスが行われるものとする．
ごとの SNR 値 γ のレベルクロスレートを表しており式3.2 システムモデル(4) があたえられる．
()√γγ
χ(γ) = fd 2π exp −(4)γγ
ここで fd はドップラー拡散周波数であり，γ = E[γ] は受信した SNR 値の平均値である．また πi (i ∈ L) は有限状態マルコフ連鎖モデルにおける状態 i の時の定常確率を表している．πi (i ∈ L) は以下の式 (5) で得られる．

πi = exp(−γi /γ) − exp(−γi+1 /γ)(5)pi,j は確率であるため ΣL−1
j=0 pi,j = 1 である．式 (1) -式
L−1(3) と Σj=0 pi,j = 1 より状態が遷移しない確率を得ることができ式 (6) に示している [1]．

1 − pi,i+1 − pi,i−1

図 1 セルラ無線通信ネットワーク

pi,j =
本稿では，システムモデルとして図 1 で示されるセルラ無線通信ネットワークを考える．1 個の BS に対して K個の MS で構成される下り通信 (ダウンリンクチャネル)システムによって行う．K 個の MS から選ばれた MS がスケジューリングを受けサービス先の MS へと通信を行う．また１タイムスロットあたりを Tf とし，時間はタイムスロット間隔に分割されており，すべての動作はタイムスロットと同期して行われるものとする．

3.3

有限状態マルコフ連鎖モデル

本研究では各 MS の正規化された SNR 値の確率過程
は Nakagami-m モデルの一つで m = 1 の場合のレイリーフェージングチャネルに従って記述できるものとする．まず，k (k = 1,. . . , K) 番目のユーザの n スロット時の SNR(k)値を {Zn }∞n=0 と定義する．さらにその SNR 値を正規化した値を L 個のチャネルグレードに分割する．次に有1 − pi,i+11 − pi,i−1(i = 1, . . . , L − 2)(i = 0)(6)(i = L − 1)

ここで正規化 SNR 値を 0 と 1 に量子化することによって2 状態マルコフ連鎖とし，これによってうまく近似されると仮定して式の変形を行うと，正規化 SNR 値が閾値より下の範囲に留まる確率は，p0,0 = 1 − p0,1(7)となり，正規化 SNR 値が閾値より上の範囲に留まる確率は，p1,1 = 1 − p1,0(8)となる．(7)，(8) 式の値は共に 0 以上 1 以下の値である．

3.4

Adaptive Modulation and Coding

AMC とは，無線状態に応じて変調方式や符号化式，及びその他の信号等を調整する仕組みのことである．AMCの信号やパラメータは無線状態が変わるにつれて変化する．無線状態の良い環境では高いデータレートでサービス提供し，無線状態の悪い環境では確実にデータが届くように低い変調方式を使用する．本研究では文献 [3] で利用されている AMC が使われているものと仮定する．タイムスロットごとに状態が変化するものとし 8 段階のモードがある AMC モデルを利用する．Rate はタイムスロットごとに送信できるパケット数を表している．
3.5

到着プロセス

本研究では，パケットの到着は ON-OFF ソースによって生成されると仮定する．ON-OFF ソースは，ON 状態，OFF 状態の 2 つの異なる状態を持っている．OFF 状態ではパケットが発生しないものとし，ON 状態の時は確率 λ
図 2 テイル分布を求めるプログラムの流れで 1 パケット発生するものとする．ON 状態の時に OFF状態に遷移する確率を 1 − α と定義し，OFF 状態の時にON 状態に遷移する確率を 1 − β と定義する．ただしこの ロセスにおいて ON 状態を維持する確率，β は到着プロ
時 α，β の値の範囲は，それぞれ 0 ≤ α ≤ 1，0 ≤ β ≤ 1 セスにおいて OFF 状態を維持する確率，λ は ON 状態のである．このように本研究で考える ON-OFF ソースモデ 時に 1 パケット発生する確率，γ は平均 SNR 値をそれぞ
ルは，α，β ，λ の 3 つのパラメータで記述される．
れ表している．また AMC モデルは文献 [3] の値を使用す
ON-OFF ソースの 3 つのパラメータ α，β ，λ により る．
Bon ，Bof f ，ρ を表すことができる．Bon は ON 状態を維持する平均時間，Bof f は OFF 状態を維持する平均時
表 1 β の変化による状態の設定
間，ρ は平均到着レートをパラメータとして考える場合，
状態
パラメータ
元の 3 つのパラメータとの関係は式 (9) で与えられる．

Bon =

11
λ(1 − β), Bof f =,ρ =1−α1−β2−α−β4

シミュレーション

4.1

実験環境

123(9)

シミュレーションを行うプログラムの作成には，Matlabを使用する．プログラムの流れとして，

γ=16(dB),λ=0.20,α=0.900,β=0.500
γ=16(dB),λ=0.20,α=0.900,β=0.800
γ=16(dB),λ=0.20,α=0.900,β=0.992

表 1 のようなネットワーク環境でシミュレーションを 100回行い遅延時間の平均の結果を図 3 に示す．
010

1. パケットが到着したか否かを審査する．また，パケットが到着した場合その時間を記録する．

3. サービスを受けたときそのパケットの遅延時間を記録する．

probability

2. パケットがキューにある場合そのパケットがサービスを受けるか審査する．

0.5
0.8
0.992

4. シミュレーションが終わったとき記録した全ての遅延時間の平均を求め，テイル分布を求める．
図 2 にプログラムの流れを示す．
04.2

シミュレーション結果

100200300

400

delay time slot (msec)

シミュレーションは，β の値を変化させパラメータを
図 3 β の値の変化の結果3 つの状態でそれぞれ行った．また，Tf (タイムスロット)=0.001(sec)，fd (ドップラー拡散周波数)=10(Hz)，図 3 の結果より，β の値が 0.8 から 0.992 にかけて急激γ̂(量子化の閾値)=2.0(dB)，MS の数は 10 個は全てのパに遅延の起こる確率が小さくなっており，比較したときラメータに対して共通のものとする．また表 1 に β の値0.992 の方が 75% 遅延の起こる確率が低くなることからを変化させた状態 1〜3 のパラメータを示す．α は到着プ
β は遅延の起こる確率に大きく影響していることがわかった．次にどのような時に β の値が適切かの調査を行った． の値を 0.975 以上に設定することが望ましいとシミュレー
今回行ったのは，データ通信の場合とリアルタイム通信 ションの結果よりわかった．セルラ無線通信ネットワーの場合の調査を行った．図 4 に，データ通信の場合のシ クに結合スケジューリングを導入する場合，α が 0.900 のミュレーションによって推定された結果を，図 5 に，リ 時，データ通信は β の値を 0.925 以上のとき，チャネル容アルタイム通信の場合のシミュレーションによって推定 量を高く，ユーザ間の公平性も高くすることができ，リされた結果を示す．図 4 と図 5 の横軸は β の値の大きさ， アルタイム通信の場合は β の値を 0.975 以上のとき，音縦軸は遅延確率を表す．
声通信などの品質を保つことができると考えられる．

5-0.1

probability

10-0.310-0.510-0.7100.2

0.4

0.60.81arrival process(β)

図 4 データ通信の場合のシミュレーション

probability

データ通信の場合，遅延時間を 1000msec 以内にするのが一般的であるので図 4 の結果は，1000msec 以上の遅延が起こる確率を調査したものである．図 4 より，β の値が0.825 あたりから急激に遅延の起こる確率が低くなっていき 0.925 以降はあまり遅延の起こる確率に変化がないとわかった．よってデータ通信の場合 β の値が 0.925 以上のとき，QoS が保障されるとシミュレーションによりわかった．しかし今回は，α を 0.900，λ を 0.2 に固定した場合だが，α を 0.9 以下に下げた場合 β の値は 0.925 よりも下回ることが考えられる．

おわりに

本研究ではマルチユーザダイバーシチを利用したスケジューリングに着目し，1FF スケジューリングと RR スケジューリングを組み合わせた結合スケジューリングを用いたセルラ無線通信ネットワークを想定し，そのネットワークにおけるパケットの待ち行列遅延のテイル分布をシミュレーションで調査を行った．正規化 SNR 値の変化を表す確率過程はレイリーフェージングチャネルを採用し 2 状態の有限マルコフ連鎖で近似されるものとした．
本研究では，結合スケジューリングのテイル分布を性質を調査するため β の値を変更しシミュレーションを行った．これにより結合スケジューリングによるパケットの待ち行列遅延時間を計算するモデルからシミュレーション結果を得ることが出来た．シミュレーション結果より，
β の値が結合スケジューリングの性能に大きく影響することがわかった．セルラ無線通信ネットワークに結合スケジューリングを導入する場合，α が 0.900 の時，データ通信は β の値が 0.925 以上のとき，チャネル容量を高く，ユーザ間の公平性も高くすることができ，リアルタイム通信の場合は β の値が 0.975 以上のとき音声通信などの品質を保つことができると考えられる．

参考文献[1] F. Ishizaki and G. U. Hwang, “Queuing delay analysis for packet schedulers with/without multiuser
diversity over a fading channel,” IEEE Trans. Veh.
Technol., Vol.56, No.5, pp.3220–3227, 2007.
[2] L. Yang, M. Kang, and M.-S. Alouini, “On thecapacity-fairness tradeoﬀ in multiuser diversity systems,” IEEE Trans. Veh. Technol., Vol.56, No.4,pp.1901–1907, 2007.

-0.1

10

[3] F. Ishizaki and G. U. Hwang, “ Cross-layer designand analysis of wireless networks using the eﬀective
bandwidth function,” IEEE Trans. Wireless Commun., Vol.6, No.6, pp. 3214–3219, 2007.

-0.2

100.2

0.4

0.6

0.8

1

arrival process(β)

図 5 リアルタイムの場合のシミュレーション
リアルタイム通信の場合，遅延時間を 150msec 以内にするのが一般的であるので図 5 の結果は，150msec 以上の遅延が起こる確率を調査したものである．図 5 より，データ通信の場合と同様に β の値が 0.825 あたりから急激に遅延の起こる確率が低くなっていきそれ以降も急激に遅延確率は下がっていくので，リアルタイム通信の場合は β[4] F. Ishizaki, “Studies on the Short Term Fairness
Properties of Joint Scheduler,” International Journal of Interdisciplinary Telecommunications andNetworking Vol.4, Issue 3, pp. 23–39, 2012.
[5] O. Somekh, A. M. Haimovich and Y. Bar-Ness,“Sum-rate analysis of downlink channels with 1-bit
feedback,” IEEE Commun. Letters, Vol.11, No.2,
pp.137–139, 2007.