论文部分内容阅读
随机进程代数PEPA是一种形式化语言,它通过组合化的方式来形式地描述一些分布式计算机和移动通信等并发系统,并可以用来提取和分析系统的功能特性,比如有无死锁、吞吐量和响应时间. 每一个PEPA模型的背后是一个连续时间马尔科夫链(CTMC),通过求解这个马尔科夫链的稳态概率分布,我们就可以计算出所建模的系统的平均性能指标,如吞吐量等.但这种计算方式受到状态空间规模快速增长(状态空间爆炸)的影响,稳态概率分布很难求解出来.丁杰在他的博士论文中提出克服此问题的一个方法就是用随机模拟这个马尔科夫链来近似地提取性能,并提出了一个随机模拟算法来模拟得出PEPA模型的经验性能.由于随机模拟将会在有限时刻停止或只有有限步迭代,所模拟出来的结果只是精确值的一个近似.在丁杰的博士论文的后续工作中,他提出了模拟值对真实值的偏离程度可以用概率论中的大偏差理论来刻画.从大偏差已有的知识知道Markov链的大偏差理论主要是通过求解此Markov链的相应的速率函数来刻画的.大偏差理论早已经应用到排队网络等建模语言中,但据我们所知,在随机进程代数领域有关大偏差理论的研究还不多. 本文主要是对随机进程代数PEPA模型的随机模拟建立大偏差理论.给出了经验稳态概率分布的大偏差理论定理和经验平均性能的大偏差理论定理,得到了稳态概率分布的大偏差理论和经验平均性能的大偏差理论中的速率函数的表达式,从而可以刻画出随机模拟得到的模拟值对真实值的偏离程度.本文还以一个PEPA模型为例进行了案例研究.首先在第三章中导出了此模型的CTMC模型,并且得到了此模型的稳态概率分布和平均性能.然后在第五章中,按照定理5.1.2和定理5.2.1的证明方法,分别计算得到此模型稳态概率分布和平均性能的速率函数. 本文的结构如下: 第一章说明相关工作的背景,发展概况及问题来源,并阐述本文的研究内容. 第二章简要介绍PEPA,解释状态空间爆炸问题,并指出PEPA模型的定量定性分析方法. 第三章提出PEPA模型的性能指标概念和一个模拟算法可以得到性能指标,并以一个PEPA模型为例计算其性能指标,得到稳态概率分布和平均性能的结果. 第四章简要介绍随机变量的大偏差理论及大偏差的基本定理. 第五章提出PEPA模型经验稳态概率分布和经验平均性能的大偏差理论,并以一个PEPA模型为例表述其大偏差理论,得到此模型经验稳态概率分布和经验平均性能的速率函数. 第六章对整篇文章作总结并提出将来的工作.