Opportunistic Finite Horizon Multicasting of Erasure-Coded Data

We propose an algorithm for opportunistic multicasting in wireless networks. Whereas prior multicast rate adaptation schemes primarily optimize long-term throughput, we investigate the finite horizon problem where a fixed number of packets has to be transmitted to a set of wireless receivers in the shortest amount of time—a common problem, e.g., for software updates or video multicast. In the finite horizon problem, the optimum rate critically depends on the recent reception history of the receivers and requires a fine balance between maximizing overall throughput and equalizing individual receiver throughput. We formulate a dynamic programming algorithm that optimally solves this problem. We then develop two low complexity heuristics that perform close to the optimal solution and are suitable for practical online scheduling. We further analyze the performance of our algorithms by means of simulation. They substantially outperform existing solutions based on throughput maximization or favoring the user with the worst channel, and we obtain a $30$ percent performance improvement over the former and a $120$ percent improvement over the latter in scenarios with Rayleigh fading. We further analyze the performance of the schemes under imperfect state information and observe an even higher improvement over the benchmark schemes.

1 Introduction

In recent years, multicasting data to mobile users (e.g., for the purpose of video streaming, video conferencing, IPTV, distribution of news and alerts, or application and operating system updates) has gained in importance. As an example, the most recent mobile network architecture, LTE, includes the evolved multimedia broadcast multicast service (eMBMS) specifically for the purpose of distributing data and mobile TV content in a cellular network. Since the amount of such traffic in cellular networks is increasing rapidly and wireless resources are scarce and costly, improving the efficiency of wireless multicast is of high practical relevance.