On Capacity and Delay of Wireless Networks with Node Failures
For designers of large-scale wireless ad hoc networks, this work provides fundamental limits on performance under node failures, revealing that redundancy is necessary but the capacity-delay trade-off is unaffected.
This paper characterizes the scaling laws for capacity and delay in wireless ad hoc networks with random node failures, showing both scale as Θ(√(n(1-q)/log n)). It finds that networks with failures have lower capacity than failure-free networks with the same number of non-faulty nodes, requiring at least ε(n,q)nq redundant nodes to compensate, and that the capacity-delay trade-off remains O(1) regardless of failures.
One key challenge in designing resilient large-scale wireless ad hoc networks is to understand how random node failures affect fundamental network performance. In this work, we show that both network capacity and delay scale as \scalebox{0.65}{$\textstyle Θ\left(\sqrt{\frac{n(1-q)}{\log n}}\right)$}, where $n$ is the total number of nodes and $q$ is the node failure probability. The network capacity degenerates to the classical result given by P. Gupta and P. R. Kumar when $q=0$. Based on these results, we find that even with the same number of non-faulty nodes, a network with $n$ nodes and node failure probability $q$ has lower network capacity than a failure-free network with $n(1-q)$ nodes. To compensate for the network capacity loss caused by random node failures, at least $ε(n,q) nq$ redundant nodes are required, where $ε(n,q)>1$. We further prove that the optimal trade-off between network capacity and delay remains $O(1)$ regardless of node failures, implying that high network capacity and low delay cannot be achieved simultaneously. These results demonstrate robustness against stochastic variations in wireless channels.