Two-Phase Opportunistic Broadcasting in Large Wireless Networks

We study how fast a broadcast message can be propagated through large wireless networks. A two-phase opportunistic broadcasting is proposed in this paper. At the first phase, all nodes having the message broadcast it simultaneously with random phases, which gives a chance for remote nodes to receive the message through opportunistic beamforming. At the second phase, each node having the message transmits it to its neighbor nodes. By performing this two phases repeatedly, the message propagates through the network. It is shown that the two- phase opportunistic broadcasting achieves a linear increase of the propagation distance. By comparing it with an upper-bound, we show it is asymptotically order optimal in the high attenuation regime. Furthermore, our scheme can have a potentially huge gain compared to naive multihop broadcasting.