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

提供: ORWiki
2007年7月8日 (日) 17:27時点における122.26.167.76 (トーク)による版
ナビゲーションに移動 検索に移動

【まちぎょうれつねっとわーくのせきけいしきかいとまるこふかてい (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のモデルを使う. 一般に待ち行列ネットワークをマルコフ連鎖で表すには, その推移率関数を次の要素に分けると見通しがよい.

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

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

　このネットワークで, ノード$j$にいるクラス$u$の客の退去推移率を $q_{ju}^{\mbox{\scriptsize \sc d}}$, その客が退去後ノード$k$へクラス$v$の客として到着する経路選択確率を $r_{ju, kv}$, ノード$k$での到着推移確率を $p_{kv}^{\mbox{\scriptsize \sc a}}$ とする. この場合のサービス完了から到着までを表す推移は, ノード$j, k$の状態が$\mbox{\boldmath $x$}_j, \mbox{\boldmath $x$}_k$ から $\mbox{\boldmath $x$}_j', \mbox{\boldmath $x$}_k'$ へ変わったとすると,

q_{ju}^{\mbox{\scriptsize \sc d}} (\mbox{\boldmath $x$}_j, \mbox{\boldmath $x$}_j') \, r_{ju, kv} \, p_{kv}^{\mbox{\scriptsize \sc a}} (\mbox{\boldmath $x$}_k, \mbox{\boldmath $x$}_k')

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


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


\begin{eqnarray*} 

&& \pi(\mbox{\boldmath $x$}) (\mbox{状態 {\boldmath $x$} で } (\ell, u)
\mbox{の客がノード$j$でサービスを完了する率}) \\
&& \qquad = \sum_{\mbox{\boldmath $x$}'} \pi(\mbox{\boldmath $x$}') (\mbox{状態 {\boldmath $x$}'
でサービスの完了または到着があり, }\\
&& \hspace{20ex} (\ell, u) \mbox{の客がノード$j$に到着し状態が$\mbox{\boldmath $x$}$となる率})

\end{eqnarray*}


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

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


\begin{eqnarray*} 

&& \pi(\mbox{\boldmath $x$}) (\mbox{状態{\boldmath $x$}で}\mbox{\boldmath $u$} \mbox{が退去する率}) \\
&& \quad = \sum_{\mbox{\boldmath $x$}', \mbox{\boldmath $v$}} \pi(\mbox{\boldmath $x$}')
(\mbox{状態{\boldmath $x$'}で\mbox{\boldmath $v$}が退去し, 
\mbox{\boldmath $u$}が到着し状態が$\mbox{\boldmath $x$}$となる率})

\end{eqnarray*}


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


\begin{eqnarray*} 

\frac {\Psi(\mbox{\boldmath $x$}-\mbox{\boldmath $u$})}{\Phi(\mbox{\boldmath $x$})} \nu(\mbox{\boldmath $u$})

\end{eqnarray*}


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


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


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

\begin{eqnarray*} 

(\mbox{クラス$u$の退去が起こり状態が$\mbox{\boldmath $x$}_j$となる率}) = \beta_{ju}\, \pi_j(\mbox{\boldmath $x$}_j)

\end{eqnarray*}

となる定数$\beta_{ju}$が存在することに等しい. 逆に準可逆性を持つノードをネットワーク状態に独立な確率的経路選択で結合すると積形式ネットワークとなる. 準可逆性を使った積形式ネットワークの構成は負の客のあるネットワークに対しても有効である. しかし, 準可逆性は積形式を持つための必要十分条件ではない(客のみを持つネットワークでは必要十分条件となる [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.

「https://orsj-ml.org/orwiki/wiki/index.php?title=《積形式解ネットワークとなるための条件》&oldid=1962」から取得