排队论基础专题宣讲.ppt

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状态 则：??Δt—Δt内到达1人概率 ??Δt—Δt内离去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和的特征函数 Network Laboratory * 排队论基础 §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）服务时间 的概率密度 以上结果亦适用于服务过程， 可得 综上所述，在以上