北郵 通信網(wǎng)實(shí)驗(yàn)報(bào)告

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

2、其他兩個(gè)已知變量的值，對于不同的變量，通過調(diào)用相應(yīng)的函數(shù)進(jìn)行求解并顯示最終的結(jié)果。2 程序界面3 流程圖4 主要的函數(shù)符號(hào)規(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的值，同時(shí)調(diào)用 Bs,a 函數(shù)計(jì)算阻塞率并與已知阻塞率比較，當(dāng)本次誤差小于上次誤差時(shí)，結(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 0.000001)if (b - b_temp) * (b - b_temps) t=1-e-t, t03 服務(wù)規(guī)則服務(wù)規(guī)則為：FIFO4 理論分析設(shè)系統(tǒng)到達(dá)率為 ，服務(wù)率為 ，則理論分析如下：理論平均等待時(shí)間：Ew=1-理論平均排隊(duì)時(shí)間：Eq=(-)理論系統(tǒng)中平均顧客數(shù)：EN=-理

4、論系統(tǒng)中平均等待隊(duì)長：ENq=(-)三 實(shí)驗(yàn)描述1 實(shí)驗(yàn)思路仿真時(shí)序圖示例時(shí)序關(guān)系圖如下：各參數(shù)含義如下：bi：第i個(gè)事件（到達(dá)或離開）發(fā)生的時(shí)間ti：第i個(gè)到達(dá)事件發(fā)生的時(shí)間ci：第i個(gè)離開事件發(fā)生的時(shí)間Ai：第（i-1）個(gè)顧客與第i個(gè)顧客到達(dá)時(shí)間間隔Di：第i個(gè)顧客排隊(duì)等待時(shí)間間隔Si：第i個(gè)顧客服務(wù)時(shí)間長度仿真設(shè)計(jì)算法1）利用負(fù)指數(shù)分布與泊松過程的關(guān)系，產(chǎn)生符合泊松過程的顧客流；2）分別構(gòu)建一個(gè)顧客到達(dá)隊(duì)列和一個(gè)顧客等待隊(duì)列。顧客到達(dá)后，首先進(jìn)入到達(dá)的隊(duì)尾排隊(duì)，并檢測是否有顧客等待以及是否有服務(wù)臺(tái)空閑，如果無人等待并且有服務(wù)員空閑則進(jìn)入服務(wù)狀態(tài)，否則顧客將進(jìn)入等待隊(duì)列的隊(duì)尾等待；3）產(chǎn)生

5、符合負(fù)指數(shù)分布的隨機(jī)變量作為每個(gè)顧客的服務(wù)時(shí)間；4）當(dāng)服務(wù)員結(jié)束一次服務(wù)后，就取出等待隊(duì)列中位于對頭的顧客進(jìn)入服務(wù)狀態(tài)，如果迭代隊(duì)列為空則服務(wù)臺(tái)空閑等待下一位顧客到來；5）在系統(tǒng)到達(dá)穩(wěn)態(tài)時(shí)，計(jì)算系統(tǒng)的平均等待時(shí)間以及平均等待隊(duì)長等數(shù)據(jù)。2 流程圖3 主要的函數(shù)1) 產(chǎn)生符合泊松過程的顧客流Interval_Arrive=-log(rand(1,SimTotal)/Lambda; %Arrival Time Interval2) 產(chǎn)生符合負(fù)指數(shù)分布的服務(wù)時(shí)間Interval_Serve=-log(rand(1,SimTotal)/Mu;%Service Time3) 計(jì)算顧客到達(dá)時(shí)間%*Arri

6、ve Time for each Customer*t_Arrive(1)=Interval_Arrive(1);ArriveNum(1)=1;for i=2:SimTotal t_Arrive(i)=t_Arrive(i-1)+Interval_Arrive(i); ArriveNum(i)=i;end4) 計(jì)算顧客離開時(shí)間%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 custo

7、mer arrives after the former has been served. t_Leave(i)=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) 計(jì)算平均等待時(shí)間t_Wait=t_Leave-t_Arrive;%Waiting Time for each Customert_Wait_avg=mean(t_Wait)

8、;%Average Waiting Time6) 計(jì)算平均排隊(duì)時(shí)間t_Queue=t_Wait-Interval_Serve;%Queueing Time for each Customert_Queue_avg=mean(t_Queue);%Average Queueing Time7) 計(jì)算平均顧客數(shù)%TimelineTimepoint=t_Arrive,t_Leave;%Record Arrival Time & Leaving Time for each Customer.Timepoint=sort(Timepoint);%Sort all Timepoints.ArriveFlag

9、=zeros(size(Timepoint);%Flag of ArrivalCusNum=zeros(size(Timepoint);temp=2; CusNum(1)=1;for i=2:length(Timepoint)if (temp=2QueLength(i)=CusNum(i)-1;%Excluding Customer being ServicedelseQueLength(i)=0;endend%Average Waiting Length of QueueQueLength_avg=sum(0 QueLength.*Time_interval 0 )/Timepoint(en

10、d);9) 仿真圖：各顧客到達(dá)時(shí)間與離去時(shí)間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(Customer ID);ylabel(Arrive/Leave Time(Accumulated);10) 仿真圖：系統(tǒng)等待隊(duì)長分布subplot(2,2,2);stairs(Timepoint,Cu

11、sNum,b)axis(0 Timepoint(end) 0 max(CusNum)title(Distribution of System Customer Number);xlabel(Time(Accumulated);ylabel(Customer Number);11) 仿真圖：各顧客在系統(tǒng)中的排隊(duì)時(shí)間和等待時(shí)間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 ma

12、x(max(t_Queue),max(t_Wait);title(Queueing Time and Waiting Time for each customer);xlabel(Customer ID);ylabel(Queueing/Waiting Time);legend(Queueing Time,Waiting Time);四 結(jié)果分析為了檢驗(yàn)算法的正確性，我們進(jìn)行了多次實(shí)驗(yà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

13、.94）分析從上面幾次實(shí)驗(yàn)結(jié)果可以看出，仿真的結(jié)果基本符合理論分析的結(jié)果。在系統(tǒng)存在穩(wěn)態(tài)時(shí)，即 時(shí)，仿真結(jié)果與理論分析結(jié)果的誤差較小，此誤差值仿真次數(shù)即 SimTotal 的值的大小影響比較明顯，當(dāng) SimTotal 的值較小時(shí)，誤差比較大，當(dāng) SimTotal 的值較大時(shí)，誤差比較小。2 仿真圖分析由于仿真圖過多，這里只選取其中一次實(shí)驗(yàn)的仿真圖，其他圖片在上傳文件的壓縮包中。這里選擇第一次實(shí)驗(yàn)的仿真圖。1）各顧客的到達(dá)時(shí)間與離去時(shí)間橫軸表示的是5000個(gè)顧客的編號(hào)，縱軸表示的是每個(gè)顧客到達(dá)或離去的時(shí)間點(diǎn)（藍(lán)線表示的是到達(dá)的時(shí)間點(diǎn)，紅線表示的是離去的時(shí)間點(diǎn)）。兩條線均嚴(yán)格單調(diào)遞增，原因是顧客按

14、編號(hào)的順序依次到來以及依次接受服務(wù)，在只有一個(gè)服務(wù)員的情況下，先到的顧客會(huì)先接受服務(wù)，因此也會(huì)先離去。兩條線的差值表示的是顧客在系統(tǒng)中的時(shí)間，包括排隊(duì)時(shí)間及服務(wù)時(shí)間，由于每個(gè)顧客在系統(tǒng)的時(shí)間相對于所有顧客總時(shí)間來說占很小一部分，因此兩條線看起來基本重合。2）系統(tǒng)顧客數(shù)分布橫軸表示的是所有顧客的總時(shí)間，縱軸表示的是對應(yīng)每個(gè)時(shí)間點(diǎn)的系統(tǒng)顧客數(shù)情況。由圖可以看出，系統(tǒng)大部分時(shí)間，顧客數(shù)保持在 02 之間，與理論分析情況一致。3）各顧客在系統(tǒng)中的排隊(duì)時(shí)間和等待時(shí)間橫軸表示的是5000個(gè)顧客的編號(hào)，縱軸表示的是每個(gè)顧客排隊(duì)或等待的時(shí)間點(diǎn)（藍(lán)線表示的是排隊(duì)時(shí)間，紅線表示的是等待時(shí)間，兩條線的差值表示的是服

15、務(wù)時(shí)間）。實(shí)驗(yàn)三 Floyd算法一 實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)Floyd算法，可對輸入的鄰接距離矩陣計(jì)算圖中任意兩點(diǎn)間的最短距離矩陣和路由矩陣，且能查詢?nèi)我鈨牲c(diǎn)間的最短距離和路由。二 實(shí)驗(yàn)原理1 定理對于圖 G，如果 wi,j 表示端 i 到端 j 的可實(shí)現(xiàn)的距離，那么 wi,j 表示端 i 到端 j 之間的最短距離當(dāng)且僅當(dāng)對于任意 i,j,k，有wi,jwi,k+w(k,j)2 Floyd算法原理Floyd算法通過迭代運(yùn)算消除不滿足上述定理的情況。具體在實(shí)現(xiàn)中，F(xiàn)loyd算法使用兩個(gè)矩陣表示：一個(gè)為距離矩陣，一個(gè)為路由矩陣。在迭代過沖中，路由矩陣依照距離矩陣變化。3 Floyd算法步驟給定圖 G 及其邊

16、i,j 的權(quán) wi,j (1in, 1jn)，則F0：初始化距離矩陣 W(0) 和路由矩陣 R(0) 為W(0)=i,j0nnR(0)=ri,j0nn其中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,jki,jk-1&ri,jk-1 i,jk=i,jk-1F2：若 kn，重復(fù)；k=n，終止。三 實(shí)驗(yàn)描述1 實(shí)驗(yàn)思路1) 求最短距離矩陣及路由矩陣 初始化最短

17、距離矩陣為輸入矩陣 W:=M； 初始化路由矩陣 Rij:=j； 置 k=1； i=1:n，對每個(gè) 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;%initializati

18、on of ShortestPath matrixR=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) 0G(j) = G(i);endendendendS = S - 1;四 結(jié)果分析1 實(shí)驗(yàn)結(jié)果我們隨機(jī)生成n階零一矩陣，使用以下兩種算法計(jì)算圖的連通性。生成零一矩陣的代碼如下：function C = Random_0_1_Ma