§1排队论基础讲解.ppt

第二章 网内业务分析;§1 排队论基础 常见现象： 顾客+服务→排队系统 矛盾统一 ; 广义化： 通信中：呼叫——线路 信息包——分组交换机 移动体——服务区 计算机：总线指令——CPU处理 数据流——存储器 其它：敌机——防空设施 客机——跑道 ;复杂性：在于随机性——到达与离去（服务率）均不确定——工作于随机状态 ? 资源少——顾客排队长——服务质量下降 资源多——服务闲置——资源浪费 ;目标：为顾客提供满意服务同时提高资 源利用率。（与统计参数和工作方 式有关） 在通信网的业务分析和性能计算中，排队论是不可缺少的 ;2.1.1、基本概念 ;;; 此三量可已知或可测出，但描述排队系统，此三要素不充分。 主要取决于 ti 和τi的统计特性（分布）和排队规则。 ;2、统计特性（分布）和排队规则。 常见排队系统的假设 平稳性： [a，a+t]内到达k个顾客（或离去）的概率与a无关，只与t有关。 无后效性 顾客到达时刻相互独立 不相交区间内到达顾客数相互独立 系统顾客数具有马氏性 稀疏性： Δt内到达2个或2个以上顾客概率为0 有限区间内的k为有限，或;(1)T内有k个顾客到达的概率 在以上假设下： T内到达顾客数为k ;据无后效性, 独立 据二项分布, N个贝努利分布 T内有k个到达的概率: ;（2）到达间隔t的概率密度a（t） 到达间隔t——连续变量 把t分N份，到达间隔为t的概率： ;（3）服务时间 的概率密度;综上所述，在以上三个假设下？？？？？？：;（4）运行方式及规则规定： 排队系统的运行性能不仅与上述的统计分布有关，还与系统预先规定的工作方式有关。 包括服务规则和排队规则： ;按服务规则分： 1）先到先服务：常见情况 2）后到先服务：不常见情况 3）优先制服务：顾客分优先级 ;按排队规则分： 1）等待型：不拒绝系统。若窗口不空，就依次排队等待，直到被服务完毕后离去。 2）截止型：分为损失制、拒绝系统 系统已有n个顾客等待，顾客到来时，就被拒绝。分为如下2种 即时拒绝：如窗口数为m,m=n,满，则顾客到达后立即被拒绝，被拒绝排队等待 （电话网） 延迟拒绝：mn,允许等待一定数量，超n，再拒绝 (带缓冲存储的数据通信）;;(6)稳定性指标：对于不拒绝系统，当到达率λ与服务率?之比（称为排队系统强度 ）大于窗口数m时，平均顾客到达数将大于平均顾客离去数，顾客的队将越来越长，平均等待时间将趋于无限大，系统不稳定。小于窗口数m时，系统是稳定的(? m)。对于截止型系统，因为队长被限制，即使排队强度大于m，系统仍然可以稳定工作。 ;;;;到达?离去 s=w+? 对任何排队系统，有 ;;?=λ/?;不拒绝系统：; 仍然稳定 ;排队系统表示符号： A/B/m(N,n);常见分布：;M—指数分布;将讨论:;解法： ;设平均到达率为?，平均服务率为?。取队长为状态变量建立系统的差微分方程。1、状态图与状态方程 ;;t+Δt时刻处于k状态（概率 ），由下述情况形成： t为k-1态，Δt内到达1人，无人离去，概率: t为k+1态，Δt内离去1人，无到达： t为k态，Δt内到达1人，离去1人: t为k态，Δt内无到达，无离去: ;;;;上式，已由?，?表示转移，得状态转移图： ;2、稳态解 ;;求p0: 用归一化条件 ;平均队长 ;k的方差 ;;;等待时间w ;;因为k为离散变量,故w的特征函数: ;w的密度: ;至此,得M/M/1结论如下: ;; 所以,M/M/1主要矛盾集中在?的选取 服务质量与系统效率之间的矛盾 解决目标:保证稳定运行条件下提高效率 M/M/1系统的主要缺点是服务质量与系统效率的的矛盾。解决的办法有两种 措施: （1） 增加窗口数（增大效率，但投资加大） （2）截止排队长度，即采用拒绝型系统（降低系统质量（顾客被拒绝），换取效率和稳定性） 将上述两个方法结合为 截止多窗口排队系统 ;三、M/M/m(n)问题 ;M/M/m(n)排队模型 ; 令系统内顾客数k为状态变量，此时