On the capacity of wireless networks: the relay case

TLDR

Gupta and Kumar determined the capacity of wireless networks under point‑to‑point coding assumptions, excluding multi‑access and broadcast codes. The authors investigate the capacity of wireless networks under a relay traffic pattern, allowing arbitrary network coding. They model a single source–destination pair with all other nodes acting as relays, construct network‑coding schemes to achieve rates, and bound performance using the max‑flow min‑cut theorem. They prove that as the number of nodes grows, the achievable rate under relay traffic with network coding scales as log n bits/s, matching the max‑flow min‑cut bound, whereas point‑to‑point coding yields a constant rate, and the result extends to fading channels and sensor networks.

Abstract

Gupta and Kumar (see IEEE Transactions an Information Theory, vol.46, no.2, p.388-404, 2000) determined the capacity of wireless networks under certain assumptions, among them point-to-point coding, which excludes for example multi-access and broadcast codes. We consider essentially the same physical model of a wireless network under a different traffic pattern, namely the relay traffic pattern, but we allow for arbitrarily complex network coding. In our model, there is only one active source/destination pair, while all other nodes assist this transmission. We show code constructions leading to achievable rates and derive upper bounds from the max-flow min-cut theorem. It is shown that lower and upper bounds meet asymptotically as the number of nodes in the network goes to infinity, thus proving that the capacity of the wireless network with n nodes under the relay traffic pattern behaves like log n bits per second. This demonstrates also that network coding is essential: under the point-to-point coding assumption considered by Gupta et al., the achievable rate is constant, independent of the number of nodes. Moreover, the result of this paper has implications' and extensions to fading channels and to sensor networks.