排队论基础.ppt

第二章网内业务分析,1排队论基础常见现象：顾客+服务排队系统矛盾统一,广义化：通信中：呼叫线路信息包分组交换机移动体服务区计算机：总线指令CPU处理数据流存储器其它：敌机防空设施客机跑道,复杂性：在于随机性到达与离去（服务率）均不确定工作于随机状态资源少顾客排队长服务质量下降资源多服务闲置资源浪费,目标：为顾客提供满意服务同时提高资源利用率。（与统计参数和工作方式有关）在通信网的业务分析和性能计算中，排队论是不可缺少的,2.1.1、基本概念,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/1M/M/m(n)中级：M/G/1G/M/1高级：G/G/1,解法：,确定状态变量，如k画状态转移图列状态转移方程求解目标参量,设平均到达率为，平均服务率为。取队长为状态变量建立系统的差微分方程。1、状态图与状态方程,t时刻，系统内有k个顾客的概率（k=0,1,2,）,二、M/M/1问题,t时刻，k状态则：tt内到达1人概率tt内离去1人概率,2019/12/14,36,可编辑,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,当m=m)占用率=1,当n,不