关键词: 非多项式完全问题, 稀疏模式协议独立组播, 基于组, 动态重定位, 禁忌搜索

Abstract: The prime problem to construct a shared multicast tree is to determine the position of the shared root,that is,the center selection problem.This is an NP-Complete problem.The positioning of center and the dynamic change of group members directly affects the structure of the multicast tree and the performance of multicast accordingly.Then it is required to adjust the position of the center and rebuild a multicast tree,which is a problem of center migration.How to avoid data loss and reduce the replication of multicast data in the process of center migration needs to be solved.In dynamic networks,the selection and migration of the center are two problems mutually independent and inseparable.They are also two steps indispensable to relocate RP.This paper proposes an RP selection algorithm based on tabu search and a new RP migration algorithm is then put forward.Simulation results show that good performance is achieved in multicast cost,delay from end to end and registration delay,and there is no loss and redundancy of multicast data in the process of migration.

Key words: NPC problem, PIM-SM, group-based, dynamic relocation, tabu search