(推荐)§1排队论基础

1、l(推荐)1排队论基础第二章第二章 网内业务分析网内业务分析1 排队论基础排队论基础 常见现象：常见现象： 顾客顾客+服务服务排队系统排队系统 矛盾统一矛盾统一 广义化：广义化： 通信中：呼叫通信中：呼叫线路线路信息包信息包分组交换机分组交换机 移动体移动体服务区服务区 计算机：总线指令计算机：总线指令cpu处理处理 数据流数据流存储器存储器 其它：敌机其它：敌机防空设施防空设施 客机客机跑道跑道 复杂性：在于随机性复杂性：在于随机性到达与离去（服务到达与离去（服务率）均不确定率）均不确定工作于随机状态工作于随机状态 资源少资源少顾客排队长顾客排队长服务质量下降服务质量下降 资源多资源多服务闲

2、置服务闲置资源浪费资源浪费 目标：为顾客提供满意服务同时提高资目标：为顾客提供满意服务同时提高资 源利用率。（与统计参数和工作方源利用率。（与统计参数和工作方 式有关）式有关）在通信网的业务分析和性能计算中，排队论在通信网的业务分析和性能计算中，排队论是不可缺少的是不可缺少的.1、基本概念、基本概念 m- 窗口数，表示资源的量。可同时向顾客提供窗口数，表示资源的量。可同时向顾客提供服务的设施数。（单窗口排队系统服务的设施数。（单窗口排队系统 m=1；多窗；多窗口排队系统口排队系统m1）-顾客到达率（平均）顾客到达率（平均） -系统服务率（平均）系统服务率（平均）1. 排队系统三

3、要素排队系统三要素: m，平均到达时间平均到达时间 t: : iintnt1lim平均到达率平均到达率单位时间到达顾客数单位时间到达顾客数 t1或或 ttnt)(lim(n(t)(n(t)t t内到达数）内到达数） 负荷轻负荷轻 -顾客到达率（平均）顾客到达率（平均）1同理同理 平均服务时间平均服务时间：系统服务率（平均）：系统服务率（平均） 此三量可已知或可测出，但描述排队系统，此三量可已知或可测出，但描述排队系统，此三要素不充分。此三要素不充分。 主要取决于主要取决于 ti 和和i的统计特性（分布）和排的统计特性（分布）和排队规则。队规则。2、统计特性（分布）和排队规则统计特性（分布）和排

4、队规则。常见排队系统的假设常见排队系统的假设l平稳性：平稳性： a，a+t内到达内到达k个顾客（或离去）的概率与个顾客（或离去）的概率与a无关，只与无关，只与t有关。有关。 l无后效性无后效性 顾客到达时刻相互独立顾客到达时刻相互独立 不相交区间内到达顾客数相互独立不相交区间内到达顾客数相互独立 系统顾客数具有马氏性系统顾客数具有马氏性l稀疏性：稀疏性： t内到达内到达2个或个或2个以上顾客概率为个以上顾客概率为0 有限区间内的有限区间内的k为有限，或为有限，或0)(kp(1)t内有内有k个顾客到达的概率个顾客到达的概率在以上假设下：在以上假设下： t内到达顾客数为内到达顾客数为kt t(=n

5、(=n) )= =t/nt/n.内有内有1顾客到达概率顾客到达概率内无顾客到达概率内无顾客到达概率1- 有有2 2个到达概率个到达概率 2)(据无后效性据无后效性, 独立独立据二项分布据二项分布, n个贝努利分布个贝努利分布t t内有内有k k个到达的概率个到达的概率: : ( )1()( )!knkkktknptktnptekk 得泊松分布为离散变量（2）到达间隔）到达间隔t的概率密度的概率密度a（t） 到达间隔到达间隔t连续变量连续变量 把把t t分分n n份，到达间隔为份，到达间隔为t t的概率：的概率： n)1 (（n n个个内无到达，第内无到达，第n+1n+1个必到达）个必到达） 若

6、若t t的概率密度的概率密度a a（t t）存在，则有：）存在，则有：tnnnnnenttata)1 (lim)1 (lim)()1 ()(指数分布（3）服务时间）服务时间 的概率密度的概率密度以上结果亦适用于服务过程，以上结果亦适用于服务过程， 可得teb)(综上所述，在以上三个假设下？：综上所述，在以上三个假设下？：l顾客到达和离去均为泊松流，均值顾客到达和离去均为泊松流，均值，二阶，二阶矩矩(+1)l相邻事件发生的间隔负指数分布，均值相邻事件发生的间隔负指数分布，均值1/，二阶矩二阶矩1/2l具有马尔可夫性，称具有马尔可夫性，称m分布称最简单流分布称最简单流（4）运行方式及规则规定：）运

7、行方式及规则规定： 排队系统的运行性能不仅与排队系统的运行性能不仅与上述的统计分布有关，还与系统上述的统计分布有关，还与系统预 先 规 定 的 工 作 方 式 有 关 。预 先 规 定 的 工 作 方 式 有 关 。包 括 服 务 规 则 和 排 队 规 则 ：包 括 服 务 规 则 和 排 队 规 则 ： 按服务规则分：按服务规则分：1）先到先服务：常见情况）先到先服务：常见情况2）后到先服务：不常见情况）后到先服务：不常见情况3）优先制服务：顾客分优先级）优先制服务：顾客分优先级按排队规则分：按排队规则分：1）等待型：不拒绝系统。若窗口不空，就依次）等待型：不拒绝系统。若窗口不空，就依次排

8、队等待，直到被服务完毕后离去。排队等待，直到被服务完毕后离去。2）截止型：分为损失制、拒绝系统）截止型：分为损失制、拒绝系统系统已有系统已有n个顾客等待，顾客到来时，就被拒绝个顾客等待，顾客到来时，就被拒绝。分为如下。分为如下2种种即时拒绝：如窗口数为即时拒绝：如窗口数为m,m=n,满，则顾客到达满，则顾客到达后立即被拒绝，被拒绝排队等待后立即被拒绝，被拒绝排队等待 （电话网）（电话网）延迟拒绝：延迟拒绝：mn,mn,允许等待一定数量，超允许等待一定数量，超n n，再拒，再拒绝绝 (带缓冲存储的数据通信）带缓冲存储的数据通信）(1)(1)队长队长k k：某时刻观察系统内滞留的顾客数。：某时刻观

9、察系统内滞留的顾客数。(2)(2)等待时间等待时间w:w:顾客从到达至开始被服务这段时顾客从到达至开始被服务这段时间。间。(3)(3)服务时间服务时间 ：一个顾客被服务的时间：一个顾客被服务的时间(4)(4)系统时间系统时间s s，或称系统停留时间，或称系统停留时间 ：顾客从到：顾客从到达至离开的这段时间。达至离开的这段时间。s=w+ s=w+ (5)(5)系统效率系统效率 ：平均窗口占用率：平均窗口占用率目标参量：目标参量：（分析排队系统时的主要求解指标（分析排队系统时的主要求解指标)(6)(6)稳定性指标：稳定性指标：对于不拒绝系统，当对于不拒绝系统，当到达率到达率与服务率与服务率 之比（

10、称为排队系统之比（称为排队系统强度强度 ）大于窗口数）大于窗口数m m时，平均时，平均顾客到达数将大于平均顾客离去数，顾顾客到达数将大于平均顾客离去数，顾客的队将越来越长，平均等待时间将趋客的队将越来越长，平均等待时间将趋于无限大，系统不稳定。小于窗口数于无限大，系统不稳定。小于窗口数m m时时，系统是稳定的，系统是稳定的( ( m)。对于截止型系统。对于截止型系统，因为队长被限制，即使排队强度大于，因为队长被限制，即使排队强度大于m m，系统仍然可以稳定工作。，系统仍然可以稳定工作。 =/=/ k队长队长k l排队长度排队长度t瞬间系统内的顾客数（含在窗口的）瞬间系统内的顾客数（含在窗口的）

11、l k离散随机变量离散随机变量l 三种观察：三种观察：ldk顾客到达时观察队长为顾客到达时观察队长为k的概率（不包括刚的概率（不包括刚到达的顾客）到达的顾客）lrk顾客服务完毕离去时观察队长为顾客服务完毕离去时观察队长为k的概率的概率（不包括正在离去的顾客）。（不包括正在离去的顾客）。l（以上为有条件抽样）（以上为有条件抽样）lpk（服务员）随机观察队长为（服务员）随机观察队长为k的概率的概率l 在最简系统中，在最简系统中，pk =rk =dkl 平均队长，又称系统数平均队长，又称系统数 w等待时间等待时间w从到达从到达开始服务的时间，是连续随机变量，开始服务的时间，是连续随机变量，其统计平均

12、为：其统计平均为： 平均等待时间（网络中等待时延的主平均等待时间（网络中等待时延的主要部分）要部分）其它时延，如传输时延和处理时延较小其它时延，如传输时延和处理时延较小 服务时间服务时间 l开始接受服务开始接受服务服务完毕离去服务完毕离去l 平均服务时间平均服务时间 到达到达离去离去 s=w+s=w+ 对任何排队系统，有对任何排队系统，有 ws )w(s公式littlek系统时间系统时间s s，或称系统停留时间，或称系统停留时间mrmr需求多窗口即忙的概率单窗口,系统效率系统效率 平均窗口占用率平均窗口占用率 共共m m个窗口，某时刻如有个窗口，某时刻如有r r个被占用，则个被占用，则 =/=

13、/ 稳定性指标稳定性指标不拒绝系统：不拒绝系统： .不稳定mww或单窗口1 )(m 仍然稳定仍然稳定 截止型系统：截止型系统：排队系统表示符号：排队系统表示符号： a/b/m(n,n)a/b/m(n,n)a a 到达规律，到达规律， 分布分布a(t)a(t)（到达时间间隔）（到达时间间隔）b b 服务规律，服务规律， 分布分布b(b() )（服务时间间隔）（服务时间间隔）m m窗口数窗口数n n顾客源，潜在顾客数，省略为顾客源，潜在顾客数，省略为 n n截止队长，省略为截止队长，省略为 ，不拒绝，不拒绝常见分布：常见分布：m m指数分布指数分布/1( )/( , )/1( )( )/( )tm

14、 ma tem m m n nm mnbem m m n到达服务将讨论将讨论: :l基本：基本：m/m/1 m/m/m(n)m/m/1 m/m/m(n)l中级：中级：m/g/1 g/m/1m/g/1 g/m/1l高级：高级：g/g/1g/g/1解法：解法： 确定状态变量，如确定状态变量，如k 画状态转移图画状态转移图 列状态转移方程列状态转移方程 求解目标参量求解目标参量设平均到达率为设平均到达率为 ，平均服务率为，平均服务率为 。取队长为状态变量建立系统的差微分取队长为状态变量建立系统的差微分方程。方程。1 1、状态图与状态方程、状态图与状态方程 t t时刻，系统内有时刻，系统内有k k个顾

15、客的概率个顾客的概率（k=0,1,2, k=0,1,2, ） )(tpk二、m/m/1问题t t时刻，时刻， k k状态状态 则：则：tttt内到达内到达1 1人概率人概率 tttt内离去内离去1 1人概率人概率 t+t时刻处于时刻处于k状态（概率状态（概率 ），由下述情），由下述情况形成：况形成：lt为为k-1态，态，t内到达内到达1人，无人离去，人，无人离去，概率概率:lt为为k+1态，态，t内离去内离去1人，无到达：人，无到达：lt为为k态，态，t内到达内到达1人，离去人，离去1人人:lt为为k态，态，t内无到达，无离去内无到达，无离去:)(ttpk11( )(1)( )kkptttpt

16、t ttptttpkk)()1 ()(112( )kp tt( )(1)(1)( ) (1)kkptttpttt k-1k+1k t t t t t t t t1 1- - t t- - t t)1)()()()(:11tttpttpttpttpkkkk得)()()()()()(:11tptptpttpttpkkkkk即)()()()()(011tptptpdttdptkkkk得导数即柯尔莫哥洛夫方程。即柯尔莫哥洛夫方程。 k=0, 需重写需重写: 原原1人人,去去1人人 tp1(t) 原原0人人,无人到无人到 (1- t) p0(t) p0(t+t)=t)= tptp1 1(t)+(t)+

17、(1- t t) p p0 0(t)(t) 得得: )()()(010tptpdttdp至此至此，得得m/m/1完整状态方程完整状态方程: )()()()()()()()(01011tptpdttdptptptpdttdpkkkk上式，已由上式，已由 ， 表示转移，得状态转移图：表示转移，得状态转移图： 021. . . . . . .k . . . . . . .2 2、稳态解、稳态解 l物理意义：物理意义： 到达与离去平衡，到达与离去平衡，p pk k(t)(t)与与t t无关无关 l数学描述：数学描述： kkkptpdttdpt)(, 0)(,00)(0111pppppkkk 021.

18、. . . . . .k . . . . . . .003302000121k1101:, 2)1 ()1 ( , 1p) 1()(1ppkppkppppppkppppppkkkkkk代入得代入得令得令求求p0: 用归一化条件用归一化条件 111)1(100002ppppkkp0系统无人概率（空闲率）系统无人概率（空闲率）1-p0= 系统有人概率（忙概率）系统有人概率（忙概率）忙忙 太大太大不稳不稳得通解：得通解：0(1)kkkpp平均队长平均队长 100002(1)(1)(1)1(1)(1)(1): () , 0.5:kkkkkkkkdkkpkkdkk 顾客观点短只与 有关折衷取以下效率观点

19、k k的方差的方差 20120122232( )(1)1(1)(1)()(1)(1)(1)(2)32kkkkkkkkkkkkkg zpp zp zp zz pgpgkpkgkzpk kzpkk pkkgk kkpkkk母函数由归一性，又 （2222222()(1)(1)()(1)(1) (1)kkkekkggkkkpekkggg的二阶原点矩的方差（二阶中心矩）022322)22/1(1)1( )(1)1(1- )(1- ) g (z) g (z)(1)(1)(1(1)(1)(1)kkkkkkm mpzzzzz 对有2kk0.50.51 1如如图图5 . 0激激增增k2尤尤甚甚等待时间等待时间w

20、 w 若系统已有若系统已有k k人人, ,即处于即处于k k状态状态, ,来一来一人的等待时间人的等待时间w w是为前面是为前面k k个人的服个人的服务时间总和务时间总和 即即: : 121kkkiiw 因为因为 i i相互独立，则相互独立，则wk是是k个独立变量之和，个独立变量之和，所以，所以， w wk k 的特征函数为的特征函数为k个个 i i 的特征函数之积。的特征函数之积。 i的特征函数的特征函数: (b()概率的付氏变换概率的付氏变换)0( )jzzeedjzkkjzw)(k个个 i和的特征函数和的特征函数 因为因为k为离散变量为离散变量,故故w的特征函数的特征函数: 000( )

21、()(1),()(1)(1)(1)(1)11(1)(1)(1)kkkkkkkkkkw zw pppxjzjzxxxxjz 令w的密度的密度:(1)1( )( )2(1) ( )(1)jzwwf ww z edzwe 平均等待时间平均等待时间: (1)0022( )0(1)11(1)(1)1wwwf w dwwedw w的方差的方差: 22222)1()2()(wdwwfww系统时间系统时间(平均停留平均停留) )1(1 ws反验反验little公式公式: ks1)1(至此至此, ,得得m/m/1m/m/1结论如下结论如下: : 1222(1)111(2)(1)1(1)kkwkpkwkwsw 概

22、率平均队长平均等待时间平均等待时间 的方差系统时间0111itp平 均 闲 期平 均 忙 期空 闲 率忙 概 率各 变 量 分 布 解 析 结 果 、 平 均 值 结 果均 取 决 于顾客观点：不稳稳定性指标：效率指标：窗口占用率的三个意义1 所以所以,m/m/1主要矛盾集中在主要矛盾集中在 的选取的选取 服务质量与系统效率之间的矛盾服务质量与系统效率之间的矛盾 解决目标解决目标:保证稳定运行条件下提高效率保证稳定运行条件下提高效率 m/m/1m/m/1系统的主要缺点是服务质量与系统系统的主要缺点是服务质量与系统效率的的矛盾。解决的办法有两种效率的的矛盾。解决的办法有两种 措施措施: （1）

23、增加窗口数（增大效率，但投资加大）增加窗口数（增大效率，但投资加大） （2）截止排队长度，即采用拒绝型系统（降低）截止排队长度，即采用拒绝型系统（降低系统质量（顾客被拒绝），换取效率和稳定性）系统质量（顾客被拒绝），换取效率和稳定性）将上述两个方法结合为将上述两个方法结合为 截止多窗口排队系统截止多窗口排队系统 三、三、m/m/m(n)m/m/m(n)问题问题 l常见多窗口排队方式有两种：常见多窗口排队方式有两种： 混合排队混合排队 （ m/m/m(n) )m/m/m(n) )分别排队 ( 为m个独立的m/m/1)m/m/m(n)m/m/m(n)排队模型排队模型 窗口数为窗口数为m,截止队长为

24、截止队长为n. 每个窗口的服务率均为每个窗口的服务率均为 ，服务时间和到达间隔均为指数分布。即：服务时间和到达间隔均为指数分布。即： 窗口服务时间窗口服务时间总到达率总到达率令令: etemm/ 令系统内顾客数k为状态变量，此时，只有n+1种状态。k=m时，有k个窗口在被占用，则服务率为k , ,当当mknmkn时时,pk=0, 永稳定永稳定 以拒绝换稳定以拒绝换稳定wm/m/m(n)的平均等待时间的平均等待时间 000:wnkwnkmwmk则分三种情况nkm只算只算 011101!)1(!11)1(pmmmrmkrpmmmmkpmmkwmrmmnrnmkkmnmkk令情况即可情况即可 k=m 等等1人人k=m+1 等等2 对对k 等等k-m+1人人所以所以:2101010110)1()()1(11!)1(1!)(1!1!mnmnmmmnmmmnrrmmmnrrmmmnmnpmmmddpmmmddpmmmrpmmm0 ,)(!/,!:01000waerlangramapmaarmprmmmppmrrmmmrrrmrrrmmmn等待时延呼叫量公式厄朗得即令拒绝概率m/m/m(n)m/m/m(n)的几种特例的几种特例a)