北郵通信網(wǎng)性能分析實(shí)驗(yàn)二MM排隊(duì)系統(tǒng)實(shí)驗(yàn)報(bào)告

1、通信網(wǎng)理論基礎(chǔ)實(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ì)

2、網(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)原理1、M/M/1排隊(duì)系統(tǒng)根據(jù)排隊(duì)論的知識(shí)我們知道，排隊(duì)系統(tǒng)的分類是根據(jù)該系統(tǒng)中的顧客到達(dá)模式、服務(wù)模式、服務(wù)員數(shù)量以及服務(wù)規(guī)則等因素決定的。設(shè)到達(dá)過程是一個(gè)參數(shù)為的Poisson過程，則長度為t的時(shí)間內(nèi)到達(dá)k個(gè)呼叫的概率Pk(t)3/Pk(t)服從Poisson分布，即k!，k=0,1,2,其中'>0為一常數(shù)，表示了平均到達(dá)率或Poisson呼叫流的強(qiáng)度。設(shè)每個(gè)呼叫的持續(xù)時(shí)間為，服從參數(shù)為'的

3、負(fù)指數(shù)分布，即其分布函數(shù)為PX:t一eTt一0服務(wù)規(guī)則采用先進(jìn)先服務(wù)的規(guī)則（FIFO）。EINI-'在該M/M/1系統(tǒng)中，設(shè)，則穩(wěn)態(tài)時(shí)的平均隊(duì)長為一'，顧客的平均等2、二次排隊(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)存在，即：叫且：宀2，則兩個(gè)排隊(duì)系統(tǒng)相互獨(dú)立，顧客穿11T二LL_）LL過網(wǎng)絡(luò)的總時(shí)延為各個(gè)排隊(duì)系統(tǒng)的時(shí)延之和，即1-2-o如將該模型應(yīng)用于數(shù)據(jù)包穿越網(wǎng)絡(luò)的平均時(shí)延的

4、計(jì)算，假設(shè)數(shù)據(jù)包的包長服從負(fù)指數(shù)分布，平均包長為b；排隊(duì)系統(tǒng)A的信道速率為C1，B的信道速率為C2。為保證兩次排隊(duì)的獨(dú)立性，Kleinrock假設(shè)數(shù)據(jù)包在從一個(gè)交換機(jī)出來后，進(jìn)入下一個(gè)交換機(jī)時(shí)，隨機(jī)按負(fù)指數(shù)分布取一個(gè)新的長度。三、實(shí)驗(yàn)內(nèi)容1、仿真時(shí)序圖示例本實(shí)驗(yàn)中的排隊(duì)系統(tǒng)為當(dāng)顧客到達(dá)分布服從負(fù)指數(shù)分布，系統(tǒng)服務(wù)時(shí)間也服從負(fù)指數(shù)分布，單服務(wù)臺(tái)系統(tǒng)，單隊(duì)排隊(duì)，按FIFO方式服務(wù)為M/M/1排隊(duì)系統(tǒng)。理論上，我們定義服務(wù)員結(jié)束一次服務(wù)或者有顧客到達(dá)系統(tǒng)均為一次事件。b為第i個(gè)任何一類事件發(fā)生的時(shí)間，其時(shí)序關(guān)系如下圖所示。bi?第i個(gè)任何一類事件發(fā)生的時(shí)間ti?第i個(gè)顧客到達(dá)類事件發(fā)生的時(shí)間ci?第

5、i個(gè)顧客離開類事件發(fā)生的時(shí)間Ai?為第i-1個(gè)與第i個(gè)顧客到達(dá)時(shí)間間隔Di?第i個(gè)顧客排隊(duì)等待的時(shí)間長度Si?第i個(gè)顧客服務(wù)的時(shí)間長度顧客平均等待隊(duì)長Q（n）及平均排隊(duì)等待時(shí)間d（n）的定義為其中，Ri為在時(shí)間區(qū)間b,b上排隊(duì)人數(shù)qi乘以該區(qū)間長度（bbi）。Di為第i個(gè)顧客排隊(duì)等待時(shí)間。2、仿真設(shè)計(jì)算法（1）利用負(fù)指數(shù)分布與泊松過程的關(guān)系，產(chǎn)生符合泊松過程的顧客流。（2）對每個(gè)排隊(duì)系統(tǒng)，分別構(gòu)建一個(gè)顧客到達(dá)隊(duì)列和一個(gè)顧客等待隊(duì)列。顧客到達(dá)后，首先進(jìn)入到達(dá)隊(duì)列的隊(duì)尾排隊(duì)，并檢測是否有顧客等待以及是否有服務(wù)臺(tái)空閑，如果無人等待并且有服務(wù)員空閑則進(jìn)入服務(wù)狀態(tài)，否則顧客將進(jìn)入等待隊(duì)列的隊(duì)尾等待。（3

6、）產(chǎn)生符合負(fù)指數(shù)分布的隨機(jī)變量作為每個(gè)顧客的服務(wù)時(shí)間。（4）當(dāng)服務(wù)員結(jié)束一次服務(wù)后，就取出等待隊(duì)列中位于隊(duì)頭的顧客進(jìn)入服務(wù)狀態(tài)，如果等待隊(duì)列為空則服務(wù)臺(tái)空閑等待下一位顧客的到來。（5）顧客結(jié)束A系統(tǒng)的服務(wù)后，立即進(jìn)入B系統(tǒng)排隊(duì)等待服務(wù)。（6）由事件來觸發(fā)仿真時(shí)鐘的不斷推進(jìn)。每發(fā)生一次事件，記錄下兩次事件間隔的時(shí)間以及在該時(shí)間段內(nèi)排隊(duì)的人數(shù)。（7）在排隊(duì)網(wǎng)絡(luò)達(dá)到穩(wěn)態(tài)時(shí)，計(jì)算顧客平均系統(tǒng)時(shí)間以及平均隊(duì)長。3、仿真結(jié)果分析（1）分析仿真數(shù)據(jù)，統(tǒng)計(jì)顧客的平均系統(tǒng)時(shí)間與平均隊(duì)長，計(jì)算其方差，分析與理論計(jì)算結(jié)果的吻合程度，驗(yàn)證仿真程序的正確性。（2）驗(yàn)證Kleinrock假設(shè)的合理性。一一假設(shè)包長不變，即

7、二次排隊(duì)不獨(dú)立，統(tǒng)計(jì)平均值與理論值的相近程度。4、仿真結(jié)果分析分析仿真數(shù)據(jù)，統(tǒng)計(jì)顧客的平均等待時(shí)間與顧客的平均等待隊(duì)長，計(jì)算其方差，分析與理論計(jì)算結(jié)果的吻合程度，驗(yàn)證仿真程序的正確性。四、實(shí)驗(yàn)要求1. 兩人一組，利用MATLAB實(shí)現(xiàn)排隊(duì)網(wǎng)絡(luò)的仿真模擬。2. 統(tǒng)計(jì)給定和條件下系統(tǒng)的平均隊(duì)長和平均系統(tǒng)時(shí)間，與理論結(jié)果進(jìn)行比對。3. 統(tǒng)計(jì)單個(gè)系統(tǒng)的平均隊(duì)長和平均系統(tǒng)時(shí)間隨的變化曲線。五、仿真模擬和理論仿真結(jié)果的對比1. 仿真設(shè)計(jì)算法（主要函數(shù)）利用負(fù)指數(shù)分布與泊松過程的關(guān)系，產(chǎn)生符合泊松過程的顧客流，產(chǎn)生符合負(fù)指數(shù)分布的隨機(jī)變量作為每個(gè)顧客的服務(wù)時(shí)間：ArriveInterval=-log（rand

8、（1,SimNum）/Lambda;%到達(dá)時(shí)間間隔ArriveTime(1)=ArriveInterval(1);%顧客到達(dá)時(shí)間時(shí)間計(jì)算SystemTime=LeaveTime-ArriveTime;%各顧客的系統(tǒng)時(shí)間WaitTime=SystemTime-ServeInterval;%各顧客的等待時(shí)間由事件來觸發(fā)仿真時(shí)鐘的不斷推進(jìn)。每發(fā)生一次事件，記錄下兩次事件間隔的時(shí)間以及在該時(shí)間段內(nèi)排隊(duì)的人數(shù)：TimePoint=ArriveTime,LeaveTime;%系統(tǒng)中顧客數(shù)隨時(shí)間的變化ArriveFlag=zeros(size(TimePoint);%到達(dá)時(shí)間標(biāo)志CusNumAvg=sum(

9、CusNumStart.*IntervalTime0)/TimePoint(end);%系統(tǒng)中平均顧客數(shù)SysCusNum=zeros(size(TimePoint);QueLengthAvg=sum(0QueLength.*IntervalTime0)/TimePoint(end);%系統(tǒng)平均等待隊(duì)長ArriveTime每個(gè)顧客的到達(dá)時(shí)間LeaveTime每個(gè)顧客的離開時(shí)間ArriveInterval顧客的到達(dá)時(shí)間間隔ServeInterval每個(gè)顧客的服務(wù)時(shí)間ArriveNum到達(dá)總?cè)藬?shù)SimNum仿真人數(shù)SystemTime每個(gè)人的系統(tǒng)時(shí)間SystemTimeAvg平均系統(tǒng)時(shí)間WaitT

10、ime排隊(duì)等待時(shí)間WaitTimeAvg平均排隊(duì)等待時(shí)間SysCusNum系統(tǒng)中的顧客人數(shù)IntervalTime事件間隔時(shí)間CusNumStart系統(tǒng)中的顧客數(shù)?CusNumAvgCusNum_avg系統(tǒng)中的平均顧客數(shù)QueLengthAvgQueLength_avg平均等待隊(duì)長2. 算法的流程圖3. 仿真結(jié)果分析設(shè)置Lambda=0.5，Mu=0.9，顧客的平均等待時(shí)間與顧客的平均等待隊(duì)長，計(jì)算其方差如下:仿真顧客總數(shù)100000/仿真次數(shù)2345-6-7平均系統(tǒng)時(shí)間2.49562.46752.51522.44652.53262.48772.4891平均等待時(shí)間1.38431.35531.

11、40711.34221.42111.37711.3775平均顧客數(shù)1.2481.23591.26261.22411.26771.24331.2376平均等待隊(duì)長0.692240.678850.706330.671540.711360.688250.684938910平均值方差理論值2.48992.50962.46132.48950.0006767912.51.37781.40031.35361.379630.0006231361.38891.24671.25891.22431.244910.0002262031.250.68990.702410.673270.6899080.000183958

12、0.69444仿真顧客總數(shù)1000000/仿真次數(shù)1234567平均系統(tǒng)時(shí)間2.49012.48922.50082.49862.50532.4942.5024平均等待時(shí)間1.37921.3771.38861.38831.39291.38331.391平均顧客數(shù)1.2441.24551.251.24991.25261.24541.2494平均等待隊(duì)長0.689010.689010.694070.694480.696410.690740.694528910平均值方差理論值2.51082.50232.49862.499210.0000449722.51.39951.39151.38851.38798

13、0.0000443041.38891.25511.25341.24961.249490.0000132971.250.69960.697020.694440.693930.0000119300.69444上表可以看出，通過這種模型和方法仿真的結(jié)果和理論值十分接近，增加仿真顧客數(shù)時(shí),可以得到更理想的結(jié)果。當(dāng)仿真人數(shù)超過100000人時(shí)，仿真結(jié)果與理論結(jié)果已經(jīng)十分接近。在誤差允許的范圍內(nèi)，認(rèn)為相符。實(shí)驗(yàn)結(jié)果截圖如下（SimNum分別為100、1000、10000、100000）100人仿真結(jié)果與理論結(jié)果對比1000人仿真結(jié)果與理論對比10000人仿真結(jié)果與理論結(jié)果對比100000人仿真結(jié)果與理論對

14、比1000000人仿真結(jié)果與理論結(jié)果對比4. 實(shí)驗(yàn)源代碼語言：matlab代碼：clear;clc;%M/M/1排隊(duì)系統(tǒng)仿真SimNum=input('請輸入仿真顧客總數(shù)SimNum=');%仿真顧客總數(shù)；Lambda=input('請輸入到達(dá)率Lambda=');%到達(dá)率LambdaMu=input('請輸入服務(wù)率Mu=');%到達(dá)率MuArriveTime=zeros(1,SimNum);LeaveTime=zeros(1,SimNum);ArriveNum=zeros(1,SimNum);LeaveNum=zeros(1,SimNum);A

15、rriveInterval=-log(rand(1,SimNum)/Lambda;%到達(dá)時(shí)間間隔ServeInterval=-log(rand(1,SimNum)/Mu;%服務(wù)時(shí)間ArriveTime(1)=ArriveInterval(1);%顧客到達(dá)時(shí)間ArriveNum(1)=1;fori=2:SimNumArriveTime(i)=ArriveTime(i-1)+ArriveInterval(i);ArriveNum(i)=i;endLeaveTime(1)=ArriveTime(1)+ServeInterval(1);%顧客離開時(shí)間LeaveNum(1)=1;fori=2:SimNu

16、mifLeaveTime(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,LeaveTim

17、e;TimePoint=sort(TimePoint);ArriveFlag=zeros(size(TimePoint);SysCusNum=zeros(size(TimePoint);temp=2;SysCusNum(1)=1;fori=2:length(TimePoint)%各顧客的系統(tǒng)時(shí)間%各顧客的等待時(shí)間%系統(tǒng)中顧客數(shù)隨時(shí)間的變化%到達(dá)時(shí)間標(biāo)志if(temp<=length(ArriveTime)&&(TimePoint(i)=ArriveTime(temp)SysCusNum(i)=SysCusNum(i-1)+1;temp=temp+1;ArriveFlag(

18、i)=1;elseSysCusNum(i)=SysCusNum(i-1)-1;endend%系統(tǒng)中平均顧客數(shù)計(jì)算IntervalTime=zeros(size(TimePoint);IntervalTime(1)=ArriveTime(1);fori=2:length(TimePoint)IntervalTime(i)=TimePoint(i)-TimePoint(i-1);endCusNumStart=0SysCusNum;CusNumAvg=sum(CusNumStart.*IntervalTime0)/TimePoint(end);QueLength=zeros(size(SysCusN

19、um);fori=1:length(SysCusNum)ifSysCusNum(i)>=2QueLength(i)=SysCusNum(i)-1;elseQueLength(i)=0;endend%系統(tǒng)中平均顧客數(shù)QueLengthAvg=sum(0QueLength.*IntervalTime0)/TimePoint(end);%仿真圖%系統(tǒng)平均等待隊(duì)長figure(1);set(1,'position',0,0,1000,700,'Color',111);subplot(2,2,1);%title('各顧客到達(dá)時(shí)間和離去時(shí)間');sta

20、irs(0ArriveNum,0ArriveTime,'r');holdon;stairs(0LeaveNum,0LeaveTime,'g');legend('到達(dá)時(shí)間','離去時(shí)間');holdoff;title('各顧客到達(dá)時(shí)間和離去時(shí)間');xlabel('顧客數(shù)');ylabel('時(shí)間');subplot(2,2,2);stairs(TimePoint,SysCusNum,'r')title('系統(tǒng)等待隊(duì)長分布');xlabel('時(shí)

21、間');ylabel('隊(duì)長');subplot(2,2,3);stairs(0ArriveNum,0WaitTime,'r');holdon;stairs(0LeaveNum,0SystemTime,'g');holdoff;title('各顧客在系統(tǒng)中的等待時(shí)間和系統(tǒng)時(shí)間');legend('等待時(shí)間','系統(tǒng)時(shí)間');xlabel('顧客數(shù)');ylabel('時(shí)間');%仿真值與理論值比較disp('理論平均系統(tǒng)時(shí)間SystemTimeAvg=

22、',num2str(1/(Mu-Lambda);disp('理論平均等待時(shí)間WaitTimeAvg=',num2str(Lambda/(Mu*(Mu-Lambda);disp('理論系統(tǒng)中平均顧客數(shù)CusNumAvg=',num2str(Lambda/(Mu-Lambda);disp('理論系統(tǒng)中平均等待隊(duì)長QueLengthAvg=',num2str(Lambda*Lambda/(Mu*(Mu-Lambda);disp('仿真平均系統(tǒng)時(shí)間SystemTimeAvg=',num2str(SystemTimeAvg)disp

23、('仿真平均等待時(shí)間WaitTimeAvg=',num2str(WaitTimeAvg)disp('仿真系統(tǒng)中平均顧客數(shù)CusNumAvg=',num2str(CusNumAvg);disp('仿真系統(tǒng)中平均等待隊(duì)長QueLengthAvg=',num2str(QueLengthAvg);六、單個(gè)系統(tǒng)的平均隊(duì)長和平均系統(tǒng)時(shí)間隨”卩的變化曲線1. 實(shí)現(xiàn)原理默認(rèn)仿真人數(shù)為100000人，卩為0.5，故只需要入變化就可以使得"卩都變化。主函數(shù)調(diào)用功能函數(shù)的平均隊(duì)長和平均系統(tǒng)時(shí)間的結(jié)果進(jìn)行繪圖。此實(shí)驗(yàn)中，入去0.10.8，故"諏值范圍

24、是0.21.6。2. 仿真算法主函數(shù)：Mu=0.5;Lambda=0.1:0.001:0.8;x=2.*Lambda;QueLengthAvg=zeros(size(Lambda);SystemTimeAvg=zeros(size(Lambda);fori=1:700QueLengthAvg(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

25、,'b')title('平均隊(duì)長分隊(duì)和Nm的圖像)；xlabel('NM);ylabel('平均隊(duì)長')；subplot(1,2,2);stairs(x,SystemTimeAvg,'y')title('平均系統(tǒng)時(shí)間隨Nm的分布');xlabel('Nm');ylabel('平均系統(tǒng)時(shí)間');功能函數(shù)：functionQueLengthAvg,SystemTimeAvg=LengthTime(Lambda)%Mu默認(rèn)為0.5%輸入Lambda返回平均隊(duì)長和平均系統(tǒng)時(shí)間%lambda/

26、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;%到達(dá)時(shí)間間隔ServeInterval=-log(rand(1,SimNum)/Mu;%服務(wù)時(shí)間ArriveTime(1)=ArriveInterval(1);%顧客到達(dá)時(shí)間ArriveNum(1)=1;fori=2:SimNumArriv

27、eTime(i)=ArriveTime(i-1)+ArriveInterval(i);ArriveNum(i)=i;endLeaveTime(1)=ArriveTime(1)+ServeInterval(1);%顧客離開時(shí)間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;%各顧客的系統(tǒng)時(shí)間%系統(tǒng)中顧客數(shù)隨時(shí)間的變化%到達(dá)時(shí)間標(biāo)志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:length(Ti