【作者】 李建；

【导师】 陈建亚；

【作者基本信息】 北京邮电大学 ， 通信与信息系统， 2011， 硕士

【摘要】 随着网络技术的不断发展,不断涌现的新业务在满足用户的服务质量(Quality of Service,QoS)上提出了不同的要求。近年来业界广泛地关注网络融合及下一代网络技术,其中对下一代网络体系结构、网络资源的管理控制及合理调度的研究是一大热点。本文基于下一代层次化虚拟网络架构,通过对网络中保证QoS的路由选择算法的研究,在充分考虑网络的不同性能特点,如可用带宽、网络流量状况、节点位置及节点资源限制、系统的可靠性要求等前提下,综合考虑网络中延时、延时抖动、带宽、丢包率等多个指标的约束,引用现代优化算法中的遗传算法(GA)与粒子群优化算法(PSO)的各自优点,提出改进的粒子群算法并将其应用到多约束的QoS路由选择模型中,通过自适应地对网络状态变化做出反应并充分利用获得的动态网络状态信息,达到网络资源整体的高效利用,得出多约束条件下综合代价最小的优化路由方案。本文主要的研究工作包括如下：(1)根据下一代层次化网络,提出了下一代多约束QoS路由选择模型。考虑网络的带宽、时延、丢失率、时延抖动和代价等约束条件,研究问题为如何更有效率地寻找网络中在满足各个约束条件下由源节点到目的节点的最优路径。(2)定义能够综合衡量路径的适应值函数F(x)。适应度值函数计算的适应度值是新的路由指标,代替传统的跳数或者单一的时延等指标,作为评判路径的优劣程度的标准。适应值函数由目标函数及惩罚函数组成,惩罚函数的设计是本文的一个创新点之一,是通过将各种约束条件的合理转化而得。通过惩罚函数转化为路径的代价值后,原带约束的QoS路由选择问题变为了无约束条件的最优化问题。(3)对现代启发式优化算法中的遗传算法和粒子群算法进行研究,提出GA-PSO优化算法。首先,GA-PSO优化算法是在粒子群算法的基础上引入遗传算法中自然选择和变异的思想,以增强粒子群的多样性,提高全局搜索能力；其次,为了将改进的粒子群算法应用到路由选择问题中,本文对其进行了离散化处理；最后,在对粒子群的邻居定义方式上进行了探讨,对全局邻居定义方式和局部邻居定义方式两种不同粒子群邻居关系定义下对算法进行了考虑。最终得到了能够应用于路由选择问题中,结合了遗传算法思想的改进粒子群算法。(4)使用MATLAB软件,对所提出的GA-PSO算法进行仿真分析。仿真主要从算法的可行性、有效性、可靠性等方面进行分析。可行性是指所提算法在解决多约束的QoS路由优化问题上是否成功；有效性是从搜索效率上比较原PSO算法与GA-PSO算法在不同邻居关系定义方式下能否寻找到全局最优路径；可靠性是用在不同初始网络条件下算法获得的搜索成功率来衡量。本文提出的GA-PSO优化算法经过仿真验证,能够成功地应用于多约束条件下的路由问题求解中,引入遗传算法的思想后能很好地预防陷入局部最优解,局部邻居定义下的GA-PSO算法在搜索成功率上较全局邻居定义更具优势。整体上讲,用GA-PSO算法解决多约束路由问题能够降低网络的综合代价。更多还原

【Abstract】 With the development of network technology, the constantly emerging new business put forward different requirements to meet the user’s QoS (Quality of Service). In recent years, the industry paid widely attention to the technologies of network integration in the NGN(Next Generation Network). Among them, the forecasting of the available resources, the management of the networks and scheduling of network resources are the difficult pointsBased on the next generation virtual network structure, full considering the different performance characteristics of the network, such as available bandwidth, the condition of the network traffic, the nodes location, the nodes resource constraints and the system reliability requirements etc, this paper cited the respective advantages of the modern optimization algorithm of GA (Genetic Algorithm) and PSO (Particle Swarm Optimization) algorithm to put forward the new algorithm—GA-PSO, and applied the new algorithm to the multi-constraint QoS routing selection, which can comprehensively consider the network delay, delay jitter, bandwidth, packet loss rate and other index constraints, make full use of the dynamic network information and adaptive respond to the network state changes. The new optimization routing scheme gets the comprehensive minimum cost under the multi-constraints and achieves high utilization of the whole network resources.The mainly work of this paper includes the following:(1) Putting forward the multi-constraint QoS routing model accord to the next generation hierarchical network. The network has constraints of the bandwidth, delay, packet loss rate, delay jitter and cost etc, the question is how to effectively find out the optimal path from the source node to destination node while satisfy the constraints condition.(2) Defining the fitness function F(x), which can comprehensively evaluate the path. The fitness value calculated by the fitness function is a new routing index, which is used to instead the traditional evaluation metrics like hop count or delay. Fitness function is composed of the target function and the penalty function. The design of the penalty function, which is transformed from the index constraints, is one of the paper’s innovative points. By transforming the multi-constraints to be part of the fitness functions, the constrained QoS routing optimal problem turn to a optimization problem without restriction.(3) Proposing the GA-PSO optimization algorithm,which is inspired by the modem heuristic optimization algorithm of genetic algorithm and particle swarm algorithm. Firstly, the GA-PSO algorithm is based on the PSO, introducing the thought of natural selection and variation in GA,which can enhance the diversity of particle swarm and improve the global search ability; Secondly, discretising the GA-PSO algorithm process, so that the algorithm can used in the routing problem; Finally, discussing the neighborhood selection method of the particle swarm. Including the global neighbor definition method and the local neighbor definition method.Then we get the improved particle swarm optimization algorithm that combines genetic algorithm thoughts can be applied in the routing problem.(4) Using the Matlab software to analysis the simulation results of the proposed GA-PSO applied in the QoS routing. The simulation is mainly discussed in three apart:the feasibility, effectiveness and reliability. The output is the chart about the GA-PSO algorithm’s specific iterative process and search probability.Through the simulation, the proposed GA-PSO optimization algorithm showed that can be successfully applied in the constraint QoS routing problem, can better prevent converging in the local optimal solution after introducing the GA algorithm thoughts and can greatly improve the search probability under the definition of local neighbors.更多还原