【作者】 张志成；

【导师】 田亚菲；

【作者基本信息】 兰州大学 ， 通信与信息系统， 2013， 硕士

【摘要】 随着网络技术的飞速发展,尤其是多媒体技术(如视频会议、网络电视、网络游戏、IP电话等)的广泛应用,对网络的传输能力提出了更高的要求。此类应用往往需要网络具备多点通信的能力,而组播通信就是针对多点传输和多方协作设计的通信方式。此通信方式在主链路上只有一个数据的拷贝,在分支链路上由路由器进行数据包的复制传输,极大的降低了网络资源的消耗,具有高效的数据传输效率。组播通信必将成为下一代网络数据传输中重要的支撑技术。组播路由是组播通信的关键和核心技术,要实现组播通信必须确定组播路径,组播路径是用组播分布树来描述的,而构建组播分布树就是组播路由的任务。QOS即服务质量,它能确保网络业务量的高效传输,针对各种网络业务的不同需求提供不同的服务质量,达到区分业务提高服务质量的目的。QoS组播路由的重要任务是构建一棵能够满足各种业务对服务质量需求的组播树,学者Kompella首先证明了具有两个或多个不相关可加性约束的QOS组播路由是NP-Complete问题,并提出了KPP算法来构造满足时延约束的Steiner树。随着多媒体技术的深入发展,多媒体业务对网络资源的要求愈来愈高,多约束条件下的QoS组播路由技术成为当前研究的热点。现代群智能优化都是基于自然界生物群体所表现出的群体智能现象所提出的,这些算法设计简单、易于理解,对所应用的领域没有特殊要求。因此,群智能优化算法得到广泛的研究与应用。传统QOS组播路由算法(最短路径树算法、最小Steiner树算法)有自己特殊的数学模型并有严格的论证,但是现实中的网络结构往往很复杂并且具有不确定性,并不是一种模型所能描述的,而群智能算法是启发式算法,可以避免建立严格模型的困难,对有两个或两个以上目标和约束的复杂可变网络一般都能求出有效解。近几年,将遗传算法、蚁群算法、粒子群算法等群智能优化算法应用到QoS组播路由中的文章相继发表,这些文章大多是对某一种算法的收敛时间、运行效率和搜索能力进行探索,因为每一篇文章所采用的仿真模型各不相同,所以不便对这些群智能优化算法进行统一的比较,不能形成一个全面的认识。本文采用Salama网络拓扑随机生成算法生成一个随机网络拓扑模型,定义相同的源节点和组播组节点,相同的QOS约束条件,在相同的网络拓扑模型基础上应用遗传算法、蚁群算法、粒子群算法、萤火虫算法求解QOS组播树,并对QOS的相关参数进行分析。本文使用Matlab仿真平台进行算法仿真,并使用该软件绘制相关的图表,对仿真结果进行分析研究。更多还原

【Abstract】 With widely application of the rapid development of network technology, especially multimedia technologies (such as video conferencing, Internet TV, online gaming, IP phones, and so on), higher demands of the transmission capacity of the network set are required. Such applications often require a network which has the ability of multicast, and multicast communication is designed for multicast and multi-collaborative communication, this communication method has only one copy of the data on the main link, replication transport of packets are done by routers on the way of the branch chain, which greatly reduces the consumption of network resources and improves the transfer efficiency. Multicast communications obviously will become one of the most important supporting technologies among newer network data transmission technologies. Multicast routing is the key and core part of multicast communication. To implement the multicast communication, the multicast path must be identified in advance, multicast path is described by multicast distribution tree and multicast routers will build the multicast distribution tree.QOS (quality of service) can ensure the efficient transmission of network traffic and provides a variety of service quality corresponding to the various needs for all network services separately to achieve the purpose of distinguishing different services and improving service quality.An important task of QoS multicast router is to build a multicast tree which can meet demands for all kinds of services, Kompella previously proved that it’s a NP-Complete problem for a QOS multicast router which has two or more unrelated additivity, and proposed the KPP algorithm to construct a Steiner tree to meet the delayed constraint. With the in-depth development of multimedia technology, multimedia service requests higher demand on network resources, hence multiple constrained QoS multicast routing technology becomes a quite hot topic.Modern intelligent optimization is based on swarm intelligence exhibited by natural biological communities arising from the nature, the algorithm is designed to be simple, easy to be understood and without special requirements in the field of the application, therefore study and application of swarm intelligence optimization algorithm is widely implemented.Traditional QOS group broadcast routing algorithm (shortest path tree algorithm, and minimum Steiner tree algorithm) has special mathematical model and strictly demonstration of their own, however, the network structure in reality often is complex and uncertain and can not be described by a single model. While group smart algorithm is a heuristic algorithm and does not need to establish an accurate model, it can seek out viable solutions for complex networks that have two or more targets and constraints.In recent years, a couple of articles which are about applying genetic algorithm, Ant group algorithm, particles group algorithm and smart group optimization algorithm to QoS group broadcast routing have been published, these articles mainly focused on time of convergence, implementing efficiency and capacity of search for exploration. Since each article adopt its own simulation model which is different from others, we cannot make comparison between those algorithms and formed a full awareness.In this paper, we establish a topology model for a random network using Salama random network topology generation algorithm in which we define identical source nodes, multicast group nodes and QOS constraints in the same network topology model based on genetic algorithms, Ant Colony Optimization, Particle Swarm Optimization, Firefly algorithm for QOS multicast trees and the study of QOS related parameters. This simulation was implemented on a Matlab simulation platform, the chart and analysis of the simulation results were also done on the same platform as well.更多还原