现代通信网课件通信网络设计基础

第3章通信网络设计基础第二讲本讲主要内容最短路径站址选择排队论基本概念1.最短路径——背景建立多个城市之间的有线通信网络，如何确定能够连接所有城市并使得线路费用最小的网络结构？在一定网络结构上，如何选择通信路由，怎样确定首选路由和迂回路由？这些问题都归结到路径选择或者路径优化问题上来。1.1最小支撑树寻找最小支撑树是一个优化问题，可以分为两种情况：无限制条件（无约束条件）和有限制条件（有约束条件）。这里重点介绍无限制条件的最小支撑树搜索方法。求无限制条件的最小支撑树的方法：K方法和P方法求解最小支撑树的Kruskal

方法（K方法）例3-3求解最小支撑树的Prim方法（P方法）求有限制条件的最小支撑树的方法在设计通信网的网络结构时，经常会提出一些特殊要求，如：两个交换中心通信时，转接的次数不能太多；某条线路上的话务量不能太大等等。这类问题可以归结为在限制条件下求最小支撑树。求有约束条件的最小支撑树的方法简单来说是这样的：先按照上述K方法或者P方法求出无约束条件的最小支撑树，然后根据所给的约束条件对网络结构进行调整，使之既满足约束条件，又尽量接近最小支撑树。1.2点间最短路径在通信网的网络结构确定以后，任意两点之间的通信，首选路由是它们之间的最短路由，这是求两点间最短路径的问题。两点间的最短路径问题有两种情况：（1）指定点到其他点的最短路径和（2）任意两点间的最短路径。指定点到其他点的最短路径求指定点到其他各点的最短路径，Dijkstra算法（简称D算法）是最有效的算法之一。D算法的具体步骤例3-5任意两点之间的最短路径算法求任意两点之间的最短路径，可以依次选择每个点为指定点，用D算法做n次运算，但这样做比较繁琐。下面介绍一种更为有效的算法——Floyd算法，简称F算法。F算法的原理与D算法相同，只是使用矩阵形式进行运算，有利于在计算机中进行处理。例3-63.站址选择实际通信网中，可以设立新的交换局，或者在某些交换局之间设立汇接局或高等级的交换局，它的位置选择应能使得路径最短或者网的总费用最小。新交换局可以设立一个或者多个，在数学上是求单中位点或者多中位点的问题。3.1单中位点距离测度单中位点位置的确定（矩形线测度）3.排队论基本概念1.排队系统的概念（1）排队论与排队系统的概念顾客——要求服务的一方；服务机构——提供服务的一方服务员——服务机构内的具体设施排队现象产生的原因和排队论需要解决的问题顾客需求的随机性和服务设施的有限性是产生排队现象的根本原因。排队论就是利用概率论和随机过程的理论，研究随机服务系统内服务机构与顾客需求之间的关系，以便合理地设计和控制排队系统。由于顾客到达的数目和要求提供服务的时间长短都是不确定的，这种要求随机服务的顾客和服务机构两个方面构成的系统称为随机服务系统或者排队系统。3.排队论基本概念（2）排队系统的一般表示任何一个排队系统都有以下过程：顾客到达服务机构，若服务员有空闲便立刻得到服务，若服务员不空闲，则需要排队等待服务员有空闲时再接受服务，服务完后离开服务机构。图3-213.2排队系统的基本参数3.2排队系统的基本参数3.3排队系统的三个特征3.3排队系统的三个特征3.3排队系统的三个特征3.3排队系统的三个特征3.3排队系统的三个特征综上所述，无论是顾客输入过程，还是服务过程，只要是最简单流，则所对应的概率分布函数都为负指数分布，又称M分布。3.3排队系统的三个特征3.4排队系统的几个主要指标及李特尔（Little）定律3.4排队系统的几个主要指标及李特尔（Little）定律3.4排队系统的几个主要指标及李特尔（Little）定律3.4排队系统的几个主要指标及李特尔（Little）定律3.5排队系统的分类3.5排队系统的分类3.6M/M/1排队系统3.6M/M/1排队系统3.6M/M/1排队系统3.6M/M/1排队系统3.7M/M/m/n排队系统3.7M/M/m/n排队系统3.8排队论在通信网中的应用3.8排队论在通信网中的应用本次课内容回顾最小支撑树求解的目的最小支撑树及其求解方法K方法和P方法最短路径求解的目的点间最短路径求解方法：指定点到其他点的