北郵-通信網(wǎng)實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上北京郵電大學(xué)實驗報告通信網(wǎng)理論基礎(chǔ)實驗報告學(xué)院: 信息與通信工程學(xué)院 班級: 學(xué)號: 姓名: 實驗一 ErlangB公式計算器一 實驗內(nèi)容編寫Erlang B公式的圖形界面計算器，實現(xiàn)給定任意兩個變量求解第三個變量的功能：1）給定到達(dá)的呼叫量a和中繼線的數(shù)目s，求解系統(tǒng)的時間阻塞率B；2）給定系統(tǒng)的時間阻塞率的要求B和到達(dá)的呼叫量a，求解中繼線的數(shù)目s，以實現(xiàn)網(wǎng)絡(luò)規(guī)劃；3）給定系統(tǒng)的時間阻塞率要求B以及中繼線的數(shù)目s，判斷該系統(tǒng)能支持的最大的呼叫量a。二 實驗描述1 實驗思路使用MATLAB GUITOOL設(shè)計圖形界面，通過單選按鈕確定計算的變量，同時通過可編輯文本框

2、輸入其他兩個已知變量的值，對于不同的變量，通過調(diào)用相應(yīng)的函數(shù)進(jìn)行求解并顯示最終的結(jié)果。2 程序界面3 流程圖4 主要的函數(shù)符號規(guī)定如下：b(Blocking)：阻塞率；a(BHT)：到達(dá)呼叫量；s(Lines)：中繼線數(shù)量。1）已知到達(dá)呼叫量a及中繼線數(shù)量s求阻塞率b使用迭代算法提高程序效率Bs,a=aBs-1,as+aB(s-1,a)代碼如下：function b = ErlangB_b(a,s)b = 1;for i = 1:sb = a * b / (i + a * b);endend2）已知到達(dá)呼叫量a及阻塞率b求中繼線數(shù)量s考慮到s為正整數(shù)，因此采用數(shù)值逼近的方法。采用循環(huán)的方式，在

3、每次循環(huán)中增加s的值，同時調(diào)用 Bs,a 函數(shù)計算阻塞率并與已知阻塞率比較，當(dāng)本次誤差小于上次誤差時，結(jié)束循環(huán)，得到s值。代碼如下：function s = ErlangB_s(a,b)s = 1;Bs = ErlangB_b(a,s);err = abs(b-Bs);err_s = err;while (err_s <= err)err = err_s;s = s + 1;Bs = ErlangB_b(a,s);err_s = abs(b - Bs);ends = s - 1;end3）已知阻塞率b及中繼線數(shù)量s求到達(dá)呼叫量a考慮到a為有理數(shù)，因此采用變步長逼近的方法。采用循環(huán)的方式，

4、在每次循環(huán)中增加a的值（步長為 s/2），同時調(diào)用 Bs,a 函數(shù)計算阻塞率并與已知阻塞率比較，當(dāng)本次誤差小于預(yù)設(shè)閾值時，結(jié)束循環(huán)，得到a值。代碼如下：function a = ErlangB_a(b,s)a = 0;step = s / 2;b_temp = ErlangB_b(a,s);b_temps = ErlangB_b(a + step,s);while (abs(b - b_temp) > 0.)if (b - b_temp) * (b - b_temps) < 0)step = step / 2;elsea = a + step;endb_temp = ErlangB

5、_b(a,s);b_temps = ErlangB_b(a + step,s);endend三 結(jié)果分析1) 已知到達(dá)呼叫量a及中繼線數(shù)量s求阻塞率ba100100100100100100100s125102050100b0.99010.98020.95050.90110.80240.50930.0757a5102050100s1010101010b0.01840.21460.53800.80470.90112) 已知到達(dá)呼叫量a及阻塞率b求中繼線數(shù)量sa125102050100b0.50.50.50.50.50.50.5s1236112651a1010101010b0.10.20.50.81

6、.0s13106213) 已知阻塞率b及中繼線數(shù)量s求到達(dá)呼叫量ab0.50.50.50.50.50.50.5s125102050100a12.73208.436918.272638.159298.0719198.0377b0.10.20.50.60.8s1010101010a7.51069.685018.272623.479848.78634）分析將程序結(jié)果與在線ErlangB公式計算器結(jié)果進(jìn)行比較，結(jié)果基本一致，說明程序的正確性。實驗二 M/M/1排隊系統(tǒng)一 實驗內(nèi)容實現(xiàn)M/M/1單窗口無限排隊系統(tǒng)的系統(tǒng)仿真，利用事件調(diào)度法實現(xiàn)離散事件系統(tǒng)仿真，并統(tǒng)計平均隊列長度以及平均等待時間等值，以與

7、理論分析結(jié)果進(jìn)行對比。二 實驗原理1 顧客到達(dá)模式設(shè)到達(dá)過程是一個參數(shù)為 的Poisson過程，則長度為 t 的時間內(nèi)到達(dá) k 個呼叫的概率Pkt 服從Poisson分布，即Pkt=tkk!et2 服務(wù)模式設(shè)每個呼叫的持續(xù)時間為 t，則服從參數(shù)為 t 的負(fù)指數(shù)分布，即PX>t=1-e-t, t03 服務(wù)規(guī)則服務(wù)規(guī)則為：FIFO4 理論分析設(shè)系統(tǒng)到達(dá)率為 ，服務(wù)率為 ，則理論分析如下：理論平均等待時間：Ew=1-理論平均排隊時間：Eq=(-)理論系統(tǒng)中平均顧客數(shù)：EN=-理論系統(tǒng)中平均等待隊長：ENq=(-)三 實驗描述1 實驗思路仿真時序圖示例時序關(guān)系圖如下：各參數(shù)含義如下：bi：第i個

8、事件（到達(dá)或離開）發(fā)生的時間ti：第i個到達(dá)事件發(fā)生的時間ci：第i個離開事件發(fā)生的時間Ai：第（i-1）個顧客與第i個顧客到達(dá)時間間隔Di：第i個顧客排隊等待時間間隔Si：第i個顧客服務(wù)時間長度仿真設(shè)計算法1）利用負(fù)指數(shù)分布與泊松過程的關(guān)系，產(chǎn)生符合泊松過程的顧客流；2）分別構(gòu)建一個顧客到達(dá)隊列和一個顧客等待隊列。顧客到達(dá)后，首先進(jìn)入到達(dá)的隊尾排隊，并檢測是否有顧客等待以及是否有服務(wù)臺空閑，如果無人等待并且有服務(wù)員空閑則進(jìn)入服務(wù)狀態(tài)，否則顧客將進(jìn)入等待隊列的隊尾等待；3）產(chǎn)生符合負(fù)指數(shù)分布的隨機變量作為每個顧客的服務(wù)時間；4）當(dāng)服務(wù)員結(jié)束一次服務(wù)后，就取出等待隊列中位于對頭的顧客進(jìn)入服務(wù)狀態(tài)

9、，如果迭代隊列為空則服務(wù)臺空閑等待下一位顧客到來；5）在系統(tǒng)到達(dá)穩(wěn)態(tài)時，計算系統(tǒng)的平均等待時間以及平均等待隊長等數(shù)據(jù)。2 流程圖3 主要的函數(shù)1) 產(chǎn)生符合泊松過程的顧客流Interval_Arrive=-log(rand(1,SimTotal)/Lambda; %Arrival Time Interval2) 產(chǎn)生符合負(fù)指數(shù)分布的服務(wù)時間Interval_Serve=-log(rand(1,SimTotal)/Mu;%Service Time3) 計算顧客到達(dá)時間%*Arrive Time for each Customer*t_Arrive(1)=Interval_Arrive(1);Ar

10、riveNum(1)=1;for i=2:SimTotal t_Arrive(i)=t_Arrive(i-1)+Interval_Arrive(i); ArriveNum(i)=i;end4) 計算顧客離開時間%Leave Time for each Customert_Leave(1)=t_Arrive(1)+Interval_Serve(1);LeaveNum(1)=1;for i=2:SimTotalif t_Leave(i-1)<t_Arrive(i)%New customer arrives after the former has been served. t_Leave(i

11、)=t_Arrive(i)+Interval_Serve(i);else%New customer arrives while the former is being served. t_Leave(i)=t_Leave(i-1)+Interval_Serve(i); end LeaveNum(i)=i;end5) 計算平均等待時間t_Wait=t_Leave-t_Arrive;%Waiting Time for each Customert_Wait_avg=mean(t_Wait);%Average Waiting Time6) 計算平均排隊時間t_Queue=t_Wait-Interva

12、l_Serve;%Queueing Time for each Customert_Queue_avg=mean(t_Queue);%Average Queueing Time7) 計算平均顧客數(shù)%TimelineTimepoint=t_Arrive,t_Leave;%Record Arrival Time & Leaving Time for each Customer.Timepoint=sort(Timepoint);%Sort all Timepoints.ArriveFlag=zeros(size(Timepoint);%Flag of ArrivalCusNum=zeros

13、(size(Timepoint);temp=2; CusNum(1)=1;for i=2:length(Timepoint)if (temp<=length(t_Arrive)&&(Timepoint(i)=t_Arrive(temp)%if the timepoint is about ArrivalCusNum(i)=CusNum(i-1)+1;%add Number of Customerstemp=temp+1;ArriveFlag(i)=1;else%if the timepoint is about LeavingCusNum(i)=CusNum(i-1)-1

14、;%reduce Number of Customersendend%Average Number of CustomersTime_interval=zeros(size(Timepoint);Time_interval(1)=t_Arrive(1);for i=2:length(Timepoint)Time_interval(i)=Timepoint(i)-Timepoint(i-1);%Timepoint IntervalendCusNum_fromStart=0 CusNum;%Average Number of CustomersCusNum_avg=sum(CusNum_fromS

15、tart.*Time_interval 0 )/Timepoint(end);8) 計算平均隊長%Length of Queue(Excluding Customer being Serviced)QueLength=zeros(size(CusNum);for i=1:length(CusNum)if CusNum(i)>=2QueLength(i)=CusNum(i)-1;%Excluding Customer being ServicedelseQueLength(i)=0;endend%Average Waiting Length of QueueQueLength_avg=su

16、m(0 QueLength.*Time_interval 0 )/Timepoint(end);9) 仿真圖：各顧客到達(dá)時間與離去時間subplot(2,2,1);stairs(0 ArriveNum,0 t_Arrive,'b');hold on;stairs(0 LeaveNum,0 t_Leave,'r');legend('Arrive Time','Leave Time');title('Arrive Time and Leave Time for each customer');xlabel('C

17、ustomer ID');ylabel('Arrive/Leave Time(Accumulated)');10) 仿真圖：系統(tǒng)等待隊長分布subplot(2,2,2);stairs(Timepoint,CusNum,'b')axis(0 Timepoint(end) 0 max(CusNum)title('Distribution of System Customer Number');xlabel('Time(Accumulated)');ylabel('Customer Number');11) 仿真

18、圖：各顧客在系統(tǒng)中的排隊時間和等待時間subplot(2,2,3);stairs(0 ArriveNum,0 t_Queue,'b');hold on;stairs(0 LeaveNum,0 t_Wait,'r');hold off;axis(0 max(max(ArriveNum),max(LeaveNum) 0 max(max(t_Queue),max(t_Wait);title('Queueing Time and Waiting Time for each customer');xlabel('Customer ID');

19、ylabel('Queueing/Waiting Time');legend('Queueing Time','Waiting Time');四 結(jié)果分析為了檢驗算法的正確性，我們進(jìn)行了多次實驗。1 數(shù)值分析1）SimTotal=5000 Lambda=0.25 Mu=0.52）SimTotal=10000 Lambda=0.6 Mu=0.83）SimTotal=2000 Lambda=0.8 Mu=0.94）分析從上面幾次實驗結(jié)果可以看出，仿真的結(jié)果基本符合理論分析的結(jié)果。在系統(tǒng)存在穩(wěn)態(tài)時，即 < 時，仿真結(jié)果與理論分析結(jié)果的誤差較小，此

20、誤差值仿真次數(shù)即 SimTotal 的值的大小影響比較明顯，當(dāng) SimTotal 的值較小時，誤差比較大，當(dāng) SimTotal 的值較大時，誤差比較小。2 仿真圖分析由于仿真圖過多，這里只選取其中一次實驗的仿真圖，其他圖片在上傳文件的壓縮包中。這里選擇第一次實驗的仿真圖。1）各顧客的到達(dá)時間與離去時間橫軸表示的是5000個顧客的編號，縱軸表示的是每個顧客到達(dá)或離去的時間點（藍(lán)線表示的是到達(dá)的時間點，紅線表示的是離去的時間點）。兩條線均嚴(yán)格單調(diào)遞增，原因是顧客按編號的順序依次到來以及依次接受服務(wù)，在只有一個服務(wù)員的情況下，先到的顧客會先接受服務(wù)，因此也會先離去。兩條線的差值表示的是顧客在系統(tǒng)中的

21、時間，包括排隊時間及服務(wù)時間，由于每個顧客在系統(tǒng)的時間相對于所有顧客總時間來說占很小一部分，因此兩條線看起來基本重合。2）系統(tǒng)顧客數(shù)分布橫軸表示的是所有顧客的總時間，縱軸表示的是對應(yīng)每個時間點的系統(tǒng)顧客數(shù)情況。由圖可以看出，系統(tǒng)大部分時間，顧客數(shù)保持在 02 之間，與理論分析情況一致。3）各顧客在系統(tǒng)中的排隊時間和等待時間橫軸表示的是5000個顧客的編號，縱軸表示的是每個顧客排隊或等待的時間點（藍(lán)線表示的是排隊時間，紅線表示的是等待時間，兩條線的差值表示的是服務(wù)時間）。實驗三 Floyd算法一 實驗內(nèi)容實現(xiàn)Floyd算法，可對輸入的鄰接距離矩陣計算圖中任意兩點間的最短距離矩陣和路由矩陣，且能查

22、詢?nèi)我鈨牲c間的最短距離和路由。二 實驗原理1 定理對于圖 G，如果 wi,j 表示端 i 到端 j 的可實現(xiàn)的距離，那么 wi,j 表示端 i 到端 j 之間的最短距離當(dāng)且僅當(dāng)對于任意 i,j,k，有wi,jwi,k+w(k,j)2 Floyd算法原理Floyd算法通過迭代運算消除不滿足上述定理的情況。具體在實現(xiàn)中，F(xiàn)loyd算法使用兩個矩陣表示：一個為距離矩陣，一個為路由矩陣。在迭代過沖中，路由矩陣依照距離矩陣變化。3 Floyd算法步驟給定圖 G 及其邊 i,j 的權(quán) wi,j (1in, 1jn)，則F0：初始化距離矩陣 W(0) 和路由矩陣 R(0) 為W(0)=i,j0n×

23、nR(0)=ri,j0n×n其中i,j0=&i,j ei,jE& ei,jE&0 i=jri,j(0)=&j i,j0&0 otherwiseF1：已求得 W(k-1) 和 R(k-1)，依據(jù)下面的迭代求W(k) 和 R(k)i,jk=mini,jk-1,i,kk-1+k,jk-1ri,j(k)=&ri,kk-1 i,jk<i,jk-1&ri,jk-1 i,jk=i,jk-1F2：若 k<n，重復(fù)；k=n，終止。三 實驗描述1 實驗思路1) 求最短距離矩陣及路由矩陣 初始化最短距離矩陣為輸入矩陣 W:=M； 初始化路

24、由矩陣 Rij:=j； 置 k=1； i=1:n，對每個 i，如果 wijwik+wkj，則更新 wij 及 Rij； k=k+1； 如 nk，轉(zhuǎn)向步驟，否則停止。2) 求最短路徑 最短路徑為 X=wij； 置路徑初始位置為 D1=i，置 k=1； 如 Rij=j，轉(zhuǎn)向步驟； k=k+1； 查路由矩陣 R，令 Dk=Rij，令 i=Rij； 轉(zhuǎn)向步驟； Dk+1=j。2 流程圖3 主要的函數(shù)1) 求最短距離矩陣及路由矩陣function W,R = floyd(M)n=size(M,1);%order of matrixW=M;%initialization of ShortestPath m

25、atrixR=zeros(n,n);%Routing matrixfor i = 1:nfor j = 1:nif (W(i,j) = inf) & (i = j)R(i,j) = j;%initialization of Routing matrixendendendfor k = 1:nfor i = 1:nfor j = 1:nif W(i,k) + W(k,j) < W(i,j)W(i,j) = W(i,k) + W(k,j);%update ShortestPath matrixR(i,j) = R(i,k);%uodate Routing matrixendenden

26、dend2) 求最短路徑function X,D = found(W,R,i,j)D = ;%initialization of path matrixD(1) = i;%start from iX = W(i,j);%shortest distancek = 1;while (R(i,j) = j)k = k + 1;D(k) = R(i,j);%next pathi = R(i,j);endD(k+1) = j;%end in jend四 結(jié)果分析為了檢驗算法的正確性，我們以課本的例子進(jìn)行了試驗。輸入的矩陣如下圖所示：經(jīng)過Floyd算法得到的最短距離矩陣以及路由矩陣與課本的答案一致，如下所

27、示：以下是求任意點間最短路徑及其路由的實驗，如下圖所示：結(jié)果與理論值一樣，說明算法的正確性。實驗四 圖的連通性分析一 實驗內(nèi)容編寫圖的連通性判斷算法，判斷圖是否連通以及連通分支的個數(shù)。二 實驗原理1 Warshall算法設(shè)矩陣 P 為判斷矩陣，pij=1 表示從 i 到 j 連通，pij=0 表示從 i 到 j 不連通。當(dāng) pij=1 即 i 到 j 連通時，若 pjk=1 即 j 到 k 連通，則 pik=1 即 i 到 k 連通。依次判斷 P 的每一行或每一列，對矩陣的值進(jìn)行更新。2 Matrix Power算法對鄰接矩陣 C 求冪，若 cijn=1，表示至少存在一個長度為 n 的鏈?zhǔn)?i

28、 到 j 連通。三 實驗描述1 實驗思路1) Warshall算法 置新矩陣 P:=C； 置 i=1； 對所有的 j，如果 pij=1，則對 k=1,2,n，有 pij=pjkpik； i=i+1； 如 ni，轉(zhuǎn)向步驟，否則停止。2) Matrxi Power算法 置新矩陣 P:=0； 置 i=1； 計算 Pi； P=P+Pi , i=i+1； 如 ni，轉(zhuǎn)向步驟，否則停止。2 流程圖3 主要的函數(shù)1) Warshall算法function G,S = Warshall(C)%initializationn = size(C,1);%order of matrix CG = zeros(1,n

29、);%initialization of connected component matrixa = 1;for i = 1:nif sum(C(i,:) = 0%if i is an isolated pointG(i) = a;a = a + 1;elsefor j = 1:nif C(i,j) = 1%if i is connected to jif G(i) = G(j)%if i and j are in a pathif G(i) = 0%if does not mark G(i)G(i) = a;%set i and j in a pathG(j) = a;a = a + 1;endelse%if i and j are