北邮通信网实验报告.docx

《北邮通信网实验报告.docx》由会员分享，可在线阅读，更多相关《北邮通信网实验报告.docx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 0.000001)if (b - b_temp) * (b - b_temps) t=1-e-t, t03 服务规则服务规则为：FIFO4 理论分析设系统到达率为 ，服务率为 ，则理论分析如下：理论平均等待时间：Ew=1-理论平均排队时间：Eq=(-)理论系统中平均顾客数：EN=-理

4、论系统中平均等待队长：ENq=(-)三 实验描述1 实验思路仿真时序图示例时序关系图如下：各参数含义如下：bi：第i个事件（到达或离开）发生的时间ti：第i个到达事件发生的时间ci：第i个离开事件发生的时间Ai：第（i-1）个顾客与第i个顾客到达时间间隔Di：第i个顾客排队等待时间间隔Si：第i个顾客服务时间长度仿真设计算法1）利用负指数分布与泊松过程的关系，产生符合泊松过程的顾客流；2）分别构建一个顾客到达队列和一个顾客等待队列。顾客到达后，首先进入到达的队尾排队，并检测是否有顾客等待以及是否有服务台空闲，如果无人等待并且有服务员空闲则进入服务状态，否则顾客将进入等待队列的队尾等待；3）产生

5、符合负指数分布的随机变量作为每个顾客的服务时间；4）当服务员结束一次服务后，就取出等待队列中位于对头的顾客进入服务状态，如果迭代队列为空则服务台空闲等待下一位顾客到来；5）在系统到达稳态时，计算系统的平均等待时间以及平均等待队长等数据。2 流程图3 主要的函数1) 产生符合泊松过程的顾客流Interval_Arrive=-log(rand(1,SimTotal)/Lambda; %Arrival Time Interval2) 产生符合负指数分布的服务时间Interval_Serve=-log(rand(1,SimTotal)/Mu;%Service Time3) 计算顾客到达时间%*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) 计算顾客离开时间%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) 计算平均等待时间t_Wait=t_Leave-t_Arrive;%Waiting Time for each Customert_Wait_avg=mean(t_Wait)

8、;%Average Waiting Time6) 计算平均排队时间t_Queue=t_Wait-Interval_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

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) 仿真图：各顾客到达时间与离去时间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) 仿真图：系统等待队长分布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) 仿真图：各顾客在系统中的排队时间和等待时间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);四 结果分析为了检验算法的正确性，我们进行了多次实验。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

13、.94）分析从上面几次实验结果可以看出，仿真的结果基本符合理论分析的结果。在系统存在稳态时，即 时，仿真结果与理论分析结果的误差较小，此误差值仿真次数即 SimTotal 的值的大小影响比较明显，当 SimTotal 的值较小时，误差比较大，当 SimTotal 的值较大时，误差比较小。2 仿真图分析由于仿真图过多，这里只选取其中一次实验的仿真图，其他图片在上传文件的压缩包中。这里选择第一次实验的仿真图。1）各顾客的到达时间与离去时间横轴表示的是5000个顾客的编号，纵轴表示的是每个顾客到达或离去的时间点（蓝线表示的是到达的时间点，红线表示的是离去的时间点）。两条线均严格单调递增，原因是顾客按

14、编号的顺序依次到来以及依次接受服务，在只有一个服务员的情况下，先到的顾客会先接受服务，因此也会先离去。两条线的差值表示的是顾客在系统中的时间，包括排队时间及服务时间，由于每个顾客在系统的时间相对于所有顾客总时间来说占很小一部分，因此两条线看起来基本重合。2）系统顾客数分布横轴表示的是所有顾客的总时间，纵轴表示的是对应每个时间点的系统顾客数情况。由图可以看出，系统大部分时间，顾客数保持在 02 之间，与理论分析情况一致。3）各顾客在系统中的排队时间和等待时间横轴表示的是5000个顾客的编号，纵轴表示的是每个顾客排队或等待的时间点（蓝线表示的是排队时间，红线表示的是等待时间，两条线的差值表示的是服

15、务时间）。实验三 Floyd算法一 实验内容实现Floyd算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。二 实验原理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 及其边

16、i,j 的权 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)，依据下面的迭代求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，重复；k=n，终止。三 实验描述1 实验思路1) 求最短距离矩阵及路由矩阵 初始化最短

17、距离矩阵为输入矩阵 W:=M； 初始化路由矩阵 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;%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;四 结果分析1 实验结果我们随机生成n阶零一矩阵，使用以下两种算法计算图的连通性。生成零一矩阵的代码如下：funct

19、ion C = Random_0_1_Matrix(n)A = rand(n);C = A/2 + A/2;C = round(C);for i = 1:nC(i,i) = 0;end运用上述代码，我们生成并选择了有代表性的几个矩阵如下：1）矩阵一2）矩阵二3）矩阵三4）矩阵四5）分析2 分析1）从上述几个实验可以看出，不管图是否连通，两种算法均能正确计算出图的连通分支数。2）两种算法程序运行的时间不同：在输入相同的情况下，Warshall算法的运行时间要小于Matrix_Power算法的于运行时间，原因是Matrix_Power算法涉及矩阵幂的计算，时间复杂度较高，而Warshall算法时间复杂度较低。