【作者】 苑芳兵；

【导师】 王新华；

【作者基本信息】 山东师范大学 ， 计算机应用技术， 2009， 硕士

【摘要】 随着网络技术的进步,Internet中的实际网络状况已非昔日可比,这不仅体现在网络带宽的快速增加,还体现在网络拓扑的异构化、网络协议的差异化、网络的无尺度化以及服务请求的多样化、服务质量的严格化。这就导致在IPv4中所使用的尽最大努力交付的方法遇到前所未有的挑战,很多研究者在这个领域做了大量的研究,提出了QoS(Quality of Service,服务质量)的概念,尤其多约束QoS路由问题已经成为研究的热点,但由于这个问题本身所具有的NP性,导致目前尚缺乏行之有效的解决策略。本文通过在该领域中引入灰色模糊理论,提出了GFMOOA算法,在如何降低多约束问题的计算复杂度以及提高算法对陈旧性信息的忍耐性、鲁棒性方面做了一些有益的探索。文章首先对后面将会用到的灰色理论作了简要的介绍,描述了灰色理论的基础知识框架,对灰色理论的基本概念、基本原理、基本方法进行了阐述,给出了传统数学理论中有关概念和方法在灰色理论中的推广,为将灰色系统理论引入多域分层体系结构下的QoS路由做好理论准备。然后简略介绍了目前在单播多约束QoS路由领域的一些概念、发展状况以及所取得成就,对目前已有的单播多约束QoS路由策略进行了对比,找出存在的缺点及需要解决的问题。对当前的Internet网络环境进行了分析研究,概括出了其分域分层的特点,为了研究与模拟的方便,参照有关文献及已有的成熟协议将现实中的Internet环境抽象为一个多域分层的体系结构,并讨论了该体系结构的工作机理,给出了域与层的划分策略,网络节点之间拓扑路由信息的同步、共享、分发机制以及域内、域间QoS路由的计算方法。最后文章给出了将灰色理论与模糊数学相结合的层次灰色模糊综合评判的原理与计算方法,并将其运用到多约束QoS路由领域,将模糊数学在处理问题中的模糊因素方面的优势与灰色理论在处理信息不完全或不充分方面的优势融合在一起,优势互补,实现了一种代价较小但鲁棒性、可扩展性较高的多约束QoS路由算法。最后在NS2网络模拟系统中实现了该协议,在具体实现上,按照由易到难的原则先实现单域灰色模糊多目标优化算法,然后在此基础上将单域算法推广到了多域分层灰色模糊多目标优化算法,从而使问题得到完整的解决。文章简略介绍了协议实现的过程,给出了GFMOOA协议在NS2实现中的程序流程图和核心代码,并通过大量的模拟实验证明该算法是正确的、有效的,能够在多项式时间内找到满足多目标要求的灰色模糊意义上的QoS路由,在一定程度上能够容忍现实网络中网络参数信息的陈旧性、不准确性,能够根据不同的业务类型采取不同的策略,具有一定的可扩展性,尤其对复杂的、无尺度的Internet网络环境具有很好的适应性,基本达到了设计目标。更多还原

【Abstract】 With the development of network technology, Internet networks in the actual situation have been non-comparable with it used to be, which is reflected not only in a rapid increase in network bandwidth, but also in the isomerization of network topology, differences of network protocol, scale-free networks, and the diversification of service request as well as strict quality of service. This resulted in the IPv4 used to do best effort delivery methods have faced unprecedented challenges, a lot of researchers do some work in this field, put forward QoS (Quality of Service, Quality of Service) concept, in particular, multi-constrained QoS routing problem has become a research hotspot, but because of the inherent NP-problem, leading to the lack of effective solutions in current. Through importing Gray Fuzzy Theory in this field, this paper bring forward GFMOOA algorithm, making some useful explorations in the aspects of how to reduce the computational complexity of multi-constrained problem as well as improve the algorithm’s patience and robustness to old information.Firstly, the article give brief introduction of the Gray Theory which will be used behind, describe the basic knowledge framework and the basic concept of it, the basic principles, basic methods are given, present the related concepts and methods of traditional math theory at the promotion in the Gray Theory, for preparaing to introduce of the Gray System Theory to Domain Hierarchical QoS routing.Then briefly introduce some of concepts, developments as well as the achievements in the field of current unicast multi-constrainted QoS routing. Conduct a comparative study among existing unicast multi-constrained QoS routing strategies to identify their shortcomings and problems needing to be resolved. Then analyze the current Internet network environment and summarize its characteristics to be a multi-domain hierarchical architecture, simultaneously in order to research and simulation convenience, this paper abstract a Multi-Domain Hierarchical Architecture from reality Internet environment according to some references and existing sophisticated protocols, and its working mechanism is outlined. Then give the strategies to divide domain and hierarchical, the mechanisms to synchronize, share, distribute routing topology information between network nodes and the method to calculate QoS routing in inter-domain or outer-domain.Finally the article give the principles and calculation methods of Hierarchical Gray Fuzzy comprehensive evaluation method which combinate the Gray Thery and the Fuzzy Math, and apply it to multi-constrained QoS routing area. By integrating the Fuzzy Math’s advantages in dealing with fuzzy factor of problem and the Gray Theory’s advantages in dealing with incomplete or inadequate information of problem together, this paper achieve a smaller cost but higher robustness, scalability multi-constrained QoS routing algorithm. In the last we implement the protocol in the NS2 network simulation system, in specific, in accordance with the principle of going from the easy to the difficult, first achieve single-domain Gray Fuzzy multi-objective optimization algorithm, and then extended this single-domain algorithm to the Multi-Domain Hierarchical Gray Fuzzy Multi-Objective Optimization Algorithm, so that the problem is complete solution. Then, this paper provides a brief description of the process of implementation of the Protocol, gives the programme flow chart and core programme code. The simulation experiments show that the algorithm is correct and effective, can find multi-constrained Grey Fuzzy QoS routing within multinomial time, can tolerate the old and inaccurate network parameter information to a certain extent in the reality network, can adopt a different strategy according to different types of services, have some scalability, especially have good adaptability to complex and scale-free Internet network environment, the basic design goals reached.更多还原