424通信网理论-排队论基础2

通信网理论（三）排队论与通信网业务分析排队论基础纪阳北京邮电大学移动生活与新媒体实验室E-mail:[e-mail]2M/M/m(n)问题ƒ通信中常见模型1.混合排队2.分别排队M/M/m(n)排队模型——混合排队模型¾m个窗口，每个窗口的服务率为µ¾总到达率为λ；截止队长为n¾窗口未占满，顾客到达后立即接受服务；¾窗口占满时，1.顾客等待，先到先服务2.当队长达到n时，新来的顾客被拒绝而离去3ƒ稳态方程：01111110000(1)()0()001kkkkkknnnikppkmpkpkupmknpmpmpknpmppλμλμλλμλμλμ−+−+−=−+=++−+=≤+−+==−==∑归一：4解的通式100111000/()!()()1!!1:!0kkrmnmmrmnnkmpmpmmppkmpmpprmmknppnknpλλρρμμρρρρρ−−+−====⎡⎤−=+⋅⎢⎥−⎣⎦==↑→↑=∴∑令：＝可得可得通解拒绝概率（）可见：拒，当时，永远稳定，以拒绝换稳定5M/M/m(n)的平均等待时间人1等对2等1人1等情况即可只算++==≤k-mkmkmknkmΜw⎪⎩⎪⎨⎧=≠≤000wwnkwnkmmk＝则分三种情况：1101011(1)1(r=k-m+1)!!nkkmmnkkmmnmkmrwkmpmkmmpmmrmpmmμρμρμ−=−=−+−==−+⋅⋅−+=⋅⋅=⋅⋅∑∑∑所以：令6()10101101021!1!1!111(1)()!1mnmmrrmnmmrrmnmmmnmnmmmprmmmdpmmdmdpmmdmnmnmpmmρρμρρμρρρρμρρρρρμρ−−−−−−+−−+=⋅⋅⎛⎞=⋅⋅⎜⎟⎝⎠⎛⎞−=⋅⋅⎜⎟−⎝⎠−−++−=⋅⋅−∑∑7M/M/m(n)的几种特例1）当n=m.为多窗口即时拒绝系统10000!!!/!——!—0rmrmmmrrmrrmmrmrmmmppmrramaamparawρρρλρμ−===⎡⎤==⎢⎥⎣⎦====∑∑∑拒绝概率：令，即，得厄朗公式呼叫量等待时延8M/M/m(n)的几种特例2）当n→∞,为非拒绝系统,M/M/m问题1021100110//01!(1)()()!!(1)1//111111cmmrmmrnMMmpmwpmmmprmmMMpμρρρρρρρρρ−−−=−−→∞=⋅=⋅−⎡⎤=+⎢⎥−⎣⎦=⎡⎤⎡⎤=+==−⎢⎥⎢⎥−−⎣⎦⎣⎦∑当，为非拒绝系统数学的问题拒绝概率平均等待数：其中，再令，为9M/M/m(n)的几种特例3）当m=1,为单窗口，M/M/1(n)101011111111(1)11nnnnnnnpppnnwρρρρρρρρρμρρ−+−+⎡⎤−−=+=⎢⎥−−⎣⎦=−+−=⋅−−10M/M/m(n)的几种特例4）当m=1,n→∞为M/M/102221(1)111()(1)()(1)2kkkwppkwkwρρρρρρρμρσρρσρ=−=−==⋅−−=−=−的方差，二阶中心矩的方差11M/M/m(n)系统效率:η¾效率即指平均窗口占用率(统计平均)¾窗口不满占用率k/m¾窗口满(k=m)占用率=11100(1)1(1)()mnkkkkmkmkppmpnpmpapnmammηηληρμηρληρμ−===⋅+→∞==≠−==−====∑∑则代入可整理出的表达式当，不拒绝多窗口单窗口－当，即时拒绝12拒绝型系统可以取ρ1仍能稳定工作,以拒绝概率(呼损)为代价ρ一定,增加截止队长(n)可提高效率,但等待时间亦长——延迟换效率所以，若延迟指标允许，用非即时拒绝型是合理的0111,//1()11110nnnmMMnpwpρηρρρη+−==⋅=−−=→∞=当当时，，＝系统不稳定不拒绝型系统可以取ρ113一般排队问题////1()()tMMMGatebtλλ−⋅=非，限于某些假设问题：到达服务任意1411111111112——010nnnnnnnnnnnnnnnnnnnCCCCknvnvkkkkvCCkkvCC+++++++++=+−==n+1两种情况：（）去时，未到（）去时，已经到第顾客离去时，系统内顾客数第顾客服务期间，到达数则与有去时人数＝去时人数＋C服务期到达数－1，有去时人数＝服务期到达数1501111000101101112010112()()!|0(|)nvvnnjnnjinknnknnnnnnnnnnnkkkkvqebdvPkjkqPkjkiqdCkdPkddqdqddqdqdqddqdqdqλτλτττ∞−++−++++−−=⋅======⎡⎤⎣⎦=+=++=++∫LL一顾客被服务期内到达人的概率为条件概率为：（）令表示去时观察系统队长为的概率，则：＝第人服务完毕观察有人则有：210nkdq+⎧⎪⎪⎨⎪⎪++⎩L160001010111202021221300121321002012300000//1()nkkkkkkkkkkkkkkkkkkkkkkdnMGddqdqddqdqdqddqdqdqdqddqdqdqdqdqQzzddzqdzqdzzqdzzqdd−−+∞=∞∞∞∞=====+⎧⎪=++⎪⎪=+++⎨⎪⎪=+++++⎪⎩==++++=+∑∑∑∑∑LLLLL稳态下，与无关，得的系统方程概率母函数：（211230rkrkkdzdzdzzq∞−=++++∑LLLL）17()()()()123012300001001000100010()1()1()!()1()()!1rkrkkkkkkkkkkzzdzdzdzdzdzzqdddzzdzQzzqzdzQzzebdkzzdzQzebdkzdzQzeeλτλτλτλτττλτττ∞−=∞−=∞∞−−=∞∞−−=−=++++++−+=−+⋅⎡⎤⎣⎦=−+⋅⋅⋅⎡⎤⎣⎦=−+⋅⋅⎡⎤⎣⎦=−+⋅⎡⎤⎣⎦∑∑∑∫∑∫LLLL（）（）（）（）()010()1()bdzdzQzBzλτττλλ∞−−⋅=−+⋅−⎡⎤⎣⎦∫（）1800122()(1)()()()(1)1(0)(1)11(0)(0)(0)(0)()1(0)()(0)()(0)(1)rrrzdBzQzzBzQdBQBBBBbdBbdmBbdmBmλλλλλττττττττ−−=−−===′+′==′=−⋅=−′′===−∫∫∫QLL0得母函数解为：为求d，有：，并应用罗毕达法则，上下求导，再代入z=1式中与的意义由拉式变换得：190000(0)(1)11(0)111()(1)(1)()()()//1()()dBQBdddQzzBzQzzBzMGbBsλλτλτρρλλλλτ==′+=−=−=−−⋅−⋅−=−−由得：已知即可写出式：上式为的顾客离去时队长概率的母函数解，其由的拉式变换所确定。20[][]2210100210021()|2(1)()()()()()kzkkkkkkkkkkkkkzmkkdQzkQzzdQzkzdzQzkzdzQzkzdkzQzλρρ∞==∞∞−==∞∞−===′===+−′=⇒=⋅′′′⇒=⋅⇒=⋅′′∴=∑∑∑∑∑平均队长：上述母函数解还可求出的各阶矩2111iinwiitnnτ+−−−+其中：第顾客等待时间第顾客等待时间第顾客与第顾客到达间隔M/G/1等待时间W的统计特性11110()nnnnnnnnnnnWttWWtWWnWpwτττ+++++−+⎧=⎨≥+⎩可见：稳态时，分布与无关，记为，令其密度存在，则：2200000()()0000()()()()()()()()()()()()()()()()()()wxttxwtttxuuwxpwpxbatdtddxwpxatbdtdxdpwtbeddtwpxbedtdxdwupubedduwpxbedxdττλλτλλτττδτττττδτλττττλτδτ=+−+∞+∞∞∞−−+∞∞∞−−−+=+=+−++==−+∫∫∫∫∫∫∫∫∫∫∫∫∫∫∫令()00[()()]()()()uuwpubdeduwGBλττττλδλλ∞−−=−+∫∫23式中B(λ)与G(λ)分别为b(τ)与p(x)的拉氏变换，即：为解上述积分方程，(p(x)为所求密度)，对左右求拉氏变换：00()()()()ttBbedGpxedxλλλττλ∞−∞−==∫∫00()00()()[()()]swswuswuwpwedwGsedwedwpubdeduλλλτττ∞−∞−∞∞−−−=⎡⎤⎣⎦=−∫∫∫∫∫左端：右端：右端式24()()()()()()()()()()GBGsBsGBssSGBGsSBsλλλλλλλλλλλλ=−+−−=−+得：其中G(s)为等待时间w的密度p(x)拉氏变换，B(s)为服务时间τ的拉氏变换用归一化条件进一步求解：G(0)=101()()()()()()(0)[]11()1[(0)]11()sBGGBGBGBsBmsλλλλλλλλλ=====−′−−−−2510()()11BGmdλλλρ=−=−=得由p(w)中之δ(w)B(λ)G(λ)知，B(λ)G(λ)即w=0的概率。最后得w分布密度p(w)的拉氏变换解同时可求w的各阶矩及方差2022(1)()()()()|2(1)(0)ssGsBssBsmwGsmmBρλλλρ=−=−+′=−=−′′=由确定平均等待时间其中为的二阶矩，26以M/M/1为例，有：已得上述结果，对M/G/1：这是由于残余寿命y分布与τ不同2222()(0)[(0)]σ′′′=−=−−wkτ≠122112()(0)(0)22(1)(1)()uBsBmBusuuwmuλμρρμρλρλ′′′==−=−=+⋅==−−==，，27由此来验证Little公式，swτ=+1()()()SsGsBsswmskλ==+=则：满足ƒ残余寿命y分析某一顾客到达时，系统正对服务，观察时刻位于，y的密度为：nCnτ11122200110()11()()()()()()222nnnnnnyybfybddFymmmmyybyyypydyfydymmττττττ∞∞∞∞∞=⋅==−==+=∫∫∫∫＝0分部积分法282110111002221011111[(1)]()(1)2//112(1)21(1)kkmwykmpmpmkmMGpdmwmmpwkmwkmwykmymwkmρλρ∞==+−=−−+==−=−===≠=+−≠≠∑对有：代入亦得：同前所述。由式可见，仅当或有：否则这也就是马尔可夫性。还可写为：可见时，平均等待时间＝顾客到达时，正在被服务顾客的残余寿命＋其余k-1个顾客的平均服务时间29G/M/1问题1nnnnnnnntCCqtknCC+−−−与之间的到达间隔内服务完毕（离去）的顾客数第个顾客到达时系统内的队长（不含）30拉氏变换的性质()()()()(1)()nnnnftLsdLstftnds→→−如果阶导数0()0()()()()!()()!()[()]()()(()k)nnnktnknnnkkstkkktqktpqkeatdtkAkASLatatedtdAAsASSdSμμμμμ∞−∞−====⋅−====∫∫在内有个顾客离去的概率对的阶导31表示顾客到达时队长为的概率达到稳态后，与n无关系统方程为：上式为线性差分方程，令通解：kr111nnnnkkkkqr++=−+Q非负，1011210110000102011020120kkkkkiikkkkkkkiikikikkrrrrrrrrrrrrrμμμμσσσμσμσμσμσσμσμσμσμσμ−+++++−−∞==⋅+⋅+⋅++⋅+==⋅+⋅+⋅++⋅=++++++=∑LLLLL－代入上式，得除得：320000000()0()()!()()!()()!()()()kktkktkktktttteatdtkteatdtkteatdtkeeatdteatdtAμμμμσμμμσμσμσμσμμσ∞∞−=∞∞−=∞∞−=∞−∞−−=⋅=⋅=⋅=⋅=⋅=−∑∫∑∫∑∫∫∫33式中的σ由a(t)的拉氏变换决定此解与M/M/1解的形式一致故平均队长:0