1、通信網理論基礎實驗二：二次排隊問題M/M/1排隊系統的級聯一、實驗目的M/M/1是最簡單的排隊系統，其假設到達過程是一個參數為的Poisson過程，服務時間是參數為的負指數分布，只有一個服務窗口，等待的位置有無窮多個，排隊的方式是FIFO。M/M/1排隊系統的穩態分布、平均隊列長度，等待時間的分布以及平均等待時間，可通過泊松過程、負指數分布、生滅過程以及Little公式等進行理論上的分析與求解。本次實驗的目標有兩個：實現M/M/1單窗口無限排隊系統的系統仿真，利用事件調度法實現離散事件系統仿真，并統計平均隊列長度以及平均等待時間等值，以與理論分析結果進行對比。仿真兩個M/M/1級聯所組成的排隊

2、網絡，統計各個隊列的平均隊列長度與平均系統時間等值，驗證Kleinrock有關數據包在從一個交換機出來后，進入下一個交換機時，隨機按負指數分布取一個新的長度的假設的合理性。二、實驗原理1、M/M/1排隊系統根據排隊論的知識我們知道，排隊系統的分類是根據該系統中的顧客到達模式、服務模式、服務員數量以及服務規則等因素決定的。設到達過程是一個參數為的Poisson過程，則長度為t的時間內到達k個呼叫的概率Pk(t)3/Pk(t)服從Poisson分布，即k!，k=0,1,2,其中'>0為一常數，表示了平均到達率或Poisson呼叫流的強度。設每個呼叫的持續時間為，服從參數為'的

3、負指數分布，即其分布函數為PX:t一eTt一0服務規則采用先進先服務的規則（FIFO）。EINI-'在該M/M/1系統中，設，則穩態時的平均隊長為一'，顧客的平均等2、二次排隊網絡由兩個M/M/1排隊系統所組成的級聯網絡，顧客以參數為的泊松過程到達第一個排隊系統A，服務時間為參數為亠的負指數分布；從A出來后直接進入第二個排隊系統B，B的服務時間為參數為叮的負指數分布，且與A的服務時間相互獨立。在該級聯網絡中，如穩態存在，即：叫且：宀2，則兩個排隊系統相互獨立，顧客穿11T二LL_）LL過網絡的總時延為各個排隊系統的時延之和，即1-2-o如將該模型應用于數據包穿越網絡的平均時延的

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

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

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

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

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

9、CusNumStart.*IntervalTime0)/TimePoint(end);%系統中平均顧客數SysCusNum=zeros(size(TimePoint);QueLengthAvg=sum(0QueLength.*IntervalTime0)/TimePoint(end);%系統平均等待隊長ArriveTime每個顧客的到達時間LeaveTime每個顧客的離開時間ArriveInterval顧客的到達時間間隔ServeInterval每個顧客的服務時間ArriveNum到達總人數SimNum仿真人數SystemTime每個人的系統時間SystemTimeAvg平均系統時間WaitT

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

11、40711.34221.42111.37711.3775平均顧客數1.2481.23591.26261.22411.26771.24331.2376平均等待隊長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仿真顧客總數1000000/仿真次數1234567平均系統時間2.49012.48922.50082.49862.50532.4942.5024平均等待時間1.37921.3771.38861.38831.39291.38331.391平均顧客數1.2441.24551.251.24991.25261.24541.2494平均等待隊長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上表可以看出，通過這種模型和方法仿真的結果和理論值十分接近，增加仿真顧客數時,可以得到更理想的結果。當仿真人數超過100000人時，仿真結果與理論結果已經十分接近。在誤差允許的范圍內，認為相符。實驗結果截圖如下（SimNum分別為100、1000、10000、100000）100人仿真結果與理論結果對比1000人仿真結果與理論對比10000人仿真結果與理論結果對比100000人仿真結果與理論對

14、比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);A

15、rriveInterval=-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)+ServeInterval(1);%顧客離開時間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)%各顧客的系統時間%各顧客的等待時間%系統中顧客數隨時間的變化%到達時間標志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%系統中平均顧客數計算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%系統中平均顧客數QueLengthAvg=sum(0QueLength.*IntervalTime0)/TimePoint(end);%仿真圖%系統平均等待隊長figure(1);set(1,'position',0,0,1000,700,'Color',111);subplot(2,2,1);%title('各顧客到達時間和離去時間');sta

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

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

22、',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

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

24、是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: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('平均隊長分隊和Nm的圖像)；xlabel('NM);ylabel('平均隊長')；subplot(1,2,2);stairs(x,SystemTimeAvg,'y')title('平均系統時間隨Nm的分布');xlabel('Nm');ylabel('平均系統時間');功能函數：functionQueLengthAvg,SystemTimeAvg=LengthTime(Lambda)%Mu默認為0.5%輸入Lambda返回平均隊長和平均系統時間%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;%到達時間間隔ServeInterval=-log(rand(1,SimNum)/Mu;%服務時間ArriveTime(1)=ArriveInterval(1);%顧客到達時間ArriveNum(1)=1;fori=2:SimNumArriv

27、eTime(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(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:length(Ti