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

摘要

近年来，随着计算机和网络技术的快速发展，越来越多的多媒体业务应用出现在互联网中，例如，广播、视频会议、远程教育等等，这些应用对网络带宽和延迟等都有很高的要求，组播一直被认为是一种有效的解决方案。但是IP组播具有极大的依赖性，特别是对网络设备，需要对组播路径上的设备进行升级，因此会耗费巨额资金，阻碍了IP组播的广泛部署。这也是IP组播一直以来没有得到广泛应用的原因之一。随着应用对网络组播的迫切需求，人们提出了应用层组播这一解决方案。
　　P2P技术作为应用层的一个实际应用也在不断的发展。基于P2P覆盖网络具有很多优点。因此，P2P覆盖网络的组播问题已成为学术界以及工业界研究的研究热点。比较典型的P2P网络组播有:Scribe、Chord组播、CAN-Multicast以及Bayeux。由于现在流媒体应用的兴起，需要传输的数据量很大，在P2P网络上用组播或广播的方式来进行软件更新文件以及预测可能流行内容的发送，从而使每个节点需要背负沉重的负载来把数据转发给它的相邻节点，为了减小节点以及链路的压力，需要有效的限制每个节点的度数。并且对于应用服务提供商来说希望得到一个总花费小的解决方案。因此，P2P组播在覆盖网络上传输内容，即使数据沿着P2P网络的生成树来进行，并且限制树的最大度数。这样的一个解决方案树被图论中称为是度约束最小生成树。
　　在本文中，P2P应用层组播为研究对象，重点研究了应用层组播如何高效寻求得到一棵高效的度约束最小组播树问题。主要工作如下:
　　(1)在本文中，提出了一种新的方案来解决度约束最小生成树问题，即采用了基于蚁群算法并且伴随有局部搜索的方法。做了相关仿真实验，并且将仿真结果与其他算法进行了比较。蚁群算法是一个通过个体寻找以及与集体合作来寻找最优解的优化算法，但是蚁群算法需要搜索的时间比较长，有时容易陷入局部最优，所以我们采用了基于蚁群算法并且结合局部搜索操作的算法，这种方法在很大程度上避免了算法陷入局部最优的缺点。仿真结果表明，我们提出的新的蚁群算法相比其他的智能算法在效率上更优。
　　(2)我们对蚁群算法进行了更改，该算法比传统算法效率提高了很多。随后研究了分布估计算法的特性，使我们提出的算法具有了快速收敛的性质，并且提出了基于此种算法伴有局部搜索的新方法。一方面从宏观上来把握搜索方向，另一方面局部搜索操作避免了此算法的易早收敛，陷入局部最优的缺点。经过仿真实验得知用新提出的方法来解决度约束最小生成树问题比以往的算法在效率上都要好，说明我们提出的这种方法是可行的。