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_38: Unlike wired networks, wireless networks do not come with links. Rather, links have to be fashioned out of the ether by nodes choosing neighbors to connect to. Moreover the location of the nodes may be random.The question that we resolve is: How many neighbors should each node be connected to in order that the overall network is connected in a multi-hop fashion? We show that in a network with n randomly placed nodes, each node should be connected to Θ(log n) nearest neighbors. If each node is connected to less than 0.074 log n nearest neighbors then the network is asymptotically disconnected with probability one as n increases, while if each node is connected to more than 5.1774 log n nearest neighbors then the network is asymptotically connected with probability approaching one as n increases. It appears that the critical constant may be close to one, but that remains an open problem.These results should be contrasted with some works in the 1970s and 1980s which suggested that the "magic number" of nearest neighbors should be six or eight.
@cite_40: Broadcasting is a basic network communication task, where a message initially held by a source node has to be disseminated to all other nodes in the network. Fast algorithms for broadcasting in radio networks have been studied in a wide variety of different models and under different requirements. Some of the main parameters giving rise to the different variants of the problem are the accessibility of knowledge about the network topology, the availability of collision detection mechanisms, the wake-up mode, the topology classes considered, and the use of randomness. The paper reviews the literature on time-efficient broadcasting algorithms for radio networks under a variety of models and assumptions.
@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.
Broadcasting has been first considered for a graph based model, where interference prevents communication and a choice has to be made which link should be used for propagation. Since we do not consider interference and allow the usage of all links a simple flooding algorithm achieves the optimal bound of the diameter of the network. So, these works (see @cite_40 for a survey) do not apply here. However, even if interference is considered there is only a constant factor slow down in the Unit-Disk-Graph model @cite_11 . Note that Unit-Disk-Graphs are connected, when the node density of the randomly placed nodes is large enough @cite_38 .