北郵二次排隊(duì)問題-MM1排隊(duì)系統(tǒng)的級聯(lián)實(shí)驗(yàn)報(bào)告

通信網(wǎng)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)一：二次排隊(duì)問題——M/M/1排隊(duì)系統(tǒng)的級聯(lián)一、實(shí)驗(yàn)?zāi)康腗/M/1是最簡單的排隊(duì)系統(tǒng)，其假設(shè)到達(dá)過程是一個(gè)參數(shù)為的Poisson過程，服務(wù)時(shí)間是參數(shù)為的負(fù)指數(shù)分布，只有一個(gè)服務(wù)窗口，等待的位置有無窮多個(gè)，排隊(duì)的方式是FIFO。M/M/1排隊(duì)系統(tǒng)的穩(wěn)態(tài)分布、平均隊(duì)列長度，等待時(shí)間的分布以及平均等待時(shí)間，可通過泊松過程、負(fù)指數(shù)分布、生滅過程以及Little公式等進(jìn)行理論上的分析與求解。本次實(shí)驗(yàn)的目標(biāo)有兩個(gè)：實(shí)現(xiàn)M/M/1單窗口無限排隊(duì)系統(tǒng)的系統(tǒng)仿真，利用事件調(diào)度法實(shí)現(xiàn)離散事件系統(tǒng)仿真，并統(tǒng)計(jì)平均隊(duì)列長度以及平均等待時(shí)間等值，以與理論分析結(jié)果進(jìn)行對比。仿真兩個(gè)M/M/1級聯(lián)所組成的排隊(duì)網(wǎng)絡(luò)，統(tǒng)計(jì)各個(gè)隊(duì)列的平均隊(duì)列長度與平均系統(tǒng)時(shí)間等值，驗(yàn)證Kleinrock有關(guān)數(shù)據(jù)包在從一個(gè)交換機(jī)出來后，進(jìn)入下一個(gè)交換機(jī)時(shí)，隨機(jī)按負(fù)指數(shù)分布取一個(gè)新的長度的假設(shè)的正確性。二、實(shí)驗(yàn)原理M/M/1排隊(duì)系統(tǒng)根據(jù)排隊(duì)論的知識我們知道，排隊(duì)系統(tǒng)的分類是根據(jù)該系統(tǒng)中的顧客到達(dá)模式、服務(wù)模式、服務(wù)員數(shù)量以及服務(wù)規(guī)則等因素決定的。設(shè)到達(dá)過程是一個(gè)參數(shù)為的Poisson過程，則長度為的時(shí)間內(nèi)到達(dá)個(gè)呼叫的概率服從Poisson分布，即，，其中>0為一常數(shù)，表示了平均到達(dá)率或Poisson呼叫流的強(qiáng)度。設(shè)每個(gè)呼叫的持續(xù)時(shí)間為，服從參數(shù)為的負(fù)指數(shù)分布，即其分布函數(shù)為.服務(wù)規(guī)則采用先進(jìn)先服務(wù)的規(guī)則（FIFO）。在該M/M/1系統(tǒng)中，設(shè)，則穩(wěn)態(tài)時(shí)的平均隊(duì)長為，顧客的平均等待時(shí)間為。二次排隊(duì)網(wǎng)絡(luò)由兩個(gè)M/M/1排隊(duì)系統(tǒng)所組成的級聯(lián)網(wǎng)絡(luò)，顧客以參數(shù)為的泊松過程到達(dá)第一個(gè)排隊(duì)系統(tǒng)A，服務(wù)時(shí)間為參數(shù)為的負(fù)指數(shù)分布；從A出來后直接進(jìn)入第二個(gè)排隊(duì)系統(tǒng)B，B的服務(wù)時(shí)間為參數(shù)為的負(fù)指數(shù)分布，且與A的服務(wù)時(shí)間相互獨(dú)立。在該級聯(lián)網(wǎng)絡(luò)中，如穩(wěn)態(tài)存在，即且，則兩個(gè)排隊(duì)系統(tǒng)相互獨(dú)立，顧客穿過網(wǎng)絡(luò)的總時(shí)延為各個(gè)排隊(duì)系統(tǒng)的時(shí)延之和，即。如將該模型應(yīng)用于數(shù)據(jù)包穿越網(wǎng)絡(luò)的平均時(shí)延的計(jì)算，假設(shè)數(shù)據(jù)包的包長服從負(fù)指數(shù)分布，平均包長為；排隊(duì)系統(tǒng)A的信道速率為，B的信道速率為。為保證兩次排隊(duì)的獨(dú)立性，Kleinrock假設(shè)數(shù)據(jù)包在從一個(gè)交換機(jī)出來后，進(jìn)入下一個(gè)交換機(jī)時(shí)，隨機(jī)按負(fù)指數(shù)分布取一個(gè)新的長度。三、實(shí)驗(yàn)內(nèi)容采用的語言：MATLAB數(shù)據(jù)結(jié)構(gòu)：基本矩陣計(jì)算，基本數(shù)組計(jì)算主要函數(shù)：1、產(chǎn)生泊松流顧客和滿足負(fù)指數(shù)分布的服務(wù)時(shí)間Interval_Arrive_a=exprnd(1/Lambda,1,Simtotal);%產(chǎn)生泊松流Interval_Serve_a=exprnd(1/Mu_a,1,Simtotal);Interval_Serve_b=exprnd(1/Mu_b,1,Simtotal);2、系統(tǒng)a的到達(dá)人數(shù)和離去人數(shù)（系統(tǒng)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);%顧客離開時(shí)間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在系統(tǒng)a中的顧客數(shù)（系統(tǒng)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%系統(tǒng)中平均顧客數(shù)計(jì)算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);系統(tǒng)a排隊(duì)人數(shù)（系統(tǒng)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);%系統(tǒng)平均等待隊(duì)長a系統(tǒng)和b系統(tǒng)的關(guān)系函數(shù)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建立總系統(tǒng)的所有事件事件以及對應(yīng)系統(tǒng)人數(shù)的矩陣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');為每個(gè)事件斷點(diǎn)配置a、b系統(tǒng)到達(dá)和離去人數(shù)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刪除重復(fù)的事件斷點(diǎn)fori=2:(3*Simtotal)ifD(1,i)==D(1,i-1)D(:,i)=[];endEnd根據(jù)各系統(tǒng)到達(dá)離去人數(shù)求出系統(tǒng)總停留人數(shù)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個(gè)figure(1);set(1,'position',[0,0,1300,700]);subplot(3,4,1);title('a各顧客到達(dá)時(shí)間和離去時(shí)間');stairs([0ArriveNum_a],[0t_Arrive_a],'b');holdon;stairs([0LeaveNum_a],[0t_Leave_a],'y');legend('到達(dá)時(shí)間','離去時(shí)間');holdoff;11、理論和仿真數(shù)值比較舉例disp(['理論平均停留系統(tǒng)時(shí)間t_Wait_avg=',num2str((1/(Mu_a-Lambda))+(1/(Mu_b-Lambda)))]);disp(['仿真平均停留系統(tǒng)時(shí)間t_Wait_avg=',num2str(t_Wait_avg_a+t_Wait_avg_b)]);開始算法流程圖：開始設(shè)置顧客總數(shù)，到達(dá)率和服務(wù)率設(shè)置顧客總數(shù)，到達(dá)率和服務(wù)率產(chǎn)生泊松流顧客產(chǎn)生泊松流顧客第一個(gè)顧客到達(dá)時(shí)間確定，由負(fù)指數(shù)分布計(jì)算下一個(gè)顧客第一個(gè)顧客到達(dá)時(shí)間確定，由負(fù)指數(shù)分布計(jì)算下一個(gè)顧客前一個(gè)顧客（i-1）是否離開系統(tǒng)a前一個(gè)顧客（i-1）是否離開系統(tǒng)a排隊(duì)排隊(duì)否否是是第i個(gè)顧客第i個(gè)顧客在系統(tǒng)a的等待時(shí)間、服務(wù)時(shí)間、離開時(shí)間 到達(dá)b系統(tǒng)時(shí)間確定到達(dá)b系統(tǒng)時(shí)間確定前一個(gè)顧客（i-1）是否離開系統(tǒng)b前一個(gè)顧客（i-1）是否離開系統(tǒng)b排隊(duì)排隊(duì) 否否是是否是結(jié)束輸出結(jié)果顧客流結(jié)束？第i個(gè)顧客在系統(tǒng)b的等待時(shí)間、服務(wù)時(shí)間、離開時(shí)間 否是結(jié)束輸出結(jié)果顧客流結(jié)束？第i個(gè)顧客在系統(tǒng)b的等待時(shí)間、服務(wù)時(shí)間、離開時(shí)間 仿真結(jié)果與分析M/M/1系統(tǒng)仿真與給定λ和μ_a,μ_b條件下a、b系統(tǒng)及總系統(tǒng)的到達(dá)離去時(shí)間，等待隊(duì)長，系統(tǒng)顧客數(shù)，排隊(duì)時(shí)間和停留時(shí)間分布：λ=0.3，μ_a=μ_b=0.8，顧客流總數(shù)為100λ=0.3，μ_a=μ_b=0.8，顧客數(shù)為1000(3)λ=0.3，μ_a=μ_b=0.8，顧客數(shù)為2000λ=0.2，μ_a=μ_b=0.9，顧客數(shù)為1000λ=0.4，μ_a=μ_b=0.5，顧客數(shù)為1000平均隊(duì)長和平均系統(tǒng)時(shí)間隨λ/μ的變化曲線實(shí)驗(yàn)結(jié)論1.從上述五組數(shù)據(jù)比較可以看出，運(yùn)用控制變量法。對于仿真顧客總數(shù)，仿真顧客數(shù)越大，仿真值越接近理論值，當(dāng)顧客數(shù)為2000時(shí)基本仿真和理論值基本相等，由于再增加人數(shù)程序運(yùn)行時(shí)間將會很長，因此就做到2000人數(shù)的仿真。因此盡可能地增加顧客數(shù)是到達(dá)穩(wěn)態(tài)的一個(gè)途徑。對于到達(dá)率和服務(wù)率的比例，當(dāng)?shù)竭_(dá)率遠(yuǎn)小于服務(wù)率時(shí)，全系統(tǒng)平均隊(duì)長和平均系統(tǒng)時(shí)間都比較小，容易達(dá)到穩(wěn)態(tài)。到達(dá)率與服務(wù)率特別接近時(shí)，全系統(tǒng)平均隊(duì)長和平均系統(tǒng)時(shí)間都比較大，系統(tǒng)仿真誤差比較大，而且很難達(dá)到穩(wěn)態(tài)。由仿真圖得出，平均隊(duì)長和平均等待時(shí)間均隨λ的增大而增大，隨μ的增大而減小。2.從平均隊(duì)長和平均系統(tǒng)時(shí)間隨λ/μ的變化曲線可以看出，平均隊(duì)長和平均系統(tǒng)時(shí)間和λ/μ的值呈正相關(guān)增長，隨著λ/μ的值不斷變大，平均隊(duì)長和平均系統(tǒng)時(shí)間呈類似于指數(shù)增長趨向于無窮大。實(shí)驗(yàn)問題和難點(diǎn)a，b系統(tǒng)級聯(lián)銜接的問題原因在于b系統(tǒng)的顧客流來自于a，并不屬于泊松分布，因此在程序中直接將a的離開時(shí)間設(shè)置為b的到達(dá)時(shí)間。計(jì)算全系統(tǒng)的顧客數(shù)和排隊(duì)顧客數(shù)的問題由于每個(gè)事件的時(shí)間斷點(diǎn)只提供到達(dá)a系統(tǒng)人數(shù)、離開a（到達(dá)b）系統(tǒng)人數(shù)、離開b系統(tǒng)人數(shù)三個(gè)中的一個(gè)，而計(jì)算全系統(tǒng)的顧客數(shù)和排隊(duì)長需要知道每個(gè)時(shí)間斷點(diǎn)的三個(gè)值，因此確定一個(gè)時(shí)間對應(yīng)的另外兩個(gè)值是本實(shí)驗(yàn)的最大難點(diǎn)。通過分析時(shí)間軸，我建立了三個(gè)矩陣對應(yīng)三種斷點(diǎn)，從而確定了這個(gè)時(shí)間點(diǎn)對應(yīng)的另外兩個(gè)值，然后將三個(gè)矩陣合并成一個(gè)時(shí)間軸的矩陣，排序，通過將a系統(tǒng)人數(shù)、離開a（到達(dá)b）系統(tǒng)人數(shù)、離開b系統(tǒng)人數(shù)三個(gè)互相的運(yùn)算從而計(jì)算出全系統(tǒng)的顧客數(shù)和排隊(duì)長。3、建立了2中的矩陣后仍不知道如何找出對應(yīng)時(shí)間點(diǎn)的另外兩個(gè)值，經(jīng)過畫時(shí)間軸通過sortrow將每行按小到大排序，再用find(a<)函數(shù)找出這個(gè)時(shí)間點(diǎn)對應(yīng)的區(qū)間，照著另外兩個(gè)矩陣相同位置便可找出另外的兩個(gè)值4、仿真出現(xiàn)問題仿真后發(fā)現(xiàn)全系統(tǒng)顧客數(shù)圖形為一個(gè)三角形這顯然是不符合情理的，為此做了大量的排查，發(fā)現(xiàn)是由于B矩陣中的一個(gè)函數(shù)的B手誤打成了b，經(jīng)過修正圖形顯示終于正常在計(jì)算顧客平均等待隊(duì)長時(shí)不知如何計(jì)算將仿真的數(shù)據(jù)轉(zhuǎn)換為仿真值，查閱教程資料后得到：顧客平均等待隊(duì)長及平均排隊(duì)等待時(shí)間的定義為其中，為在時(shí)間區(qū)間上排隊(duì)人數(shù)乘以該區(qū)間長度。為第i個(gè)顧客排隊(duì)等待時(shí)間。6、關(guān)于穩(wěn)態(tài)的確定從實(shí)驗(yàn)結(jié)果中可以看出，測試的顧客人數(shù)越多，仿真值越接近理論值，在圖表中當(dāng)排隊(duì)長和顧客數(shù)的曲線分布接近平穩(wěn)之后即可認(rèn)為系統(tǒng)已達(dá)到穩(wěn)態(tài)。實(shí)驗(yàn)心得此次實(shí)驗(yàn)我們做的是兩個(gè)M/M/1系統(tǒng)的級聯(lián)問題，較之單個(gè)系統(tǒng)在編程難度上有了很大的提升，因此我們在編寫程序過程中也遇到了很多麻煩。同時(shí)也學(xué)習(xí)了很多關(guān)于MATLAB的基本語句函數(shù)和算法思想。在實(shí)際操作過程中，知道了用矩陣數(shù)組運(yùn)算代替for循環(huán)可以加快運(yùn)算速度，這對