北邮 通信网实验报告

1、北京邮电大学实验报告通信网理论基础实验报告学院: 信息与通信工程学院 班级: 2013211124 学号: 姓名: 实验一 ErlangB公式计算器一 实验内容编写Erlang B公式的图形界面计算器，实现给定任意两个变量求解第三个变量的功能：1）给定到达的呼叫量a和中继线的数目s，求解系统的时间阻塞率B；2）给定系统的时间阻塞率的要求B和到达的呼叫量a，求解中继线的数目s，以实现网络规划；3）给定系统的时间阻塞率要求B以及中继线的数目s，判断该系统能支持的最大的呼叫量a。二 实验描述1 实验思路使用MATLAB GUITOOL设计图形界面，通过单选按钮确定计算的变量，同时通过可编辑文本框输入

2、其他两个已知变量的值，对于不同的变量，通过调用相应的函数进行求解并显示最终的结果。2 程序界面3 流程图4 主要的函数符号规定如下：b(Blocking)：阻塞率；a(BHT)：到达呼叫量；s(Lines)：中继线数量。1）已知到达呼叫量a及中继线数量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）已知到达呼叫量a及阻塞率b求中继线数量s考虑到s为正整数，因此采用数值逼近的方法。采用循环的方式，在每次

3、循环中增加s的值，同时调用 Bs,a 函数计算阻塞率并与已知阻塞率比较，当本次误差小于上次误差时，结束循环，得到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及中继线数量s求到达呼叫量a考虑到a为有理数，因此采用变步长逼近的方法。采用循环的方式，在每

4、次循环中增加a的值（步长为 s/2），同时调用 Bs,a 函数计算阻塞率并与已知阻塞率比较，当本次误差小于预设阈值时，结束循环，得到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.000001)if (b - b_temp) * (b - b_temps) < 0)step = step / 2;elsea = a + step;endb_temp = Erl

5、angB_b(a,s);b_temps = ErlangB_b(a + step,s);endend三 结果分析1) 已知到达呼叫量a及中继线数量s求阻塞率ba100100100100100100100s125102050100b0.99010.98020.95050.90110.80240.50930.0757a5102050100s1010101010b0.01840.21460.53800.80470.90112) 已知到达呼叫量a及阻塞率b求中继线数量sa125102050100b0.50.50.50.50.50.50.5s1236112651a1010101010b0.10.20.5

6、0.81.0s13106213) 已知阻塞率b及中继线数量s求到达呼叫量ab0.50.50.50.50.50.50.5s125102050100a12.73208.436918.272638.159298.0719198.0377b0.10.20.50.60.8s1010101010a7.51069.685018.272623.479848.78634）分析将程序结果与在线ErlangB公式计算器结果进行比较，结果基本一致，说明程序的正确性。实验二 M/M/1排队系统一 实验内容实现M/M/1单窗口无限排队系统的系统仿真，利用事件调度法实现离散事件系统仿真，并统计平均队列长度以及平均等待时间等

7、值，以与理论分析结果进行对比。二 实验原理1 顾客到达模式设到达过程是一个参数为 的Poisson过程，则长度为 t 的时间内到达 k 个呼叫的概率Pkt 服从Poisson分布，即Pkt=tkk!et2 服务模式设每个呼叫的持续时间为 t，则服从参数为 t 的负指数分布，即PX>t=1-e-t, t03 服务规则服务规则为：FIFO4 理论分析设系统到达率为 ，服务率为 ，则理论分析如下：理论平均等待时间：Ew=1-理论平均排队时间：Eq=(-)理论系统中平均顾客数：EN=-理论系统中平均等待队长：ENq=(-)三 实验描述1 实验思路仿真时序图示例时序关系图如下：各参数含义如下：bi

8、：第i个事件（到达或离开）发生的时间ti：第i个到达事件发生的时间ci：第i个离开事件发生的时间Ai：第（i-1）个顾客与第i个顾客到达时间间隔Di：第i个顾客排队等待时间间隔Si：第i个顾客服务时间长度仿真设计算法1）利用负指数分布与泊松过程的关系，产生符合泊松过程的顾客流；2）分别构建一个顾客到达队列和一个顾客等待队列。顾客到达后，首先进入到达的队尾排队，并检测是否有顾客等待以及是否有服务台空闲，如果无人等待并且有服务员空闲则进入服务状态，否则顾客将进入等待队列的队尾等待；3）产生符合负指数分布的随机变量作为每个顾客的服务时间；4）当服务员结束一次服务后，就取出等待队列中位于对头的顾客进入

9、服务状态，如果迭代队列为空则服务台空闲等待下一位顾客到来；5）在系统到达稳态时，计算系统的平均等待时间以及平均等待队长等数据。2 流程图3 主要的函数1) 产生符合泊松过程的顾客流Interval_Arrive=-log(rand(1,SimTotal)/Lambda; %Arrival Time Interval2) 产生符合负指数分布的服务时间Interval_Serve=-log(rand(1,SimTotal)/Mu;%Service Time3) 计算顾客到达时间%*Arrive Time for each Customer*t_Arrive(1)=Interval_Arrive(1

10、);ArriveNum(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_Lea

11、ve(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) 计算平均等待时间t_Wait=t_Leave-t_Arrive;%Waiting Time for each Customert_Wait_avg=mean(t_Wait);%Average Waiting Time6) 计算平均排队时间t_Queue=t_Wait-Int

12、erval_Serve;%Queueing Time for each Customert_Queue_avg=mean(t_Queue);%Average Queueing Time7) 计算平均顾客数%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=z

13、eros(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-

14、1)-1;%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_f

15、romStart.*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_av

16、g=sum(0 QueLength.*Time_interval 0 )/Timepoint(end);9) 仿真图：各顾客到达时间与离去时间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(&#

17、39;Customer ID');ylabel('Arrive/Leave Time(Accumulated)');10) 仿真图：系统等待队长分布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、) 仿真图：各顾客在系统中的排队时间和等待时间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、9;);ylabel('Queueing/Waiting Time');legend('Queueing Time','Waiting Time');四 结果分析为了检验算法的正确性，我们进行了多次实验。1 数值分析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）分析从上面几次实验结果可以看出，仿真的结果基本符合理论分析的结果。在系统存在稳态时，即 < 时，仿真结果与理论分析结果的误差

20、较小，此误差值仿真次数即 SimTotal 的值的大小影响比较明显，当 SimTotal 的值较小时，误差比较大，当 SimTotal 的值较大时，误差比较小。2 仿真图分析由于仿真图过多，这里只选取其中一次实验的仿真图，其他图片在上传文件的压缩包中。这里选择第一次实验的仿真图。1）各顾客的到达时间与离去时间横轴表示的是5000个顾客的编号，纵轴表示的是每个顾客到达或离去的时间点（蓝线表示的是到达的时间点，红线表示的是离去的时间点）。两条线均严格单调递增，原因是顾客按编号的顺序依次到来以及依次接受服务，在只有一个服务员的情况下，先到的顾客会先接受服务，因此也会先离去。两条线的差值表示的是顾客在

21、系统中的时间，包括排队时间及服务时间，由于每个顾客在系统的时间相对于所有顾客总时间来说占很小一部分，因此两条线看起来基本重合。2）系统顾客数分布横轴表示的是所有顾客的总时间，纵轴表示的是对应每个时间点的系统顾客数情况。由图可以看出，系统大部分时间，顾客数保持在 02 之间，与理论分析情况一致。3）各顾客在系统中的排队时间和等待时间横轴表示的是5000个顾客的编号，纵轴表示的是每个顾客排队或等待的时间点（蓝线表示的是排队时间，红线表示的是等待时间，两条线的差值表示的是服务时间）。实验三 Floyd算法一 实验内容实现Floyd算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵

22、，且能查询任意两点间的最短距离和路由。二 实验原理1 定理对于图 G，如果 wi,j 表示端 i 到端 j 的可实现的距离，那么 wi,j 表示端 i 到端 j 之间的最短距离当且仅当对于任意 i,j,k，有wi,jwi,k+w(k,j)2 Floyd算法原理Floyd算法通过迭代运算消除不满足上述定理的情况。具体在实现中，Floyd算法使用两个矩阵表示：一个为距离矩阵，一个为路由矩阵。在迭代过冲中，路由矩阵依照距离矩阵变化。3 Floyd算法步骤给定图 G 及其边 i,j 的权 wi,j (1in, 1jn)，则F0：初始化距离矩阵 W(0) 和路由矩阵 R(0) 为W(0)=i,j0n&#

23、215;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)，依据下面的迭代求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，重复；k=n，终止。三 实验描述1 实验思路1) 求最短距离矩阵及路由矩阵 初始化最短距离矩阵为输入矩阵 W:=M；

24、初始化路由矩阵 Rij:=j； 置 k=1； i=1:n，对每个 i，如果 wijwik+wkj，则更新 wij 及 Rij； k=k+1； 如 nk，转向步骤，否则停止。2) 求最短路径 最短路径为 X=wij； 置路径初始位置为 D1=i，置 k=1； 如 Rij=j，转向步骤； k=k+1； 查路由矩阵 R，令 Dk=Rij，令 i=Rij； 转向步骤； Dk+1=j。2 流程图3 主要的函数1) 求最短距离矩阵及路由矩阵function W,R = floyd(M)n=size(M,1);%order of matrixW=M;%initialization of ShortestPa

25、th 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) < W(i,j)W(i,j) = W(i,k) + W(k,j);%update ShortestPath matrixR(i,j) = R(i,k);%uodate Routing matrixende

26、ndendend2) 求最短路径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四 结果分析为了检验算法的正确性，我们以课本的例子进行了试验。输入的矩阵如下图所示：经过Floyd算法得到的最短距离矩阵以及路由矩阵与课本的答案一致

27、，如下所示：以下是求任意点间最短路径及其路由的实验，如下图所示：结果与理论值一样，说明算法的正确性。实验四 图的连通性分析一 实验内容编写图的连通性判断算法，判断图是否连通以及连通分支的个数。二 实验原理1 Warshall算法设矩阵 P 为判断矩阵，pij=1 表示从 i 到 j 连通，pij=0 表示从 i 到 j 不连通。当 pij=1 即 i 到 j 连通时，若 pjk=1 即 j 到 k 连通，则 pik=1 即 i 到 k 连通。依次判断 P 的每一行或每一列，对矩阵的值进行更新。2 Matrix Power算法对邻接矩阵 C 求幂，若 cijn=1，表示至少存在一个长度为 n 的

28、链使 i 到 j 连通。三 实验描述1 实验思路1) Warshall算法 置新矩阵 P:=C； 置 i=1； 对所有的 j，如果 pij=1，则对 k=1,2,n，有 pij=pjkpik； i=i+1； 如 ni，转向步骤，否则停止。2) Matrxi Power算法 置新矩阵 P:=0； 置 i=1； 计算 Pi； P=P+Pi , i=i+1； 如 ni，转向步骤，否则停止。2 流程图3 主要的函数1) Warshall算法function G,S = Warshall(C)%initializationn = size(C,1);%order of matrix CG = zeros

29、(1,n);%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 a