排队论算法含ppt

1排队论及其应用

Lecture2 随机过程&排队论初步中国科学技术大学计算机科学与技术学院田野随机过程随机变量X，分布函数不变如果随机变量的分布函数随时间变化，对时间集合T，得到一组随机变量，称之为随机过程如果时间集合T离散，如T={0,1,2,…}，称为离散时间的随机过程，{Xn:n∈T}如果时间集合T连续，称为连续时间的随机过程，{X(t):t∈T}如果Xn或者X(t)离散/连续，称这个随机过程离散/连续2例：某路由器的IP包t时刻进入缓存等待转发，等待时间{W(t):t>0}是一个连续时间的连续随机过程从时间0到t到达路由器的IP包个数{N(t):t>0}是一个连续时间的离散随机过程Xn表示一周7天中某一天某计算机启动的进程数，n∈{1,2,3,4,5,6,7}。{Xn}是一个离散时间的离散随机过程。Xn表示一周7天中某一天某计算机的工作时间，n∈{1,2,3,4,5,6,7}。{Xn}是一个离散时间的连续随机变量。3计数过程令N(t)表示在时间段[0,t)内的某种事件发生的次数。N(t)称为该事件的计数过程。计数过程是一种随机过程。事件：数据包到达路由器；顾客到达商店性质：N(0)=0N(t)非负如果s<t，N(s)≤N(t)，N(t)-N(s)是时间[s,t)内发生的事件个数4例，伯努力过程X1，X2，…是独立同分布的伯努力变量，成功的概率为p。令Sn=X1+X2+…+Xn，即前n次伯努力实验的成功次数，{Sn}是一个计数过程，被称为伯努力过程。Sn的分布是二项分布。5泊松过程一个计数过程{N(t),t≥0}如果满足以下条件，则被称为参数λ的泊松过程独立增量过程（即独立时间段上的事件发生的个数是独立的）平稳过程（在任意一段时间内发生的事件个数的分布是不变的）在一小段时间h内发生一个事件的概率为λh+o(h)。在一小段时间h内发生多于一个事件的概率为o(h)λ被称为泊松过程的速率6定理：{N(t)，t≥0}是一个速率为λ的泊松过程。Y表示一段时间t>0内事件发生的个数，则证明：定义，

取h→0

代入初始条件，得到

7参数为λt的泊松分布对时间t+h时n个事件发生的情况Pn(t+h)，三种情况时间t时已经发生了n个事件，时间t时发生了n-1个事件，[t,t+h)这段时间发生了1个事件时间t时发生了n-k个事件，[t,t+h)这段时间发生了k个事件，k>1

取h→0，

初始条件，迭代求解得到

8定理：{N(t)，t≥0}是一个速率为λ的泊松过程。令0<t1<t2<t3<…为事件发生的一系列时间。定义事件发生的间隔τ0=t1-0，τ1=t2-t1，τ2=t3-t2，…，τk=tk+1-tk，…。时间间隔{τi}是独立同分布的，服从参数为λ的指数分布。证明：对任意n和τ，下面两个事件等价

{τn>s}，{N(tn-1+s)-N(tn-1)=0}

所以，P[τn>s]=P[N(tn-1+s)-N(tn-1)=0]=P[N(s)=0]=e-λs9指数分布定理：{N(t)，t≥0}是一个计数过程，事件发生间隔记为{τn}。如果{τn}为独立同分布的随机变量，且服从参数λ的指数分布，则N(t)是一个泊松过程。证明：略10总结泊松过程从时间0到时间t发生的事件个数是参数λt的泊松分布事件发生间隔{τn}是指数分布泊松过程1112例

某商店，假设顾客按照以下比例单个或者成双到达，f(1)=p，f(2)=1-p。客户到达批次间隔服从以下分布

证明时间[0,t)内累计到达的客户数量服从分布如果总共有n个客户，假设其中发生k次成对到达，n-2k次单个到达，分别可以用速率为(1-p)λ和pλ的泊松过程表示。k次成对到达，n-2k次单个到达，k的取值范围从0到1314例

给定两个泊松过程，事件发生速率分别为λ1，λ2。从时间t=0开始，问首先观察到第一个过程事件发生的概率。假定过程1的第一个事件发生的时间是t1，过程2的第一个事件发生的时间是t2。t1和t2是参数为λ1和λ2的指数分布

15排队问题排队随处可见顾客在超市收银柜台排队飞机在机场排队等待起飞进程在操作系统排队等待调度…排队的原因：由于服务需求大于服务能力规范用语客户（Customer），请求并接受服务者，例如顾客、飞机、进程、等等服务器（Server），提供服务的设施，例如收银员、机场跑道、CPU、等等16排队系统六要素一个排队系统包括六要素客户到达模式服务模式排队规则系统容量服务器数量服务阶段17排队系统六要素客户到达模式耐心客户/非耐心客户：中途离开？客户到达时间间隔可以看作一个随机变量用一个随机过程描述客户到达模式例如：可以用一个泊松过程表示客户到达，到达间隔服从指数分布平稳/非平稳（stationary）到达模式例如：突发大批到达客户服务模式状态无关/状态相关：服务可以“换档”服务时间可以看作一个随机变量例如：可以用一个指数分布描述服务时间平稳/非平稳（stationary）服务时间例如：服务器可以学习，提高服务效率1819排队规则FCFS，LCFS，优先级先占优先（Preemptive），非先占优先（Nonpreemptive）系统容量客户不能立即获得服务时选择等待/离开有限/无限个等待位服务器数量单个/多个服务器多服务器多队列，多服务器单队列20多服务器多队列多服务器单队列服务阶段完整的服务由多个服务阶段（服务器）组成可能有回路比如：体检，产品生产过程（有回路）2122排队系统命名法则一个排队系统表示为A/B/X/Y/ZA：客户到达模式B：服务模式X：服务器数量Y：等待位数量Z：排队规则23符号取值解释A、BM、D、Ek，Hk，PH，G客户到达间隔/服务时间的概率分布，M表示指数分布（马尔科夫），G表示任意分布，D表示固定值X，Y1,2,…,∞服务器/等待位数量ZFCFS，LCFS，RSS，PR，GD先到先服务，先到后服务，随机，优先级，任意例：M/D/2/∞/FCFS，客户到达符合泊松过程;固定服务时间;2个服务器；无限个等待位；First-come-first-serve通常假定无限个等待位和FCFS，因此常用A/B/X描述一个排队系统比如，M/M/1，M/M/c，…，等等24排队系统常见的性能指标客户等待时间客户在队列中等待的时间(Lq)客户在整个排队系统中消耗的时间(L)=队列等待时间+服务时间客户在排队系统中的累积程度等待队列中的客户数目(Nq)整个排队系统中的客户数目(N)=等待队列客户数目+正在接受服务的客户数目空闲服务器服务器空闲的时间比例系统设计目标：提高服务器利用率，缩短客户等待时间等等，目标往往是相互矛盾的2526G/G/1和G/G/c上的一般性结论单位时间λ个客户到达，一个服务器单位时间能够服务μ个客户，客户到达时间间隔和服务时间任意分布，1个或者c个服务器，无限等待位。G/G/1或者G/G/c。定义ρ>1：客户不断累积，越来越多ρ<1：排队系统达到平稳态，系统不随时间变化ρ=1：除非客户到达和离开时间固定且匹配，否则无稳态。27一些定义N(t)系统在时刻t的规模Nq(t)队列在时刻t的规模Ns(t)时刻t正在接受服务的客户数量pn(t)P[N(t)=n]pn稳态pn(t)，即limt→∞pn(t)L系统平均规模Lq队列平均规模W客户在系统内平均耗时Wq客户在队列中平均耗时28Little等式(Little’slaw)Little等式（Little’sformula）系统规模=客户达到率×客户在系统中消耗时间“系统”可以是整个排队系统，也可以是一个队列对于队列，这个结果适用于排队模型，与客户到达模式和服务模式无关！单服务器G/G/1排队系统客户在系统时间=排队时间+服务时间正在接受服务的客户数同时，所以服务器繁忙的概率为pb=1-p0=λ/μ29单服务器，稳态下λ/μ不可能大于1。30多服务器G/G/c排队系统每台服务器繁忙的概率为pb=λ/cμ

共c个服务器，平均λ/μ个客户接受服务，平均每个服务器λ/cμ个客户，或者单位时间中λ/cμ服务器繁忙λ/μ很重要。定义ρ=λ/μ为一个排队系统的提交负载（offeredload）：服务器完成一个客户服务的时间平均到达的客户数量31G/G/c排队系统总结提交负载Little等式Little等式服务器繁忙概率接受服务的客户数量G/G/1系统为空的概率例：某快餐店在高峰时每小时到达40位客人，每个客人平均在柜台用5.5分钟点餐。至少需要设置多少个柜台？每小时到达40位客人，假设有c个柜台，则柜台繁忙概率

λ/cμ=40/c×(60/5.5)<1c>40×5.5/60，客人才不至于在柜台累积c至少为43233例

某公司安排接线员接听顾客电话。由于人手不够，顾客必须等待才能被接听。公司希望顾客平均等待时间为75秒，估计每分钟打进3个客户电话。问需要多少线路用于保持电话等待？λWq=Lq，Lq=3×75/60=3.75，需要4条线路34例

考虑一个M/G/1/K排队系统，其阻塞概率为pK=0.1，并且λ=μ=1，L=5。计算λeff，W，Wq，p0和ρeff。生灭过程（Birth-and-deathprocess）考虑一个群体（比如，海岛上的海鸟群），群体数量取决于两种事件，出生和死亡。当群体个数为n时，λn表示此时的出生率，即在一小段时间h，出生一个个体的概率为λnh+o(h)；μn表示此时的死亡率，即在一小段时间h，死亡一个个体的概率为μnh+o(h)。这个群体可以用一个生灭过程来描述。35定义：考虑一个连续参数的离散随机过程{X(t):t>0}，取值空间为{0,1,2,...}。如果X(t)=n，则称这个随机过程描述的系统在时间t处于状态En，n=0，1，2，...。如果出生速率{λn}和死亡速率{μn}满足以下条件，则称这个随机过程为生灭过程。状态转移只能EnEn+1，n=0，1，2，...。如果在时间t系统位于状态En，则在一小段时间[t,t+h)发生状态转移EnEn+1的概率是λnh+o(h)。如果在时间t系统位于状态En，则在一小段时间[t,t+h)发生状态转移EnEn-1的概率是μnh+o(h)。如果在时间t系统位于状态En，则在一小段时间[t,t+h)发生其它转移的概率o(h)。36令Pn(t)=P[X(t)=n]在时间t+h，系统仍然在状态En的概率Pn(t+h)，有四种情况在时间t系统位于状态En，[t,t+h)状态没有发生改变在时间t系统位于状态En-1，[t,t+h)发生一个出生事件在时间t系统位于状态En+1，[t,t+h)发生一个死亡事件在时间t系统位于上述状态以外的状态37情况1发生的概率情况2发生的概率情况3发生的概率情况4发生的概率综合4种情况38整理取h0对n≥1当n=0初始条件，t=0时，系统位于状态Ei，所有μn=0，称为纯生过程，“人口爆炸”如果纯生过程λn=λ，即为泊松过程所有λn=0，称为纯灭过程，“种群消亡”39稳态生灭过程当t∞，系统状态Pn(t)不随时间改变。称这种状态为稳态（Stationary或者steady-state）记，稳态下稳态下对任意一个状态，“进入该状态的概率=退出该状态的概率”40对状态0，对其它任意一个状态i，解线性方程组可得稳态生灭过程各状态概率当有无限个状态，生灭过程的稳态解为生灭过程有稳态接的必要和充分条件为41例一个单服务器排队系统，无等待位。假设客户到达是一个速率为λ的泊松过程，服务器服务时间服从指数分布，服务速率为μ，即单位时间服务1/μ个客户。求解：没有等待位，系统只有两个状态，“0”和“1”

根据生灭过程方程42

解微分方程

稳态，t∞。

直接求解稳态，用“流入=流出”计算稳态状态概率4344例

考虑一个单服务器的生灭过程系统中。系统只能够容纳3个客户，到达速率(λ0λ1λ2)=(3,2,1)，服务（死亡）速率为(μ1μ2μ3)=(1,2,2)。计算稳态下各状态概率，并计算有效到达速率和客户等待时间W求解生灭过程(p0,p1,p2,p4)=(0.117647,0.352941,0.352941,0.176471)例：在eMule网络上，文件被用户下载以后，该用户默认共享这个文件。考虑eMule网络上的一个文件，新的用户下载并共享这个文件可以视为一个速率为λ的泊松过程，；对每个共享源，由于各种原因（用户、系统、硬件），单位时间这个共享源不再共享这个文件的概率是θ。问这个文件有n个共享源的概率？n是任意非负整数。解答：这是一个生灭过程，

出生率，新共享源出现服从泊松分布，λi=λ

死亡率，某时刻有i个共享源时的死亡率为μi=iθ45当λ>iθ，共享源增多当λ<iθ，共享源减少进一步处理eMule网络中文件的共享源个数取决于文件的流行程度λ，以及用户的共享意愿θ46这是一个泊松分布马尔科夫过程随机过程{X(t),t∈T}满足如下条件，则称它是一个马尔科夫过程，给定时间点集合{ti}，t1<t2<t3<…，有系统将来的状态只和当前状态有关，和整个过去的历史无关如果集合X(t)的取值是离散的，则称为马尔科夫链47如果T是离散的，称为离散时间马尔科夫链，并记X(ti)为Xi。上式写为m步状态转移概率转移概率的矩阵形式48一步转移概率例：考虑一系列独立伯努力实验，每次实验的成功概率为p。用随机变量Xi表示包含第i次实验的连续实验成功次数。例如，如果前五次实验结果SFSSF，X0=1，X1=0，X2=1，X3=2，X4=0。试分析随机过程{Xi}。{Xi}是一个马尔科夫过程：转移矩阵49M步状态转移概率根据全概率公式

转移概率Chapman-Kolmogorov（CK）公式

由英国数学家S.Chapman和苏联数学家

A.Kolmogorov分别独立得到。矩阵形式50m步转移概率矩阵是1步转移概率矩阵的m次方例：一个通信装置接受信号0或者1，并且随机地把0变成1，1变成0发送出去。信号转换的概率为0.25。如果4个这样的装置串联，输入信号0，最后发送仍然为信号0的概率是多少？51马尔科夫链上的状态定义：令i与j表示马尔科夫链的状态

相反定义状态之间的连通关系具有自反性、对称性和传递性自反性：对称性：传递性：52由于连通的三种性质，连通可以被视为一种等价关系，所有连通的状态集合可以被视为一个等价类定义：一个马尔科夫链中如果所有状态都属于同一等价类，则这个马尔科夫链被称为不可约分的（Irreducible）。53例马尔科夫链的转移矩阵如下状态1：常返态（从状态5进入后，不能离开）状态2、5：暂态（一旦进入其它状态，永远不能返回）状态0、3、4：常返态（从状态2进入后，不能离开），它们构成一个等价类54令表示从状态i出发，经过n步转移回到i的概率

并且令表示从状态i出发，在有限时间内回到状态i的概率定义：状态i被称为常返（recurrence）的，当且仅当

当状态i为常返态，令表示回归时间期望当mi=∞，状态i被称为零常返（nullrecurrence）当mi<∞，状态i被称为正常返（positiverecurrence）55定义：如果从状态i出发，有大于0的概率马尔科夫链永远不能够回到i，则状态i被称为暂态。相应有定理：如果i↔j且i是常返态，则j也是常返态。56定义：一个状态被称为吸收态，当且仅当pii=1。吸收态是正常返态，例如上例中状态1定义：状态i的周期被定义为所有满足的n的最大公约数。如果一个状态的周期为1，则这个状态被称为非周期的。定理：如果如果i↔j，则i与j有相同的周期。这个定理说明周期成为一种等价性质。一个等价类的所有状态有相同周期。对一个不可约分的马尔科夫链，如果包含一个非周期状态，则所有状态是非周期的，这个马尔科夫链被称为非周期的。定理：令P为一个不可约分的、非周期的有限状态马尔科夫链的转移矩阵，则存在N，当n≥N，P(n)上所有元素非零。57稳态马尔科夫链定义第n步转移后的马尔科夫链{Xn}状态分布