多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展，多播技术应用日益广泛，多播路由是要寻找连接源节点和一组目的节点的一棵多播树，这个问题在数学上归结为Steiner树问题，它是一个NPC问题。在实际网络中，网络节点具备不同的多播能力，有些节点不支持多播，有些节点支持多播，但为了保证网络速度和节点负载平衡，支持多播的节点要限制其复制信息的数量，即节点的多播能力受限。在这种情况下，寻找多播树变得更加困难，该文用节点的约束来表示敏个节点具备的多播能力，节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题，其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树，因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树；外层算法进行全局搜索。该文将算法在稀疏图上进行实验，为了更好地模拟真实网络，稀疏图中每个节点具有不同的多播能力，并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较：（1）解的质量；（2）计算时间；（3）算法的收敛性。实验结果表明，文中提出的遗传算法能够找到费用较小的多播树，但是当网络规模增大时，算法的求解时间也较长。

Degree-Constrained Multicasting for Multimedia Communications

With the proliferation of multimedia group applications, multicasting is becoming increasingly important. Multicast routing is establishing a multicast tree that is rooted from the source node and contains all the multicast destinations, which is often modeled as the NP-Complete Steiner problem in networks.Finding a multicast tree is complicated by the likely heterogeneous nature of the multicast environment. Nodes in the network will likely vary in their abilities to support multicasting. Some nodes may not support multicasting; others may be limited in the number of multicast copies they can reasonably make in order to ensure network speed and distribute the load more evenly among the nodes in the network. The multicast capability of each node is represented in this paper by a degree-constraint. The problem of how to create the multicast tree when nodes have different multicast capability is referred to as the degree-constrained multicast tree problem, which is also a NP-Complete problem. In this paper, a two-layer genetic algorithm (GA) for solving the degree constrained multicasting problem is proposed. The basic idea of this algorithm is that the optimal multicast tree must be a minimal spanning tree satisfying the degree-constraint, so the key to the final result is to find the Steiner nodes which should be included in the final tree. The algorithm adopts binary coding. The inner layer GA builds the degree constrained minimal spanning tree; the outer layer GA performs global exploration. The paper presents the simulation results of the algorithm proposed on sparse networks of nodes with varying multicast capability, and the simulated multicast groups are small relative to the size of the network, reflecting likely multicast applications. We experiment on the GA in three aspects: (1) quality of solution; (2) computational time; (3) convergence. Experimental results show that the algorithm proposed can find the tree with minimal cost. But the GA proposed requires much time to find a multicast tree when the network grows larger.