1FF スケジューリングにおけるパケットの待ち行列遅延に関する研究

2008MI126 松原 正悟

2008MI139 水野 陽介
指導教員

1 はじめに近年，10 年以上利用され続けている 100 ヶ国以上，8億人以上のユーザーが加入していると言われている第 3世代移動通信システムに代わる次世代通信ネットワー
ク，第 4 世代移動通信ネットワーク (以下 4G) の開発が進められている．4G では高速かつ大容量の通信サービスが可能となる一方，通信帯域や伝送遅延といった通信サービス品質 (Quality of Service，以下 QoS) が要求される．移動通信システムの QoS を満足させるために，現在マルチユーザダイバーシチ [9, 10, 13] の研究が盛んに行われている [5]．最も基本的なスケジューリング
アルゴリズムに Round Robin(以下 RR) スケジューリングがある．RR スケジューリングとはモバイルステーション (以下 MS) の状態に関係なく順番に MS にサービスを提供するスケジューリングである．これと対極なスケジューリングに Knopp and Humblet(以下 KH) ス
ケジューリングがある [9]．KH スケジューリングは最も SNR 値 (状態の良さ) が高い MS にサービスを提供するスケジューリングである．RR スケジューリングでは公平性は保たれているがマルチユーザダイバーシチを利用せず，各ユーザの無線状態を無視しているため全体のチャネル容量の平均が低くなってしまうことに問題がある．一方，KH スケジューリングではマルチユーザダイバーシチを最大限に活用しているため常に最高のチャネル容量でサービスを提供できるが，無線リンク状態の悪いユーザが選ばれる確率は非常に低くなってしまうため公平性に問題がある．
公平性とチャネル容量のバランスをとるために考え出されたのが，Proportional Fair(以下 PF) スケジューリングである [8]．このスケジューリングは各 MS の SNR
値をその MS の平均 SNR で割った値を正規化した SNR値とし，その値が最も高い MS にサービスするというスケジューリングである．正規化を行うことによって各ユーザに公平にサービスを提供することが可能になり，かつ，チャネル容量もマルチユーザダイバーシチをまったく利用していない RR スケジューリングと比べると大きくなることが知られている [4]．したがって，PF スケジューリングは，KH スケジューリング，RR スケジューリングと比べて，公平性とチャネル容量のバランスをとることが出来ているといえる．
しかしながら，PF スケジューリングは各 MS が毎回正規化した値をベースステーション (以下 BS) に報告するので，帯域と電力の消費が大きいことが問題となっている．この問題を解決するために考えられたのが Quantized PF(以下 QPF) スケジューリングである

2008MI271 山本 裕哉

石崎 文雄[3, 6]．QPF スケジューリングは PF スケジューリングと違い，正規化した SNR 値を量子化して BS 送ることによって電力の消費を抑えることができる．量子化することによって平均チャネル容量に大きく影響する可能性が考えられるが，適切な量子化を行うことによって十分なチャネル容量のサービスを行うことが出来ることが知られている [4]．
本研究では，2 状態の量子化を行った QPF スケジュー
リングを one-bit feedback fair(以下 1FF) スケジューリ
ング [4, 7, 11] と呼び，それについて研究を行う．現在，
1FF スケジューリングでのパケット遅延時間のテイル分布を実効帯域理論 [2] という方法を用いて解析する研究が行われている．今までの方法ではテイル分布の極僅かだが起こりうるレアイベントの確率を求めることが出来なく，このレアイベントが起こることは非常に致命的で QoS の低下に当然繋がってしまう．この研究はこれらを克服するために行われている [5, 12]．本研究では
1FF スケジューリングが行われる無線通信ネットワー
クを想定し，そのネットワークにおけるパケットの待ち行列遅延時間のシミュレーションを行う．シミュレー
ション結果を精査することで，1FF スケジューリング下でのパケット遅延のテイル分布の性質を調べる．また，Adaptive Modulation and Coding(以下 AMC) を採用し AMC モデルを使用したものと，AMC モデルを使用していない 1FF スケジューリングの 2 つをシミュレーションし，結果を比較する．

2 モデル
BS と MS が通信を行う図 1 で示されるセルを考える．
本研究では，図 1 で示されるようなセル内での BS からMS へのダウンリンクについて考える．また時間は１タイムスロットを Tf とし，時間はタイムスロット間隔に分割されており，すべての動作はタイムスロットと同期して行われるものとする．

図1セルラーネットワーク

マルチユーザダイバーシチ
本研究では K 個の MS と 1 個の BS から構成されるセルラネットワークを想定し，1FF スケジューリングを利用しスケジューリングを行う．システムモデルは図2 に示す．1FF スケジューリングとは QPF スケジュー
リングの状態を 2 状態で量子化し，量子化された正規化 SNR 値が最も高いユーザを選択しサービスするスケジューリングである．正規化 SNR 値が最も高いユーザが複数存在する場合はその中からランダムでユーザが 1人選ばれる．つまり 1FF スケジューリングにおいては状態が 2 状態なので設定した正規化 SNR の閾値を超えたユーザの中からランダムで 1 人選ぶことになる [5]．

2.1

2.2 Adaptive Modulation and Coding
AMC とは，無線状態に応じて変調方式を選択する仕組みである．無線状態の良い環境では高いデータレートでサービス提供し，無線状態の悪い環境では確実にデータが届くように低いデータレートでサービス提供する．
本研究ではタイムスロットごとに状態が変化するものとしデータレートは 8 段階のモードがある AMC モデルを利用する．なおモードの遷移確率は有限状態マルコフ連鎖モデルを利用する．Rate はタイムスロットごとに送信できるパケット数を表している．本研究では文献[1] で利用されている AMC を使うものとする．例えば
SNR 値が 10.37484 の MS にパケットサービスを行うとき 8.01273≤x<11.82217(dB) の範囲にあるのでモード1 でパケットサービスが行われるので Rate = 1 でサービスが行われる．Rate は 1 タイムスロットで送信できるパケットの数を表している．
表 1 AMC モデルの設定例

モード

Rate

x=SNR 値 (dB)01234567012345670.0 ≤ x < 8.01273
8.01273 ≤ x < 11.82217
11.82217 ≤ x < 16.24006
16.24006 ≤ x < 18.84206
18.84206 ≤ x < 22.58435
22.58435 ≤ x < 24.97838
24.97838 ≤ x < 28.57040
28.57040 ≤ xの状態 i から状態 j への遷移確率とする．このときタイムスロット Tf はかなり短い時間で設定されるものとして扱うので２つ以上先の状態に遷移することがないことが言える．これにより式 (1) を定義することができる．

pi,j = 0,|i − j| ≥ 2

次に状態が隣接した 1 つ上の状態に遷移する確率は，

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

pi,i−1 =χ(γi )Tf,πi

i = 1, . . . , L − 1(3)と定義される．ここでの χ(γ) は Nakagami-m モデルでのタイムスロットごとの SNR 値 γ のレベルクロスレー
トを表しており式 (4) があたえられる．

χ(γ) =√(()m− 12)
2πfd mγmγexp −Γ(m)γγ(4)ここで fd はドップラー拡散であり，γ = E[γ] は受信した SNR 値の平均値である．また式 (4) での Γ(m) は∫∞Γ(m) = 0 tm−1 exp(−t)dt のガンマ関数である．また
πi (i ∈ L) は有限状態マルコフ連鎖モデルにおける状態i の時の定常確率を表している．πi (i ∈ L) は式 (5) が与えられる．

Γ(m, mγi /γ) − Γ(m, mγi+1 /γ)
(5)
Γ(m)
∫∞
ま た Γ(m) = x tm−1 exp(−t)dt は 不 完 全 ガ ン マ
関 数 を 補 足 す る も の で あ る ．pi,j は 確 率 で あ る た め
L−1
ΣL−1
j=0 pi,j = 1 である．式 (1) -式 (3) と Σj=0 pi,j = 1 より状態が遷移しない確率を得ることができ式 (6) はそれを示している．[5]．
πi ={1 − p0,1pi,j =1 − p1,0(i = 0)(i = 1)

有限状態マルコフ連鎖モデル
本節では有限マルコフ連鎖モデルについて説明する．
本研究では各 MS の正規化された SNR 値の確率過程
は Nakagami-m モデルで記述するものとする．まず，k (k = 1,. . . , K) 番目のユーザの n スロット時の SNR

2.3

値を {Zn }∞n=0 と定義する．さらにその SNR 値を正規化した値を L 個のチャネルグレード {γl }Ll=0 に分割する．さらに γ0 = 0,γl < γl+1 (l=0,. . .,L-1)γL = ∞である．次に有限状態マルコフ連鎖モデルの状態空間を {0,. . . , L − 1} とする．ただし状態 l は SNR 値がγl ≤l<γl+1 である．Pi,j (0,. . .,L-1) を有限マルコフ連鎖

(1)

(k)

図3

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

(6)

図2

システムモデル到着プロセス
本節ではパケットの到着プロセスについて説明する．
本研究では，パケットの到着は ON-OFF ソースによって生成されると仮定する．ON-OFF ソースは 2 つの異なる状態，ON 状態，OFF 状態がある．OFF 状態の時は送るパケットが発生しないものとし，ON 状態の時は確率 λ で 1 パケット発生するものとする．ON 状態の時に OFF 状態，OFF 状態の時に ON 状態に遷移する確率は，それぞれ 1 − α，1 − β とする．ただしこの時 α，β の値の範囲は，それぞれ 0 ≤ α, β ≤ 1 である．このように本研究で考える ON-OFF ソースモデルは，α，β ，λ の 3 つのパラメータで記述される．
ON-OFF ソースの 3 つのパラメータ α，β ，λ を考えるよりも，より物理的な意味のはっきりしたパラメー
タを考えたほうが都合が良い場合も多い．ON 状態を維持する平均時間 Bon ，OFF 状態を維持する平均時間
Bof f ，平均到着レート ρ をパラメータとして考える場
合，元の 3 つのパラメータと，新たに考える物理的な意
味がよりはっきりしたパラメータ Bon ，Bof f ，ρ との関係は式 (7) で与えられる．

2.411λ(1 − β), Bof f =,ρ =1−α1−β2−α−β設定

パラメータ

1234

γ=12(dB),λ=0.30,α=0.900,β=0.992
γ=12(dB),λ=0.20,α=0.500,β=0.800
γ=16(dB),λ=0.30,α=0.900,β=0.992
γ=16(dB),λ=0.20,α=0.500,β=0.800てないもの)，図 5(AMC を使用したもの) にそれぞれ示
す．AMC モデルは表 1 の値を使用する．また AMC モデルを使用しない場合は常に Rate=1 とする．表それぞれの図の ave1，ave2，ave3，ave4 は設定 1，設定 2，設定 3，設定 4 を示している．グラフの横軸は遅延時間の大きさ (単位はタイムスロット)，縦軸は遅延確率を表している．また遅延時間の大きさはパケットの送信時間を含むため，最低値は 1 となる．
010
ave1
ave2
ave3
ave4(7)3 シミュレーション結果
本節では 1FF スケジューリングでのパケットの待ち行列遅延のシミュレーションを行い，待ち行列遅延のテイル分布を推定する．今回はパラメータを 4 パターンの設定でそれぞれシミュレーションを行った．また MS の数を 10 個，Tf (タイムスロット)=0.001(sec)，fd (ドップラー拡散周波数)=10(Hz)，γ̂=2.0(dB) は全ての設定に対して共通とする．また表 2 に設定 1〜4 のパラメータを示す．α は到着プロセスにおいて ON 状態を維持する確率，β は到着プロセスにおいて OFF 状態を維持する確率，λ は ON 状態の時に 1 パケット発生する確率，
γ は平均 SNR 値をそれぞれ表している．
表 2 のようなネットワーク環境でシミュレーションを100 回行い遅延時間の平均の結果を図 4(AMC を使用しprobabilityBon =表 2 シミュレーションにおけるパラメータの設定-110-2

10050100150200250300350400

delay time slot (msec)

図 4 1FF(AMC 未使用) シミュレーション結果

図 4 の結果から，設定 1，設定 3 の時にほぼ同じような確率となり，設定 2，設定 4 の時も同じような確率となった．4 設定のグラフを比較したところ，設定 1，設
定 3 の方が設定 2，設定 4 の時と比べて遅延が起こる確率が小さいことが分かった．以上の結果から，遅延確率

は α，β ，λ の値が大きく影響し，平均 SNR 値はほとんど影響しないことが分かった．

010
ave1
ave2
ave3
ave4-1probability

10-210-310050100150200250300350400

delay time slot (msec)

図 5 1FF(AMC 使用) シミュレーション結果

図 5 の結果から設定 1，設定 2，設定 3，設定 4 の順番で遅延が起こる確率が少ないことが分かった．AMC モ
デルを利用した場合，使用しない場合と比較すると，α，β ，λ の値に加えて，平均 SNR 値も遅延時間に影響することが分かった．

4 おわりに
本研究では 1FF スケジューリングを用いたセルラー無線ネットワークを想定し，そのネットワークにおけるパケットの待ち行列遅延のテイル分布をシミュレーションで調べた．本研究では AMC モデルを使用していな
い 1FF モデルと AMC モデルを組み込んだ 1FF モデ
ルの 2 種類のシミュレーションを行った．これにより，
1FF スケジューリングによるパケットの待ち行列遅延時間を計算するモデルからシミュレーション結果を得ることが出来た．図 4 と図 5 のシミュレーション結果から，AMC モデルを使用することによって大きな遅延時間が起こる確率を小さくなることが分かった．しかし平均 SNR 値=16(dB) と設定した設定 3，設定 4 の場合，AMC を使用しても遅延時間起こる確率はわずかに小さくなっているだけである．よって平均 SNR 値が大きい
場合 AMC モデルを使用しない方が遅延確率が小さくなる可能性がある．また帯域を考えると遅延確率が AMCモデルを使用しても使用しない場合と比べてわずかしか小さくならない場合 AMC モデルを使用しない場合の方が現実的なモデルな可能性もある．本研究では AMC モデルを使用しない場合の方が遅延確率が小さくなることは確かめられていないため，今後の研究課題として残されている．

参考文献[1] 椴山馨, 松田倫幸:実効サービス帯域関数の推定法について，南山大学数理情報学部情報通信学科卒業論

文 (2009 年度)．
[2] C.S. Chang, Performance guarantees in communication networks, Springer-Verlag, 2000.
[3] F. Florén, O. Edfors and B.A. Molin, “The effect of feedback quantization on the throughputof a multiuser diversity scheme,” Proc. of IEEE
GLOBECOM 2003, pp.497-501, 2003.
[4] G. U. Hwang and F. Ishizaki, “Design of afair scheduler exploiting multiuser diversity withfeedback information reduction,” IEEE Communications Letters, Vol.12, No.2, pp.124–126, 2008.
[5] 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.
[6] F. Ishizaki and G.U. Hwang, “Throughput performance of quantized proportional fair scheduling with adaptive modulation and coding,” Proceedings of Wireless Telecommunications Symposium (WTS) 2009, 2009.
[7] F. Ishizaki, “Analysis of the statistical timeaccess fairness index of one-bit feedback fairscheduler,” Numerical Algebra, Control and Optimization, Vol.4, pp.675–689, 2011.
[8] H. Kim and Y. Han, “An opportunistic channel quality feedback scheme for proportional
fair scheduling,” IEEE Communications Letters,
Vol.11, No.6, pp.501–503, 2007.
[9] R. Knopp and P. A. Humblet, “Information
capacity and power control in single-cell multiuser communications,” Proc. of IEEE ICC ’95,
pp.331–335, 1995.
[10] X. Qin and R. Berry, “Exploiting multiuser diversity for medium access control in wireless networks,” Proc. of IEEE INFOCOM ’03, pp.1084–1094, 2003.
[11] O. Somekh, A. M. Haimovich and Y. Bar-Ness,“Sum-rate analysis of downlink channels with1-bit feedback,” IEEE Communications Letters,
Vol.11, pp.137–139, 2007.
[12] D. Wu and R. Negi, “Eﬀective capacity: a wireless link model for support of quality of service,”
IEEE Trans. Wireless Commun., Vol.2, pp.630–643, 2003.
[13] L. Yang, M. Kang and M.S, Alouini, “On thecapacity-fairness tradeoﬀ in multiuser diversitysystems,” IEEE Trans. on Vehicular Technology,
Vol.56, No.4, pp.1901–1907,2007.