Capacity of interference-limited ad hoc networks with infrastructure support

In this letter, we consider the capacity of ad hoc networks with infrastructure support. Although Grossglauser-Tse mobile network model enables /spl Theta/(1) per-node throughput scaling, the mobility assumption may be too unrealistic to be accepted in some practical situations. One of the key observations we acquired is that the infrastructure support plays the same role played by the mobility in the Grossglauser-Tse model. We show that nodes can utilize the randomly located infrastructure support instead of mobility when nodes are nearly static. In this case, we show that the per-node throughput of /spl Theta/(1) is still achievable when the number of access points grows linearly with respect to the number of nodes.     

Throughput and Delay in Random Wireless Networks With Restricted Mobility

Grossglauser and Tse (2001) introduced a mobile random network model where each node moves independently on a unit disk according to a stationary uniform distribution and showed that a throughput of Theta(1) is achievable. El Gamal, Mammen, Prabhakar, and Shah (2004) showed that the delay associated with this throughput scales as Theta(nlogn), when each node moves according to an independent random walk. In a later work, Diggavi, Grossglauser, and Tse (2002) considered a random network on a sphere with a restricted mobility model, where each node moves along a randomly chosen great circle on the unit sphere. They showed that even with this one-dimensional restriction on mobility, constant throughput scaling is achievable. Thus, this particular mobility restriction does not affect the throughput scaling. This raises the question whether this mobility restriction affects the delay scaling. This correspondence studies the delay scaling at Theta(1) throughput for a random network with restricted mobility. First, a variant of the scheme presented by Diggavi, Grossglauser, and Tse (2002) is presented and it is shown to achieve Theta(1) throughput using different (and perhaps simpler) techniques. The exact order of delay scaling for this scheme is determined, somewhat surprisingly, to be of Theta(nlogn), which is the same as that without the mobility restriction. Thus, this particular mobility restriction does not affect either the maximal throughput scaling or the corresponding delay scaling of the network. This happens because under this 1-D restriction, each node is in the proximity of every other node in essentially the same manner as without this restriction     

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.     

Capacity of ad hoc wireless networks with infrastructure support

We determine the asymptotic scaling for the per user throughput in a large hybrid ad hoc network, i.e., a network with both ad hoc nodes, which communicate with each other via shared wireless links of capacity W bits/s, and infrastructure nodes which in addition are interconnected with each other via high capacity links. Specifically, we consider a network model where ad hoc nodes are randomly spatially distributed and choose to communicate with a random destination. We identify three scaling regimes, depending on the growth of the number of infrastructure nodes, m relative to the number of ad hoc nodes n, and show the asymptotic scaling for the per user throughput as n becomes large. We show that when m /spl lsim/ /spl radic/n/logn the per user throughput is of order W//spl radic/n log n and could be realized by allowing only ad hoc communications, i.e., not deploying the infrastructure nodes at all. Whenever /spl radic/n/log n /spl lsim/ m /spl lsim/ n/log n, the order for the per user throughput is Wm/n and, thus, the total additional bandwidth provided by m infrastructure nodes is effectively shared among ad hoc nodes. Finally, whenever m /spl gsim/ n/log n, the order of the per user throughput is only W/log n, suggesting that further investments in infrastructure nodes will not lead to improvement in throughput. The results are shown through an upper bound which is independent of the routing strategy, and by constructing scenarios showing that the upper bound is asymptotically tight.     

A deterministic approach to throughput scaling in wireless networks

We address the problem of how throughput in a wireless network scales as the number of users grows. Following the model of Gupta and Kumar, we consider n identical nodes placed in a fixed area. Pairs of transmitters and receivers wish to communicate but are subject to interference from other nodes. Throughput is measured in bit-meters per second. We provide a very elementary deterministic approach that gives achievability results in terms of three key properties of the node locations. As a special case, we obtain /spl Omega/(/spl radic/n) throughput for a general class of network configurations in a fixed area. Results for random node locations in a fixed area can also be derived as special cases of the general result by verifying the growth rate of three parameters. For example, as a simple corollary of our result we obtain a stronger (almost sure) version of the /spl radic/n//spl radic/(logn) throughput for random node locations in a fixed area obtained by Gupta and Kumar. Results for some other interesting non-independent and identically distributed (i.i.d.) node distributions are also provided.     

Capacity and delay tradeoffs for ad hoc mobile networks

We consider the throughput/delay tradeoffs for scheduling data transmissions in a mobile ad hoc network. To reduce delays in the network, each user sends redundant packets along multiple paths to the destination. Assuming the network has a cell partitioned structure and users move according to a simplified independent and identically distributed (i.i.d.) mobility model, we compute the exact network capacity and the exact end-to-end queueing delay when no redundancy is used. The capacity-achieving algorithm is a modified version of the Grossglauser-Tse two-hop relay algorithm and provides O(N) delay (where N is the number of users). We then show that redundancy cannot increase capacity, but can significantly improve delay. The following necessary tradeoff is established: delay/rate/spl ges/O(N). Two protocols that use redundancy and operate near the boundary of this curve are developed, with delays of O(/spl radic/N) and O(log(N)), respectively. Networks with non-i.i.d. mobility are also considered and shown through simulation to closely match the performance of i.i.d. systems in the O(/spl radic/N) delay regime.     

Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with Bernoulli nodes

Nodes in wireless ad hoc networks may become inactive or unavailable due to, for example, internal breakdown or being in the sleeping state. The inactive nodes cannot take part in routing/relaying, and thus may affect the connectivity. A wireless ad hoc network containing inactive nodes is then said to be connected, if each inactive node is adjacent to at least one active node and all active nodes form a connected network. This paper is the first installment of our probabilistic study of the connectivity of wireless ad hoc networks containing inactive nodes. We assume that the wireless ad hoc network consists of n nodes which are distributed independently and uniformly in a unit-area disk, and are active (or available) independently with probability p for some constant 0

相似文献   

Mobility increases the capacity of ad hoc wireless networks

The capacity of ad hoc wireless networks is constrained by the mutual interference of concurrent transmissions between nodes. We study a model of an ad hoc network where n nodes communicate in random source-destination pairs. These nodes are assumed to be mobile. We examine the per-session throughput for applications with loose delay constraints, such that the topology changes over the time-scale of packet delivery. Under this assumption, the per-user throughput can increase dramatically when nodes are mobile rather than fixed. This improvement can be achieved by exploiting a form of multiuser diversity via packet relaying.     

A genetic algorithm-based methodology for optimizing multiservice convergence in a metro WDM network

We consider the multi-objective optimization of a multi-service arrayed-waveguide grating-based single-hop metro WDM network with the two conflicting objectives of maximizing throughput while minimizing delay. We develop and evaluate a genetic algorithm based methodology for finding the optimal throughput-delay tradeoff curve, the so-called Pareto-optimal frontier. Our methodology provides the network architecture (hardware) and the medium access control (MAC) protocol parameters that achieve the Pareto-optima in a computationally efficient manner. The numerical results obtained with our methodology provide the Pareto-optimal network planning and operation solutions for a wide range of traffic scenarios. The presented methodology is applicable to other networks with a similar throughput-delay tradeoff.     

A nontrivial lower bound on the Shannon capacities of the complements of odd cycles

This article contains a construction for independent sets in the powers of the complements of odd cycles. In particular, we show that /spl alpha/(C~/sub 2n+3/(2/sup n/))/spl ges/2(2/sup n/)+1. It follows that for n/spl ges/0 we have /spl Theta/(C~/sub 2n+3/)>2, where /spl Theta/(G) denotes the Shannon (1956) capacity of graph G.     

On the improvement of scaling laws for large-scale MANETs with network coding

This paper investigates the problem of how much benefit network coding can contribute to the network performance in terms of throughput, delay, and storage requirements for mobile ad hoc networks (MANETs), compared to when only replication, storage and forwarding are allowed in relay nodes. We characterize the throughput-delay-storage tradeoffs under different node mobility patterns, i.e., i.i.d. and random walk mobility, with and without network coding. Our results show that when random linear coding instead of replication is used in MANETs, an order improvement on the scaling laws of MANETs can be achieved. Note that previous work showed that network coding could only provide constant improvement on the throughput of static wireless networks. Our work thus differentiates MANETs from static wireless networks by the role network coding plays.     

Wireless Ad Hoc Networks: Strategies and Scaling Laws for the Fixed SNR Regime

This paper deals with throughput scaling laws for random ad hoc wireless networks in a rich scattering environment. We develop schemes to optimize the ratio lambda(n) of achievable network sum capacity to the sum of the point-to-point capacities of source-destinations (S-D) pairs operating in isolation. Our focus in this paper is on fixed signal-to-noise ratio (SNR) networks, i.e., networks where the worst case SNR over the S-D pairs is fixed independent of n. For such fixed SNR networks, which include fixed area networks as a special case, we show that collaborative strategies yield a scaling law of lambda(n)=Omega(1/n^1/3) in contrast to multihop strategies which yield a scaling law of lambda(n)=Theta(1/radicn). While networks where worst case SNR goes to zero do not preclude the possibility of collaboration, multihop strategies achieve optimal throughput. The plausible reason is that the gains due to collaboration cannot offset the effect of vanishing receive SNR. This suggests that for fixed SNR networks, a network designer should look for network protocols that exploit collaboration     

Improving the Gilbert-Varshamov bound for q-ary codes

Given positive integers q,n, and d, denote by A/sub q/(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that A/sub q/(n,d+1)/spl ges/q/sup n//V/sub q/(n,d) where V/sub q/(n,d)=/spl Sigma//sub i=0//sup d/ (/sub i//sup n/)(q-1)/sup i/ is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant /spl alpha/ less than (q-1)/q there is a positive constant c such that for d/spl les//spl alpha/n A/sub q/(n,d+1)/spl ges/cq/sup n//V/sub q/(n,d)n. This confirms a conjecture by Jiang and Vardy.     

A reduced-power channel reuse scheme for wireless packet cellularnetworks

We present a novel reduced-power channel reuse scheme to improve the spectrum efficiency in wireless packet cellular networks. The basic idea is to reduce intercellular interference and improve the capture probability by an a priori assignment of power levels of channels used in different cells. We formulate and solve an optimal channel-selection problem for our scheme. We find that the optimal policy is in a form of bang-bang control. We illustrate our channel-selection solution by a case study with uniform fairness constraint. We evaluate, via numerical analysis and simulation, both throughput and delay of the new scheme, and compare them with other schemes. We find that our scheme can achieve significant performance improvements, in terms of both the maximum throughput and throughput-delay tradeoff, over a wide range of capture ratio values     

The AWG/spl par/PSC network:a performance-enhanced single-hop WDM network with heterogeneous protection

Single-hop wavelength-division-multiplexing (WDM) networks based on a central passive star coupler (PSC) or arrayed-waveguide grating (AWG) hub have received a great deal of attention as promising solutions for the quickly increasing traffic in metropolitan and local area networks. These single-hop networks suffer from a single point of failure: if the central hub fails, then all network connectivity is lost. To address this single point of failure in an efficient manner, we propose a novel single-hop WDM network, the AWG/spl par/PSC network. The AWG/spl par/PSC network consists of an AWG in parallel with a PSC. The AWG and PSC provide heterogeneous protection for each other; the AWG/spl par/PSC network remains functional when either the AWG or the PSC fails. If both AWG and PSC are functional, the AWG/spl par/PSC network uniquely combines the respective strengths of the two devices. By means of analysis and verifying simulations we find that the throughput of the AWG/spl par/PSC network is significantly larger than the total throughput obtained by combining the throughput of a stand-alone AWG network with the throughput of a stand-alone PSC network. We also find that the AWG/spl par/PSC network gives over a wide operating range a better throughput-delay performance than a network consisting of either two load sharing PSCs in parallel or two load sharing AWGs in parallel.     

Even One-Dimensional Mobility Increases the Capacity of Wireless Networks

We study the capacity of ad hoc wireless networks with mobile nodes. The mobility model examined is one where the nodes are restricted to move along one-dimensional paths. We examine the scaling laws for the per-user throughput achievable over long time-scales, making this suitable for applications with loose delay constraints. We show that under this regime of restricted mobility, we attain a constant throughput (i.e.,$Theta(1)$) per user, which is significantly higher than the throughput of fixed networks, which decays as$O(1over sqrtn)$with the number of nodes$n$, as shown by Gupta and Kumar.     

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.     

Algebraic gossip: a network coding approach to optimal multiple rumor mongering

The problem of simultaneously disseminating k messages in a large network of n nodes, in a decentralized and distributed manner, where nodes only have knowledge about their own contents, is studied. In every discrete time-step, each node selects a communication partner randomly, uniformly among all nodes and only one message can be transmitted. The goal is to disseminate rapidly, with high probability, all messages to all nodes. It is shown that a random linear coding (RLC) based protocol disseminates all messages to all nodes in time ck+/spl Oscr/(/spl radic/kln(k)ln(n)), where c<3.46 using pull-based dissemination and c<5.96 using push-based dissemination. Simulations suggest that c<2 might be a tighter bound. Thus, if k/spl Gt/(ln(n))/sup 3/, the time for simultaneous dissemination RLC is asymptotically at most ck, versus the /spl Omega/(klog/sub 2/(n)) time of sequential dissemination. Furthermore, when k/spl Gt/(ln(n))/sup 3/, the dissemination time is order optimal. When k/spl Lt/(ln(n))/sup 2/, RLC reduces dissemination time by a factor of /spl Omega/(/spl radic/k/lnk) over sequential dissemination. The overhead of the RLC protocol is negligible for messages of reasonable size. A store-and-forward mechanism without coding is also considered. It is shown that this approach performs no better than a sequential approach when k=/spl prop/n. Owing to the distributed nature of the system, the proof requires analysis of an appropriate time-varying Bernoulli process.     

On the /spl theta/-coverage and connectivity of large random networks

Wireless planar networks have been used to model wireless networks in a tradition that dates back to 1961 to the work of E. N. Gilbert. Indeed, the study of connected components in wireless networks was the motivation for his pioneering work that spawned the modern field of continuum percolation theory. Given that node locations in wireless networks are not known, random planar modeling can be used to provide preliminary assessments of important quantities such as range, number of neighbors, power consumption, and connectivity, and issues such as spatial reuse and capacity. In this paper, the problem of connectivity based on nearest neighbors is addressed. The exact threshold function for /spl theta/-coverage is found for wireless networks modeled as n points uniformly distributed in a unit square, with every node connecting to its /spl phi//sub n/ nearest neighbors. A network is called /spl theta/-covered if every node, except those near the boundary, can find one of its /spl phi//sub n/ nearest neighbors in any sector of angle /spl theta/. For all /spl theta//spl isin/(0,2/spl pi/), if /spl phi//sub n/=(1+/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, it is shown that the probability of /spl theta/-coverage goes to one as n goes to infinity, for any /spl delta/>0; on the other hand, if /spl phi//sub n/=(1-/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, the probability of /spl theta/-coverage goes to zero. This sharp characterization of /spl theta/-coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if /spl phi//sub n/=(1+/spl delta/)log/sub 2/n. Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed.