欢迎来到天天文库
浏览记录
ID:32011098
大小:943.58 KB
页数:33页
时间:2019-01-30
《pepa模型大偏差理论》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、周莉:PEPA模型的大偏差理论中文摘要随机进程代数PEPA是一种形式化语言,它通过组合化的方式来形式地描述一些分布式计算机和移动通信等并发系统,并可以用来提取和分析系统的功能特性,比如有无死锁、吞吐量和响应时问.每一个PEPA模型的背后是一个连续时间马尔科夫链(cTMc),通过求解这个马尔科夫链的稳态概率分布,我们就可以计算出所建模的系统的平均性能指标,如吞吐量等.但这种计算方式受到状态空问规模快速增长(状态空间爆炸)的影响,稳态概率分布很难求解出来.丁杰在他的博士论文中提出克服此问题的一个方法就是用随机模拟这个马尔科夫链来近似地提取性能,并
2、提出了一个随机模拟算法来模拟得出PEPA模型的经验性能.由于随机模拟将会在有限时刻停止或只有有限步迭代,所模拟出来的结果只是精确值的一个近似.在丁杰的博士论文的后续工作中,他提出了模拟值对真实值的偏离程度可以用概率论中的大偏差理论来刻亟.从大偏差已有的知识知道Markov链的大偏差理论主要是通过求解此Markov链的相应的速率函数来刻画的.大偏差理论早已经应用到排队网络等建模语言中,但据我们所知,在随机进程代数领域有关大偏差理论的研究还不多.本文主要是对随机进程代数PEPA模型的随机模拟建立大偏差理论.给出了经验稳态概率分布的大偏差理论定理和
3、经验平均性能的大偏差理论定理,得到了稳态概率分布的大偏差理论和经验平均性能的大偏差理论中的速率函数的表达式,从而可以刻画出随机模拟得到的模拟值对真实值的偏离程度.本文还以一个PEPA模型为例进行了案例研究.首先在第三章中导出了此模型的CTMC模型,并且得到了此模型的稳态概率分布和平均性能.然后在第五章中,按照定理5.1.2和定理5.2.1的证明方法,分别计算得到此模型稳态概率分布和平均性能的速率函数.本文的结构如下:第一章说明相关工作的背景,发展概况及问题来源,并阐述本文的研究内容.第二章简要介绍PEPA,解释状态空间爆炸问题,并指出PEPA
4、模型的定量定性分析方法.第三章提出PEPA模型的性能指标概念和一个模拟算法可以得到性能指标,并以一个PEPA模型为例计算其性能指标,得到稳态概率分布和平均性能的结果.第四章简要介绍随机变量的大偏差理论及大偏差的基本定理.扬州大学硕士学位论文第五章提出PEPA模型经验稳态概率分布和经验平均性能的大偏差理论,并以一个PEPA模型为例表述其大偏差理论,得到此模型经验稳态概率分布和经验平均性能的速率函数.第六章对整篇文章作总结并提出将来的工作.关键词:PEPA状态空问爆炸问题连续马尔科夫链大偏差稳态概率分布平均性能速率函数周莉:PEPA模型的大偏差理
5、论Abstract3ThestochasticprocessalgebraPEPAisapowerfulmodelingformalism,throughthecombinationwaytodescribesomeconcurrentsystems,suchasdistributedcomputerandmobilecommunicationsystem,etc.PEPAcarlbeusedtoderiveandanalyzethesystem’Sfeatures,e·g·deadlockcheckingthroughputandrespo
6、nsetime.UnderlingeveryPEPAmodelisacontinuoustimeMarkovchain(CTMC).BysolvingthisMarkovchain’Ssteadystateprobabilitydistribution,wecanobtaintheaverageperformancemeasuresofthismodelingsystem,suchasthroughputetc.Butthiscalculationwayislimitedbytheinfluenceofrapidgrowthofthestat
7、espace’Sscale,SOthesteadystateprobabilitydistributionisdifficulttobesolvedout.J.DingproposedamethodinhisdoctoralthesistoovercomethisweakpointbyusingtheMarkovchainstochasticsimulationtoderivetheperformanceofthesystem,andgivesastochasticsimulationalgorithmtosimulatetheempiric
8、alperformancemeasuresofthePEPAmodel.Sincethestochasticsimulationwillstopafterfinit
此文档下载收益归作者所有