基于模糊最小生成树的城域通信网络优化模型

基于模糊最小生成树的城域通信网络优化模型

1网络拓扑结构的优化近年来，随着计算机网络应用的蓬勃发展，新的网络产品和网络技术也得到了应用，使计算机网络的规模可以扩大。在现实生活中，有许多问题类似于建筑工地之间的电话线、管道和建筑物之间的道路。通常，在一些早期的发展阶段，由于技术和财力的限制，人们总是从降低成本的角度设计网络，并尝试连接不同的城市。这是最短的长度。某省的7个城市需要架设通信网络系统,为连接这7个城市,每2个城市之间的距离如表1所示.考虑地理环境的影响,综合考虑各城市之间的距离和每公里修建网络的费用,各城市之间修建网络每公里的费用可用与10000元之间的比较来估计(表2).试问如何架设通信网络,使总费用最小?对于此类网络架设问题,通常采用星型、环型或总线型网络拓扑结构,能够较好地解决网络建设过程中的连接和通信问题.但仅仅是基于网络拓扑结构的网络构架,往往达不到建设费用最小的要求.图与网络是运筹学中的一个经典和重要的分支,所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域.因此,在网络拓扑结构的优化中引入图论的方法,以获得实际应用中较理想的网络建设方案.同时,以往对于此类问题的处理,通常都是采用精确数学的方法去解决.然而,人们的思维中有许多没有明确外延的概念,即模糊概念.语言上有许多模糊概念的词,例如以人的年龄为论域,那么“年青”、“中年”、“老年”都没有明确的外延.在上述问题中所给出的“相当接近”、“可认为是”、“差不多是”等词都是模糊概念,无法用精确数学的方法去解决.所以,又引入了模糊数学,模糊集合是其基本概念之一.2相关概念和符号的表达2.1图论与线性规划图、边、权、无向图、链、连通图、树、生成树、最小生成树的概念及符号表示见文献.图论方法已经成为数学模型中重要的数学方法,许多数学问题如果能够归结为图论问题,往往能够迎刃而解,在计算机理论以及数学的其他分支中有广泛的应用.在管理科学中,基于图论的统筹方法也得到广泛的应用.许多图论问题可以化为线性规划问题,不过图论中的许多特殊算法比利用一般线性规划方法有效得多.2.2模糊数学的基本方法将被讨论的全体对象或范围叫做论域,常用U,V,E,…,X,Y,…大写字母表示.将论域中的每个对象称为元素,用相应的小写字母u,v,e,…,x,y,…表示.隶属函数:用解析形式描术元素属于集合的程度.设A是论域X上的集合,记为UA(x)={1当x∈A,0当x∉A.UA(x)={1当x∈A,0当x∉A.集合A的特征函数,也称为隶属函数.模糊集:论域X上的模糊集合A¯¯¯A¯由隶属函数U(x)来表征,其中U(x)在实轴的闭区间[0,1]上取值,U(x)的值反映了X中的元素x对于A¯¯¯A¯的隶属程度.模糊数学是研究现实中许多界限不分明问题的一种数学工具,它的主要概念包括模糊集合、隶属函数等.模糊集合完全由隶属函数所刻划.接下来用图论法和模糊集合的方法来解决网络架设问题的数学模型.3模糊集合的确定按照图论法的规则建立通信网络的图论模型,即以7个相邻的城市为图的顶点,两顶点之间的网络线路为图的边,其定义如下:G={V,E},V={R1,R2,R3,R4,R5,R6,R7},E={(R1,R2),(R1,R3),(R1,R4),(R1,R5),(R1,R6),(R1,R7),(R2,R3),(R2,R4),(R2,R5),(R2,R6),(R2,R7),(R3,R4),(R3,R5),(R3,R6),(R3,R7),(R4,R5),(R4,R6),(R4,R7),(R5,R6),(R5,R7),(R6,R7)}.由该定义所构成的无向连通图如图1所示.每条边的权w为某2个顶点之间网络建设的费用,如联结顶点R1和R2的边上的权值记为w(R1,R2).因此,一个无向连通图可以定义为顶点、边、权值构成的集合,即G={V,E,W}.通过以上定义,可将城市之间的通信网络架设问题转化为以建设费用最省为优化目标,求解最优通信网络的问题.在建设费用函数未知的情况下,可先将建设网络的费用看作城市之间距离的线性函数,并考虑其他因素(地理、环境)的影响,先求解城域网络的初始布局,即将这些顶点用边联结起来,用两顶点间的直线距离与每公里网络建设费用的乘积作为边的权,使总的权值最小.可用图论中的求解最小生成树的方法求解.所以,问题的关键在于如何确定各条边上的权值.在前面定义过,权值等于城市之间距离与每公里网络建设费用的乘积.各城市之间的距离是以公里为单位的确定值,可以定义L(Ri,Rj)为两顶点Ri和Rj之间的距离,在表1中已列出所有具体值.由于考虑到受地理、环境因素的影响,相同距离、不同地段的建设费用存在差别,而表2中只列出了各地段每公里建设费用与10000元之间的比较关系,因此,引入模糊集合来表示这种界限不分明的情况.前面提到过,模糊集合完全由隶属函数所刻划,隶属函数及其确定是模糊数学中最重要、最基本的量.在实际应用中,它的确定方法主要有模糊统计法、德尔菲法、对比排序法、综合加权法等等,当然也可以直接使用常见的规则的隶属度函数,但必须知道变量的确定量度和意义.按照表2所列出的各种比较关系,根据语义规则,可以得到一个程度集合(完全是、可认为是、差不多是、非常接近、十分接近、相当接近、很接近、比较接近、大致接近).根据相对于10000元的各种比较关系,分3种情况讨论每公里网络建设的实际费用:(1)10000元是最大值;(2)10000元是最小值;(3)10000元是一个中间值.由于问题要求求解最小费用,因此可以暂且只考虑以10000元为每公里网络建设费用的最大值,这样使得总花费最小.于是给定程度集合的一个加权因子P=[1,0.95,0.9,0.85,0.8,0.75,0.7,0.65,0.6],这些因子与10000的乘积,可用于计算每公里网络建设费用的近似值.在表3中给出程度集合的符号表示以及按语义规则所分配的值.通过上述定义,可以进一步描述图1中联接每对顶点的边的权值w(vi,vj)=L(vi,vj)·Cn·M,(1)其中M为常数10000.为计算每条边的权值,参照表1至表3得到2个矩阵,其对应位置上分别列出L(vi,vj)和Cn的值:⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜41011581084326965510107955⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟‚⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜0.60.950.7510.650.90.850.80.9510.70.90.850.80.60.9510.650.70.850.65⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟(41058610118491010367259555)‚(0.60.9510.850.70.950.750.650.80.910.90.950.850.6510.80.70.60.850.65)表4是根据(1)式计算得到的任意2个城市之间网络建设的费用.图论中求无向连通图G={V,E,W}的最小生成树法.最小生成树法将城域网络看作无向连通图,求该图的最小生成树,常用经典算法有prim算法、Kruskal算法.下面将介绍以Kruskal算法解决上述问题的步骤.4执行文件和运行结果4.1赋权图g中的边的排列每次添加权尽量小的边,使新的图无圈,直到生成1棵树为止,便得最小生成树.算法步骤如下:(ⅰ)将赋权图G中的边按权的非减次序排列;(ⅱ)按(ⅰ)排列的次序检查G中的每一条边,如果这条边与已得到的边不产生圈,就取这一条边为解的一部分;(ⅲ)若已取到n-1条边,算法终止,此时以V为顶点集,以取到的n-1条边为边集的图即为最小生成树.4.2s1.4.3t4.3赋权的连通图G={V,E,W}中m=|E|,n=|V|.S1对E中各边的权排序,设w1≤w2≤…≤wm,wi=w(ei).S2初始化:w←0,T←∅,k←1,t←0.S3若t=n-1则转S6,否则转S4.S4若T∪{ek}有圈则k←k+1转S4,否则转S5.S5T←T∪{ek},w←w+wk,t←t+1,k←k+1,转S3.S6输出T及w,结束.其中T为最小树,w为T的权.具体流程图见图2.4.3计算机上测试按照上述思想,用C语言编写了Kruskal算法的实现程序,并在计算机上测试.测试结果与预期结果完全一样,即得到了连结7个城市的最小生成树.程序运行后,得到图1的最小生成树见图3.其总权值为1670,为连接7个城市的最小权值.5算法实现程序模拟对现代城域网络架设问题进行了建模分析,基于模糊最小生成树理论对网络初始模型实施优化处理,在现实界限不分明的情况下,以投资建设费用最省为目标,获得了7个城市间网络架设的最佳方案,并使用C语言编写了算法实现程序,得到正确的运行结果.通过分析认为,在