実効サービス帯域関数の推定法について
2006MI095 松田 倫幸
指導教員

1 はじめに研究の背景
現在，第 4 世代移動通信システム (Fourth-generation
Wireless systems 以下 4G) といわれる次世代移動通信ネットワークの開発が進んでいる．次世代無線通信ネットワークにおいては，通信サービス品質 (Qualityof Service:以下 QoS) 保証が不可欠になっている．また，QoS を大きく左右するのがベースステーション (以下BS) での遅延時間（あるいはキュー長）のテイル分布である．したがって，遅延時間あるいはキュー長のテイル分布を正確に見積もることが次世代無線通信ネットワー
クの QoS 保証を行う上で重要な鍵となっている．そのために，次世代無線通信ネットワークの性能評価に関する研究が盛んにおこなわれている．しかしながら，従来の解析手法で遅延時間のテイル分布の厳密解を求めることは難しい．その理由は，次世代無線通信ネットワー
クでは，各ユーザの無線チャネルの状態に応じたスケジューリングや符号化が行われるため，モデルを記述するための状態数が非常に多くなるためである．また，通常のモンテカルロシミュレーションによる遅延時間のテイル分布の推定も，膨大なシミュレーション時間がかかることや，レアイベントが発生する確率を見積もることが難しいといった理由から難しい．
従来の解析手法の困難さを解決するために実効帯域理論 [6] を用いることができるかもしれない．実効帯域理論とは 1990 年代に Asynchronous Transfer Mode ネッ
トワークの QoS 保証のために用いられた技術であり，現在では無線通信の性能評価をするために用いられている [1, 3]．しかしながら，複雑なスケジューリングや無線チャネルの状態変化といった理由から次世代移動通信ネットワークでは実効帯域理論を用いても遅延時間 (あるいはキュー長) のテイル分布を解析することは容易ではない．
実効帯域理論は有線ネットワークで広く研究されており，通信許可制御やリソース配分の基礎理論として知られている．近年では実効帯域理論は無線ネットワークの研究でも使用されるようになってきている [3]．この参考文献 [3] では，流体モデルのネットワークが想定されており，パケットごとのスケジューリングが行われるモデルではない．実際のネットワークでは，パケットごとのスケジューリングが行われるため，スケジューリングの性能を評価するためのモデルとしては不十分である．また他の研究では，実効帯域理論を使用してチャネル状態を 2 状態に分類し，coarest version of theKnopp and Humblet(以下 CKH) スケジューリングとround-robin(以下 RR) スケジューリングの性能を比較

1.1

2006MI107 椴山 馨

石崎 文雄
した研究がされている [1]．この研究では，システム全体のスループットパフォーマンスとは対称的にユーザ個々のディレイパフォーマンスは，システムが厳しい環境にある．すなわち，到着レートが大きく到着過程がバース
ト的で負荷が大きいか平均 SNR が低い時に限り，CKHスケジューリングは RR スケジューリングより優れていることが報告されている．また，もし SNR が低いことによるエラーの発生確率が高くなる場合，許容量はCKH スケジューリングが RR スケジューリングより優れている範囲が狭くなることも示されている．しかし，この研究ではチャネル状態が 2 状態と少なく，実際のネットワークヘの応用は難しいと考えられる．
1.2 研究目的・方法
本研究は，無線チャネルの状態に応じたスケジューリングと符号化が用いられる無線通信ネットワークを想定し，そのネットワークの実効サービス帯域関数を推定するための手法を提案する．推定された実効サービス帯域関数を使用して，実効帯域理論に基づき性能評価を行えることを実証する．
本研究では，シミュレーションによりネットワークの実効サービス帯域関数を推定する．さらに，シミュレーションにより推定された実効サービス帯域関数と解析により得られた実効サービス帯域関数の比較をし，シミュレーションにより推定された実効サービス帯域関数の妥当性を確認する．本研究で考える無線通信ネットワー
クは，無線チャネルの状態によって変調符号化の方式を適切に変える Adaptive Modulation and Coding(以下AMC) を利用したネットワークである．AMC のモードの遷移は有限状態マルコフ連鎖によってモデル化する．
また，各ユーザの正規化された SNR(Singnal-to-NoiseRatio) 値により次にサービスされるユーザが決定される Quantized Proportional Fair(以下 QPF) スケジューリングが使用されていることを想定する．無線チャネルのモデルは Rayleigh fading channel モデルを使用する．
さらに，本研究で提案したシミュレーションによる実効サービス帯域関数の推定法の妥当性を確認するために，RR スケジューリングを組み込んだネットワークを想定し実効サービス帯域関数を推定する．また、簡単なスケジューリングを想定し解析とシミュレーションの両方から実効サービス帯域関数の推定をおこない，シミュレーションによる推定法の正確性を確認する．

2 実効帯域理論
この節では，後の節の参照のために，サービスされるパケットのサービス容量が時間的に変化するネットワー
クを想定した実効帯域理論から得られる結果を簡単に説明する．サービスされるパケットのサービス容量が時間的に変化するネットワークを想定した実効帯域理論の詳細な説明は，参考文献 [1],[2],[6] に記述されている．
始めに，サービス容量の時間的変化を表わすサービス過程 c(t) を考える．ここに，c(t) (t = 0, 1, . . .) は t 番
目のタイムスロットでサービス可能なパケット数を表わす確率変数である．累積サービス過程 C(t) を C(t) =Pt−1
n=0 c(n) と定義する．すなわち，C(t) (t = 0, 1, ....)
は時間 [0, t) にサービス可能なパケット数を表わす確率変数である．また，[0, t) の間に到着する累積パケット数を A(t) とすると，t 番目のタイムスロットに到着したパケット数 a(t) は a(t) = A(t) − A(t − 1) である．q(t) を
t 番目のタイムスロット開始直後のキュー長を表わすとする．このとき，キューのダイナミクスを表わすリンドレー方程式 (Lindley equation) は以下のように書ける．

q(t + 1) = (q(t) + a(t + 1) − c(t + 1))+= (q(t) + (a(t + 1) − c(t + 1)) − 0)+(1)3 システムモデル
3.1 Adaptive Modulation and Coding
AMC は無線リンクの状態（例:パスロス，他の送信機からの信号による干渉，受信機の感度）に応じて変調方式や符号化方式，及びその他の信号やプロトコルパラメータを調整する仕組みのことである．AMC のプロセスは動的なものであり，信号やプロトコルパラメータは，無線リンクの状態が変わるにつれて変化する．
本研究では，文献 [2] で示された AMC が使われているものと仮定する．AMC は 2ms 毎に状態が変化するものとし 8 段階のモードを持つとする．8 つのモードの SNR の閾値は表 1 の通りである．例えば，モード 1は SNR 値が [8.01273, 11.82217)dB であるときに使われ，その時のサービスレートは 1 に等しい．Rate は 1スロット当り送信できるパケット数を表している．
表 1 AMC モード 8 区分 (閾値)ここで，累積到着過程 A と累積サービス過程 C は以下の条件を満たすと仮定する．

モード{a(t), t ≥ 0} は定常である．
全ての実数 θ に対して，limt→∞ 1t log E[eθA(t) ] =ΛA (θ) が存在する．
(III) 全ての実数 θ に対して，ΛA (θ) は微分可能である．
(IV) {c(t), t ≥ 0} は定常である．
(V) 全ての実数 θ に対して，limt→∞ 1t log E[eθC(t) ] =ΛC (θ) が存在する．
(VI) 全ての実数 θ に対して，ΛC (θ) は微分可能である．
(VII) 累積到着過程 A と累積サービス過程 C が互いに01234567(I)
(II)

Rate
0123
4567x(SNR:dB)
0.0≤x<8.01273
8.01273≤x<11.82217
11.82217≤x<16.24006
16.24006≤x<18.84206
18.84206≤x<22.58435
22.58435≤x<24.9783824.97838≤x<28.57040
28.57040≤x

独立である．
スケジューリング
本研究ではパケットのスケジューリングは QPF スケジューリングを使用した無線通信ネットワークを想定する．QPF スケジューリングは各モバイルステーション(以下 MS) の SNR 値を正規化したものを量子化し，量子化された正規化 SNR 値が最も高い MS を選択しサービスをするスケジュールである [5]．
3.3 有限状態マルコフ連鎖モデル
本研究のシミュレーションにおいては，Rayleigh fading channel モデルを用いる．Rayleigh fading channel
は Nakagami-m channel モデルにおいて m = 1 と設定したときのモデルと同等である [4]．
本研究では，Rayleigh fading channel は SNR 値の時間的変化を算出するために用いている．しかし，このモデルのままではシミュレーションを行うことが困難であるため本研究では AMC のモードを使用した 8 状態の有限状態マルコフ連鎖モデルを使い，近似的なシミュレーションを行うことにする．
有限状態マルコフ連鎖モデルによってモデル化を行うにあたり，以下の条件を満たしていると仮定する．今回のシミュレーションでは遷移する時間間隔を 2ms とかなり短い時間としている．そのために，SNR 値が上位のモードまたは下位のモードを遷移するときに，2 つ以

3.2
このとき，実効到着帯域関数は

ξA (θ) =ΛA (θ)
θ

このとき，実効サービス帯域関数は

ξC (θ) = −ΛC (−θ)θ(2)で定義される．このとき，以下のことが知られている[6]．

ΛA (θ) + ΛC (−θ) = 0(3)の唯一の解 θ ∗ > 0 が存在するとき，キュー長 q(t) の分布は t → ∞ で収束し，以下の式を満たす．

lim

1x→∞ xlog P (q(∞) ≥ x) = −θ∗(4)

ξA (θ) = ξC (θ)(5)

ここで，式 (3) はと書き直すことが出来ることにする．したがって，実効帯域理論によると，実効到着帯域関数と実効サービス帯域関数が定まれば，方程式 (4) を満たす解 θ ∗ > 0 を求めることにより，式 (3) からキュー長のテイル分布の漸近的振る舞いを知ることが出来ることになる．

上先のモードに遷移することがないとする．
以上の条件満たした, 上の状態に遷移する確率 (6), 下の状態に遷移する確率 (7), 遷移せず状態を維持する確率(8) を以下に示す。

Pn,n+1 =Nn+1 Tf,
Pr (n)

Pn,n−1 =(Pn,n =N n Tf,Pr (n)n = 0, ..., N − 1(6)n = 1, ..., N(7)

QPF スケジューリング
この小節では QFP スケジューリングを組み込んだネットワークの設定推定した結果のグラフを示す．ネットワークの環境設定は表 2 の通りである．

5.1

表2

シミュレーション環境

ネットワークの設定

1 − Pn,n+1 − P n, n − 1,1 − P0,1 ,1 − Pn ,n=0<n<Nn=0n=N(8)MS 数
各 MS の平均 SNR 値

10 個
15dB
10Hz
2ms

ドップラー拡散時間間隔

8 モード
10000 個チャネル状態
サンプル数

4 実効サービス帯域関数の推定−1h NX
iffC (−θ) = 1 log 1Λe−θCn (t)t
N n=0で，計算する．ここに θ の値の上下限はシミュレーションを行うことにより変化させ必要な範囲を決定する．

5 シミュレーション結果
本節では本研究で行ったシミュレーション結果を示す．

以上の設定によってシミュレーションを行い実効サービス帯域関数を推定した結果を図 1 に示す．図の縦軸は
ξC (θ) を，横軸は θ を表している (0.00001 ≤ θ ≤ 0.1)．
図 1 においてはタイムスロット t を t = 200 から t =3000 設定しシミュレーションを行っている．t = 200の結果では，値が発散することもなく，単調減少が表れている．また同様に t を増加させ t = 3000 として実効サービス帯域関数を推定した結果から、t = 3000 の場合でも実効サービス帯域関数の特性である単調減少が表れている．本研究で行ったシミュレーションによって実効サービス帯域関数を推定できている．
EBF of service processes(QPF)
0.7"qpf(t=200)""qpf(t=1000)""qpf(t=2000)""qpf(t=3000)"

0.6

0.5

Effective bandwidth

実効サービス帯域関数 ξC (θ) は単調減少関数である．
また，θ ↓ 0 のとき平均サービスレートととなり，θ → ∞のとき最小サービスレートとなる．実効サービス帯域関数 ξC (θ) は，サービス過程がマルコフ変調過程で記述され，その状態数が小さい場合は，行列の最大固有値を計算することで比較的容易に計算することができる．しかし，状態数が大きくなると行列の最大固有値を計算することが難しくなり，実効サービス帯域関数を計算することは難しい．本研究で考えているモデルは，サービス過程がマルコフ変調過程で記述されるが，その状態数は非常に大きくなる．例えば，AMC のモード数が8 で MS の数が 20 の場合，マルコフ変調過程の状態数は 820 = 1.15 × 1018 になる．したがって，本研究で考えているモデルでは，行列の最大固有値を計算することで実効サービス帯域関数 ξC (θ) を計算することは非常に困難である．そこで，本研究では実効サービス帯域関数 ξC (θ) を解析的手法ではなくシミュレーションにより推定する方法を提案する．そのために，ΛC (−θ) をシミュレーションにより推定する．ΛC (−θ) がシミュレーションにより推定されれば，式 (2) により実効サービス帯域関数 ξC (θ) が推定できる．したがって，以下では ΛC (−θ) をシミュレーションにより推定する方法を示す．
まず，シミュレーションにより，十分に大きな t にfn (t) (n =関する累積サービス過程 C(t) のサンプル C
0, . . . , N − 1) を N 個発生させる．このとき，ΛC (−θ)
fC (−θ) をの推定値 Λ

0.4

0.3

0.2

0.1

000.01

0.02

0.03

0.04

0.05

0.06

0.07

0.08

0.09

0.1

図 1 QPF(8 状態) シミュレーション結果

5.2 QPF スケジューリングと RR スケジューリングの比較
次に RR スケジューリングを組み込んだネットワー
クの設定と結果を示す．そして，RR スケジューリングと QPF スケジューリングの実行サービス帯域関数の性質の比較を行う．尚，QPF スケジューリングとの比較をするため，前節のネットワークの設定を採用した．また，QPF スケジューリング，RR スケジューリング共にの AMC を 2 状態にし再度シミュレーションを行った．平均 SNR 値の設定は 8，12，16，20dB に変更しシミュレーションを実行した．異なる二つスケジューリングの実効サービス帯域関数を比較したものを図 2 に示す．また，図 2 では平均 SNR 値が 12dB と 16dB のときのみ結果であり，Condition1 は 12dB，，Condition2

は 16dB となっている．
EBF of service processes(QPF,RR)
0.1"qpf(Condition1)""qpf(Condition2)""rr(Condition1)""rr(Condition2)"
0.095

Effective bandwidth

0.09

0.085

0.08

0.075

0.07
0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

図 2 QPF,RR(2 状態) シミューレション結果

解析とシミュレーションの比較
実効サービス帯域関数を推定するシミュレーションの正確性を確認するために，単純なスケジューリングを組込みシミュレーションと解析をともに行い，比較した
図 3 を以下に示す．この検証で組み込んだスケジューリ
ングは各タイムスロットで 0.2 の確率でサービスに成功し，0.8 の確率でサービスをしないものである．

5.3

EBF of service processes"Analysis""Simulation"

Effective bandwidth

0.195

0.190.185

0.180.175

図30.050.1

0.15

0.20.25

7 おわりに
本研究では実効サービス帯域関数の推定法の提案をし，研究成果から推定法の妥当性の確認ができた．また特定のネットワーク環境を組込み検証を行うことでより実用的な推定法になると考えられる．

参考文献

0.2

0

提案した手法ではスケジューリングに依存することなく実行サービス帯域関数を推定すること可能であると考えられる．さらに，シミュレーション結果の妥当性を確かめるために，単純なスケジューリングを組み込んだネットワークを想定し解析とシミュレーションの実効サービス帯域関数を推定することも行った．θ の値が小さい時は解析とほぼ同一のシミュレーション結果を得ることができた. また，θ の値が 0.3 より大きくなると徐々にシミュレーションの推定値に誤差が生じはじめることもわかった．θ の値が大きい領域ではより正確な手法の提案が必要となるかもしれない．しかしながら，θ の値の大きい領域は性能が十分に良い状態であるので，QoS 保証の観点からは θ の値の大きい領域での性能評価は重要ではない．したがって，本研究で提案した推定法の妥当性については確認できたと言える．

0.3

解析とシミュレーションの比較

6 研究成果
本研究は，無線チャネルの状態に応じたスケジューリングと符号化が用いられる無線通信ネットワークを想定し，そのネットワークの実効サービス帯域関数をシミュレーションにより推定するための手法を提案した．シ
ミュレーション結果から，シミュレーション時間の増加に伴って，推定された実行サービス帯域関数の単調減少が顕著に表れるようになった．つまり，シミュレーション時間の増加に伴って求めたい実際の実行サービス帯域関数に上から近付いていくと考えられる．したがって，シミュレーション時間はある程度長い時間が必要であること言える．今回の環境での実効サービス帯域関数を推定するためには，4000ms 程度までの累積サービス過程のサンプルを集めることが必要であることがわかった．
また，異なるいくつかのスケジューリングをネットワークの設定に組み込み，シミュレーションを行ったところ，各指定された実効サービス帯域関数はいずれも実効サービス帯域関数の特徴である単調減少を示した．つまり，[1] F. Ishizaki and G .U. Hwang, “Queuing delay analysis for packet schedulers with/without multiuser
diversity over a fading channel,” IEEE Transactions on Vehicular Technology, vol.56, no.5,
pp.3220–3227, 2007.
[2] F. Ishizaki and G. U. Hwang, “Cross-layer design and analysis of wireless networks using theeﬀective bandwidth function,” IEEE Transactions
on Wireless Communication, vol.6, no.9, pp.3214–3219, 2007.
[3] D. Wu, and R. Negi, “Utilizing multiuser diversity for eﬃcient support of quality of servir over afading channel,” IEEE Transactions on VehicularTechnology, vol.54, no.3, pp.1198–1206, 2005.
[4] Q. Lin and S. Zhou, “Queuing with adaptive
modulaton and coding over wireless links,” IEEE
Transactions on Vehicular Technology, vol.56,no.4, pp.1902–1907, 2007.
[5] F. Ishizaki and G. U. Hwang, “Throughput performance of quantized proportional fair scheduling with adaptive modulation and coding,”
Proc. of Wireless Telecommunication Symposium,
CDROM, 2009.
[6] C.-S. Chang, Performance guarantees in communicaton networks, New York:Springer-Verlag,
2000.
[7] 笹岡秀一，ウェーブサミット講座 移動通信，オーム社, pp.88-90.