Abstract: In Application Layer Multicast（ALM） system, the end-hosts undertaking the task of forwarding data have no wire-speed forwarding capability. Heavy forwarding load can result in congestion occurring on the end-host, thus causing that the sub-routing tree rooted at the congested end-host losses connection. In order to address the issue of poor stability of ALM resulted from congestion, the process of constructing the optimal multicast routing tree is formulated as the degree-constrained least-cost Steiner tree problem. A Genetic Algorithm（GA） for constructing node-forwarding-capability-restricted ALM routing tree is proposed. The proposed GA encodes a multicast routing tree by using the predecessor of each tree-node, which is convenient for measuring the out-degree of nodes. In order to make the genetic manipulation applicable to the predecessor-based routing tree representation, the conception of  “gene-pool” is introduced to implement the operation of crossover and mutation. Aiming at the production of infeasible solutions caused by the degree-constraint, a new optimization objective is proposed to treat the excess that a multicast routing tree violates the degree-constraint as the 2nd minimization goal such that the multicast routing tree being satisfied with the degree-constraint can be chosen from the Pareto front, which avoids the risk of obtaining infeasible solution by using the penalty function-based method. Simulation experiments show that the proposed GA is capable of constructing the node-forwarding-capability-restricted ALM routing tree of the least transmission delay and possesses good reliability on problem-solving.

Key words: application layer multicast, genetic algorithm, constraint-relaxation, multi-objective optimization

摘要： 在应用层组播系统中，负责数据转发的终端节点不具备线速转发能力，较重的转发负载会引起拥塞。以拥塞节点为根的整个子路由树将与源节点失联。为解决由拥塞导致应用层组播稳定性差的问题，将构造最优组播树的过程抽象为有度约束的最小代价Steiner树问题。提出了一种用于构造节点转发能力受限应用层组播树的遗传算法，算法以组播树上各节点的直接前驱对其进行遗传表达，便于节点出度的统计。为使遗传操作适用于直接前驱编码，引入了“基因池”的概念并以此为基础实现了交叉与变异。针对度约束导致产生非可行解的问题，提出将组播树对度约束的超出量作为一个新的优化目标，从而以多目标优化的方式得到Pareto前沿，并从Pareto前沿上截取满足度约束的解作为最终输出，避免了使用惩罚函数法的求得非可行解的风险。仿真实验表明，提出的遗传算法能够构造节点转发能力受限的应用层组播路由树，具有良好的求解可靠性。

关键词: 应用层组播, 遗传算法, 约束松弛, 多目标优化