Delay-Constrained Multicast Throughput Maximization in MEC Networks for High-Speed Railways

Multi-access Edge Computing presents a compelling solution for delivering seamless connectivity to computing services. In this study, we aim to optimize multicast throughput to ensure high-quality experiences for passengers engaged in inter-train interactions within dedicated MEC networks designed for high-speed railways. Considering the unique challenges associated with high-speed railways, we model multicast routing paths as group Steiner trees. Subsequently, we devise a rapid tree construction method by converting the root search into the Generalized Assignment Problem (GAP). This innovative approach skillfully balances accuracy and computational efficiency. We demonstrate that this problem can be effectively reduced to the bounded knapsack problem with setups. In addition, we recognize the presence of precedence constraints between tasks and their respective outcomes. Consequently, we introduce a new variant of the knapsack problem, which we refer to as the Precedence-constrained Bounded Knapsack Problem with Setups. Our approach, termed the GAP- and knapsack-based Group Steiner Tree (GKGST), offers a relative performance guarantee of 1/2. We evaluate the GKGST algorithm against three baseline algorithms, which are adapted and extended from existing literature. Simulation results indicate that our proposed algorithm exhibits considerable potential for enhanced performance.