PEPA模型的大偏差理论

来源 :扬州大学 | 被引量 : 1次 | 上传用户:liuqin1225
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随机进程代数PEPA是一种形式化语言,它通过组合化的方式来形式地描述一些分布式计算机和移动通信等并发系统,并可以用来提取和分析系统的功能特性,比如有无死锁、吞吐量和响应时间.  每一个PEPA模型的背后是一个连续时间马尔科夫链(CTMC),通过求解这个马尔科夫链的稳态概率分布,我们就可以计算出所建模的系统的平均性能指标,如吞吐量等.但这种计算方式受到状态空间规模快速增长(状态空间爆炸)的影响,稳态概率分布很难求解出来.丁杰在他的博士论文中提出克服此问题的一个方法就是用随机模拟这个马尔科夫链来近似地提取性能,并提出了一个随机模拟算法来模拟得出PEPA模型的经验性能.由于随机模拟将会在有限时刻停止或只有有限步迭代,所模拟出来的结果只是精确值的一个近似.在丁杰的博士论文的后续工作中,他提出了模拟值对真实值的偏离程度可以用概率论中的大偏差理论来刻画.从大偏差已有的知识知道Markov链的大偏差理论主要是通过求解此Markov链的相应的速率函数来刻画的.大偏差理论早已经应用到排队网络等建模语言中,但据我们所知,在随机进程代数领域有关大偏差理论的研究还不多.  本文主要是对随机进程代数PEPA模型的随机模拟建立大偏差理论.给出了经验稳态概率分布的大偏差理论定理和经验平均性能的大偏差理论定理,得到了稳态概率分布的大偏差理论和经验平均性能的大偏差理论中的速率函数的表达式,从而可以刻画出随机模拟得到的模拟值对真实值的偏离程度.本文还以一个PEPA模型为例进行了案例研究.首先在第三章中导出了此模型的CTMC模型,并且得到了此模型的稳态概率分布和平均性能.然后在第五章中,按照定理5.1.2和定理5.2.1的证明方法,分别计算得到此模型稳态概率分布和平均性能的速率函数.  本文的结构如下:  第一章说明相关工作的背景,发展概况及问题来源,并阐述本文的研究内容.  第二章简要介绍PEPA,解释状态空间爆炸问题,并指出PEPA模型的定量定性分析方法.  第三章提出PEPA模型的性能指标概念和一个模拟算法可以得到性能指标,并以一个PEPA模型为例计算其性能指标,得到稳态概率分布和平均性能的结果.  第四章简要介绍随机变量的大偏差理论及大偏差的基本定理.  第五章提出PEPA模型经验稳态概率分布和经验平均性能的大偏差理论,并以一个PEPA模型为例表述其大偏差理论,得到此模型经验稳态概率分布和经验平均性能的速率函数.  第六章对整篇文章作总结并提出将来的工作.
其他文献
研究各种群的性质和结构是群论研究的一个主要任务.准素子群的性质和有限群结构之间的关系已被广泛地研究.特别地,子群的嵌入性质已经成为群论研究中非常活跃的领域之一.  
最小主元分析(Minor Component Analysis,MCA)是一种多元的统计方法,主要应用于数据分析、图形图像处理、曲线/曲面拟合等领域.MCA学习算法用于寻找空间中的一个方向,使得目标数
自从 8 0年代中期以来 ,生产商用一种专门的透明光耦合凝胶来填充光纤元件的拼接处。现在 ,合成光学凝胶已用于医学传感器和仪器、光二极管阵列、工业管道镜、激光收发机和许
温贮备可修系统,是可靠性理论模型中一个非常重要的研究内容之一.修复非新是依赖于众多现实问题的一个实际情况.在现实生产中,部件发生失效经修理后,未必能够修复如新,而是在
压缩感知/压缩传感理论(Compressed Sensing简称CS理论)作为信号及图像处理领域的一个热门方向,已经在计算机科学、应用数学和电气工程领域吸引了相当多的关注。这表明压缩感
随机微分方程不仅在数学科学、物理学等自然科学方面有着非常广泛的应用,同时也是工程技术、经济管理以及金融工程方面最常用的数学模型之一。  本文针对一类二阶随机微分方
针对一种基于混沌特性的有限域Chebyshev多项式和RSA结合的公钥密码算法的问题,通过对密钥生成的初始值和条件的限定,加密算法中对中间值的限定给出了一种改进方法,改进后的
在本篇论文中,我们主要讨论多重序列比对上的次优正则联合结构的预测,以及核糖核酸(RNA)的拓扑性质。  在第一章中,我们首先简要地介绍了核糖核酸之间相互作用问题(RIP)的背景