2-2网内业务分析-排队论

2011-9-221通信网理论基础1引论(通信网及通信网概述）2网内业务分析3多址接入系统分析4通信网结论（图论基础）5通信网中的流量优化6通信网的可靠性2011-9-222第二章网内业务分析2.1排队论基础2.1.1基本概念2.2.2M/M/1排队问题2.2.3M/M/m(n)问题2.1.4一般排队问题2.2通信网的业务模型与分析2.3提高网效率的一些措施2011-9-2232.1.2M/M/1问题M/M/1问题模型等效于M/M/1/∞/∞。1.队列模型：M/M/1是一个基本的标准排列模型；一个服务台,到达率λ和服务率μ都服从指数分布。∞泊松流到达λn指数服务μ顾客离开图：M/M/1排队模型2.列系统状态转移方程，求稳态概率Pn。μλλλλλ012K-1KK+1…λμμμμμ…λμ2011-9-2242.列M/M/1系统状态转移方程，求稳态概率Pn。10;ppμλ=11()kkkpppλμλμ−++=+在任意状态n达到稳态平衡的条件：（流入=流出）产生该状态的平均速率=该状态转变成其他状态的平均速率.021();pppλμλμ+=[phone],,,;1,1,(1)nnnnnnpppppppppλρρρμρρρρ∞=======−=−∑Qμλλλλλ012K-1KK+1…λμμμμμ…λμ2011-9-2252.1.2M/M/1问题1000[](1)1nnsnnnnkLEnnpnρρρρρ∞∞∞+======⋅=⋅−==−∑∑∑211[1](1)()1qnnnsnnLEnnpnppLρρρ∞∞===−=−⋅=−=−=−∑∑11[],(1)ssWEwμλμρ===−−111qsρμμρ==−=−3.计算M/M/1排队系统运行的性能指标。1）系统中队列平均长度Ls及队列中平均等待顾客数Lq。2）系统逗留时间Ws服从μ−λ的指数分布。()()()swsfweμλμλ−−=−⋅2011-9-226,1skLρρ==−2,1qLρρ=−1,(1)sWμρ=−11qWWρμρ==−*M/M/1排队系统运行的性能指标总结2.1.2M/M/1问题*一般来说，排队系统满足的Little公式有下列特征,ssqLWLμλλ=⋅=+队列长度,qqssLLLWρρλ==⋅−=排列等待长度1,sqWWμ=+系统逗留时间1,qssρμ==−排列等待时间2011-9-227M/M/1举例（性能参数计算）到达病人数出现次数fn010128229316410566人及以上1某医院记录病人来诊（100小时)和完成手术（100人）情况如下：手术时长(小时)出现次数fv0—0.2380.2—0.4250.4—0.6170.6—0.890.8—1.061.0—1.251.2小时以上0则基本参数：每小时病人平均到达率：λ=∑nfn/100=2.1人/小时每次手术平均时长：∑vfv/100=0.4小时/人。则手术完成u=2.5人/小时根据数理统计χ2检查方法：得到λ=2.1满足泊松分布，手术时长μ=2.5满足负指数分布。ρ=λ/μ=0.84，其它运行指标Ls,Lq,Ws,Wq略。2011-9-2282.1.2M/M/1问题M/M/squeuingcomputationsArrivalrate5Servicerate6Numberofservers1Utilization83.33%P(0),probabilitythatthesystemisempty0.1667Lq,expectedqueuelength4.1667L,expectednumberinsystem5.0000Wq,expectedtimeinqueue0.8333W,expectedtotaltimeinsystem1.000000.050.10.150.20246810121416182022242628303234363840NUMBERINSYSTEMProbability例：M/M/1队列2011-9-229例：某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。试对此排队队系统进行分析。2.1.2M/M/1问题解：对此排队队系统分析如下：（1）这是单服务台M/M/1系统，则确定参数值如下：25.075.0110=−=−=ρPhhh/4/1560,/3人人服务率人到达率===μλ,75.043===μλρ服务强度（2）计算稳态概率：这就是急诊室空闲的概率，即病人不必等待立即就能就诊的概率。而病人需要等待的概率则为：这也是急诊室繁忙的概率。75.010=−=Pρ2011-9-22102.1.2M/M/1问题（3）计算系统主要工作指标。急诊室内外的病人平均数：急诊室外排队等待的病人平均数：病人在急诊室内外平均逗留时间：病人平均等候时间：人人3343=−=−=λμλL人人25.275.03=×==ρLLqmin6013411==−=−=hhWλμmin4575.075.01==×==hhWWqρ（4）为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？由于211≤−=λμWmin12511=≤hμ代入λ=3，解得μ≥5，平均服务时间为：15－12＝3min，即平均服务时间至少应减少3min。2011-9-2211两边取对数，得（x＋2）lgρ≤lg0.1，2.1.2M/M/1问题(5)若医院希望候诊的病人90%以上都能有座位,则候诊室至少应安置多少座位?设应该安置χ个座位,加上急诊室的一个座位,共有χ+1个。要使90%以上的候诊病人有座位，相当于使“来诊的病人数不多于χ+1个”的概率不少于90%，即9.0)1(1)1(≥+−=+≤xNPxNP;1.0)1(≤+xNP1.021)1(≤=+++xxρρ875.0lg1lg1.0lg2=−=≥+ρx因ρ1，故所以，x≥6，即候诊室至少应安置6个座位。2011-9-22122.1.3M/M/m(n)问题图：M/M/m(n)排队模型状态转移μλλλλλ012m-1mm+1…λ2μ3μmμ…λ(m−1)μmμmμNmμn泊松流到达λ客源::指数服务顾客离开图：M/M/m(n)混合排队模型μμμ12m1.M/M/m(n)混合排队模型2.M/M/m(n)状态转移2011-9-22132.1.3M/M/m(N)问题在稳态平衡的条件下：流入=流出，令服务强度ρ=λ/(mμ);另外，系统的Erlang呼叫量a=λ/μ。02112;ppppλμλμ+=+001000()1,!1,(1)/(1);,1/[].!kNkkkNrmrrmpppkmpmNmprρρρρ=+=====−−==∑∑Q10;ppμλ=11(1)kkkkpkppkpλμλμ−+++=+μλλλλλ012K-1KK+1…λ2μ3μkμ…λ(k−1)μ(k+1)μ(k+2)μNmμ2011-10-1312.1.3M/M/m(n)问题(256)−有了Pk的通式，就可计算平均等待时间参数量。到达顾客的等待时间与到达时刻系统状态有关。当时，顾客不需等待即被服务；时，顾客被拒绝而离去，也无等待时间；所有只有当时，才存在等待问题。此时，个顾客中，有个正在被服务，个在排队等待；则新到顾客需要要等待个顾客服务完毕，才能开始服务。由于个窗口都在工作，所以平均服务概率是，则新到顾客的平均等待时间：ωkmkn≥mkn≤mkm−kmμk1km−+mω110111100110211!()()!!111(1)()!(1)mnnkkkmkmmkmmnmnnkkmmnmnmmkmkmmppmmmppmdmdmmmmdmmdpmnmnmmωρμμρρρρρρμρμρρρρρρμρ−−==+++−=−−−+−+−+==⋅−−=⋅−=⋅−−−−−++−=⋅−∑∑∑2011-10-132或是平均等待的顾客数。当时，并用式(2-52)代入，可得问题的平均等待人数。当时，并用式(2-55)代入，可得问题的平均等待人数再令，上式就成为的情况，即11021(1)()!(1)mmnmnmmnmnmpmρρρμωρ−−−+−−++−=−μω1m=||1()MMn110211(1)1(1)(1)11nnnnnnnnnpρρρρρμωρρρρ−−+−+−−+−==−−−n→∞||MMm111201()()[]!(1)!!(1)mrmmmrmmmmrmρρμωρρρ−−−==+−−∑1m=||1MM1ρμωρ=−(258)−(257)−2.1.3M/M/m(n)问题2011-10-1332.1.3M/M/m(n)问题求平均队长，k经过一般的运算，结果为：顾客在系统中停留时间s的平均值可从算出，0010()!!kmmnkkkmmmkkpkpkmρρ−===+∑∑12120110()()(1)(1)(1)!!(1)(2-59)()()1!!1−+−+−=−+−=−−−++++−−=−+−∑∑kmnmnmmkkmnmmkmmmmnnkkmkmmkmρρρρρρρρρρω1(1)(1)(2-60)nnsPPωτωμ=+−=+−2011-10-1342.1.3M/M/m(n)问题3.系统运行性能参数为：（推导过程详见书P38—42页）。10000(),!!kmNmNkekkkkmmmkSkPkPkPkmρλρ−====⋅==+∑∑∑队列长度(1)(;1)qeennkPLPWλλλμλ=−−=−=排队等待长度,1SWμ=+系统逗留时间11021(1)(),!(1)mmnmnmPmnmnmWmρρρμρ−−−+−−++−=−排队等待时间2011-10-1312.1.3M/M/m(n)问题3.系统运行性能参数为：系统效率η：用户数km时，窗口占用率k/m；当k≥m时，窗口占用率1。ρ=λ/(mμ)，则系统效率η为01001,1,(1),(1),mnkkkkmmenPmPkPPmPPmλρμλρμηρλρμ−==⎧==≠−⎪⎪⎪===−⎪=+⎨⎪=−⎪⎪=−=⎪⎩∑∑模型M/M/m，多窗口不拒绝模型M/M/1，单窗口不拒绝模型M/M/m/m，立即拒绝模型M/M/m/n，延迟拒绝2011-9-2215M/M/m问题例：某售票处有3个售票窗口，顾客到达服从泊松过程，平均到达率λ=0.9人/分钟，售票时长服从负指数分布，μ=0.4人/分钟，顾客到达后排成一队，依次到空闲窗口服务。解：m=3,N=∞，λ=0.9人/分钟，μ=0.4人/分钟。100(),1/[]0.0748!!(1)rmmrrmmNprmρρρ−==∞=+=−∑3.95,sqLkLλμ==+=队列长度30022()2.250.751.70(1)30.25mqmLppmρρρ×===−×排列等待长1.71.890.9qqLWλ===排列等待时间系统时间4.39ssLWλ==ρ=λ/(mμ)=2.25/3=0.751，稳定；Erlang呼叫量a=λ/μ=2.252011-10-131*数据网常用的ErlangC公式„ErlangC公式定义为业务到达需要等待的概率。在M/M/m/n→∞延迟拒绝系统中，令业务量a=λ/μ10[0]!(1)!mWdkmmkaPTaaammk−==+−∑呼叫需要延迟等待时间Td大于t称的条件概率为：[/0]exp[()/],1/WddPTtTmatτμτ=−−=则呼叫需要等待t秒以上概率为：[][0]exp[()/]WdWdPTtPTmatτ=⋅−−2011-10-131解：已知m=20，PW=5%=0.05，每用户a0=0.05erl，(1)利用ErlangC公式，计算得到一个小区的话务强度a=13erl，则一个小区可支持用户N0=13/0.05=260，整个GSM系统可支持总用户数：N=60*N0=15600。ErlangC公式例：一个无线GSM系统，有60个小区，每小区有20个信道，每用户话务量强度为0.05erl，平均每小时呼叫2次。该系统呼叫等待概率为PW=5%的ErlangC系统。求：(1)可支持多少用户？(2)一个呼叫被延迟10秒以上概率为多少？(2)1个