待ち行列：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]