Multi-hop multicast path construction in modern wireless relay networks

In recent years, multicast over wireless access networks has become a popular research topic. However, if relay nodes are supported in such a network, forming an efficient multicast topology becomes a challenging task. Since existing works fail to solve this problem satisfyingly, we in this paper propose a multi-hop multicast routing scheme for modern wireless relay networks. First, we formulate this important problem as Multi-Hop Multicast Maximization (MHMM), which involves forming a resource allocation of the base-station and relay stations in order to maximize the number of recipients with the given resource budget and channel conditions. To solve MHMM, we propose a heuristic called Multi-Hop Path Selection (MHPS). We prove that MHMM is NP-complete, and also analyze MHPS’s computational complexity and its worst-case performance. The results of simulations conducted to evaluate the heuristic’s performance demonstrate that, under variant conditions, MHPS utilizes bandwidth resources and relay nodes effectively such that it significantly outperforms all existing approaches. Moreover, its performance difference to the optimum is bounded. To the best of our knowledge, MHPS is the only scheme that focuses on this important issue and achieves such a satisfactory performance.