1、北邮通信网性能分析实验二MM1排队系统实验分析报告通信网理论基础实验二:二次排队问题M/M/1排队系统的级联一、 实验目的M/M/1是最简单的排队系统,其假设到达过程是一个参数为的Poisson过程,服务时间是参数为的负指数分布,只有一个服务窗口,等待的位置有无穷多个,排队的方式是FIFO。M/M/1排队系统的稳态分布、平均队列长度,等待时间的分布以及平均等待时间,可通过泊松过程、负指数分布、生灭过程以及Little公式等进行理论上的分析与求解。本次实验的目标有两个: 实现M/M/1单窗口无限排队系统的系统仿真,利用事件调度法实现离散事件系统仿真,并统计平均队列长度以及平均等待时间等值,以与理
2、论分析结果进行对比。 仿真两个M/M/1级联所组成的排队网络,统计各个队列的平均队列长度与平均系统时间等值,验证Kleinrock有关数据包在从一个交换机出来后,进入下一个交换机时,随机按负指数分布取一个新的长度的假设的合理性。二、 实验原理1、 M/M/1排队系统根据排队论的知识我们知道,排队系统的分类是根据该系统中的顾客到达模式、服务模式、服务员数量以及服务规则等因素决定的。设到达过程是一个参数为的Poisson过程,则长度为的时间内到达个呼叫的概率服从Poisson分布,即,其中0为一常数,表示了平均到达率或Poisson呼叫流的强度。设每个呼叫的持续时间为,服从参数为的负指数分布,即其
3、分布函数为.服务规则采用先进先服务的规则(FIFO)。在该M/M/1系统中,设,则稳态时的平均队长为,顾客的平均等待时间为。2、 二次排队网络由两个M/M/1排队系统所组成的级联网络,顾客以参数为的泊松过程到达第一个排队系统A,服务时间为参数为的负指数分布;从A出来后直接进入第二个排队系统B,B的服务时间为参数为的负指数分布,且与A的服务时间相互独立。在该级联网络中,如稳态存在,即且,则两个排队系统相互独立,顾客穿过网络的总时延为各个排队系统的时延之和,即。如将该模型应用于数据包穿越网络的平均时延的计算,假设数据包的包长服从负指数分布,平均包长为;排队系统A的信道速率为,B的信道速率为。为保证
4、两次排队的独立性,Kleinrock假设数据包在从一个交换机出来后,进入下一个交换机时,随机按负指数分布取一个新的长度。三、 实验内容1、 仿真时序图示例本实验中的排队系统为当顾客到达分布服从负指数分布,系统服务时间也服从负指数分布,单服务台系统,单队排队,按FIFO方式服务为M/M/1排队系统。理论上,我们定义服务员结束一次服务或者有顾客到达系统均为一次事件。为第i个任何一类事件发生的时间,其时序关系如下图所示。bi?第i个任何一类事件发生的时间ti?第i个顾客到达类事件发生的时间ci?第i个顾客离开类事件发生的时间Ai?为第i-1个与第i个顾客到达时间间隔Di?第i个顾客排队等待的时间长度
5、Si?第i个顾客服务的时间长度顾客平均等待队长及平均排队等待时间的定义为其中,为在时间区间上排队人数乘以该区间长度。为第i个顾客排队等待时间。2、 仿真设计算法(1)利用负指数分布与泊松过程的关系,产生符合泊松过程的顾客流。(2)对每个排队系统,分别构建一个顾客到达队列和一个顾客等待队列。顾客到达后,首先进入到达队列的队尾排队,并检测是否有顾客等待以及是否有服务台空闲,如果无人等待并且有服务员空闲则进入服务状态,否则顾客将进入等待队列的队尾等待。(3)产生符合负指数分布的随机变量作为每个顾客的服务时间。(4)当服务员结束一次服务后,就取出等待队列中位于队头的顾客进入服务状态,如果等待队列为空则
6、服务台空闲等待下一位顾客的到来。(5)顾客结束A系统的服务后,立即进入B系统排队等待服务。(6)由事件来触发仿真时钟的不断推进。每发生一次事件,记录下两次事件间隔的时间以及在该时间段内排队的人数。(7)在排队网络达到稳态时,计算顾客平均系统时间以及平均队长。3、 仿真结果分析(1)分析仿真数据,统计顾客的平均系统时间与平均队长,计算其方差,分析与理论计算结果的吻合程度,验证仿真程序的正确性。(2)验证Kleinrock假设的合理性。假设包长不变,即二次排队不独立,统计平均值与理论值的相近程度。4、 仿真结果分析分析仿真数据,统计顾客的平均等待时间与顾客的平均等待队长,计算其方差,分析与理论计算
7、结果的吻合程度,验证仿真程序的正确性。四、 实验要求1. 两人一组,利用MATLAB实现排队网络的仿真模拟。2. 统计给定和条件下系统的平均队长和平均系统时间,与理论结果进行比对。3. 统计单个系统的平均队长和平均系统时间随的变化曲线。五、 仿真模拟和理论仿真结果的对比1. 仿真设计算法(主要函数)利用负指数分布与泊松过程的关系,产生符合泊松过程的顾客流,产生符合负指数分布的随机变量作为每个顾客的服务时间:ArriveInterval=-log(rand(1,SimNum)/Lambda;%到达时间间隔ServeInterval=-log(rand(1,SimNum)/Mu;%服务时间Arri
8、veTime(1)=ArriveInterval(1);%顾客到达时间时间计算SystemTime=LeaveTime-ArriveTime;%各顾客的系统时间WaitTime=SystemTime-ServeInterval;%各顾客的等待时间由事件来触发仿真时钟的不断推进。每发生一次事件,记录下两次事件间隔的时间以及在该时间段内排队的人数:TimePoint=ArriveTime,LeaveTime;%系统中顾客数随时间的变化ArriveFlag=zeros(size(TimePoint);%到达时间标志CusNumAvg=sum(CusNumStart.*IntervalTime0)/T
9、imePoint(end);%系统中平均顾客数SysCusNum=zeros(size(TimePoint);QueLengthAvg=sum(0QueLength.*IntervalTime0)/TimePoint(end);%系统平均等待队长ArriveTime每个顾客的到达时间LeaveTime每个顾客的离开时间ArriveInterval顾客的到达时间间隔ServeInterval每个顾客的服务时间ArriveNum到达总人数SimNum仿真人数SystemTime每个人的系统时间SystemTimeAvg平均系统时间WaitTime排队等待时间WaitTimeAvg平均排队等待时间S
10、ysCusNum系统中的顾客人数IntervalTime事件间隔时间CusNumStart系统中的顾客数?CusNumAvgCusNum_avg系统中的平均顾客数QueLengthAvgQueLength_avg平均等待队长2. 算法的流程图3. 仿真结果分析设置Lambda=0.5,Mu=0.9,顾客的平均等待时间与顾客的平均等待队长,计算其方差如下:从上表可以看出,通过这种模型和方法仿真的结果和理论值十分接近,增加仿真顾客数时,可以得到更理想的结果。当仿真人数超过100000人时,仿真结果与理论结果已经十分接近。在误差允许的范围内,认为相符。实验结果截图如下(SimNum分别为100、10
11、00、10000、100000)100人仿真结果与理论结果对比1000人仿真结果与理论对比10000人仿真结果与理论结果对比100000人仿真结果与理论对比1000000人仿真结果与理论结果对比4. 实验源代码语言:matlab代码:clear;clc;%M/M/1排队系统仿真SimNum=input(请输入仿真顾客总数SimNum=);%仿真顾客总数;Lambda=input(请输入到达率Lambda=);%到达率LambdaMu=input(请输入服务率Mu=);%到达率MuArriveTime=zeros(1,SimNum);LeaveTime=zeros(1,SimNum);Arriv
12、eNum=zeros(1,SimNum);LeaveNum=zeros(1,SimNum);ArriveInterval=-log(rand(1,SimNum)/Lambda;%到达时间间隔ServeInterval=-log(rand(1,SimNum)/Mu;%服务时间ArriveTime(1)=ArriveInterval(1);%顾客到达时间ArriveNum(1)=1;fori=2:SimNumArriveTime(i)=ArriveTime(i-1)+ArriveInterval(i);ArriveNum(i)=i;endLeaveTime(1)=ArriveTime(1)+Ser
13、veInterval(1);%顾客离开时间LeaveNum(1)=1;fori=2:SimNumifLeaveTime(i-1)ArriveTime(i)LeaveTime(i)=ArriveTime(i)+ServeInterval(i);elseLeaveTime(i)=LeaveTime(i-1)+ServeInterval(i);endLeaveNum(i)=i;endSystemTime=LeaveTime-ArriveTime;%各顾客的系统时间SystemTimeAvg=mean(SystemTime);WaitTime=SystemTime-ServeInterval;%各顾客
14、的等待时间WaitTimeAvg=mean(WaitTime);TimePoint=ArriveTime,LeaveTime;%系统中顾客数随时间的变化TimePoint=sort(TimePoint);ArriveFlag=zeros(size(TimePoint);%到达时间标志SysCusNum=zeros(size(TimePoint);temp=2;SysCusNum(1)=1;fori=2:length(TimePoint)if(temp=2QueLength(i)=SysCusNum(i)-1;elseQueLength(i)=0;endendQueLengthAvg=sum(0
15、QueLength.*IntervalTime0)/TimePoint(end);%系统平均等待队长%仿真图figure(1);set(1,position,0,0,1000,700,Color,111);subplot(2,2,1);%title(各顾客到达时间和离去时间);stairs(0ArriveNum,0ArriveTime,r);holdon;stairs(0LeaveNum,0LeaveTime,g);legend(到达时间,离去时间);holdoff;title(各顾客到达时间和离去时间);xlabel(顾客数);ylabel(时间);subplot(2,2,2);stairs
16、(TimePoint,SysCusNum,r)title(系统等待队长分布);xlabel(时间);ylabel(队长);subplot(2,2,3);stairs(0ArriveNum,0WaitTime,r);holdon;stairs(0LeaveNum,0SystemTime,g);holdoff;title(各顾客在系统中的等待时间和系统时间);legend(等待时间,系统时间);xlabel(顾客数);ylabel(时间);%仿真值与理论值比较disp(理论平均系统时间SystemTimeAvg=,num2str(1/(Mu-Lambda);disp(理论平均等待时间WaitTim
17、eAvg=,num2str(Lambda/(Mu*(Mu-Lambda);disp(理论系统中平均顾客数CusNumAvg=,num2str(Lambda/(Mu-Lambda);disp(理论系统中平均等待队长QueLengthAvg=,num2str(Lambda*Lambda/(Mu*(Mu-Lambda);disp(仿真平均系统时间SystemTimeAvg=,num2str(SystemTimeAvg)disp(仿真平均等待时间WaitTimeAvg=,num2str(WaitTimeAvg)disp(仿真系统中平均顾客数CusNumAvg=,num2str(CusNumAvg);d
18、isp(仿真系统中平均等待队长QueLengthAvg=,num2str(QueLengthAvg);六、 单个系统的平均队长和平均系统时间随/的变化曲线1. 实现原理默认仿真人数为100000人,为0.5,故只需要变化就可以使得/都变化。主函数调用功能函数的平均队长和平均系统时间的结果进行绘图。此实验中,去0.10.8,故/取值范围是0.21.6。2. 仿真算法主函数:Mu=0.5;Lambda=0.1:0.001:0.8;x=2.*Lambda;QueLengthAvg=zeros(size(Lambda);SystemTimeAvg=zeros(size(Lambda);fori=1:7
19、00QueLengthAvg(i),SystemTimeAvg(i)=LengthTime(Lambda(i);end%仿真图figure(1);set(1,position,0,0,1000,700,Color,111);subplot(1,2,1);stairs(x,QueLengthAvg,b)title(平均队长分队和/的图像);xlabel(/);ylabel(平均队长);subplot(1,2,2);stairs(x,SystemTimeAvg,y)title(平均系统时间随/的分布);xlabel(/);ylabel(平均系统时间);功能函数:functionQueLengthA
20、vg,SystemTimeAvg=LengthTime(Lambda)%Mu默认为0.5%输入Lambda返回平均队长和平均系统时间%lambda/Mu就是2*lambdaSimNum=100000;Mu=0.5;ArriveTime=zeros(1,SimNum);LeaveTime=zeros(1,SimNum);ArriveNum=zeros(1,SimNum);LeaveNum=zeros(1,SimNum);ArriveInterval=-log(rand(1,SimNum)/Lambda;%到达时间间隔ServeInterval=-log(rand(1,SimNum)/Mu;%服务
21、时间ArriveTime(1)=ArriveInterval(1);%顾客到达时间ArriveNum(1)=1;fori=2:SimNumArriveTime(i)=ArriveTime(i-1)+ArriveInterval(i);ArriveNum(i)=i;endLeaveTime(1)=ArriveTime(1)+ServeInterval(1);%顾客离开时间LeaveNum(1)=1;fori=2:SimNumifLeaveTime(i-1)ArriveTime(i)LeaveTime(i)=ArriveTime(i)+ServeInterval(i);elseLeaveTime(
22、i)=LeaveTime(i-1)+ServeInterval(i);endLeaveNum(i)=i;endSystemTime=LeaveTime-ArriveTime;%各顾客的系统时间SystemTimeAvg=mean(SystemTime);TimePoint=ArriveTime,LeaveTime;%系统中顾客数随时间的变化TimePoint=sort(TimePoint);ArriveFlag=zeros(size(TimePoint);%到达时间标志SysCusNum=zeros(size(TimePoint);temp=2;SysCusNum(1)=1;fori=2:le
23、ngth(TimePoint)if(temp=2QueLength(i)=SysCusNum(i)-1;elseQueLength(i)=0;endendQueLengthAvg=sum(0QueLength.*IntervalTime0)/TimePoint(end);%系统平均等待队长3. 实验结果4. 实验结论从上图可以看出,排队的平均队长和平均系统时间跟/的取值有直接的关系。当/1时,出现了转折,排队人数直线上升。建议实际排队系统中尽量使得/小于1。七、 遇到的问题及解决方法1实验最初设定的人数太少,与理论结果有较大的误差,经过把参数修改为较大的数值之后,就解决了。2.仿真人数设置过多后,比如10000000人后,matlab就会崩溃了。所以数值不能设置的太大。3.排队过程不是很清楚,实验参数设定不好确定。最后通过把到达,离去的时间都设置为一个TimePoint,最后完成了排队时间和人数的计算。八、 实验心得这是一个非常有趣的实验,平时的排队过程,我们通过实验完成仿真,并与理论结果进行对比。在这个实验中,我重新认识了排队过程,到达,离去都作为一个事件去推动。通过本次实验,对matlab有了更深的认识,更加认识到了通信网性能分析课程的重要性,为将来的学习打下坚实的基础。