A Study of Multicast Message Allocation for Content Distribution with Device-to-Device Communications
Jianguo Xie, Wei Song, Xi Tao · 2017
As an enabling technology for the fifth-generation (5G) wireless networks, device-to-device (D2D) communications can provide many promising applications such as message dissemination and content distribution. In this paper, we study an important problem for D2D-assisted content distribution, which allocates the message requests to be served by the cache devices via D2D multicast. Aiming to minimize the total transmission cost or maximize the gain in cost saving for the base station (BS), this message allocation problem can be formulated from different perspectives, as a weighted set cover problem (WSCP), a hypergraph matching problem, or a multiple-choice knapsack problem (MCKP). Here, we evaluate three approaches for the formulated problems, including a greedy algorithm, a heuristic algorithm based on Lagrangian relaxation, and a fully polynomial-time approximation scheme (FPTAS), respectively. Simulations are conducted to compare the performance in the static and dynamic scenarios in terms of total cost, unit cost, D2D offload ratio, and service latency. The results show that the MCKP based approach outperforms the other two because the approximation guarantee of the FPTAS results in solutions closest to the optimum.