光网络流量工程优化算法研究

《光网络流量工程优化算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论文量度的流量控制越来越显出它的局限性。当前，流量工程技术的研究主要集中在对自治系统内部的各种业务流的管理与控制方面。通过对各种具有不同Q。S要求的业务流进行适当的路由选择、路由优化和采取多种高效的流量管理和控制手段来达到此目的。使各种业务流能够在系统内部均匀、合理地分布，从而显著地降低链路的拥塞概率，提高网络资源的利用率，实现网络工作性能最佳化的目标。基于约束的路由选择“。是流量工程中的核心技术，也是实现Q。，S业务的关键。它可以根据多个约束条件(既可以是QOS的约束条件，也可以是其

2、他策略性的约束条件)计算出所有的可行路径，并根据一定的优选策略从中选出一条最优的路径，以提高网络资源的利用率和网络负载的均衡，实现网络性能的优化。本文主要针对复杂的光网络进行流量工程的优化计算，按照光网络的特殊结构和子网保护规则计算出所有的可行路由集，以网络资源占有、网络负载均衡、保护资源占有、保护资源均衡四个目标为优化目标，以GA算法优化求取一条较优的路由。1．1．2流量工程模型从图论观点看，该工程是一个传输网络中的问题，传输网络中的问题又叫网络流问题(或流问题)。通信网络是一种传输网络，传送的是多业务。多

3、业务流问题就是多个业务的资源优化分配问题。多业务流问题是NP完全问题，在数学上还没有有效的解决方法。从数学观点看，这是一个多目标的优化问题。优化的具体目标包括：占用网络资源尽量少、网络负载均衡、占用保护资源尽量少、保护资源负载均衡等。一、多目标优化对于多目标优化“1问题，科学和工程领域最终归结为求解一个带有约束条件的函数优化问题。对于约束优化问题，已有的许多算法都基于梯度的概念，只适用于目标函数约束可微的情形，而且一般只能保证到局部最优解。由于遗传算法中国科学技术大学硕j．学位论文不要求目标函数约束是可微的，

4、同时，GA能以较大概率求得全局最优解，因此，它成为求解约束优化问题的一个强有力的工具。在GA被广泛应用之前，优化问题的解法主要有：(1)基于计算的方法通过求目标函数导数的零点或一系列迭代计算过程求最优解。对多峰问题，这类方法易陷入局部最优点附近，且要求目标函数有较好的连续性或可微性。(2)枚举法在有限的或被离散化的无限搜索空间中比较每一点的目标函数值，求出最优解。当搜索空间大时，计算量的迅速增加使这类算法失效。(3)随机算法这类算法主要有MonterCarlo法和模拟退火法。MonterCarlo法盲目性大；

5、模拟退火法在实际应用中较成功，但它的从一点到另一点的迭代过程使多峰问题较容易陷入局部最优解。对于一个优化算法，寻求最优点不是唯一目的，实际中经常遇到的优化问题更重要的目标是进步，即优化过程应该是一个不断改进的过程，对复杂系统的优化更是如此。与传统优化算法相比，GA具有如下特点：(1)搜索时，不直接使用变量本身，而使用它的编码；(2)搜索过程是从一组解迭代到另一组解，减少了陷入局部最优解的可能性；(3)它使用的是随机搜索过程而非确定性搜索过程：(4)对搜索空间没有任何特殊要求(如连通性，凸性等)，只需要计算目标

6、函数值，不需要目标函数是否连续、可微等辅助信息，因而它的适用范围更广。光网络流量工程优化计算的核心问题是路由分配全局优化，即根据输入的光网络拓扑、业务需求等信息，求出满足限制条件的业务路由，并且该解对应的综合指标最好(或接近最好)。工程欲采用GA算法”1并且合理的构造～个兼顾多个目标的适应度函数，实现上述要求。要优化的具体目标比较多，这些目标相互存在矛盾(矛盾是指某个目标的优化可能以另一些目标的劣化为代价)，要全局平衡各目标的矛盾，构造一个兼顾各个目标的适应度函数。±里型兰垫查查兰竺主兰垡堡兰——在计算中主要

7、考虑的是四个目标：网络资源的占用情况、网络负载均衡、保护资源的分配以及保护资源分配的均衡。希望网络资源被占用得越少越好、网络流量在各条链路上分配愈均衡愈好、网络保护资源分配和使用的尽量少、保护资源在起保护作用的链路上分配尽可能均衡。目标之间的矛盾主要是：网络资源的占用和均衡上，资源占用少的情况下使得负载均衡有所劣化；保护资源分配和使用的越少可能造成保护负载不均衡，使得保护负载过于集中反而不利于保护。光网络拓扑信息和网络业务信息的数据量也太大，路由的全局优化过程存在太多的变量和约束条件“3，计算难度很大。采用普

8、通的优化算法计算效率低而且很可能找到的解只是局部最优解。最主要的难点主要在于：(1)构造一个兼顾各个目标的综合适应度函数：(2)网络拓扑和网络业务信息量很大，光网络特殊的网络结构以及网络中复杂的保护结构，优化计算太复杂，计算效率比较低。经过预处理找到可行的路由集情况下采用GA来求解问题能够在保证有可行解的前提下以较大概率求得一个兼顾各个目标的全局最优解。二、光网络流量工程的数学模型用图论工具来描述网