基于度约束的P2P覆盖网络组播智能算法的研究

发布时间：2018-07-03 00:55

本文选题：P2P组播 + 应用层组播　；参考：《山东大学》2014年硕士论文

【摘要】：近年来,随着计算机和网络技术的快速发展,越来越多的多媒体业务应用出现在互联网中,例如,广播、视频会议、远程教育等等,这些应用对网络带宽和延迟等都有很高的要求,组播一直被认为是一种有效的解决方案。但是IP组播具有极大的依赖性,特别是对网络设备,需要对组播路径上的设备进行升级,因此会耗费巨额资金,阻碍了IP组播的广泛部署。这也是IP组播一直以来没有得到广泛应用的原因之一。随着应用对网络组播的迫切需求,人们提出了应用层组播这一解决方案。 P2P技术作为应用层的一个实际应用也在不断的发展。基于P2P覆盖网络具有很多优点。因此,P2P覆盖网络的组播问题已成为学术界以及工业界研究的研究热点。比较典型的P2P网络组播有：Scribe、Chord组播、CAN-Multicast以及Bayeux。由于现在流媒体应用的兴起,需要传输的数据量很大,在P2P网络上用组播或广播的方式来进行软件更新文件以及预测可能流行内容的发送,从而使每个节点需要背负沉重的负载来把数据转发给它的相邻节点,为了减小节点以及链路的压力,需要有效的限制每个节点的度数。并且对于应用服务提供商来说希望得到一个总花费小的解决方案。因此,P2P组播在覆盖网络上传输内容,即使数据沿着P2P网络的生成树来进行,并且限制树的最大度数。这样的一个解决方案树被图论中称为是度约束最小生成树。在本文中,P2P应用层组播为研究对象,重点研究了应用层组播如何高效寻求得到一棵高效的度约束最小组播树问题。主要工作如下： (1)在本文中,提出了一种新的方案来解决度约束最小生成树问题,即采用了基于蚁群算法并且伴随有局部搜索的方法。做了相关仿真实验,并且将仿真结果与其他算法进行了比较。蚁群算法是一个通过个体寻找以及与集体合作来寻找最优解的优化算法,但是蚁群算法需要搜索的时间比较长,有时容易陷入局部最优,所以我们采用了基于蚁群算法并且结合局部搜索操作的算法,这种方法在很大程度上避免了算法陷入局部最优的缺点。仿真结果表明,我们提出的新的蚁群算法相比其他的智能算法在效率上更优。 (2)我们对蚁群算法进行了更改,该算法比传统算法效率提高了很多。随后研究了分布估计算法的特性,使我们提出的算法具有了快速收敛的性质,并且提出了基于此种算法伴有局部搜索的新方法。一方面从宏观上来把握搜索方向,另一方面局部搜索操作避免了此算法的易早收敛,陷入局部最优的缺点。经过仿真实验得知用新提出的方法来解决度约束最小生成树问题比以往的算法在效率上都要好,说明我们提出的这种方法是可行的。
[Abstract]:In recent years, with the rapid development of computer and network technology, more and more multimedia applications appear in the Internet, such as broadcasting, video conferencing, distance education and so on. These applications have high requirements for network bandwidth and latency, multicast has been considered as an effective solution. However, IP multicast has a great dependence, especially for network devices, it needs to upgrade the devices on the multicast path, so it will cost a lot of money and hinder the extensive deployment of IP multicast. This is one of the reasons that IP multicast has not been widely used. With the urgent demand of application for network multicast, people put forward the solution of application-layer multicast, and P2P technology as a practical application of the application layer is developing constantly. P2P overlay network has many advantages. Therefore, the multicast problem of P2P overlay network has become a research hotspot in academia and industry. The typical P2P multicast networks include: Scribechord multicast CAN-Multicast and Bayeux. Due to the emergence of streaming media applications, the amount of data needed to be transmitted is very large. In P2P networks, multicast or broadcast is used to update software files and predict the transmission of popular content. In order to reduce the pressure of nodes and links, each node needs to carry a heavy load to transmit the data to its adjacent nodes. In order to reduce the pressure of nodes and links, it is necessary to effectively limit the degree of each node. And for the application service provider, the hope is to get a small total cost of the solution. Therefore, P2P multicast transmits content over overlay network, even if the data is carried out along the spanning tree of P2P network, and the maximum degree of the tree is limited. Such a solution tree is called the degree constraint minimum spanning tree in graph theory. In this paper, P2P application-layer multicast is studied, and the problem of how to find an efficient minimum multicast tree with degree constraints is studied. The main works are as follows: (1) in this paper, a new scheme is proposed to solve the degree constrained minimum spanning tree problem, which is based on ant colony algorithm and accompanied by local search. The simulation results are compared with other algorithms. Ant colony algorithm is an optimization algorithm to find the optimal solution through individual search and collective cooperation, but ant colony algorithm needs to search for a long time, sometimes it is easy to fall into local optimization. So we adopt the algorithm based on ant colony algorithm and combined with local search operation, this method largely avoids the disadvantage that the algorithm falls into local optimum. Simulation results show that the proposed new ant colony algorithm is more efficient than other intelligent algorithms. (2) We have modified the ant colony algorithm, which is much more efficient than the traditional algorithm. Then, the characteristics of the distribution estimation algorithm are studied, which makes the proposed algorithm have the property of fast convergence, and a new method based on this algorithm with local search is proposed. On the one hand, the search direction is grasped from the macro level; on the other hand, the local search operation avoids the premature convergence of the algorithm and falls into the local optimum. The simulation results show that the proposed method is more efficient than the previous algorithms to solve the degree constrained minimum spanning tree problem, which shows that the proposed method is feasible.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02;TP18

【参考文献】