《排队论基础》PPT课件.ppt

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