1FF スケジューリングの公平性に関する研究
2008MI070 石井 佑美香

2008MI182 岡橋 実加
指導教員

1 はじめに
近年，無線通信媒体の普及により無線通信における帯域の利用が増加してきた．無線通信において帯域は最も貴重な資源の一つであり，帯域の効率的な利用はQoS(Quality-of-Service) の確保にとって重要である．
その方法の一つとしてマルチユーザダイバーシチ (multiuser diversity) を利用することが挙げられる．
マルチユーザダイバーシチとは，チャネル変動が独立な多数のユーザが存在するシステムにおいて，任意の時間で一部のユーザが他のユーザに比べて良好なチャネル利得を持つことから発生するダイバーシチである．これを利用することにより，システム全体の情報理論的チャネル容量を増加させることができるので，マルチユーザダイバーシチを利用したスケジューリングの研究が盛んに行われてきている [1, 3, 4, 8, 11]．しかしマルチユーザダイバーシチを利用したスケジューリングにおいては，システム全体のチャネル容量と個々のユーザの公平性の間にトレードオフが存在することが知られている[12]．したがってマルチユーザダイバーシチを利用したスケジューリングにおいては，チャネル容量と公平性の間のバランスのとれたスケジューリングを開発することが重要である．
本稿ではセルラー通信網を想定し，基地局 (BS，BaseStation) と移動局 (MS，Mobile Stations) の通信におけるスケジューリングに着目する．チャネル容量と公平性の観点からスケジューリング方法に着目すると，代表的なスケジューリング方法として RR(Round-Robin)
方式や KH(Knopp and Humblet) 方式 [5] がある．RR方式はマルチユーザダイバーシチをまったく利用せず，各 MS に順番にサービスを提供する方法である．非常に公平性は優れているがシステム全体のチャネル容量は低い．その一方で KH 方式はマルチユーザダイバーシチを最大限に利用している．BS は SNR(Signal-to-NoiseRatio) 値の最も高い MS にサービスを提供するので，システム全体のチャネル容量は最大となる．しかし平均SNR 値の低い MS はサービスを提供されにくいので公平性に深刻な問題がある．
この KH 方式の問題を解決するために考え出されたのが PF(Proportional Fair) 方式である．PF 方式は各MS の SNR 値をその MS の平均 SNR 値で正規化し，正規化された SNR 値の最も高い MS をサービスのために選択する．各 MS の SNR 値は独立同一分布に従うので各 MS がサービスを受ける確率は等しく，長期間の公平性が保証される．またシステム全体のチャネル容量も，マルチユーザダイバーシチを全く利用していない RR 方式に比べて相当大きくなる．しかし全 MS が BS に正2008MI281 安江 佐織

石崎 文雄
規化 SNR 値を通知するので帯域の消費が激しいという欠点がある．欠点を克服するために PF 方式を改良した1FF(One-bit Feedback Fair) スケジューリング方式が考え出された．1FF スケジューリング方式では，MS は2 状態に量子化した正規化 SNR 値が任意の閾値を越えていれば BS に通知する．BS は閾値を越えた MS をランダムに選択し，サービスを行う．各 MS は 1bit のみBS に通知するので帯域の消費を減らすことができる．
公平性は短期間公平性と長期間公平性に分類できる．
短期間公平性は，スケジューリングが有限観察期間内にサービス時間などのネットワーク資源を複数の MS にいかに等しく分配できるかというスケジューリングの能力を表す．対して長期間公平性は, スケジューリングが無限観察期間内にサービス時間などのネットワーク資源を複数の MS にいかに等しく分配できるかというスケジューリングの能力を表す. 短期間公平性は個々の MSのパケット遅延や損失などのパケットレベルの性能に大きな影響を及ぼす [2]．したがって QoS 保証の観点からスケジューリングの短期間公平性の特性を知ることが重要である．しかしながら，その重要性にも関わらず 1FFスケジューリングの短期間公平性について十分には調べられていない．
短期間公平性の指標の一つとして，[6] が提案した
STAFI(Statical Time-Access Fairness Index) と呼ばれる短期間公平性の指標がある．STAFI は有限期間内の 2 つの MS のサービスされた時間の差の確率分布に着目したものである．
本稿では,1FF スケジューリングの持つ短期間公平性の性質を明らかにする．特に短期間公平性評価の指標として STAFI を考え，1FF スケジューリングの STAFIをシミュレーションにより調査する．
安江佐織は主に研究背景を，岡橋実加は主にシステムモデルから公平性指標までを，石井佑美香は主にシミュレーションの結果以降を行った．

2 モデル
本節では，システムと公平性指標のモデル化を行う．
システムモデル
本稿では，システムモデルとして図 1 で示されるセルラ無線通信ネットワークを採用する．1 つの BS に対しK 個の MS で構成される下りの通信 (ダウンリンクチャネル) システムを 1FF スケジューリングによって行う．
単位時間 Tf で分割されてスケジューリングするものとし，時刻 t(t = 0, 1, ...) での MSi(i = 1, ..., K) の正規化 SNR 値を z (i) (t) とする．各 MS の正規化 SNR 値の変化を表す確率過程を {z (i) (t)} とし，Nakagami-m モ

2.1

√Nn =2πfd mγn m− 1mγn() 2 exp(−)
Γ(m)γ̄
γ̄

(5)

平均 SNR 値を γ̄ = E[γ]，ガンマ関数を Γ(m) =R ∞ m−1texp(−t)dt で表す．さらに有限状態マルコフ0連鎖が状態 n にある定常状態確率を表したものを以下に示す．

Z Γn+1Pr (n) =ργ (γ)dγ
Γn=図1

システムモデルデルの一つであるレイリーフェージングチャネルに従って記述できるものとする [10]．また正規化 SNR 値の変化を表す確率過程は有限状態マルコフ連鎖でうまく近似できるものとする．
次に，正規化 SNR 値の変化を表す確率過程を有限状態マルコフ連鎖で近似したモデル [7] について考える．
有限状態マルコフ連鎖の状態空間を {0, ..., N } とし，正規化 SNR 値の境界点である {γn }Nn=0 を定める．連続した区間を重複しないように分割する．その結果 γ0 = 0，γl < γl+1 (l = 0, ..., N )，γN +1 = ∞ となる．状態空間にある n は SNR 値が [γn , γn+1 ) であることを表しているものとする．また有限状態マルコフ連鎖の遷移確率をPi,j (i, j = 0, ..., N ) とする．正規化 SNR の状態遷移を自身への遷移もしくは隣接した状態への遷移のみ行うとする．よって二つの連続した状態を跨ぐ遷移の確率は 0であることから

Pl,n = 0, |l − n| ≥ 2(1)を得る．次に，隣接した状態の遷移確率について定める．
状態が 1 つ上の状態に遷移する条件付き確率は [9]Pn,n+1 =Nn+1 Tf, (n = 0, ..., N − 1)
Pr (n)(2)Γ(m, mγn /γ̄) − Γ(m, mγn+1 /γ̄)
Γ(m)

(6)n
また mγγ̄ は閾値とし f d をドップラー周波数とする．
以上，式 (1)-(6) を用いて有限状態マルコフ連鎖の遷移確率をすべて定める．
上記に示したように各 MS の無線チャネルはレイリーフェージングチャネルに従うので m = 1 と定める．ここで正規化 SNR 値を 0 と 1 に量子化することによって2 状態の有限マルコフ連鎖とし，これによってうまく近似されると仮定して式の変形を行うと，正規化 SNR が閾値より上に遷移する確率 (2) はP0,1 =N Tf
Pr (0)(7)となる．さらに正規化 SNR が閾値より下に遷移する確率 (3) は

P1,0 =N Tf
Pr (1)(8)となる．正規化 SNR が自身の状態に留まる確率 (4) における，正規化 SNR 値が閾値より下の範囲に留まる確率は

P0,0 = 1 − P0,1(9)となり，正規化 SNR 値が閾値より上の範囲に留まる確率は

P1,1 = 1 − P1,0(10)となる．正規化 SNR 値が γn を横切る確率 (5) ではで定められる．状態が 1 つ下の状態に遷移する条件付き確率は

N n TfPn,n−1 =, (n = 1, ..., N )Pr (n)

Pn,n =

1 − Pn,n+1 − Pn,n−1 , (0 < n < N )1 − P0,1 ,(n = 0)1 − PN,N −1 ,(n = N )(11)(3)となり，2 状態の有限マルコフ連鎖の定常状態確率 (6) はで定められる．自身の状態にとどまる条件付き確率は(rγγ
N = f d 2π exp(− )γ̄γ̄(4)で定められる．また (2)(3) にもあるように Nn は正規化 SNR 値が γn を横切る確率を表している．以下にその式を示す．

γPr (0) = 1 − exp(− )γ̄γPr (1) = exp(− )γ̄(12)(13)と定めることができる．また閾値は γγ̄ となる．このようにして定められた MS k の 2 状態の有限マルコフ連鎖を {s(k) (t)} で表すものとする．

公平性指標本稿では，短期間公平性評価の指標として STAFI を利用する．STAFI を定義するために，まず変数をいくつか定義する．

2.2

ν(t) =KX

I(s(k) (t) = 1)

(14)

k=1

ここで I(·) は指標関数 (indicator function) を表す．
よって，ν(t) は時刻 t に 2 状態の有限マルコフ連鎖の状態が 1 にある MS の数を表す．次に，{v(t)} を独立で [0, 1) 上の一様分布に従う確率変数とする．この確率変数を使って {c(1) (t)}，{c(2) (t)} を以下のように定義する．

 1 (s(1) (t) = 1, v(t) ∈ [0, 1/ν(t)))c(1) (t) =1 (ν(t) = 0, v(t) ∈ [0, 1/K))
 0 (otherwise)

(15)

(2)
(1)

 1 (s (t) = 1, v(t) ∈ [s (t)/ν(t), (s(1)(t) + 1)/ν(t)))c(2) (t) = 1 (ν(t) = 0, v(t) ∈ [1/K, 2/K))
0 (otherwise)(16)
このようにして定義された c (t) (i = 1, 2) は，MS i が時刻 t にサービスされるならば c(i) = 1，そうでなければ c(i) = 0 となる確率変数となる．この c(i) (t) を使用して，MS i の期間 [t0 , t0 + n) における累積サービス時
間 α(i) (t0 , t0 + n) (i = 1, 2) は
t0 X+n−1c(i) (t)(17)

t=t0のように表すことができる．ここで STAFI は以下のように定義される．

Gn (x) = P (|α(1)(t0 , t0 + n) − α(2)

表1

閾値

2.00
3.78
6.00

P0,00.991864
0.996083
0.999049(t0 , t0 + n)| ≥ x)
(18)

x は指標を表す数で，Gn (x) は x 以上になる確率を示し，各 MS の割り当ての差である．この値が小さいほどユーザ間の公平性は高いとえる．

3 シミュレーション結果
本節では 1FF スケジューリングを利用した短期間公平性についてのシミュレーションの結果について述べる．シミュレーションは，各 MS の定常状態を擬似乱数を用いて定め，遷移確率に従って状態を遷移させる．擬
似乱数の発生には GSL(GNU Scientific Library)[13] の乱数発生器 (ranlux) を用いた．
本節のシミュレーションでは以下のような環境を設定した．第 2 章で述べたように，レイリーフェージングチャネルを使用し m = 1 とする．Tf を 0.001sec，すな
わち Tf = 0.001 とし，ドップラー周波数を 10Hz，すな
わち f d = 10 として変化させる．STAFI の指標の値を40，すなわち x = 40，タイムスロット数を 256 回，す遷移確率P0,10.008136
0.0039170.000951

P1,00.031557
0.038734
0.050014

P1,10.968443
0.961266
0.949986

上記の値を用いてシミュレーションプログラムを作成した．閾値と MS の値を変化させ，シミュレーションを行った結果を表 2 に示す．
表2(i)α(i) (t0 , t0 + n) =なわち n = 256，各 MS の割り当ての差を求める回数を 106 回とする．また今回，MS の数を 20，30，40 個，すなわち K = 20, 30, 40 と変化させる．また，閾値が3.78dB の時に 1FF スケジューリングにおけるチャネル容量が最大になることから，閾値を 2.00，3.78，6.00dB，すなわち γγ̄ =2.00,3.78,6.00dB と変化させ結果の比較を行う．遷移確率を第 3 節の結果を元に求め，次に示す．

シミュレーション結果 (10−2 )条件 (閾値，MS の数)(2.00，20)(2.00，30)(2.00，40)(3.78，20)(3.78，30)(3.78，40)(6.00，20)(6.00，30)(6.00，40)

STAFI の値 100 個の平均値
3.03
0.27
0.01
8.43
3.50
1.30
4.46
3.70
3.07

表 2 から γγ̄ =3.78dB，K = 20 の時に STAFI の値が最大となる．これは，SNR γ̄γ =3.78dB はチャネル容量が最大となる値なので，トレードオフの関係により公平性が低くなり，STAFI が大きくなったと考えられる．また
γγ̄ =2.00dB，K = 40 の時に STAFI の値が最小となる．
これは，閾値が低いときにより多くの MS が状態１に存在する確率が高くなること，また MS の数を増加させることで１つの MS が選択される回数が減少することによって高い公平性が得られたと考えられる．もし MS1のみが状態 0 にあったとしても MS2 を選択する確率は1/(K − 1) であるから，公平性にあまり影響がないと考えられる．対して閾値が高いときは，可能性は非常に低いが MS1 が状態 1 にありその他の MS が状態 0 にある
場合に MS1 が選択される可能性が高く公平性に大きな問題が生じる可能性が高い．次に MS の数が 40 の場合は，トレードオフの関係による公平性の低下が起こる閾
値 3.78 の場合よりも，閾値 6 の場合の方が STAFI の平均値は 1.77 高いことから，MS の数が多いほど閾値を高く設定した場合の影響を受けやすいと考えられる．また
今回設定したどの閾値の場合においても MS の数が増加するほど公平性は高くなったことから，MS の数の影響を強く受けると考えられる．閾値 6 の場合は MS が 40個の平均値は MS が 20 個の平均値の約 68.83% になっているが，閾値 2.00 の場合は MS が 40 個の平均値はMS が 20 個の平均値の 0.33% になっている．この結果から閾値が低いほど MS の数による影響を受けると考えられる．次に推定値の分散を求めた結果を示す．
表3

推定値分散 (10−8 )条件 (閾値，MS の数)

推定値分散(2.00,20)(3.78,20)(6.00,20)

2.12
0.69
4.21

以上より，STAFI の推定値の分散が非常に小さいことが分かる．同様に上記以外の条件においても，非常に小さい結果になる．つまりこのシミュレーションによって得られた結果は非常に信頼性が高いことが分かる．

4 まとめ
本稿では，マルチユーザダイバーシチを利用したスケジューリングのチャネル容量と公平性の間のバランスについて注目し，1FF スケジューリングの短期間公平性に関する研究を行った．正規化 SNR 値の変化を表す確率過程はレイリーフェージングチャネルを採用し 2 状態の有限マルコフ連鎖で近似されるものとした．短期間公平性を評価する指標として STAFI を導入し，擬似乱数を用いた定常状態を定め，遷移状態における STAFI の値をシミュレーションにより調査を行った．閾値と MSの数を変化させ比較し，STAFI の値の変化を観察した．
その結果，以下のことが考察できた．

• MS の数が少ない場合は通信容量と公平性のトレードオフの影響を強く受け，MS の数が多いほど閾値が高いことによる影響を強く受ける．

• MS の数が増加するほど公平性は高くなる．
• 閾値が低いほど MS の数による影響を受ける．
• 閾値を高く設定することにより長期的な高い公平性を確保できるが，短期的な公平性に深刻な問題が発生する可能性がある．反対に閾値を低く設定することにより公平性は RR 方式に近づくが，同時に通信容量は低下する．

参考文献[1] D. Gesbert and M.-S. Alouini, “How much feedback is multi-user diversity really worth?,” Proc.
of IEEE ICC ’04 , pp.234–238, 2004.
[2] G. U. Hwang and F. Ishizaki, “Analysis of shortterm fairness and its impact on packet level performance,” Performance Evaluation, Vol.67, No.12,
pp.1340-1352, 2010.

[3] 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.
[4] 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.
[5] 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.
[6] Y. Liu, S. Gruhl and E. W. Knightly, “WCFQ:
an opportunistic wireless scheduler with statistical fairness bounds,” IEEE Trans. Wireless Commun., Vol.2, No.5, pp.1017–1028, 2003.
[7] Q. Liu, S. Zhou and G. B. Giannakis, “Queuingwith adaptive modulation and coding over wireless links: cross-layer analysis and design,” IEEE
Trans. Wireless Commun., Vol.4, No.3, pp.1142–1153, 2005.
[8] X. Qin and R. Berry, “Exploiting multiuser diversity for medium access control in wireless networks,” Proc. of IEEE INFOCOM ’03, pp.1084–1094, 2003.
[9] J. Razavilar, K. J. R. Liu and S. I. Marcus,“Jointly optimized bit-rate/delay control policy
for wireless packet networks with fading channels,”IEEE Trans. Commun., Vol.50, No.3, pp.484–494,
2002.
[10] G. L. Stüber, Principles of mobile communication, 2nd ed., Kluwer, 2001.
[11] D. Wu and R. Negi, “Utilizing multiuser diversity
for efficient support of quality of service over a fading channel,” IEEE Trans. Veh. Technol., Vol.54,No.3, pp.1198-1206, 2005.
[12] L. Yang, M. Kang and M.-S. Alouini, “On thecapacity-fairness tradeoff in multiuser diversitysystems,” IEEE Trans. Veh. Technol., Vol.56,No.4, pp.1901–1907, 2007.
[13] M. Galassi, J. Davies, J. Theiler, B. Gough,G. Jungman, M. Booth, F. Rossi, GNU ScientificLibrary, Vol.1 No.8, pp.145-159, 2006.