We consider the multihop broadcasting problem for @math nodes placed uniformly at random in a disk and investigate the number of hops required to transmit a signal from the central node to all other nodes under three communication models: Unit-Disk-Graph (UDG), Signal-to-Noise-Ratio (SNR), and the wave superposition model of multiple input single output (MISO). In the MISO model, informed nodes cooperate to produce a stronger superposed signal. We do not consider the problem of transmitting a full message nor do we consider interference. In each round, the informed senders try to deliver to other nodes the required signal strength such that the received signal can be distinguished from the noise. We assume sufficiently high node density @math . In the unit-disk graph model, broadcasting needs @math rounds. In the other models, we use an Expanding Disk Broadcasting Algorithm, where in a round only triggered nodes within a certain distance from the initiator node contribute to the broadcasting operation. This algorithm achieves a broadcast in only @math rounds in the SNR-model. Adapted to the MISO model, it broadcasts within @math rounds. All bounds are asymptotically tight and hold with high probability, i.e. @math .
@cite_16: 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.
The authors of @cite_16 consider a system model similar to our work. They use two phase opportunistic broadcasting to achieve linear increase in propagation distance. In Phase 1, nodes inside a disk of specific radius broadcast message with different random phases while in Phase 2, a node broadcasts the message to its neighboring nodes. These phases are performed repeatedly to broadcast the message. Improving on this work we obtain better bounds by coordinating the phase of the nodes, while we consider only the path loss factor of @math .