近年来Internet发展迅速,网络上需要组通信支持的各种分布式应用不断增多。作为支持组通信的主要技术,传统的IP (Internet protocol)组播技术要求网络为每一个组播组(甚至组播组的每一个源)建立和维护一棵组播转发树,树上的每台路由器都需要保存这个组播组(源)的转发状态。当网络上并发的组播组不断增加时,路由器上为这些组播组维护的组播转发状态也会不断增加。不断增长的组播转发状态一方面需要路由器更多的内存来存储,另一方面转发组播分组时查表的时间更长。同时,一个组播组的转发状态需要组播组的树上路由器之间周期性的交换信息来建立和维护。当并发的组播组增加时,用于建立和维护这些转发状态的控制信息也会不断增加,这会消耗网络更多的带宽。转发状态和控制信息的增多会减慢网络的转发速度,导致整个网络的性能不断下降。当网络上组播组的数量增加到一定程度,整个网络就会由于性能下降的厉害而变得不可用。这就是传统IP组播技术面临的组播状态扩展性问题。尤其是,这个问题当组播支持服务质量(Quality of Service, QoS)时变得更加严重,这时不仅需要额外的内存来存储各种服务质量的参数,同时,由于组播组成员服务质量的要求不同,可能一个组播组需要几棵组播树才能够完成满足不同服务质量要求的数据的传递。所以,真正大规模部署IP组播时,面临着组播状态扩展性问题的挑战,只有解决了这个问题,大规模的组播的部署才会变得可能。由于Internet网络是一个层次网络,多个用户网络连接到一个区域网络,多个区域网络连接到一个骨干网络。多个用户网络之间的数据传输都需要经过共同的骨干网络,传统IP组播技术中骨干网络需要为每个经过它的组播组维护组播状态,组播状态扩展性问题在骨干网络中尤为突出。所以,研究组播状态扩展性问题,尤其是骨干网络上的组播状态扩展性问题,具有重要的理论和现实意义。聚合组播作为近年提出的一种非常有前途的解决骨干网络中组播状态扩展性问题的思想,使多个组播组共享一棵组播树(聚合树)。组播树数量的减少,不但减少了整个网络中组播状态,同时也减少了网络建立和维护树的控制开销。共享的组播树一定要能够完全覆盖其所服务的组播组才能够完成数据的正确传输,由于共享组播树的组播组不一定有共同的成员集合,通常情况下聚合树的叶子节点要多于每个组播组的成员。这就会带来额外的带宽浪费。因此,聚合组播是组播树数量减少和额外带宽浪费的一种折中。这是一个多目标优化问题,对应着两个优化方向：给定带宽浪费率,最小化组播树数量的聚合树优化问题(带宽浪费率受限的聚合组播问题)；和给定聚合树数量,最小化带宽浪费率的带宽优化问题(聚合树数目受限的聚合组播问题)。能否有效的解决这两个优化问题,得到相应优化问题较好的解,关系到聚合组播在网络中实际的部署效果。同时,这两个问题又都是NPC问题。为这两个问题设计有效的解决算法,提高算法的优化能力,是本文研究的重点。首先,论文给出了聚合树优化问题(ATOP, Aggregated Tree Optimization Problem)的最小分组描述和最小分组模型。最小分组问题是一类问题的统称,许多具体的问题,如装箱问题、图分色问题和最小团覆盖问题等,都属于最小分组问题。使用启发式算法解决这些问题时,通常由于陷入局部最优而不能得到满足需求的比较优化的解。为了得到更高质量的解,近年来提出许多种类的元启发式算法。由于蚁群优化(Ant Colony Optimization, ACO)算法在解决许多最小分组问题的具体问题时能够取得一流的或有竞争力的解,所以重点是设计高效的聚合树优化问题的蚁群优化算法。在设计具体的蚁群优化算法时,使用了分层的设计思路：首先根据问题的最小分组特征,尤其是在一次迭代过程结束时,经常有多个迭代最优解的情况,为了有效的从这些解中得到有利于寻找最优解的知识,提出了两个组播组之间的适应度函数的设计原则,并在此之上,设计了新的多级信息素的分配原则。同时,根据算法的随机特性,提出了算法的新的终止条件。然后,在这些原则的基础上分别使用装箱模型和最小团覆盖模型来解析聚合树优化问题中的聚合条件,提出了基于装箱模型和基于最小团覆盖模型的启发式信息,以及具体的组播组之间的适应度函数的定义和信息素的更新规则。这两个模型分别从不同的角度刻画和描述了聚合树优化问题,反应了聚合树优化问题的不同的特征。仿真结果显示,本文提出的组播组之间的适应度函数定义原则和与之关联的多级信息素分配原则能够显著的提高算法的寻优能力。与已有算法比较,不再需要事先计算候选树集合,更加适用于带宽浪费率比较大或网络规模比较大的场景。其次,论文使用分组模型定义了带宽优化问题,并提出了基于组播树的相似性的蚁群优化算法。通过分析带宽优化问题的特征,将带宽优化问题分解为初始树选择和树聚合两个阶段。定义了组播树(组播组)的相似性,分析了相似性的不对称特征,提出使用相似度和相似性排名的组合来确定初始树选择阶段和树聚合阶段的启发式信息。同时,在这两个阶段中,根据信息素的含义,在不同的阶段使用信息素的两种形式(信息素本身和它的反)和相似性的两种形式。根据问题的特征设计了新的信息素的更新规则。仿真结果表明,本文提出的算法取得了比启发式算法更加优化的解,与普通的蚁群优化算法相比,本文提出的算法能够更快的收敛到同样优化的解,验证了所提启发式信息的有效性。论文的最后给出了以后研究的展望,提出了解决聚合组播问题的动态算法、带有服务质量的聚合组播算法等研究方向。