The influence of error propagation on the capacity of wireless networks

In this paper, it is shown that the achievable throughput capacity of wireless networks suffers from a fundamental limitation under finite node resource constraints. It is shown that this reduction results from a fundamental lower bound on the error performance of the wireless-channel model. In particular, the problem is addressed for the classic parallel-unicast problem introduced by Gupta-Kumar (2000). Under an AWGN channel-model assumption and for a pathloss exponent of α > 2, it is shown that the best available scheme for this setup achieves a throughput-capacity scaling of only Θ(n-1/2(log n)-1) per node. This is significant since an upper bound on asymptotic throughput capacity, scaling as Θ(n-1/2), was earlier shown to have been achieved by a scheme introduced by Franceschetti et. al. in 2006. The gap between achievability and the upper bound did not figure in past work on this problem, mainly due to transmission models that implicitly assume wireless nodes to have unlimited storage and encoding/decoding capabilities. Under the assumption of finite node memory, it is shown that such transmission models are unjustified in a strict information-theoretic sense. The new reduction in capacity scaling occurs from a necessity to modify the schemes used for showing achievability, in order to ensure that the failure probability is arbitrarily small. The analysis presented in this paper employs well-known sphere-packing bounds on the error probability of any block code in terms of the channel-error exponent. The result shows that for wireless networks with resource-constrained nodes, (a) the tightness of the best-known upper bound on capacity scaling still needs to be investigated, and (b) perhaps a better scheme that achieves higher capacity-scaling can be devised, but it is still an open problem.
QC 20120124