待ち行列：Jacksonネットワークの計算

待ち行列理論の中でJacksonネットワークの計算をしてみます。
(1)推移確率行列
ノードがN個あるネットワークを考える。推移確率行列は次の式になります。通常、行和が1になりますが、1にならない場合がそのノードから外部への退去と考えます。例えばi行の行和が0.7の場合、ノードiから外部への退去は0.3となります。

推移確率行列が上の場合、ノード2は行和が0.6のため、ノード2から外部への退去は0.4となります。

(2) トラフィック方程式
次にノードiへの到着率αを求めます。トラフィック方程式は次のようになります。
ベクトル表記

要素で表記

行列表記

これを式変形して計算しやすい形にします。

ベクトル表記

この線形方程式を解くことでαが得られます。ρは次の式で求められます。μはサービス率です。

 (3) 定常分布の算出
ノード i の人数を ni とすると、全ノードのそれぞれの人数のベクトル表現を n = (n1, n2, · · · , nN ) とする。 この時、定常分布は下記になる。ただし全てのノードで ρi < 1 となることが必要である。周辺分布は、それぞれのノードの定常分布となる

 (4) 平均系内人数
各ノードの平均系内人数は M/M/1 待ち行列モデルに従うので、それぞれの平均系内人数 Li は下記になる

(5) 数値計算
簡単な例で数値計算をしてみます。加藤、小沢、ORの基礎、実教出版、P153の例を使ってみます。

この場合の推移確率行列は、下記です。

外部からの到着率は

サービス率は

これからトラフィック方程式を解くと、αは

これからρは

平均系内人数は

ρが1に近くなると系内人数は発散します。

定常分布を求めます。今回はn = [6, 1, 2]と人数分布になる場合のそれぞれのノードの定常分布は、下記になります。

 n = [6, 1, 2]となる場合の結合分布は

となります。各ノードの定常分布のグラフは下記になります。

[ソースコード:Matlab]

	%パラメタ設定
	N = 3;
	P = [0 0 1; 0 0 0.6; 0.5 0 0]
	lambda = [2; 1; 0]
	mu = [5; 4; 6]
	%[p^t-E]α = -λ
	A = P.' - eye(N)
	alpha = linsolve(A, -lambda)
	rho = alpha ./ mu
	%平均系内人数
	L = rho ./ (1 - rho)
	fplot(@(x) x/(1-x), [0 0.97])
	%人数分布
	n = [6, 1, 2]
	%nとした場合の定常分布(周辺)を求める
	for i = 1:N
	i
	rho(i)
	n(i)
	pi(i) = (1-rho(i))*rho(i)^n(i);
	end
	pi
	%rho(i)を使い、人数を変化させた時の定常分布のグラフ
	figure
	hold on
	for i = 1:N
	fplot(@(x) (1-rho(i))*rho(i)^x, [0 30])
	end
	legend
	hold off
	%Jackson定常分布
	jpi = 1;
	for i = 1:N
	jpi = jpi * pi(i);
	end
	jpi

view raw Jackson hosted with ❤ by GitHub