QPF スケジューリングの公平性に関する研究
2006MI105 水野 喬之

2006MI115 中内 芳朗
指導教員

2006MI188 虎山 雄哉

石崎 文雄
RR スケジューリングに比べて相当大きくなることが知1 はじめにられている．

近年，無線ネットワークにおいてマルチユーザダイ

しかしながら，PF スケジューリングでは，各 MS

バーシチ (multiuser diversity) を使用したパケットスが基地局 (BS) に正規化された SNR 値を報告するこケジューリングの研究が盛んに行われている．マルチとが必要で，そのために帯域と MS の電力を消費する

ユーザダイバーシチは，チャネル変動が独立な多数のという問題がある．そこで，正規化された SNR 値をユーザが存在するシステムにおいて，任意の時間で一部BS に報告する代わりにそれを量子化した値を報告するのユーザがほかのユーザに比べて良好なチャネル利得を持つことから発生するダイバーシチである．マルチユーQPF(Quantized PF) スケジューリングが考えられた[2, 3]．QPF スケジューリングは，各 MS が BS に量子ザダイバーシチを利用したスケジューリングでは，シス化された正規化 SNR 値を表わす量だけを報告すればよ

テム全体の情報理論的チャネル容量とユーザ間でのサーいので帯域の消費が少なく，また適切な量子化を行えばビスの公平性の間にトレードオフの関係があることがたとえ 2 段階の量子化であっても PF スケジューリング

知られており，その両立が問題となっている [5]．そのに比べて遜色のないチャネル容量を達成できることが知トレードオフの関係の観点において両極端にあるスケられている [4]．また，QPF スケジューリングは PF ス

ジューリングは，RR(Round-Robin) スケジューリング

ケジューリングと同じ長期間公平性を達成できる．と KH(Knopp and Humblet) スケジューリング [1] で無線通信網においてユーザ間の公平性は重要な性能指ある．RR スケジューリングは，マルチユーザダイバー標であるが，マルチユーザダイバーシチを利用したスケシチを全く利用せず，ユーザのチャネル状態とは無関

ジューリングにおけるユーザ間の公平性に関する研究は係に，決められた順番に全てのモバイルステーションまだ十分ではない．公平性については，有限期間内での(MS) をサービスするスケジューリングである．マルチ公平性の指標である短期間公平性 (short-term fairness)ユーザダイバーシチを利用しないため，システム全体と，無限期間内での公平性の指標である長期間公平性をのチャネル容量は低いが，ユーザ間の公平性は優れて考えることができる．特に短期間公平性に関する研究はいる．一方，KH スケジューリングは，マルチユーザダ現在までほとんど行われていない．短期間公平性は各イバーシチを最大限利用したスケジューリングである．

ユーザの遅延性能など重要な性能指標と密接な関連があ

常に最も SNR(Signal-to-Noise Ratio) 値の高い MS をるので，たとえ長期間公平性が達成されていても，短期サービスするので，システム全体でのチャネル容量は最間公平性が不十分なスケジューリングは，各ユーザの性大となる．しかしながら，KH スケジューリングはシス能に深刻な問題を発生させることになる．

テム全体のチャネル容量を最大化するが，平均 SNR 値

本研究では，QPF スケジューリングの短期間公平性にの低いユーザが選ばれにくくユーザ間の公平性に深刻なついてシミュレーションにより調査する．短期間公平性問題が発生することが知られている [5]．

を評価するための評価指標として FI(Fairness Index)[5]

サービス全体のチャネル容量とユーザ間でのサービスの サ ン プ ル パ ス バ ー ジ ョ ン で あ る SFI(Sample-pathの公平性の間に存在するトレードオフにおいて適当なバ

version of FI) を考え，SFI の時間による変化を観察ランスを取るために PF(Proportional Fair) スケジューする．

リングが考え出された．PF スケジューリングでは，各2 モデル

ユーザの SNR 値をそのユーザの平均 SNR 値で正規化し，正規化された SNR 値の最も高い MS をサービスの2.1システムモデルために選択する．各ユーザの正規化された SNR 値は独本研究で考えるシステムモデルとして，図１で示され立同一分布 (i.i.d.) に従うので，PF スケジューリング

るようなセルラ無線通信ネットワークを考える．システ

においては，各ユーザがサービスのために選ばれる確率

ムは K 個の MS と 1 つの BS から構成されており，BSは等しく，ユーザ間の厳密な長期間公平性 (long-term

は K 個の MS との通信を行う下りリンクにおいて QPFfairness) が達成できる．また，システム全体のチャネスケジューリングによりスケジュールを行う．また，時ル容量も，マルチユーザダイバーシチを全く利用しない

間は Tf の等間隔に分割されており，Tf を単位時間とし

1

図1

システムモデルで 定 め ら れ る ．式 (2)，(3) に 含 ま れ る Nn は Levelてスケジューリングが行われるものとする．
時刻 t (t = 0, 1, . . .) での MS i (i = 1, . . . , K) の正Crossing Rate，すなわち SNR が γn を横切る率を表

規化 SNR 値を z (i) (t) とし，各 MS の無線チャネルのわしており，以下の式で与えられる．

正規化された SNR 値の変化を表わす確率過程 {z (i) (t)}√µ2πfdNn =Γ(m)は，Nakagami-m モデル [6] で記述することが出来るものとする．さらに，文献 [7] で示されたように，この確

mγnγ¶m− 12µmγnexp −γ¶(5)率過程は有限状態マルコフ連鎖でうまく近似できるもの

ここに，MS の移動により引き起こされるドップラー拡とする．

散を表わし，γ = E[γ] は平均 SNR を表わし, Γ(m) =R ∞ m−1texp(−t)dt はガンマ関数である．また Pr (n)0以下で，[7] で提案された有限状態マルコフ連鎖モデ(n = 0, . . . , N ) は有限状態マルコフ連鎖が状態 n にあルを説明する．まず，正規化された SNR 値の取り得るる定常状態確率を表わしており，値を {γn }Nn=0 に分割する．ここで，γ0 = 0，γl < γl+1

(l = 0, . . . , N ) ，γN +1 = ∞ である．次に，有限状態

Γ(m, mγn /γ) − Γ(m, mγn+1 /γ)(6)
Γ(m)
R∞で与えられる．ここで，Γ(m, x) = x tm−1 exp(−t)dt
は第 2 種不完全ガンマである．式 (1)–(6) を使って有限Pr (n) =マルコフ連鎖の状態空間を {0, . . . , N } とし，状態 n はSNR 値が [γn , γn+1 ) であることを表わしているものとする．Pi,j (i, j = 0, . . . , N ) を有限状態マルコフ連鎖の遷移確率とする．ここで，有限状態マルコフ連鎖は隣接状態マルコフ連鎖の遷移確率をすべて定めることがでした状態あるいは自分自身への状態へのみ状態遷移を行きる．

うと仮定する．この仮定は短い Tf に関しては自然な仮2.2定である．この仮定より，

Pl,n = 0,|l − n| ≥ 2(1)

するための指標として FI のサンプルパスバージョンである SFI を考える．

を得る．次に，隣接した状態の遷移確率は，現在の状態FI を定義する前に，まず各ユーザの自己公平性 (selffairness) fi (i = 1, . . . , K) を以下のように定義する．

から１つ上の状態に上がる場合の遷移確率は，Pn,n+1 =Nn+1 Tf,Pr (n)公平性指標

本研究では，スケジューリングの短期間公平性を評価(n = 0, . . . , N − 1)(2)
fi = −で，現在の状態から１つ下の状態に下がる場合の遷移確

log(Pi )
log K

(7)

ここに，K は MS の数を表わし，Pi は MS i が選ばれる

率は

N n TfPn,n−1 =,Pr (n)定常確率，すなわち全体の中で MS i の伝送のために割(n = 1, . . . , N )(3)り当てられる時間の割合を表わす．式 (7) を使って FIは以下のように定義される．

で定められる．また同じ状態にとどまる場合の遷移確率は

 1 − Pn,n+1 − Pn,n−1 , (0 < n < N )1 − P0,1 ,(n = 0)
Pn,n =
1 − PN,N −1 ,(n = N )

FI =K
X

Pi fi

i=1(4)=−2PK

i=1 Pi log Pilog K(8)

式 (8) は，各 MS が等確率で選ばれるスケジューリング

は，さまざまな環境を想定してシミュレーションを行うのエントロピーに対して考えているスケジューリングのため γ1 (SNR 値) の値を変化させることによって時間変エントロピーの比と考えることができる．したがって，化がどう変わるかを調べる. このとき有限状態マルコフ

エントロピーの性質から 0 ≤ FI ≤ 1 であることが分連鎖の遷移確率を 2 節の結果を使って求めると，例として以下のようになる.

かる．

次に，SFI を定義する．そのために {1, . . . , K} 上の

γ1 = 1dB

確率過程 {X(t)} を定義する．ここに，X(t) は時刻 t に

P0,0 = 0.501177, P0,1 = 0.498823
P1,0 = 0.005013, P1,1 = 0.994987

おいてサービスのために選ばれた MS のインデックスを示す．さらに Pi∗ (t) (i = 1, . . . , K; t = 0, 1, . . .) を以下のように定義する．

γ1 = 20dB の時

Pi∗ (t) =t−1
1X

t n=0

I{Xn =i}(9)

ここに I は指標関数 (indicator function) を表わし，I{Xn =i} =½1 (Xn = i)
0 (Xn =6 i)

ものを図 2 に示す．図の x 軸を時間 (msec)，y 軸をSFI とする．シミュレーションにおいて必要な疑似乱数は，GNU 科学技術計算ライブラリ (GNU ScientificLibrary，GSL) [8] の乱数発生器を利用し，図 2 にはのもとで確率 1 でranlux を利用した．シミュレーションによる推定値は100 個のサンプルのサンプル平均により得て，その推定(11)値の 5 個のサンプル平均をシミュレーション結果としてと な る こ と に 注 意 ．こ の と き ，時 刻 t に おけ る SFI

図 2 に示している．図 2 は γ1 = 1dB である．また表SFI(t) (t = 0, 1, . . .) は以下のように定義される．
SFI(t) = −PK∗∗
i=1 Pi (t) log Pi (t)log K

P1,1 = 0.949867

から 10000msec までシミュレーションによって求めた(10)スのために選ばれた割合を表わし，エルゴード性の仮定

t→∞P0,1 = 0.027176

P1,0 = 0.050133,

上記の設定で，QPF スケジューリングの SFI を 0msec

である．ここで，式 (9) は時刻 t までに MS i がサービ

Pi = lim Pi∗ (t)P0,0 = 0.970824,

1 に，ranlux を用いた時の 5 個の推定値の分散を，時間 (msec) を 2000，4000，6000，8000，10000 に関して(12)示す．
図 2 から SFI は 10sec 程度でほぼ 1 に収束すること

ここで，エルゴード性の仮定のもとで確率 1 でが分かる．また 4sec 程度で 0.5 を超えることも分かる．

FI = lim SFI(t)
t→∞

(13)

また，他の 5 つのサンプルも近似したシミュレーション結果を得られたことから，シミュレーションに信頼性がとなることに注意．

あると考えられる. これは，他の γ1 でも同様の結果が3 シミュレーション結果得られた．

本節では，QPF スケジューリングの SFI SFI(t) をシ

表1ミュレーションによって調べ，QPF スケジューリング

推定値分散 (10−11 )の短期間公平性について論じる．QPF スケジューリン

時間

推定値分散：1(dB)

推定値分散：20(dB)

グの FI は 1 であるので，時間の経過にともない SFI が2000

0.510893502

12.605797323

どのような速さで，どのような形で 1 に近づくかを観察

4000

0.040208367

10.242271304

する．本節で示すシミュレーション結果においては以下6000

0.074670567

11.003962523の環境を仮定した．MS の数 K は 20 とし，各 MS の無8000

0.087509793

16.812579396

線チャネルは Nakagami-m モデルにおいて m = 1 と設10000

0.072892097

21.017735829

定したモデルで記述できるとする．すなわち，各 MS の無線チャネルは Rayleigh fading モデルで記述できると

表 1 から，各時間帯で平均 SNR の推定値の分散が非する．また，各 MS の無線チャネルの状態を表わす有限常に小さい．つまり，このシミュレーション結果による状態マルコフ連鎖の状態数は 2，すなわち N = 1 とし，推定の信頼性が高いと確認できる．また，他の 4 個の乱γ = 20dB とする．また QPF スケジューリングの量子化のグレード数は 2, すなわち L = 2 とする. 本研究で数発生器や他の γ1 でも表 1 のように，非常に小さい結果を得ることも確認できている.

3

図 2 SFI:ranlux-1[2] F. Florén, O. Edfors and B.-A. Molin, “The effect of feedback quantization on the throughput

4 おわりに4.1 まとめと研究結果

of a multiuser diversity scheme,” Proc. of IEEE
GLOBECOM 2003, pp.497–501, 2003.
[3] F. Ishizaki and G. U. Hwang, “Throughput per-

本研究では，マルチユーザダイバーシチを利用したQPF スケジューリングを考え，QPF スケジューリングの短期間公平性について調べた．QPF スケジューリン

formance of quantized proportional fair scheduling with adaptive modulation and coding,” Proc.

グを使用した時の短期間公平性が PF スケジューリンof Wireless Telecommunication Symposium, 2009.
[4] G. U. Hwang and F. Ishizaki, “Design of a fairscheduler exploiting multiuser diversity with feed-

グのそれとほとんど変わらない性能を持っているのであれば，PF スケジューリングよりも帯域が少なく，使用電力が大幅に少なく済ませることができる QPF スケ

back information reduction,” IEEE Communications Letters, Vol.12, No.2, pp.124–126, 2008.

ジューリングが実用上望ましい．本研究では，短期間公平性を評価する指標として SFI を導入し，SFI の時間[5] L. Yang, M. Kang and M.-S. Alouini, “On thecapacity-fairness tradeoff in multiuser diversitysystems,” IEEE Transactions on Vehicular Tech-

変化をシミュレーションにより調べた．シミュレーショ
ン結果から，QPF スケジューリングにおいては SFI は10sec 程度でほぼ 1 に収束すること，また時間の経過とnology, Vol.56 No.4, pp.1901–1907, 2007.
[6] G. L. Stüber, Principles of mobile communication,ともにほとんど確実に理想的な状態に収束してくことが分かった．また，時間変化を調べるために，さまざまな状態でシミュレーションを行ってみた. SNR 値をさま

2nd ed., Kluwer, 2001.
[7] Q. Liu, S. Zhou and G. B. Giannakis, “Queuingwith adaptive modulation and codeing over wire-

ざまな値で変化させ，時間変化を調べたところ，すべての状態がほぼ近似した結果を示していた. つまり，QPF

less links: cross-layer analysis and design,” IEEE
Transactions on Wireless Communications, Vol.4

スケジューリングは時間変化はあまり変化することがな
く，どんな状態ででも公平性を持つことが確認できた.

No.3, pp.1142–1153, 2005.
[8] M. Galassi, J. Davies, J. Theiler, B. Gough,G. Jungman, M. Booth, F. Rossi, GNU Scientific

参考文献[1] R. Knopp and P. A. Humblet, “Information capacity and power control in single-cell multiuser communications,” Proc. of IEEE ICC ’95, pp.331–

Library, Vol.1 No.8, pp.145–159, 2006.

335, 1995.

4