The Capacity of Wireless Networks: Information-Theoretic and Physical Limits

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.     

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.     

Scalability and Performance Evaluation of Hierarchical Hybrid Wireless Networks

This paper considers the problem of scaling ad hoc wireless networks now being applied to urban mesh and sensor network scenarios. Previous results have shown that the inherent scaling problems of a multihop ldquoflatrdquo ad hoc wireless network can be improved by a ldquohybrid networkrdquo with an appropriate proportion of radio nodes with wired network connections. In this work, we generalize the system model to a hierarchical hybrid wireless network with three tiers of radio nodes: low-power end-user mobile nodes (MNs) at the lowest tier, higher power radio forwarding nodes (FNs) that support multihop routing at intermediate level, and wired access points (APs) at the highest level. Scalability properties of the proposed three-tier hierarchical hybrid wireless network are analyzed, leading to an identification of the proportion of FNs and APs as well as transmission range required for linear increase in end-user throughput. In particular, it is shown analytically that in a three-tier hierarchical network with nA APs, nF FNs, and nM MNs, the low-tier capacity increases linearly with nF, and the high-tier capacity increases linearly with nA when nA = Omega(radic{nF}) and n _A = O(nF). This analytical result is validated via ns-2 simulations for an example dense network scenario, and the model is used to study scaling behavior and performance as a function of key parameters such as AP and FN node densities for different traffic patterns and bandwidth allocation at each tier of the network.     

Hierarchical Cooperation in Ad Hoc Networks: Optimal Clustering and Achievable Throughput

For a wireless network with n nodes distributed in an area A, and with n source-destination pairs communicating with each other at some common rate, the hierarchical cooperation scheme proposed in (Ozgur, Leveque, and Tse, 2007) is analyzed and optimized by choosing the number of hierarchical stages and the corresponding cluster sizes that maximize the total throughput. It turns out that increasing the number of stages does not necessarily improve the throughput, and the closed-form solutions for the optimization problem can be explicitly obtained. Based on the expression of the maximum achievable throughput, it is found that the hierarchical scheme achieves a scaling with the exponent depending on n . In addition, to apply the hierarchical cooperation scheme to random networks, a clustering algorithm is developed, which divides the whole network into quadrilateral clusters, each with exactly the number of nodes required.     

User Capacity Scaling Laws of Multi-user Fading Channels in the Presence of MMSE Channel Estimators

Considering development of delay-sensitive applications in wireless communications and cellular networks along with lack of system resources and environmental factors including fading and noise all together make it impossible for all users to be active and to achieve quality of service requirements simultaneously. To analyze wireless systems performance, user capacity is defined as the maximum number of users that can be activated at the same time. In order to obtain user capacity scaling laws, channel distribution information is required and channel gains can be estimated by different channel estimators such as minimum mean square error estimators. In this paper, estimated channel gains are substituted for true channel gains and effects of imperfect channel estimation errors on the user capacity scaling laws are analyzed. It is shown that the user capacity scales double logarithmically and there is a gap depending on channel estimators accuracy between the lower and upper bounds. Moreover, assuming estimated channels for different users are independent and identically distributed, it is shown that the user capacity scaling laws are asymptotically tight.     

Unreliable sensor grids: coverage, connectivity and diameter

We consider an unreliable wireless sensor grid network with n nodes placed in a square of unit area. We are interested in the coverage of the region and the connectivity of the network. We first show that the necessary and sufficient conditions for the random grid network to cover the unit square region as well as ensure that the active nodes are connected are of the form p(n)r²(n)  log(n)/n, where r(n) is the transmission radius of each node and p(n) is the probability that a node is “active” (not failed). This result indicates that, when n is large, even if each node is highly unreliable and the transmission power is small, we can still maintain connectivity with coverage.

We also show that the diameter of the random grid (i.e., the maximum number of hops required to travel from any active node to another) is of the order . Finally, we derive a sufficient condition for connectivity of the active nodes (without necessarily having coverage). If the node success probability p(n) is small enough, we show that connectivity does not imply coverage.     

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.     

Capacity of Multichannel Wireless Networks Under the Protocol Model

This paper studies the capacity of a n node static wireless network with c channels and m radio interfaces per node under the protocol model of interference. In their seminal work, Gupta and Kumar have determined the capacity of a single channel network (c=1, m=1). Their results are also applicable to multichannel networks provided each node has one interface per channel (m=c) . However, in practice, it is often infeasible to equip each node with one interface per channel. Motivated by this observation, we establish the capacity of general multichannel networks (m les c). Equipping each node with fewer interfaces than channels in general reduces network capacity. However, we show that one important exception is a random network with up to O(logn) channels, where there is no capacity degradation even if each node has only one interface. Our initial analysis assumes that the interfaces are capable of switching channels instantaneously, but we later extend our analysis to account for interface switching delays seen in practice. Furthermore, some multichannel protocols proposed so far rarely require interfaces to switch, and therefore, we briefly study the capacity with fixed interfaces as well.     

On capacity of random wireless networks with physical-layer network coding

Throughput capacity of a random wireless network has been studied extensively in the literature. Most existing studies were based on the assumption that each transmission involves only one transmitter in order to avoid interference. However, recent studies on physical-layer network coding (PLNC) have shown that such an assumption can be relaxed to improve throughput performance of a wireless network. In PLNC, signals from different senders can be transmitted to the same receiver in the same channel simultaneously. In this paper, we investigate the impact of PLNC on throughput capacity of a random wireless network. Our study reveals that, although PLNC scheme does not change the scaling law, it can improve throughput capacity by a fixed factor. Specifically, for a one-dimensional network, we observe that PLNC can eliminate the effect of interference in some scenarios. A tighter capacity bound is derived for a two-dimensional network. In addition, we also show achievable lower bounds for random wireless networks with network coding and PLNC.     

Optimal Unicast Capacity of Random Geometric Graphs: Impact of Multipacket Transmission and Reception

We establish a tight max-flow min-cut theorem for multi-commodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to infinity, the maximum concurrent flow (MCF) and the minimum cut-sparsity scale as θ(n²r³(n)/k), for a random choice of k = ω(n) source-destination pairs, where n and r(n) are the number of nodes and the communication range in the network respectively. The MCF equals the interference-free capacity of an ad-hoc network. We exploit this fact to develop novel graph theoretic techniques that can be used to deduce tight order bounds on the capacity of ad-hoc networks. We generalize all existing capacity results reported to date by showing that the per-commodity capacity of the network scales as θ(1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as θ(nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of (perfect) multiple-packet transmission (MPT) and reception (MPR), then it is feasible to achieve the optimal scaling of θ(n²r³(n)/k), despite the presence of interference. In comparison to the Gupta-Kumar model, the realization of MPT and MPR may require the deployment of a large number of antennas at each node or bandwidth expansion. Nevertheless, in stark contrast to the existing literature, our analysis presents the possibility of actually increasing the capacity of ad-hoc networks with n even while the communication range tends to zero!     

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.     

Sequence-Based Localization in Wireless Sensor Networks

We introduce a novel sequence-based localization technique for wireless sensor networks. We show that the localization space can be divided into distinct regions that can each be uniquely identified by sequences that represent the ranking of distances from the reference nodes to that region. For n reference nodes in the localization space, combinatorially, O(n") sequences are possible, but we show that, due to geometric constraints, the actual number of feasible location sequences is much lower: only O(n ⁴). Using these location sequences, we develop a localization technique that is robust to random errors due to the multipath and shadowing effects of wireless channels. Through extensive systematic simulations and a representative set of real mote experiments, we show that our lightweight localization technique provides comparable or better accuracy than other state-of-the-art radio signal strength-based localization techniques over a range of wireless channel and node deployment conditions.     

Capacity Bounds for MIMO Nakagami- $m$ Fading Channels

This paper studies the ergodic capacity limits of multiple-input multiple-output (MIMO) antenna systems with arbitrary finite number of antennas operating on general fading environments. Through the use of majorization theory, we first investigate in detail the ergodic capacity of Nakagami- $m$ fading channels, for which we derive several ergodic capacity upper and lower bounds. We then show that a simple expression for the capacity upper bound is possible for high signal-to-noise ratio (SNR), which permits to analyze the impact of the channel fading parameter $m$ on the ergodic capacity. The asymptotic behavior of the capacity in the large-system limit in which the number of antennas at one or both side(s) goes to infinity, is also addressed. Results demonstrate that the capacity scaling laws for Nakagami-$m$ and Rayleigh-fading MIMO channels are identical. Finally, we employ the same technique to distributed MIMO (D-MIMO) systems undergoing composite log-normal and Nakagami fading, where we derive similar ergodic capacity upper and lower bounds. Monte Carlo simulation results are provided to verify the tightness of the proposed bounds.      

Queuing network models for delay analysis of multihop wireless ad hoc networks

In this paper we analyze the average end-to-end delay and maximum achievable per-node throughput in random access multihop wireless ad hoc networks with stationary nodes. We present an analytical model that takes into account the number of nodes, the random packet arrival process, the extent of locality of traffic, and the back off and collision avoidance mechanisms of random access MAC. We model random access multihop wireless networks as open G/G/1 queuing networks and use the diffusion approximation in order to evaluate closed form expressions for the average end-to-end delay. The mean service time of nodes is evaluated and used to obtain the maximum achievable per-node throughput. The analytical results obtained here from the queuing network analysis are discussed with regard to similarities and differences from the well established information-theoretic results on throughput and delay scaling laws in ad hoc networks. We also investigate the extent of deviation of delay and throughput in a real world network from the analytical results presented in this paper. We conduct extensive simulations in order to verify the analytical results and also compare them against NS-2 simulations.     

On the capacity of network coding for random networks

We study the maximum flow possible between a single-source and multiple terminals in a weighted random graph (modeling a wired network) and a weighted random geometric graph (modeling an ad-hoc wireless network) using network coding. For the weighted random graph model, we show that the network coding capacity concentrates around the expected number of nearest neighbors of the source and the terminals. Specifically, for a network with a single source, l terminals, and n relay nodes such that the link capacities between any two nodes is independent and identically distributed (i.i.d.) /spl sim/X, the maximum flow between the source and the terminals is approximately nE[X] with high probability. For the weighted random geometric graph model where two nodes are connected if they are within a certain distance of each other we show that with high probability the network coding capacity is greater than or equal to the expected number of nearest neighbors of the node with the least coverage area.     

Scaling Laws for One- and Two-Dimensional Random Wireless Networks in the Low-Attenuation Regime

The capacity scaling of extended two-dimensional wireless networks is known in the high-attenuation regime, i.e., when the power path loss exponent alpha is greater than 4. This has been accomplished by deriving information-theoretic upper bounds for this regime that match the corresponding lower bounds. On the contrary, not much is known in the so-called low-attenuation regime when 2lesalphales4. (For one-dimensional networks, the uncharacterized regime is 1lesalphales2.5.) The dichotomy is due to the fact that while communication is highly power-limited in the first case and power-based arguments suffice to get tight upper bounds, the study of the low-attenuation regime requires a more precise analysis of the degrees of freedom involved. In this paper, we study the capacity scaling of extended wireless networks with an emphasis on the low-attenuation regime and show that in the absence of small scale fading, the low attenuation regime does not behave significantly different from the high attenuation regime.     

保护区域对无线Ad Hoc网络空间进度密度的影响

研究无线Ad Hoc网络容量的文章中,往往不会考虑如何抑制干扰信号功率,使得网络容量的提高受到很大限制。文章使用随机几何对无线Ad Hoc网络进行建模,研究空间进度密度这一容量定义,提出在无线Ad Hoc网络中通过设置保护区域的方式来抑制干扰信号功率,推导了网络的空间进度密度的近似值、上下界和最优保护区域半径等的理论表达式。理论分析与仿真结果说明,中断概率和空间进度密度的近似值和上下界能够很好的逼近仿真值;设置保护区域能够降低无线Ad Hoc网络中的干扰信号功率,提高空间进度密度。     

Analysis of the effects of time delay spread on TCM performance

We investigate the effect of time delay spread on trellis coded modulation (TCM) in a wireless radio environment where equalization is not employed to mitigate the effects of frequency selective fading when the time delay spread is small. Using a random variable decomposition technique and a Gaussian approximation of the intersymbol interference terms, we obtain explicit bounds for the pairwise error probability of TCM over multipath Rayleigh fading channels characterized by various power delay profiles. A method to calculate an upper bound of the bit error rate (BER) based on Jamali and LeNgoc (1995) bound is also presented. These bounds are used to evaluate TCM performance as well as investigate the delay spread tolerance limit of TCM, including I-Q TCM, over frequency selective fading channels     

Bounds on the throughput gain of network coding in unicast and multicast wireless networks

Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales with an increasing number of nodes n as lambda(n) = ominus(1/radic(n log n)), thus indicating that performance does not scale well. However, Gupta and Kumar did not consider network coding and wireless broadcasting, which recent works suggest have the potential to significantly improve throughput. Here, we establish bounds on the improvement provided by such techniques. For random networks of any dimension under either the protocol or physical model that were introduced by Gupta and Kumar, we show that network coding and broadcasting lead to at most a constant factor improvement in per node throughput. For the protocol model, we provide bounds on this factor. We also establish bounds on the throughput benefit of network coding and broadcasting for multiple source multicast in random networks. Finally, for an arbitrary network deployment, we show that the coding benefit ratio is at most O(log n) for both the protocol and physical communication models. These results give guidance on the application space of network coding, and, more generally, indicate the difficulty in improving the scaling behavior of wireless networks without modification of the physical layer.     

无线自组织网络极限信道容量增长规律研究

 为了分析和提高无线自组织网络的吞吐能力,提出了无线自组织网络的极限信道容量增长规律(capacity scaling laws)的一般表达式,研究发现单个节点的策略决定了整个无线自组织网络的吞吐能力,证明了使得整个网络吞吐能力最大化的最优策略的存在性。进一步通过应用博弈论,推导得出最优策略,并验证其满足纳什均衡且是演化稳定策略。