PaperlayerView exact revision on arXiv

Source-linked AI summary

On Capacity Scaling in Arbitrary Wireless Networks

Urs Niesen, Piyush Gupta, Devavrat Shah

arXiv:0711.2745v3cs.ITmath.IT

TL;DR

The paper asks how arbitrary node placement affects throughput scaling in extended wireless networks. It proposes cooperative schemes that work across placement patterns and path-loss regimes. The results show that placement regularity does not affect scaling for α ∈(2, 3], but does for α > 3, where an interpolating family is order optimal under adversarial placement.

  • Problem

    For extended wireless networks, the effect of arbitrary node placement on achievable-rate scaling is not well understood, although random-placement scaling is characterized.

    Source: §I · p. 1, B. Our Contributions · p. 2

  • Method

    The paper develops hierarchical relaying for arbitrary placements and a family of schemes that interpolates between cooperative communication and multi-hop according to placement regularity.

    Source: §XIII · p. 38

  • Results

    For α ∈(2, 3], the scheme is order optimal with the same rate scaling regardless of placement, while for α > 3 an interpolating scheme is order optimal under adversarial placement with a regularity constraint.

    Source: §XIII · p. 38

  • Takeaways & Limitations

    Placement regularity has no impact on achievable-rate scaling for α ∈(2, 3], but strongly affects scaling for α > 3, where simple multi-hop may not be order optimal.

    Source: §XIII · p. 38

Abstract

from arXiv · show

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\in(2,3]$ cooperative communication is order optimal, and for large path-loss exponents $\alpha > 3$ multi-hop 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 \in (2,3]$, we show that our scheme is order optimal for all node placements, and achieves exactly the same throughput scaling as in Ozgur et al. This shows that the regularity of the node placement does not affect the scaling of the achievable rates for $\alpha\in (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 "interpolate" between multi-hop 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$.

I. INTRODUCTION

The paper studies how arbitrary node placement affects achievable-rate scaling in extended wireless networks. It shows that placement regularity matters differently across path-loss regimes: low-exponent scaling is unchanged, while high-exponent schemes depend on regularity.

I. INTRODUCTION

  • For arbitrary placement, the established random-placement scaling results do not settle how node regularity affects achievable rates.The analysis considers deterministic node placements subject to a minimum-separation constraint.Source: §I · p. 1, B. Our Contributions · p. 2

A. Related Work

  • Earlier results for random placement identify a threshold: cooperative communication is order optimal for α ∈(2, 3], while multi-hop is order optimal for α > 3.For α > 3, random placement yields per-node scaling Θ(n^-1/2) achievable with multi-hop.Source: A. Related Work · p. 2

B. Our Contributions

  • For α > 3, achievable-rate scaling depends on placement regularity, and an order-optimal family interpolates between multi-hop and cooperative communication under adversarial placement.The required degree of interpolation depends on regularity; simple multi-hop may not be order optimal for any α > 3.Source: B. Our Contributions · p. 2

C. Organization

  • The paper’s results are organized around low- and high-path-loss regimes, followed by scheme descriptions, proofs, discussion, and conclusions.Sections IV and V describe the cooperative and interpolation schemes, respectively.Source: C. Organization · pp. 2–3

II. MODEL

  • The paper defines an extended network with n nodes in a region of area n and evaluates the uniformly achievable per-node rate for permutation traffic.The channel model uses path loss with exponent α > 2 and considers fast or slow fading with full channel-state information.Source: §II · p. 3

A. Low Path Loss Regime α ∈(2, 3]

  • Hierarchical relaying enables global cooperation by routing data through densely populated regions, avoiding reliance on source or destination clusters that may be isolated.The scheme is proposed for arbitrary placement with a minimum-separation requirement, under either fast or slow fading.Source: A. Low Path Loss Regime α ∈(2, 3] · p. 4
  • For α ∈(2, 3], hierarchical relaying is order optimal for arbitrary node placement and achieves the same rate scaling as random placement.The paper states that placement regularity has no impact on achievable rates in this regime.Source: B. Our Contributions · p. 2, A. Low Path Loss Regime α ∈(2, 3] · p. 5

B. High Path Loss Regime α > 3

For α > 3, achievable rates depend on placement regularity: cooperative multi-hop interpolates between local cooperation and global hierarchical relaying. Under adversarial placement, hierarchical relaying can be order optimal even where multi-hop is not.

B. High Path Loss Regime α > 3

  • For any α > 3, hierarchical relaying is order optimal under adversarial placement and can achieve a rate of order n higher than multi-hop for some placements.This contrasts with random placement, where multi-hop is order optimal for α > 3.Source: B. High Path Loss Regime α > 3 · pp. 5–6
  • Cooperative multi-hop uses cooperation at the placement’s regularity scale and multi-hop across the network, interpolating between classical multi-hop and hierarchical relaying.At d(n)=1 it becomes classical multi-hop; at d(n)=n^1/2 it becomes hierarchical relaying.Source: B. High Path Loss Regime α > 3 · pp. 5–6
  • For α > 3, cooperative multi-hop achieves at least d*(n)^(3-α)n^-1/2-β(n) when the placement is regular at resolution d*(n).The result holds under fast fading, and under slow fading with probability 1-o(1); β(n) converges to zero.Source: B. High Path Loss Regime α > 3 · p. 6
  • Theorem 5 gives placements with the same regularity for which random permutation traffic achieves essentially the same rate order as the cooperative multi-hop bound.The stated result holds with high probability; the supplied passage does not include the bound’s full expression.Source: B. High Path Loss Regime α > 3 · pp. 5–7
  • For d*(n)=n^η, regular and random placements give order n^-1/2 scaling, while completely irregular placement gives order n^(1-α/2).The examples correspond respectively to η=0, η=log log(n)/log(n), and η=1/2.Source: B. High Path Loss Regime α > 3 · pp. 6–7

IV. HIERARCHICAL RELAYING SCHEME

Hierarchical relaying routes each source-destination pair through a dense squarelet, where recursive communication enables cooperation among relay nodes. The construction uses smaller-scale schemes to support the multiple-access and broadcast operations at each level.

IV. HIERARCHICAL RELAYING SCHEME

  • Each source-destination pair uses a dense squarelet as a relay, and the scheme recurses within relay squarelets to enable joint decoding and encoding.Different relay squarelets are time-shared.Source: §IV · p. 7

A. Construction

  • At each hierarchy level, a scheme for a smaller network is used as a building block to achieve the desired rate for the larger network.The recursion terminates at a chosen level.Source: A. Construction · p. 8

1) Setting up Relays:

  • The region is divided into equal squarelets; each pair selects a dense one sufficiently far from both endpoints, with each relay serving at most n_(ℓ+1) pairs.A squarelet is dense when it contains at least n_(ℓ+1) nodes.Source: 1) Setting up Relays · p. 8

2) Multiple Access Phase:

  • In the multiple-access phase, sources split messages into parts and send each part through its assigned relay node; recursive communication shares quantized relay observations so each relay can decode.Relay nodes exchange quantized observations by organizing the demand as smaller-scale permutation traffic.Source: 2) Multiple Access Phase · p. 9
  • Relay nodes quantize their observations and send them to other relays using repeated smaller-scale permutation schemes, enabling recovery of the observations needed for decoding.The relays then decode the source messages using the exchanged estimates.Source: 2) Multiple Access Phase · p. 9
  • The broadcast phase uses a similar hierarchical construction to transmit decoded messages from relay squarelets to destination nodes.Local communication within each relay squarelet supports the cooperation needed for the multiple-access and broadcast channels.Source: §IV · pp. 7–8, 3) Broadcast Phase · p. 10

3) Broadcast Phase:

The broadcast phase uses relay cooperation to beamform messages toward their destinations, with quantized symbols exchanged locally through the hierarchy. The rate analysis accounts for both broadcast and multiple-access costs, time sharing, and recursion termination.

3) Broadcast Phase:

  • The broadcast phase uses hierarchical relaying to transpose the matrix of quantized beamformed symbols among relay nodes before wireless transmission.Each relay node obtains the symbols needed to transmit its beamformed channel symbol.Source: 3) Broadcast Phase · p. 10
  • Relay nodes beamform encoded message parts, share quantized beamformed symbols locally, then transmit them to destination nodes for decoding.The relay-squarelet cooperation organizes local information exchange as permutation traffic matrices and uses the hierarchy to move the quantized symbols between relays.Source: 3) Broadcast Phase · p. 10
  • Each destination decodes part of its source’s message from the received channel output associated with its relay transmission.The relay transmissions occur at designated time instances following the preceding MAC and local-cooperation phases.Source: 3) Broadcast Phase · pp. 10–11

4) Spatial Re-Use and Termination of Recursion:

  • The recursive hierarchy terminates at level L, where transmissions among n_L nodes use TDMA and multiple regions operate simultaneously.The construction chooses L large enough and uses spatial reuse at that final scale.Source: 4) Spatial Re-Use and Termination of… · p. 11

B. Achievable Rates

  • The rate analysis combines MAC and BC transmission times recursively, then selects the branching factor and hierarchy depth to control the loss term.The derivation gives a lower bound on the hierarchical-relaying per-node rate.Source: B. Achievable Rates · pp. 11–13

V. COOPERATIVE MULTI-HOP SCHEME

The cooperative multi-hop scheme builds a square-grid communication graph and implements each neighboring-square edge with hierarchical relaying. Messages are then routed across the graph using multi-hop communication.

V. COOPERATIVE MULTI-HOP SCHEME

  • Each edge between neighboring d(n)-squares is implemented with hierarchical relaying, forming the cooperative multi-hop communication graph.The figure depicts the full square of sidelength √n and the dashed squares of sidelength d(n).Source: §V · p. 13, Figure 4 · p. 14
  • Messages travel between their source and destination squares by multi-hop routing over adjacent-square edges.The route spans distance √n with hop length d(n), and each hop uses hierarchical relaying over distance d(n).Source: §V · p. 14
  • Each graph edge has capacity b(n)d(n)^(4−α) and supports roughly n^(1/2)/d(n) source-destination pairs, yielding a per-node rate from edge capacity and traffic load.The passage gives the per-node rate expression after accounting for the number of pairs sharing an edge.Source: §V · p. 14

VI. ANALYSIS OF THE HIERARCHICAL RELAYING SCHEME

The analysis establishes hierarchical relaying under stated placement, power, and channel assumptions. Its relay setup uses dense squarelets and decomposes permutation traffic into a bounded number of balanced schedules.

VI. ANALYSIS OF THE HIERARCHICAL RELAYING SCHEME

  • The analysis considers hierarchy levels under fast fading, with bounded-power noise that may include interference and need not be Gaussian.The relay-squarelet power constraint is chosen to preserve the overall average power constraint under time sharing.Source: §VI · pp. 14–15

A. Setting up Relays

  • With minimum separation r_min, each squarelet has a bounded node count and at least K_2·2^(−ℓ)γ(n) squarelets are dense.The paper notes this constant-fraction density is the only consequence of minimum separation used for Theorem 1.Source: A. Setting up Relays · p. 15
  • Relay-squarelet selection spreads traffic across dense squarelets, limits each squarelet’s load, and keeps sources and destinations at least √(2a_(ℓ+1)) away.These constraints define the permitted schedules used to relay a permutation traffic matrix.Source: A. Setting up Relays · p. 16
  • For all sufficiently large n, with the threshold independent of ℓ, every permutation traffic matrix λ(nℓ) can be decomposed into K3·2^ℓ schedules.Source: A. Setting up Relays · p. 17

B. Multiple Access Phase

The multiple-access phase sends message parts from sources to relay nodes, which quantize their observations and exchange them locally. The analysis models this as an induced MAC and establishes achievable rate and quantization requirements.

B. Multiple Access Phase

  • Each source splits its message into parts for relay nodes, which quantize their observations and exchange them through a uniform local traffic pattern.The local pattern is expressed as a sum of permutation traffic matrices, with a fraction of the traffic sent according to each matrix.Source: B. Multiple Access Phase · p. 18
  • The induced MAC has n_(ℓ+1) single-antenna transmitters and one relay-squarelet receiver with n_(ℓ+1) antennas.The analysis assumes a scheme is available to send quantized observations to the dedicated relay node.Source: B. Multiple Access Phase · p. 18
  • Under uncorrelated relay noise and per-node power P_ℓ(n) ≤ n^(−1), the lemma gives an achievable per-source rate and bounds relay quantization bits.The stated quantization bound is at most K_5 bits per n_(ℓ+1) total message bits sent by the sources.Source: B. Multiple Access Phase · p. 18
  • The analysis obtains a per-node communication rate of at least K_4P_ℓ(n)n_(ℓ+1)a_ℓ^(−α/2) using constant-rate quantizers.The result follows by applying the quantized-channel lemma to the source-to-relay channel and matched-filter observations.Source: B. Multiple Access Phase · pp. 18–19

C. Broadcast Phase

The broadcast phase uses relay-squarelet nodes to beamform encoded messages, quantize them, and distribute them locally before transmission to destinations. The construction accounts for unavailable future channel state at encoding time by reordering transmissions across quantized channel states.

C. Broadcast Phase

  • Quantizing the encoded message samples requires at most K7(ℓ+1) log(n) bits at each relay per n^(ℓ+1) total message bits received by the destinations.The total message bits are summed across the n^(ℓ+1) destination nodes.Source: C. Broadcast Phase · p. 21
  • Because future channel state is unknown when encoding, the scheme reorders transmissions and cycles through quantized channel states; destinations reorder received samples using full CSI.The channel-state quantization is used to choose which encoded-message samples are sent in each time slot.Source: C. Broadcast Phase · p. 22
  • Relay-squarelet nodes beamform encoded messages for their destinations, quantize the resulting vector, distribute it within the squarelet, and then transmit it to destination nodes.The induced local traffic is uniform and can be decomposed into permutation traffic matrices.Source: C. Broadcast Phase · pp. 21–22
  • The analysis verifies that the quantized relay signal satisfies each relay node’s power constraint.The power constraint is established for the relay squarelet in the calculation preceding the broadcast bound.Source: C. Broadcast Phase · p. 23

VII. PROOF OF THEOREM 1

The proof of Theorem 1 is divided into fast-fading and slow-fading cases.

VII. PROOF OF THEOREM 1

  • The fast-fading proof is given in Section VII-A, and the slow-fading proof in Section VII-B.The two cases form the separate parts of the proof of Theorem 1.Source: §VII · p. 24

A. Fast Fading

For fast fading, the proof validates the power and interference assumptions for one hierarchy level, then uses them to bound the rate of the full hierarchy. Spatial reuse and time-sharing costs are included in the level-by-level rate analysis.

A. Fast Fading

  • Spatial reuse separates active relay squarelets so their interference is stationary, ergodic, additive, and bounded independently of n.The squarelets are partitioned into four subsets whose members are separated by at least √(a_(ℓ+1)).Source: A. Fast Fading · p. 25
  • The proof establishes that spatial-reuse interference and the power constraints satisfy the conditions needed to apply the one-level MAC and BC lemmas.The power constraint is shown to hold for sufficiently large n, independent of the hierarchy level.Source: A. Fast Fading · pp. 24–26
  • The hierarchy’s rate lower bound combines MAC and BC channel-use costs with relay reuse and time-sharing across squarelets.The proof applies the level-by-level recursion through L levels and then uses the stated choice of γ(n) and L(n).Source: A. Fast Fading · pp. 26–27
  • For δ > 0, the n log^(δ−1/2)(n) term dominates in the final bound.This dominance completes the fast-fading proof of Theorem 1.Source: A. Fast Fading · p. 27

B. Slow Fading

For slow fading, the scheme routes each pair over multiple separated relay squarelets, since any one relay’s channel may be in a bad state. With high probability, enough relays support the target rate to preserve the fast-fading order rate across hierarchy levels.

B. Slow Fading

  • Each pair uses multiple distinct, separated dense relay squarelets rather than relying on a single relay squarelet.The construction finds K2^(−ℓ−1)γ(n) such squarelets for each pair.Source: B. Slow Fading · p. 27
  • The extra time-sharing loss from using multiple relays is small under the chosen γ(n).The loss is at most a factor 2γ(n) greater than in Lemma 7.Source: B. Slow Fading · p. 28
  • With probability 1−o(1), at least one quarter of each pair’s relay squarelets support at least 1/64 of the fast-fading achievable rate, yielding at least 1/256 of its per-node rate.The conclusion applies to every source-destination pair on every hierarchy level.Source: B. Slow Fading · p. 28
  • Conditioned on channel gains between active relay squarelets, each candidate relay succeeds with probability at least 1/2, and the success events are independent across the scheduled relays.The proof uses disjoint channel-gain sets to establish conditional independence, then a Chernoff bound for the number of successful relays.Source: B. Slow Fading · p. 29
  • With probability 1−o(1), the same order rate as in fast fading is achieved at every hierarchy level, including the final TDMA level.At the final level, phase fading leaves received signal power dependent on distance rather than the fading realization.Source: B. Slow Fading · p. 30

VIII. PROOF OF THEOREM 2

The proof sharpens the converse in by bounding cooperative MIMO capacity, then applies a cut-set argument to the arbitrary-placement network. The argument accommodates the minimum-separation constraint by adding traffic-free helper nodes to the grid.

VIII. PROOF OF THEOREM 2

  • The converse starts with a MIMO-capacity upper bound for disjoint node sets, expressed through inter-set distances and normalized channel gains.The proof generalizes and sharpens the converse in.Source: §VIII · p. 30
  • The MIMO-capacity argument applies to fast and slow fading, and the placement conditions needed for its use follow from minimum separation and the added grid nodes.Minimum separation bounds the number of nodes in constant-area regions; the added nodes ensure at least one node in each square of sidelength d.Source: §VIII · p. 32
  • For arbitrary placement, a vertical cut can divide the network into two parts, each containing Θ(n) nodes and, with probability 1 − o(1), Θ(n) crossing source-destination pairs.The proof adds a traffic-free node to each grid square of sidelength d = √(2 log(n)); this increases the node count by less than a factor of 2.Source: §VIII · p. 32
  • The cut-set bound then limits the aggregate rate across the cut, using the number of crossing pairs to bound the achievable per-node rate.The proof invokes the MIMO-capacity lemma to obtain the cut bound.Source: §VIII · pp. 30, 32

IX. PROOF OF THEOREM 3

The proof uses a placement with two separated node clusters and traffic crossing between them to contrast multi-hop performance with a cut-based converse. The resulting bound applies for every α > 2.

IX. PROOF OF THEOREM 3

  • Multi-hop traffic crossing the gap is rate-limited even without interference from other nodes.At least one hop must cross the gap between the two clusters.Source: §IX · p. 33
  • For all α > 2, the proof combines a multi-hop bound requiring a hop to cross the gap between the left and right clusters with a cut-set bound obtained by applying Lemma 12.Source: §IX · p. 33

X. PROOF OF THEOREM 4

The proof constructs a cooperative multi-hop scheme whose local cooperation scale is set by node-placement regularity. It combines hierarchical relaying within regions with routing between them, with rates established for fast and slow fading.

X. PROOF OF THEOREM 4

  • A placement that is μ-regular at resolution d(n) supports a cooperative multi-hop per-node rate of at least d(n)^(3−α)n^(−1/2−β(n)) as n → ∞.The proof uses the smallest admissible d(n) to obtain its result.Source: §X · p. 33
  • The scheme performs cooperative communication locally at scale d(n) and multi-hop communication globally across the extended network.It groups adjacent d(n)-squares into larger regions and partitions those regions into four time-shared subsets; within each region, λ1 and λ2 carry traffic across the top-bottom and left-right halves.Source: §X · pp. 33–34, Figure 6 · p. 34
  • Within each larger region, hierarchical relaying works because the region contains at least 4μd(n)^2 nodes and interference from simultaneously active regions is bounded.The resulting fast-fading rate is given by the theorem-based construction; the passage does not state its value.Source: §X · p. 34
  • Shifting the larger-region partition and time-sharing creates a communication graph on d(n)-squares whose edges can carry traffic simultaneously.The graph connects squares adjacent within either the original or shifted larger regions; the proof also gives slow-fading guarantees with probability 1 − o(1).Source: §X · pp. 34–35
  • For the regime using simple multi-hop between adjacent squares, the proof bounds achievable rates under either fast or slow fading and routes over the square graph.Each square contains at most K1d(n)^2 nodes by minimum separation, which is used in the routing analysis.Source: §X · p. 35

XI. PROOF OF THEOREM 5

For α > 3, the proof establishes a cut-based bound under a regularity constraint, and the discussion clarifies the scheme's assumptions and scope. The conclusion distinguishes small- and large-path-loss regimes: arbitrary placement leaves small-α scaling unchanged, but affects optimal communication at large α.

XI. PROOF OF THEOREM 5

  • For α > 3, a cut between the two clusters and Lemma 12 yield the bound used to prove Theorem 5.The setup assumes a 1/2-regular placement at resolution d*(n) and Θ(n) source-destination pairs crossing between the clusters with probability 1 − o(1).Source: §XI · p. 36

A. Full CSI Assumption

  • The converse assumes full channel-state information, while achievability needs only 2-bit quantization of channel state at all nodes to retain the same scaling behavior.The paper says quantized-state beamforming causes only a constant-factor rate loss.Source: A. Full CSI Assumption · p. 36

B. Burstiness of Hierarchical Relaying Scheme

  • The scheme's time-domain burstiness creates a high peak-to-average power ratio, but CDMA or OFDM can distribute the burstiness across parallel channels.The paper presents these alternatives as ways to avoid high peak-to-average power in the time domain.Source: B. Burstiness of Hierarchical Relaying… · p. 36

C. Dense Networks

  • Rescaling power by n^(−α/2) maps a dense network to an extended-network model, yielding linear per-node rate scaling for hierarchical relaying.The discussion obtains the dense-network result by taking the limit α → 2.Source: C. Dense Networks · p. 36

D. Minimum-Separation Requirement

  • The minimum-separation requirement is sufficient but not necessary for Theorem 1; a sufficient alternative is that a constant fraction of squarelets are dense.The discussion states that this alternative holds with high probability for uniformly random node placement.Source: D. Minimum-Separation Requirement · p. 37

E. Comparison with [8]

  • Unlike 's joint decoding, this scheme uses matched filters and transmit beamforming to reduce relay decoding and encoding to single-user problems while retaining the same scaling.The scheme in can also be modified to use matched-filter receivers.Source: E. Comparison with [8] · p. 37
  • The scheme gains multiple-antenna capability by relaying through dense squarelets, rather than directly connecting source and destination squarelets as in.The added choice of relay squarelet also lets the result extend to slow-fading channels.Source: E. Comparison with [8] · p. 37

XIII. CONCLUSIONS

  • For α ∈ (2, 3], placement regularity does not change achievable-rate scaling; for α > 3, regularity affects scaling and less regular placements may require cooperative schemes for optimality.The proposed scheme interpolates between multi-hop and hierarchical cooperation and is order optimal under the stated adversarial-placement regularity constraint.Source: §XIII · p. 38
Loading 0711.2745v3…