平成 26 年度創成シミュレーション工学専攻修士論文梗概集計算応用科学分野スペクトル法を用いた IEEE802.16 無線通信システムの性能解析学籍番号 25413527 氏名熊谷優指導教員名 1 はじめに馮偉間はコンテンションスロットと呼ばれる固定時間単 IEEE802.16無線通信システムは見通し距離50km内位のスロットで構成される。帯域幅要求を送信したで最大通信速度70Mbpsを実現する広域高速の無線通い端末は、まずバックオフカウントと呼ばれるラン信規格である。現在ではIEEE802.16-2004規格に基づダムな整数値を選ぶ。 i回目の再送では0から𝑊𝑖 − 1 いたWiMAXというサービスが行われており、さらなるの範囲から選ばれる。𝑊𝑖 はバックオフウィンドウと高速通信を実現できるIEEE802.16ｍ規格に基づく呼ばれる値で、バックオフウィンドウの初期値𝑊0を WiMAX2というサービスへの移行が行われている。用いて𝑊𝑖 = 2𝑖 𝑊0 で表される。バックオフカウント IEEE802.16ネットワークに関する研究は、新たなは 1 スロット経過する毎に 1 つずつカウントダウン規格の策定と前後して広く行われている。しかし多され、0 に到達したスロットで端末は帯域幅要求をくのパラメータや状態推移が複雑に絡み合うシステ送信する。帯域幅要求を送信した端末は基地局からムのため、これらの研究の多くは近似的な計算によの帯域幅割り当てを待つ状態となる。利用できる帯る評価が一般的である。域幅があれば、基地局は端末に帯域幅を割り当てる。そこで、本研究では新たな解析手法としてスペク 𝑇𝑊 フレーム以内に割り当てが行われなければ、端末トル法をIEEE802.16無線通信システムに適用させるは帯域幅要求の再送のために再びバックオフを行う。ことで理論値を求めることを目的とした。スペクト 3 マルコフ連鎖によるモデル化ル法とは、無限に連なる個々の行列を成分ごとに分本研究では 1 基の基地局と n 台の端末から構成さけ、スペクトル領域において母関数を用いて表したれる IEEE802.16 無線通信システムについて考える。方程式による解法のことである。この手法は各々の上田[1]のモデルを基に、マーク端末の状態を 3 次パラメータから直接解を求められるため、システム元の離散時間マルコフ連鎖によってモデル化する。の確率過程の次元が大きい場合に特に有用である。時間推移はスロット単位で起こるものとする。離散しかし、母関数についての境界条件が複雑になる場時刻 t におけるマーク端末のバッファ内のパケット合が多く、その方程式は簡単には構成できない。そ数、再送回数、バックオフカウント値もしくは帯域こで本研究ではスペクトル法において非常に重要と幅割当要求送信後の経過スロット数を表す確率過程なるカーネル行列について計算し、求めるべき母関をそれぞれx(t), s(t), b(t)とする。離散時刻 t におけ数の存在を仮定ではなく具体的に証明することがでるマーク端末の状態はX(t) = (x(t), s(t), b(t))と書きた。き表せ、X(t)は 3 次元の離散時間マルコフ連鎖とな 2 IEEE802.16 無線通信システムの通信方式る。この時のマルコフ連鎖の推移確率行列𝑷を求め IEEE802.16 標準規格では PMP(一対多接続)方式が想定され、1 つの基地局がカバレッジ内の全端末の通信制御を行う。ネットワーク中の端末はすべて基地局から割り当てられた帯域幅を利用してデータ送ると次のようになる。 𝐶0 𝐴1 𝐶1 𝐵1 𝐶2 𝑷= 信を行うため、まず基地局に帯域幅の割り当てを要求しなければならない。 [ 𝐴2 𝐵2 𝐵1 𝐶2 𝐴3 𝐵3 𝐵2 𝐵1 𝐶2 ⋯ ⋯ ⋯ ⋯ ⋯ ⋱] 帯域幅要求の衝突を回避するため、各端末は帯域これは M/G/1 型マルコフ連鎖の推移確率行列となっ幅要求の送信前にバックオフを行う。バックオフはている。このとき、(i,j)成分の行列はバッファ内のコンテンション期間で行われる。コンテンション期パケット数が i からｊへ変化するときの推移確率で平成 26 年度創成シミュレーション工学専攻修士論文梗概集計算応用科学分野ある。次の方程式が成り立つ。 4 スペクトル法によるモデルの解析 𝐶2𝑉0 = 0 端末の定常状態分布を { ∑ 𝝅 = (𝝅𝟎 , 𝝅𝟏 , 𝝅𝟐 ⋯ ) 𝑘 1 1 𝐵𝑙 𝑉𝑘−𝑙 = 𝑉 (𝑘 (𝑘 − 𝑙)! − 1)! 𝑘−1 𝑙=0 特異点z = 0及びz = 1において、この係数行列と式 𝝅𝒌 = lim 𝑷(𝑥(𝑡) = 𝑘) 𝑡→∞ (2)を用いて𝝅𝟎 及び𝝅𝟏 についてのW個の方程式を得ることができた。したがってこれらのW + 1個の方 = (𝜋𝑘,0,0 , ⋯ , 𝜋𝑘,𝑚,𝑊𝑚 +𝑀−1 ) と定義したとき、推移確率行列𝑷との間に𝝅 = 𝝅𝑷と程式より𝝅𝟎 及び𝝅𝟏 を定めることで、𝝅(z)を導出すいう関係式が成り立つ。この式について各成分行列ることができる。また、定常状態分布𝝅𝒌 の定義から 1 𝑑𝑘 𝝅𝒌 = 𝝅(𝑧)| 𝑘! 𝑑𝑧𝑘 𝑧=0 をまとめると、次の式が得られる。 𝝅𝟎 = 𝝅𝟎 𝐶0 + 𝝅𝟏 𝐶1 𝑘 { 𝝅𝒌 = 𝝅𝟎 𝐴𝑘 + ∑ 𝝅𝒍 𝐵𝑘−𝑙 + 𝝅𝒌+𝟏 𝐶2 (1) ることができる。 𝑙=1 また、次のようにそれぞれの母関数を定義する。 ∞ A(z) = 𝐶0 + ∑ B(z) = 𝐶2 + ∑ ∞ 𝝅(z) = ∑ によって𝝅(z)を再変換することで、𝜋𝑘 をすべて求め 5 まとめ本研究ではIEEE802.16無線通信システムについて 𝑧 𝑘 𝐴𝑘 𝑘=1 スペクトル法を用いた性能解析を行った。従来の研 ∞ 究ではカーネル行列の存在は仮定されることが多い 𝑧 𝑘 𝐵𝑘 が、本論文ではその証明をすることができた。また、 𝑘=1 解析を行っていく中で必要な式や計算はとても煩雑 𝑧 𝑘 𝝅𝒌 𝑘=0 なものが多く、式の導出だけで多くの時間がかかっ式(1)についてこの変換を行うと以下のように書きてしまった。そのため様々なパラメータについてこ直すことができる。の解法による𝝅𝒌 の値を十分に数値シミュレーションすることはできなかった。一方で比較のために、 𝝅(z)(zI − B(z)) 近似的にマトリクス法を用いた性能解析は行った。 = 𝝅𝟎 (𝑧𝐴(𝑧) − 𝐵(𝑧)) + 𝑧𝝅𝟏 (𝐶1 − 𝐶2 ) 𝝅(z) = [𝝅𝟎 (𝑧𝐴(𝑧) − 𝐵(𝑧)) + 𝑧𝝅𝟏 (𝐶1 − 𝐶2 )]𝑎𝑑𝑗∆(z) 𝑑𝑒𝑡∆(z) しかしシステムの状態数が膨大であるため、マトリ (2) クス法では計算量を抑制したシミュレーションしかこのとき∆(z) = (zI − B(z))と置き、これをカーネ行うことができず、やはり十分なシステムパフォール行列とした。det∆(z)が存在する場合、𝝅𝟎 およびマンスの評価は結論付けられなかった。今後の課題 𝝅𝟏 から𝝅(z)を導出することができる。本論文ではことしては、高次の複数階微分を必要とする𝝅(z)の再の行列式を以下に示すように具体的に導出し、 2つの変換におけるアルゴリズムの導出が挙げられる。そ特異点が存在することを証明することができた。れによって、マトリクス法では扱うことのできない det(zI − B(z)) = ような高次元のパラメータも扱えるようになり、定 𝑧 z ∑𝑚 𝑖=0 𝑊𝑖 +(𝑚+1)(𝑀−1)−1 𝑝 𝑊𝑚 [𝑧 − 𝑧𝑃𝑚 𝑄 𝑀−3 (𝑄 2 +𝑄+ 1)∆∗𝑊𝑚 − 𝑊𝑚 −1 𝑛 ∏𝑗=1 𝑞𝑗𝑚 ) − (ℎ𝑚,𝑚 (𝑎) + 𝑎𝑚𝑐 (𝑧)(1 + ∑𝑛=1 量的なシステムパフォーマンスの評価が可能になると考えられる。 𝑊𝑚 −1 𝑛 ∏𝑗=1 𝑞𝑗𝑚 )] ℎ𝑚,𝑚 (𝑏) ∑𝑛=1 6 参考文献この式から、 z = 1はシンプルな特異点であり、 z=0 [1]上田晋大: “非飽和状態における IEEE802.16 無は多重特異点であることがわかる。また、𝝅𝟎 及び𝝅𝟏 線通信ネットワークの性能解析”平成 24 年修士論文を求めるためにはその未知数であるW + 1個の方程 [2] Wei Feng : “Spectral analysis of IEEE802.11 queueing 式が必要であり、一つは式(1)の上式である。 networks”, Proceedings of Symposium on Stochastic Models ここで、カーネル行列の余因子行列を求める。係 𝑘 数行列母関数V(z)を用いて、V(z) = ∑∞ 𝑘=0 𝑧 𝑉𝑘 = 2014, pp.267-276, (2014) adj∆(z)と置いたとき、k = 1,2, ⋯ , W − 2において