通信网实验指导书
- 格式：docx
- 大小：38.15 KB
- 文档页数：3
通信网实验指导书
通信网理论基础实验指导书
吉林大学通信工程学院通信网课程组
2021年5月
目 录
实验一：路径选择实验 .................................... 1 实验二：通信业务量分析实验 ............................... 4 实验三：Gompertz（龚伯兹）模型实验 ....................... 8 实验四：Logistic（罗吉特）模型实验 ...................... 13
实验一：路径选择实验
一、实验目的
在进行通信网选择路由时，首选路由和各个迂回路由通常都是按照路径最短的原则进行的，目的是为了使网络费用达到最小。在求解最短径的算法中常用的有D算法和F算法。D算法用于求指定节点到其他各节点的最短路径；F算法用于求任意端间最短径。在实际中都是由计算机实现这两种算法来帮助设计人员进行路由设计。本次实验目的就是要使学生深入理解这两种算法并能用计算机实现这两种算法。
二、实验内容
1． 用编程语言实现D算法。 2． 用编程员实现F算法。
三、实验原理
（一）D算法
1．D算法原理
已知图G=(V,E)，将其节点集分为两组：置定节点集Gp和未置定节点集G-Gp。其中Gp内的所有置定节点，是指定点vs到这些节点的路径为最短（即已完成最短路径的计算）的节点。而G-Gp内的节点是未置定节点，即vs到未置定节点距离是暂时的，随着算法的下一步将进行不断调整，使其成为最短径。在调整各未
置定节点的最短径时，是将Gp中的节点作为转接点。具体地说，就是将Gp中
的节点作为转接点，计算（vs,vj）的径长（vj∈G-Gp），若该次计算的径长小于上次的值，则更新径长，否则，径长不变。计算后取其中径长最短者，之后将vj划归到Gp中。当（G-Gp）最终成为空集，同时Gp=G，即求得vs到所有其他节点的最短路径。
wj：表示vs与其他节点的距离。
在Gp中，wi表示上一次划分到Gp中的节点vi到vs的最短路径。
在G-Gp中，表示从vs到vj (vj?G?Gp)仅经过Gp中的节点作为转接点所求得的该次的最短路径的长度。
如果vs与vj不直接相连，且无置定节点作为转接点，则令wj??。
1
2．D算法实现流程 D算法流程如图1所示。
ws=0；设Gp ={vs}，未置定节点集G-Gp，??dijvj∈G-Gp，s与j直接相连未置定节点标值wj=???vj∈G-Gp，s与j不直接相连重计算G-Gp中的wj的暂置值――修改wj值。G-Gp中的各个节点的最短径可能经vi转接（或不转接），重新对（G-Gp）中的wj值取?在G-Gp中找到点vj，使vs到点vj的距离最小，并将vj划归到Gpw*j=min(wj,wi+dij)vj?G-Gpvi?Gp以新Gp中的节点作为转接点，计算并修改（G-Gp）中的wj 选定所有w*j的最小值，并将其划归到Gp中：wi=minw*jvj?G-Gp得到新的Gp，vj与vs直连且dsi=mindsjvj?G-GPGp=nN将vi划归到Gp中，即新的
Gp?vs,vi，wi?dsi??Y所有节点被置定，算法终止 图1 D算法流程图
（二）F算法
1．F算法的基本思路
F算法使用距离矩阵和路由矩阵。
距离矩阵是一个n�wn矩阵，以图G的n个节点为行和列。记为W ?[wij]n?n，其中wij表示图G中vi和vj两点之间的路径长度。
路由矩阵是一个n�wn矩阵，以图G的n个节点为行和列。记为R?[rij]n?n，其中rij表示vi至vj经过的转接点（中间节点）。
F算法的思路是首先写出初始的W阵和R阵，接着按顺序依次将节点集中的各个节点作为中间节点，计算此点距其他各点的径长，每次计算后都以求得的与上次相比较小的径长去更新前一次较大径长，若后求得的径长比前次径长大或相等则不变。以此不断更新W和R，直至W中的数值收敛。
2．F算法实现流程 F算法流程如图2所示。
2
写出图G的初始距离矩阵W00W0=[wij]n?n?dij?0wij????0?当vi与vj间有边时，dij为边(i,j)长当vi与vj间没有边i=j以k为中间节点时，求第k次修改矩阵矩阵：kwk=[wij]n?nkk-1k-1k-1wij?min?wij,wik+wkj?：R0写出图G的初始路由矩阵以k为中间节点时，求第k次修改矩阵矩阵R?[r]0?j当w??,即i?j前次经过的转接点rij0??0?0w
ij??时或i?j时0 ij0ijn?nRk=
[rijk]n?n??kr??k?1??rijkijk?1k?1k?1wij?wik?wkjk?1k?1k?1wij?wik?wkj(即wij改动时)(即wij无改动时)k=k+1k=1k=nYY结束N 图2 F算法流程图
四、实验要求
1．自学熟悉某一种编程语言。
2．用自己熟悉的编程语言实现D算法和F算法。 3．记录下实验过程中遇到的问题。
4．写出实验报告。
3
感谢您的阅读，祝您生活愉快。
