Modeling, design, and analysis on the resilience of large-scale wireless multi-hop networks

Wireless multi-hop networks are more vulnerable to failures due to topology changes, node misbehaviors, or even security attacks, which imposes a critical demand for the resilience of these networks. Motivated by this demand and the limitation of current research, we first propose a novel semi-Markov node behavior model to analyze the impacts of node misbehaviors and failures on the node connectivity. Based on the modeling, the topological survivability of wireless networks is analyzed and the asymptotic bounds of the probabilistic k-connectivity are obtained and evaluated. In order to mitigate the impact of routing misbehaviors on network performance and topological connectivity, we next design a distributed topology control protocol, called PROACtive, to achieve (suboptimal) resilient topologies upon the original non-cooperative networks. Simulation results show that our protocol maintains generated topologies k-connected with high probability and improves network goodput significantly with low communication overhead. Noticing that a full connectivity can be impractical to achieve for large-scale networks, we then focus on the resilience of large-scale networks to random failures and investigate the critical time at which the network topology decomposes from a giant component to small disconnected parts. By coupling the network devolution process with an inverse continuum percolation process, we find the scaling laws of the critical phase transition time with respects to both light-tailed and heavy-tailed node lifetime distributions and show that a network with non-uniform node distribution may be more resilient to random failures than a network with uniform node distribution. Finally, we study the connection availability from the perspective of end users with individual mobility by analyzing the stochastic properties of the times for a node to connect any neighbor and the giant component, respectively. By using the theory of Markov renewal process, stochastic geometry, and bond percolation, we obtain the asymptotic bound on the expected neighbor connection time and provide the distribution of the time to contact the giant component. Our results will shed new lights on the fundamental analysis as well as the practical design of resilient wireless multi-hop networks.