新的群播路由算法  

Algorithm for Group Multicast Satisfying QoS

作　　者：江莉[1] 

机构地区：[1]青岛科技大学数理系,山东青岛266000

出　　处：《计算机工程与应用》2006年第32期140-142,153,共4页Computer Engineering and Applications

摘　　要：考虑了费用非对称通信网络上的群播路由问题。首先提出了一种满足带宽约束接近最小成本的启发式算法NEW1-GM算法。该算法以FMPH算法(FastMinimumPathCostHeuristicAlgorithm)为基础,可以有效地降低成本。数值实验表明,这种算法是有效的,且所获得解的总费用几乎总是小于或等于由GTM算法所获得的解的总费用。然后,提出了一种满足延迟约束的DFMPH算法(Delay-ConstrainedFastMinimumPathCostHeuristicAlgorithm)。最后,在NEW1-GM算法和DFMPH算法的基础上提出了一种不仅满足延迟和带宽要求且接近最小成本的启发式算法DGM1算法。NEW1-GM算法和DGM1算法的时间复杂度均与GTM算法相同,为O(p3n2)。In this paper,we consider the Group Muhicast Routing Problem （GMRP） in cost-asymmetric communication networks.Firstly,a heuristic algorithm based on the Fast Minimum Path Cost Heuristic Algorithm（FMPH）,namely NEW1- GM,is presented.It can reduce cost effectively.The simulation results show that the algorithm is effective.Then,a delayconstrained multicast algorithm,the Delay-Constrained Fast Minimum Path Cost Heuristic Algorithm （DFMPH）,is presented.At last,another heuristic algorithm（DGM1） based on NEW1-GM and DFMPH is presented,which can find a set of sub-optimal cost muhicast trees satisfying delay and bandwidth constraints.NEW1-GM and DGM1 have the same 3 2 time complexity O（p^3 n^2 ） as GTM.

关 键 词：通信网络 多播 QOS约束 启发式算法 群播 

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