Channel and question
- Input
- Unicast packets originate at fixed nodes in a planar disk of radius \(R>0\). The budget of n nodes counts sources, destinations, and relays; unused nodes are idle.
- Output
- Each packet reaches its source's chosen destination without error.
- Law
- A transmission from x to y succeeds on a subchannel if every other simultaneous transmitter z on that subchannel satisfies \(\|z-y\|\ge(1+\Delta)\|x-y\|\), where \(\Delta>0\).
- Quantity
- Transport capacity \(T_n(W,R,\Delta)\), measured in bit-meters per second.
Criterion. Supremum of the sum of delivered packet bit counts times source-to-destination Euclidean distance, divided by elapsed time, over all permitted placements and finite executions.
- The node budget n is a nonnegative integer and the total link rate satisfies \(W\ge0\).
- Node locations, each source's destination, traffic volumes, routes, transmission ranges, and schedules are optimized. Nodes do not move.
- A finite set of orthogonal subchannels has fixed nonnegative rates summing to at most W bits per second. A node sends to at most one receiver per subchannel at a time.
- Packets are routed without network coding, may wait at intermediate nodes, and traverse their hops in strictly increasing slots. Per-link bit counts obey the slot duration and subchannel rate.
- Finite executions start with the packets at their sources and count only fully delivered packets. Repetition gives a sustained transport rate. Schedules carry no information and multicast is not credited.
Current status
Main Result 1 gives matching order bounds for fixed positive guard parameter. The disk has area \(\pi R^2\); unit area means \(R=1/\sqrt\pi\). The exact finite-n optimum is not determined by these bounds.
| Result | Relation | Method | Year |
|---|---|---|---|
| Lower | \(T_n(W,R,\Delta)=\Omega_\Delta(WR\sqrt n)\) | Place transmitter–receiver pairs on a separated grid and transmit directly and simultaneously; leave unused nodes idle. Gupta–Kumar, Main Result 1 and Section III. | 2000 |
| Upper | \(T_n(W,R,\Delta)=O_\Delta(WR\sqrt n)\) | Protocol inequalities separate receiver guard disks. Area packing and Cauchy–Schwarz bound simultaneous hop distance; route triangle inequalities bound delivered distance. Gupta–Kumar, Theorem 2.1. | 2000 |
Open question
Determine the finite-n transport capacity or sharpen its leading constant.
The packing converse and explicit grid construction have different constants.
The order in n is settled for this arbitrary-placement protocol model. Random placement and physical interference require separate models.
Formal verification
The local proof gives explicit nonsharp constants for the published order result, including nonsquare node counts. These constants are from the local construction and enclosing-disk proof, not the paper's displayed constants. The model accounts for integer packet bits, causal routes, subchannels, and delivered endpoint distance.
Claims
- For n at least 4, R and Delta positive, and W nonnegative, transport capacity lies between W R sqrt(n)/(32(1+Delta)) and 2(1+Delta) W R sqrt(n)/Delta.
square-root-bounds· capacity bounds · solved · Formally proved · v1
Lean declarations (3)
CapacityAtlas.WirelessTransport.Executiondefinition
lean/CapacityAtlasForMathlib/Network/WirelessTransport/Basic.lean — Finite store-and-forward executions with protocol interference and per-link service constraints.CapacityAtlas.WirelessTransport.capacitydefinition
lean/CapacityAtlasForMathlib/Network/WirelessTransport/Basic.lean — Supremum of delivered bit-distance per unit time over node placements and executions.CapacityAtlas.Claims.wirelessTransportBoundsclaim · square-root-bounds
lean/CapacityAtlas/Claims/WirelessTransport.lean — Full local proof of the matching square-root transport-capacity bounds.
References
- Piyush Gupta and P. R. Kumar (2000). The Capacity of Wireless Networks. IEEE Transactions on Information Theory 46(2), 388–404.