【作者】 王刚；

【导师】 王华；

【作者基本信息】 山东大学 ， 计算机系统结构， 2007， 硕士

【摘要】 随着高速网络技术和多媒体技术的飞速发展，人们越来越多地提出了包括多媒体通信在内的综合服务要求。传统的分组交换网络，如Internet，是面向非实时的数据通信而设计的，只提供“尽力而为”的服务，这就意味着它只能尽力的转发用户的数据报，而在带宽和延迟等方面不提供任何保证。虽然这种服务非常适用于传统的应用，但是对于新出现的实时和分布式多媒体应用却是无法忍受的。在新一代网络上提供高水平服务质量保证己经成为目前计算机网络研究的主要课题。近几年的研究表明网络路由算法对实现网络保证质量的服务起到了非常关键的作用，对QoS路由的研究已经成为QoS研究领域中的一个非常重要研究方向。由于基于多个约束条件建立的网络模型可以更准确地反映实际的QoS路由选择问题，随着人们对网络服务质量要求的提高和网络规模的不断扩大，研究基于多条件限制的QoS路由算法，以获得良好的网络服务质量和高的网络资源利用率具有十分重要的研究意义。本文主要研究基于多约束QoS的路由算法及相关技术。本文首先深入分析了QoS路由、路由策略与算法，论述了多约束的QoS路由算法的研究现状，并讨论了多约束QoS路由算法研究的问题和数学模型。目前，Ad Hoc网络因其优异的特性和特殊的应用，受到越来越广泛的重视。多约束的路由问题是一个NP-完全问题，Ad Hoc网络链路质量差、拓扑变化频繁、容量较低的特点使得其QoS保障问题变得更加复杂。通常采用启发式算法进行求解。在目前已有的启发式算法中，蚁群优化算法以其健壮性并行性、灵活性、搜寻过程不需要人工干预以及求解精度高的特点，得到了广泛应用。但此算法在进行大规模优化时，初期收敛速度慢、收敛时间过长、易陷入局部最优解。这是蚁群优化算法的最为突出的缺陷。针对这些缺陷，近年来众多国内外学者在蚁群算法的改进方面做了大量的研究工作。但许多改进由于网络环境的复杂特性，并不适用于多约束QoS的路由优化问题。本文提出了一种的基于方向因子的蚁群改进算法OACO，借助于GPS定位来解决多约束QoS路由问题。该算法基于方向因子来调整蚂蚁的搜索行为，并根据目标函数值来调整信息素的更新，从而保证搜索的快速有效性，避免陷入局部最优解。仿真结果表明该算法提高了执行速度，减少了信息包的发送量，节省了能量开销。此外，本文还引入交叉熵方法来解多约束QoS问题。交叉熵方法最初是由Rubinstein提出，在随机模拟领域中用来估计稀有事件发生的概率，后来演变为解决组合优化问题的一个有力工具。由于其良好的全局搜索能力和完善的数学体系，得到越来越广泛的应用。本文尝试采用分布式的交叉熵方法，来解决多QoS约束路由优化问题。NS-2下的仿真结果显示出该算法的可行性和有效性，能够快速找到可行解。更多还原

【Abstract】 With the fast development of high-speed network technique and multimedia technique, people are more and more putting forward the comprehensive request of service including multimedia communication. The traditional packet switching network, such as Internet, is designed for non real time data communication, only provides "best effort" service, this means it can try its best to transmit user’s datagram, but not provide any assurance at bandwidth and delay etc. aspect. Such service is very suitable for traditional application, however, for new emergence of real time and distributed multimedia application it is beyond all bearing. Providing high level quality of service assurance at new generation network has become main task of current network research.The research in these years shows that the algorithm of network routing plays an important part in providing quality of service guarantees. The study of QoS routing has become a very important study direction in research field of QoS. Considering that network model based multiple constraints can reflect QoS routing problem in practice more accurately, with the increase of quality of service demand and the enlargement of network scale, the research of QoS routing algorithm with multiple constraints is of very important research significance to achieve good network quality of service and high efficiency in resource utilization. In this paper, we mainly study QoS routing algorithms based multiple constraints and relative technologies.First, this paper deeply analyzes QoS routing, routing policy and algorithm , and introduces the research status of routing algorithms with multiple constraints. Then the routing problem and model with multiple constraints are discussed in the paper.The Ad Hoc network has attracted more and more attention with its good performance and special application. Generally, multi-constrained QoS routing is an NP-Complete problem. The drawbacks of the ad hoc network—poor quality of network links, frequent topology change and low capacity, make it more complicated for the QoS guarantee because the time and information needed for the algorithm to search path is relatively limited. Usually heuristic algorithms are taken to solve this problem. Among the available heuristic algorithms, the ant colony optimization (ACO) has been widely applied because of its good features of being robust, parallel, flexible, demanding no artificial interference and accurate rate of solution. However, when it is used in large-scale optimization programs, it converges slowly in the beginning, and is prone to fall into local optimization. This is the main drawback of the algorithm. Many researchers have been studying to modify the algorithm in order to overcome this drawback. But due to the complexity of network environment, most modifications are not suitable to solve multi-constrained QoS routing optimization problem.We propose a modified ant colony optimization based on the orientation factor to solve multi-constrained QoS routing problem by recurring to GPS location. This algorithm employs the orientation factor to adjust the search act of ants and update pheromones according to objective function values, thus guaranteeing the speed and efficiency of the search, and avoiding falling into local optimization. Simulation results indicate that the algorithm proposed in this paper has good performance in computing speed and reduction of control information amount, thus saves energy spending.Besides, this paper introduces cross entropy method to solve multi-constrained QoS routing problem. The cross-entropy method, initially proposed by Rubinstein, is used in the field of random simulation to estimate the probability of rare events, which evolves later as a powerful tool for combined optimization. Because of well global searching ability and systemic mathematics frame, it has gained more and more application. In this paper, we try to use the distributed cross-entropy method to solve multi-constrained Qos routing optimization. Simulation results in NS-2 environment indicate the feasibility and efficiency of it, enabling quick finding of global solution.更多还原