44通信网理论-排队论基础1

We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT通信网理论（三）排队论与通信网业务分析排队论基础纪阳北邮无线新技术研究室Tel:[phone]E-mail:[e-mail]2We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT排队论概述•排队系统–要求服务的顾客–提供服务的服务员3We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT排队论概述•排队系统的广泛性–顾客+服务→排队系统–矛盾统一，广义化：•通信中：–呼叫——线路–信息包——分组交换机–移动体——服务区•计算机：–总线指令——CPU处理–数据流——存储器•其它：–敌机——防空设施–客机——跑道4We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT排队论概述•排队现象存在的基础–资源的有限性–需求的随机性•排队系统的复杂性在于随机性–到达与离去（服务率）均不确定，工作于随机状态5We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT排队论概述•排队系统中的资源冲突–资源少——顾客排队长——服务质量下降–资源多——服务闲置——资源浪费•排队系统设计目标–为顾客提供满意服务同时提高资源利用率。（与统计参数和工作方式有关）6We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何描述一个排队系统（1）•排队系统三要素:m，λ，μ–m-窗口数，表示资源的量•可同时向顾提供服务的设施数。•（单窗口m=1；多窗口m1）–λ-顾客到达率（平均）–μ：系统服务率（平均）7We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何描述一个排队系统（1）λ↓——负荷轻•此三量可已知或可测出，但描述排队系统，此三要素不充分•主要取决于ti和τi的统计特性（分布）和排队规则8We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何描述一个排队系统（1）•此三量可已知或可测出，但描述排队系统，此三要素不充分•排队系统性能主要取决于–ti和τi的统计特性（分布）–服务规则和排队规则9We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT到达与服务的分布类型•M——指数分布–平稳性–稀疏性–独立性•泊松分布•Er——r阶爱尔兰分布•HR——R阶指数分布•D分布——确定性分布10We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT系统工作方式•服务规则–先到先服务FirstIn,FirstServe–后到先服务LastIn,FirstServe–优先制服务Priority•排队规则–等待型•不拒绝系统–截至型•n=m,即时拒绝，电话网•mn,延时拒绝，缓冲区数据通信11We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT排队过程的实例到达离去忙时T闲时I顾客数t1t2tnt1τ2τnτ12We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何分析一个排队系统•排队队长k的概率分布、均值、方差•等待时间w的均值、方差•服务时间τ•系统时间S•系统效率η–窗口占用率，η＝r/m•稳定性–ρ=λ/µ•ifρm,不拒绝系统，notstable,•ifρm,截至型系统，stable13We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT队长k排队长度—t瞬间系统内的顾客数（含在窗口的）k—离散随机变量三种观察：dk—顾客到达时观察队长为k的概率rk—顾客离去时观察队长为k的概率（以上为有条件抽样）pk—（服务员）随机观察队长为k的概率在最简系统中，pk=rk=dk—平均队长，又称系统数k注意：其他的系统中这几种观察的结果是不同的。14We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT等待时间w和服务时间τ从到达→开始服务的时间，是连续随机变量—平均等待时间w等待时延是信息在网络中平均时延的主要部分其他时延，如传输时延、处理时延一般是较小的等待时间w服务时间τ：τ开始接受服务→服务毕离去—平均服务时间15We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT系统时间s•或称系统停留时间到达→离去,swswττ=+=+显然有于是有16We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT系统效率η•系统效率η：平均窗口占用率–共m个窗口，某时刻有如r个被占用，则mrmr需求多窗口即忙的概率单窗口,,=η17We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT稳定性指标•稳定性指标：ρ=λ/µ不拒绝系统：.不稳定mρ∞→↑ww或单窗口1)(ρ截止型系统：mρ，仍然稳定18We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPTLittle公式kλλ⋅=在一个平均到达率为的排队系统，在平均意义上，有sLittle定理适用于任何排队系统19We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何描述一个排队系统（2）•Kendall记号——A/B/m(N,n)–A——到达规律，分布a(t)–B——服务规律，分布b(t)–m—窗口数–N—顾客源，潜在顾客数，省略为∞–n—截止队长，省略为∞，不拒绝20We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何描述一个排队系统（2）•到达与服务的分布类型–M——指数分布–泊松分布–Er——r阶爱尔兰分布–HR——R阶指数分布–D分布——确定性分布21We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT目标问题•基本问题–M/M/1–M/M/m（n）•中级问题–M/G/1–G/M/1•高级问题–G/G/122We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何分析一个排队系统•一般来讲，马尔可夫型排队系统求解任意时刻的状态概率较容易些；而非马尔可夫排队系统在采用嵌入马尔可夫链的手法分析时求解到达时刻或退去时刻状态概率比较容易些，因此三者之间如能建立其某种关系将很有帮助23We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何分析一个排队系统•平均队列长度和平均等待时间是排队系统的两个最基本的性能参数–e.g.,考虑任意一个单一服务者排队系统。假设顾客的平均到达间隔为4分钟，平均服务时间为3分钟，并且经观察在任意时刻平均等待队列长度为5人。试问：（1）正在接受服务的顾客数的平均？（2）排队系统中的平均总人数（包括正在服务中的顾客）为多少？（3）顾客的平均等待时间为多少（15分钟？18分钟？20分钟？）24We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT如何分析一个排队系统•几个公理式假设–两个随机变量同时发生的概率为高阶无穷小，不予以考虑–一般多考虑排队系统达到稳态情况下的特性•解法：确定状态变量，如k列状态转移图列状态转移方程求解目标参量25We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPTM/M/1问题26We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT•t为k-1态，Δt内到达1人，无人离去概率:11()(1)()kkptttpttλµλ−−⋅∆−∆≅⋅∆•t为k+1态，Δt内离1人，无到达ttptttpkk∆⋅≅∆−∆⋅⋅++µλµ)()1()(11概率:•t为k态，Δt内到达1人，离去1人:2)(ttpk∆⋅λµ概率:•t为k态，Δt内无到达，无离去概率:()(1)(1)()(1)kkptttptttλµλµ−∆−∆≅⋅−∆−∆27We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT11:()()()()(1)kkkkptttpttptptttλµλµ−++∆=∆+∆+−∆−∆得11()()()()()()kkkkkpttptptptpttλµλµ−++∆−=+−+∆即:)()()()()(011tptptpdttdptkkkkµλµλ+−+=→∆+−得导数即柯尔莫哥洛夫方程28We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT()()pkpk=进入态离开态()0kdptdt=稳态下，29We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT30We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT31We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT32We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT33We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT——通过母函数求导的方法来计算34We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT2kσ0.51ρ如图5.0ρ激增kσ235We’reThinkingforInnovations…WirelessTechnologyInnovationLabs,BUPT等待时间w若系统已有k人,来一人的等待时间w为k人的服务时间即:∑==+++=kiikw121ττττLτi的特征函数:(a(t)的付氏变换)∫∞−−==0)(jzdeezZjzµµτµτµτk个τi和的特征函数kkjzw)(−=µµ因为k为离散变量,故w的特征函数:36We’reThinkingforInnovations…WirelessTechnologyInnovation