On the throughput capacity of random wireless networks
Massimo Franceschetti, Olivier Dousse, David N. C. Tse, Patrick Thiran · 2004
We consider the problem of how throughput in a wireless network with randomly located nodes scales as the number of users n grows. We show that randomly scattered nodes can achieve the same 1/ √ n per-node transmission rate of arbitrarily located nodes. This contrasts with previous achievable results suggesting that a 1/ √ n log n reduced rate is the price to pay for the additional randomness introduced into the system. Our results rely on percolation theory arguments. When the node density is too high the network is fully connected but generates excessive interference. In the low density regime the network looses connectivity. Percolation theory ensures that a connected backbone forms in the transition region between these two extreme scenarios. This backbone does not include all the nodes, nevertheless it is sufficiently rich in crossing paths so that it can transport the total amount of traffic. By operating the network in this transition region between order and disorder, we are able to prove our tight bound.