| 摘要: |
| 光传输网络中聚合组播问题是一个完全NP 难问题,提出了一种解决聚合组播问题的双邻域查找算法.该算法使得生成的聚合树数量在满足波长约束的前提下,带宽浪费比率尽可能地小.基于贪婪策略定义了一种优先聚合规则以生成初始解;定义了两种邻域结构,使邻域查找具有效率;提出了跳坑策略以跳出局部最优解并且将查找引向有希望的方向.模拟实验结果表明:该算法可以有效地进行组播树的聚合,当轻载时,组播组阻塞比率始终为0;当重载时,与其他算法相比,平均带宽浪费比率降低25%以上.因此,对不同的网络状况都能获得较好的性能. |
| 关键词: 全光传输网络 组播聚合 拟人跳坑策略 双邻域查找 波长带宽分配 |
| DOI：10.3724/SP.J.1001.2013.04247 |
| 分类号: |
| 基金项目:光纤通信技术和网络国家重点实验室开放基金(2010OCTN-03) |
|
| 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
|
| 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. |
| Key words: all-optical transmission network multicast aggregation quasi-human off-trap strategy double neighborhood search wavelength and bandwidth allocation |
