§1排队论基础PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,第二章 网内业务分析,1,2025/4/29 周二,1,排队论基础,常见现象：,顾客,+,服务排队系统 矛盾统一,2,2025/4/29 周二,广义化：,通信中：呼叫,线路,信息包,分组交换机,移动体,服务区,计算机：总线指令,CPU,处理,数据流,存储器,其它：敌机,防空设施,客机,跑道,3,2025/4/29 周二,复杂性：在于随机性,到达与离去（服务率）均不确定,工作于随机状态,资源少,顾客排队长,服务质量下降,资源多,服务闲置,资源浪费,4,2025/4/29 周二,目标：为顾客提供满意服务同时提高资,源利用率。（与统计参数和工作方,式有关）,在通信网的业务分析和性能计算中，排队论是不可缺少的,5,2025/4/29 周二,2.1.1,、基本概念,m-,窗口数，表示资源的量。可同时向顾客提供服务的设施数。（单窗口排队系统,m=1,；多窗口排队系统,m1,）,-,顾客到达率（平均）,-,系统服务率（平均）,1.,排队系统三要素,:m,，,，,6,2025/4/29 周二,平均到达时间,:,平均到达率,单位时间到达顾客数,或,(n(T),T,内到达数）,负荷轻,-,顾客到达率（平均）,7,2025/4/29 周二,同理,平均服务时间,：系统服务率（平均）,8,2025/4/29 周二,此三量可已知或可测出，但描述排队系统，此三要素不充分。,主要取决于,t,i,和,i,的统计特性（分布）和排队规则。,9,2025/4/29 周二,2,、,统计特性（分布）和排队规则,。,常见排队系统的假设,平稳性：,a,，,a+t,内到达,k,个顾客（或离去）的概率与,a,无关，只与,t,有关。,无后效性,顾客到达时刻相互独立,不相交区间内到达顾客数相互独立,系统顾客数具有马氏性,稀疏性：,t,内到达,2,个或,2,个以上顾客概率为,0,有限区间内的,k,为有限，或,10,2025/4/29 周二,(1)T,内有,k,个顾客到达的概率,在以上假设下：,T,内到达顾客数为,k,内有,1,顾客到达概率,内无顾客到达概率,1-,有,2,个到达概率,11,2025/4/29 周二,据无后效性,独立,据二项分布,N,个贝努利分布,T,内有,k,个到达的概率,:,12,2025/4/29 周二,（,2,）到达间隔,t,的概率密度,a,（,t,）,到达间隔,t,连续变量,把,t,分,N,份，到达间隔为,t,的概率：,（,N,个,内无到达，第,N+1,个必到达）,若,t,的概率密度,a,（,t,）存在，则有：,指数分布,13,2025/4/29 周二,（,3,）服务时间 的概率密度,以上结果亦适用于服务过程，,可得,14,2025/4/29 周二,综上所述，在以上三个假设下？：,顾客到达和离去均为泊松流，均值,，二阶矩,(+1),相邻事件发生的间隔负指数分布，均值,1/,，二阶矩,1/,2,具有马尔可夫性，称,M,分布称最简单流,15,2025/4/29 周二,（,4,）运行方式及规则规定：,排队系统的运行性能不仅与上述的统计分布有关，还与系统预先规定的工作方式有关。,包括服务规则和排队规则：,16,2025/4/29 周二,按服务规则分：,1,）先到先服务：常见情况,2,）后到先服务：不常见情况,3,）优先制服务：顾客分优先级,17,2025/4/29 周二,按排队规则分：,1,）等待型：不拒绝系统。若窗口不空，就依次排队等待，直到被服务完毕后离去。,2,）截止型：分为损失制、拒绝系统,系统已有,n,个顾客等待，顾客到来时，就被拒绝。分为如下,2,种,即时拒绝：如窗口数为,m,m=n,满，则顾客到达后立即被拒绝，被拒绝排队等待（电话网）,延迟拒绝：,mn,允许等待一定数量，超,n,，再拒绝,(,带缓冲存储的数据通信）,18,2025/4/29 周二,(1),队长,k,：某时刻观察系统内滞留的顾客数。,(2),等待时间,w:,顾客从到达至开始被服务这段时间。,(3),服务时间,：一个顾客被服务的时间,(4),系统时间,s,，或称系统停留时间：顾客从到达至离开的这段时间。,S=w+,(5),系统效率：平均窗口占用率,目标参量：,（分析排队系统时的主要求解指标,),19,2025/4/29 周二,(6),稳定性指标：,对于不拒绝系统，当到达率,与服务率,之比（称为排队系统强度 ）大于窗口数,m,时，平均顾客到达数将大于平均顾客离去数，顾客的队将越来越长，平均等待时间将趋于无限大，系统不稳定。小于窗口数,m,时，系统是稳定的,(,m),。对于截止型系统，因为队长被限制，即使排队强度大于,m,，系统仍然可以稳定工作。,=/,20,2025/4/29 周二,队长,k,排队长度,t,瞬间系统内的顾客数（含在窗口的）,k,离散随机变量,三种观察：,d,k,顾客到达时观察队长为,k,的概率（不包括刚到达的顾客）,r,k,顾客服务完毕离去时观察队长为,k,的概率,（不包括正在离去的顾客）。,（以上为有条件抽样）,p,k,（服务员）随机观察队长为,k,的概率,在最简系统中，,p,k,=r,k,=d,k,平均队长，又称系统数,21,2025/4/29 周二,等待时间,w,从到达,开始服务的时间，是连续随机变量，其统计平均为：,平均等待时间（网络中等待时延的主要部分）,其它时延，如传输时延和处理时延较小,22,2025/4/29 周二,服务时间,开始接受服务,服务完毕离去,平均服务时间,23,2025/4/29 周二,到达,离去,s=w+,对任何排队系统，有,系统时间,s,，或称系统停留时间,24,2025/4/29 周二,系统效率,平均窗口占用率,共,m,个窗口，某时刻如有,r,个被占用，则,25,2025/4/29 周二,=/,稳定性指标,26,2025/4/29 周二,不拒绝系统：,27,2025/4/29 周二,仍然稳定,截止型系统：,28,2025/4/29 周二,排队系统表示符号：,A/B/m(N,n),A,到达规律，分布,a(t),（到达时间间隔）,B,服务规律，分布,b(,),（服务时间间隔）,m,窗口数,N,顾客源，潜在顾客数，省略为,n,截止队长，省略为,，不拒绝,29,2025/4/29 周二,常见分布：,30,2025/4/29 周二,M,指数分布,31,2025/4/29 周二,将讨论,:,基本：,M/M/1 M/M/m(n),中级：,M/G/1 G/M/1,高级：,G/G/1,32,2025/4/29 周二,解法：,确定状态变量，如,k,画状态转移图,列状态转移方程,求解目标参量,33,2025/4/29 周二,设平均到达率为,，平均服务率为。取队长为状态变量建立系统的差微分方程。,1,、状态图与状态方程,t,时刻，系统内有,k,个顾客的概率（,k=0,1,2,）,二、,M/M/1,问题,34,2025/4/29 周二,t,时刻，,k,状态,则：,t,t,内到达,1,人概率,t,t,内离去,1,人概率,35,2025/4/29 周二,t+t,时刻处于,k,状态（概率 ），由下述情况形成：,t,为,k-1,态，,t,内到达,1,人，无人离去，,概率,:,t,为,k+1,态，,t,内离去,1,人，无到达：,t,为,k,态，,t,内到达,1,人，离去,1,人,:,t,为,k,态，,t,内无到达，无离去,:,36,2025/4/29 周二,37,2025/4/29 周二,即柯尔莫哥洛夫方程。,38,2025/4/29 周二,k=0,需重写,:,原,1,人,去,1,人,tp,1,(t),原,0,人,无人到,(1-,t)p,0,(t),p,0,(t+,t)=,tp,1,(t)+,(1-,t,),p,0,(t),得,:,至此,，,得,M/M/1,完整状态方程,:,39,2025/4/29 周二,上式，已由,，,表示转移，得状态转移图：,40,2025/4/29 周二,2,、稳态解,物理意义：,到达与离去平衡，,p,k,(t),与,t,无关,数学描述：,41,2025/4/29 周二,42,2025/4/29 周二,求,p,0,:,用归一化条件,p,0,系统无人概率（空闲率）,1-p0=,系统有人概率（忙概率）,忙,太大,不稳,得通解：,43,2025/4/29 周二,平均队长,44,2025/4/29 周二,k,的方差,45,2025/4/29 周二,46,2025/4/29 周二,47,2025/4/29 周二,等待时间,w,若系统已有,k,人,即处于,K,状态,来一人的等待时间,w,是为前面,k,个人的服务时间总和 即,:,因为,i,相互独立，则,w,k,是,k,个独立变量之和，所以，,w,k,的特征函数为,k,个,i,的特征函数之积。,48,2025/4/29 周二,i,的特征函数,:(b(),概率的付氏变换,),k,个,i,和的特征函数,49,2025/4/29 周二,因为,k,为离散变量,故,w,的特征函数,:,50,2025/4/29 周二,w,的密度,:,平均等待时间,:,w,的方差,:,系统时间,(,平均停留,),反验,Little,公式,:,51,2025/4/29 周二,至此,得,M/M/1,结论如下,:,52,2025/4/29 周二,53,2025/4/29 周二,所以,M/M/1,主要矛盾集中在,的选取,服务质量与系统效率之间的矛盾,解决目标,:,保证稳定运行条件下提高效率,M/M/1,系统的主要缺点是服务质量与系统效率的的矛盾。解决的办法有两种,措施,:,（,1,）增加窗口数（增大效率，但投资加大）,（,2,）截止排队长度，即采用拒绝型系统（降低系统质量（顾客被拒绝），换取效率和稳定性）,将上述两个方法结合为,截止多窗口排队系统,54,2025/4/29 周二,三、,M/M/m(n),问题,常见多窗口排队方式有两种：,混合排队（,M/M/m(n),分别排队,(,为,M,个独立的,M/M/1),55,2025/4/29 周二,M/M/m(n),排队模型,窗口数为,m,截止队长为,n.,每个窗口的服务率均为,，,服务时间和到达间隔均为指数分布。即：,窗口服务时间,总到达率,令,:,56,2025/4/29 周二,令系统内顾客数,k,为状态变量，此时，只有,n+1,种状态。,K=m,时，有,k,个窗口在被占用，则服务率为,k,当,mkn,时,p,k,=0,永稳定,以拒绝换稳定,59,2025/4/29 周二,M/M/m(n),的平均等待时间,只算,情况即可,k=m,等,1,人,k=m+1,等,2,对,k,等,k-m+1,人,60,2025/4/29 周二,所以,:,61,2025/4/29 周二,M/M/m(n),的几种特例,62,2025/4/29 周二,a),当,n=m.,为多窗口即时拒绝系统,63,2025/4/29 周二,b),当,n,为多窗口非拒绝系统,数学的,M/M/m,问题,拒绝概率,p,c,=0,平均等待的顾客数,:,64,2025/4/29 周二,c),当,m=1,为单窗口。,M/M/1(n),65,2025/4/29 周二,d),当,m=1,n,为,M/M/1,66,2025/4/29 周二,M/M/m(n),系统效率,:,效率即指平均窗口占用率,(,统计平均,),窗口不满 占用率,k/m,窗口满,(k=m),占用率,=1,67,2025/4/29 周二,当,n,不拒绝多窗口,单窗口,当,n=m,即时拒绝,当,m=1,M/M/1(n),不拒绝系统只能取,当,时,系统不稳定,68,2025/4/29 周二,拒绝型系统可以取,仍能稳定工作,以拒绝概率,(,呼损,),为代价,一定,增加截止队长,(n),可提高效率,但等待时间亦长,延迟换效率,所以，若延迟指标允许，用非即时拒绝型是合理的,69,2025/4/29 周二,