一种时延约束的多点到多点组播路由启发式算法  

A Delay-Constrained Many-to-Many Multicast Routing Heuristic Algorithm

作　　者：张琨[1] 王珩[1] 刘凤玉[1] 

机构地区：[1]南京理工大学计算机科学与技术系,南京210094

出　　处：《计算机科学》2005年第4期107-109,共3页Computer Science

基　　金：国家自然科学基金(编号:69973020);国防科工委应用基础基金(编号:J1300D004)

摘　　要：多点到多点组播路由是组播研究领域内的一个重要问题。当单棵共享组播树不能满足时延约束时,需要建立多棵共享组播树,但同时又会增加管理开销。因此,如何尽量减少共享组播树的个数成为关键问题。本文提出了一种启发式算法DCMMHA,用来解决时延约束的多共享组播树问题(DCMSMT),该问题已被证明为NP完全问题。本文算法按照特定规则生成候选中心列表,在不违反时延约束条件下,将源节点和目的节点加入共享树,并且对已选择中心进行更新。仿真实验将DCMMHA算法同其它四种同类算法进行比较,结果表明本文的算法所获得的中心数最少,显著降低了共享树的管理开销。Many-to-many multicast routing is an important problem in multicast research fields. In some cases, when the delay constraint value of a multicast session is sufficiently small, a single shared multicast tree may not be able to satisfy this constraint. However, constructing multiple shared trees can increase managing overhead. The objective is to construct the minimum number of shared trees necessary to satisfy the delay constraint. The Delay-Constrained Multiple-Shared Multicast Tree problem (DCMSMT)is known to be NP-complete. In this paper, a heuristic algo- rithm named DCMMHA is proposed to solve DCMSMT problem. The algorithm generates an ordered list of candidate centers according to specific criterion. Then the sources and destinations attempt to join one of the shared trees, with- out violating the delay constraint. Finally, algorithm updates the selected centers. A large number of simulations demonstrate that DCMMHA algorithm has the best performance of the number of multicast centers compared to the other four algorithms, and reduces total overhead for managing these shared trees.

关 键 词：启发式算法 时延约束 组播路由 点到多点 NP完全问题 组播树 研究领域 关键问题 规则生成 约束条件 仿真实验 共享树 A算法 中心数 管理 节点 列表 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] O223[自动化与计算机技术—计算机科学与技术]