Collaborative content distribution with device-to-device communications
University of New Brunswick
With the increasing penetration of smart devices, device-to-device (D2D) communications offer a promising paradigm to accommodate the ever-growing mobile traffic and unremitting demands. The redundant storage and communication capacities of smart devices can be exploited for collaborative content caching and distribution. In this thesis, we first studied the D2D pairing problem, which appropriately pairs a device requesting a content item with a nearby device which caches the requested item. We formulated the D2D pairing problem as an integer linear program (ILP) and developed a heuristic channel-aware algorithm to solve it. Computer simulations were conducted to compare the channel-aware algorithm with the optimal solution, as well as a minimum distance-based algorithm and a random algorithm. The results show that the channel-aware algorithm outperforms the random algorithm in terms of total number of served D2D pairs and average latency of served pairs. Then, we studied the message allocation problem, 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). We compared three algorithms for the formulated problems, including a greedy algorithm, a heuristic algorithm based on Lagrangian relaxation, and a fully polynomial-time approximation scheme (FPTAS), respectively. The simulations results show that the WSCP based algorithm outperforms the other two in static scenarios in terms of D2D offload ratio and total cost. In dynamic scenarios, the MCKP based algorithm performs the best because the approximation guarantee of the FPTAS results in solutions closest to the optimum.