CAJ | 학술논문

光传输网络中聚合组播问题是一个完全NP难问题,提出了一种解决聚合组播问题的双邻域查找算法.该算法使得生成的聚合树数量在满足波长约束的前提下,带宽浪费比率尽可能地小.基于贪婪策略定义了一种优先聚合规则以生成初始解;定义了两种邻域结构,使邻域查找具有效率;提出了跳坑策略以跳出局部最优解并且将查找引向有希望的方向.模拟实验结果表明:该算法可以有效地进行组播树的聚合,当轻载时,组播组阻塞比率始终为0;当重载时,与其他算法相比,平均带宽浪费比率降低25%以上.因此,对不同的网络状况都能获得较好的性能.
광전수망락중취합조파문제시일개완전NP난문제,제출료일충해결취합조파문제적쌍린역사조산법.해산법사득생성적취합수수량재만족파장약속적전제하,대관낭비비솔진가능지소.기우탐람책략정의료일충우선취합규칙이생성초시해;정의료량충린역결구,사린역사조구유효솔;제출료도갱책략이도출국부최우해병차장사조인향유희망적방향.모의실험결과표명:해산법가이유효지진행조파수적취합,당경재시,조파조조새비솔시종위0;당중재시,여기타산법상비,평균대관낭비비솔강저25%이상.인차,대불동적망락상황도능획득교호적성능.
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.