一种基于禁忌搜索的时延约束组播路由算法  

A Multicast Routing Algorithm with Delay-constrained Based on Tabu Search

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

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

出　　处：《计算机工程》2005年第11期22-24,64,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(60273035);国家高技术研究发展计划基金资助项目(2001AA113161);江苏省自然科学基金资助项目(BK2002080)

摘　　要：提出了一种使用禁忌搜索方法构造组播树的时延约束最小代价组播路由算法(TSBDMA)。该算法充分利用禁忌搜索方法中灵活的记忆功能和禁忌规则等特点,以最小时延树为初始解,并使用换边操作构造邻域集,最终求得满足条件的组播树。仿真实验结果表明本算法具有代价性能良好、可靠性高、收敛速度快、时延低的特点。A novel algorithm based on tabu search for delay-constrained least-cost multicast routing (TSBDMA) is proposed to solve delay-constrained multicast routing problem. This algorithm makes use of the characteristics of flexible memory function and tabu rule in TS algorithm, starts with an initial least delay tree, generates neighborhood structure based on 'exchange edge' operations, and finds multicast tree satisfying constraint. A large number of simulations demonstrate that the algorithm has characteristics of nice cost performance, high reliability, fast convergence speed and low delay.

关 键 词：组播路由 禁忌搜索 QOS约束 

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