1、1排队论的发展史初期(10s-40s):主要研究应用于电话网和远程通信系统等无队列的排队系统(损失制)中期(40s-60s):推广应用到军事、运输、生产、社会服务等领域，主要研究有队列(等待制)的排队系统和排队网络近期(60s-今):主要研究大规模复杂排队系统的理论分析、数值分析和近似分析，尤其注重对业务突发性和带有各种网络控制的排队系统的研究21909:Erlang 发表他的有关排队论的第一篇论文;1917:Erlang 发表著名的论文“Solution of Some Problems in the Theory of Probability of Significance in Auto
2、matic Telephone Exchanges”1936-47:Palm 发表论文“Repairmen in Serving Automatic Machines”1951:Kendall 发表论文”排队论中的某些问题”,在1953 年提出使用Kendall记号;1953-57:Kendall,Lindley,Pollaczek&Khinchin 用嵌入 Markov链的方法研究M/G/1排队模型;31961:Little 提出Little 公式;1975/6:Kleinrock著的两卷”Queueing Systems”出版;1982:Wolff 提出和推广和 PASTA(Poisson
3、 Arrivals See Time Averages)准则1981:Neuts 引进矩阵分析方法;在以后的时间里,有大量的描述突发和具有 相关性通信业务的模型(如流体模型,MMPP 模型等)发表;1990后后:提出长相关自相似的业务量模型提出长相关自相似的业务量模型.4KleinrockWolff5 内容:1.基本概念和预备知识 2.Poisson到达指数服务的排队系统(M/M/1)3.M/M/m(n)问题 4.各种测度和指标 5.提高网效率的一些措施 6.优先权服务系统只涉及上世纪60年代以前的成果,此后的成果将在”现代通信中的排队论”课程中介绍6以上内容只是排队论的很少的一部分以上内容只
4、是排队论的很少的一部分,也是最初等也是最初等的一部分的一部分.除了从除了从理论分析、数值分析和近似分析理论分析、数值分析和近似分析各方向各方向(这些是从数学学科的角度这些是从数学学科的角度)发展外发展外,近二十近二十年来，在技术学科特别是通信学科的激励下年来，在技术学科特别是通信学科的激励下,尤其尤其注重对排队输入流注重对排队输入流(通信业务流通信业务流)业务突发性和带业务突发性和带有各种网络控制的排队系统的研究有各种网络控制的排队系统的研究.可以毫不夸张地说可以毫不夸张地说,通信理论的发展通信理论的发展,离不开排队论离不开排队论.7排队论所研究的问题有排队论所研究的问题有:(1)(1)等待时
5、间的等待时间的分布分布,平均平均等待时间等待时间;(2)(2)系统时间系统时间(也称逗留时间也称逗留时间)的的分布分布,平均平均系统时系统时 间及系统时间的间及系统时间的方差方差(时延抖动时延抖动););(3)(3)在系统中的顾客数在系统中的顾客数(也称系统占有数也称系统占有数)的的分布分布及及 均值均值;(4)(4)等待顾客数的等待顾客数的分布分布及其及其均值均值;(5)(5)服务器忙着服务器忙着(或空闲或空闲)的的概率概率;(6)(6)忙期长度的忙期长度的分布分布及其及其均值均值;(7)(7)在忙期被服务的顾客数的在忙期被服务的顾客数的分布分布以及它的以及它的均值均值。81.基本概念和预备
6、知识概率知识：事件A，B它可推广到无穷多个事件的情形：).()()(,BPAPBAPBA则若jiAAAPAPjinnnn,)()(11(概率加法定理概率加法定理)9事件A，B该公式称全概率公式全概率公式若对事件A，B有则称A与B相互独立相互独立。的条件概率下称在条件ABBPBAPBAP,)()()/()()/()()()(,2,1,1111nnnnnnnnjinnAPABPABPABPBPnAjiAAA为完备组称)()()(BPAPBAP10随机变量X的分布函数概率分布的母函数母函数概率分布密度的Laplace变换变换X1,X2相互独立相互独立,则在离散时则在离散时,和的母函数等和的母函数等于
7、母函数的乘积于母函数的乘积;在连续时在连续时,和的和的Laplace变变换换等于等于Laplace变换变换的乘积的乘积.)(xXPxFX0)(nnnzpzG0*)()(dxexfsFsxX)()()();()()(*21212121sFsFsFzGzGzGXXXXXXXX11ErlangKendall其中:X-到达分布;Y-服务时间分布;Z-服务员个数 A-等待空间大小,B-顾客源的限制;C-服务规则Kendall记号记号:X/Y/Z/A/B/C122.Poisson到达指数服务的排队系统 指数分布指数分布指数分布和普松过程在排队论中有着特殊的地位。这是因为,一方面指数分布在连续型概率分布中是
8、唯一的具有无记忆性质的分布,普松分布又和指数分布有着紧密的关系。另一方面,实验证明普松分布是电话呼叫数概率分布的一种比较好的近似,而指数分布又是电话通话时间概率分布的一种好的近似,它们在排队论的发展历史中起了很大的作用并继续起着重要的作用。13 定义定义 一个随机变量x当且仅当对任意的 满足条件 时，则称x的分布是无记忆无记忆的。无记忆性的直观理解是:一个物体的使用寿命是指被使用的时间，它是一个随机变量。如果该物体不论被使用了多久，其剩余寿命的分布与总寿命的分布完全相同，那么这种寿命分布是无记忆的，体现了永远年轻。0,/XPXXP14按条件概率定义，我们有 如果随机变量x是无记忆的，那么 反之
9、，如果随机变量的分布满足(*)，则该分布是无记忆的。/,/XPXPXPXPXXPXXP(*)XPXPXP15因为指数分布的余分布函数为 而 故指数分布是无记忆的。当服务时间是指数分布时，则不论顾客占用服务台多久，其剩余的服务时间仍为指数分布的随机变量。在连续型在连续型随机变量中指数分布是唯一的具有无记忆分布随机变量中指数分布是唯一的具有无记忆分布的随机变量的随机变量。在离散随机变量中，几何分布是唯一的具有无记忆性质的随机变量。tetFtTPtG)(1)()()()(21)(212121tGtGeeettGtttt16Poisson过程过程定义定义 若用n(t)表示从0开始到时刻t为止已经发生的
10、事件的数目，则称随机过程n(t),t 0为计数过程。一般地说,在计数过程的记号上还应标以计数的起始时刻,如果过程的统计特性与起始时刻无关,则称过程为平稳的.下面我们讨论的,除非特别指明都是平稳过程。显然,计数过程n(t)取非负的整数值,并且n(t)是t的非降函数。对于 是在区间(s,t内发生的事件数,量 称为n(t)在区间(s,t的增量。如当 独立,则称有则称有独立增量独立增量.)()(,(sntnntsts)()(sntn,(,(22112211,(,(tstsnntsts与时17 Poisson过程定义(1):一计数过程n(t)如果满足1.n(0)=0;2.n(t),t 0有独立增量;3.
11、发生在任何长为t的区间中的事件数服从参数为 的Poisson分布:Pn(t+s)-n(s)=n=则称计数过程n(t)是率(参数)为(0)的Poisson过程。senttn,!)(t18Poisson过程定义(2):一计数过程n(t)如果满足1.n(0)=0;2.n(t),t 0是平稳的，且有独立增量;3.Pn(h)=1=h+o(h);4.Pn(h)2=o(h)。则称计数过程n(t)是参数为(0)的Poisson过程。19在一个时间区间内的顾客的到达数与时间起点无关叫平稳性平稳性;顾客的到达时刻相互独立称无后效性无后效性;在很短的时间间隔内到达两个以上顾客的概率可认为是0,这叫稀疏性稀疏性.满足
12、以上三个条件的随机流称为简单流简单流.简单流的到达间隔是负指数分布的,且在一段时间内到达的顾客数是普松分布.现证明简单流的到达间隔是负指数分布简单流的到达间隔是负指数分布:设到达间隔为t,把0,t)分成N等份,每份的长度为 ,在0,t)都未到达,而在时刻t有顾客到达了的概率为)(,)1()1()1()(NetNtNtatttNNN 个N20),(!)()1(!)(11)()1(!)1()1()()1()(称到达强度客数是单位时间里到达的顾TkkNkkkNkkNkekTNTkTNkNNNNNNTNTkkNNNkNTp再证明当到达间隔是指数分布时当到达间隔是指数分布时,在时间间隔在时间间隔T T内
13、内的的到达数是普松分布到达数是普松分布:把时间间隔T分成N等份,在这N个小区间内,有k个顾客顾客:21现已证明现已证明:简单流的到达间隔是负指数分布简单流的到达间隔是负指数分布;当到达间隔是指数分布时当到达间隔是指数分布时,在时间间隔在时间间隔T T内内的到达数是普松分布的到达数是普松分布.在一段时间内在一段时间内,电话的呼叫是简单流电话的呼叫是简单流,因为因为顾客的到达数与时间起点无关;顾客的到达时刻相互独立;在很短的时间间隔内到达两个以上顾客的概率可认为是0.22Poisson过程的性质性质如下:1.令 和 分别是具有参数和的独立Poisson过程,则N(t),t 0是率为+的Poisso
14、n过程。证明:Poisson过程的分布母函数：的分布母函数=)1(00!)()(znntnnnnezentzpzG)1)()1()1(21)()(zzzeeezGzG0),(1ttn0),(2ttn)()()(21tntntN)()()(21tntntN232.对于参数为的Poisson过程，假设发生的 每个事件独立地以概率p做了记录，未做记 录的概率为1-p。令n1(t)是到t为止被做了记 录的事件数，而n2(t)是未被记录的事件数,则 和 分别是参数 为 和 的Poisson分布且相互独立.p)1(p0),(2ttn0),(1ttn24!)1(!)()1()()(/)()(!)(!)1(!
15、)()()!()()1(!)()1()()(/)()()1(22011mtpenteppmnntNPntNmtnPmtnPmpteektpmtptemntpmpnteppmnntNPntNmtnPmtnPmtpntmmnmnmnmptktkmmtmnmnmnmntmnmmnmn证明证明:25这两条性质说的是:(1)独立Poisson过程的和仍是Poisson过程,而且“和过程”的参数为加项过程的参数之和;(2)Poisson过程的分支也是Poisson过程,而且 各分支过程的参数是分支概率乘以原过程 的参数.26 Little定理定理:在排队系统中的平均顾客数=顾客的平均到达率平均逗留时间:E
16、N=Es证明:Little27A(t)=(0,t)内顾客的到达数,则在(0,t)内的平均到达率为 。D(t)=在(0,t)内离开系统的顾客数。N(t)=在时刻t，系统中的顾客数,于是N(t)=A(t)-D(t)。图中两条折线之间的面积表示在(0,t)内所有顾客花费在系统中的总时间,记为(t)。Tt=在(0,t)内每一个顾客在系统中的平均逗留时间(对(0,t)内全部顾客取平均)，于是 .ENt=在(0,t)内系统中的平均顾客数,于是 ,令t取极限得 这里,EN是排队系统中的平均顾客数,T是一个顾客在系统中的平均逗留时间,是顾客的平均到达率。ttAt/)()(/)(tAtTttttTttAtAtt
17、tNE/)()(/)(/)(TNE28这个结论与 到达间隔分布,服务时间分布,服务员个数以及 排队规则都无关。29排队系统排队系统(M/M/1)是指到达间隔是指到达间隔(到达数到达数)服从负指数服从负指数(普松普松)分布分布,服务时间服从负指数服务时间服从负指数分布分布,服务窗口数为服务窗口数为1 1的排队系统的排队系统.设到达分布的参数为设到达分布的参数为 ,服务时间服务时间分布的参数为分布的参数为 ,时间间隔时间间隔t(t(不失一般性不失一般性,可设为可设为(0,t(0,t区间区间)内有内有n n个顾客到达的概率记为个顾客到达的概率记为 .现考察区间现考察区间,它可看成它可看成于是在内到达
18、于是在内到达n n个顾客这个事件可分解为以下事件个顾客这个事件可分解为以下事件的并的并:在在 内到达内到达n+1n+1个顾客个顾客,在在 内离开一内离开一个顾客个顾客,在在 内到达内到达n-1n-1个顾客个顾客,在在 内又到内又到因为 的概率=;的概率=的概率=;的概率=)(tPn),0(ttMarkov),0(tt),(,0(tttt,0(t),(ttt,0(t),(ttt30)()()()()();()()()()()()1()();()()1()(1110011100tPtPtPtPtPtPtPttPttPtPttttPttPtPtttPnnnnnnnn因为 的概率=;的概率=的概率=;
19、的概率=nn1t00)1(tnn1tnn)1(tt到达一个顾客到达一个顾客,在在 内到达内到达n n个顾客个顾客,在在 内内顾客的到达数和离开数相等顾客的到达数和离开数相等.故而可列出以下瞬态故而可列出以下瞬态方程方程:,0(t),(ttt310tttt在时刻 系统中有n个顾客是由以下三个事件组成:1)在时刻t有N+1个顾客,在 的时间里没有到达但离开一个顾客;2)在时刻t有N-1个顾客,在 的时间里到达一个顾客但没有离开的顾客;2)在时刻t有N个顾客,在 的时间里到达和离去的顾客数相等(包括未到和未离去).ttttt)(1ttPn)()1(tPttn)(1ttPn32在 内到达一个顾客的概率
20、为没有到达的概率为在 内离开一个顾客的概率为没有顾客离开的概率为)()!2)(1(2totttttettt)()!2)(1(112totttetYPt)(1tot)(1tot33)2()()(1()2()()2()();(2212121(tItItIeitPmmnimninininntn,2,1,0),()(!)!()2()(02mxIxIjmjxxImmjjmm为m阶Bessel函数方程)(xIm瞬态方程的解为瞬态方程的解为34下面我们考察随机稳态解。我们定义 ,于是有 这是一个递推公式,经逐次递推得 再由归一化条件求得 ,当然这一切必须在=/n=(1-)=)(limtPPntn002120
21、1)(,)()(,)(PPPPPPPnn1njj1n0)(limtPnt),3,2,1(,)(,1101nPPPPPnnn10Pnnp)1(35M/M/1的稳态解是的稳态解是那么平均队长是那么平均队长是由由Little定理定理,时延为时延为,2,1,0,)1(nPnn)1()1(1)1()11()1()()1()1()1(200100ddddnnnpnnnnnnnnn)1(1)1(nS36在稳定状态下指数系统的平衡方程法在稳定状态下指数系统的平衡方程法设所有到达间隔和服务时间都是指数分布的,那么从任何时刻直到状态变化的这段时间也是指数分布的。以前我们写出P(t)的微分方程并让 而得到稳态方程,
22、我们也可以直接列出方程。在稳定情况下,进入状态的率必须等于从同一个状态离开的率,即进入和离开的率必须平衡。对于M/M/1，以下的表是平衡的概念。0)(tP37 状态 离开率 进入率 0 P0 =P1 1 (+)P1 =P0+P2 2 (+)P2 =P1+P3 3 (+)P3 =P2+P4 n (+)Pn =Pn-1+Pn+1 这些方程称为“平衡方程平衡方程”。011nn1n38生灭过程生灭过程:它也是一种马尔科夫过程它也是一种马尔科夫过程,只是状态只是状态只向相邻的状态转移只向相邻的状态转移.在连续时间的情况下在连续时间的情况下,状状态有以下转移率矩阵态有以下转移率矩阵:44443333222
23、2111100)(000)(000)(000)(00039更一般地,对于生-灭过程,我们有n=系统处在n时的到达率,n=系统处在n时的服务率.那么由生-灭平衡概念,得 状态 离开率 进入 0 0P0 =1 P1 1 (1+1)P1 =0P0+2P2 2 (2+2)P2 =1P1+3P3 3 (3+3)P3 =2P2+4P4 n (n+n)Pn =n-1Pn-1+n+1Pn+1 0121nn1n1022n1nn1n1231nn1n2n40在这情形,我们有 如此递推得 得 101n1i,1)(1 niiP,0211012120101PPPPP01011,nnniiinPPP由1111011nnii
24、niiP41为使稳定解存在,必须要有否则 P0=0 P1=0 P2=0 等等。1111nniinii423.M/M/m(n)问题(话务工程中的计算方法话务工程中的计算方法)在话务工程中,经典排队论被广泛地应用,其中爱尔兰(Erlang)-B公式和恩格塞特(Engset)公式在计算中起着重要的作用。在较长的时间内,使用这两个公式进行某种定量分析时依靠查表。国外的有些大学和研究机构早已把话务工程中涉及的数学计算编成软件,如波兰波兹南大学的J.Kubasik(1985),AT&T的D.L.Jagerman(1984年)编了有关软件。现在我们将介绍这方面的内容。43有限源有限源设总的用户数为N，中继线
25、数为n，为每个用户呼叫的到达率,为服务率,如果总的话务量为A，则a.损失制损失制如果没有缓冲器,那麽一旦系统的中继线全被占用,来到的呼叫将被拒绝,这就是损失制(式)。在损失制中我们总是假定N n(不然就无损失可言)。按设定我们有 NA),3,2,1()1,2,1,0()(njjnjjNjj44系统的状态分布为系统的状态分布为 njjknkkkpjNkNpnkpkNp0_1000)(:.,),2,1(平均到达率为011001)(!)1()1()1(PkkNNNPiiNPPkkikiiik45下面介绍呼损概率。下面介绍呼损概率。应当说明应当说明,在有限源损失制中在有限源损失制中,有两种意义的有两种
26、意义的损失率损失率,其一为按时间计算的损失率其一为按时间计算的损失率,那就是全部那就是全部服务台被占的概率服务台被占的概率 另一种意义的损失率是按呼另一种意义的损失率是按呼叫计算的损失率叫计算的损失率,那就是的那就是的Engset公式公式,它的意义是它的意义是单位时间损失的平均呼叫数单位时间损失的平均呼叫数 与单位时与单位时间到达的平均呼叫数间到达的平均呼叫数 之比之比:npnN)(npnjjpjN0_)(njjnnjjnpjNjNpnNnNpjNpnNB0000)()()()(46kNNkNkNNkNkNkNkNkNEngestjNnNjNjNnNnNpjNjNpnNnNpjNpnNBnjj
27、nnjjnnjjnnjjn1)!1(!)!1()!(!)()()(11)()()()()()(000000其中公式47b.等待制等待制设系统的缓冲器容量为N,也就是说,如果系统的中继线全被占用,再来的呼叫总可以等待到有线路空出而得到通信。在这种制式下无损失而只有时延。按定义有48101000!),(,!),(,1,)1,2,1,0()(nkNnknkkkniiiijjnnkkNkNpNinpnniiNnipiNpNjnnnjjNjjN49需要等待的概率为 PW0=系统中的平均顾客数(平均占有数)为 平均等待数为 NnkkpNkkdkpL0NnkkqpnkL)(50无限源无限源设到达率设到达率=
28、，服务率服务率=，中继线数中继线数=n。a.损失制损失制状态分布为状态分布为)(!),()(,!),2,1,0(,!01000公式呼损概率为BErlangknnEkpnipipNkknNkkii51阻塞(损失)概率 定义为顾客被拒绝进入队列的概率。因为按顾客计算的阻塞率是损失的顾客数与要求服务的顾客数之比,假定等待空间容量为K，当系统已达到稳定时,在长为的时间内能进入系统的平均顾客数为 因为当系统在状态K时顾客的到达将被阻塞,顾客被阻塞的平均数为 ,所以在M/M/n的情况下,iKiKBPPKP0iK/)(KPKiKiiP0BPniinnnninininBinPPPPPnP000in!/!/1/
29、)(52b.等待制等待制/nMM100_101000)(!)(!)(!0),1(1:)(,)(!),(,!),(,!nknknnnkknknkniiiinnnknnnpnnnpWPDnDSnnnkpnipnnnipip其中平均时延53DnDnnnnnpnjnpnnknppnnnkpnkLnjjnnknknnknkknkkq)1(1)()1(1)(!)(!)(!)()(201010101平均等待数541 11!)(1!)!1()!1(!:10101011010110111110111nDLpnnnkpnnnnknnkpnnkkpnnknkpnnkkkkpLqnknkknknkknknknkknk
30、nkkknknknkkknknknkknknknknkkkkkd平均占有数55c.混合制混合制(M/M/n/m)1(,:,!:)(,!),(,!),(,!_1_10101000mmkkddnkmnknkkknmmmnkmnknkkkniiiipkpLLSnnknnpnnkpminpnnnipip时延呼损概率56特别对于单服务损失制排队M/M/1/K，111001)1()()(11)(11)(1,00,),(,KKKKKKKnniippKiKii对所有的57下面我们推导一个比上式更一般的式子的递推计下面我们推导一个比上式更一般的式子的递推计算公式。对于有限容量的算公式。对于有限容量的(参数依赖状
31、态的参数依赖状态的)M/M/1/K系统系统)1(1)1()(1)()(10n1110n11K10nK0nKKPKPPPPPPPPPPKPBKKBKKnKnKKKKnKnKKKKKnKnKnKnKB58以上利用了关系式以上利用了关系式:当当 时时,记记 则有则有 )1(1)1()(KPKPKPBBB11KKKKPP0.023493(10)0.030073,(9),0.038756(8)0.0503985,(7)0.0663417,(6)0.0888195(5)0.121847,(4)0.173442,(3)0.262295(2)0.444444,(1)1,(0):10,8.0BBBBBBBBBB
32、BPPPPPPPPPPPKnn,59按时间计算的阻塞率按时间计算的阻塞率因为在这个系统中到达率不变因为在这个系统中到达率不变,所以两种意义所以两种意义的阻塞率是相同的。的阻塞率是相同的。023493.08.018.0)8.01(-1)1(11101KK60例例1某商店有3个服务员,每个服务员在每一时刻只能服务一个顾客,服务时间为负指数分布,均值为2.5分钟.顾客到达为普松分布,平均每分钟到达1.2人.设无等待,求顾客到达而未被服务所占的百分比;若要求到达而未被服务所占的比例小于5%,问需几个服务员?解:排队系统类型:M/M/3.35.0135.4!3;13!3!21;5.4!3;5.4!2;3
33、;35.22.1,5.21,2.130333232kkkP61设需n个服务员,则.022.0846.19434.0!7,846.19!,434.0!7.05271.04125.190125.1!6,4125.19!,0125.1!6;11.04.180255.2!5,4.18!,025.2120243!5;206.0375.16375.3!4,375.16375.313!,375.32481!4;35.22.1,5.21,2.17077707606660650555054044404kkkkkkkkkkkkkkkkkPkkPkkPkkPk62例例2某厂有N=20台机床,每台机床平均每隔1小时就
34、要损坏,维修人员修复一台机床的平均时间为0.1小时.如一台机床由于等待维修不能开工造成的损失为C1=180元/时.维修工的工资为C2=6元/小时.问最好保留几位维修工可使费用(损失加工资)最少?解:系统是M/M/n/N/N.排队系统的状态是损坏的机器数.101000!),(,!),(,1,)1,2,1,0()(nkNnknkkkniiiijjnnkkNkNpNinpnniiNnjpiNpNjnnnjjNjjN上述公式里的.1.0,163如果发生故障的机床数为j,等待维修的机床数为(j-n),平均数为 ,由此造成的损失为:如果损坏的机床数少于修理工的数目,则就有空闲的修理工,他们空闲着但工资照拿
35、,对老板来说有损失:总损失=NnjjqpnjCLC111)(njjpjnC02)(njjNnjjqpjnCpnjCLCLC0211*21)()(Nnjjpnj1)(这里都指每小时的损失.64njjpjn0)(Nnjjpnj1)(总损失n=30.33891.212668.2696n=40.06832.18825.4287n=5*0.01293.18321.4237n=60.00224.18225.4799n=70.00035.1631.146665例3某维修站有2名工人,站内可放5台机器.设待修机器的到达间隔与维修时间皆负指数分布,平均每隔5分钟就有一部机器送来,每部机器的修理时间平均为10分钟
36、.求1)维修站里没有机器的概率;2)维修站里场地有空的概率;3)进入维修站的平均机器数;4)机器在维修站内的平均等待时间.解:这是M/M/2/5/FCFS问题.101000)(,!),(,!),(,!nkmnknkkkniiiinnkpminpnnnipip66667.69601095511301,55911951)1(,11211116322!2727.211301111632581644832422543211911211,1111632816482421!.5,2,2,101,51_5_0255554321541011100NEWppppppppppppnnkpmnnkmnknkkk在站
37、内平均机器数站内有空位的概率67例4售票处有三个窗口,顾客以每分钟4人的平均速度按普松规律到达,服务时间按指数分布,均值为0.5分钟.求1)售票处空闲的概率;2)平均队长;3)平均等待时间和逗留时间.解:为M/M/3/.2249491233!32)(!09142211)(!130100pnnnpWPDnnnkpnnkknknk681813)941(5.0)1(1:3,)32(2191)32(29!,274!3,92!2,92912),(,!),(,!_00330220100nDSipnnpppppppnipnnnjpipiiniiiniiii平均时延926)1(21:1DnDkpLkkd平均占
38、有数69982)(1DDnpnkLnkkq平均等待数平均逗留时间:平均等待时间1813)1(5.01 DnDLSd925.0/1DDnLWq70例5有一洗车间,服务速率为60辆/小时,洗车间外可停4辆车,汽车到达的速率为40辆/小时.求1)汽车冲洗间无车的概率;2)停满车的概率;3)汽车到达此冲洗处的平均数目;4)平均等待数目;5)平均逗留时间;6)平均等待时间.解:M/M/1/5类型.5,4,3,2,1,665243)32(;365.0665243111!.1,326040,60,4001061543210ippnnkpniiinkmnknkkk71min242.108.38788.0,78
39、8.0)1(min,242.20374.008.38423.1:08.38952.040)048.01(40)1(,423.1,048.01)1(1!_0_16554325101555qdqdmmkkdnkmnknkkkLWpLLhLSpkpLnnknnp时延72例6某商店每天开10个小时,一天平均有90个顾客到达商店,商店的服务是平均每小时服务10个顾客,若假定顾客到达服从普松规律,服务时间服从负指数分布.求1)在商店等待服务的顾客平均数;2)在队长中多于2个顾客的概率;3)在商店中的平均顾客数;4)若希望商店的平均顾客数少到2人,平均服务速度需提高到多少?解:M/M/1/问题,队长分布为0
40、,)1(npnn5.13227,932,23,21;1.8;729.02;91.09.019.0109,10,10903则令NENENENPNEw734.各种测度和指标各种测度和指标业务量业务量是指在指定时间内线路被占用的总时间.若某线路有m条信道,第r条信道被占 秒,则m条信道(或该线路)的业务量为 .业务的强度业务的强度通常指呼叫量,是线路占用时间与观察时间之比,单位是Erlang.一天内最忙的一小时内的呼叫量称日呼叫量.一年内取三十天,取这些天的日呼叫量的平均值称为年呼叫量或基准呼叫量基准呼叫量.mrrQQ1rQ顾客到达的时间进程服务时间观察时间线路占用时间74 时间阻塞率时间阻塞率是在
41、总观察时间内阻塞时间所占的百 分比,它也就是截止队长为n时的拒绝概率,记为pn.呼叫阻塞率呼叫阻塞率是被拒绝的呼叫次数占总呼叫次数的百分比,通常称为呼损的就是这个呼叫阻塞率,记为pc.从排队论看,pn相当于随机时刻观察系统处于状态n的概率,pc相当于顾客到达时刻观察系统处于状态n的概率.(顾客到达时,系统处于状态n将被拒绝进入系统,其概率就是拒绝的百分比.)一般说来,由于阻塞期间可能没有顾客到达,故pc pn.75时延时延指消息进入网内后直到被利用完毕所需的时间,这包括等待时间,服务时间,传输时延和处理时间.在所要求的呼叫中,有一部分被拒绝,通常以单位时间通过的业务量为通过量通过量,即 (Er
42、lang),其中a是呼叫量 ,pc是呼损.也有把单位时间内通过的呼叫次数作为通过量,即 (次/秒).信道的利用率:,其中 是线路的容量.)1(crpaT)1(crpTrrCTrC76今考虑用户数为有限值N的准随机呼叫,令 为每个用户在单位时间内的平均呼叫次数，截止队长为n.当r个用户已被接受排队服务时,到达率为(N-r),则呼叫阻塞率为其中分子是被阻塞的呼叫次数,分母是总呼叫次数.当N时,所有r与N相比均可忽略,且 ,则上式成为在N有限时,pcpn.当N n时,pc和pn差别不大.从统计测量来说,用pc比用pn方便.在Nn的情况下,准随机呼叫可近似成随机呼叫.nnrrncpprNpnNp000
43、)()(NNlimn0rrnppcp77设网内的源宿端间某有向径上有r条边,边上呼损(i=1,2,r),源宿端间的呼损将为对于数字线路,其容量也可用路数m来表示,它是线路上传输速率R与信息传输速率r之比:通信网中有M条边,相当于M条线路,则全网效率为 总通过量为)1(1r1icicpprRm M0iM0iiTiC)1(0ciMiipaTCip78业务分析步骤业务分析步骤:1)建立模型建立模型;2)定义状态变量定义状态变量;3)列出状态方程列出状态方程;4)求解状态方程求解状态方程;最后计算所需的性能指标最后计算所需的性能指标.79业务分析举例业务分析举例1）主叫线即时拒绝系统站换交A主用线B备
44、用线00100111)(2)4()(3()(2()()1(1001111100101101100100ppppppppppp为占为空表备线状态表主线状态状态1,0,),(yxyx802211210220120022)22)(1()2()22)(1(222pppp0021110002110100211100100100111211),3(,211),2(,2),(),1(),(2),4(pppppppppppppp由由由由81系统的线路利用率211100122)1()(21ppp换个角度,(0,1),(1,0)时通过一个,(1,1)时通过2个.对于M/M/2/2系统,2120220202!2/!
45、22)!1(2)1(pprrrBmTrrrrrr822）公共备线即时拒绝系统AB12ACB)(0),(1,),(空表闲占表忙的忙闲CBAzyx83111112222221000100001110111101010011841)9()(3)8()()2)(7()2)(6()()2)(5()()(4()()(3()()(2()()(1(1111101010111000100010001012110210111111111100001110121111002010111021111001010201111011100001100211100110002010211010110012110000101
46、000021ppppppppppppppppppppppppppppppppppppppp85000212100021100020002210002210002001200021100111012100000101010010002110101011000100010001)32(23)65(322)2()22)(22()12(:)6()5()2()(12(,2)22)(12(,2)12(),2(,22,22,2),4()3()2(2),1(pxxxpxxpxpxxpxxxpxpxppppxxppppxpppppppp由由866141091812261410)34()12(2223),8(61
47、41034)12(,614106116:)2(22300022000200021110002210002231pppppxpx由代入87)31015124)(1(,37531015124)(1(3753132527164375,)375364221(1.37536423422342234520000002232111110101011001010100000000223111pppppppppppp88)41215103)(1()463()243()5.0)(43()35.53()43(,57343223111221102101011210001020012000pppppppp89A端用户的
48、呼损B端用户的呼损简化：线路的利用率：若 得近似式：11101121111011ppppppCC2)820163(32221CCpp)123847266(3)(32)(31432111101110011100010001ppppppp1)1(2),1(221211Cpp903）两次排队问题储存储存AB2C1C输入为普松流，到达率 包/秒。每包平均比特数为a，信包长为指数分布。r和s分别为在C1和C2前的队长，信道C1和C2的服务率分别是)/(),/(2211秒包秒包acac911,21,11,1211,021,1102120,10101200)(,0,0)(,0)(,0,0srsrsrrsss
49、srrrppppsrppprpppsppsr001001110rs0rs122192)(21)1(1)1(1)1)(1(),1)(1()1)(1(1,21221121212121000021002100002100ssSpppppppsrrsrssrrsrssrrs平均时延效率935.提高网效率的一些措施 (1)大群化效应 (2)延迟效应 (3)综合效应 (4)迂回效应94大群化效应大群化效应:资源集中利用优于分散经营.从 及(其中a=是呼叫量,m为信道数)可算出:大群化效应之例mrrmcramap0!m)p-a(1c95阻塞率 值要求 0.1时,可得当a=1(Erlang)时,需m=3,此时
50、 =0.0625,=(1-)/3=31%,当a=10(Erlang)时,需m=13,此时 =0.0843,=10(1-0.0843)/13=70.5%,当a=100(Erlang)时,需m=96,此 =0.1017,=100 .系统业务量愈大节省愈明显.bpbpbpbp%9496/)1(bpcpcpma11010010.50.910.9930.06250.750.97100.2150.90300.701000.07600061071071.196A=100A=10A=5A=1Pm3139697在信息交换网中主要关心时延.已知系统时间(时延)为 信道效率为=.若把n个到达率为的业务集中到一个大容
