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_11: Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node sends a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc networks. Our objective is to minimize the latency and the number of transmissions in the broadcast. We show that minimum latency broadcasting is NP-complete for ad hoc networks. We also present a simple distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of transmissions are within O(1) times their re spective optimal values. Our algorithm and analysis extend to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithms perform much better in practice than the analytical guarantees provided for the worst case.
@cite_7: Cooperative broadcast aims to deliver a source message to a locally connected network by means of collaborating nodes. In traditional architectures, node cooperation has been at the network layer. Recently, physical layer cooperative schemes have been shown to offer several advantages over the network layer approaches. This form of cooperation employs distributed transmission resources at the physical layer as a single radio with spatial diversity. In decentralized cooperation schemes, collaborating nodes make transmission decisions based on the quality of the received signal, which is the only parameter available locally. In this case, critical parameters that influence the broadcast performance include the source relay transmission powers and the decoding threshold (the minimum signal-to-noise ratio (SNR) required to decode a transmission). We study the effect of these parameters on the number of nodes reached by cooperative broadcast. In particular, we show that there exists a phase transition in the network behavior: if the decoding threshold is below a critical value, the message is delivered to the whole network. Otherwise, only a fraction of the nodes is reached, which is proportional to the source transmit power. Our approach is based on the idea of continuum approximation, which yields closed-form expressions that are accurate when the network density is high.
@cite_44: Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set, domination, independent domination, and connected domination; NP-completeness for the domination problem is shown to hold even for grid graphs, a subclass of unit disk graphs. In contrast, we give a polynomial time algorithm for finding cliques when the geometric representation (circles in the plane) is provided.
@cite_24: This paper presents Glossy, a novel flooding architecture for wireless sensor networks. Glossy exploits constructive interference of IEEE 802.15.4 symbols for fast network flooding and implicit time synchronization. We derive a timing requirement to make concurrent transmissions of the same packet interfere constructively, allowing a receiver to decode the packet even in the absence of capture effects. To satisfy this requirement, our design temporally decouples flooding from other network activities. We analyze Glossy using a mixture of statistical and worst-case models, and evaluate it through experiments under controlled settings and on three wireless sensor testbeds. Our results show that Glossy floods packets within a few milliseconds and achieves an average time synchronization error below one microsecond. In most cases, a node receives the flooding packet with a probability higher than 99.99 , while having its radio turned on for only a few milliseconds during a flood. Moreover, unlike existing flooding schemes, Glossy's performance exhibits no noticeable dependency on node density, which facilitates its application in diverse real-world settings.
@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.
Broadcasting algorithms have been widely optimized for speed, throughput, and energy consumption. A lot of algorithms apply MAC (medium access control) protocols like TDMA (Time Division Multiple Access) @cite_44 @cite_11 @cite_17 @cite_2 , CDMA (Code Division Multiple Access) @cite_24 @cite_7 , FDMA (Frequency Division Multiple Access) @cite_7 to increase spatial reuse. Physical models with high path loss exponent @math are beneficial here and increase the spatial reuse with only local interference. With spatial reuse, parallel point-to-point communications are possible which either spread the same broadcast message in the network or pipeline multiple broadcast messages at the same time. The latter can achieve a constant broadcasting rate for path loss exponent @math . Cooperative transmission with MISO (Multiple Input Single Output) is applied to increase the transmission range and broadcast speed by a constant factor (where underlying MAC protocols still work).