平成 26 年度創成シミュレーション工学専攻修士論文梗概集
計算応用科学分野
相関性トラヒックをもつ S-ALOHA システムの性能解析
学籍番号 25413551 氏名 長尾 洋輔
指導教員名
1 はじめに
馮 偉
って変化するトラヒックである。具体的には、𝑐(𝑡)
無線通信ネットワークにおいて、限られた周波数
を到着トラヒックの状態過程とし、𝑐(𝑡) = 𝑖の時、デ
資源（チャンネル）を効率よく利用しできるだけ多
ータパケットの到着は到着率𝜆𝑖 のポアソン過程に従
数のユーザーが利用できるアクセス方式が展開され
てきた。その一つとして、スロット付きALOHA(S-
うとしている。到着トラヒックの状態は推移確率行
列𝑸 = {𝑞𝑖,𝑖′ }0≤𝑖,𝑖 ′≤𝑁−1 に従い推移する。また、到着トラ
ALOHA)方式と呼ばれる多重ランダムアクセス方式が
ヒックの状態の定常分布をβ = (𝛽1 , ⋯ , 𝛽2 )とする。
用いられている。
3 有限バッファモデルの解析
S-ALOHA方式の性能解析はこれまでに広く行われ
端末のバッファサイズが有限である有限バッファ
ている。従来の研究では、データパケットの到着が
モデルに対して解析を行う。バッファサイズはKと
独立で到着率が一定であるという仮定の下で解析が
する。時刻tにおける端末の状態過程を次のように定
行われている。しかし、実際の無線通信ネットワー
義する。
クでは、データパケットの到着は環境や時間によっ
𝑋(𝑡) = (𝑥(𝑡), 𝑠(𝑡), 𝑐(𝑡), 𝑏(𝑡))
て変化する相関性トラヒックである。そこで本研究
ここで、𝑥(𝑡)はバッファ内パケット数、𝑠(𝑡)はバッ
では、
相関性トラヒックをもつS-ALOHA無線通信シス
クオフステージ、𝑐(𝑡)は到着トラヒックの状態、𝑏(𝑡)
テムをバッファサイズの異なる2つのモデルで提案
はバックオフカウンタの値の状態過程を表している。
し、性能解析を行った。
確率過程𝑋(𝑡)の状態空間𝑆はすべて離散値であり、
2 S-ALOHA 無線通信システム
到着トラヒックの状態過程がマルコフ連鎖で到着は
本研究が取り扱う S-ALOHA 無線通信システムでは、
ポアソン過程に従うという仮定の下で、確率過程
1 つの基地局と M 個の端末が同時に通信を行う多重
𝑋(𝑡)は１つのマルコフ連鎖である。この 4 次元のマ
アクセス方式を想定している。１つの基地局が利用
ルコフ連鎖の推移確率行列𝑷は以下のようになる。
可能な周波数帯域は限られており、端末の通信が衝
突しないよう、その周波数帯域をチャンネルに分割
している。したがって本研究では P 個のチャンネル
をもつ S-ALOHA システムを考えている。同じ時刻に
同一スロットで 2 つ以上の端末が送信を行うと衝突
が起き送信は失敗してしまう。そのような衝突を回
端末の状態の定常分布を
避するアルゴリズムとして、一様バックオフを取り
𝜋0,𝑖 = lim 𝑃(𝑋(𝑡) = (0, 𝑖))
入れている。一様バックオフでは、各端末は送信を
𝜋𝑘,𝑗,𝑖,𝑢 = lim 𝑃(𝑋(𝑡) = (𝑘, 𝑗, 𝑖, 𝑢))
行う際に、バックオフカウンタと呼ばれるランダム
とすると、バッファサイズが有限であるため、定常
な整数値を[0,1, ⋯ U]から一様に選ぶ。バックオフカ
分布は常に存在する。マルコフ連鎖の性質𝝅 = 𝝅𝑷,
ウンタは1スロット毎に1ずつカウントダウンされ、
𝝅𝑒⃗ = 1より定常分布𝛑が求め、定常状態における
0 に到達すると送信を試みる。また、再送回数をバ
バッファ内の平均パケット数𝐸[𝐿]を求める。
ックオフステージと呼び、バックオフステージの最
大数を J-1 とする。
パケットの到着トラヒックは相関性トラヒックと
している。これはデータパケットの到着が時間によ
𝑡→∞
𝑡→∞
𝐾
𝐸[𝐿] = ∑ 𝑘𝜋𝑘
𝑘=0
平成 26 年度創成シミュレーション工学専攻修士論文梗概集
4 無限バッファモデルの解析
端末のバッファサイズが無限である無限バッフ
計算応用科学分野
の推移確率𝑞0,0 を変化させた𝐸[𝐿]を表している。
ァモデルに対して解析を行う。有限バッファモデル
𝑞0,0 = 0.65,0.75,0.85で比較を行った。𝑞0,0が大き
くなると𝐸[𝐿]の値は小さくなっている。これは、
と同様に端末の状態過程を時刻tにおける端末の状
𝑞0,0が大きくなるとパケットが到着しない状態が長
態過程を次のように定義する。
𝑋(𝑡) = (𝑥(𝑡), 𝑠(𝑡), 𝑐(𝑡), 𝑏(𝑡))
くなるため、バッファ内にパケットが溜まりにくく
なるためと考えられる。
有限バッファモデルと異なるのは、バッファ内パケ
ット数の取りうる値に上限がないことである。した
がって、推移確率行列𝑷は以下のように表される。
定常分布を有限バッファモデルと同様に定義すると、
定常分布𝛑が存在する必要十分条件は以下となる。
𝜖 < 1⁄𝐸[𝐷]
𝜖は平均到着率であり𝜖 =
図 1：バッファ内平均パケット数
∑𝑁−1
𝑖=0 𝜆𝑖 𝛽𝑖 で表される。ま
た𝐸[𝐷]は平均遅延を表している。
6 まとめ
無限バッファモデルはスペクトル法を用いて解析
本研究では相関性トラヒックをもつS-ALOHAシス
を行う。パケット数に注目した定常確率ベクトルを
テムモデルを提案し、性能解析を行った。解析モデ
𝜋𝑘 = (𝜋𝑘,0,0,0 , 𝜋𝑘,0,0,1 , ⋯ , 𝜋𝐾,𝐽−1,𝑁−1,𝑈−1 ) 𝑘 ≥ 0
ルが4次元のマルコフ連鎖となったことで状態数が
∞
𝑘
𝑘
とし、𝜋(𝑧) = ∑∞
𝑘=0 𝑧 𝜋𝑘 , 𝐴(𝑧) = 𝐶0 + ∑𝑘=1 𝑧 𝐴𝑘 ,
非常に大きくなり、計算量を用句精するために推移
𝑘
𝐵(𝑧) = 𝐶2 + ∑∞
𝑘=1 𝑧 𝐵𝑘 と定義すると、マルコフ連鎖
確率行列𝑷のサイズを制限した計算しか行えなかっ
の性質𝝅 = 𝝅𝑷から以下の方程式が得られる。
た。
特に到着トラヒックの状態数は2つとして数値計
𝜋(𝑧)
算を行ったが、実際の到着トラヒックは多数の事象
[𝜋0 [𝑧𝐴(𝑧) − 𝐵(𝑧)] + 𝜋1 𝑧(𝐶1 − 𝐶2 )]𝑎𝑑𝑗[𝑧𝐼 − 𝐵(𝑧)]
𝑑𝑒𝑡 [𝑧𝐼 − 𝐵(𝑧)]
に依存するため、到着トラヒックの状態数を増加さ
分母det[𝑧𝐼 − 𝐵(𝑧)]の零点から𝜋0 , 𝜋1 を求め、𝜋(𝑧)
また、無限バッファモデルにおいてスペクトル法
を導出する。そこからすべての定常分布𝛑を求める
による解析法を提案した。しかし、det[𝑧𝐼 − 𝐵(𝑧)]の
ことができる。
零点の一部を仮定している。そのため、det[𝑧𝐼 −
5 数値計算結果と考察
𝐵(𝑧)]のすべての零点を確立させ、実際にスペクト
=
今回有限バッファモデルに関して数値計算を行
せたうえで計算結果を検証する必要がある。
ル法により数値解析を行う必要がある。
った。4次元のマルコフ連鎖でモデル化したところ
7 参考文献
状態数が膨大なものとなった。そこで、今回の数値
[1] Jun-Bae Seo , Victor C. M. Leung : “Queuing
計算では計算量の抑制のため、ネットワーク内の端
Performance of Multichannel S-ALOHA
末数M=100、バッファの容量K=10、バックオフステ
Systems With Correlated Arrivals”, IEEE Trans. Veh.
ージの最大数J=5、到着トラヒックの状態数N=2、バ
Technol., vol. 60, no. 9,pp.4575-4586, (2011)
ックオフウィンドウサイズU=20とした。相関性トラ
[2] Wei Feng“Spectral analisis of IEEE8022.11
ヒックに関しては、ON状態ではパケットが到着し、
queueing networks” Proceedings of Symposium on
OFF状態ではパケットが到着しない、ON-OFF2状態の
Stochastic Models 2014,pp.267-276,(2014)
到着トラヒックとした。図1はOFF状態からOFF状態
© Copyright 2024 ExpyDoc
