北邮二次排队问题-MM1排队系统的级联实验报告

通信网理论基础实验报告实验一：二次排队问题——M/M/1排队系统的级联一、实验目的M/M/1是最简单的排队系统，其假设到达过程是一个参数为的Poisson过程，服务时间是参数为的负指数分布，只有一个服务窗口，等待的位置有无穷多个，排队的方式是FIFO。M/M/1排队系统的稳态分布、平均队列长度，等待时间的分布以及平均等待时间，可通过泊松过程、负指数分布、生灭过程以及Little公式等进行理论上的分析与求解。本次实验的目标有两个：实现M/M/1单窗口无限排队系统的系统仿真，利用事件调度法实现离散事件系统仿真，并统计平均队列长度以及平均等待时间等值，以与理论分析结果进行对比。仿真两个M/M/1级联所组成的排队网络，统计各个队列的平均队列长度与平均系统时间等值，验证Kleinrock有关数据包在从一个交换机出来后，进入下一个交换机时，随机按负指数分布取一个新的长度的假设的正确性。二、实验原理M/M/1排队系统根据排队论的知识我们知道，排队系统的分类是根据该系统中的顾客到达模式、服务模式、服务员数量以及服务规则等因素决定的。设到达过程是一个参数为的Poisson过程，则长度为的时间内到达个呼叫的概率服从Poisson分布，即，，其中>0为一常数，表示了平均到达率或Poisson呼叫流的强度。设每个呼叫的持续时间为，服从参数为的负指数分布，即其分布函数为.服务规则采用先进先服务的规则（FIFO）。在该M/M/1系统中，设，则稳态时的平均队长为，顾客的平均等待时间为。二次排队网络由两个M/M/1排队系统所组成的级联网络，顾客以参数为的泊松过程到达第一个排队系统A，服务时间为参数为的负指数分布；从A出来后直接进入第二个排队系统B，B的服务时间为参数为的负指数分布，且与A的服务时间相互独立。在该级联网络中，如稳态存在，即且，则两个排队系统相互独立，顾客穿过网络的总时延为各个排队系统的时延之和，即。如将该模型应用于数据包穿越网络的平均时延的计算，假设数据包的包长服从负指数分布，平均包长为；排队系统A的信道速率为，B的信道速率为。为保证两次排队的独立性，Kleinrock假设数据包在从一个交换机出来后，进入下一个交换机时，随机按负指数分布取一个新的长度。三、实验内容采用的语言：MATLAB数据结构：基本矩阵计算，基本数组计算主要函数：1、产生泊松流顾客和满足负指数分布的服务时间Interval_Arrive_a=exprnd(1/Lambda,1,Simtotal);%产生泊松流Interval_Serve_a=exprnd(1/Mu_a,1,Simtotal);Interval_Serve_b=exprnd(1/Mu_b,1,Simtotal);2、系统a的到达人数和离去人数（系统b同理）ArriveNum_a(1)=1;fori=2:Simtotalt_Arrive_a(i)=t_Arrive_a(i-1)+Interval_Arrive_a(1)ArriveNum_a(i)=i;endt_Leave_a(1)=t_Arrive_a(1)+Interval_Serve_a(1);%顾客离开时间LeaveNum_a(1)=1;fori=2:Simtotalift_Leave_a(i-1)<t_Arrive_a(i)t_Leave_a(i)=t_Arrive_a(i)+Interval_Serve_a(i);elset_Leave_a(i)=t_Leave_a(i-1)+Interval_Serve_a(i);endLeaveNum_a(i)=i;End在系统a中的顾客数（系统b同理）CusNum_a(1)=1;fori=2:length(Timepoint_a)if(temp<=length(t_Arrive_a))&&(Timepoint_a(i)==t_Arrive_a(temp))CusNum_a(i)=CusNum_a(i-1)+1;temp=temp+1;ArriveFlag_a(i)=1;elseCusNum_a(i)=CusNum_a(i-1)-1;End%系统中平均顾客数计算Time_interval_a=zeros(size(Timepoint_a));Time_interval_a(1)=t_Arrive_a(1);fori=2:length(Timepoint_a)Time_interval_a(i)=Timepoint_a(i)-Timepoint_a(i-1);endCusNum_fromStart_a=[0CusNum_a];CusNum_avg_a=sum(CusNum_fromStart_a.*[Time_interval_a0])/Timepoint_a(end);系统a排队人数（系统b同理）QueLength_a=zeros(size(CusNum_a));fori=1:length(CusNum_a)ifCusNum_a(i)>=2QueLength_a(i)=CusNum_a(i)-1;elseQueLength_a(i)=0;endendQueLength_avg_a=sum([0QueLength_a].*[Time_interval_a0])/Timepoint_a(end);%系统平均等待队长a系统和b系统的关系函数Interval_Arrive_b(1)=t_Leave_a(1);fori=2:SimtotalInterval_Arrive_b(i)=t_Leave_a(i)-t_Leave_a(i-1)endInterval_Serve_b=exprnd(1/Mu_b,1,Simtotal);fori=1:Simtotalt_Arrive_b(i)=t_Leave_a(i);ArriveNum_b(i)=i;end建立总系统的所有事件事件以及对应系统人数的矩阵A=[t_Arrive_a;ArriveNum_a;zeros(1,Simtotal);zeros(1,Simtotal)];B=[t_Leave_a;zeros(1,Simtotal);LeaveNum_a;zeros(1,Simtotal)];C=[t_Leave_b;zeros(1,Simtotal);zeros(1,Simtotal);LeaveNum_b];A=sortrows(A');B=sortrows(B');C=sortrows(C');为每个事件断点配置a、b系统到达和离去人数fori=1:Simtotalb=B(:,1);t=find(b<=A(i,1));j=length(t);ifj==0A(i,3)=0;elseA(i,3)=B(j,3);endEnd删除重复的事件断点fori=2:(3*Simtotal)ifD(1,i)==D(1,i-1)D(:,i)=[];endEnd根据各系统到达离去人数求出系统总停留人数CusNum=zeros(1,length(D));fori=1:length(D)if(D(2,i)-D(3,i))>=2CusNum(i)=D(2,i)-D(3,i)-1;elseCunNum(i)=0;endendfori=1:length(D)if(D(3,i)-D(4,i))>=2CusNum(i)=CusNum(i)+D(3,i)-D(4,i)-1;elseCusNum(i)=CusNum(i);endendTimepoint=D(1,:);10、建立画图窗口并生成12个figure(1);set(1,'position',[0,0,1300,700]);subplot(3,4,1);title('a各顾客到达时间和离去时间');stairs([0ArriveNum_a],[0t_Arrive_a],'b');holdon;stairs([0LeaveNum_a],[0t_Leave_a],'y');legend('到达时间','离去时间');holdoff;11、理论和仿真数值比较举例disp(['理论平均停留系统时间t_Wait_avg=',num2str((1/(Mu_a-Lambda))+(1/(Mu_b-Lambda)))]);disp(['仿真平均停留系统时间t_Wait_avg=',num2str(t_Wait_avg_a+t_Wait_avg_b)]);开始算法流程图：开始设置顾客总数，到达率和服务率设置顾客总数，到达率和服务率产生泊松流顾客产生泊松流顾客第一个顾客到达时间确定，由负指数分布计算下一个顾客第一个顾客到达时间确定，由负指数分布计算下一个顾客前一个顾客（i-1）是否离开系统a前一个顾客（i-1）是否离开系统a排队排队否否是是第i个顾客第i个顾客在系统a的等待时间、服务时间、离开时间 到达b系统时间确定到达b系统时间确定前一个顾客（i-1）是否离开系统b前一个顾客（i-1）是否离开系统b排队排队 否否是是否是结束输出结果顾客流结束？第i个顾客在系统b的等待时间、服务时间、离开时间 否是结束输出结果顾客流结束？第i个顾客在系统b的等待时间、服务时间、离开时间 仿真结果与分析M/M/1系统仿真与给定λ和μ_a,μ_b条件下a、b系统及总系统的到达离去时间，等待队长，系统顾客数，排队时间和停留时间分布：λ=0.3，μ_a=μ_b=0.8，顾客流总数为100λ=0.3，μ_a=μ_b=0.8，顾客数为1000(3)λ=0.3，μ_a=μ_b=0.8，顾客数为2000λ=0.2，μ_a=μ_b=0.9，顾客数为1000λ=0.4，μ_a=μ_b=0.5，顾客数为1000平均队长和平均系统时间随λ/μ的变化曲线实验结论1.从上述五组数据比较可以看出，运用控制变量法。对于仿真顾客总数，仿真顾客数越大，仿真值越接近理论值，当顾客数为2000时基本仿真和理论值基本相等，由于再增加人数程序运行时间将会很长，因此就做到2000人数的仿真。因此尽可能地增加顾客数是到达稳态的一个途径。对于到达率和服务率的比例，当到达率远小于服务率时，全系统平均队长和平均系统时间都比较小，容易达到稳态。到达率与服务率特别接近时，全系统平均队长和平均系统时间都比较大，系统仿真误差比较大，而且很难达到稳态。由仿真图得出，平均队长和平均等待时间均随λ的增大而增大，随μ的增大而减小。2.从平均队长和平均系统时间随λ/μ的变化曲线可以看出，平均队长和平均系统时间和λ/μ的值呈正相关增长，随着λ/μ的值不断变大，平均队长和平均系统时间呈类似于指数增长趋向于无穷大。实验问题和难点a，b系统级联衔接的问题原因在于b系统的顾客流来自于a，并不属于泊松分布，因此在程序中直接将a的离开时间设置为b的到达时间。计算全系统的顾客数和排队顾客数的问题由于每个事件的时间断点只提供到达a系统人数、离开a（到达b）系统人数、离开b系统人数三个中的一个，而计算全系统的顾客数和排队长需要知道每个时间断点的三个值，因此确定一个时间对应的另外两个值是本实验的最大难点。通过分析时间轴，我建立了三个矩阵对应三种断点，从而确定了这个时间点对应的另外两个值，然后将三个矩阵合并成一个时间轴的矩阵，排序，通过将a系统人数、离开a（到达b）系统人数、离开b系统人数三个互相的运算从而计算出全系统的顾客数和排队长。3、建立了2中的矩阵后仍不知道如何找出对应时间点的另外两个值，经过画时间轴通过sortrow将每行按小到大排序，再用find(a<)函数找出这个时间点对应的区间，照着另外两个矩阵相同位置便可找出另外的两个值4、仿真出现问题仿真后发现全系统顾客数图形为一个三角形这显然是不符合情理的，为此做了大量的排查，发现是由于B矩阵中的一个函数的B手误打成了b，经过修正图形显示终于正常在计算顾客平均等待队长时不知如何计算将仿真的数据转换为仿真值，查阅教程资料后得到：顾客平均等待队长及平均排队等待时间的定义为其中，为在时间区间上排队人数乘以该区间长度。为第i个顾客排队等待时间。6、关于稳态的确定从实验结果中可以看出，测试的顾客人数越多，仿真值越接近理论值，在图表中当排队长和顾客数的曲线分布接近平稳之后即可认为系统已达到稳态。实验心得此次实验我们做的是两个M/M/1系统的级联问题，较之单个系统在编程难度上有了很大的提升，因此我们在编写程序过程中也遇到了很多麻烦。同时也学习了很多关于MATLAB的基本语句函数和算法思想。在实际操作过程中，知道了用矩阵数组运算代替for循环可以加快运算速度，这对