Multicast Capacity of Wireless Ad Hoc Networks

Assume that n wireless nodes are uniformly randomly deployed in a square region with side-length a and all nodes have the uniform transmission range r and uniform interference range R > r. We further assume that each wireless node can transmit (or receive) at W bits/second over a common wireless channel. For each node vi , we randomly and independently pick k-1 points pi,j (1 les j les k-1) from the square, and then multicast data to the nearest node for each pi,j. We derive matching asymptotic upper bounds and lower bounds on multicast capacity of random wireless networks. Under protocol interference model, when a ²/r ²=O(n/log(n)), we show that the total multicast capacity is Theta(radic{n/log n}middot(W/radick)) when k=O(n/log n); the total multicast capacity is Theta(W) when k=Omega(n/log n). We also study the capacity of group-multicast for wireless networks where for each source node, we randomly select k-1 groups of nodes as receivers and the nodes in each group are within a constant hops from the group leader. The same asymptotic upper bounds and lower bounds still hold. We also extend our capacity bounds to d -dimensional networks.     

Transmission capacity of wireless ad hoc networks with outage constraints

In this paper, upper and lower bounds on the transmission capacity of spread-spectrum (SS) wireless ad hoc networks are derived. We define transmission capacity as the product of the maximum density of successful transmissions multiplied by their data rate, given an outage constraint. Assuming that the nodes are randomly distributed in space according to a Poisson point process, we derive upper and lower bounds for frequency hopping (FH-CDMA) and direct sequence (DS-CDMA) SS networks, which incorporate traditional modulation types (no spreading) as a special case. These bounds cleanly summarize how ad hoc network capacity is affected by the outage probability, spreading factor, transmission power, target signal-to-noise ratio (SNR), and other system parameters. Using these bounds, it can be shown that FH-CDMA obtains a higher transmission capacity than DS-CDMA on the order of M/sup 1-2//spl alpha//, where M is the spreading factor and /spl alpha/>2 is the path loss exponent. A tangential contribution is an (apparently) novel technique for obtaining tight bounds on tail probabilities of additive functionals of homogeneous Poisson point processes.     

On the capacity of large Gaussian relay networks

The capacity of a particular large Gaussian relay network is determined in the limit as the number of relays tends to infinity. Upper bounds are derived from cut-set arguments, and lower bounds follow from an argument involving uncoded transmission. It is shown that in cases of interest, upper and lower bounds coincide in the limit as the number of relays tends to infinity. Hence, this paper provides a new example where a simple cut-set upper bound is achievable, and one more example where uncoded transmission achieves optimal performance. The findings are illustrated by geometric interpretations. The techniques developed in this paper are then applied to a sensor network situation. This is a network joint source-channel coding problem, and it is well known that the source-channel separation theorem does not extend to this case. The present paper extends this insight by providing an example where separating source from channel coding does not only lead to suboptimal performance-it leads to an exponential penalty in performance scaling behavior (as a function of the number of nodes). Finally, the techniques developed in this paper are extended to include certain models of ad hoc wireless networks, where a capacity scaling law can be established: When all nodes act purely as relays for a single source-destination pair, capacity grows with the logarithm of the number of nodes.     

On the capacity of MIMO relay channels

We study the capacity of multiple-input multiple- output (MIMO) relay channels. We first consider the Gaussian MIMO relay channel with fixed channel conditions, and derive upper bounds and lower bounds that can be obtained numerically by convex programming. We present algorithms to compute the bounds. Next, we generalize the study to the Rayleigh fading case. We find an upper bound and a lower bound on the ergodic capacity. It is somewhat surprising that the upper bound can meet the lower bound under certain regularity conditions (not necessarily degradedness), and therefore the capacity can be characterized exactly; previously this has been proven only for the degraded Gaussian relay channel. We investigate sufficient conditions for achieving the ergodic capacity; and in particular, for the case where all nodes have the same number of antennas, the capacity can be achieved under certain signal-to-noise ratio (SNR) conditions. Numerical results are also provided to illustrate the bounds on the ergodic capacity of the MIMO relay channel over Rayleigh fading. Finally, we present a potential application of the MIMO relay channel for cooperative communications in ad hoc networks.     

Impact of deployment size on the asymptotic capacity for wireless ad hoc networks under Gaussian channel model

We study the throughput capacity and transport capacity for both random and arbitrary wireless networks under Gaussian Channel model when all wireless nodes have the same constant transmission power P and the transmission rate is determined by Signal to Interference plus Noise Ratio (SINR). We consider networks with n wireless nodes \(\{v_1,v_2,\ldots,v_n\}\) (randomly or arbitrarily) distributed in a square region B _a with a side-length a. We randomly choose n _s node as the source nodes of n _s multicast sessions. For each source node v _i , we randomly select k points and the closest k nodes to these points as destination nodes of this multicast session. We derive achievable lower bounds and some upper bounds on both throughput capacity and transport capacity for both unicast sessions and multicast sessions. We found that the asymptotic capacity depends on the size a of the deployment region, and it often has three regimes.     

Bounds on the delay-constrained capacity of UWB communication with a relay node

We derive bounds on the expected capacity and outage capacity of a three-node relay network for UWB communications. We also provide a simple tight approximation for the derived upper bound on the capacity and then using this bound we obtain the outage probability of the network. Numerical results show that a significant improvement in the system capacity and outage probability is obtained by adding a relay node. Moreover, our theoretical results reveal that the diversity gain of a relay channel substantially increases by using UWB links instead of NB links. We also derive these bounds when we have a constraint on the total transmitted power of the source and the relay nodes.     

Capacity of large hybrid erasure networks with random node distribution

The Gupta–Kumar’s nearest-neighbor multihop routing with/without infrastructure support achieves the optimal capacity scaling in a large erasure network in which n wireless nodes and m relay stations are regularly placed. In this paper, a capacity scaling law is completely characterized for an infrastructure-supported erasure network where n wireless nodes are randomly distributed, which is a more feasible scenario. We use two fundamental path-loss attenuation models (i.e., exponential and polynomial power-laws) to suitably model an erasure probability. To show our achievability result, the multihop routing via percolation highway is used and the corresponding lower bounds on the total capacity scaling are derived. Cut-set upper bounds on the capacity scaling are also derived. Our result indicates that, under the random erasure network model with infrastructure support, the achievable scheme based on the percolation highway routing is order-optimal within a polylogarithmic factor of n for all values of m.     

On the path-loss attenuation regime for positive cost and linear scaling of transport capacity in wireless networks

Wireless networks with a minimum inter-node separation distance are studied where the signal attenuation grows in magnitude as 1/ρ/sup δ/ with distance ρ. Two performance measures of wireless networks are analyzed. The transport capacity is the supremum of the total distance-rate products that can be supported by the network. The energy cost of information transport is the infimum of the ratio of the transmission energies used by all the nodes to the number of bit-meters of information thereby transported. If the phases of the attenuations between node pairs are uniformly and independently distributed, it is shown that the expected transport capacity is upper-bounded by a multiple of the total of the transmission powers of all the nodes, whenever δ>2 for two-dimensional networks or δ>5/4 for one-dimensional networks, even if all the nodes have full knowledge of all the phases, i.e., full channel state information. If all nodes have an individual power constraint, the expected transport capacity grows at most linearly in the number of nodes due to the linear growth of the total power. This establishes the best case order of expected transport capacity for these ranges of path-loss exponents since linear scaling is also feasible. If the phases of the attenuations are arbitrary, it is shown that the transport capacity is upper-bounded by a multiple of the total transmission power whenever δ>5/2 for two-dimensional networks or δ>3/2 for one-dimensional networks, even if all the nodes have full channel state information. This shows that there is indeed a positive energy cost which is no less than the reciprocal of the above multiplicative constant. It narrows the transition regime where the behavior is still open, since it is known that when δ<3/2 for two-dimensional networks, or δ<1 for one-dimensional networks, the transport capacity cannot generally be bounded by any multiple of the     

Bounds on the Number of Iterations for Turbo-Like Ensembles Over the Binary Erasure Channel

This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check (LDPC) codes and variations of repeat–accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-$2$ variable nodes, the target bit erasure probability, and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-$2$ variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).      

Upper bounding service capacity in multi-hop wireless SSMA-based ad hoc networks

Upper bounds on the service carrying capacity of a multi-hop, wireless, SSMA-based ad hoc network are considered herein. The network has a single radio band for transmission and reception. Each node can transmit to, or receive from, multiple nodes simultaneously. We formulate the scheduling of transmissions and control of transmit powers as a joint, mixed-integer, nonlinear optimization problem that yields maximum return at minimum power subject to SINR constraints. We present an efficient tabu search-based heuristic algorithm to solve the optimization problem and rigorously assess the quality of the results. Through analysis and simulation, we establish upper bounds on the VoIP call carrying capacity of the network as function of various parameters. We discuss the pros and cons of using SSMA as a spectrum sharing technique in wireless ad hoc networks.     

Towards an information theory of large networks: an achievable rate region

We study communication networks of arbitrary size and topology and communicating over a general vector discrete memoryless channel (DMC). We propose an information-theoretic constructive scheme for obtaining an achievable rate region in such networks. Many well-known capacity-defining achievable rate regions can be derived as special cases of the proposed scheme. A few such examples are the physically degraded and reversely degraded relay channels, the Gaussian multiple-access channel, and the Gaussian broadcast channel. The proposed scheme also leads to inner bounds for the multicast and allcast capacities. Applying the proposed scheme to a specific wireless network of n nodes located in a region of unit area, we show that a transport capacity of /spl Theta/(n) bit-meters per second (bit-meters/s) is feasible in a certain family of networks, as compared to the best possible transport capacity of /spl Theta/(/spl radic/n) bit-meters/s in Gupta et al. (2000), where the receiver capabilities were limited. Even though the improvement is shown for a specific class of networks, a clear implication is that designing and employing more sophisticated multiuser coding schemes can provide sizable gains in at least some large wireless networks.     

Impact of traffic localization on communication rates in ad-hoc networks

The effect of traffic distribution on communication rates and receiver complexity in ad-hoc networks is addressed, considering a network with constant density of users and a certain traffic model. Information theoretic upper bounds on communication rates are derived under an assumption that transmitting nodes as well as receiving nodes cooperate. It is shown that for the case of large signal attenuation the bounds hold even when the cooperation among users is limited to a certain region of the network domain. Furthermore, achievability bounds on communication rates are derived. The bounds rely on two proposed local cooperation strategies. A comparison shows that the upper bounds are tight and closely follow the achievability results. Finally, the impact of traffic localization on the receiver complexity is addressed.     

Capacity Scaling of Wireless Networks with Inhomogeneous Node Density: Upper Bounds

We analyze the capacity scaling laws of wireless ad hoc networks comprising significant inhomogeneities in the node spatial distribution over the network area. In particular, we consider nodes placed according to a shot-noise Cox process, which allows to model the clustering behavior usually recognized in large-scale systems. For this class of networks, we introduce novel techniques to compute upper bounds to the available perflow throughput as the number of nodes tends to infinity, which are tight in the case of interference limited systems.     

Transmission capacity for inhomogeneous overlaid wireless Ad-hoc networks

In the analysis of overlaid wireless Ad-hoc networks, the underlying node distributions are commonly assumed to be two independent homogeneous Poisson point processes. In this paper, by using stochastic geometry tools, a new inhomogeneous overlaid wireless Ad-hoc network model is studied and the outage probability are analyzed. By assuming that primary （PR） network nodes are distributed as a Poisson point process （PPP） and secondary （SR） network nodes are distributed as a Matern cluster processes, an upper and a lower bounds for the transmission capacity of the primary network and that of the secondary network are presented. Simulation results show that the transmission capacity of the PR and SR network will both have a small increment due to the inhomogeneity of the SR network.     

Computing 2-terminal reliability for radio-broadcast networks

The authors present a probabilistic graph model for radio broadcast networks where nodes fail randomly and the edges are perfectly reliable. This model can represent the general case where both the nodes and edges can fail. Using this model, it is shown that the two-terminal reliability problem for radio broadcast networks is computationally difficult, in particular #P-complete, even in two important restricted cases. Efficient bounding techniques based on subgraph counts and vertex-packing methods are presented. The subgraph counting and vertex-packing bounds are the counterparts of the subgraph counting and edge-packing bounds for wired point-to-point networks with reliable nodes and unreliable links. The authors define series and parallel node reductions for arbitrary networks with unreliable nodes and reliable edges, and they incorporate these reductions into a new polynomial-time algorithm to improve the vertex-packing bounds via approximation by series-parallel reducible graphs     

大规模分簇超宽带传感网的生存期渐近界

本文考虑了n个传感节点和一个Sink组成的跳时脉冲无线电超宽带(TH-IR UWB)传感网,其中n个传感节点按照Poisson点过程分布在正方形上.推导结果表明密集分簇TH-IR UWB传感网的生存期界随着节点数的增加而增加;而扩展网络的生存期界随着节点数的增加而减小.研究也表明分簇网络的生存期界远大于非分簇网络的生存...     

On the connectivity in finite ad hoc networks

Connectivity and capacity analysis of ad hoc networks has usually focused on asymptotic results in the number of nodes in the network. In this letter we analyze finite ad hoc networks. With the standard assumption of uniform distribution of nodes in [0, z], z > 0, for a one-dimensional network, we obtain the exact formula for the probability that the network is connected. We then extend this result to find bounds for the connectivity in a two-dimensional network in [0, z]²     

The nominal capacity of wireless mesh networks

Wireless mesh networks are an alternative technology for last-mile broadband Internet access. In WMNs, similar to ad hoc networks, each user node operates not only as a host but also as a router; user packets are forwarded to and from an Internet-connected gateway in multihop fashion. The meshed topology provides good reliability, market coverage, and scalability, as well as low upfront investments. Despite the recent startup surge in WMNs, much research remains to be done before WMNs realize their full potential. This article tackles the problem of determining the exact capacity of a WMN. The key concept we introduce to enable this calculation is the bottleneck collision domain, defined as the geographical area of the network that bounds from above the amount of data that can be transmitted in the network. We show that for WMNs the throughput of each node decreases as O(1/n), where n is the total number of nodes in the network. In contrast with most existing work on ad hoc network capacity, we do not limit our study to the asymptotic case. In particular, for a given topology and the set of active nodes, we provide exact upper bounds on the throughput of any node. The calculation can be used to provision the network, to ensure quality of service and fairness. The theoretical results are validated by detailed simulations.     

The influence of QoS routing on the achievable capacity in TDMA based Ad hoc wireless networks

The issue of providing Quality of Service (QoS) guarantees in an Ad hoc wireless network is a very challenging problem. In this paper, we make the following contributions: (i) analytically derive bounds for the end-to-end call acceptance rate using existing queueing theory methods, (ii) study the impact of the routing scheme on the end-to-end call acceptance rate, and (iii) propose a differentiated services scheme for deterministically providing QoS guarantees. Unlike the existing studies which analyze the transport capacity, we focus on the end-to-end call acceptance. The framework that we assume is that of a TDMA based Ad hoc wireless network. The routing scheme employed influences the end-to-end call acceptance of the network. The metrics that we consider are the call acceptance probability and the system saturation probability (i.e., the probability that the network is in a state in which every new call is rejected). We derive general bounds on the call acceptance and the system saturation for the case of differentiated-classes of users in the network. These bounds indicate the number of calls of the highest priority class that can be admitted into the network. Simulation studies were carried out to study the effect of load, hopcount, and the influence of the routing protocol on the call acceptance. The increase in the call acceptance rate with the introduction of load-balancing highlights the importance of load-balancing in enhancing the system performance. From these studies, we arrive at the following results: (i) load-balancing leads to significant improvement in the end-to-end call acceptance rate, and is an important factor in attaining the maximum end-to-end call acceptance rate in a given network and (ii) it is indeed possible to provide deterministic QoS guarantees for a designated set of nodes which are characterized by “deterministic guarantee limit”.     

Rate Regions for Relay Broadcast Channels

A partially cooperative relay broadcast channel (RBC) is a three-node network with one source node and two destination nodes (destinations 1 and 2) where destination 1 can act as a relay to assist destination 2. Inner and outer bounds on the capacity region of the discrete memoryless partially cooperative RBC are obtained. When the relay function is disabled, the inner bound reduces to an inner bound on the capacity region of broadcast channels that includes an inner bound of Marton, and GePfand and Pinsker. The outer bound reduces to a new outer bound on the capacity region of broadcast channels that generalizes an outer bound of Marton to include a common message, and that generalizes an outer bound of GePfand and Pinsker to apply to general discrete memoryless broadcast channels. The proof for the outer bound simplifies the proof of GePfand and Pinsker that was based on a recursive approach. Four classes of RBCs are studied in detail. For the partially cooperative RBC with degraded message sets, inner and outer bounds are obtained. For the semideterministic partially cooperative RBC and the orthogonal partially cooperative RBC, the capacity regions are established. For the parallel partially cooperative RBC with unmatched degraded subchannels, the capacity region is established for the case of degraded message sets. The capacity is also established when the source node has only a private message for destination 2, i.e., the channel reduces to a parallel relay channel with unmatched degraded subchannels.