《通信网理论基础》实验二：二次排队问题——M/M/1排队系统的级联一、实验目的M/M/1是最简单的排队系统，其假设到达过程是一个参数为λ的Poisson过程，服务时间是参数为μ的负指数分布，只有一个服务窗口，等待的位置有无穷多个，排队的方式是FIFO。
M/M/1排队系统的稳态分布、平均队列长度，等待时间的分布以及平均等待时间，可通过泊松过程、负指数分布、生灭过程以及Little公式等进行理论上的分析与求解。
本次实验的目标有两个：➢实现M/M/1单窗口无限排队系统的系统仿真，利用事件调度法实现离散事件系统仿真，并统计平均队列长度以及平均等待时间等值，以与理论分析结果进行对比。
➢仿真两个M/M/1级联所组成的排队网络，统计各个队列的平均队列长度与平均系统时间等值，验证Kleinrock有关数据包在从一个交换机出来后，进入下一个交换机时，随机按负指数分布取一个新的长度的假设的合理性。
二、实验原理1、M/M/1排队系统根据排队论的知识我们知道，排队系统的分类是根据该系统中的顾客到达模式、服务模式、服务员数量以及服务规则等因素决定的。
设到达过程是一个参数为λ的Poisson过程，则长度为t的时间内到达k个呼叫的概率)(t P k 服从Poisson 分布，即()()!ktk t P t k eλλ-=，⋅⋅⋅⋅⋅⋅⋅⋅⋅=,2,1,0k ，其中λ>0为一常数，表示了平均到达率或Poisson 呼叫流的强度。
设每个呼叫的持续时间为i τ，服从参数为μ的负指数分布，即其分布函数为{}1,0t P X t e t μ-<=-≥.服务规则采用先进先服务的规则（FIFO ）。
在该M/M/1系统中，设λρμ=，则稳态时的平均队长为[]1E N ρρ=-，顾客的平均等待时间为1T μλ=-。
2、 二次排队网络由两个M/M/1排队系统所组成的级联网络，顾客以参数为λ的泊松过程到达第一个排队系统A ，服务时间为参数为1μ的负指数分布；从A 出来后直接进入第二个排队系统B ，B 的服务时间为参数为2μ的负指数分布，且与A 的服务时间相互独立。
在该级联网络中，如稳态存在，即1λμ<且2λμ<，则两个排队系统相互独立，顾客穿过网络的总时延为各个排队系统的时延之和，即1211T μλμλ=+--。
如将该模型应用于数据包穿越网络的平均时延的计算，假设数据包的包长服从负指数分布，平均包长为b ；排队系统A 的信道速率为1C ，B 的信道速率为2C 。
为保证两次排队的独立性，Kleinrock 假设数据包在从一个交换机出来后，进入下一个交换机时，随机按负指数分布取一个新的长度。
三、 实验内容1、 仿真时序图示例本实验中的排队系统为当顾客到达分布服从负指数分布，系统服务时间也服从负指数分布，单服务台系统，单队排队，按FIFO 方式服务为M/M/1排队系统。
理论上，我们定义服务员结束一次服务或者有顾客到达系统均为一次事件。
ib 为第i 个任何一类事件发生的时间，其时序关系如下图所示。
bi?第i 个任何一类事件发生的时间 ti?第i 个顾客到达类事件发生的时间 ci?第i 个顾客离开类事件发生的时间 Ai?为第i-1个与第i 个顾客到达时间间隔 Di?第i 个顾客排队等待的时间长度 Si?第i 个顾客服务的时间长度顾客平均等待队长()Q n 及平均排队等待时间()d n 的定义为其中，i R 为在时间区间1[,]i i b b -上排队人数i q 乘以该区间长度1()i i b b --。
iD 为第i 个顾客排队等待时间。
2、 仿真设计算法（1）利用负指数分布与泊松过程的关系，产生符合泊松过程的顾客流。
（2）对每个排队系统，分别构建一个顾客到达队列和一个顾客等待队列。
顾客到达后，首先进入到达队列的队尾排队，并检测是否有顾客等待以及是否有服务台空闲，如果无人等待并且有服务员空闲则进入服务状态，否则顾客将进入等待队列的队尾等待。
（3）产生符合负指数分布的随机变量作为每个顾客的服务时间。
（4）当服务员结束一次服务后，就取出等待队列中位于队头的顾客进入服务状态，如果等待队列为空则服务台空闲等待下一位顾客的到来。
（5）顾客结束A系统的服务后，立即进入B系统排队等待服务。
（6）由事件来触发仿真时钟的不断推进。
每发生一次事件，记录下两次事件间隔的时间以及在该时间段内排队的人数。
（7）在排队网络达到稳态时，计算顾客平均系统时间以及平均队长。
3、仿真结果分析（1）分析仿真数据，统计顾客的平均系统时间与平均队长，计算其方差，分析与理论计算结果的吻合程度，验证仿真程序的正确性。
（2）验证Kleinrock假设的合理性。
——假设包长不变，即二次排队不独立，统计平均值与理论值的相近程度。
4、仿真结果分析分析仿真数据，统计顾客的平均等待时间与顾客的平均等待队长，计算其方差，分析与理论计算结果的吻合程度，验证仿真程序的正确性。
四、实验要求1.两人一组，利用MATLAB实现排队网络的仿真模拟。
2.统计给定λ和μ条件下系统的平均队长和平均系统时间，与理论结果进行比对。
3.统计单个系统的平均队长和平均系统时间随λμ的变化曲线。
五、仿真模拟和理论仿真结果的对比1.仿真设计算法（主要函数）利用负指数分布与泊松过程的关系，产生符合泊松过程的顾客流，产生符合负指数分布的随机变量作为每个顾客的服务时间：ArriveInterval=-log(rand(1,SimNum))/Lambda;%到达时间间隔ServeInterval=-log(rand(1,SimNum))/Mu;%服务时间ArriveTime(1)=ArriveInterval(1);%顾客到达时间时间计算SystemTime=LeaveTime-ArriveTime; %各顾客的系统时间WaitTime=SystemTime-ServeInterval;%各顾客的等待时间由事件来触发仿真时钟的不断推进。
每发生一次事件，记录下两次事件间隔的时间以及在该时间段内排队的人数：TimePoint=[ArriveTime,LeaveTime];%系统中顾客数随时间的变化ArriveFlag=zeros(size(TimePoint));%到达时间标志CusNumAvg=sum(CusNumStart.*[IntervalTime 0] )/TimePoint(end); %系统中平均顾客数SysCusNum=zeros(size(TimePoint));QueLengthAvg=sum([0 QueLength].*[IntervalTime 0] )/TimePoint(end);%系统平均等待队长ArriveTime 每个顾客的到达时间LeaveTime 每个顾客的离开时间ArriveInterval 顾客的到达时间间隔ServeInterval 每个顾客的服务时间ArriveNum 到达总人数SimNum 仿真人数SystemTime 每个人的系统时间SystemTimeAvg 平均系统时间WaitTime 排队等待时间WaitTimeAvg 平均排队等待时间SysCusNum 系统中的顾客人数IntervalTime 事件间隔时间CusNumStart 系统中的顾客数？CusNumAvg CusNum_avg系统中的平均顾客数QueLengthAvg QueLength_avg平均等待队长2.算法的流程图3.仿真结果分析设置Lambda=0.5，Mu=0.9，顾客的平均等待时间与顾客的平均等待队长，计算其方差如下：从上表可以看出，通过这种模型和方法仿真的结果和理论值十分接近，增加仿真顾客数时，可以得到更理想的结果。
当仿真人数超过100000人时，仿真结果与理论结果已经十分接近。
在误差允许的范围内，认为相符。
实验结果截图如下（SimNum分别为100、1000、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);ArriveNum=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;for i=2:SimNumArriveTime(i)=ArriveTime(i-1)+ArriveInterval(i);ArriveNum(i)=i;endLeaveTime(1)=ArriveTime(1)+ServeInterval(1);%顾客离开时间LeaveNum(1)=1;for i=2:SimNumif LeaveTime(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;%各顾客的等待时间WaitTimeAvg=mean(WaitTime);TimePoint=[ArriveTime,LeaveTime];%系统中顾客数随时间的变化TimePoint=sort(TimePoint);ArriveFlag=zeros(size(TimePoint));%到达时间标志SysCusNum=zeros(size(TimePoint));temp=2;SysCusNum(1)=1;for i=2:length(TimePoint)if (temp<=length(ArriveTime))&&(TimePoint(i)==ArriveTime(temp)) SysCusNum(i)=SysCusNum(i-1)+1;temp=temp+1;ArriveFlag(i)=1;elseSysCusNum(i)=SysCusNum(i-1)-1;endend%系统中平均顾客数计算IntervalTime=zeros(size(TimePoint));IntervalTime(1)=ArriveTime(1);for i=2:length(TimePoint)IntervalTime(i)=TimePoint(i)-TimePoint(i-1);endCusNumStart=[0 SysCusNum];CusNumAvg=sum(CusNumStart.*[IntervalTime 0] )/TimePoint(end);%系统中平均顾客数QueLength=zeros(size(SysCusNum));for i=1:length(SysCusNum)if SysCusNum(i)>=2QueLength(i)=SysCusNum(i)-1;elseQueLength(i)=0;endendQueLengthAvg=sum([0 QueLength].*[IntervalTime 0] )/TimePoint(end);%系统平均等待队长%仿真图figure(1);set(1,'position',[0,0,1000,700],'Color',[1 1 1]);subplot(2,2,1);% title('各顾客到达时间和离去时间');stairs([0 ArriveNum],[0 ArriveTime],'r');hold on;stairs([0 LeaveNum],[0 LeaveTime],'g');legend('到达时间','离去时间');hold off;title('各顾客到达时间和离去时间');xlabel('顾客数');ylabel('时间');subplot(2,2,2);stairs(TimePoint,SysCusNum,'r')title('系统等待队长分布');xlabel('时间');ylabel('队长');subplot(2,2,3);stairs([0 ArriveNum],[0 WaitTime],'r');hold on;stairs([0 LeaveNum],[0 SystemTime],'g');hold off;title('各顾客在系统中的等待时间和系统时间');legend('等待时间','系统时间');xlabel('顾客数');ylabel('时间');%仿真值与理论值比较disp(['理论平均系统时间SystemTimeAvg=',num2str(1/(Mu-Lambda))]);disp(['理论平均等待时间WaitTimeAvg=',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)]);disp(['仿真系统中平均等待队长QueLengthAvg=',num2str(QueLengthAvg)]);六、单个系统的平均队长和平均系统时间随λ/μ的变化曲线1.实现原理默认仿真人数为100000人，μ为0.5，故只需要λ变化就可以使得λ/μ都变化。