排队系统

排队系统通信1班王锐目录2.排队论系统的概念3.Little公式4.M/M/15.一般混合制的M/M/S(n)系统7.例题赏析1.排队论系统的起源6.排队系统的应用1.排队论的起源•日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象。排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。自20世纪初以来，电话系统的设计一直在应用这个公式。30年代苏联数学家А.Я.欣钦把处于统计平衡的电话呼叫流称为最简单流。瑞典数学家巴尔姆又引入有限后效流等概念和定义。他们用数学方法深入地分析了电话呼叫的本征特性，促进了排队论的研究。50年代初，美国数学家关于生灭过程的研究、英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础。在这以后，L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。70年代以来，人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。2.排队系统的概念在实际应用中，有一大类系统被称之为随机服务系统或排队系统。在这些系统中顾客到来的时刻与服务时间的长短都是随机的，并且可能会随不同的条件而变化，因而服务系统的状况也是随机的，会随各种条件而波动。在电信网络中，交换机就可以看成是一种随机服务系统。对于不同的电信网络，可以使用不同的排队系统模拟不同的电信业务交换机进行分析。模拟这些系统的排队系统的状态变化实际上是一个生灭过程。服务员到来的顾客流离开的顾客流队列服务机构图1.排队系统模型•要仔细描述一个排队系统，主要需要描述三个方面的内容：输入过程、服务时间、排队方式等。下面使用一个随机点移动模型来说明关于排队系统的模型和假设。服务员服务机构队列t1t2τ1τ2如果只有一个服务员，在轴上有一些点从左向右做同速率的匀速直线运动，图中的t1,t2….表示顾客到达排队系统的到达间隔，它们均为随机变量；在系统忙时，τ1，τ2…表示不同顾客的服务时间，它们也是随机变量，关于ti和τi满足下面3个假设：（1）ti独立同分布；（2）τi独立同分布；（3）ti和τi独立。图2排队系统的点移动模型不同排队系统的记法采用肯德尔（D.G.Kendall）的记号A/B/C/D/E。A表示输入过程；B表示服务时间；C表示服务数目；D表示系统的容量；E表示排队规则，其中D/E的缺省表示容量无限大和FIFO方式。排队系统的分析希望指标•（1）队长。队长分布或其各种统计值及其估计。•（2）等待时间。等待时间分布或其各种统计值及其估计。•（3）忙期。即服务机构连续繁忙的时期图3排队系统模型Little公式描述了任意排队系统满足的关系，下面通过简单描述来说明该公式。下面考虑一个任意的排队系统，为了说明Little公式，首先定义：A（t）为在（0,t）内到达的顾客数；B(t)为在（0，t）内离开的顾客数；那么t时刻系统内的顾客数为N（t）=A(t)-B(t)图4到达过程A(t)和离开过程B(t)3.Little公式列德尔（Little）公式•如果N表示系统中的平均顾客数，T表示顾客在系统中的平均时间（这个时间有时也被称为系统时间）,λ表示单位时间到达系统的顾客数，对于任意排队系统，有N=Tλ上面结论可以证明对于任意排队系统都是正确的，直观意义就是一种平衡关系。公式证明过程4.M/M/1•假设一个随机过程的到达过程是一个参数为λ的Poisson过程，服务时间是参数为µ的负指数分布，等待的位置有无穷多个，排队的方式是FIFO，则这个随机过程是M/M/1。M/M/1是简单的排队系统，下面通过对这个系统的分析来加深对排队系统的了解。在求得M/M/1的队长分布和系统时间分布后，对M/M/1的稳态分析就基本完成。在对数据网络进行分析时，将使用M/M/1系统对数据交换机的一个端口进行建模。如果到达过程不是Poisson过程，或服务时间不是负指数分布，排队系统的分析就要复杂一些。在M/G/1或G/M/1中，为了消除残余分布的影响，使用嵌入马尔可夫链来替代连续时间马尔可夫链进行分析。对于G/G系统的分析就更加复杂和困难。排队系统除了稳态分析，还有瞬态分析等内容。瞬态分析考虑初始值的影响，由于分析依赖微分方程组而稳态分析依赖于线性方程组，瞬态分析的研究将比稳态分析复杂许多。MM1概述：定理2-5：M/M/1排队系统在稳态时，系统时间s服从参数为λµ−的负指数分布。证明过程现在考虑一般的排队系统，这个系统有s个服务员，但系统的容量为n。呼叫在到达系统时，如果有任何一个空闲的中继线，可以立刻得到服务，而系统如果已有n个呼叫，新到的呼叫会被拒绝。如果到达的呼叫流为参数λ的Poisson过程，服务时间服从参数为μ的负指数分布，这个系统是一个生灭过程。5.一般混合制的M/M/S(n)系统012ksn2kss状态转移图图)(//9.3nsMM............6.排队模型的应用在通信、交通、港口泊位设计、机器维修、库存控制、计算机设计等各个领域中排队论都获得了广泛应用。通信系统仍然是排队论应用的主要领域，也是其发展的重要推动力量。经过通信、计算机和应用数学三个领域的研究学者的努力研究，排队论得到了迅速的发展。在宽带综合业务数字网中，异步传送模式，统计复用，随机多址接入中都涉及到许多排队论问题，而且正在研究解决中，如ATM业务流的数学模型及其排队分析方法。使用MATLAB分析排队论由于排队论模型设计大量的数据计算和分析，所以我们可以用MATLAB来进行相关分析。MATLAB软件具有高精确度、高可靠性的特点，它提供了强大的科学运算、灵活的程序设计流程、高质量的图形可视化与界面设计、便携的与其他语言程序和语言的接口功能。所以我们利用MATLAB开发环境实现排队论中一些常用模型的工具箱开发是非常有必要的。7.例题赏析例：验证M/M/1的状态变化为一个生灭过程谢谢观看！