Scheduling algorithms and bounds for rateless data dissemination in dense wireless networks

Many applications in wireless cellular networks rely on the ability of the network to reliably and efficiently disseminate data to a large client audience. The stochastic nature of packet loss across receivers and channel interference constraints between cells complicate this task, however. In this paper, we analyze the problem of minimizing the delay of data dissemination in dense multi-channel wireless cellular networks, using rateless coding transmission. We begin with an extreme value analysis of the delay in a single cell setting, and show that the growth rate of this random variable becomes deterministic as the client audience scales up. Next, we extend the analysis to multi-cell, multi-channel settings and derive tight performance bounds on the delay. Our analysis reveals that the availability of more channels does not always reduce delay proportionally. This sub-linear gain effect is guaranteed to occur if the difference between the chromatic number and the fractional chromatic number of the graph is greater than one.