1FF 方式と RR 方式を組合わせた結合スケジューリングの公平性に関する研究
2008MI111 小谷 大地

2008MI291 吉村 詩織

2009SE255 清水 龍介

指導教員：石崎 文雄

はじめに当大きくなる．しかし PF スケジューリングでは各 MS がBS に正規化 SNR 値を報告することが必要であり，その近年，携帯電話など無線通信媒体が広く普及することにために帯域と MS の電力を消費するという問題がある．
より無線通信における帯域の利用が増加してきた．帯域
さらにこの PF スケジューリングの欠点を克服するたを効率的に利用することは QoS(Quality-of-Service) の確めに考案されたのが 1FF(One-bit Feedback Fair) スケ
保にとって重要である．帯域を効率良く利用するためのジューリングと呼ばれる方式である．1FF スケジューリ方法の一つとしてマルチユーザダイバーシチ (multiuserングの特徴として，MS は 2 状態に量子化した正規化 SNRdiversity) を利用することが挙げられる [1，3，4，8，11]．
値が任意の閾値を越えていれば BS に通知し，BS は閾値
マルチユーザダイバーシチとは，チャネル変動が独立を越えた MS をランダムに選択しサービスを行い，さらな多数のユーザが存在するシステムにおいてそれらを比に各 MS が送信する情報は 1bit のみに限られるので帯域較する際にそれ自身の平均で割ることにより変動の大きの消費を減らすことができる．
いチャネル容量を比較しやすくするという考え方である．
公平性に関してはスケジューリング期間を有限期間内マルチユーザダイバーシチを利用したスケジューリングで考慮した短期間公平性と無限に等しいほどの長さで観では，システム全体の情報理論的チャネル容量とユーザ察する長期間公平性とに大別できる．短期間公平性と長間でのサービスの公平性の間にトレードオフの関係があ
期間公平性は観察期間の違いのみで，共にスケジューリることが知られており，その両立が重要である [12]．シングがサービス時間などのネットワーク資源を複数の MSステム全体のチャネル容量とユーザ間でのサービスの公にいかに等しく分配できるかというスケジューリングの平性の間のトレードオフの関係の観点において両極端に能力を表す．短期間公平性は個々の MS のパケット遅延あるスケジューリングは，RR(Round-Robin) スケジューや損失などのパケットレベルの性能に大きな影響を及ぼリングと KH(Knopp and Humblet) スケジューリングです [2]．したがって，QoS 保証の観点からスケジューリンある．
グの短期間公平性の特性を知ることが重要である．短期
本稿では基地局 (BS，BaseStation) と移動局 (MS，Mo間公平性を調べるための指標の一つとして，[6] が提案しbile Stations) の通信におけるスケジューリングに着目す
た STAFI(Statistical Time-Access Fairness Index) と呼る．その中でチャネル容量と公平性の観点からスケジューばれる短期間公平性の指標がある．STAFI は有限期間内リング方法に注目すると，代表的なスケジューリング方の 2 つの MS のサービスされた時間の差の確率分布に着式として，上記の RR スケジューリング，KH スケジュー目したものである．
リングの他に PF(Proportional Fair) スケジューリングな
1FF スケジューリングは長期間で見ると非常に優れてどが挙げられる [5]．3 つのスケジューリングにはそれぞいるが短期間で見た場合同じ MS ばかり選んでしまい公
れ長所と短所が挙げられる．RR スケジューリングはマル平性に欠ける恐れがある．その点の改善のために 1FF ス
チユーザダイバーシチを利用せずに各 MS に順番にサーケジューリングと RR スケジューリングを組み合わせたビスを提供する方法である．公平性は非常に優れている
スケジューリングであれば公平性，チャネル容量，共にが通信速度の善し悪しも考慮せずに提供するためシステベストにできるのではないかという可能性が見えてきた．
ム全体のチャネル容量は低くなる．KH スケジューリン
本研究では，1FF スケジューリングと RR スケジューリ
グはマルチユーザダイバーシチを最大限に利用し，BS はングを組み合わせたスケジューリング方式 (本稿では結合SNR(Signal-to-Noise Ratio) 値の最も高い MS にサービスケジューリングと呼ぶ) の短期間公平性の性質を明らかスを提供する方法である．システム全体のチャネル容量はにする．特に短期間公平性評価の指標として STAFI を考最大となるが，平均 SNR 値の低い MS はサービスを提供え，結合スケジューリングの STAFI をシミュレーションされにくいので公平性に深刻な問題がある．この KH スにより調査する．また，この調査結果を 1FF スケジューケジューリングの問題を解決するために考え出されたのリングの結果と比較する．
が PF(Proportional Fair) スケジューリングである．PFスケジューリングは各 MS の SNR 値をその MS の平均 2 モデル
SNR 値で正規化し，正規化された SNR 値の最も高い MS
本節では、結合スケジューリングの内容と無線通信シをサービスのために選択する方法である．各 MS の SNRステムのモデル化，公平性指標の定義を行う．
値は独立同一分布に従うので各 MS がサービスを受ける確率は等しく，長期間の公平性が保証される．またシス 2.1 結合スケジューリング
テム全体のチャネル容量も，マルチユーザダイバーシチ
結合スケジューリングの内容を特定するためには，フを全く利用していない RR スケジューリングに比べて相 レーム中の何番目のスロットが 1FF スケジューリングで1

あるか，RR スケジューリングであるのかを決定する必要
Nn+1 Tfがある．さらに RR スケジューリングなら何番目の MS へ，(n = 0, ..., N − 1)
(2)
Pn,n+1 =Pr (n)のサービスかを表すことが必要になる．このときフレームの n 番目のスロットでどのようなスケジューリングが で定められる．状態が 1 つ下の状態に遷移する条件付き−1行われるかを表したものがサービス列 {mn }Tn=0である． 確率は条件として mn = 0 のときは 1FF スケジューリングが行
Nn Tf
Pn,n−1 =，(n = 1, ..., N )(3)
われ，mn > 0 のときは RR スケジューリングが行われPr (n)る．特に mn > 0 のときは，mn 番目の MS へのサービスで定められる．自身の状態にとどまる条件付き確率はが行われる．

2.2

 1 − Pn,n+1 − Pn,n+1 ,Pn,n =1 − P0,1 , 1−PN,N −1 ,システムモデル(0 < n < N )(n = 0)(n = N )(4)で定められる．また式 (2)，(3) にもあるように Nn は正規化 SNR 値が γn を横切る率を表している．以下にその式を示す．

√N = fdγγ
2π exp(− )γγ(5)となり，2 状態マルコフ連鎖の定常状態確率はγ
Pr (0) = 1 − exp(− ),γ

図 1 無線通信システムモデル

γPr (1) = exp(− )γ(6)と定めることができる．また 閾値は γ/γ とし fd をドッ本稿では，システムモデルとして図 1 で示されるセルプラー周波数とする．このようにして定められた MSk のラ無線通信ネットワークを考える．1 つの BS に対して K2 状態マルコフ連鎖を {s(k) (t)} で表すものとする．
個の MS で構成される下り通信 (ダウンリンクチャネル)
以上，式 (1)-(6) を用いて有限状態マルコフ連鎖の遷移システムによって行う．
確率を全て定める．
単位時間 Tf で分割されてスケジューリングするものとここで正規化 SNR 値を 0 と 1 に量子化することによっし，時刻 t(t=0,1,...) での MSi(i=1,...,K) の正規化 SNRて 2 状態マルコフ連鎖とし，これによってうまく近似さ値を z (i) (t) とする．各 MS の無線チャネル正規化 SNRれると仮定して式の変形を行うと，正規化 SNR が閾値よ値の変化を表す確率過程を z (i) (t) とし，Nakagami-m モり上に遷移する確率 (2) はデルの一つであるレイリーフェージングチャネルに従って記述できるものとする [10]．
N Tf
P0,1 =(7)
正規化 SNR 値の変化を表す確率過程を有限状態マルコPr (0)フ連鎖でうまく近似できるものとし，それで近似したモとなる [7]．さらに正規化 SNR が閾値より下に遷移する
デル [7] について考える．有限状態マルコフ連鎖の状態を確率(3) は[0,...,N ] とし，正規化 SNR 値の境界点である {γn }Nn=0 を定める．連続した区間を重複しないように分割する．そN Tf(8)
P1,0 =の結果 γ0 = 0，γl < γl+1 (l = 0, ..., N )，γN +1 = ∞ となる．
Pr (1)
状態空間にある n は SNR 値が [γn , γn+1 ) であることを表しているものとする．また有限状態マルコフ連鎖の遷 となる [7]．正規化 SNR が自身の状態に留まる確率 (4) に移確率を Pi,j (i, j = 0, ..., N ) とする．正規化 SNR の状態 おける，正規化 SNR 値が閾値より下の範囲に留まる確率
遷移を自身への遷移もしくは隣接した状態への遷移のみ は，行うとする．よって二つの連続した状態を跨ぐ遷移の確
P0,0 = 1 − P0,1(9)率は 0 であることから，となり，正規化 SNR 値が閾値より上の範囲に留まる確率
はPl,n = 0，|l − n| ≧ 2(1)P1,1 = 1 − P1,0(10)を得る．次に，隣接した状態の遷移確率について定める．
状態が 1 つ上の状態に遷移する条件付き確率は [9]となる．(7)，(8) 式の値は共に 0 以上 1 以下の定数である．

2.3

公平性指標

本稿では，短期公平性評価の指標として STAFI を利用する．STAFI を定義するために，まず変数をいくつか定義する．v(t) は時刻 t に 2 状態マルコフ連鎖の状態が 1にある MS の数を表す．

v(t) =K∑I(s(k) (t) = 1)

表 1 遷移確率閾値 [dB]

P00

P01

P10

P11

2.00
3.87
6.00

0.991684
0.996083
0.999049

0.008136
0.003917
0.000951

0.031557
0.038734
0.050014

0.968443
0.961266
0.949986(11)

表 1 の結果より，刻一刻変わる通信状態において 0 から 0，1 から 1 に遷移する確率は，0 から 1，1 から 0 に
ここで I(・) は指標関数 (indicator function) を表す．次に 遷移する確率に比べてはるかに高く，閾値を変えた場合
ν(t) を独立で [0,1) 上の一様分布に従う確率変数とする． もその傾向は変わらないことが分かった．0 か 1 での判断
この確率変数を使って c(1) (t)，c(2) (t) を以下のように定義 になるため，極短い時間においてではいきなり閾値を越する．
えるということは少なく，01，10 の遷移確率が低くなっていると考えられる．
(1)
ν(t) ∈ [0, 1/v(t)))
 1 (s (t) = 1，
STAFI の指標である x を 40 に固定しシミュレーショ
c(1) (t) =(12)1 (v(t) = 0，ν(t) ∈ [0, 1/K))
ンにより推定した結合スケジューリングの STAFI を表
0 (otherwise)
2 に示す．シミュレーションは 106 個のサンプルを取り，
(2)(1)
STAFI の推定を行った. 表 2 に示した STAFI の推定値は，
1 (s (t) = 1，ν(t) ∈ (s /v(t)，
シミュレーションによって得られた推定値
100 個の平均(s(1)(t) + 1)/v(t)))c(2) (t) =(13)値を示している．同様に 1FF スケジューリングの STAFI
1 (v(t) = 0，ν(t) ∈ (1/K, 2/K)) 0 (otherwise)を表 3 に示す．
k=1

このようにして定義された c(i) (t)(i =1,2) は，MSi が時刻t にサービスされるならば c(i) = 1，そうでなければ c(i) =0となる確率変数となる．この c(i) (t) を使用して，MSi の期
間 [t0 , t0 +n) における累積サービス時間 α(i) (t0 , t0 +n)(i =1, 2) は(i)α (t0 , t0 + j) =t0∑
+j−1c(i) (t)(14)

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

表 2 結合スケジューリングのシミュレーション結果(STAFI の指標値 x=40)
条件 (閾値 [dB]，MS の数)

STAFI の推定値における 95%信頼区間(2.00，20)(3.78，20)(6.00，20)(2.00，30)(3.78，30)(6.00，30)(2.00，40)(3.78，40)(6.00，40)

2.06 × 10−2 ± 2.27 × 10−5
6.74 × 10−2 ± 5.37 × 10−5
3.67 × 10−2 ± 3.64 × 10−5
0.15 × 10−2 ± 7.96 × 10−6
2.66 × 10−2 ± 3.31 × 10−5
3.06 × 10−2 ± 3.03 × 10−50.01 × 10−2 ± 1.27 × 10−60.92 × 10−2 ± 1.95 × 10−5
2.55 × 10−2 ± 3.14 × 10−5

Gj (x) = P (|α(1) (t0 , t0 + j) − α(2) (t0 , t0 + j)| ≧ x) (15)x は指標を表す数で Gj (x) は x 以上になる確率を示し，
表 3 1FF スケジューリングのシミュレーション結果
各 MS の割り当ての差である．この値が小さい程ユーザ(STAFI の指標値 x=40)間の公平性は高いことがいえる．
条件 (閾値 [dB]，MS の数) STAFI の推定値における 95%信頼区間

3

シミュレーション(2.00，20)(3.78，20)(6.00，20)(2.00，30)(3.78，30)(6.00，30)(2.00，40)(3.78，40)(6.00，40)

2.38 × 10−2 ± 2.90 × 10−58.43 × 10−2 ± 5.74 × 10−54.47 × 10−2 ± 3.81 × 10−50.18 × 10−2 ± 9.14 × 10−6
3.50 × 10−2 ± 3.75 × 10−53.73 × 10−2 ± 3.16 × 10−50.01 × 10−2 ± 2.12 × 10−6
1.30 × 10−2 ± 2.50 × 10−5
3.10 × 10−2 ± 3.40 × 10−5

シミュレーションは，各 MS の定常状態を擬似乱数を用いて定め，遷移確率に従って状態を遷移させる．擬似乱数の発生には GSL(GNU Scientiﬁc Library)[13] の乱数発生器 (ranlux) を用いた．本節のシミュレーションでは以下のような環境を設定した．第 2 章で述べたように，レイリーフェージングチャネルを使用し m =1 とする．
表 2 より閾値 [dB]=2.00，3.78，6.00 において，K=20，Tf =0.001sec，ドップラー周波数 f d=10Hz として変化さ
3.78dBの時に，STAFI の値が最大となることが分かる．
せる．STAFI の指標の値 x= 40，タイムスロット数 n=256回，各 MS の割り当ての差を求める回数を 106 回とする． 今回設定したどの閾値の場合においても MS の数を 20 かまた今回，MS の数 K を 20，30，40 と変化させる．ま ら 40 に増加させた場合．閾値 6.00 の場合，MS の増加にた，閾値が 3.78dB の時に 1FF スケジューリングにおけ よって約 31.2%，閾値 3.78 の場合，約 86.1%，閾値 2.00
るチャネル容量が最大になることから，閾値 γ/γ[dB] を の場合，約 99.7%STAFI の推定値が小さくなっている．
2.00，3.78，6.00 と変化させ結果の比較を行う．遷移確率 この結果から閾値が低いほど MS の数による影響を受けると考えられる．
を第 3 節の結果を元に求め，表１に示す．

次に表 3 より，このシミュレーションにおいて，閾値 [4] H. Kim and Y. Han, “An opportunistic channel qual6.00 の場合，MS の数を 20 から 40 に増加させることに
ity feedback scheme for proportional fair schedulより約 30.6%，閾値 3.78 の場合，約 84.6%，閾値 2.00 のing,” IEEE Communications Letters, Vol.11, No.6,
場合，約 99.5%公平性が高くなっている．この結果から，pp.501–503, 2007.
1FF スケジューリングの場合でも閾値が低いほど MS の数 [5] R. Knopp and P. A. Humblet, “Information capacityによる影響を受けると考えられる．この結果を表 2 の結果
and power control in single-cell multiuser communiと比較すると，結合スケジューリングは 1FF スケジュー
cations,” Proc. of IEEE ICC ’95, pp.331–335,1995.
リングに RR スケジューリングを組み込ませているので，[6] Y. Liu, S. Gruhl and E. W. Knightly, “WCFQ:
閾値の変化による MS の選択は 1FF スケジューリングの
an opportunistic wireless scheduler with statistical
方が多くなることが予想できた. しかし，閾値の変化に伴
fairness bounds,” IEEE Trans. Wireless Commun. ,う STAFI の変化率に大きな違いはなく，全体として結合Vol.2, No.5, pp.1017–1028, 2003.
スケジューリングの方が STAFI の推定値が小さくなるこ[7] Q. Liu, S. Zhou and G. B. Giannakis, “Queuing withとが見て取れる.
adaptive modulation and coding over wireless links:
表 2，3 より， STAFI の推定値における 95%信頼区間
cross-layer analysis and design,” IEEE Trans. Wireが非常に小さいことがわかる．つまりこのシミュレーショ
less Commun. , Vol.4, No.3, pp.1142–1153, 2005.
ンによって得られた結果は非常に信頼性が高いと言える．
[8] X. Qin and R. Berry, “Exploiting multiuser diver4 まとめ
sity 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する研究を行った．正規化 SNR 値の変化を表す確率過程
packet networks with fading channels,” IEEE Trans.
はレイリーフェージングチャネルを採用し 2 状態の有限Commun. , Vol.50, No.3, pp.484–494,2002.
マルコフ連鎖で近似されるものとした．短期間公平性を[10] G. L. Stiiuber, Principles of mobile communica評価する指標として STAFI を導入し，疑似乱数を用いた
tion, 2nd ed., Kluwer, 2001.
定常状態を定め，遷移状態における STAFI の推定値をシ[11] D.Wu and R. Negi, “Utilizing multiuser diversity
ミュレーションにより調査を行った．閾値と MS の数を
for eﬀcient support of quality of service over a fading
変化させ比較し，STAFI の推定値の変化を監査した．そchannel,” IEEE Trans. Veh. Technol. , Vol.54,No.3,の結果，以下のことが考察できた．
pp.1198–1206, 2005.
• MS の数が少ない場合は通信容量と公平性のトレードオフの影響を強く受け，MS の数が多いほど閾値 [12] L. Yang, M. Kang and M.-S. Alouini, “On thecapacity-fairness tradeoﬀ in multiuser diversity sysが高いことによる影響を強く受ける．
tems,” IEEE Trans. Veh. Technol. , Vol.56, No.4,• MS の数が増加する程公平性は高くなる．
pp.1901–1907, 2007.
• 閾値が低いほど MS の数による影響を強く受ける．
[13] B. Gough, F. Rossi, G. Jungman, J. Davies, J.
• 閾値を高く設定することにより長期的な高い公平性
Theiler, M. Booth, M. Galassi, GNU Scientiﬁc Liを確保できるが，短期間公平性に深刻な問題が発生
brary, Vol.1 No.8, pp.145–159, 2006.
する可能性がある．反対に閾値を低く設定すること[14] 石井佑美香，岡崎実加，安江佐織，“1FF スケジューにより公平性は RR 方式に近づくが，同時に通信容リングの公平性に関する研究”南山大学 数理情報学部
量は低下する．
情報通信学科 2011 年度卒業論文要旨集.

参考文献[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.