Percolation Processes and Performance Analysis of Large-Scale Wireless Networks

Traditionally, performance of wireless networks has been examined with the assumption that the networks are fully connected. This approach, however, is extremely costly and sometimes impossible to achieve for large-scale wireless networks which are emerging these days. In this thesis, we analyze performance of large-scale wireless networks from a percolation perspective. We first study resilience of large-scale wireless networks to node failures. In an effort to capture the reality of practical wireless networks, in which the failure probability of a node may depend on how many neighbors it has, we develop a degree-dependent node failure model, where each node fails with a probability depending on its degree. By analyzing the problem as a degree-dependent site percolation process on random geometric graphs, we obtain analytical conditions on percolation in this model. We also study cascading failures which result from an initial failure with subsequent failures caused by redistribution of the load from failed nodes to other nearby nodes. We demonstrate that such problems can be mapped to a degree-dependent percolation process on random geometric graphs. We obtain analytical conditions on the occurrence of a cascading failure as well. We further apply this framework to the study and design of energy saving mechanisms for large-scale wireless sensor networks. We propose a fully distributed energy management algorithm, which schedules sensors' activities and guarantees the network percolated for all time. We then investigate connectivity and latency of information dissemination in large-scale wireless networks with unreliable links by modelling the problem as bond percolation processes and first passage percolation processes on random geometric graphs. Assuming zero propagation delay, we show that there are two regimes such that in one regime, the latency scales linearly with the distance between the sender and receiver, and in the other regime, the delay scales sub-linearly with the distance. Rather than assume the network is stationary, we finally study large-scale mobile wireless networks, where connectivity cannot be assessed at a fixed time instant. We develop a novel analytical technique which maps a random network with mobile nodes to a random network with stationary nodes and dynamic links. This "mobility-induced fading process" plays a key role in our analysis of connectivity and information dissemination in large-scale mobile wireless networks.