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_2: The physical (or SINR) model of wireless communication is more intricate than radio networks and still not well understood. If two neighbors of a node are transmitting, the node may be able to decode one of the transmissions, depending on the relative nearness of the transmitters. Thus, even the lack of proper reception carries indirect information. We explore here the power of such indirect signaling to infer the approximate topology of the network. In particular, we obtain a polylogarithmic time algorithm to compute a backbone: a set of nodes of constant density that dominates every e-neighborhood. A backbone has wide utility for information dissemination, functioning as a sparse spanner. It also leads to fast broadcast, running in O(Diameter) time after a polylogarithmic precomputation, which previously was only known when additional features such as carrier sense, collision detection, geometric coordinates, or power control were available.
@cite_17: Modeling communications in wireless networks is a challenging task, since it requires a simple mathematical object on which efficient algorithms can be designed but which must also reflect the complex physical constraints inherent in wireless networks, such as interferences, the lack of global knowledge, and purely local computations. As a tractable mathematical object, the unit disk graph (UDG) is a popular model that has enabled the development of efficient algorithms for crucial networking problems. In a ρ-UDG, two nodes are connected if and only if their distance is at most ρ, for some ρ ≪ 0. However, such a connectivity requirement is basically not compatible with the reality of wireless networks due to the environment of the nodes as well as the constraints of radio transmission. For this purpose, the signal interference plus noise ratio model (SINR) is the more commonly used model. The SINR model focuses on radio interferences created over the network depending on the distance to transmitters. Nevertheless, due to its complexity, this latter model has been the subject of very few theoretical investigations and lacks of good algorithmic features. In this paper, we demonstrate how careful scheduling of the nodes enables the two models to be combined to give the benefits of both the algorithmic features of the UDG and the physical validity of the SINR. Precisely, we show that it is possible to emulate a 1 √n ln n-UDG that satisfies the constraints of the SINR over any set of n wireless nodes distributed uniformly in a unit square, with only a O(ln3 n) time and power stretch factor. The main strength of our contribution lies in the fact that the scheduling is set in a fully distributed way and considers non-uniform power ranges, and it can therefore fit the sensor network setting. Moreover, our scheduling is optimal up to a polylogarithmic factor in terms of throughput capacity according to the lower bound of Gupta and Kumar.
When the energy of each sender is constrained, in @cite_17 it is shown that the SNR-model does not give much improvement compared to the UDG-model. So, @cite_17 incorporates the unit disk model with the SINR (Signal to Interference and Noise) model. The focus are TDMA scheduling schemes to enhance the network capacity. The path-loss exponent in the SINR model is chosen with @math and interference has only local effects for unsynchronized transmitters. In this context, the SNR model is used for each sender separately. So, the problem of broadcast mainly reduces to range assignment and scheduling problem, for which the number of rounds approaches the diameter @cite_2 .