信息与通信工程学院通信网性能分析基础实验报告专业信息工程班级姓名学号实验二:M/M/1排队系统一、实验目的M/M/1是最简单的排队系统,其假设到达过程是一个参数为λ的Poisson 过程,服务时间是参数为μ的负指数分布,只有一个服务窗口,等待的位置有无穷多个,排队的方式是FIFO 。
M/M/1排队系统的稳态分布、平均队列长度,待时间的分布以及平均等待时间,可通过泊松过程、负指数分布、生灭过程以及Little 公式等进行理论上的分析与求解。
本次实验要求实现M/M/1单窗口无限排队系统的系统仿真,利用事件调度法实现离散事件系统仿真,并统计平均队列长度以及平均等待时间等值,以与理论分析结果进行对比。
二、实验原理根据排队论的知识我们知道,排队系统的分类是根据该系统中的顾客到达模式、服务模式、服务员数量以及服务规则等因素决定的。
1、 顾客到达模式设到达过程是一个参数为λ的Poisson 过程,则长度为t 的时间内到达k 个呼叫的概率)(t P k 服从Poisson 分布,即etk k k t t p λλ-=!)()(,⋅⋅⋅⋅⋅⋅⋅⋅⋅=,2,1,0k ,其中λ>0为一常数,表示了平均到达率或Poisson 呼叫流的强度。
2、 服务模式设每个呼叫的持续时间为i τ,服从参数为μ的负指数分布,即其分布函数为{}1,0t P X t e t μ-<=-≥3、 服务规则先进先服务的规则(FIFO ) 4、 理论分析结果在该M/M/1系统中,设λρμ=,则稳态时的平均等待队长为1Q ρλρ=-,顾客的平均等待时间为T ρμλ=-。
三、 实验内容1、 仿真时序图示例本实验中的排队系统为当顾客到达分布服从负指数分布,系统服务时间也服从负指数分布,单服务台系统,单队排队,按FIFO 方式服务为M/M/1排队系统。
理论上,我们定义服务员结束一次服务或者有顾客到达系统均为一次事件。
i b 为第i 个任何一类事件发生的时间,其时序关系如下图所示。
bi 第i 个任何一类事件发生的时间 ti 第i 个顾客到达类事件发生的时间 ci 第i 个顾客离开类事件发生的时间 Ai 为第i-1个与第i 个顾客到达时间间隔 Di 第i 个顾客排队等待的时间长度 Si 第i 个顾客服务的时间长度顾客平均等待队长()Q n 及平均排队等待时间()d n 的定义为1011()()()Tni i Q n Q n Q t dt R T T ===≈∑⎰其中,i R 为在时间区间1[,]i i b b -上排队人数i q 乘以该区间长度1()i i b b --。
11()()ni i d n D n D n ===∑i D 为第i 个顾客排队等待时间。
2、 实验结果:(1) 利用负指数分布与泊松过程的关系,产生符合泊松过程的顾客流。
function r = Createpoiss(lambda,m,n)%原理说明:泊松过程时间间隔概率密度:f(x)=lambda*exp(-lambda*x); % 分布函数:y=F(x)=1-exp(-lambda*x);% 因为顾客流服从泊松分布,其对应的时间间隔序列f(x)服从均值为1/lambda 的指数分布temp=rand(m,n); %生成均匀分布的m*n随机数r=-log(temp)/lambda; %生成泊松过程(e为底的对数)(2)分别构建一个顾客到达队列和一个顾客等待队列。
Arrive_time=zeros(1,Total); %顾客到来时间变量,加快速度;Leave_time=zeros(1,Total); %顾客离去时间变量Arrive_num=zeros(1,Total); %顾客到达人数变量Leave_num=zeros(1,Total); %顾客离去人数变量(3)产生符合负指数分布的随机变量作为每个顾客的服务时间。
function r = Createpoiss(lambda,m,n)%原理说明:泊松过程时间间隔概率密度:f(x)=lambda*exp(-lambda*x);% 分布函数:y=F(x)=1-exp(-lambda*x);% 因为顾客流服从泊松分布,其对应的时间间隔序列f(x)服从均值为1/lambda的指数分布temp=rand(m,n); %生成均匀分布的m*n随机数r=-log(temp)/lambda; %生成泊松过程(e为底的对数)(4)当服务员结束一次服务后,就取出等待队列中位于队头的顾客进入服务状态,如果等待队列为空则服务台空闲等待下一位顾客的到来。
function[Timepoint,NumInSys]=Create_Timepoint_NumInSys(Arrive_time,Leave_time)%系统中顾客数随时间的变化;%输入:% Arrive_time为到达时间点;% Leave_time为离开时间点;%输出:% Timepoint返回按时间排序的到达和离开的时间点;% NumInSys返回与Timepoint对应的系统中顾客数;Timepoint=[Arrive_time,Leave_time];Timepoint=sort(Timepoint);%对到达和离开时间排序NumInSys=zeros(size(Timepoint));temp=2;NumInSys(1)=1;fori=2:length(Timepoint)if (temp<=length(Arrive_time))&&(Timepoint(i)==Arrive_time(temp))NumInSys(i)=NumInSys(i-1)+1;temp=temp+1;elseNumInSys(i)=NumInSys(i-1)-1;endend(5)由事件来触发仿真时钟的不断推进。
每发生一次事件,记录下两次事件间隔的时间以及在该时间段内排队的人数。
%各顾客到来时间;Arrive_time(1)=Arrive_interval(1);%初始化Arrive_num(1)=1;fori=2:TotalArrive_time(i)=Arrive_time(i-1)+Arrive_interval(i);%下一个顾客到达时间等于前一个顾客到达的时间加上到达间隔时间Arrive_num(i)=i;end%Arrive_time%各顾客离开时间;Leave_time(1)=Arrive_time(1)+Serve_interval(1);Leave_num(1)=1;fori=2:Totalif Leave_time(i-1)<Arrive_time(i) %前一个顾客在下一个顾客到来之前离开Leave_time(i)=Arrive_time(i)+Serve_interval(i);%则下一个顾客的离开时间等于他到达的时间加上服务间隔时间elseLeave_time(i)=Leave_time(i-1)+Serve_interval(i);%如果前一个顾客在下一个顾客到来之时或之后才离开end %则下一个顾客的离开时间等于前一个顾客离开时间加上服务间隔时间Leave_num(i)=i; %离开顾客数增加一名end%Leave_time(6)在系统达到稳态时,计算系统的平均等待时间以及平均等待队长。
Wait_time=Leave_time-Arrive_time; %各个顾客在系统中的等待时间Queue_time=Wait_time-Serve_interval; %各个顾客的排队时间Wait_time_avg=mean(Wait_time); %平均系统等待时间Queue_time_avg=mean(Queue_time); %平均排队时间[Timepoint,NumInSys]=Create_Timepoint_NumInSys(Arrive_time,Leave_time);%调用timepoint函数%说明:系统中平均顾客数。
% 因为Timepoint不是均匀分布的,所以不能用各个时间点的人数相加再除以总时间点个数的方法。
% 过程具有各态历经性,可用计算时间平均来代替统计平均;Time_interval=zeros(size(Timepoint));Time_interval(1)=Arrive_time(1);fori=2:length(Timepoint)Time_interval(i)=Timepoint(i)-Timepoint(i-1);endNumInSys_fromStart=[0 NumInSys];NumInSys_avg=sum(NumInSys_fromStart.*[Time_interval 0] )/Timepoint(end);%平均队列长度NumInQue=zeros(size(NumInSys));fori=1:length(NumInSys)ifNumInSys(i)>=2NumInQue(i)=NumInSys(i)-1;elseNumInQue(i)=0;endendNumInQue_avg=sum([0 NumInQue].*[Time_interval 0] )/Timepoint(end);流程图:统计给定λ和μ条件下系统的平均队列长度和平均等待时间,与理论结果进行比对:仿真平均逗留时间Wait_time_avg为:3.3053仿真平均排队时间Queue_time_avg为:2.3244仿真系统中平均顾客数为:2.3464仿真系统中平均排队顾客数为:1.6501理论平均逗留时间Wait_time_avg为:3.3333理论平均排队时间Wait_time_avg为:2.3333理论系统中平均顾客数为:2.3333理论系统中平均排队顾客数为:1.6333统计平均队列长度和平均等待时间随λ和μ的变化曲线:到来:离去:3、实验结果分析:由实验结果可看到,仿真值和理论值相近,顾客到达分布服从负指数分布,系统服务时间也服从负指数分布,单服务台系统,单队排队,按FIFO方式服务为M/M/1排队系统。
在实验中区顾客总数为5000,顾客到达率为0.7,服务率为1。
遇到的问题:在做顾客离开的时间这个部分的时候时序没有判断好,导致理论值和仿真值不符。
比如:前一个顾客在下一个顾客到来之前离开时,下一个顾客的离开时间等于他到达的时间加上服务间隔时间;如果前一个顾客在下一个顾客到来之时或之后才离开,则下一个顾客的离开时间等于前一个顾客离开时间加上服务间隔时间。
还有就是因为Timepoint不是均匀分布的,所以不能用各个时间点的人数相加再除以总时间点个数的方法。
因为需要构造泊松过程和时间点以及M/M/1程序,所以编了3个部分,见3个m文件。