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_36: In recent work, Ozgur, Leveque, and Tse (2007) obtained a complete scaling characterization of throughput scaling for random extended wireless networks (i.e., n nodes are placed uniformly at random in a square region of area n). They showed that for small path-loss exponents alpha isin (2,3], cooperative communication is order optimal, and for large path-loss exponents alpha > 3, multihop communication is order optimal. However, their results (both the communication scheme and the proof technique) are strongly dependent on the regularity induced with high probability by the random node placement. In this paper, we consider the problem of characterizing the throughput scaling in extended wireless networks with arbitrary node placement. As a main result, we propose a more general novel cooperative communication scheme that works for arbitrarily placed nodes. For small path-loss exponents alpha isin (2,3], we show that our scheme is order optimal for all node placements, and achieves exactly the same throughput scaling as in Ozgur. This shows that the regularity of the node placement does not affect the scaling of the achievable rates for alpha isin (2,3]. The situation is, however, markedly different for large path-loss exponents alpha > 3. We show that in this regime the scaling of the achievable per-node rates depends crucially on the regularity of the node placement. We then present a family of schemes that smoothly ldquointerpolaterdquo between multihop and cooperative communication, depending upon the level of regularity in the node placement. We establish order optimality of these schemes under adversarial node placement for alpha > 3.
@cite_20: It is shown that the capacity scaling of wireless networks is subject to a fundamental limitation which is independent of power attenuation and fading models. It is a degrees of freedom limitation which is due to the laws of physics. By distributing uniformly an order of n users wishing to establish pairwise independent communications at fixed wavelength inside a two-dimensional domain of size of the order of n, there are an order of n communication requests originating from the central half of the domain to its outer half. Physics dictates that the number of independent information channels across these two regions is only of the order of radicn, so the per-user information capacity must follow an inverse square-root of n law. This result shows that information-theoretic limits of wireless communication problems can be rigorously obtained without relying on stochastic fading channel models, but studying their physical geometric structure.
@cite_22: We consider a large distributed MIMO system where wireless users with single transmit and receive antenna cooperate in clusters to form distributed transmit and receive antenna arrays. We characterize how the capacity of the distributed MIMO transmission scales with the number of cooperating users, the area of the clusters and the separation between them, in a line-of-sight propagation environment. We use this result to answer the following question: can distributed MIMO provide significant capacity gain over traditional multi-hop in large ad hoc networks with n source-destination pairs randomly distributed over an area A? Two diametrically opposite answers [24] and [26] have emerged in the current literature. We show that neither of these two results are universal and their validity depends on V the relation between the number of users n and √A λ, which we identify as the spatial degrees of freedom in the network. λ is the carrier wavelength. When √A λ ≥ n, there are n degrees of freedom in the network and distributed MIMO with hierarchical cooperation can achieve a capacity scaling linearly in n as in [24], while capacity of multihop scales only as √n. On the other hand, when √A λ ≤ √n as in [26], there are only √n degrees of freedom in the network and they can be readily achieved by multihop. Our results also reveal a third regime where √n ≤ √A λ ≤ n. Here, the number of degrees of freedom are smaller than n but larger than what can be achieved by multi-hop. We construct scaling optimal architectures for this intermediate regime.
@cite_6: n source and destination pairs randomly located in an area want to communicate with each other. Signals transmitted from one user to another at distance r apart are subject to a power loss of r-alpha as well as a random phase. We identify the scaling laws of the information-theoretic capacity of the network when nodes can relay information for each other. In the case of dense networks, where the area is fixed and the density of nodes increasing, we show that the total capacity of the network scales linearly with n. This improves on the best known achievability result of n2 3 of Aeron and Saligrama. In the case of extended networks, where the density of nodes is fixed and the area increasing linearly with n, we show that this capacity scales as n2-alpha 2 for 2lesalpha 4. Thus, much better scaling than multihop can be achieved in dense networks, as well as in extended networks with low attenuation. The performance gain is achieved by intelligent node cooperation and distributed multiple-input multiple-output (MIMO) communication. The key ingredient is a hierarchical and digital architecture for nodal exchange of information for realizing the cooperation.
For the MIMO model in @cite_6 and @cite_36 the authors give a recursive construction, which allows a capacity of @math for @math senders using MIMO communication. However, in @cite_20 , an upper bound of @math has been proved. This seeming contradiction has been addressed in @cite_22 , where they address the question whether distributed MIMO provides significant capacity gain over traditional multi-hop in large ad hoc networks with @math source-destination pairs randomly distributed over an area A. It turns out that the capacity depends on the ratio @math , it describes the spatial degree of freedom. If it is larger than @math it allows @math degrees of freedom @cite_6 , if it is less than @math the bound of @cite_20 holds. For all regimes optimal constructions are provided in these papers. While in @cite_6 path loss exponents @math are considered, for @math the regularity of the node placement must be taken into account @cite_36 .