《積形式解ネットワークとなるための条件》

提供: ORWiki
2007年8月7日 (火) 16:18時点におけるKuwashima (トーク | 投稿記録)による版
ナビゲーションに移動 検索に移動

【せきけいしきねっとわーくとなるためのじょうけん (product form solution of queueing network and Markov process) 】

 待ち行列ネットワークの特性を調べる上で, 定常分布を求めることは重要であるが一般には難しい. しかし, ジャクソンBCMPネットワークのように定常分布が解析的に得られる場合がある. 特に, これらのネットワークは積形式の定常分布を持つ. このようなネットワークを一般に積形式ネットワーク (product form network) と呼ぶ. この他, 集団移動型ネットワーク (batch movement network) などで, 特殊なサービス規律を適用すると定常分布が解析的に得られる場合がある. なぜこれらのネットワークでは定常分布が解析的に得られるのであろうか? 一般的なモデルを対象にその理由を説明する.


マルコフ過程による記述 ネットワークをマルコフ過程によりモデル化する. このマルコフ過程には次の2つのタイプがある.


1. 各ノードの客数を主な状態とし, サービス中の客のサービス経過時間などを補助変数とするマルコフ過程で, 代表的なものに一般化セミマルコフ過程 (generalized semi-Markov process, GSMPと略称化される) がある.

2. サービス時間と到着間隔の分布を指数分布と仮定したり, 1の補助変数の部分を相型分布などを使って離散化することにより, 離散的状態を持つマルコフ過程, すなわち, マルコフ連鎖としてモデル化する.

 1のモデルは2のモデルで十分に近似することができるので, 以下では2のモデルを使う. 一般に待ち行列ネットワークをマルコフ連鎖で表すには, その推移率関数を次の要素に分けると見通しがよい.

  • 内部推移率:ノードの内部的な変化 (サービスの進行など) を表す部分
  • 退去推移率:退去とそのときの状態変化を表す部分
  • 到着推移確率:到着による状態変化を条件付き確率で表す部分

 例えば, 個のノードを持つ開放型ネットワークで, 複数のクラスの客があり, 各客はサービス完了後のクラスとノードにのみに依存した確率で次のノードとクラスを選択するとする. なお, 各ノードには, と番号のついたサービス位置があり, 人の客がいるときには, のサービス位置を占める. ノードでの各サービス位置の客のクラスとサービスの経過状態からなるベクトルをとすれば, ネットワークの状態は と表すことができる. このネットワークはジャクソンや BCMPネットワークを一般化したモデルである.

 このネットワークで, ノードにいるクラスの客の退去推移率を , その客が退去後ノードへクラスの客として到着する経路選択確率を , ノードでの到着推移確率を とする. この場合のサービス完了から到着までを表す推移は, ノードの状態が から へ変わったとすると,



である. なお, 開放型の場合は, 外部をノードとみなし, ネットワーク状態に取り入れる. ただし, 外部からの到着がポアソン過程に従うならば, ノードからの退去率は各に対して定数であり, ノードの状態をネットワーク状態に取り入れる必要はない. ネットワーク全体の推移率は, このような退去・到着による推移率と内部推移率の総和である([6]参照).


局所平衡 BCMPやケリーネットワークの特徴は, この推移率の定常分布が次の局所平衡方程式 (local balance equation)を満たすことにある [4]. サービスを受ける位置に番号をつけ, 位置にいるクラスの客をとするとき,


状態 の客がノード でサービスを完了する率

状態 でサービスの完了または到着があり,
の客がノード に到着し状態が となる率


逆に, サービス時間分布が一般の場合にこの方程式が成り立つならば, サービス規律は対称型 である [1]. さらに, 内部推移についても同様な局所平衡方程式が成り立ち, すべての局所平衡方程式を加えると大域平衡方程式 (global balance equation)が得られる. これより, が局所平衡方程式を満たせば, 定常分布であることが確認できる. この局所平衡方程式は, 客の残りサービス時間や経過サービス時間が客の配置と独立であることと同値である. 積形式に加えこの独立性が成り立つとき2重積形式 (double product form)を持つという.

 局所平衡方程式は, 複数のノードで同時に退去や到着が起こる集団移動型のモデルの解析においても役立つ. このネットワークの状態は各ノードの客数を要素とするベクトルであり, 集団をベクトルで表すとき, の退去がネットワーク状態に依存した率で起こる. この集団が集団となって到着する確率をとする. このモデルで, 局所平衡方程式


状態 が退去する率

状態 が退去し, が到着し状態が となる率


が, 任意の状態とすべて集団について成り立つならば. 定常分布を求めることができる [1]. 例えば, 推移行列{}が定常分布を持ち, 任意に与えた正値関数と非負値関数に対して, 状態でのの退去率が



であるならば, 局所平衡方程式が成り立ち, 定常確率に比例する [3]. このネットワークはWalrand [5] の離散時間同期型ネットワークや回線交換網などを特別な場合として含む. この種のネットワークは, 転送確率がネットワークの状態に依存する場合にも拡張されている [1].


逆時間過程 局所平衡方程式は一般の積形式ネットワークでは必ずしも成立しない. 例えば, 到着により客が減る負の客 (negative customer) [2] や負の客が瞬間的に複数のノードを通過するネットワークも積形式解を持つが局所平衡は成立しない [1]. この種のネットワークの解析には, 時間を逆転した確率過程すなわち逆過程 (reversed process)が有効である. 一般に定常なマルコフ連鎖の逆過程もまた定常なマルコフ連鎖となることから, 逆過程の推移率を推測できれば, 定常分布が求められる([6] 参照).


準可逆性 多くの積形式ネットワークでは, 各ノードを切り離し客をポアソン到着させると退去もまたポアソン過程となる. これを準可逆性 (quasi-reversibility)と呼ぶ. ノードの準可逆性は, 切り離してポアソン入力した場合の定常分布をとすれば, 各クラスに対して,


クラス の退去が起こり状態が となる率


となる定数が存在することに等しい. 逆に準可逆性を持つノードをネットワーク状態に独立な確率的経路選択で結合すると積形式ネットワークとなる. 準可逆性を使った積形式ネットワークの構成は負の客のあるネットワークに対しても有効である. しかし, 準可逆性は積形式を持つための必要十分条件ではない(客のみを持つネットワークでは必要十分条件となる [1]). なお, 準可逆性を持つネットワークを定常分布が得られるように退去率や到着確率をネットワーク全体の状態に依存する形に拡張する方法も工夫されている[1]



参考文献

[1] X. Chao, M. Miyazawa and M. Pinedo, Queueing Networks, Customers, Signals and Product form, John Wiley & Sons, 1999.

[2] E. Gelenbe, "Product-form Queueing Networks with Negative and Positive Customers" Journal of Applied Probability, 28 (1991), 656-663.

[3] W. Henderson and P. G. Taylor, "Product Form in Networks of Queues with Batch Arrivals and Batch Services," Queueing Systems, 6 (1990), 71-88.

[4] F. P. Kelly, Reversibility and Stochastic Networks, John Wiley & Sons, 1979.

[5] J. Walrand, "A Discrete-time Queueing Network," Journal of Applied Probability, 20 (1983), 903-909.

[6] 宮沢政清, 「待ち行列ネットワークと積形式解」, 『オペレーションズ・リサーチ』, 43 (1998), 442-448.