A general algorithm to compute the steady-state solution of product-form cooperating Markov chains
A general algorithm to compute the steady-state solution of product-form cooperating Markov chains
复制标题
计算乘积形式协作马尔可夫链稳态解的通用算法
DOI：
10.1109/mascot.2009.5366744
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. R. Bulò
中科院分区：
文献类型：
--
作者：
A. Marin;S. R. Bulò
近年来，人们提出了一些关于随机模型积型解的新结果。其中，反向复合代理定理（RCAT）及其扩展在产品形式的协作随机模型的表征中起着关键作用。虽然这些结果已经被用来证明几个著名的定理（例如，Jackson排队网络和g -网络解）以及一些新的定理，但据我们所知，一个自动工具来推导一组随机过程之间的一般合作的乘积形式解（如果存在），还没有开发出来。在本文中，我们解决了由RCAT应用引起的非线性方程组的求解问题。我们提出了一个迭代算法，它是目前正在开发的软件工具的基础。我们举例说明了该算法，讨论了其收敛性和复杂性，并将其与先前为Jackson网络和g网络分析所定义的算法进行了比较。针对RCAT在产品形态中（任意）大量合作过程的解决方案进行了一些测试。
In the last few years several new results about product-form solutions of stochastic models have been formulated. In particular, the Reversed Compound Agent Theorem (RCAT) and its extensions play a pivotal role in the characterization of cooperating stochastic models in product-form. Although these results have been used to prove several well-known theorems (e.g., Jackson queueing network and G-network solutions) as well as novel ones, to the best of our knowledge, an automatic tool to derive the product-form solution (if present) of a generic cooperation among a set of stochastic processes, is not yet developed. In this paper we address the problem of solving the non-linear system of equations that arises from the application of RCAT. We present an iterative algorithm that is the base of a software tool currently under development. We illustrate the algorithm, discuss the convergence and the complexity, compare it with previous algorithms defined for the analysis of the Jackson networks and the G-networks. Several tests have been conducted involving the solutions of a (arbitrary) large number of cooperating processes in product-form by RCAT.