基于数学模型的网络优化方法研究
- 格式:doc
- 大小:218.50 KB
- 文档页数:6
数学模型方法及应用的论文数学模型是指用数学的方法描述和解决实际问题的一种工具。
它通过建立数学关系和方程式来分析问题,从而得出解决问题的方法或结果。
数学模型方法广泛应用于各个领域,比如物理、工程、经济、生物学等。
以下将介绍几篇关于数学模型方法及应用的论文。
1. "数学模型在交通网络优化中的应用":该论文探讨了交通网络中的优化问题,通过建立数学模型和使用最优化方法,解决了交通拥堵、路线选择、交叉口信号灯配时等问题。
2. "基于数学模型的疾病传播预测与控制":该论文研究了疾病传播的模型,通过建立传染病的流行病学模型,预测了疫情的扩展趋势,并提出了控制和治疗的策略,对公共卫生和疾病防控具有重要意义。
3. "数学模型在供应链管理中的应用":该论文讨论了供应链管理中的一些重要问题,如库存管理、生产计划、物流规划等。
通过建立数学模型和使用运筹学方法,优化了供应链的效率和成本,提高了企业的竞争力。
4. "金融风险模型及其应用研究":该论文研究了金融领域的风险模型,通过建立数学模型和使用统计方法,对金融市场的波动性和风险进行了分析和预测,为投资者和金融机构提供了决策依据。
5. "数学模型在环境保护中的应用":该论文探讨了环境保护领域中的一些重要问题,如水资源管理、气候变化建模、环境污染物传输等。
通过建立数学模型和使用数值模拟方法,评估和预测了环境的影响和风险,为环境决策和政策制定提供了科学依据。
以上是一些关于数学模型方法及应用的论文的简要介绍。
数学模型的应用范围广泛,可以有助于解决各个领域的实际问题,提高效率和效果。
通过不断改进和创新数学模型方法,可以进一步拓展其应用领域,为社会发展和进步做出更大的贡献。
基于遗传算法的人工神经网络模型构建与优化研究人工神经网络(Artificial Neural Network,ANN)是一种模仿生物神经网络结构和功能的计算模型,通过模拟神经元之间的连接和信号传递,能够实现机器学习和模式识别任务。
而遗传算法(Genetic Algorithm,GA)是一种基于自然选择和遗传机制的优化算法,通过模拟生物进化过程来寻找最优解。
本文将探讨基于遗传算法的人工神经网络模型的构建与优化研究。
首先,构建人工神经网络模型是研究的首要任务。
人工神经网络由多个神经元和这些神经元之间的连接组成。
每个神经元接收来自其他神经元的输入,并通过激活函数对输入信号进行加权计算,最终输出结果。
遗传算法可以应用于优化神经元的连接权重和调整激活函数的参数,以获得更好的网络性能。
在构建人工神经网络模型时,首先需要确定网络的拓扑结构,包括输入层、隐藏层和输出层的神经元数量,以及它们之间的连接方式。
遗传算法可以通过进化过程搜索最佳的拓扑结构,以提高神经网络的性能。
遗传算法通过定义适应度函数来衡量每个个体的适应度,适应度高的个体将更有可能被选中下一代进化。
通过遗传算法的迭代过程,我们可以找到最佳的拓扑结构。
其次,优化神经元的连接权重是构建人工神经网络模型的关键一步。
连接权重决定了不同神经元之间的信号传递强度。
遗传算法可以通过进化过程调整连接权重,以找到最佳的权重组合。
在遗传算法的优化过程中,通过交叉和变异等操作,通过上一代个体中的优秀基因来生成新的个体,逐步优化连接权重,使神经网络的性能得到提高。
此外,还可以使用遗传算法来优化激活函数的参数。
激活函数决定了神经元输出的非线性特性,常用的激活函数包括Sigmoid、ReLU、Tanh等。
通过调整激活函数的参数,我们可以改变神经元的响应特性,从而使网络更好地拟合训练数据。
遗传算法可以在多个激活函数和参数组合中搜索最佳的选择,以提高神经网络的性能。
此外,在进行人工神经网络的训练和优化时,还可以使用遗传算法来选择最优的训练样本和参数初始化方法。
计算机网络中的网络拓扑优化方法研究网络拓扑优化是计算机网络中重要的研究领域,它旨在通过改进网络拓扑结构,提高网络性能和可靠性。
本文将介绍网络拓扑优化的基本概念、常见方法和研究进展。
一、网络拓扑优化的基本概念网络拓扑优化指的是通过调整网络中的节点、链路或其它网络组件的连接方式,从而改进网络的性能和可靠性。
网络拓扑包括逻辑拓扑和物理拓扑两个方面。
逻辑拓扑表示节点之间的连接关系,而物理拓扑表示节点之间的物理连接。
二、网络拓扑优化的方法1. 基于图论的方法:图论是网络拓扑优化的基础理论。
通过分析网络中的节点和链路之间的关系,可以建立拓扑图,进而进行拓扑优化。
其中一种常见的方法是最小生成树算法,它通过选择最短路径来构建最优拓扑结构。
2. 基于模型的方法:网络拓扑优化可以使用数学模型来描述和求解。
常用的模型包括整数规划、线性规划和非线性规划等。
这些模型可以通过设置目标函数和约束条件,从而得到最优的拓扑结构。
3. 基于启发式算法的方法:启发式算法是一种从经验中得到解决方案的方法。
常见的启发式算法包括遗传算法、蚁群算法和粒子群优化算法等。
这些算法利用搜索和优化技术,通过迭代过程来逐渐逼近最优解。
三、网络拓扑优化的研究进展1. 链路权重分配:链路权重分配是网络拓扑优化的重要内容之一。
通过合理分配链路的权重,可以平衡网络中的传输负载,提高网络的吞吐量和响应速度。
2. 动态拓扑优化:动态拓扑优化是指根据网络的实际情况,动态调整网络的拓扑结构。
通过监测网络中节点和链路的状态信息,可以及时进行拓扑优化,以应对网络故障和变化。
3. 虚拟网络拓扑优化:虚拟网络拓扑是指在物理网络上构建的一种抽象表示,它可以满足特定的性能和可靠性要求。
虚拟网络拓扑优化旨在找到最优的映射方式,将虚拟网络映射到物理网络上,以实现资源的高效利用。
四、网络拓扑优化的应用领域1. 数据中心网络:数据中心网络是指大规模服务器集群之间互连的网络。
通过优化数据中心网络的拓扑结构,可以提高数据中心的吞吐量、延迟和可扩展性。
复杂网络优化模型及算法研究复杂网络是一种由大量相互连接的节点组成的网络结构,具有高度复杂性和非线性特征。
而网络优化旨在设计出最佳的网络结构,以提高网络的性能和效率。
因此,复杂网络的优化模型和算法成为了研究的焦点。
一、复杂网络优化模型复杂网络优化模型旨在解决网络结构设计及网络性能改进的问题。
尽管网络优化问题的具体形式各不相同,但优化模型通常包括以下几个关键要素。
1. 目标函数:优化模型的目标函数是衡量网络性能和效率的指标。
常见的目标函数包括最小化网络总成本、最大化网络吞吐量、最小化网络延迟等。
2. 约束条件:网络设计往往需要满足一定的约束条件,以保证网络的可行性和稳定性。
例如,网络设计需要满足带宽要求、节点度数限制、路径长度限制等。
3. 决策变量:决策变量是网络设计中的可调整参数。
它们用于表示节点之间的连接方式、带宽分配、路由选择等网络结构和性能相关的决策。
二、复杂网络优化算法复杂网络优化算法是用于求解复杂网络优化模型的数学和计算方法。
以下是几种常见的优化算法。
1. 遗传算法:遗传算法是一种基于生物进化原理的优化算法。
它通过模拟遗传操作,通过不断迭代优化个体的适应度,最终得到最优解。
遗传算法可以应用于复杂网络设计、路由优化等问题。
2. 粒子群优化算法:粒子群优化算法是一种基于群体智能的优化算法。
它通过模拟鸟群或鱼群的行为,通过不断搜索空间中的潜在解,最终收敛到全局最优解。
粒子群优化算法在复杂网络设计中具有广泛的应用。
3. 蚁群算法:蚁群算法是一种基于蚂蚁寻找食物路径的启发式优化算法。
它通过模拟蚂蚁在搜索过程中的信息交流和信息素释放行为,找到最短路径或最优解。
蚁群算法适用于复杂网络路由优化等问题。
4. 模拟退火算法:模拟退火算法是一种基于统计物理学思想的全局优化算法。
它通过模拟固体物体在高温下退火的过程,以跳出局部最优解并收敛到全局最优解。
模拟退火算法可用于复杂网络的布局和结构优化。
三、应用领域复杂网络优化模型和算法具有广泛的应用领域,包括但不限于以下几个方面。
数学建模中的优化算法应用实例数学建模是一种有效的解决实际问题的方法,而优化算法则是数学建模中不可或缺的工具之一。
优化算法能够寻找最优解,最大化或最小化某个目标函数,有着广泛的应用领域。
本文将介绍数学建模中的几个优化算法应用实例,以展示其在实际问题中的作用和价值。
一、车辆路径规划优化在实际的物流配送领域中,如何合理地规划车辆路径,使得总运输成本最小、配送效率最高,是一个关键问题。
优化算法在车辆路径规划中起到了至关重要的作用。
通过建立数学模型,基于某个目标函数(如最小化总运输成本),可以采用遗传算法、模拟退火算法等优化算法,快速找到最优解,从而提高物流配送的效率和效益。
二、资源分配优化在资源分配问题中,常常需要考虑到各种限制条件,如最大化利润、最小化生产成本等。
优化算法能够帮助决策者在有限的资源下做出最优的分配决策。
例如,对于生产调度问题,可以利用线性规划等优化算法,将生产计划与订单需求进行匹配,使得生产成本最小化、交货期最短化。
三、供应链优化供应链管理中的优化问题也是实际应用中的重点关注点之一。
通过数学建模和优化算法,可以实现供应链中物流、库存、订单等多个环节的优化。
例如,在供应链网络设计中,可以使用整数规划算法来寻找最优仓储和配送中心的位置,从而降低总运输成本;在需求预测和库存管理中,可以利用模拟退火算法等优化算法,提高供应链的响应速度和利润率。
四、机器学习模型参数优化在机器学习领域,模型参数的选择对模型的性能和准确性有着重要的影响。
通过建立数学模型,可以将模型参数优化问题转化为参数寻优问题,进而采用优化算法求得最优参数。
例如,在神经网络的训练过程中,可以利用遗传算法、粒子群优化算法等进行参数调整,提高模型的预测准确性和泛化能力。
五、能源系统优化能源系统的优化是实现可持续发展的重要方向之一。
通过优化算法,可以针对能源系统进行容量规划、发电机组简化和能源分配等问题的优化。
例如,在微电网系统优化中,可以利用整数规划等算法,实现可再生能源与传统能源的协同供电,最大化清洁能源的利用率。
基于遗传算法的人工神经网络优化方法研究人工神经网络(Artificial Neural Network,ANN)是一类模拟自然神经网络结构和功能的数学模型,广泛应用于图像识别、语音识别、自然语言处理等领域。
然而,ANN中的参数众多,优化难度大,因此需要一种高效的优化方法。
遗传算法(Genetic Algorithm,GA)作为一种优化算法,能够有效地在搜索空间中寻找最优解,因此,研究基于遗传算法的ANN优化方法具有理论意义和实际应用价值。
一、ANN优化技术的研究现状当前,ANN优化技术主要有遗传算法、粒子群优化(Particle Swarm Optimization,PSO)、模拟退火(Simulated Annealing,SA)等算法。
其中,遗传算法受到了广泛的关注和研究。
遗传算法是一种模拟生物进化过程的搜索算法,通过模拟自然界的生物进化过程,不断筛选优化解,最终在搜索空间中找到最优解。
遗传算法具有以下几个优点:(1)全局搜索能力强;(2)可以处理多个目标问题;(3)适应度函数的选择范围广泛,能够处理非线性非凸问题;(4)算法简单,易于实现;(5)可以与其他优化算法相结合,提升优化效果。
二、基于遗传算法的ANN优化方法基于遗传算法的ANN优化方法一般分为以下几个步骤:①编码;②初始化种群;③计算适应度;④选择操作;⑤交叉操作;⑥变异操作;⑦产生新种群。
①编码编码是将ANN参数向量转化为遗传算法遗传信息的过程。
常用的编码方式有二进制编码、实值编码等。
在实值编码中,ANN每个参数用一个实数表示,遗传算法的每个染色体也用一个实值向量表示。
②初始化种群初始化种群需要随机产生一组遗传信息,通常使用均匀分布或高斯分布来生成初始种群。
这些遗传信息被称为个体或染色体,它们的集合被称为种群。
③计算适应度计算适应度是将ANN参数向量转化为遗传算法的适应度函数的过程。
通常,适应度函数定义在ANN误差函数的基础上,例如均方误差(Mean Square Error,MSE)。
基于深度学习的复杂网络分析与优化研究复杂网络分析与优化在当今信息时代具有重要的意义和价值,然而,由于网络结构的复杂性和海量数据的存在,传统的分析方法效率低下,难以满足实际应用的需求。
近年来,基于深度学习的方法成为网络分析与优化的研究热点。
本文将针对基于深度学习的复杂网络分析与优化进行综述和深入讨论。
首先,本文将介绍深度学习在复杂网络分析方面的应用。
深度学习可以从底层的网络结构特征中学习到高层次的数据表征,能够发现网络中隐藏的规律和关系。
例如,图卷积网络(Graph Convolutional Network,简称GCN)是深度学习在图领域的经典模型,通过卷积操作在图上学习特征表示,在社交网络分析、生物网络分析等领域取得了显著的效果。
此外,深度学习还可以用于复杂网络的异常检测、社区发现、链接预测等任务,提高了网络分析的准确性和效率。
接着,本文将探讨深度学习在复杂网络优化方面的应用。
复杂网络优化是指在网络中寻找最优解或基于某种目标进行优化。
深度学习可以通过学习网络的表示和参数化的方法,进行复杂网络的优化。
例如,深度强化学习(Deep Reinforcement Learning,简称DRL)可以应用于复杂网络的动态路由优化,通过训练智能体在网络中自主学习网络结构和参数,并根据网络状态采取动态决策,优化网络的性能和效率。
此外,深度学习还可以用于复杂网络的拓扑结构设计、资源分配与调度等方面,提高网络的可靠性和灵活性。
在研究方法方面,本文将重点介绍基于深度学习的复杂网络分析与优化的常见算法和模型。
例如,除了前面提到的GCN和DRL,还有基于卷积神经网络(Convolutional Neural Network,简称CNN)的网络表示学习方法,基于自编码器(Autoencoder)的异常检测方法,基于生成对抗网络(Generative Adversarial Network,简称GAN)的社区发现方法等。
这些模型和算法通过对网络数据的特征学习和生成,提高了网络分析和优化的性能。
基于随机几何与排队论的无线网络性能研究基于随机几何与排队论的无线网络性能研究随着无线网络的飞速发展,人们对网络性能的要求也越来越高。
为了提高网络的性能,研究人员们开始利用随机几何和排队论等理论进行无线网络性能研究,这些研究对于无线网络的优化与改进具有重要意义。
随机几何是研究空间中随机分布的点与物体之间关系的数学学科,对于无线网络而言,可以利用随机几何来建模网络中用户的空间分布。
无线网络中的用户可以看作是在空间中的随机分布的点,而基站则可以看作是放置在空间上的固定点。
研究人员通过利用随机几何理论,可以对无线网络中用户之间的距离、用户到基站的距离等进行建模,从而对网络性能进行分析与优化。
排队论是研究顾客到达和服务之间的关系的数学学科,对于无线网络而言,可以利用排队论来研究网络中用户的排队现象。
在无线网络中,用户需要不断地向基站发送数据请求,而基站需要对这些请求进行处理。
如果基站处理速度跟不上用户的数据请求速度,就会出现排队现象,用户需要等待其他用户的数据请求处理完毕才能得到回应。
利用排队论,研究人员可以对无线网络中用户的排队时间、排队长度等进行建模,从而对网络性能进行分析与优化。
通过结合随机几何和排队论等理论,可以对无线网络的性能进行研究和优化。
具体研究内容可围绕以下几个方面展开:首先,可以基于随机几何理论进行网络拓扑建模。
通过建立网络中用户与基站之间的空间距离模型,可以分析和优化用户之间的信号干扰,提高网络的容量和覆盖范围。
其次,可以基于排队论进行网络流量建模。
通过分析用户的数据请求和基站的处理速度,可以建立网络中的排队模型,从而分析和优化网络的延迟和吞吐量,提高网络的性能。
此外,还可以利用随机几何和排队论等理论进行无线资源的优化分配。
通过研究用户在网络中的分布情况和数据请求情况,可以合理地分配无线资源,提高网络的利用率和性能。
最后,可以通过仿真实验验证理论模型的正确性和有效性。
利用计算机仿真技术,可以模拟真实的无线网络环境,并进行各种性能测试和优化实验,以验证随机几何和排队论等理论的可行性和实用性。
数学建模组合优化模型数学建模是一种将实际问题转化为数学模型,并通过数学方法进行求解的技术。
在实际应用中,很多问题都可以使用组合优化模型来描述和解决。
组合优化模型主要研究如何在给定的约束条件下,找到最优的组合方式。
组合优化模型最早出现在20世纪50年代,当时主要应用于军事领域。
随着计算机技术的发展和应用范围的扩大,组合优化模型的研究逐渐扩展到了经济、交通、电力、通信等各个领域。
组合优化模型的基本思想是将问题抽象为一个图或者网络,通过定义合适的目标函数和约束条件,寻找使得目标函数最优的节点或者路径。
在组合优化模型中,最常见的问题包括最短路径问题、旅行商问题、背包问题、任务调度问题等。
在组合优化模型中,最常见的方法是枚举法、贪心法、动态规划法和分支定界法等。
枚举法是最简单的方法,它逐个考虑每种组合情况,然后计算出目标函数的值,并找出最优解。
贪心法是一种局部最优的方法,它每次都选择使得目标函数最优的节点或者路径,然后不断迭代直到找到最优解。
动态规划法是一种通过将问题划分成若干个子问题,并通过求解子问题的最优解得到原问题的最优解的方法。
分支定界法是一种通过将问题划分成若干个子问题,并剪枝掉不可能成为最优解的子问题,从而找到最优解的方法。
为了解决组合优化模型,需要建立合适的数学模型,并采用适当的求解方法。
建立数学模型的过程主要包括以下几步:明确问题目标、确定决策变量、建立目标函数、建立约束条件。
在建立模型的过程中,需要根据实际问题的特点选择合适的模型和方法。
总之,组合优化模型是一种将实际问题抽象为数学模型,并通过数学方法进行求解的技术。
组合优化模型已经广泛应用于各个领域,并取得了很多重要的成果。
未来,随着计算机技术的进一步发展和应用需求的不断增加,组合优化模型将会发挥越来越重要的作用。
基于数学模型的网络优化方法研究赵鹏 通信一团技术室摘 要 为了提高网络链路的利用率,解决网络传输中的最大流问题,该文利用建立数学模型的方法来求解网络的传输路径,研究了基于路径的网络优化方法。
该方法能够极大地提高网络的链路利用率,从而降低网络的拥塞,使得网络的性能得到较大改善。
关键词 网络优化 最大流 数学模型1 引言随着网络技术的进步和人们对多媒体综合业务需求,传统的数据网络逐渐转向多媒体网络,在这过程中,除了相关服务以外,我们还面临许多极具战性的网络设计和优化问题。
网络优化的目标是提高或保持网络质量,而网络质量是各种因素相互作用的结果,随着网络优化工作的深入开展和优化技术的提高,优化的范围也在不断扩大。
在计算机网络优化设计中,各条链路的容量分配和各节点间的路由选择是两个重要问题。
在给定网络拓扑结构和各节点间传输流量的条件下,如何确定各条链路的容量大小和选择各节点间的最佳路由,使整个网络成本费用最低并能满足规定的性能指标呢?许多网络优化的文献,研究针对CDMA 网络、GPRS 网络、GSM 网络、PHS 网络等具体网络在投入运行后,对网络进行参数采集、数据分析,找出影响网络质量的原因,通过技术手段或参数调整使网络达到最佳运行状态,涉及到交换网络技术、无线参数、小区参数配置、信令和设备技术等方面。
本文针对目前许多网络传输链路和网络设备没有得到充分利用,从而影响网络性能的问题,利用网络优化方法从理论上进行分析,研究了用于提高网络链路利用率的基于路径的网络优化方法,该方法能够充分地利用网络链路进行流量传输,从而改善网络的整体性能。
2 网络优化理论很多情况下可以将网络优化问题转化成数学问题进行研究和分析。
从根本上讲,优化问题包含三个基本要素:决策变量集合或向量:nR x ∈(本文,x 代表在一条或多条路径上的流量) 目标函数R R x f n→:)(一组约束条件g(x)和h(x),用来定义x 的范围。
解决优化问题实际上就是找出一个点x*,使得f(x)最大化或最小化。
典型的网络优化问题包含找出一组路由和该路由上的流量值以便达到最大或最小化目标函数的目的。
目标函数可以代表最大链路利用率、平均延迟或其他指标。
基于路径的问题首先要计算出网络流可能流经的路径,要最大限度的利用网络链路,同时路径上的流量不能超过链路容量。
对于基于路径的网络优化问题可以简单表示成: max f(x)s.t.∑∈=Pp pb xA j i u xPj i ij p∈∀≤∑∈),( ),(0≥xx p 为路径p 上的数据流,b 为要传输的流量,u ij 为弧(i,j )上的容量,A 代表网络中弧的集合,P 为源点——目的点之间路径的集合。
3 基于数学模型的网络优化方法3.1 最大流问题的研究在现实网络中,如图1所示的网络结构是很常见的。
当从源点向目的点传输流量时,如何充分利用整个网络资源,达到要求的服务质量是我们要考虑的事情。
传统的IP 网络是通过路由算法找到一条按某种算法达到的最优路径,如,RIP ,OSPF 等。
图1 进行研究的网络拓扑结构图中每条弧上的数字代表了相应链路的可用链路容量,单位为Mbps 。
从路由器1到路由器有多条路径:path1:1→2→3→6;path2:1→2→5→6;path3:1→4→5→6; path4:1→4→3→6;path5:1→2→3→5→6;⋅⋅⋅⋅⋅⋅我们要研究的是在多条路径的条件下,通过分析选取合适路径,使得所有源点与目的点之间的流量达到最大。
首先,建立网络的数学模型。
令g(V ,A)代表网络,V 代表网络中的节点集合,A 代表链路集合,s k 代表第k 条路径的源点,t k 代表第k 条路径的目的点,f k 代表第k 条路径的传输流量,K 为所有路径的编号集合,x ij 为弧(i ,j )上的流量,u ij 为弧(i ,j )的容量上界。
运用关联矩阵b Nx =进行分析,其中,向量b k = {b i k },⎪⎩⎪⎨⎧==+=其他如果果 0t i -s i 如 k k k k ki f f b那么,对于我们要研究的最大流问题可以用数学模型描述为:∑∈K k k f max (1)s.t. K k b Nx kk∈∀= (2)∑∈∈∀≤Kk ij k ijA j i u x),( (3)A j i K k x k ij ∈∀∈∀≥),( , 0 (4)该情况下的最大流问题一般来讲是一种大规模线性规划问题,可以直接采用线性规划、整数规划等方法求解。
图1中假定网络有两个源点和目的点,第一条源点——目的点从路由器1到路由器6,第二条源点——目的点从路由器2到路由器5。
网络的关联矩阵为: N= ⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡----------100100000011001100000110001010001110010000000111010000000011相应的两个源点和目的点的b 为T f f b ]- 0 0 0 0 [111=,T f f b ]0 - 0 0 0[222=,其中,T 表示转置,0,21≥f f 。
求解公式(1)、(2)、(3)、(4)所确定的线性规划。
则Nx = b 可表示为:⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡-=⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡----------ii i i ii i ii i i if f x x x x x x x x x x 000010010000001100110000011000101000111001000000011101000000001156454336352524231412 其中,i=1,2。
对于第一条源点——目的点的1ij x 记为x ij ,将第二条源点——目的点的2ij x 记为y ij 。
经过简化,得到下面的线性规划:)max (21f f +s.t. x 12+x 14=f 1;x 23+x 24+x 25-x 12=0;1 2 3 4 5 6 x 12 x 14 x 23 x 24 x 25 x 35 x 36 x 43 x 45 x 56x 35+x 36-x 23-x 43=0; -x 14-x 24+x 43+x 45=0; -x 45-x 25-x 35+x 56=0; -x 36-x 56=-f 1; y 12+y 14=0;y 23+y 24+y 25-y 12=f 2; y 35+y 36-y 23-y 43=0; -y 14-y 24+y 43+y 45=0; -y 45-y 25-y 35+y 56=-f 2; -y 36-y 56=0; x 12+y 12<=2; x 14+y 14<=7; x 23+y 23<=4; x 24+y 24<=4; x 25+y 25<=3; x 35+y 35<=1; x 36+y 36<=2; x 43+y 43<=1; x 45+y 45<=5; x 56+y 56<=4; x ij ,y ij >=0。
得到:Mbps f f 11)max (21=+;f 1=3Mbps ;f 2=8Mbps ;x 12=2Mbps ;x 14=1Mbps ;x 23=2Mbps ;x 36=2Mbps ;x 45=1Mbps ;x 56=1Mbps ; y 23=1Mbps ;y 24=4Mbps ;y 25=3Mbps ;y 35=1Mbps ;y 45=4Mbps ;其余为0。
从上面的求解结果可以看出,对于图1中的网络: 从路由器1到路由器6的路径为:x 12+x 23+x 36即,1→2→3→6,带宽为2Mbps ; x 14+x 45+x 56即,1→4→5→6,带宽为1Mbps 。
从路由器2到路由器5的路径为: y 23+y 35即,2→3→5,带宽为1Mbps ; y 24+y 45即,2→4→5,带宽为4Mbps ; y 25即,2→5,带宽为3Mbps 。
由此可以看出,从路由器1到路由器6链路带宽最高可达3Mbps ,从路由器2到路由器5链路带宽最高可达8Mbps 。
在此基础上采用MPLS 的ER-LSP 技术可以将流量安排到各条计算出的路径上。
图2 最大流问题链路利用的结果分析如果利用求解网络中两点间最短路径的Dijkstra 算法,求解最短路径优先协议下,在相同网络中的两个同样的传输,效果会怎样呢?同样先对问题进行数学描述,然后求解计算网络的最短路径,在此不再进行详细说明。
通过计算得到:从路由器1到路由器6的最短路径为1→4→5→6,带宽为4Mbps ;从路由器2到路由器5的最短路径为2→5,带宽为3Mbps 。
利用Dijkstra 算法计算得到的两条路径的带宽总共为7Mbps ,而利用上述算法计算得到的路径带宽总共为11Mbps ,明显由于7Mbps 。
这是因为OSPF 协议仅仅使用了一条最优路径,而上述算法中利用MPLS 协议可以充分利用网络的所有可能的路径,从而使得网络的链路资源得到最大的利用率。
图3为两种算法的链路利用率对比;图中蓝色的实线代表本文算法求出的链路带宽,粉红色的虚线为Dijkstra 算法求得的链路带宽,绿色的波浪线为链路可用带宽;x 轴依次代表x12,x14,x23,x24,x25,x35,x36,x43,x45,x56;y 轴代表带宽(单位:Mbps )。
由图中可以看出,使用本文所用的算法能够使各条链路得到充分利用,极大的提高了链路利用率,从而能够减小网络的拥塞现象,改善网络的性能。
而Dijkstra 算法使得部分链路未得到充分利用。
1234567812345678910图3 两种算法链路利用率对比在目前网络信息高度膨胀,网络传输过程中出现大量的拥塞情况而言,本文的算法能够保证网络的链路得到充分利用,从而提高网络的整体性能,使网络得到优化。
然而该算法也存在一个明显的弱点,即将数据流过于分散到各条链路上。
由于分流就不可避免地造成分组的失序,这对音频和视频流的传输是不合适的。
对于音频和视频流的传输应尽可能的减少分流,在传输某一特定流时应该充分利用所使用的链路。
3.2 流量集中传输对源点——目的点之间的路径进行选择,从而实现流量集中传输。
方法为:(1)将用上述算法求出的路径按照带宽从大到小排列为p 1,p 2,... ,p n (假定共有n 条路径);(2)判断如果p i带宽大于流量时,路径p i能够满足对流量的传输要求,则选择p i;(3)如果p i的链路带宽小于流量时,选择该路径作为流量传输的路径之一;(4)再对路径p i+1进行判断,...,直到能够满足流量的传输需求。