基于模糊最小生成树的通信网络架设模型

《基于模糊最小生成树的通信网络架设模型》由会员分享，可在线阅读，更多相关《基于模糊最小生成树的通信网络架设模型（7页珍藏版）》请在金锄头文库上搜索。

1、基于模糊最小生成树的通信网络架设模型摘要：根据图论的擘求和模糊集合的原理对现代城域通信网络进行优化，以连接距离最短、网络建设费用最少、网络可靠性最高为目标建立模型，并且保证网络连通性、辐射状运行等约束条件，得到通信网络架设规化的近似最优解研究了网络建设中一些界限不分明的因素，建立了模糊最小生成树模型，它具有简单、实用、实时性强等特点，在现代城域网络建设中有很强的适用性关键词：通信网络；图论；模糊集合；最小生成树；算法 一、图论与模糊数学的引入近几年来。随着计算机网络应用蓬勃发展，新的网络产品和网络技术得到了进一步的应用，这使得计算机网络规模的扩展成为可能现实生活中有许多类似在城镇间架设电话线、

2、铺设管道、修筑道路的问题，通常在一些早期的发展阶段，由于技术或财力的局限，人们总是从节省材料或资金的角度，试图设计一个网络能够使不同城镇均能被直接或间接的连接起来，且总长度最短某省的个城市需要架设通信网络系统，为连接这个城市，每个城市之间的距离如表所示考虑地理环境的影响，综合考虑各城市之间的距离和每公里修建网络的费用，各城市之间修建网络每公里的费用可用与 10000 元之间的比较来估计（表） 试问如何架设通信网络，使总费用最小？对于此类网络架设问题，通常采用星型、环型或总线型网络拓扑结构。能够较好地解决网络建设过程中的连接和通信问题但仅仅是基于网络拓扑结构的网络构架，往往达不到建设费用最小的要

3、求图与网络是运筹学中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域因此，在网络拓扑结构的优化中引入图论的方法，以获得实际应用中较理想的网络建设方案 同时，以往对于此类问题的处理，通常都是采用精确数学的方法去解决 然而， 人们的思维中有许多没有明确外延的概念，即模糊概念语言上有许多模糊概念的词，例如以人的年龄为论域，那么“年青” 、 “中年” 、 “老年”都没有明确的外延在上述问题中所给出的“相当接近” 、 “可认为是” 、 “差不多是”等词都是模糊概念，无法用精确数学的方法去解决所以，又引入了模糊数学，模糊集合是其基本概念之

4、一表 1 各城市之间的距离 kmR2 R3 R4 R5 R6 R7R1 大致接近 可认为是 完全是 非常接近 很接近 可认为是R2 相当接近 比较接近 十分接近 差不多是 完全是R3 差不多是 可认为是 非常接近 比较接近R4 完全是 十分接近 很接近R5 大致接近 非常接近R6 比较接近表 2 各城市之间架设网络每公里的费用与 10 000 元之间的比较R2 R3 R4 R5 R6 R7R1 4 10 5 8 6 10R2 11 8 4 9 10R3 10 3 6 7R4 2 5 9R5 5 5R6 5二、相关概念及符号表示图论中相关概念及符号表示图、边、权、无向图、链、连通图、树、生成树、

5、最小生成树的概念及符号表示见文献 图论方法已经成为数学模型中重要的数学方法，许多数学问题如果能够归结为图论问题，往往能够迎刃而解，在计算机理论以及数学的其他分支中有广泛的应用在管理科学中，基于图论的统筹方法也得到广泛的应用许多图论问题可以化为线性规划问题，不过图论中的许多特殊算法比利用一般线性规划方法有效得多模糊数学相关概念及符号表示将被讨论的全体对象或范围叫做论域，常用 U，X ，Y，大写字母表示将论域中的每个对象称为元素，用相应的小写字母 u，v，e,x，y,表示隶属函数：用解析形式描术元素属于集合的程度设是论域上集合，记为()=1 当 0 当 集合的特征函数，也称为隶属函数模糊集：论域上

6、的模糊集合 由隶属函数 来表征，其中 在实轴的闭区间A () ()，上取值， 的值反映了中的元素 x 对于 的隶属程度() A模糊数学是研究现实中许多界限不分明问题的一种数学工具，它的主要概念包括模糊集合、隶属函数等模糊集合完全由隶属函数所刻划接下来用图论法和模糊集合的方法来解决网络架设问题的数学模型三、模型的建立与优化按照图论法的规则建立通信网络的图论模型，即以个相邻的城市为图的顶点，两顶点之间的网络线路为图的边，其定义如下：， ， ，（，） ，（，） ， （，） ， （，） ， （，） ， （，） ，（，） ， （，R） ， （，） ， （，） ， （，） ，（，） ， （，） ， （R，

7、） ， （，） ， （，） ，（，） ， （，） ， （，） ， （，） ， （，） 由该定义所构成的无向连通图如图所示每条边的权为某个顶点之间网络建设的费用，如联结顶点1 和2 的边上的权值记为 （1，） 因此，一个无向连通图可以定义为顶点、边、权值构成的集合，即一，W 通过以上定义，可将城市之间的通信网络架设问题转化为以建设费用最省为优化目标，求解最优通信网络的问题在建设费用函数未知的情况下，可先将建设网络的费用看作城市之间距离的线性函数，并考虑其他因素（地理、环境）的影响，先求解城域网络的初始布局，即将这些顶点用边联结起来，用两顶点间的直线距离与每公里网络建设费用的乘积作为边的权，使总的

8、权值最小可用图论中的求解最小生成树的方法求解4图 1 7 个城市网络的初试图论模型所以，问题的关键在于如何确定各条边上的权值在前面定义过，权值等于城市之间距离与每公里网络建设费用的乘积各城市之间的距离是以公里为单位的确定值，可以定义（ ， ）为两顶点 和 ，之间的距离，在表中已列出所有具体值由于考虑到受 地理、环境因素的影响，相同距离、不同地段的建设费用存在差别。而表中只列出了各地段每公里建设费用与 10000 元之间的比较关系，因此，引入模糊集合来表示这种界限不分明的情况前面提到过，模糊集合完全由隶属函数所刻划，隶属函数及其确定是模糊数学中最重要、最基本的量 在实际应用中，它的确定方法主要有

9、模糊统计法、德尔菲法、对比排序法、综合加权法等等，当然也可以直接使用常见的规则的隶属度函数，但必须知道变量的确定量度和意义按照表所列出的各种比较关系，根据语义规则，可以得到一个程度集合（完全是、可认为是、差不多是、非常接近、十分接近、相当接近、很接近、比较接近、大致接近） 根据相对于 10000 元的各种比较关系，分种情况讨论每公里网络建设的实际费用：（）10000 元是最大值；（）10000 元是最小值；（）10000 元是一个中间值由于问题要求求解最小费用，因此可以暂且只考虑以 10000 元为每公里网络建设费用的最大值，这样使得总花费最小于是给定程度集合的一个加权因子1,0.95,0.9

10、,0.85,0.8,0.75,0.7,0.65,0.6 ，这些因子与 10000 的乘积，可用于计算每公里网络建设费用的近似值在表中给出程度集合的符号表示以及按语义规则所分配的值通过上述定义，可以进一步描述图中联接每对顶点的边的权值, （1）(,)=(,)其中为常数 10000为计算每条边的权值，参照表至表得到个矩阵，其对应位置上分别列出 和 的值：(,) ,(4 10 5 8 6 10 11 8 4 9 10103 6 7 2 5 95 5 5)(0.60.951 0.850.70.95 0.750.650.8 0.9 10.90.950.850.65 1 0.8 0.70.60.85 0.

11、65)表 3 语义规则程度 符号 值完全是 C1 1可认为是 C2 0.95差不多是 C3 0.9非常接近 C4 0.85十分接近 C5 0.8相当接近 C6 0.75很接近 C7 0.7比较接近 C8 0.65大致接近 C9 0.6表 4 各城市之间网络建设费用 单位/百元 R2 R3 R4 R5 R6 R7R1 240 950 500 680 420 950R2 825 520 320 810 1000R3 900 285 510 455R4 200 400 630R5 300 425R6 325表是根据（）式计算得到的任意个城市之间网络建设的费用图论中求无向连通图一，的最小生成树法最小生

12、成树法将城域网络看作无向连通图，求该图的最小生成树，常用经典算法有算法、算法6 下面将介绍以算法解决上述问题的步骤四、程序实现及运行结果ruskal 算法思想及步骤每次添加权尽量小的边，使新的图无圈，直到生成棵树为止，便得最小生成树算法步骤如下：（）将赋权图中的边按权的非减次序排列；（）按（）排列的次序检查中的每一条边，如果这条边与已得到的边不产生圈，就取这一条边为解的一部分；（）若已取到一条边，算法终止，此时以为顶点集，以取到的 n 一条边为边集的图即为最小生成树程序流程赋权的连通图， 中| ，n|S1 对中各边的权排序，设 n,i=(ei).S2 初始化：0,T,k1,t0 S3 若n-1

13、 则转 S6，否则转 S4S4 若ek有圈则转 S4，否则转 S5S5 ek ， k,t,k，转 S3S6 输出 T 及 ,结束其中为最小树， 为 T 的权具体流程图见图图 2 Kruskal 算法流程程序实现及运行结果按照上述思想，用语言编写了算法的实现程序，并在计算机上测试测试结果与预期结果完全一样，即得到了连结个城市的最小生成树程序运行后，得到图的最小生成树见图其总权值为 1670，为连接个城市的最小权值图 最小生成树五、结语对现代城域网络架设问题进行了建模分析，基于模糊最小生成树理论对网络初始模型实施优化处理，在现实界限不分明的情况下，以投资建设费用最省为目标，获得了个城市间网络架设的

14、最佳方案，并使用语言编写了算法实现程序，得到正确的运行结果通过分析认为，在这几个城市之间的网络架设总费用最小应为 16.7 万元，其具体连接方法如图所示正如前面所提到的，对于网络架设中每公里建设费用的取值有种情况，而在文章中只详细讨论了其中种，即以 10000 元作为最大值如以 10000 元作为最小值来分析这个问题，则可以得到另一个结果，设为 而网络建设总费用的值域应为 16.7， 所以，今后的工作就是详细分析另种情况，以获得更加准确的取值参考文献：刘健，杨文宇，余健明，等一种基于改进最小生成树算法的配电网架优化规划 中国电机工程学报，（10）：渠西陈最小生成树与构造造价最低通迅网J 宿州教育学院学报，（）： 严葱敏数据结构 北京；清华大学出版社，陈小娟最小生成树问题J 福建电脑，（）：李 雷隶属函数模糊集及其应用（）隶属函数模糊集基本概念与性质