英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
基于工作崩溃的MAP/M/1排队论性能系统分析
Qingqing Yea Liwei Liub
a.统计系, 数学与统计学院, 南京信息工程大学, 南京, 中国
b.统计与金融数学系, 理学院, 南京理工大学, 南京, 中国
摘要: 在本文中, 我们分析了工作崩溃下的MAP/M/1排队论系统. 利用矩阵几何解法得到了系统中处于平稳状态的客户数量, 提供了几个有用的性能度量. 此外, 我们还给出了一个递归公式, 得到了一个平稳停留时间的近似值, 最后列出几个数值例子.
关键词: 马尔科夫过程; 几何矩阵解法; 平稳时间; 系统规模; 工作崩溃
- 引言
在实际情况中, 由于“完全可靠的服务器几乎不存在”这一重要事实, 服务器损坏或故障是很常见的情况. 因此, 具有服务器故障的系统作为一个排队模型或可靠性模型在几十年来引起了广泛的关注, 并在局域网, 制造系统, 数据包通信系统等领域有着广泛的应用, 关于这一主题的早期研究可以追溯到 Thirurengadan (1963) 及其中的参考资料. Cao 和 Cheng(1982) 对服务器不可靠的M/G/1类型队列进行了拓展. 随后, Li, Shi 和 Zhao (1997) , Ke(2004), Ke (2005), Ke (2006), Ke, Lin, Yang 和 Zhang (2009), Dimitriou 和 Langaris (2010), Falin (2010), Li, Yang 和 Park (2011), Choudhury 和 Tadj (2011), Choudhury 和 Ke (2012), Dimitriou (2013) 等学者认为不可靠性的排队论系统具有各种特征. 在上述文章中, 他们都有一个基本的假设: 一旦服务器出现故障, 它将立即被送到修理厂进行维修, 当前的客户仍将留在系统中, 无需等待修复过程的完成. 然而, 许多复杂系统总是可以在多类型故障模式而不是在正常的两类型 (工作或故障) 模式下工作, 这样的部分故障系统允许故障服务器可以继续提供服务, 而不是完全停止服务. 具有这种部分故障服务器的队列的研究可以追溯到 Gnedenko 和 Kovalenko (1989), 作者在这一研究中,对具有不可靠性和“可再生”服务器的M/G/1类型队列进行了分析. 随后, Sridharan 和 Jyashree (1996) 考虑了具有双态故障模式 (部分故障和完全故障) 的有限容量排队系统; Baykal-gursoy 和 Xiao (2004) 研究了马尔科夫调整服务速率下的M/M/1模型. 最近, 一个新的带有故障的排队模型(称之为工作崩溃)被 Kalidass 和 Kasturi (2012) 提出. 该故障的特点是: 当系统在正常服务速度下运行时,它可能会在任何时间点崩溃; 当服务器处于故障期时, 服务速度会降低, 而不是在故障期结束前完全停止服务. 工作崩溃策略在现实世界中有许多潜在的应用, 例如, 当计算机系统受到病毒感染被攻击时, 有时它们仍然可以执行各种任务, 但速度要慢得多. 我们还可以举一个基于机器更换问题的例子, 在实际情况下, 许多机器都配备了替代 (备用) 服务器, 为主机器的故障做准备. 当主机器运行时, 它可能会意外崩溃, 并将被送到修理厂进行维修, 与此同时, 备用机器将被激活并以较低速度继续服务.
在本文中, 我们假设客户到达排队系统依据马尔科夫到达过程 (MAP), 这是一个可跟踪的类别马尔科夫更新过程. 泊松过程, Erlang更新过程, PH更新过程, 马尔科夫切换泊松过程 (MSPP) 和马尔科夫调整泊松过程 (MMPP) 都被视为马尔科夫过程 (MAP). 事实上, 我们可以使用一个马尔科夫到达过程的序列来任意接近任何随机过程. 值得注意的是, MAP的基本马尔科夫结构在矩阵分析方法 (见 Neuts 1981) 中很好地与随机模型拟合, 因此, 矩阵分析法通常被用来分析基于MAP的顾客到达排队系统. 此外, 作为一个模拟非更新和更新到达的强大工具, MAP在通信、制造和工程生产领域有很多实际应用, 在这些领域中, 到达系统的顾客通常不会形成一个更新过程. 关于MAP及其在随机模型中的应用的更多细节, 我们可以参考Neuts (1981, 1989, 1992), Lucantoni (1991) 和 Chakravarthy (2001, 2010), 以及最近与MAP有关的作品.
一般情况下, 我们可以描述基于其基本马尔科夫链的连续时间的MAP, 基本马尔科夫链应该是不可约的, 并且有一个转移率矩阵. 在状态的逗留时间服从指数分布, 参数为, 停留在状态后可能发生两个事件: (i) 依据概率, 马尔科夫链转移到状态伴随一个顾客到达; (ii) 依据概率, 马尔科夫链转移到状态并且没有顾客到达. 需要注意的是, 只有通过顾客的到达, 马尔科夫链才能从状态转移到状态. 我们定义两个矩阵: 和, 满足: , 生成元可以通过得出. 可以清楚地看出, 控制没有顾客到达的情况下状态的转移, 控制有顾客到达的情况下状态的转移.
本文的其余部分结构如下. 第二节详细介绍了马尔科夫到达过程下工作崩溃的排队系统情况. 第三部分研究了模型的稳定条件, 给出了获取平稳概率向量的计算过程. 第四部分提出一个递归公式, 以获得任意顾客的逗留时间的近似值. 我们在第五节中介绍了几个数值示例. 最后是总结.
- 模型描述
我们考虑基于马尔科夫到达过程的一个具有工作崩溃的连续时间单一服务排队系统, 它确切特征如下:
(1) 我们假设顾客到达排队系统是根据一个连续时间的科夫到达过程, 该过程可用两个 维矩阵和来描述, 其中记录了没有到达时从阶段到阶段的转移率, 记录了发生到达时从阶段到阶段的转移率. 我们假定矩阵是一个不可约矩阵, 是矩阵的一个不变向量, 即, 其中表示维单位列向量, 这个MAP的平均到达速率可以由计算出. 为了避免出现不必要的情况, 设, 因此.
(2) 工作崩溃描述如下: 当服务器处于正常服务时期, 我们假设服务时间服从参数为的指数分布, 服务器故障是按照速率的一个泊松过程发生的. 一旦服务器崩溃, 将立即被送去修复, 我们假设服务器的修复时间服从参数为的指数分布. 在修复期间, 备用服务器可能会继续为系统中当前的顾客提供服务, 而不是完全停止服务, 但服务速率会降低. 我们假定服务器故障后服务时间服从参数为的指数分布. 此时, 服务器以较低服务速度工作的连续时间称为工作崩溃时期. 修复结束后, 服务器恢复到正常服务器, 服务速率将立即变回.
(3) 假设到达时间、正常服务时期和工作故障时期的服务时间、故障时间、以及修复时间相互独立. 此外, 一旦到达, 所有顾客进入到一个单一队列, 按照“先到先服务”(FCFS)的原则被服务.
我们可以发现, 在任何时间, 系统完全可以用三个随机变量来描述: , 其中表示在时间时系统中的客户数量, 表示时间的到达阶段, 代表时间时服务器的状态, 有:
(1)
则是具有状态空间的连续马尔科夫链,
用马尔科夫链的状态的规定顺序, 即
我们可以得到如下马尔科夫链的无穷小生成函数:
(2)
其中,
其中表示一个维的单位矩阵.
从的结构容易地看出, 马尔科夫链是一个准生灭(QBD)过程.
- 稳态概率向量
我们首先研究了所考虑的排队系统的稳定性条件.
定理1. 生灭过程是稳定的, 当且仅当
(3)
证明. 定义, 使称为不可约矩阵的不变向量, 即不难证出
(4)
基于 He (2014) 中的定理3.2.1, 生灭过程是平稳的, 当且仅当
(5)
其中由等式(3)给出.
将等式 (4) 带入 (5) , 得到
(6)
注意到, 则式子 (6) 有
(7)
最后减少至, 其中由等式 (3) 给出. 证毕.
定理1中对稳定性条件有直观的解释. 显然, 方程 (7) 的左侧是到达率. 请注意, 服务器的状态在正常服务和工作崩溃之间交替, 服务器停留在正常服务期内的时间比例为, 同样地, 服务器停留在工作崩溃中的时间比例为. 因此方程 (7) 的右侧可以被看作是有效的服务率. 在有效服务率必须超过到达率的条件下, 我们可以预期队列的稳定性.
设为在稳态下的概率向量, 即, , 将向量分为
(8)
其中是一个维度为的行向量, 是一个维的行向量, 表示系统中有个顾客, 且服务器处于正常服务期, 到达阶段为; 是一个维的行向量, 表示系统中有个顾客, 且服务器处于工作崩溃期, 到达阶段为.
由于马尔科夫链是一个生灭过程, 我们可以通过矩阵几何解法对其进行分析 (见Neuts 1981) . 在条件下, 稳态概率向量由以下式子给出
(9)
其中是矩阵方程的最小非负解.
(10)
可根据以下矩阵方程求出:
(11)
(12)
有许多有效的算法来计算矩阵(见Neuts (1981) 和 Lucantoni (1991)) . 例如, 由以下递归式
(13)
定义的序列非递减序列, 且当时收敛于.
总之, 平稳概率向量可通过以下步骤获得.
(1) 利用方程 (3) 检验排队系统的稳定性.
(2) 利用递归方程 (13) 计算速率矩阵.
(3) 结合方程式 (12) 给出的归一化条件, 利用方程式 (11) 计算.
(4) 用方程 (9) 计算时的.
令表示系统中的固定队列的长度, 平均队列长度可由以下式子给出
(14)
其方差可表示为
(15)
令和分别为服务器停留在正常服务期和工作崩溃期的概率.由于服务器在这两个状态之间交替, 因此我们有
(16)
(17)
设为系统为空的概率, 即没有客户留在系统中的概率, , 注意,
(18)
其中由等式 (4) 给出, 故
(19)
- 任意客户的逗留时间分布
在这一节中, 我们给出了一个递归公式来计算平稳停留时间的互补分布. 该方法可以追溯到 Masuyama 和 Takine (2003), 他们分析了MAP/M/1共享队列过程的逗留时间. 在此基础上, 我们证明了由 Masuyama 和 Takine (2003) 提出的方法可以应用于我们模型中逗留时间的研究.
令表示任意客户的逗留时间, 即从客户到达系统时
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[19889]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
