Journal of Software:2013.24(2):243-254

(武汉邮电科学研究院,湖北 武汉 430074)
Double Neighborhood Search Algorithm in Multicast Aggregation
WANG Xue-Shun,YU Shao-Hua,DAI Jin-You
(Wuhan Research Institute of Post and Telecommunication, Wuhan 430074, China)
Chart / table
Similar Articles
Article :Browse 2190   Download 2485
Received:January 23, 2011    Revised:April 16, 2012
> 中文摘要: 光传输网络中聚合组播问题是一个完全NP 难问题,提出了一种解决聚合组播问题的双邻域查找算法.该算法使得生成的聚合树数量在满足波长约束的前提下,带宽浪费比率尽可能地小.基于贪婪策略定义了一种优先聚合规则以生成初始解;定义了两种邻域结构,使邻域查找具有效率;提出了跳坑策略以跳出局部最优解并且将查找引向有希望的方向.模拟实验结果表明:该算法可以有效地进行组播树的聚合,当轻载时,组播组阻塞比率始终为0;当重载时,与其他算法相比,平均带宽浪费比率降低25%以上.因此,对不同的网络状况都能获得较好的性能.
Abstract:The problem of aggregated multicast in optical transmission networks has been known to be a complete NP-hard problem. A double neighborhood search algorithm (DNSA) for solving the multicast aggregation problem is presented. The objective of this algorithm is to minimize the bandwidth wastage ratio that is subject to the constraints that the number of multicast aggregation tree is affected by the amount of wavelength. In this paper, a priority aggregate rule based on the greedy strategy is proposed to generate initial solution: two kind neighborhood structures are proposed to search effectively, and some off-trap strategies are proposed to jump from local optimal solution and carry the search to the feasible areas in promising directions. Simulation experiments show the double neighborhood search algorithm can aggregate multicast trees effectively. The multicast group blocking ratio is 0 at light load. Compared with other algorithms at heavy load, the average bandwidth wastage ratio has decreased more than 25%. The results indicate that improvements may be obtained in different network condition.
文章编号:     中图分类号:    文献标志码:
基金项目:光纤通信技术和网络国家重点实验室开放基金(2010OCTN-03) 光纤通信技术和网络国家重点实验室开放基金(2010OCTN-03)
Foundation items:
Reference text:


WANG Xue-Shun,YU Shao-Hua,DAI Jin-You.Double Neighborhood Search Algorithm in Multicast Aggregation.Journal of Software,2013,24(2):243-254