到着間隔とサービス時間との間に相関のある待ち行列の研究
2009SE115 川西 健太

2009SE200 中島 智槻 2009SE226 岡本 直樹
指導教員： 石崎 文雄
それらの結果を比較する．

1

はじめに
2

近年，インターネットの普及に代表されるように通信ネットワークは大きな変化を遂げた．通信ネットワークのブロードバンド化に伴いネットワーク内のトラフィック量は 1990年代後半より指数関数的に増大している．また，通信ネッ
トワークのマルチメディア化によりネットワークの利用形態も多様化し，電話網の時代に比べて，トラフィックは統計的に複雑な挙動を示すようになった[1]．それにより，通信システムの設計や待ち行列理論において到着間隔とサービス時間との間に相関をもつ到着過程のモデル化といった課題が発生してきた．
待ち行列モデルは通信ネットワークの混雑現象を解析するためのモデルとして使われることが多い[1]．また，通常の待ち行列システムでは客の到着間隔とサービス時間は独立であることを仮定している．しかし，通信システムを待ち行列モデルでモデル化した際に，到着間隔とサービス時間との間に相関を持つような待ち行列モデルとしてモデル化することが適当である場合がある．例として，トークン方式のようなメディアアクセスの制御が行われている場合，トークンが回ってくる間の時間が長ければ，それだけ仕事が溜まっていることになる．その場合，到着間隔が長い(=トークンの回ってくる時間)と，そのサービス時間は長くなる．このような場合は正の相関が発生する．トークン方式は FDDI や Token Ring などの LAN 規格に使用されている．本研究では，このような到着間隔とサービス時間との間に相関があるような待ち行列モデルを考え，相関の強さがシステムの性能，特に待ち行列長のテイル分布と客の待ち時間のテイル分布に与える影響をシミュレーションによって調査する．負の相関は実際のネットワークの中では使用されないので，本研究では正の相関についてのみ考える．
参考文献[2]，[3]，[4]において，客の到着間隔とサービス時間との間に相関を持った待ち行列システムの解析が行われている．これらの研究においては，ゲートを持った待ち行列システムを考えている．これらの待ち行列シス
テムにおいては，ゲートの開く間隔がある分布に従って開くゲートがあり，ゲートが開いた時にゲートの外の待ち行列の客は全てゲートの中の待ち行列に移動する．ゲー
トの中に移動させる客の集団を一人の客として見ることにより解析を行い，客の待ち時間の分布等について議論している．本研究では，このようなゲートを持った待ち行列システムではなく，客の到着間隔の実現値によって，その客の平均サービス時間のパラメータが変わるような待ち行列システムを考える．このことにより，客の到着間隔とサービス時間との間に相関が生じることになる．本研究では，このような待ち行列システムの性能をシミュレーションによって調査する．到着間隔とサービス時間との間に相関のない待ち行列システムについてもシミュレーションを行い，モデルの説明
本研究では一つの窓口に対して，ポアソン過程に従って客が到着し，サービスを受けてその後退出するという待ち行列モデルを考えている．これは一般に客の到着は独立した事象であり，ポアソン過程に従う到着はランダムに客が到着するからである．また同時に複数の到着は起きないものとし，待時型非損失系モデルを使用する．到着がポアソン過程に従うので，その間隔は指数分布関数となる．従って指数分布に従う乱数を発生させ，到着間隔を求め，到着時刻を計算する．サービス時間についても同様に，指数分布関数を用いてサービス終了時刻を計算し，シミュレーションを行う．
平均到着率を λ，平均サービス処理率を μ とする．n 番目に到着した客とその客の前に到着した客との間の到着間隔を とし，n 番目に到着した客の到着時刻を とす
るとは(1)式で表すことができる．
(1)
ここで，は平均の指数分布に従う．

は待ち行列に加わってからサービスを受けるまでの待ち時間を求める計算にも使われており， を n 番目に到着した客の待ち時間とし， を n 番目に到着した客のサービス終了時刻とすると は式(2)になる．
(2)
これはある客が到着するよりも前に，その客の前に到着した客のサービスが終了していれば待ち時間は 0 になるということである．また，n 番目に到着した客のサービス時間
を とすると は(3)と表される．ここで， は相関のあるモデルの 1 人目の場
合と相関のないモデルの場合では平均の指数分布に従い，相関のあるモデルの 2 人目以降の場合は平均の指数分布に従う． は n 番目に到着した客の場合での正の相関を持たせるために平均サービス時間を計算したものである． は(4)式で定義され，到着間隔とサービス時間との間に正の相関を持たせている．
１(4)ここで，α は相関係数を決めるためのパラメータである．
α は 0 以上 1 以下の実数であり，α が 1 に近づくほど相関は強くなる．従って，α=1 の時に相関は最も強くなり，α＝0 の時に相関は全くなくなる．

3

また，を待ち行列長が n 以上となる確率，を待ち行列長が n の時間とすると次の式が成り立つ．
(n が最大の時)

シミュレーションについて

本研究のシミュレーションは，窓口で並ぶ客が作る待ち行列の長さやその待ち時間を知るためのシミュレーションである．またすべてのイベントがそれ以前のイベントによって予定できる．この場合，イベントドリブン方式は高速なシミュレーションを実行するための有効な手法となるので，イベントドリブン方式を使用する[5]．
本研究のシミュレーションではシミュレーション終了時刻を T(=1000000)秒とし，そのシミュレーション 10000 回分のデータを取り，それを k(=10)回繰り返す．精度の良い結果を得るためには多くの試行回数が必要となるが，一度に多量のデータを取ると膨大な時間がかかり，多くの試行を行うことは困難である．従って本研究では 100000回を 10 回に分けてシミュレーションを行った．
本研究のシミュレーションでは，プログラムには GSL[6]の指数乱数を使用した．また，シミュレーションにはモンテカルロ法を使用する．ここでは到着時刻やサービス終了時刻の計算方法について説明する．
基本的には到着イベントの場合は次の到着時刻を予定し，サービス終了イベントの場合は次のサービス終了時刻を予定する．しかし例外として，到着イベントの場合でサービスを受けている客も含めてこの待ち行列モデルのシステム内に客がいない時はその客のサービス終了イベントを予定し，サービス終了イベントの場合で待ち行列に客がいない時は何も予定しない．これらの計算は GSLの指数乱数を用いて計算する．この予定されるイベントの発生時刻を とすると は(5)式で与えられる．
(5)
ここで， は現在の時刻であり，r は乱数発生器である．また，Y はイベントが到着イベントの場合はであり，サービス終了イベントの場合では相関のあるモデルの 1 人目と相関のないモデルではとなり，相関のあるモデルの2 人目以降は となる．
は平均到着間隔，は平均サービス時間である．
また，本研究では待ち行列長と待ち時間のテイル分布を推定し，その結果を比較する．ここからは待ち行列長と待ち時間のテイル分布を推定するために用いた数式を示していく．
を待ち時間が m 以上となる確率，を 1 回のシミュレーションでサービスが終了した人数，を待ち時間の最大値， を待ち時間が m 以上 m+1 未満の客の人数とすると(6)式が成り立つ．
(6)(n が最大ではない時)

(7)
(8)

ここで，T はシミュレーションの終了時刻である．
また，本研究ではシミュレーションの精度を確かめるた
めに との分散と 95%信頼区間を求める．分散と95%信頼区間を求めるために用いた値は との10000 回のシミュレーションの平均 k(=10)個である．また推定したテイル分布の値は，待ち行列長のテイル分布の場合， の 100000 回のシミュレーションの平均を使用し，待ち時間のテイル分布の場合，の 100000 回のシミュレーションの平均を使用している．

4

シミュレーション結果
本節では，到着間隔とサービス時間との間に相関のある待ち行列と相関のない待ち行列の待ち行列長と待ち時間のテイル分布をモンテカルロ・シミュレーションで推定した結果を提示する．
まず，シミュレーションの精度を確かめるため，相関のない M/M/1 待ち行列モデルの待ち行列長のテイル分布と待ち時間のテイル分布を計算によって求め，シミュレーションによるものと比較した．その結果， α=0 の時のシミュレーションの待ち行列長のテイル分布と待ち時間のテイル分布は λ と μ の値がどの値の場合でも計算によって求めた相関のないものとほぼ一致した． このことから，このシミュレーションによるデータは少なくとも相関のないものについては正確であることが分かる．
図 1，図 2，図 3 は，モンテカルロ・シミュレーションによって推定した待ち行列長のテイル分布を示している．x 軸は待ち行列長を表し，y 軸は待ち行列長が x 以上となる確率を表す．また，y 軸は対数軸になっている．図 4，図 5，
図 6 は，モンテカルロ・シミュレーションによって推定した待ち時間のテイル分布を示している．x 軸は待ち時間を表し，y 軸は待ち時間が x 以上となる確率を表す．また，y軸は対数軸になっている．待ち行列長と待ち時間が長くなる確率が低くなることをシステムの効率が良いこととする．
また，相関の強さが最も強い時から全くない時まで 5 段階に分け，それを α の値を変えることで相関の強いほうから順番にそれぞれ 1，0.75，0.5，0.25,0 に対応させている．

図 1 待ち行列長のテイル分布(λ，μ)=(0.25，1)

図 5 待ち時間のテイル分布(λ，μ)=(0.5，1)

図 2 待ち行列長のテイル分布(λ，μ)=(0.5，1)

図 6 待ち時間のテイル分布(λ，μ)=(0.75，1)
待ち行列長のテイル分布と待ち時間のテイル分布は双方とも，全体的に見れば α=0.25 の時に最も待ち行列長と待ち時間が長くなる確率が低くなり，システムの効率が良くなった．しかし，(λ，μ)=(0.25，1)である図 1，図 4 だ
けは α=0 の時の方がシステムの効率が良かった．また，λの値が大きくなるにつれて，α=0.25 のものと α=0.5 のものとの差が小さくなっている．このことから，待ち行列長と待ち時間のテイル分布から同じようなことが言える．
また，それぞれのシミュレーションでの到着間隔とサービス時間の間の相関係数を推定した．シミュレーションに

図 3 待ち行列長のテイル分布(λ，μ)=(0.75，1)より推定された相関係数を表 1 に示す．相関係数の理論値を求める事は大変難しいので，ここではシミュレーションの結果のみを示す．
表 1 シミュレーションでの相関係数(λ，μ)α=0α=0.25α=0.5
α=0.75α=1(0.25，1)
0.000024
0.235723
0.408260
0.514507
0.577359(0.5，1)0.000003
0.235711
0.408252
0.514493
0.577357(0.75，1)0.000005
0.235705
0.408252
0.514508
0.577354

表 1 より α の値が同じ場合の相関係数は λ と μ に関係なく近い値になっていることが分かる．
図 4 待ち時間のテイル分布(λ，μ)=(0.25，1)

5

シミュレーションの評価と考察ない確率も高くなる．待ち行列に客がいない場合では，本研究ではシミュレーションの精度を確かめるため，シミュレーションによって求めた待ち行列長のテイル分布と待ち時間のテイル分布の分散と信頼区間を求めた．
分散は n と m の値をそれぞれ 3 つずつ決め， との標本分散を求めた．(λ，μ)=(0.75，1)，α=1，n=8の時にとなり の分散が最大になった．また，(λ，μ)=(0.25，1)，α=0，n=3 の時にとなり，の分散が最小になった．(λ，μ)=(0.75，1)，α=1，n=8 の時にとなりの分散が最大になった．また，(λ，μ)=(0.25，1)，α=0，n=3 の時にとなり，の分散が最小になった．
また，信頼区間も分散と同じように n と m の値をそれぞれ 3 つずつ決め， との 95%信頼区間を求めた．
例として(λ，μ)=(0.75，1)の α=0.25 のときの ， ， ，，，の信頼区間を表 2 に示す．

サービス時間が短くなったとしても次からの客には影響がない．以上のことよりサービス時間が短くなる場合よりも，サービス時間が長くなる場合の方が次からの客に大きな影響を与える可能性が高くなることが分かる．
α の値が大きくなり，相関が強くなるほどこれらの影響が大きくなる．また，λ と μ の比の λ の割合が低くなるほど，待ち行列に客がいない確率が高くなるので，サービス時間が短くなる場合の影響を受けにくい．よって，全体的に見れば λ と μ の比における λ の割合が低くなるほど，α の値が大きくなった時にシステムの効率が良くなる影響よりもシステムの効率が悪くなる影響の方が大きくなる．
以上のことから到着間隔とサービス時間との間に正の相関がある M/M/1 待ち行列を考えた場合，相関の強さがλ と μ の比にあった適切な強さであれば相関がない時よりもシステム効率が良くなるが，必要以上に相関が強すぎるとシステム効率がかえって悪くなることが確かめられる．

表 2 (λ，μ)=(0.75，1)の α=0.25 の時の信頼区間

6

信頼区間0.290890
0.149845
0.054366
0.327419
0.180968
0.052539

0.290914
0.149867
0.054383
0.327445
0.180993
0.125712

これらの結果を踏まえると， との値に比べ，その分散はとても小さく，95%信頼区間も広くないことが分かる．例として(λ，μ)=(0.75，1)，α=1 の時， =0.111820 であるのに対し，分散はであり， の値に比べ分散はとても小さい．また，(λ，μ)=(0.75，1)の α=0.25 の時，＝であるのに対して，その信頼区間は0.054366 より大きく 0.054383 未満であるので，おわりに本研究では，到着間隔とサービス時間の間に正の相関のある M/M/1 待ち行列モデルと相関のない M/M/1 待ち行列モデルの待ち行列長と待ち時間についてそれぞれシミュレーションを行い，それらの結果を比較し，考察した．その結果，到着間隔とサービス時間との間に正の相関がある M/M/1 待ち行列を考えた場合，相関の強さが平均到着人数と平均サービス人数の比にあった適切な強さであれば相関がない時よりもシステム効率が良くなるが，必要以上に相関が強すぎるとシステム効率がかえって悪くなるということが確かめられた．

参考文献の値に比べると信頼区間は広くない．λ，μ，α，n が他の値の場合でも同じように との値に比べてその分散はとても小さく，95%信頼区間も広くないと言える．このことより，本研究のシミュレーションによる推定値は精度が良かったと言える．
図 1～図 6 に示した結果が得られた理由として，次のことが考えられる．到着間隔が平均到着間隔よりも長い場
合はサービス時間が長くなる確率が高くなる．長くなった
場合は，その客の次からの客の到着間隔が短くても，その到着間隔が長かった客へのサービス時間は長いままである．したがって，その客へのサービスが長くなることに
よってその客以降の客の待ち時間が長くなり，待ち行列長も長くなる．
到着間隔が平均到着間隔よりも短い場合はサービス時間が短くなる確率が高くなる．しかし，サービスが終了するまでに次の客が到着せず，待ち行列に次の客がい[1] 電子情報通信学会知識ベース“知識の森”
http://www.ieice-hbkb.org/portal/(2012.9 )[2] Borst, S.C., Boxma, O.J. and Combé, .B.:Collectionof customers: a correlated M/G/1 queue. Perfor. Eval. Rev., vol.20 (1992) 47-59.
[3] Borst, S.C., Boxma, O.J. and Combé, M.B.: An
M/G/1 queue with custormer collection. StochasticModels, vol.9 (1993) 341-347.
[4] Ishizaki.F, Takine.T and Hasegawa.T, “Analysis of adiscrete-time queue with a gate,” Proceedings ofInternational Teletraffic Congress (1994) 169-178.
[5] Simulation の作り方
http://www.ysr.net.it-chiba.ac.jp/data/sim.pdf(2012.9 )[6] ＧＳＬのダウンロード先
http://www.gnu.org/software/gsl/(2012.8 )