在计算机网络中，多播是目前研究最多、应用最广的连接方式。多播涉及将同一信息从源节点传送到网络中多个节点（不一定是网络中所有节点）。多播路由是网络层具备的功能，多播问题的关键在于多播路径的确定。实现多播的一般方式是建立多播树，多播树是根为源节点，且覆盖所有多播成员的一棵生成树。多播树的优点在于，首先信息以并行方式沿着树枝发送到不同的多播成员，从而降低了信息传递的时延；其次信息的复制只在树杈上进行，因此网络中需要传送的复制信息最少，能够节省网络带宽资源，减少拥塞。多播路由算法主要用来建立一棵性能好的多播树，并使得它满足各种业务的服务质量（QoS：Quality of Service）需求。 目前多播路由算法的研究大多都针对无约束多播路由问题和时延受限多播路由问题。本论文首先对无约束多播问题，即最优Steiner树问题的启发式算法进行了总结；接着对时延受限多播问题提出了三种性能良好的多播路由算法；此外，本论文又研究了在网络部分节点具有多播能力情况下的多播路由算法和带宽受限的多播路由算法。 本文的主要研究工作如下：1、由于求解费用最小多播树问题在数学上归结为Steiner树问题，为此本文总结 了Steiner树问题的各种启发式算法，分析了算法的复杂度以及各种算法适用 的情况和特点，这为后面的工作打下了基础。2、给出了三种求解时延受限多播路由问题的多播路由算法。第一种算法是基于遗 传算法和局部搜索算法的混合遗传算法，算法采用自然编码方式，即每个个体 就是一棵覆盖多播组成员的子树，并针对问题特点，提出了修正算法和基于局 部搜索的交叉算子。第二种多播路由算法仍是一个遗传算法，算法采用二进制 编码方式，通过对中间节点进行搜索，以确定包含在最优解中的Steiner节点， 最后确定最优多播树。仿真结果表明，提出的这两种算法与目前性能最好的同 类算法BSMA性能接近，但时间复杂度小于BSMA算法的复杂度。第三种算 法是一个利用局部信息的多播路由算法，算法确定路由时无需源节点具有全网 拓扑，每个节点只需同邻接节点交换信息就可进行路由计算，算法实现简单并 且性能与CDKS算法的性能相当，表明它是一个很实用的算法。3、研究了在网络中有些节点不具备多播能力的情况下如何进行多播路由。采用节 点的度约束来表示每个节点不同的多播能力，提出了三种带度约束的多播路由 算法。第一种算法是分布式多播路由算法，其优点是每个节点不需存储全网拓 扑，并且只有多播组成员才参与路由的确定，路由的计算和建立同时完成；并 且算法所需传递信息的数量小，复杂度低。第二种算法是一个双层遗传算法， 算法对中间节点进行编码，采用标准邀传算于，内层遗传算法用于求解带度约 束的最小生成树，外层算法求解多括树。实验结果表明算法的性能良好。第三 种算法是利用局部信息的多括路由算法，算法实现只需每个节点保存到目的节 点的最短路信息。算法简单易行。4、带度约束和时延约束的多括路由问题是在本论文中首先提出的一类新问题。利 用拉格朗日松弛法给出了带度约束和时延约束的多括路由算法，算法效果良 好。5、研究了带宽受限条件下，要求时延最小的多括路由问题，提出了最大带宽最小 时延多播路由算法和带宽受限最小时延多括路由算法，证明了算法的正确性并 给出了算法的复杂度。