無線通信網のパケット・スケジューリングの公平性に関する研究
2009SE152
2009SE280

真下 知恵
2009SE214
田中 俊行
2009SE288
指導教員： 石崎 文雄

1 はじめに
1.1 研究背景
近年，携帯電話やスマートフォンなどの無線通信媒体の急激な普及により無線通信における帯域の利用が増加してきたため，無線通信網の通信量が増えることによる通信の不具合が発生している．
無線通信において帯域は最も貴重な資源の一つであり，帯域の効率的な利用はQoS(Quality-of-Service)の確保にとって重要である．このことから，効率的な通信帯域の使用法が注目されており，その方法の一つとしてマル
チユーザダイバーシチ(multiuser diversity)を利用する方法が挙げられる．マルチユーザダイバーシチとは，チャネル変動が独立な多数のユーザが存在するシステムにおいて，任意の時間で一部のユーザが他のユーザに比べて良好なチャネル利得を持つことから発生するダイバーシチのことである．
マルチユーザダイバーシチを利用することでシステム全体のチャネル容量を増加させることができるため，マル
チユーザダイバーシチを利用したスケジューリングの研究が盛んに行われてきている [1,2,3,7,10] ．マルチユーザ
ダイバーシチを利用したスケジューリングにおいては，システム全体のチャネル容量と個々のユーザの公平性の間にトレードオフが存在することが知られている．したがってマルチユーザダイバーシチを利用したスケジューリング
においては，チャネル容量と公平性の間のバランスのとれたスケジューリングを開発することが重要である．
無線通信網においてユーザ間の公平性は重要な性能指標であるが，マルチユーザダイバーシチを利用したスケジューリングにおけるユーザ間の公平性に関する研究はまだ十分ではない．公平性は，短期公平性(short-term fairness)と長期公平性(long-term fairness)に分類することができる．短期公平性は，スケジューリングが有限期間内に，一方長期公平性は，スケジューリングが無限期間内に通信時間などのネットワーク資源を複数の移動局(MS, Mobile Station)にいかに等しく分配できるかというスケジューラの能力を表す．短期公平性は，各ユーザの遅延性能など重要な性能指標と密接な関連があるので，たとえ長期公平性が達成されていても短期公平性が不十分なスケジューリング方式は，各ユーザの性能に深刻な問題を発生させることになる．

2スケジューリング方式

本稿ではセルラ通信網を想定し，基地局(BS，BaseStation)と MS の下りの通信(ダウンリンク)におけるスケジューリングに着目する．チャネル容量と公平性の観点からスケジューリング方式に着目すると，代表的なスケジューリング方式として RR(Round-Robin)方式と KH(Knopp andHumblet)方式[4]がある．
RR 方式はマルチユーザダイバーシチをまったく利用せず，MS のチャネル状態とは無関係に，各 MS に順番

野本 貴嗣
塚崎 啓義に通信が行われるスケジューリングである．マルチユーザ
ダイバーシチを利用しないためシステム全体のチャネル容量は低いが，ユーザ間の公平性は優れている．一方，KH 方式はマルチユーザダイバーシチを最大限に利用しているスケジューリングである．KH 方式においては，BSは常に最も SNR(Signal-to-Noise Ratio)値の高い MS に通信が行われるので，システム全体のチャネル容量は最大となる．しかし，平均 SNR 値の低い MS は通信されにくいので，MS 間の公平性に深刻な問題が発生することが知られている．
通信全体のチャネル容量と MS 間でのサービスの公平性の間に存在するトレードオフにおいて適当なバランスを取るために考え出されたのが PF(Proportional Fair)方式である．PF 方式は各 MS の SNR 値をその MS の平均SNR 値で正規化し，正規化 SNR 値の最も高い MS を通信のために選択する．各 MS の正規化 SNR 値は独立同一分布(independent and identically distributed)に従うので，各 MS に通信が行われる確率は等しく，MS 間の長期公平性が保証される．またシステム全体のチャネル容量も，マルチユーザダイバーシチを全く利用していない RR方式に比べて相当大きくなることが知られている．しかし，PF 方式では各 MS が BS に正規化 SNR 値を通知しなければならず，そのために帯域と MS の電力の消費が激しいという欠点がある．
PF 方 式 の 欠 点 を 克 服 す る た め に 1FF(One-bitFeedback Fair)方式が考え出された．この方式では，MSは 2 状態に量子化した正規化 SNR 値が任意の閾値を超えていれば BS に 1bit の情報を通知する．BS は閾値を超えた MS をランダムに選択し，通信を行う．各 MS は1bit のみ BS に通知するので帯域の消費を減らすことができる．しかし MS の数が増えると消費帯域が増えるという欠点がある．
MS の数が増えるとフィードバックによる消費帯域が増
え る と い う 1FF 方 式 の 持 つ 欠 点 を 改 良 し た も の がOFF(Opportunistic Feedback Fair)方式である[2]．OFF 方式では，フィードバックのためにミニスロットを利用する．この方式では，各 MS は各々の正規化 SNR 値が定めた閾値を超えているか判断し，超えたものはアクセス確率 でミニスロットに送信する．送信された MS が 2 つ以上の場合は，その送信は失敗する．この様子を図 1 に示す．ミニスロットの個数回このような試行が行われた後，送信された情報の中から 1 個を選び，その情報を持つ MS に通信が行われる．もしミニスロットに送信された情報がなければ，全 MS から 1 つランダムに選び通信が行われる．
本稿では，OFF スケジューリングの持つ短期公平性の性質を明らかにする．短期公平性について調査する指標の 1 つとして STAFI(Statistical Time-Access FairnessIndex) [5]と呼ばれるものがある．STAFI は，有限期間内の 2 つの移動局の通信された時間の差の確率分布に着目したものである．本研究では，シミュレーションによりSTAFI の値を推定することにより OFF 方式の短期公平性の性質を調べる．
SignalNo
SignalMS１No
SignalNo
Signal…
…

しているものとする．また有限状態マルコフ連鎖の遷移確率をとする．正規化SNR値が状態遷移を自身もしくは隣接した状態への遷移のみを行うとする．
よって二つの連続した状態を跨ぐ遷移の確率は0である
ことから
(3.1)

MS2を得る．
次に，隣接した状態への遷移確率について定める．
状態が 1 つ上の状態に遷移する条件付き確率は

図 1 ミニスロット,3 モデル
本節では，OFF 方式のシステムのモデル化と公平性指標の定義について説明する．
3.1 システムモデル
本稿では，システムモデルとして図 2 で示されるセルラ無線通信ネットワークを採用する[6]．1 つの BS に対して個の MS で構成されるダウンリンクチャネルシステムをOFF 方式によって行う．BS から MS への通信は，単位時間 ｆ で分割されてスケジューリングするものとし，時刻におけるの正規化 SNR 値をとする．今回のモデル化において各 MS の正規化 SNR の状態は任意に定めた閾値と閾値の間のどの状態空間に存在するかで考えられる．各 MS の正規化 SNR
値の状態変化を表す確率過程をとし，Nakagami-m モデルの 1 つであるレイリーフェージングチ
ャネルに従って記述できるものとする[10]．また正規化
SNR 値の状態の変化を表す確率過程は有限状態マルコフ連鎖でうまく近似できるものとする．
Base station

Mobile stations

BufferB

MS1

Wireless channel(3.2)

で定められる．状態が 1 つ上の状態に遷移する条件付き確率は,(3.3)

で定められる．自身の状態に留まる条件付き確率は(3.4)

で定められる ．また(3.2)(3.3) にあるように は正規化
SNR値が を横切る率を表している．ここで，平均SNR値を， ガンマ関数をで表す． または閾値とし をドップラー周波数とする．
前述のように各MSの無線チャネルはレイリーフェージングチャネルに従うためと定める．さらに，正規化
SNR値を0と1に量子化することで2状態の有限マルコフ連鎖とし，これによってうまく近似されると仮定すると，正規化SNR値が閾値より上に遷移する確率(3.2)は(3.5)

MS2正規化SNRが閾値より下に遷移する確率(2.3)は(3.6)
MS KScheduler

図2

正規化SNR値が自身の状態に留まる確率(2.4)における，閾値より下の範囲に留まる確率は無線通信ネットワークのシステムモデル

次に，正規化SNR値の変化を表す確率過程の有限状態マルコフ連鎖で近似したモデル[7]について考える．有限状態マルコフ連鎖の状態空間をとし，正規化
SNR値の境界点であるを定め，連続した空間を重複しないように分割する．
その結果，，となる．状態空間にある はSNR値がであることを表(3.7)
閾値より上の範囲で留まる確率は(3.8)
正規化SNR値が を横切る率は(3.9)

定められたMS の2状態の有限マルコフ連鎖をと表すものとする[11]．

は ， 擬 似 乱 数 を 用 い て 各 MS の 定 常 状 態 を 定 め ，(3.5)-(3.8)によって与えられる遷移確率(表4.1)によって状態を遷移させる．シミュレーションにおける擬乱数の発生にはGSL(GNU Scientific Library)[13]の乱数発生器を用いた．
本研究のシミュレーションでは以下のような環境を設定した．単位時間を0.001sec，すなわちとし，ドップラー周波数を10Hz，すなわち，タイムスロット数を256，すなわち，各MSの割り当ての差を求

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

める回数を ５ 回とする．今回，MSの数を20，30，40個，すなわち， ， アクセス確率を0.3，0.6，0.9，すなわち， ， と変化させる． また，閾値を2.00，4.00，6.00 dB，すなわち，，dBと2状態の有限マルコフ連鎖の定常状態確率は＝＝)(3.10))(3.11)と定めることができる．また閾値は となる．このようにして(3.12)

変化させて結果の比較を行う．また，STAFIの基準値 をMSの数に合わせて(MSの数，STAFIの基準値)={(20，4)，(30，3)，(40，2)}と変化させる．

ここでは指標関数を表す．従って， （ ） は時刻 に 2状態の有限マルコフ連鎖の状態が 1 にある MS の数を表す．次にを独立で上の一様分布に従う確率変数とすると，この確率変数を使用し，のように定義することができる．

，を以下.13)(3.14)
このようにして定義されたは MS が時刻ｔにサービスされるなら，そうでなければとなる確率変数である．このを利用して，MSi の 期 間における累積サービス時間
は

表4.１ 遷移確率
閾値P0,0P0,1

P1,0P1,1

2.00

0.99180.00810.03150.96844.00

0.99600.00390.03870.96126.00

0.99900.00090.05000.9499

遷移確率

上述の設定における遷移確率(3.5)-(3.8)の値を表4.1に示す．表4.1の値を用いて，シミュレーションプログラムを作成する．MSの数，閾値，アクセス確率を変えてシミュレーションを行った結果得られたSTAFIの推定値を表4.2-4.4に示す．
表4.2 MSの数が20個の場合でのシミュレーション結果(STAFIの基準値)
アクセス確率
0.3

0.6

0.9

2.00

0.18490.17350.13984.00

0.16390.15270.15706.00

0.12340.12360.1234閾値＝(3.15)と表すことができ，STAFI は(3.16)で定義できる．
(3.16)
は指標を表す数では 以上になる確率を示しており，は MS1 が割り当てられた回数，は MS2 が割り当てられた回数を表している．よって (3.16)の値が小さいほどユーザ間の公平性は高いと言える．

表 4.3 MS の数が 30 個の場合でのシミュレーション結果(STAFI の基準値)
アクセス確率
閾値0.3

0.60.94 シミュレーション結果

2.00

0.2436

0.35550.2038

本節では，OFF 方式の短期公平性の調査するために行ったシミュレーションについて説明する．
4.1 シミュレーション
本節ではOFF 方式を利用した短期公平性についてのシミュレーションの結果について述べる．シミュレーション

4.00

0.25560.22060.22666.00

0.1977

0.1977

0.1970表 4.4 MS の数が 40 個の場合でのシミュレーション結果(STAFI の基準値)
アクセス確率0.3

0.60.92.00

0.44570.69390.49964.00

0.53140.47670.45956.00

0.40930.40770.4064閾値

表 4.2-4.4 より，アクセス確率の場合に閾値が 6.00dB と 2.00dB の場合を比べると，閾値が 6.00dBの場合の方が，STAFI の値が高いことがわかる．これは閾値が 6.00dB と高い値であることから，多くの場合で全 MS が状態 0 に存在しており，全ての MS が等しく採用される傾向にあるためであると考えられる．アクセス確率が， の場合も同様であり，閾値が 2.00，4.00dB の場合よりも，6.00dB の場合のほうが公平性は高くなる．しかし閾値が 6.00dB の場
合は，公平性は良いものの OFF 方式が正しく動作しているとは言えず，どちらかと言うと RR 方式に近い形になっている．したがって，トレードオフの関係から公平性は高くなることが予想されるが，通信帯域を上手く使えているとは言えないだろう．
また，アクセス確率 0.9 の場合，MS の数が 20，30，40 のどの場合であろうと，閾値の変化による STAFIの値の増加率が 25%以下となり，グラフも横ばいに近い形となる(本稿の図 4.9 参照)という結果も得た．
これは，アクセス確率が高いため，MS がミニスロッ
トに送信される確率が低くなることにより，ランダムに選ばれる可能性が高くなるためだと考えられる．
最後にSTAFIの値の推定値の分散を求めた結果を示す．表4.2-4.4において示したシミュレーションによって得られたSTAFIの推定値の中からいくつかを選び，その推定値の分散を表4.5に示す．表4.5より，シミュレーションによって得られたSTAFIの推定値の分散は，いずれも推定値に比べて非常に小さいことがわかる．このことから，シミュレーションによって得られた推定値は信頼性が高いと言える．
表 4.5 推定値分散((MS の数,閾値,アクセス確率))
推定値分散(20,2.00,0.3)

2.2839(30,4.00,0.6)

2.7214(40,6.00,0.9)

2.05155 おわりにMS を遷移確率により遷移させた際の STAFI の値をシミュレーションにより調査した．閾値と MS の数，アクセス確率を変化させて，STAFI の値の変化を観察した．その結果，以下の事が判明した．
1．閾値が高いほど，アクセス確率の影響を受けづらくなり公平性は安定した．
2．MS の数が少ないほどミニスロットへの送信が失敗する確率が高い．
3．アクセス確率が， の場合は，の場合に比べミニスロットに送信が失敗する確率が高い．
4．以上の 2，3 より，MS の数が少なく，アクセス確率が高い（または低い）場合，全 MS からランダムで選ばれる確率が増えて公平性は RR 方式に近づくが，トレードオフの観点から通信容量は低下する．
今後さらに MS の数，ミニスロット数，アクセス確率などの数値を現実的な環境に近づけ，通信容量と公平性の間のトレードオフの関係を考えて上手く設定することで，より確かな研究結果が得られ，無駄の少ないスケジューリング方法となり得るのではないかと考えられる．

参考文献[1] D. Gesbert and M.-S. Alouini, “How much feedback ismulti-user diversity really worth?,” Proc.of IEEE ICC'04 , pp.234-238, 2004.
[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, No.5, pp.3220-3227, 2007.
[3] 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.
[4] R. Knopp and P. A. Humblet, “Information capacityand power control in single-cell multiusercommunications,” Proc. of IEEE ICC '95, pp.331-335,
1995.
[5] Y. Liu, S. Gruhl and E. W. Knightly, “WCFQ: anopportunistic wireless scheduler with statisticalfairness bounds,” IEEE Trans. Wireless Commun.,Vol.2, No.5, pp.1017-1028, 2003.
[6] Q. Liu, S. Zhou and G. B. Giannakis, “Queuing withadaptive modulation and coding over wireless links:
cross-layer analysis and design, ” IEEE Trans.
Wireless Commun., Vol.4, No.3, pp.1142-1153, 2005.
[7] X. Qin and R. Berry, “Exploiting multiuser diversity
for medium access control in wireless networks,” Proc.
of IEEE INFOCOM '03, pp.1084-1094, 2003.
[8] J. Razavilar, K. J. R. Liu and S. I. Marcus, “Jointlyoptimized bit-rate/delay control policy for wirelesspacket networks with fading channels, ” IEEE Trans.
Commun., Vol.50, No.3, pp.484-494,2002.
[9] G. L. Stüber, Principles of mobile communication, 2nded., Kluwer, 2001.
[10] D.Wu and R. Negi, “Utilizing multiuser diversity
for efficient support of quality of service over a fadingchannel,” IEEE Trans. Veh. Technol., Vol.54,No.3,pp.1198-1206, 2005.
[11] 石井佑美香，岡橋実加，安江佐織，“1FFスケジューリングの公平性に関する研究”南山大学数理情報学部卒業論文2012年1月