【作者】 葛连升；

【导师】 王海洋；

【作者基本信息】 山东大学 ， 计算机软件与理论， 2010， 博士

【摘要】 随着Internet的不断普及和多媒体通信技术的快速发展,特别是下一代互联网的建设、研究和试商用,以及IPTV、视频会议、视频点播、远程教学等多媒体应用迅速发展和普及,使得原来已经存在的、庞大的数据流量成倍增长,据Cisco估计,2007至2012年间Internet流量会每两年翻一番,这对Internet的健康发展带来了严峻的挑战。优化网络带宽可满足数据流量增长的需要,而IP组播通信技术是适用于一对多(或者多到多)的数据传输业务,已经成为研究实现优化带宽的一个重要手段。IP组播通信是由Steve Deering博士最初提出的一种网络体系结构,可以将源节点数据流的副本以多路复用的方式发送到一组接收者。利用组播通信技术,源节点只需产生并发送一份数据流,经过组播树中路由器的复制和转发,将数据流传送到一组目的节点。因此,与单播通信相比,组播通信可以极大地降低网络资源的消耗,同时能够减轻源节点的负担,因而IP组播通信是目前实现多媒体组通信的最佳方式。针对组播和组播路由算法的研究一直是学术界和工业界的研究热点,其中,为满足多媒体组通信对网络QoS的要求,寻找一种简单、高效、健壮的具有多约束条件的组播路由算法一直是网络界致力研究但未完全解决的问题。在数学上,带约束条件的组播路由问题被归结为带约束的Steiner树问题,该问题已经被证明是NP-Complete的,一般不能在多项式时间内找到可行解,解决这类问题一般使用近似算法、启发式算法等新型智能算法。随着中国下一代互联网示范工程CNGI的试商用,以及电信网、广播电视网和互联网三网融合工作的启动,这对IPTV、网络视频会议、网络远程教学等多媒体应用的推广部署及应用具有非常积极的政策意义和推动作用,从而对组播和网络服务质量(QOS)等产生了迫切需求,因此探索使用新型智能算法研究组播路由算法既有理论意义,也有现实意义。特别是随着下一代互联网为代表的新型、高性能网络的部署,高性能组播路由算法将成为研究的难点和热点问题,主要表现为动态、分层／聚合、分布式、高性能、低复杂度的多QoS约束的组播路由问题。另外,在实际的网络通信中,各个网络节点的组播能力是受到限制的,如何既减少节点复制信息的数量,缩短处理信息的时闻,有助于保证网络的传输速度,又平衡各个节点的负载,这就引入了度约束(degree constrained)问题。通过对网络节点给定度约束来管理节点的组播能力,并研究在有度约束情况下的组播路由问题,这在实际网络中具有重要意义。蚁群算法是一种基于种群的模拟进化算法,由意大利的Marco Dorigo于1991年在其博士论文中首先提出,并将其成功的应用于求解旅行商TSP问题。蚁群算法能够通过群体之中个体之间的相互作用解决优化问题,从而可以克服利用传统方法加以解决某些优化问题所经常遇到的无法求解或求解极其复杂等困难。其基本原理在于：蚂蚁在寻找食物过程中,虽然开始时单个蚂蚁的路径是杂乱无章的,但是蚂蚁通过相互交流信息,最后总能找到蚁巢与食物之间的最短路径。这种能力是靠其在所经过的路上留下一种信息素来实现的。蚂蚁在一条路上前进时会留下一定量的信息素,信息素的强度会随着时间的推移会逐渐挥发消失,后来的蚂蚁选择该路径的概率与当时这条路径上信息素强度成正比。对于一条路径,选择它的蚂蚁越多,则在该路径上蚂蚁所留下的信息素强度就越大,而更大的信息素强度则会吸引更多的蚂蚁,从而形成一种正反馈,通过这种正反馈,蚂蚁最终可以发现最短路径,以后大部分的蚂蚁都会走此路径。随着Internet上分布式多媒体应用对QoS的需求日益增长,QoS路由作为实现QoS需求的关键技术之一,也越来越得到研究人员的重视。将蚁群算法应用于研究受限组播路由,可以解决包括带宽、延时、包丢失率和最小花费等约束条件在内的QoS组播路由问题及度约束组播路由问题,是当前网络组播路由优化领域的一个研究热点。本论文就是使用蚁群优化这一启发式算法,研究提出了几种解决带约束条件的组播路由问题的新型蚁群算法,包括度约束环境下的组播路由算法和多QoS约束环境下的组播路由算法两个方面。论文的主要学术贡献可归纳如下：1)针对度约束组播路由问题,利用蚁群算法的正反馈机制设计了一种基于树的蚁群算法NAH。在NAH算法中,蚂蚁按照一定的概率选择一条链路加入组播子树,然后检查加入点的度约束情况,如果该点的度约束情况达到饱和,则蚂蚁以后不再选取与该点连接的链路。仿真实验表明,相比现有的AH算法,NAH算法能在更短的时间内找到最优解,而且显著地降低了空间复杂度,NAH算法的总空间复杂度为o(M×N),而AH算法的总空间复杂度为o(M×N×n),运算速度也明显加快。2)将交叉熵算法和蚁群算法相结合,设计了一个求解多QoS约束组播路由问题的新型蚁群算法。该算法将多QoS约束的组播路由问题表示成适用于交叉熵算法求解的数学模型,利用蚂蚁代理的概念,给出了基于交叉熵的蚁群算法求解多QoS约束组播路由问题时的执行步骤。通过将蚁群算法与具有完备数学基础的交叉熵算法相结合,交叉熵算法随机机制的优点保证了求解的规模和寻找解的范围足够大,从而可以显著提高最优解的质量,而且在运算速度、可扩展性等方面均优于传统蚁群算法。3)根据蚁群算法开始收敛速度慢的情况,针对多QoS约束的组播路由问题,设计了一个基于地理位置感知的蚁群优化算法。该算法将地理位置信息引入蚁群算法,蚂蚁在寻路时可以使用位置信息以获得更准确的路径选择。在此基础上,借鉴地理位置感知的思想,提出了“方向因子”的概念,并基于方向因子提出了一个改进的多QoS约束组播路由蚁群算法MACA。该算法采用了组成员节点驱动的方式构建组播树,并在概率转移函数中加入了方向因子,使蚂蚁在寻找路径时摆脱最初的盲目性,以更大的概率快速地向源节点移动,从而可以克服了传统蚁群算法中存在的收敛速度慢的缺陷。仿真实验表明,MACA算法较标准蚁群算法在收敛速度、运行时间等方面均有显著的改进。更多还原

【Abstract】 With the high popularity of Internet and rapid development of multimedia communication technology, especially with the construction, research and pre-commercialization of next generation Internet (NGI), a variety of multimedia services, such as IPTV, video-on-demand (VoD), media streaming and distance learning, have greatly expanded and produced as many times as already existed huge network traffic. It is estimated by Cisco that the Internet traffic will double every two years between 2007 and 2012. This poses a serious challenge to the healthy development of Internet. Optimizing network bandwidth can satisfy the demand of ever increasing data traffic. IP multicast, designed to be suitable for one to many (or many to many) data transmission service, is one of the most efficient network bandwidth optimization approaches. IP multicast is a novel network architecture first proposed by Steve Deering, with which the source can send only one copy of the data to a group of receivers with multiplexing. In contrast to unicast, IP multicast can significantly reduce the network overload and lower the burden of the data source; therefore, it is one of the best solutions to multimedia group communication.Multicast and multicast routing always are two hot research topics in both academia and industry. In particular, in order to meet the QoS requirements of multimedia group communication, how to seek a simple, effective, and robust multiple QoS constrained multicast routing algorithm is a problem that researchers in network and communication areas are always endeavoring to work on but never get it solved. In December 2008, the project of pre-commercialization of China next generation Internet (CNGI) is launched, and in January 2010, the integration of telecommunication networks, cable TV networks and the Internet, is put on the agenda in the executive meeting of state council. All these will have a positive influence on the deployment and application of multimedia group communication services such as IPTV, video conferencing and distance learning, and will also boost the development of these multimedia applications. As a result, IP multicast and QoS have become two urgent requirements for the forthcoming next generation multimedia services. Therefore, it is both of theoretical significance and realistic sense to research on multicast routing problems with new intelligent computational algorithms.The multi-constrained multicast routing algorithm is mathematically considered as a constrained Steiner tree problem, which is proven to be NP-Complete and can not get solved in polynomial time. Many research institutions and communities domestic and abroad have thoroughly studied this problem and proposed many approximation algorithms, such as BSMA, DMVA and SPH-R. However, these algorithms are so complicated that they have high computational complexity, and even worse, they can not guarantee the finding of the global optimal solutions in real-world networks. With the rise of intelligent computational algorithms, researchers have resorted intelligent computational algorithms, such as genetic algorithm, immune algorithm, to solve the constrained multicast routing algorithm. However, these algorithms usually do not converge at a satisfactory rate, and they do not converge to the global optimal solution in many situations.The ant colony algorithm is a new simulated evolutionary algorithm which was firstly introduced by Italian researcher Marco Dorigo in his doctoral thesis and was successfully applied to solve the traveling salesman problem (TSP). The ant colony algorithm solves the optimization problem by using the collaboration between the individuals in the population, so that it will be able to overcome the difficulties that traditional methods can not, or be hard to, solve the optimization problems. Its basic methodology is that the ant chooses a path in proportion to the path’s pheromone intensity when it is searching the food. As a result, for a path, the more ants select the path, the stronger the path’s pheromone intensity will be, and in turn, the stronger path’s pheromone intensity will attract more ants to select this path, thus a positive feedback mechanism is formed by which the ant can find the shortest path. In short, in contrast to other intelligent computational methods, the ant colony algorithm has many distinguished merits such as positive feedback, distributed computing and constructive greedy heuristic searching; therefore, the ant colony algorithm has been extensively used to solve the network routing optimization problem.With the increasing demand for multicast and network QoS by the distributed multimedia applications, it has become a hot research topic in current network and communication area that applies the ant colony algorithm to solve bandwidth, delay, packet loss rate and minimum cost constrained multicast routing problem.In this paper, we are engaged in proposing several novel multi-constrained multicast routing algorithms with ant colony optimization as our mathematical tool, including degree constrained multicast routing algorithm and multiple QoS constrained multicast routing algorithm. The main contributions of the thesis can be summarized as below:1) To solve the degree constrained multicast routing problem, we propose a novel tree based ant colony algorithm called NAH by utilizing its positive feedback mechanisms. The NAH algorithm first selects a link with a certain probability and adds it to the multicast subtree, and then it checks the degree constraint of the selected node. If the degree of the node is greater than the threshold, the ant will never select the links connected to that node again. Computer simulations show that compared with existed AH algorithm, the NAH algorithm can find the optimal solution within a shorter period; moreover, it can significantly reduce the spatial complexity. In particular, the space complexity of NAH algorithm is o(M x N), while that of AH algorithm is o(M×N×n).2) Combining cross entropy algorithm with ant colony algorithm, we design a new ant colony algorithm to solve multiple QoS constrained multicast routing problem. In the new algorithm, the multiple QoS constrained multicast routing problem is transformed into the mathematical model that can be solved by the cross entropy algorithm. After that, the procedures are presented how to apply cross entropy based ant colony algorithm to solve multiple QoS constrained multicast routing problem with the notion of ant agent. By combining ant colony algorithm with mathematically self-contained cross entropy algorithm, the quality of optimal solution is greatly improved because the randomness mechanism in the cross entropy algorithm guarantees the solution scale as well as the search scope for the solution. In addition, the new algorithm has advantages in computing speed and scalability over standard ant colony algorithm.3) As the ant colony algorithm converges with a slow speed in its initial phase, we propose a geographical awareness based ant colony algorithm which introduces geographical information into the standard ant colony algorithm. The ants in the new algorithm can make better path selection with the help of the incorporated geographical information. Then we present the notion of "orientation factor" by utilizing the concept of geographical awareness. Based on the notion of orientation factor, we propose an improved multiple QoS constrained multicast routing ant colony algorithm named MACA. The MACA algorithm builds the multicast tree using the receiver-driven approach, and it adds orientation factor into the path selection probability function which can make the ants move faster to the source by getting rid of the blindness in early path selection. Experimental results show that the MACA algorithm make great improvements in both convergence speed and computing time.更多还原