Opportunistic feedback fair スケジューリングの短期公平性の解析
2009SE028 福永拓郎 2009SE237 大谷太郎
指導教員： 石崎文雄

1 はじめに
近年，無線ネットワークにおいてマルチユーザダイバーシチ[1]を使用したパケットスケジューリングの研究が盛んに行われている[2，3，4]．マルチユーザダイバーシチ
はチャネル変動が独立な多数のユーザが存在するシス
テムにおいて，任意の時間で一部のユーザが他のユーザに比べて良好なチャネル利得を持つことから発生するダイバーシチである．マルチユーザダイバーシチを利用したスケジューリングでは，システム全体の情報理論的チ
ャネル容量とユーザ間でのサービスの公平性の間にトレードオフの関係があることが知られており，その両立が問題となっている．
サービス全体のチャネル容量とユーザ間でのサービスの公平性の間に存在するトレードオフにおいて適当なバランスを取るためにPF(Proportional Fair) スケジューリン
グが考え出された．PFスケジューリングでは，各ユーザのSNR値をそのユーザの平均SNR値で正規化し，正規化
SNR値の最も高いMobile Station(MS)をサービスのために選択する．各ユーザの正規化SNR値は独立同一分布に従うので，PFスケジューリングにおいては，各ユーザがサービスのために選ばれる確率は等しく，ユーザ間の厳密な長期間公平性(long term fairness) が達成できる．
しかしながら，PFスケジューリングでは各MSが基地局(BS)に正規化SNR値を報告することが必要であり，そのために帯域とMSの電力を消費するという問題がある．そこで，正規化SNR値をBSに報告する代わりにそれを量子化した値を報告するQPFスケジューリングが考えられた[4，5]．QPF スケジューリングは，各MSがBSに量子化された正規化SNR値を表わす量だけを報告すればよいので帯域の消費が少なく，また適切な量子化を行えばたとえ2段階の量子化であってもPFスケジューリングに比べて遜色のないチャネル容量を達成できることが知られている[6]．
この2段階の量子化を行うQPFスケジューリングのことを1FF(One-Bit Feedback Fair) スケジューリングと呼ぶ．また，1FFスケジューリングはPFスケジューリングと同じ長期間公平性を達成できる．しかしながら，1FFスケジューリン
グはMSの増加に応じてフィードバック負荷が漸近的に増えることがわかっている．その解決策として，ランダムアクセスフィードバックを用いたopportunistic feedback fair スケジューラが提唱されている．Opportunistic feedback fair
スケジューラはミニスロットを利用したスケジューリングで，各MSの正規化したSNR値が閾値を越えたものの中から，MSが任意の確率でフィードバックする．このフィードバックする確率をアクセス確率と呼び，以下 とする．以上がアップリンク伝送であり，MSからBSに情報が送られる仕組みである(図1)．ここで，2つ以上のMSがフィードバックされた時，ミニスロット内の情報は送信されない．
次に，BSからMSにサービスを提供するダウンリンク伝送を説明する．送信された情報の中から1つ選び，その情報を持つMSをサービスするものとする．ミニスロットに送信されたデータが１つもない場合は全てのMSの中からランダムに選びサービスを提供する．

図1

ミニスロット構造

無線通信網においてユーザ間の公平性は重要な性能指標であるが，マルチユーザダイバーシチを利用したス
ケジューリングにおけるユーザ間の公平性に関する研究はまだ十分ではない．公平性については，有限期間内での公平性の指標である短期間公平性と無限期間内での公平性の指標である長期間公平性を考えることができる．
短期間公平性に関する研究は現在までほとんど行われていない．短期間公平性は各ユーザの遅延性能など重要な性能指標と密接な関連があるので，たとえ長期間公平性が達成されていても短期間公平性が不十分なスケジューリングは，各ユーザの性能に深刻な問題を発生させることになる．
スケジューリングにおいて実現される短期間公平性はMS の初期状態に大きく依存することが知られており，短期間公平性に関するほとんどの研究は初期状態においてすべての MS が定常状態であることを仮定している[7]．
本研究では，opportunistic feedback fair スケジューラの短期的な公平性に焦点を当て，短期公平性の表す指標であるSTAFI(Statistical Time-access Fairness Index)[8]の解析を行う．また，MSの初期状態が定常状態であると仮定し，スケジューラのMSとミニスロットの数，閾値，アクセス確率を変化させSTAFIを観察し，解析結果を得る．

2 モデルと定式化
2.1 システムモデル
本研究において，システムは図2で示されるようにK個のMSと1つのBSから構成されるものであり，BSはK個のMSと の通信を行う ．短期的な公平性の尺度と してのSTAFIを考え，スケジューラが提供する短期的な公平性の性質を調べる．時間軸は単位時間 で分割されるものとする．

2.2 モデル化
時刻t(t=0，1，…)でのMSi（i=1，…，K）のSNRを (t)とする．SNR値 (t)が定常である時{ (t)}は以下の指数分布に従う．
P{(t)}=1-exp(-x/(1)と表すことができる．この時，状態0は，閾値をSNR値が超えていない場合であり，状態1は，閾値をSNR値が超えている場合である．

2.3 公平性指標

図2
また，

本研究では，スケジューリングの短期間公平性を評価するための指標としてとの間のSTAFIについて考える．STAFIは，選択回数の差による短期公平性である．時刻tにおけるMSiのサービス量を表す確率変数を(t)(t=0，1，…;i=1，…，K)とする．MS の[ ， +n）における選択回数， +n）は，システムモデル

はMSiが受信した平均SNR値であり，＝E[(t)]， +n）＝(2)で表される．Opportunistic feedback fair スケジューラのもとでは，正規化SNRを考える．正規化SNRは(t)/｝（i=1，…，K）で表される．また，フィードバックの負荷を減らすために，閾値 を任意に定め，(t)/< ならばMSi の チ ャ ネ ル 状 態 は 時 間 ｔ に お い て 0 で あ り ，(t)/であればMSiのチャネル状態は時間 ｔ において1である．MSの無線チャネルの正規化SNR値の変化を表す確率過程(t)｝はレイリーフェージングチャネ
ルモデル[9]で記述することができ，有限状態マルコフ連鎖でうまく近似できる[10]． 以下で，有限状態マルコフ連鎖 に つ い て 説 明 す る ． MSi の 無 線 チ ャ ネ ル 状 態 を(t)}(t=0，1，…;i=1，…，K)とすると， (t)/のときに1，それ以外の時に0となる．{ (t)}は2状態マルコフ連鎖によってうまく記述することができ，2状態マルコフ連鎖の遷移確率をP＝( ， )(i，j=0，1)とする(図3)．

(7)と表される．以上の式をもとに，STAFIうに定義する．
(x)=P(，(x) は以下のよ，(8)

ここで，，， はとの選択回数の違いを示す．また，STAFI は0(x) 1 であり，0に近いほど公平性が高く，1に近いほど公平性が低いことになる．

3 解析
本節では， (x)の解析をする．この目的を達成するために，選択回数の差に注目する．そのため，M １ とM以外のMSをひとくくりにし，M １ とM 以外のMSの遷移を表す（K-1）×（K-1）行列Rを以下に示す．
=・

図3 2状態マルコフ連鎖
また，γでの正規化SNRのレベルクロッシングレートχ( ) ，すなわちSNR値がγを横切る率は，以下のように表わされる[11]．
χ( )=exp(- )
(3)
ここで， はドップラー周波数を示す．次に2状態離散時間型マルコフ連鎖 (t)の定常確率ベクトルs=( ， )は，(1)より以下のようになる．
(4)
ここで，2状態マルコフ連鎖の遷移確率は，，=1-，(5)=1-(6)(9)

ここでの(i,j=0,1,…K-2)は，定常確率ベクトル{r(t)}のマルコフ連鎖の遷移確率 を示し ている．ま たr(t)はとして示す．従って，はM １ とM を除いた個のMSの間で，時刻 t-1の時，(K-2)個の内i個が状態1から，時刻tの時，(K-2)個の内j個が状態1になることを示す．そのため，定常確率ベクトルrは以下のように定式化できる．
(10)
ここで，， ，は，rのj番目の要素を示し，と は(4)式で表記されたものをりようしている．また2状態マルコフ連鎖｝は常にi=3，…，Kであり，定常状態ベクトルrは2状態マルコフ連鎖｝(i=3，…，K)の和の初期状態ベクトルでもある．次に，2状態マルコフ連鎖｝(i=1，…，K)の遷移確率である4(K-1)×4(K-1)
行列Qを以下に示す．

Q=P P R(11)

ここで，右辺についてPは左からそれぞれとの遷移確率であり，Rは(K-2)個のMSの遷移確率である． は，クロネッカー積であり，Pは(5)式と(6)式より定義し，Rは(9)式より定義する．
は，と以外の状態1であるMSの個数をk個，ミニスロットの数を ｎ個，アクセス確率をxとし，k個の全てのMSがフィードバックに失敗したものとする．従って，k=0，…，K-2:n=1，2…:01と範囲が決定し，定式化すると以下のようになる．
=[1-k(1-xx

本研究では以下のような環境を設定した．2節で述べた よ うに ，レイ リー フェ ージ ングチ ャネ ルを 使用し ，=0.001， =10 として変化させる．また，観測期間を64とした．ミニスロットの数は2，5，10，20とし，閾値は2.00dB，4.00dB，6.00dBとした．アクセス確率は0.2，0.4，0.6，0.8とした．

(12)

次に，4(K-1) 4(K-1)の対角行列Dを以下に定義する．
，D(z)=diag(，，)(13)

またこの時，対角行列Dは，Qに合わせた大きさにしている．そして，(i,j=0,1)は1 (K-1)ベクトルはそれぞれ以下によって場合分けして表わすことができる[12]．
[=[[

(14)
=+(1-(15)+(1-(16)+(1-(17)図5MS 数の変化に対する STAFI

図5はミニスロット数を10，閾値とアクセス確率はそれぞれ2.00dBと0.2の時，MSの数を20，30，40と変化させたものである．MSの数を変化させた場合，閾値などの条件に関わらずMSの数が多いほど公平性が高くなった．これは，ある1つのMSが選ばれる回数が少なくなり，互いの選ばれる差が小さくなったからだと考えられる．以後，MSの個数を30に固定する．

==である．さらに4(K-1)×4(K-1)行列のC(z)を以下によって定義する．
C(z)=D(z)Q(18)
この時，D(z)と Q は(13)式と(11)式により定義しており，nフレーム間でのとの選択回数の差の確率母関数(z) (n=1,2,…)が以下になる．
(z)=(r)C(z e(19)

ここで，(19)式は，確率母関数であり，逆変換を行わなければならない．ここで，FFT方式[13]を利用し逆変換を行い，STAFIと変数の関係性を調査する．

4 解析結果
本節では，opportunistic feedback fairスケジューリング
におけるnフレーム間でのSTAFIの解析について行った．
FFTに関する計算の部分はGSL(GNU Scientific Library)[14]のFFTライブラリを使用した．

図6 ミニスロット数の変化に対するSTAFI

ミニスロット数の変化によるSTAFIについて調査した（図6）．このとき，閾値は2.00dB，アクセス確率は0.2である．ミニスロット数を小さくするとサービスするMSを決めることができなくなる場合が増え，ランダムでMSを選択するため，公平性は高くなるが性能は悪くなることがわかった．
次に，閾値のみを変化させた（図7）．このとき，ミニスロット数は10，アクセス確率は0.2である．これより，閾値が大きくなるとSTAFIの分散が大きくなり，公平性に大きな影響を与えることが分かった．また，閾値が小さいほど公平性が高くなった．閾値を小さく設定することで，状態1のMSの個数が増えたためと考えられる．
最後に，アクセス確率のみを変化させた（図8）．ミニス
ロット数は10，閾値は2.00dBである．また，ここではMSの

参考文献

図7

図8

閾値の変化に対するSTAFI

アクセス確率の変化に対するSTAFI数を20とした．このとき， =0.4のとき短期的公平性は最も悪くなった．また，アクセス確率が小さい時，アクセス確率の増加に伴って短期公平性が悪くなる．しかし，ある特定の確率からは，アクセス確率の増加に伴って短期公平性は良くなる．

5 おわりに本稿では，opportunistic feedback fair スケジューラの短期的な公平性に関する研究を行った．正規化SNR値の変化を表す確率過程はレイリーフェージングチャネルを採用し2状態の有限マルコフ連鎖で近似されるものとした．短期間公平性を評価する指標としてSTAFIを導入し，遷移状態におけるSTAFIの値を解析により調査を行った．
MSの数とミニスロット数，閾値，アクセス確率を変化させ比較し，STAFIの値の変化を観察した．その結果，以下のことが考察できた．
・MSの数を変化させた場合，閾値などの条件に関わらずMSの数が多いほど公平性が高くなる．
・ミニスロットのみを変化させた時，ミニスロットの数が少ないほど公平性が高いが，システムの性能は悪くなる．
・閾値が大きくなると，深刻ではない不公平性については，起こる可能性が低くなるが，深刻な不公平性については，起こる可能性が高くなる．
・アクセス確率が小さい時，アクセス確率の増加に伴って
opportunistic feedback fair スケジューリングの短期的公平性は悪くなる．しかし，ある特定の確率からは，アクセス確率の増加に伴って短期公平性は良くなる．

[1] R. Knopp and P. A. Humblet, “Information capacityand power control in single-cell multiuser communications” Proc. of IEEE ICC '95, pp. 331–335, 1995.
[2] 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, pp. 3220–3227, 2007.
[3] L. Yang, M. Kang and M. S. Alouini, “On the capacity-fairness tradeoff in multiuser diversity systems,”
IEEE Trans. Veh. Technol., Vol. 56, pp. 1901–1907,
2007.
[4] F. Florén, O. Edfors and B. A. Molin, “The effect offeedback quantization on the throughput of a multiuser
diversity scheme,” Proc. of IEEE GLOBECOM 2003,
pp. 497–501, 2003.
[5] F. Ishizaki and G.U. Hwang, “Throughput performance of quantized proportional fair scheduling withadaptive modulation and coding,” Proc. of WirelessTelecommunication Symposium, 2009.
[6] G. U. Hwang and F. Ishizaki, “Design of a fair scheduler exploiting multiuser diversity with feedback information reduction,” IEEE Communications Letters,Vol. 12, pp. 124–126, 2008.
[7] F. Ishizaki, “Statistical time-access fairness index of
one-bit feedback fair scheduler,” Proc. of International Conference on Queueing Theory and Network
Applications (QTNA), 2011.
[8] Y. Liu, S. Gruhl and E. W. Knightly, “WCFQ: anopportunistic wireless scheduler with statistical fairness bounds,” IEEE Trans. Wireless Commun., Vol. 2,
pp. 1017–1028, 2003.
[9] G. L. Stüber, Principles of mobile communication,2nd ed., Kluwer, 2001.
[10] Q. Liu, S. Zhou and G. B. Giannakis, “Queuing withadaptive modulation and coding over wireless
link:cross-layer analysis and design,” IEEE Trans.
Wireless Commun. Vol. 4, pp. 1142–1153, 2005.
[11] M. D. Yacoub, J. E. Vargas Bautista, and L. G. de R.
Guedes,“ On higher order statistics of theNakagami-m distribution,” IEEE Trans. Veh.
Technol., Vol. 48, pp, 790-794, 1999.
[12] F. Ishizaki, “Analysis of statistical time-accessfairness index of opportunistic feedback fair scheduler,” Proc. of International Conference on Wirelessand Mobile Communications (ICWMC), 2012.
[13] H. C. Tijms, A first course in stochastic models, John
Wiley & Sons, 2003.
[14] M. Galassi, J. Davies, J. Theiler, B. Gough, G.
Jungman, M. Booth, F. Rossi, GNU Scientific Library,Vol.1 No.8, pp.145-159, 2006.