通信网理论基础.4排队论[1].ppt

2004 8 17 第1 103页 第4章排队论及网内通信业务分析 第4章排队论及网内通信业务分析 2004 8 17 第2 103页 第4章排队论及网内通信业务分析 4 1排队论基础4 2M M 1排队4 3M M m n 排队4 4排队论在通信网中的应用4 5提高网效率的措施4 6多址通信 2004 8 17 第3 103页 4 1排队论基础 4 1 1基本概念4 1 2概率模型与最简单流4 1 3生灭过程4 1 4排队系统的主要性能指标 4排队论及网内通信业务分析 2004 8 17 第4 103页 4 1 1基本概念 排队现象顾客 要求服务的一方 服务 提供服务的一方 排队系统广义排队现象通信 呼叫 线路信息包 分组交换机其它 敌机 防空设施客机 跑道复杂性随机性 到达与离去不确定 工作于随机状态资源少 顾客排队长 服务质量下降资源多 服务闲置 资源浪费目标顾客提供满意服务 提高资源利用率 4 1排队论基础 2004 8 17 第5 103页 4 1 1基本概念 基本概念排队论又称随机服务系统 主要解决与随机到来 排队服务现象有关的应用问题 排队论的创始人Erlang正是为了解决电话交换机容量的设计问题而提出排队论 排队论主要研究三个方面内容 1 形态问题 即研究各种排队系统的规律性 这包括队长分布 等待时间分布 忙闲期分布等 同时又分稳态和瞬态两种情形 2 最优化问题 又分静态最优和稳态最右 前者指最优设计 后者指现在排队系统的最优运用 3 排队系统的统计推断 即判断一个给定的排队系统符合那种类型 以便根据排队理论进行分析研究 4 1排队论基础 2004 8 17 第6 103页 4 1 1基本概念 输入过程 是对顾客到来的特征进行描述 包括顾客总体数目 到来方式 单个或成批 到来间隔的规律等 服务规则 包括先到先服务 FIFO 后到先服务 LIFO 随机服务 有优先权服务等 服务机构 包括服务员数目 服务时间特征等 排队系统在运行中包括三个过程 顾客输入过程 顾客到达的规律排队过程 与排队规则有关顾客接受服务然后离去过程 取决于服务机构的效率 一 排队系统的组成 4 1排队论基础 2004 8 17 第7 103页 4 1 1基本概念 1 输入过程 顾客总体数 可以无限 可以有限顾客到来方式 顾客到达的规律顾客流的概率分布 顾客到达的时间间隔分布 顾客流 到达排队系统的顾客序列 4 1排队论基础 一 排队系统的组成 2004 8 17 第8 103页 4 1 1基本概念 2 排队规则 损失制 拒绝方式 拒绝系统 截至型 顾客到达系统时 若系统已经有n个顾客 允许排队队长 且m个窗口 窗口数 均被占满 则顾客遭到拒绝 即不容许排队等候 4 1排队论基础 一 排队系统的组成 排队系统类型 非损失制 非拒绝方式 非拒绝系统 当顾客到达系统时 如所有窗口均被占有 顾客就加入排队行列等待服务 即允许顾客排队等待 且对队长没有限制 2004 8 17 第9 103页 4 1 1基本概念 即时拒绝系统 立接制 n m 排队队长 窗口数 顾客到达后或立即被拒绝或立即被服务延时拒绝系统 混合制 m n 此时容许一定数量的顾客排队等候 当顾客超过排队队长时再被拒绝而离去 延时拒绝系统和非拒绝系统又称为等待制系统 允许顾客等待 2 排队规则 4 1排队论基础 一 排队系统的组成 拒绝系统类型 2004 8 18 第10 103页 4 1 1基本概念 服务规则 工作方式 先到先服务 按照顾客到达的先后 顺序服务后到先服务 优先制服务 按照预先设置的优先级服务随机服务 窗口空闲时随机指定顾客接受服务 3 服务规则 4 1排队论基础 一 排队系统的组成 2004 8 18 第11 103页 4 1 1基本概念 当m 1时称为单窗口排队系统 当m 1时 称为多窗口排队系统 4 服务机构 4 1排队论基础 一 排队系统的组成 窗口 或服务员 数量 2004 8 18 第12 103页 4 1 1基本概念 服务方式 某一时刻接受服务的顾客数 按照服务方式分为 串列服务方式 单个顾客接受服务 m个窗口服务内容不同 每个顾客要依次经过这m个窗口接受服务 如零件经过m道工序 并列服务方式 成批顾客同时接受服务 m个窗口服务内容相同 系统一次可以同时服务m个顾客 4 服务机构 4 1排队论基础 一 排队系统的组成 服务方式及排队方式 2004 8 21 第13 103页 4 1 1基本概念 混合排队 顾客排成一队分别排队 顾客排成m个队列 4 服务机构 4 1排队论基础 一 排队系统的组成 排队方式 2004 8 21 第14 103页 4 1 1基本概念 分别排队 多窗口并列 4 服务机构 4 1排队论基础 一 排队系统的组成 排队方式 2004 8 21 第15 103页 4 1 1基本概念 混合排队 多窗口并列 4 服务机构 4 1排队论基础 一 排队系统的组成 排队方式 2004 8 21 第16 103页 4 1 1基本概念 4 服务机构 4 1排队论基础 一 排队系统的组成 排队方式 2004 8 21 第17 103页 4 1 1基本概念 两次混合排队 多窗口并 串列 4 服务机构 4 1排队论基础 一 排队系统的组成 排队方式 2004 8 21 第18 103页 4 1 1基本概念 服务时间是随机变量 一般有定长分布 指数分布 爱尔兰分布等 4 服务机构 4 1排队论基础 一 排队系统的组成 服务时间分布 2004 8 21 第19 103页 4 1 1基本概念 4 1排队论基础 二排队系统的3个基本参数 2004 8 21 第20 103页 4 1 1基本概念 4 1排队论基础 二排队系统的3个基本参数 2004 8 21 第21 103页 4 1 1基本概念 二排队系统的3个基本参数 4 1排队论基础 2004 8 21 第22 103页 4 1 1基本概念 二排队系统的3个基本参数 4 1排队论基础 2004 8 21 第23 103页 4 1 1基本概念 二排队系统的3个基本参数 4 1排队论基础 2004 8 21 第24 103页 4 1 1基本概念 二排队系统的3个基本参数 4 1排队论基础 排队强度 稳定性参数 2004 8 21 第25 103页 4 1 1基本概念 三 排队系统分类的表示方法 4 1排队论基础 2004 8 21 第26 103页 4 1 1基本概念 输入过程的时间分布 服务时间分布和窗口数量进行分类 4 1排队论基础 肯特尔表示方法 三 排队系统分类的表示方法 2004 8 21 第27 103页 4 1 1基本概念 4 1排队论基础 常见分布 三 排队系统分类的表示方法 2004 8 21 第28 103页 4 1 1基本概念 4 1排队论基础 肯特尔分类法例子 三 排队系统分类的表示方法 2004 8 21 第29 103页 4 1 1基本概念 4 1排队论基础 四 排队系统研究的内容与目的 2004 8 21 第30 103页 4 1 1基本概念 四排队系统研究的内容与目的 1 研究内容 队长k 顾客排队等待服务队列长短 包括正在接受服务的顾客数 两个指标 平均队长 队长概率分布等待时间和逗留时间分布 等待时间 到达排队系统的时刻始 开始接受服务的时刻止 逗留时间 到达排队系统的时刻始 离开系统的时刻止 即等待时间 服务时间忙期和闲期分布忙期 窗口连续服务时间 有顾客的持续时间 闲期 窗口连续保持空闲的时间 无顾客的持续时间 4 1排队论基础 2004 8 21 第31 103页 4 1 1基本概念 忙期 四排队系统研究的内容与目的 1 研究内容 4 1排队论基础 2004 8 21 第32 103页 4 1 1基本概念 2 排队系统的优化问题 上述个中参数的优化 四排队系统研究的内容与目的 4 1排队论基础 2004 8 21 第33 103页 4 1 2概率模型和最简单流 4 1 2概率模型和最简单流 4 1排队论基础 2004 8 21 第34 103页 4 1 2概率模型和最简单流 一 排队系统常用概率模型 4 1排队论基础 2004 8 17 第35 103页 4 1 2概率模型和最简单流 1 泊松分布 2 指数分布 4 1排队论基础 一排队系统常用概率模型 2004 8 17 第36 103页 4 1 2概率模型和最简单流 2 指数分布 4 1排队论基础 一排队系统常用概率模型 2004 8 21 第37 103页 4 1 2概率模型和最简单流 1 系统状态 一个系统中的顾客数 含正在接受服务的顾客 4 1排队论基础 二常用概念 系统状态的含义 2004 8 21 第38 103页 4 1 2概率模型和最简单流 2 N t 在时刻t排队系统中的顾客数 即系统在时刻t的瞬时状态 4 1排队论基础 二常用概念 2004 8 21 第39 103页 4 1 2概率模型和最简单流 在时刻t系统恰好有k个顾客的概率 4 1排队论基础 二常用概念 2004 8 21 第40 103页 4 1 2概率模型和最简单流 在时刻t系统恰好有k个顾客的概率 系统中有k个顾客时 新顾客的到达率 单位时间内新顾客的到达数 4 1排队论基础 二常用概念 2004 8 21 第41 103页 4 1 2概率模型和最简单流 4 1排队论基础 二常用概念 系统中有k个顾客时 系统的平均服务率 单位时间内服务完毕离开系统的顾客数 2004 8 21 第42 103页 4 1 2概率模型和最简单流 4 1排队论基础 二常用概念 系统中有k个顾客时 系统的平均服务率 单位时间内服务完毕离开系统的顾客数 6 稳定状态 2004 8 21 第43 103页 4 1 2概率模型和最简单流 一最简单流 4 1排队论基础 2004 8 21 第44 103页 4 1 2概率模型和最简单流 4 1排队论基础 三最简单流 1最简单流的定义 2004 8 22 第45 103页 4 1 2概率模型和最简单流 4 1排队论基础 三最简单流 2最简单流的概率分布 2004 8 22 第46 103页 4 1 2概率模型和最简单流 4 1排队论基础 三最简单流 2最简单流的概率分布 证明 2004 8 17 第47 103页 4 1 2概率模型和最简单流 4 1排队论基础 三最简单流 2最简单流的概率分布 证明 2004 8 22 第48 103页 4 1 2概率模型和最简单流 指数分布 4 1排队论基础 三最简单流 2最简单流的概率分布 特例 2004 8 22 第49 103页 4 1 2概率模型和最简单流 4 1排队论基础 三最简单流 2最简单流的概率分布 时间间隔t内有k个以上顾客到达的概率 2004 8 17 第50 103页 4 1 2概率模型和最简单流 4 1排队论基础 三最简单流 2最简单流的概率分布 均值 2004 8 17 第51 103页 4 1 2概率模型和最简单流 4 1排队论基础 三最简单流 2最简单流的概率分布 方差 2004 8 22 第52 103页 4 1 2概率模型和最简单流 3顾客到达的时间间隔分布 4 1排队论基础 三最简单流 时间间隔T的分布函数 两次相邻呼叫 顾客 时间间隔大于t的概率 时间t内没有呼叫 顾客 的概率 2004 8 22 第53 103页 4 1 2概率模型和最简单流 3顾客到达的时间间隔分布 4 1排队论基础 三最简单流 时间间隔T的分布函数 2004 8 22 第54 103页 4 1 2概率模型和最简单流 3顾客到达的时间间隔分布 4 1排队论基础 三最简单流 时间间隔T的概率密度函数 2004 8 22 第55 103页 4 1 2概率模型和最简单流 3顾客到达的时间间隔分布 4 1排队论基础 三最简单流 时间间隔T的数学期望 均值 2004 8 22 第56 103页 4 1 2概率模型和最简单流 服务时间 占用时间 一个顾客接受服务时占用一个窗口的时间 服务结束间隔时间服务过程 即为顾客离去的过程 前1个顾客服务完毕离开窗口 后1个顾客立即得到服务 然后离去 两者的间隔时间即为服务时间 若顾客的离去过程满足最简单流条件 则离去过程 即服务过程 亦为泊松过程 离去时间间隔 服务时间间隔 为指数分布 4服务时间分布 4 1排队论基础 三最简单流 基本概念 2004 8 22 第57 103页 4 1 2概率模型和最简单流 若顾客的离去过程满足最简单流条件 则离去过程 即服务过程 亦为泊松过程 离去时间间隔 服务时间间隔 为指数分布 4服务时间分布 4 1排队论基础 三最简单流 顾客离去过程的模型 2004 8 22 第58 103页 4 1 2概率模型和最简单流 4服务时间分布 4 1排队论基础 三最简单流 服务时间的概率密度函数 2004 8 22 第59 103页 4 1 2概率模型和最简单流 4服务时间分布 4 1排队论基础 三最简单流 完成服务的平均时间 2004 8 22 第60 103页 4 1 2概率模型和最简单流 设电话呼叫为30次 小时的泊松过程 求5分钟间隔内 1 不呼叫的概率 2 呼叫3次的概率 5例题 4 1排队论基础 三最简单流 2004 8 22 第61 103页 4 1 2概率模型和最简单流 5例题 4 1排队论基础 三最简单流 解 2004 8 22 第62 103页 4 1 3生灭过程 4 1排队论基础 4 1 3生灭过程 2004 8 22 第63 103页 4 1 3生灭过程 4 1排队论基础 一生灭过程的概念 2004 8 22 第64 103页 4 1 3生灭过程 4 1排队论基础 一生灭过程的概念 1定义 2004 8 22 第65 103页 4 1 3生灭过程 4 1排队论基础 一生灭过程的概念 1定义 2004 8 22 第66 103页 4 1 3生灭过程 4 1排队论基础 一生灭过程的概念 2特殊情况 有限生灭过程 2004 8 22 第67 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 2004 8 22 第68 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 问题 2004 8 22 第69 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 解 2004 8 22 第70 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第1种情况 2004 8 22 第71 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 没有顾客到达 没有顾客离开的概率 2004 8 22 第72 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 1个顾客到达 1个顾客离开的概率 2004 8 22 第73 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第1种情况的概率 2004 8 22 第74 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第1种情况的概率 2004 8 22 第75 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第2种情况 2004 8 22 第76 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第2种情况的概率 2004 8 22 第77 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第2种情况的概率 2004 8 22 第78 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第3种情况 2004 8 22 第79 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第3种情况的概率 2004 8 22 第80 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第4种情况 1个顾客离去而无顾客到达 2004 8 17 第81 103页 4 1 3生灭过程 1个顾客离去而无顾客到达 4 1排队论基础 二系统状态 第4种情况的概率 2004 8 23 第82 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第5种情况的概率 2004 8 23 第83 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 第5种情况的概率 2004 8 23 第84 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 问题回顾 2004 8 23 第85 103页 4 1 3生灭过程 思路 4 1排队论基础 二系统状态 问题回顾 2004 8 23 第86 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 2004 8 23 第87 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 特殊情况 2004 8 25 第88 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 回顾结果 2004 8 25 第89 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 回顾结果 2004 8 25 第90 103页 4 1 3生灭过程 4 1排队论基础 二系统状态 回顾结果 2004 8 25 第91 103页 4 1 3生灭过程 19 2004 8 25 第92 103页 4 1 3生灭过程 20 结果 微分方程组 2004 8 25 第93 103页 4 1 3生灭过程 21 特例 系统稳定状态方程 系统方程 系统处于稳定状态的条件 带入微分方程组 2004 8 17 第94 103页 4 1 3生灭过程 22 得到 系统稳定状态方程 系统方程 2004 8 25 第95 103页 4 1 3生灭过程 23 生灭过程的状态转移图 2004 8 25 第96 103页 4 1 3生灭过程 24 2004 8 25 第97 103页 4 1 3生灭过程 25 2004 8 26 第98 103页 4 1 3生灭过程 26 实际系统中 但时间很大时 系统很快趋于统计平衡 2004 8 25 第99 103页 4 1 4排队系统的重要性能指标 主要评价指标 排队长度等待时间服务时间系统时间系统效率 2004 8 17 第100 103页 4 1 4排队长度 排队长度 简称队长 某时刻观察系统内滞留的顾客数 包括正被服务的顾客 非负的离散型随机变量 2004 8 17 第101 103页 4 1 4等待时间 等待时间 顾客到达至开始被服务的时间 连续型随机变量 平均等待时间 等待时间的统计平均值平均等待时间是信息在通信网内的平均时延的主要组成部分 2004 8 25 第102 103页 4 1 4服务时间 服务时间 顾客被服务的时间 顾客从开始被服务起到离开系统的时间间隔 连续型随机变量 平均服务时间 服务时间的统计平均值 2004 8 17 第103 103页 4 1 4系统时间 系统时间 系统逗留时间 顾客到达至离开的时间间隔 连续型随机变量 平均系统逗留时间系统时间的统计平均值 2004 8 25 第104 103页 4 1 4列德尔公式 2004 8 25 第105 103页 4 1 4系统效率 系统效率 可定义为窗口平均占有率 窗口数与某时刻窗口被占用的数量比值 2004 8 25 第106 103页 4 2M M 1排队系统 1 排队系统分类的表示方法 2004 8 25 第107 103页 4 2M M 1排队系统 2 M M 1排队系统模型 2004 8 25 第108 103页 4 2M M 1排队系统 3 4 2 1M M 1排队系统4 2 2M M 1排队系统的各项性能指标4 2 3M M 1排队系统的应用 主要内容 2004 8 17 第109 103页 4 2 1M M 1排队系统 1 基本问题 一 求解思路 2004 8 28 第110 103页 4 2 1M M 1排队系统 2 二 求解过程 2004 8 17 第111 103页 4 2 1M M 1排队系统 3 系统状态转移示意图 2004 8 28 第112 103页 4 2 1M M 1排队系统 4 计算3种情况的概率 2004 8 28 第113 103页 4 2 1M M 1排队系统 5 2004 8 28 第114 103页 4 2 1M M 1排队系统 6 2004 8 28 第115 103页 4 2 1M M 1排队系统 7 2004 8 28 第116 103页 4 2 1M M 1排队系统 8 2004 8 28 第117 103页 4 2 1M M 1排队系统 9 目的系统的稳态解 系统运行一段时间后进入稳定状态的情况 稳态解条件 2004 8 28 第118 103页 4 2 1M M 1排队系统 10 各项与时间无关 2004 8 28 第119 103页 4 2 1M M 1排队系统 11 递推法得 2004 8 28 第120 103页 4 2 1M M 1排队系统 12 概率归一性 讨论 时 上式收敛 系统状态概率 2004 8 28 第121 103页 4 2 1M M 1排队系统 13 M M 1排队系统的状态转移图 2004 8 17 第122 103页 4 2 1M M 1排队系统 14 2004 8 28 第123 103页 4 2 2M M 1排队系统的性能指标