1FF スケジューリングにおけるパケットの待ち行列遅延の解析に関する研究
M2010MM028 椴山 馨
指導教員：石崎 文雄

研究背景

クの負荷が小さい時に CKH スケジューリングは RR ス
ケジューリングよりサービスレートが高くなり，反対に現在，第 4 世代移動通信システムといわれる次世代移ネットワークの負荷が大きくなると RR スケジューリン
動通信ネットワークの開発が進んでおり，無線データサー
グは CKH スケジューリングよりサービスレートが高くビスに対する需要は増加を続けている．無線データサーなる事が明らかにされた．
ビスのトラヒックは，マルチメディア会議のようなリア本研究では，無線通信ネットワークにおけるマルチユールタイムのトラヒックとファイル転送のような非リアルザダイバーシチを利用したパケットスケジューリングにタイムのトラヒックが混ざり合っている．このような無線ついて焦点をあてる．特に，AMC(Adaptive Modulation
通信ネットワークにおいては，QoS(Quality of Service)and Coding) を利用した 1FF(One-bit Feedback Fair) ス
保証が不可欠であり，遅延やパケット損失がリアルタイケジューリングについて考える．1FF スケジューリング
ムトラヒックに大きく影響する．無線通信ネットワークとは，QPF(Quantized Proportional Fair) スケジューリ
は有線通信ネットワークに比べ，非常に信頼性が低く，環ングに基づいてアルゴリズムが構築されており，本研究境によって通信信号が大きく変化するため厳密な QoS 保
では量子化を 2 状態にした QPF スケジューリングを 1FF証の妨害になる．つまり，無線通信ネットワークの QoSスケジューリングと呼ぶ．このようなパケットおきにスケ保証においては，効率的な有効帯域の利用のためにスケジューリングを行なうキューイングモデルは流体キューイジューリングや通信制御が重要な鍵になる．
ングモデルよりスケジューリングアルゴリズムの性能評
無線通信ネットワーク上で有効帯域を得るための方法
価に適していると考える．その理由として，流体キューイとして，ダイバーシチを利用する事が挙げられる．ダイングモデル上では複数のユーザが同時に送信するが，実際バーシチによって，送信機と受信機の間に存在する複数のネットワーク上ではユーザはパケットごとにスケジューの独立の信号経路から高いチャネル容量を持つ経路を選リングされているからである．また，本研究では離散時間択する事ができる．中でも，マルチユーザダイバーシチでのキューイングモデルに関して議論する．各ユーザのを導入したものとしては KH(Knopp and Humblet) スケ
無線チャネルプロセスはレイリーフェージングチャネルをジューリング [1] がある．マルチユーザダイバーシチとは，用い，その上で 1FF スケジューリング下でのサービスプ
チャネル変動が独立な複数のユーザが存在するシステムロセスの実効帯域関数を決定する．決定した実効帯域関において，良好なチャネル利得を持つユーザが選択させ数から，実効帯域理論に基づいた離散時間キューイングる事をいう．
モデルを解析する．その解析結果から，1FF スケジュー
近年，いくつかの研究でマルチユーザダイバーシチをリング下の任意のユーザのパケットの待ち行列遅延のテ利用したスケジューリングアルゴリズムや通信制御の研イル分布の推定する．また，本研究では 1 番目のユーザ究が行なわれている．そして，それらの研究によってマを任意のユーザとし，そのユーザをタグユーザと呼ぶ．
ルチユーザダイバーシチを利用する事でシステム全体の最大スループットとチャネル容量を大幅に増加させる事 2 システムモデルが明らかにされた．それらの研究に反して、参考文献 [2]本モデルは，無線チャネル上にマルチトラヒックが存在の Wu と Negi はマルチユーザダイバーシチを利用したスするシステムモデルである．また，時間はタイムスロッケジューリングアルゴリズム下で発生する遅延を無線通
ト Tf で分割され，１スロット毎にパケットがサービス
信ネットワークの QoS 保証の問題としている．彼ら，レされる事を仮定する．このモデルでは，基地局から K 個イリーフェージングを想定した K 人のユーザが存在する(K = 1) のモバイル端末 (ユーザ) にデータを送信するセダウンリンクチャネルの QoS 保証に関して議論している．
ルラー無線ネットワークのダウンリンクについて考える．
最近では，参考文献 [2] のようにパケットの待ち行列遅延に着目した無線ネットワークの QoS 保証に関する研究も 2.1 チャネルモデル増えており、参考文献 [3] もその一つである．参考文献 [3]各ユーザの無線チャネルプロセスは Nakagami-m チャ
は参考文献 [2] と同様に無線ネットワークの遅延に関する ネルモデルの m = 1 の場合のレイリーフェージングチャ研究を行なっており，さらにパケットの待ち行列遅延を ネルになる事を仮定する．
解析するために，実効帯域理論を用いた手法を提案してまず，k 番目 (k = 1, ..., K) のユーザの無線チャネルプいる．彼らは，マルチユーザダイバーシチを利用してる ロセスを {Z (k) }∞ と定義する．Z (k) とは k 番目のユー
nnn=0
CKH(Constant version of the Knopp and Humblet) ス ザの n スロット時の SNR(Signal-to-Nosie Ratio) 値を示
ケジューリングと利用していない RR(Round Robin) ス している．すべての無線チャネルプロセスは各ユーザ毎ケジューリングの比較している．その結果，ネットワー に独立であり，定常であると仮定し，加えて無線チャネ1

ルプロセスは一様である事も仮定する．
ルチユーザダイバーシチを利用する事ができる．1FF ス
次に，マルチユーザダイバーシチを利用するため無線 ケジューリング下では，全てのユーザのチャネルグレー(k)チャネルプロセスの正規化された SNR 値を L 個のグレー ド Ln を知る事ができると仮定する．各ユーザの中で最ドで量子化すると仮定し，そのときの各グレードの正規 も高いチャネルグレードを τn∗ とし，τn∗ を以下のように
γ0 = 0，̂γl < γ̂l+1 ， 定義する．
化された SNR 値 {γ̂l }L
l=0 (γ̂l = γl /γ ，̂
l = 0, ..., L − 1，γ̂L = ∞) とする．また，γ = E[γ] は受τn∗ = max L(k)(7)
nk∈{1,...,K}
信した SNR 値の平均値である．ここで L = {0, ..., L − 1}(k)(k)
についての確率変数 Ln を定義する．確率変数 Ln は もし最も高いチャネルグレードを持つユーザが複数存在(k)(k)
γ̂l < Zn /γ < γ̂l+1 ならば Ln = l となる．またグレー するならば，ランダムで 1 個のユーザが選択され，n ス(k)ド数が L の時，Ln は n スロット時の k 番目のユーザの ロット時にパケットを送信する事ができる．また，本モ
デルではパケットの送信可能の有無，送信レートは AMC
チャネルグレードと考える．
∞
チャネルグレードプロセス {Ln=0 }(k = 1, ..., K) は によって決定される．AMC については次節で説明を行
FSMC(Finite-State Markov Chain) となる [4]．低速フ なう．
ェージングかつ Tf が小さい値であるという条件下では， 2.3 Adaptive Modulation and Coding
チャネルグレードプロセスは隣接する状態にのみ遷移す
AMC は無線リンクの状態に応じて変調方式や符号化方る．また，P = (pi,j )(i, j ∈ L) を FSMC の遷移行列と仮式，及びその他の信号やプロトコルパラメータを調整す定し，遷移確率を求めていく．以上の仮定をもとに，以る仕組みの事である．AMC のプロセスは動的なもので下の式を得る事ができる．
あり，信号やプロトコルパラメータは，無線リンクの状
pi,j = 0,|i − j| ≥ 2(1) 態が変わるにつれて変化する．本研究では，参考文献 [5]で示された AMC が使われているものと仮定する．AMC
次に，隣接する状態への遷移確率は以下のようになる． は 1 ms 毎に状態が変化するものとし 8 段階のモードを持つとする．8 つのモードの SNR 値の閾値は表 1 の通りでχ(γi+1 )Tf
pi,i+1 =,i = 0, . . . , L − 2(2) ある．例えば，モード 1 は SNR 値が [8.01273, 11.82217)
πidB であるときに使われ，その時のサービスレートは 1 に
χ(γi )Tfpi,i−1 =,i = 1, . . . , L − 1(3) 等しい．Rate は 1 スロット当り送信できるパケット数をπi表している．
χ(γ) はレイリーフェージングチャネルでの SNR 値 γ のレべルクロスレートであり，以下の式が与えられる．
表 1 AMC モード 8 区分 (閾値)()√モード Ratex(SNR:dB)γγ
χ(γ) = 2π fd exp −(4)γγ000.0≤x<8.01273
118.01273≤x<11.82217
fd はドップラー拡散周波数である．また，πi (i ∈ L) は
22
11.82217≤x<16.24006
FSMC おいて状態 i での定常確率である．定常確率 πi (i ∈3316.24006≤x<18.84206
L) は以下の式で得られる．
4418.84206≤x<22.58435
5522.58435≤x<24.97838
πi = exp(−γi /γ) − exp(−γi+1 /γ)(5)∑L−16624.97838≤x<28.57040
さらに， j=0 pi,j = 1 と式 (1)-(3) より，以下の式を
7728.57040≤x得られる．

 1 − pi,i+1 − pi,i−1 ,pi,i =1 − pi,i+1 , 1−pi,i−1 ,(i = 1, . . . , L − 2)(i = 0)(i = L − 1)3(6)以上，式 (1)-(3)，(6) より遷移行列 P を得る事ができ，また定常分布は式 (5) によって得られる．

2.2

1FF スケジューリング

1FF スケジューリングとは，各ユーザの SNR 値を正規化したものを 2 状態に量子化し，量子化された正規化
SNR 値が最も高いユーザを選択しサービスをするスケジュールである．また，量子化された正規化 SNR 値を(k)チャネルグレード Ln と呼ぶ．本モデルでは各ユーザのチャネルプロセスが独立であると仮定している事から，マ

実効帯域理論よる解析

本節では，実効帯域理論 [6] に基づいた解析手法を示す．
実効帯域理論は，すでに無線パケットネットワークの研究の分野で広く利用され，接続許可制御やリソース分配の基礎として利用されている．ここで解析の行なうためにいくつかの仮定をする．まず，マルチユーザダイバー
シチのチャネルグレードの量子化の分割数を L = 2 とする．次に，パケット誤り率は受信した SNR 値と符号化スキームによって決定される．受信した SNR 値が量子化の閾値 γ̂1 を超えた場合，パケット誤り率は無視してもよいとし，また常にパケットの送信が可能になる．さらに，本研究では参考文献 [6] を基に，1FF スケジューリングとAMC を組み込んだ新たな実効サービス帯域関数の定式化を提案する．また，AMC の利用を考えているため，1スロットあたりに送信できるパケット数は AMC に依存する．以上の仮定を基に，1FF スケジューリングについて解析を行なう．

3.1

実効到着帯域関数

本節では，始めに GE(Gärtner-Ellis) limit の概念から説明していく．一般到着プロセスの累積到着プロセス Ãn のGE limit ΛA (θ) を定義する．Ãn とは時間区間 [0, n) の累積到着プロセスである．ΛA (θ) は lim n−1 log E exp(θÃn )n→∞

スレートに収束し，また θ ↑ ∞ である時に最小サービスレートになる事が知られている．
ここから，1FF スケジューリングと AMC を組み込んだ実効サービス帯域関数の新たな定式化について説明する．
(1)
マルコフ連鎖 {(Ln , Sn )} のマルコフ変調過程を {Cn } と∑K(k)し，またこの時の Sn は Sn = k=2 Ln である．本モデルのサービスプロセスの GE limit と実効サービス帯域関数を表すために，いくつかの行列を定義する必要がある．
まず，始めに K × K の行列 R を定義する．
( )min(i,j)∑i[R]i,j =pk pi−kk 1,1 1,0k=max(0,i+j−K+1))(K −1−i
K−1−i−j+kpj−k(11)0,1 p0,0j−kと記述する事ができる．次に，実効到着帯域関数 ξA (θ) =ΛA (θ)/θ を定義する．ξA (θ) は単調増加である事が知られており，また θ ↓ 0 である時に平均到着レートに収束し，θ ↑ ∞ である時に最大到着レートになる．
次に，本研究でのモデルについて記述していく．ONOFF ソースから到着プロセス {An }∞[R]i,j (i, j = 0, . . . , K − 1) は (i, j) 番目の行列 R の要素
n=0 が発生すると仮定し，これは到着プロセスのバースト作用も組み込まれ である．[R]i,j は L(k)n = 1 であるプロセスが i 個から jている．ON-OFF ソースは，ON 状態と OFF 状態の異 個に変わる確率である．次に，2K × 2K の行列 Q1FFなる二つの状態を持っている．OFF 状態ではパケットは を定義する．Q1FF は Q1FF = P ⊗ R であり, ⊗ はクロ発生しないが，ON 状態では確率 λ でパケットが 1 個発 ネッカー積を表している．さらに，GK × GK の対角行生する. ON 状態から OFF 状態に遷移する確率を 1 − α 列 D1FF (θ) を定義する．G とは AMC とチャネルグレーと定義し，反対に OFF 状態から ON 状態に遷移する確 ドを組み合わせたモード数となる．そして，モード数 G率を 1 − β と定義する．このとき α と β は，0 ≤ α ≤ 1， はチャネルグレードの閾値 γ̂1 によって変化する．AMC0 ≤ β ≤ 1 である．以下の ON 状態の平均期間 BON ， がモード g(g = 0, . . . , G − 1) のときの，AMC と組み合OFF 状態の平均期間 BOFF ，平均到着レート ρ の３つの わせた時のチャネルグレードを以下のように表す事がでパラメータは ON-OFF ソースの決めるために使われる． きる．
これらのパラメータは α，β ，λ によって表す事ができる．
(12)g ∗ = {g|ψg ≤ γ̂1 γ < ψg+1 }11λ(1 − β)BON =, BOFF =, ρ=(8)ψg は AMC のモード g の閾値を表している．この時，AMC1−α1−β2−α−βの各モードの送信レートを aĝ とすると，チャネルグレー
そして，本研究での到着プロセスの GE limit ΛA (θ) と実 ドと組合せたときの各モードの送信レート â を以下のよĝ
効到着帯域関数 ξA (θ) は次のように与えられる．
うに表す事ができる．ψg = γ̂1 γ となる g が存在しない場
合は以下のようになる．
logδA (θ), θ ≥ 0 (9)ΛA (θ) = logδA (θ), ξA (θ) ={θaĝ
if ĝ ≤ g ∗(ĝ = 0, . . . , G)âĝ =(13)√∗2aĝ−1 if ĝ ≥ g + 1 (ĝ = 0, . . . , G)
δA (θ) は δA (θ) = ζ(θ) + ζ(θ) − bφ(θ)，φ(θ) = 1 − λ +λeθ ，ζ(θ) = (αφ + β)/2，b = α + β − 1 によって得る事ができる．
3.2

1FF スケジューリング下での実効サービス帯域関数

本節では，まず一般サービスプロセスための実効サービス帯域関数について定義する．始めに，一般サービスプロセスの GE limit について考える．確率変数 C̃n (n =0, 1, . . .) を時間区間 [0, n) の累積サービスプロセスと仮定し，その時の ΛC (θ) を累積サービスプロセス C̃n の GElimit であると考える．累積サービスプロセス C̃n の GE
limit は ΛC (θ) = lim n−1 log E exp(θC̃n ) のように記述

この時の対角行列 D1FF (θ) を âĝ を用いて以下のように定義する．
g∗ × Kz }| {eâg∗ +1 θ + K − 1,D1FF (θ) =diag(1, . . . , 1, eâg∗ +1 θ , . . . ,KeâG θ + K − 1. . . , eâG θ , . . . ,)(14)
K
次に，ψg = γ̂1 γ となる g が存在する場合は，âĝ = aĝ
(ĝ = 0, . . . , G − 1) となり，対角行列 D1FF (θ) を以下のように定義する．

n→∞する事ができる．以上の事から関数 ξC (θ) は以下のようになる．
ΛC (−θ)(10)ξC (θ) = −θg∗ × Kz }| {eâg∗ +1 θ + K − 1,
D1FF (θ) =diag(1, . . . , 1, eâg∗ +1 θ , . . . ,KeâG−1 θ + K − 1. . . , eâG−1 θ , . . . ,)(15)
K
式 (10) は実効サービス帯域関数と呼ばれている．また，
式 (10) は ξC (θ) = −Λ−C (θ)/θ と書き換えられる．実効 最後に，GK × GK の行列 C1FF (θ) = Q1FF D1FF (θ) をサービス帯域関数 ξC (θ) は，θ ↓ 0 である時に平均サービ 定義する．以上の行列から，1FF スケジューリング下で

Λc (θ) = logδC (θ)(16)δC (θ) は C1FF (θ) の最大固有値である．以上より，実効サービス帯域関数 ξC (θ) は以下のように定義できる．
ξC (θ) = −3.3

logδC (−θ)
θ(17)

Effctive bnadwidth of Service Process (kbps)のサービスプロセスの GE limit Λc (θ) を得る事ができる．

パケットの待ち行列遅延について

実効帯域理論を用いて，定常状態におけるパケットの待ち行列遅延のテイル分布を近似的に得る事ができる．
まず，確率変数 D がタグユーザのパケットの待ち行列遅延であると定義する．パケットの待ち行列遅延のテイル分布 P (D > n) の近似式は以下のようになる．

4103102101

1000ESBF-Condition1
ESBF-Condition2
ESBF-Condition3

12Theta3

4510010-1(18)また，θ∗ は式 (19) の実数解である．

ΛA (θ) + ΛC (−θ) = 04

図 1 実効サービス帯域関数

Tail probability

P (D > n) ≈ exp(ΛC (−θ∗ )n)10(19)

解析結果
10-2

Simulation (EABF-Condition1)
Analysis (EABF-Condition1)
Simulation (EABF-Condition2)
Analysis (EABF-Condition2)

050100150200250300
本節では，1FF スケジューリング下でパラメータを変n化させ，同条件で解析とシミュレーションを行い，数値結果を比較する．また解析環境は，パケットサイズが 250
図 2 パケットの待ち行列遅延のテイル分布
B，モバイル端末数 (ユーザ数) が 10 個，ドップラー拡
散周波数が 10 Hz，1 タイムスロットが 1 ms とする．また．そして，パケットの待ち行列遅延のモデル化を行いた，図 1，2 の ESBF とは実効サービス帯域関数を示し，解析結果を得る事ができた．また、シミュレーション結EABF とは実効到着帯域関数を示している．
果と比較をし，提案手法の正確性も確認する事ができた．
まず始めに，実効サービス帯域関数の解析結果の図 1 を見る．図 1 中にある実効サービス帯域関数の設定は，γ̂1 = 参考文献
2.0 dB として３つのパラメータを用意した．Condition1[1] R. Knopp and P. A. Humblet, Information capacity
は γ = 12 dB，Condition2 は γ = 24 dB，Condition3 はand power control in single-cell multiuser communiγ = 7 dB である．Condition1，Condition2，Condition3
cations, Proc. IEEE ICC, vol. 1, pp. 331-335, 1995.
を比較すると最小サービスレートはあまり変化がないが[2] D. Wu and R. Negi, Utilizing multiuser diversity
事が分かる．反対に，平均サービスレートは Condition1
for eﬃcient support of quality of service over a fadingが約 430 kbps，Condition2 が約 1070 kbps，Condition3
channel, IEEE Trans. Veh. Technol., vol. 54, pp.
が約 220 kbps と大きく変化が現れた．つまり，1FF ス
1198-1206 , 2005.
ケジューリングの実効サービス帯域関数は平均 SNR 値によって最小サービスレートは影響を受けにくく，平均 [3] F. Ishizaki and G. U. Hwang, Queuing delay analysis for packet schedulers with/without multiuser diサービスレートは影響を受けやすい事が分かる．
versity over a fading channel, IEEE Trans. Veh.
次に，遅延のテイル分布の解析結果の図 2 を見る．図 2 のTechnol.,vol. 56, pp. 3220-3227, 2007.
実効サービス帯域関数のパラメータは Condition1 を使用し，実効到着帯域関数のパラメータは Condition1 が α =0.500，β = 0.980，λ = 0.300 の場合であり，Condition2が α = 0.100，β = 0.999，λ = 0.200 の場合である．図 2から，数値結果を比較すると各パラメータで小さな誤差はあるが、傾きが近似している事が分かる．つまり，提案した解析手法によりパケットの待ち行列遅延のテイル分布を推定できる事が分かる．

5おわりに

本研究では 1FF スケジューリング下での無線パケットネットワークのパケットの待ち行列遅延の解析を行なっ[4] Q. Liu, S. Zhon, and G. B. Giannakis, Queuingwith adaptive modulation and coding over wirelesslinks: Cross-layer analysis and design, IEEE Tran.
Commum., vol. 50, pp. 484-494, 2005.
[5] F. Ishizaki and G. U. Hwang, Cross-layer design
and analysis of wireless networks using the eﬀective
bandwidth function, IEEE Trans. Wireless Commun., vol. 6, pp. 3214-3219, 2007.
[6] C. -S. Chang, Performance Guarantees in Communication Networks. New York:Spring-Verlag, 2000.