Uncovering the topology of an infinite-server queueing network from population data

技术摘要：从群体数据中揭示无限服务队列网络的拓扑结构

问题陈述
本文研究了由 $n$ 个无限服务队列（$M/G/\infty$）组成的网络中的统计推断问题。在标准的运筹学操作中，模型参数通常被假定为已知，以便评估性能指标。然而在实践中，这些参数必须通过数据进行推断。本文解决的具体挑战是一个“逆问题”：即仅基于对网络状态的间接、周期性观测，来估计系统的底层外生参数。

该系统具有以下特征：

1. 外部到达： 速率为 $\boldsymbol{\lambda}$ 的泊松过程。
2. 服务时间： 每个站点的独立同分布（IID）非负随机变量 $G_i$，且具有有限均值。
3. 路由： 路由矩阵 $Q$，其中 $q_{ij}$ 表示客户在服务完成后从站点 $i$ 移动到站点 $j$ 的概率。
4. 观测： 网络人口向量 $\mathbf{M}(t)$ 在由速率 $\beta$ 生成的随机时间点被观测。本文还考虑了“有噪声”的观测情况，即只有一定比例的客户被检测到，且检测概率 $\mathbf{p}$ 未知。

主要目标是利用观测到的队列长度来估计路由矩阵 $Q$、外部到达率 $\boldsymbol{\lambda}$，以及可能存在的服务时间分布参数（或分布本身）。次要目标是恢复网络的有向结构，即区分具有相同平稳分布的不同拓扑结构。

方法论
作者提出了一种矩估计量（method-of-moments estimator）。该方法依赖于推导在泊松时间点观测到的网络人口向量的显式解析表达式。

1. 矩的推导：

   • 文中建立，在泊松时间点观测到的人口向量的平稳分布具有独立的泊同分布边缘。
   • 该方法的核心在于计算两个不同观测时刻之间的互矩（cross-moments）。具体而言，作者推导了 $E[\mathbf{M}(0)\mathbf{M}(T_\beta)^\top]$ 的表达式，其中 $T_\beta$ 是一个服从指数分布的观测间隔时间。
   • 为了处理具有更多未知参数的情况（例如未知的服务时间参数或观测概率），该方法扩展到了 Erlang-2 观测间隔时间（$E_{\beta,2}$），对应于第 $k$ 个和第 $k+2$ 个泊松时刻之间的观测。这在不需要新的数据收集机制的情况下提供了额外的矩方程。
   • 推导过程中利用了服务时间分布及其剩余服务时间（超额寿命）的拉普拉斯-斯蒂尔杰斯变换（Laplace-Stieltjes transforms），以考虑到初始观测时刻存在的客户。

2. 估计量构建：

   • 估计量通过求解一个矩方程组来定义，在该方程组中，理论矩（作为 $\boldsymbol{\lambda}$、$Q$ 和服务参数的函数）与通过数据计算出的经验矩相等。
   • 在服务时间分布已知的案例中，由均值和滞后-1 互矩组成的 $n^2 + n$ 个矩方程与未知参数的数量（$n$ 个到达率和 $n^2$ 个路由条目）相匹配。
   • 对于未知的服务时间参数或观测概率，系统通过增加滞后-2 互矩来扩充，以确保方程数量与增加的未知数数量一致。
   • 由于矩方程的原始解可能会落在有效参数空间之外（例如负速率或行和 $>1$），作者采用了投影步骤以确保最终估计量位于可行集 $\Theta$ 内。

3. 无模型方法（Model-Free Approach）：

   • 作者提出了一个“无模型”变体，其中服务时间的参数形式是未知的。该方法不是估计分布参数，而是估计每个站点的第一个矩、在 $\beta$ 处的拉普拉斯-斯蒂尔杰斯变换以及在 $\beta$ 处的导数。这需要 $3n$ 个额外的参数，但避免了模型误设定问题。

主要贡献与结果

• 一致性： 本文证明了所提估计量的一致性。在温和的假设下（非平凡流且非爆炸系统），随着观测次数 $m \to \infty$，估计量几乎处处收敛于真实的参数值。其证明利用了与主控 $M/G/\infty$ 过程的耦合关系来建立经验矩的几乎处处收敛性。
• 可辨识性： 作者证明了矩向量（均值和互矩）与模型参数 $(\boldsymbol{\lambda}, Q)$ 之间存在一一映射关系。这确保了可以唯一地恢复网络拓扑（路由矩阵），即使在不同拓扑产生相同平稳分布的情况下也是如此。使用不同时间滞后的互矩打破了原本会导致无法区分流量方向的对称性。
• 处理噪声与未知量： 该框架被扩展到处理受限观测（未知的检测概率）和未知的服务时间分布，并表明通过增加使用的矩方程数量，该方法仍然适用。
• 数值性能： 广泛的数值实验验证了该方法。
  • 估计量能够准确恢复各种拓扑结构（线型、环型、对称环型、团）下的路由矩阵结构。
  • 该方法即使在参数较多和高维网络（$n=10$）的情况下也表现良好。
  • 无模型方法被证明对模型误设定具有鲁棒性；当假设的服务分布（如指数分布）与实际数据（如 Erlang-2）不符时，参数化方法会失效，而无模型方法在两种场景下均能获得准确的估计。

意义与主张
本文声称其主要贡献在于提供了一种能够估计所有模型参数的程序，包括路由矩阵、到达率、服务时间特性以及观测概率，且仅需利用泊松时间点的群体计数。

一个重要的理论主张是能够揭示网络的有向拓扑。作者指出，这种能力与因果性的概念相关联，因为该方法推断了节点间的流量方向（因果关系），而这在使用仅有的平稳分布数据时是无法实现的。

这项工作被定位为解决一类具有挑战性的运筹学逆问题，即在无法直接观测随机过程的情况下进行推断。作者谦虚地指出，虽然对于已知服务分布的情况，一致性证明是严谨的，但对于完全扩展的情况（未知服务参数和观测概率），其理论处理仍需进一步的辨识条件，目前仍作为一个开放领域留待未来研究，尽管其实际应用效果已得到验证。

最后，本文强调了该方法在社会网络分析（识别影响者和社群）和通信网络（从端点数据推断内部特征）等领域的实际应用价值，并提出了针对单服务队列和内生路由动力学的未来研究方向。