Latency-optimized broadcast in mobile ad hoc networks without node coordination

We consider the problem of broadcasting a message in a mobile ad hoc network (MANET) with the objective of minimizing the broadcast latency. Due to the mobility of network nodes, the coordination among nodes is hard and expensive. Thus it is much desired to design efficient, one-sided broadcast protocols where each node acts according to its own state solely. Although random scheduling is a popular and effective one-sided approach for leveraging the broadcast nature of wireless medium while coping with transmission collisions, both critical for reducing the broadcast latency, in this paper, we show that when nodes move very fast, the performance of pure random scheduling must be sub-optimal, no matter how the forwarding probabilities are specified. Furthermore, we propose a novel one-sided broadcast protocol named R2, which first splits the message into a certain number of mini-messages and then couples a fine-grained random scheduling with random linear network coding for broadcasting the mini-messages. Theoretical analyses demonstrate that R2 performs optimally in order sense, no matter how fast network nodes move around, although different mobility has distinct effect on the speed of message broadcast.