1FF スケジューリングの公平性と定常状態の関係に関する研究
M2010MM029 中内 芳朗
指導教員：石崎 文雄

はじめに

ジューリングが考えられた [4, 5]．QPF スケジューリン
グは，各 MS が BS に量子化された正規化 SNR 値を表わ
近年，無線ネットワークにおいてマルチユーザダイバー
す量だけを報告すればよいので帯域の消費が少なく，まシチ (multiuser diversity)[1] を使用したパケットスケジ
た適切な量子化を行えばたとえ 2 段階の量子化であってューリングの研究が盛んに行われている [2, 3, 4]．マルチ
も PF スケジューリングに比べて遜色のないチャネル容量
ユーザダイバーシチはチャネル変動が独立な多数のユーを達成できることが知られている [6]．この 2 段階の量子ザが存在するシステムにおいて，任意の時間で一部のユー化を行う QPF スケジューリングのことを 1FF(One-Bit
ザが他のユーザに比べて良好なチャネル利得を持つこと
Feedback Fair) スケジューリングと呼ぶ．また，1FF ス
から発生するダイバーシチである．マルチユーザダイバー
ケジューリングは PF スケジューリングと同じ長期間公シチを利用したスケジューリングでは，システム全体の平性を達成できる．
情報理論的チャネル容量とユーザ間でのサービスの公平
無線通信網においてユーザ間の公平性は重要な性能指性の間にトレードオフの関係があることが知られており，標であるが，マルチユーザダイバーシチを利用したスケ
その両立が問題となっている．システム全体のチャネル容ジューリングにおけるユーザ間の公平性に関する研究は量とユーザ間でのサービスの公平性の間のトレードオフ
まだ十分ではない．公平性については，有限期間内での公の関係の観点において両極端にあるスケジューリングは，平性の指標である短期間公平性 (short-term fairness) とRR(Round-Robin) スケジューリングと KH(Knopp and
無限期間内での公平性の指標である長期間公平性を考え
Humblet) スケジューリング [1] である．RR スケジューることができる．短期間公平性に関する研究は現在まで
リングはマルチユーザダイバーシチを全く利用せず，ユー
ほとんど行われていない．短期間公平性は各ユーザの遅ザのチャネル状態とは無関係に，決められた順番に全て延性能など重要な性能指標と密接な関連があるので，たのモバイルステーション (MS) をサービスするスケジューとえ長期間公平性が達成されていても短期間公平性が不リングである．マルチユーザダイバーシチを利用しない
十分なスケジューリングは，各ユーザの性能に深刻な問ためシステム全体のチャネル容量は低いが，ユーザ間の題を発生させることになる．
公平性は優れている．一方，KH スケジューリングはマ
スケジューリングにおいて実現される短期間公平性は
ルチユーザダイバーシチを最大限利用したスケジューリ
MS の初期状態に大きく依存することになるが，短期間公ングである．常に最も SNR(Signal-to-Noise Ratio) 値の平性に関するほとんどの研究は初期状態においてすべて高い MS をサービスするので，システム全体でのチャネの MS が定常状態であることを仮定しており，[8] その初
ル容量は最大となる．しかしながら，KH スケジューリ
期状態の影響は現在まで詳しく調べられていない [9]．しングはシステム全体のチャネル容量を最大化するが，平たがって，スケジューリングにおいて実現される短期間
均 SNR 値の低いユーザが選ばれにくくユーザ間の公平性
公平性を評価するためには短期間公平性が劣悪となるよに深刻な問題が発生することが知られている [3]．
うな MS の初期状態も含め，様々な初期状態のもとでのサービス全体のチャネル容量とユーザ間でのサービスの短期間公平性の特性を調べる必要がある．
公平性の間に存在するトレードオフにおいて適当なバラ本研究では，1FF スケジューリングの短期間公平性に関ンスを取るために PF(Proportional Fair) スケジューリンする性質についてシミュレーションにより調査する．短期
グが考え出された．PF スケジューリングでは，各ユーザ間の公平性の指標として STAFI(Statistical Time-Accessの SNR 値をそのユーザの平均 SNR 値で正規化し，正規
Fairness Index)[7] を考え，STAFI の MS，正規化 SNR
化 SNR 値の最も高い MS をサービスのために選択する．
値，計測時間，指標による変化を観察する．また，定常各ユーザの正規化 SNR 値は独立同一分布 (independent状態にある MS 群に新たに初期状態の MS をいくつか参and identically distributed) に従うので，PF スケジュー
入させるという環境を考え，MS の初期状態の STAFI に
リングにおいては，各ユーザがサービスのために選ばれ及ぼす影響をシミュレーションにより調査する．
る確率は等しく，ユーザ間の厳密な長期間公平性 (longterm fairness) が達成できる．また，システム全体のチャ 2 モデル
ネル容量も，マルチユーザダイバーシチを全く利用しな
2.1 システムモデル
い RR スケジューリングに比べて相当大きくなることが本研究では図 1 で示されるようなセルラ無線通信ネット
知られている．
ワークを考える．システムは
K 個の MS と 1 つの BS か
しかしながら，PF スケジューリングでは各 MS が基ら構成されており，
BSはK個のMS との通信を行う下り
地局 (BS) に正規化 SNR 値を報告することが必要であり，そのために帯域と MS の電力を消費するという問題があ リンクにおいて 1FF スケジューリングによりスケジューる．そこで，正規化 SNR 値を BS に報告する代わりにそ ルを行う．また，時間は Tf の等間隔に分割されており，れを量子化した値を報告する QPF(Quantized PF) スケ Tf を単位時間としてスケジューリングが行われるものと1

にある定常状態確率を表しており，∫ γn+1Pr (n) =pγ (γ)dγγn= exp(−

図 1 システムモデル

γnγn+1) − exp(−
)
γ
γ

(6)

で与えられる．式 (1)–(6) を使って有限状態マルコフ連鎖の遷移確率をすべて定めることができる．

2.2

公平性指標

する．時刻 t (t = 0，1，. . .) での MS i (i = 1，. . . ，K) の本研究では，スケジューリングの短期間公平性を評価
正規化 SNR 値を z (i) (t) とし，各 MS の無線チャネルの するための指標として MS1 と MS2 の間の STAFI につい
正規化 SNR 値の変化を表わす確率過程 {z (i) (t)} は，レ て考える．[0，1) の一様分布によって導かれる独立同一分
イリーフェージングチャネルモデル [10] で記述すること 布に従う確率過程 {v(t)}(t = 0，1，. . .) を使用する．確率ができ，確率過程は有限状態マルコフ連鎖でうまく近似 変数 ν (i) (t)(i = 1，2; t = 0，1，. . .) を定義する．
できる [11]．
K∑
以下で，[11] で提案された有限状態マルコフ連鎖モデル
ν(t)=I(s(k) (t) = 1)(7)を説明する．まず，正規化 SNR 値の取り得る値を {γn }Nn=0k=1に分割する．ここで，γ0 = 0，γl < γl+1 (l = 0，. . . ，N )，(i)γN +1 = ∞ である．次に，有限状態マルコフ連鎖の状態 I(·) は指標関数を意味する．c (t)(i = 1，. . . ，K; t = 0，1
空間を {0，. . . ，N } とし，状態 n は SNR 値が [γn ，γn+1 ) ，. . .) は，時間 t における MSi のサービス量に代表する確であることを表わしているものとする．Pi，j (i，j = 0 率変数である．すなわち，1FF スケジューリングで時間 t，. . . ，N ) を有限状態マルコフ連鎖の遷移確率とする．こ において下りリンクの伝送のために MSi が選択された時(i)(i)
こで，有限状態マルコフ連鎖は隣接した状態あるいは自 c (t) = 1 であり，MSi 以外が選択された時 c (t) = 0(1)(2)
分自身への状態へのみ状態遷移を行うと仮定する．この である．c (t)，c (t) は以下のように表すことができる．

仮定は短い Tf に関しては自然な仮定である．この仮定(1) 1 (s (t) = 1，v(t) ∈ [0，1/ν(t)))
より，(1)c (t) =
(8)
1 (ν(t) = 0，v(t) ∈ [0，1/K))
Pl，n = 0， |l − n| ≥ 2(1) 0 (otherwise)を得る．次に，隣接した状態への遷移確率の中で，現在の状態から１つ上の状態への遷移確率は，
1 (s(2) (t) = 1，v(t) ∈ [s(1) (t)/ν(t), (s(1)(t) + 1)/ν(t)))
Nn+1 Tfc(2) (t) =(9)
Pn，n+1 =， (n = 0，. . . ，N − 1) (2) 1 (ν(t) = 0，v(t) ∈ [1/K, 2/K))

Pr (n)
 0 (otherwise)
で，現在の状態から１つ下の状態への遷移確率は
MSi の [t0 ，t0 + T ) でのサービス量 α(i) (t0 ，t0 + T ) は以
N n Tf下のように表すことができる．
Pn，n−1 =， (n = 1，. . . ，N )(3)
Pr (n)
t0 +T
∑−1
(i)
α
(t
，
t
+
T
)
=
c(i) (t)(10)
0 0で定められる．また，同じ状態にとどまる場合の遷移確
t=t0
率は

以上の式をもとに，STAFI GT (x) は以下のように定義
 1 − Pn，n+1 − Pn，n−1 ， (0 < n < N )する．
Pn，n =
1 − P0，1 ，(n = 0) (4)
1 − PN ，N −1 ，(n = N )GT (x) = P (| α(1) (t0 ，t0 +T )−α(2) (t0 ，t0 +T ) |≥ x) (11)で定められる．式 (2)，(3) に含まれる Nn は Level Crossing Rate，すなわち SNR 値が γn を横切る率を表わして
おり，以下の式で与えられる [13]．
(
)
√
γn
γn
(5)
Nn = 2π fd exp −γγ
ここで，fd は MS の移動により引き起こされるドップラー
拡散を表わし，γ = E[γ] は平均 SNR 値を表わす．またPr (n) (n = 0，. . . ，N ) は有限状態マルコフ連鎖が状態 n

ここで，STAFI は 0 ≤ GT (x) ≤ 1 であり，0 に近いほど公平性が高く，1 に近いほど公平性が低いことになる．

3

シミュレーション結果

本節では，1FF スケジューリングの STAFIGT (x) をシ
ミュレーションによって調べ，1FF スケジューリングの短期間公平性と定常状態の関係について論じる．1FF スケ
ジューリングの計測時間 T と STAFI の MS1 と MS2 の選択される回数の差を測るための指標 x を固定して，MSの数 K と正規化 SNR 値 γ1 /γ を変化させ，また，MS の表 2 MS の数と正規化 SNR 値を変化させた場合の STAFI
条件
定常状態
MS1 のみ状態 0 MS1,2 が状態 0
γ1 /γ = 2.00 dB，K = 20
3.03 × 10−2
2.82 × 10−2
2.54 × 10−2
γ1 /γ = 2.00 dB，K = 30
0.27 × 10−20.24 × 10−2
0.21 × 10−2−2−2
γ1 /γ = 2.00 dB，K = 40
0.01 × 10
0.01 × 10
0.01 × 10−2−2−2
γ1 /γ = 3.78 dB，K = 20
8.43 × 10
8.00 × 10
7.53 × 10−2
γ1 /γ = 3.78 dB，K = 30
3.50 × 10−2
3.29 × 10−2
3.06 × 10−2−2−2
γ1 /γ = 3.78 dB，K = 40
1.30 × 10
1.21 × 10
1.11 × 10−2−2−2
γ1 /γ = 6.00 dB，K = 20
4.47 × 10
4.29 × 10
4.11 × 10−2
γ1 /γ = 6.00 dB，K = 30
3.73 × 10−2
3.58 × 10−2
3.42 × 10−2−2−2
γ1 /γ = 6.00 dB，K = 40
3.10 × 10
2.97 × 10
2.84 × 10−2

MS1,2 が状態 1
3.64 × 10−20.35 × 10−2
0.02 × 10−2
12.4 × 10−2
5.46 × 10−2
2.14 × 10−2
14.0 × 10−2
11.8 × 10−2
9.99 × 10−2

数 K と正規化 SNR 値 γ1 /γ を固定して，計測時間 T とまた，上記の計測時間と MS1 と MS2 の選択される回
STAFI の MS1 と MS2 の選択される回数の差を測るため 数の差を測るための指標を変化させる設定で全ての MSの指標 x を変化させ，STAFI の変化を観察する．
が定常状態，MS1，2，3 が良好なチャネル状態で参入し本節で示すシミュレーション結果においては以下の環 た場合について 1FF スケジューリングの STAFI をシミュ
境を仮定した．各 MS の無線チャネルはレイリーフェー レーションによって求めたものを図 2， 3 に示す．
ジングモデルで記述できるとする．各 MS の無線チャネ
ルの状態を表わす有限状態マルコフ連鎖の状態数は 2，すなわち N = 1 とする．1FF スケジューリングのであるので，量子化のグレード数は 2，すなわち L = 2 とする．
本研究では，さまざまな環境を想定してシミュレーショ
ンを行うため，計測時間は 1 msec を 1 スロットと考え，
256 スロット計測するものとする．すなわち T = 256 とする．STAFI の MS1 と MS2 の選択される回数の差を測るための指標を 40 とする．すなわち x = 40 とする．正規化 SNR 値 γ1 /γ の値を 2.00，3.78，6.00 dB と MS の数
x[slot]K を 20，30，40 変化させることによって，STAFI の変化を観察する．γ1 /γ = 3.78 dB は 1FF スケジューリングに
図 2 全ての MS が定常状態での STAFI
おいて最も高いチャネル利得が得られる値である．
また，正規化 SNR 値を 3.78 dB とする．すなわち
γ1 /γ = 3.78 dB とする．MS の数を 20 とする．すなわ
ち K = 20 とする．計測時間 T を 32，64，128，256 ス
ロットと変化させ，スロット数において STAFI の MS1と MS2 の選択される回数の差を測るための指標を 0 から
5 刻みで増加させ，時間の経過とともに STAFI が 0.01 に収束するまでの過程を観察していく．
このとき有限状態マルコフ連鎖の遷移確率を 2.1 節の結果を使って求めたものを表 1 で示す．
STAFI

1

T=256
T=128
T=64
T=32

0.1

0.01

0

20

40

60

80

STAFI

1

表 1 シミュレーションに使用する遷移確率
γ1 /γ
P00
P01
P10
P11
2.00 dB 0.991864 0.008136 0.031557 0.968443
3.78 dB 0.996083 0.003917 0.038734 0.961266
6.00 dB 0.999049 0.000951 0.050014 0.949986
上記の MS の数と正規化 SNR 値を変化させる設定で全ての MS が定常状態，MS1 のみが初期状態で参入した
場合，MS1，2 が初期状態で参入した場合，MS1，2 が良
好なチャネル状態で参入した場合の 4 つの条件のもとで
1FF スケジューリングの STAFI をシミュレーションによって求めたものを表 2 に示す．

100

T=256
T=128
T=64
T=32

0.1

0.01

0

20

40

x[slot]

60

80

100

図 3 MS1,2,3 が状態 1 での STAFI
シミュレーションにおいて必要な疑似乱数は，GNU 科学
技術計算ライブラリ (GNU Scientiﬁc Library，GSL)[12]の乱数発生器を利用した．シミュレーションによる推定値
は 100 個のサンプル平均により得た値をシミュレーショ
ン結果として表 2 に示している．
ここで，定常状態の推定値分散を示す．γ1 /γ = 3.78 dB，
K = 20，T = 256 スロット，x = 40 の時，推定値分散は 8.49014636(10−8 ) であり，非常に小さいことがわかる．
つまり，このシミュレーションによって得られた結果は

信頼性が高いものであるといえる．また，他のいずれの きた．
条件でも，同様に非常に小さい結果が得られたことも確
参考文献
認できている．
表 2 から全ての MS が定常状態の STAFI で最大値は [1] R. Knopp and P. A. Humblet, Information capacityand power control in single-cell multiuser communiγ1 /γ = 3.78 dB，K = 20 の時であり，最小値は γ1 /γ =cations Proc. of IEEE ICC ’95, pp.331–335, 1995.
2.00 dB，K = 40 である．正規化 SNR 値 γ1 /γ = 3.78 dB
はチャネル容量が最大となる値なので，トレードオフの [2] F.Ishizaski and G.U.Hwang, Queuing delay analy関係により公平性が低くなり，STAFI が大きくなったと
sis for packet schedlers with/without multiuser di考えられる．また，最小値では閾値が下がることによりversity over a fading channel, IEEE Trans. Veh.
多くの MS が状態 1 に存在する確率が上昇する．さらにTechnol., vol.56, pp.3220–3227, 2007.
MS の数を増加させることで 1 つの MS が選択される回 [3] L. Yang，M. Kang and M.-S. Alouini， On the
数が減少するので，高い公平性を得られたといえる．さcapacity-fairness tradeoﬀ in multiuser diversity sysらに，閾値が無限に近いまたは 0 に近い場合，MS の状態
tems, IEEE Trans. Veh. Technol., vol.56, pp.1901–
が片方の状態に偏るので，長期的な公平性は同じになる
1907，2007.
と考えられる．しかしながら，可能性は非常に低いが，閾
[4] F. Florén, O. Edfors and B.-A. Molin, The ef値が無限に近い場合，MS1 が状態 1 にありその他の MS
fect of feedback quantization on the throughput of aが状態 0 にある場合に MS1 が選択される確率が高く，公multiuser diversity scheme, Proc. of IEEE GLOBE平性に大きな問題を生じる可能性が高い．一方，閾値がCOM 2003, pp.497–501, 2003.
0 に近い場合，MS1 が状態 0 にありその他の MS が状態
1 にある場合に MS2 が選択させる確率は 1/(K − 1) であ [5] F. Ishizaki and G. U. Hwang, Throughput performance of quantized proportional fair scheduling withるので，公平性にさほど大きな影響を与えるとは考えら
adaptive modulation and coding, Proc. of Wireless
れない．よって，γ1 /γ = 2.00 dB の場合により公平性がTelecommunication Symposium, 2009.
高くなると考えられる．
また各条件間で比較をすると，定常状態に比べて MS1， [6] G. U. Hwang and F. Ishizaki, Design of a fair
2 が状態 1 の時 STAFI が大きくなることがわかる．これscheduler exploiting multiuser diversity with feedは，MS1，2 が状態 1 で参入することによって MS1，2 がback information reduction, IEEE Communications
他の MS より選択される確率が高くなり，MS1，2 の選
Letters, vol.12, pp.124–126，2008.
択回数の差が大きくなりやすく公平性が低くなったこと [7] Y. Liu, S. Gruhl and E. W. Knightly, WCFQ:を示している．
an opportunistic wireless scheduler with statistical
図 2 から，MS1，2 が状態 0 になる可能性がある場合にfairness bounds, IEEE Trans. Wireless Commun.,
短期間で状態が遷移する確率は非常に低いので MS1，2
vol.2, pp.1017–1028, 2003.
ともに選択されることはなく，計測時刻 t が 10 スロット
[8] F. Ishizaki Statistcal time-access fairness index ofまでに著しく STAFI が減少する．その後，時間が経過す
one-bit feedback fair scheduler, Proc. of Internaるにつれて良好な状態に遷移する可能性が生じて選択さtional Conference on Queueing Theory and Network
れる確率が増加し，STAFI がなだらかに減少をすること
Applications (QTNA), 2011.
がわかる．図 3 から，MS1，2，3 が良好なチャネル状態
で参入した場合では MS1，2 が良好な状態から始まるの [9] F. Ishizaki, Eﬀect of initial states on statisticaltime access fairness index of one-bit feedback fair
で，選択される確率が高く選択回数に差が生じやすくな
scheduler, Proc. International Workshop on Cross
ると考えられる．よって，計測開始の時点からなだらか
Layer Design, 2011.
に減少していることがわかる．
[10] G. L. Stüber，Principles of mobile communication，
4 おわりに2nd ed.，Kluwer，2001.
本研究では，マルチユーザダイバーシチを利用した 1FF [11] Q. Liu，S. Zhou and G. B. Giannakis， Queuing
スケジューリングを考え，1FF スケジューリングの短期with adaptive modulation and codeing over wireless
間公平性と定常状態との関係について調べた．短期間公links: cross-layer analysis and design, IEEE Trans.
平性を評価する指標として STAFI を導入し，定常状態とWireless Commun., vol.4, pp.1142–1153，2005.
定常状態に新たに MS が参入した場合との違いについて[12] M. Galassi，J. Davies，J. Theiler，B. Gough，
調べた．
G. Jungman，M. Booth，F. Rossi， GNU Scientiﬁc
シミュレーション結果から，1FF スケジューリングにおLibrary. Vol.1 No.8，pp.145–159，2006.
いての STAFI は定常状態と比べ，通信状態が良好な MSが参入した場合に公平性が著しく損なわれることが確認 [13] M. D. Yacoub, J. E. Vargas Bautista, and L. G. de
R. Guedes,
On higher order statistics of the
できた．また，通信状態が良好な MS が参入した場合でNakagami-m distribution, IEEE Trans. Veh. Techは，STAFI が計測開始の時点からなだらかに減少するの
nol., vol. 48, pp.790–794, 1999.
で，計測時間ごとの結果に差が生じやすいことも確認で