8 - Percolation and Connectivity in Wireless Networks

Summary

Introduction

In this chapter, we exploit the basic ideas of percolation theory discussed in Chapter 7 to study percolation and connectivity in wireless networks under a signal-to-interference-plus-noise ratio (SINR) model. In the SINR model, two nodes are connected if the SINR between them is larger than a threshold. The SINR model allows multiple transmitters to share the same time/frequency and consequently interfere with each other. This is in contrast to the Gilbert's disc model, where all nodes transmit in orthogonal time/frequency slots, and consequently the spatial reuse/capacity of the SINR model is significantly larger than that of the Gilbert's disc model.

We assume that the locations of the nodes of the wireless network are drawn from a Poisson point process (PPP), and study the critical density of nodes required for percolation in the SINR model. The SINR model is characterized by the interference suppression parameter γ that measures the capacity of any node to suppress the interference received from non-intended transmitters. We show that for any density larger than the critical density of an appropriate Gilbert's disc model, the SINR model percolates for a small enough γ > 0. Thus, if each node can sufficiently mitigate the interference, percolation in the Gilbert's disc model guarantees the percolation in the SINR model. Conversely, we will show that if the density is smaller than the critical density of an appropriate Gilbert's disc model, the SINR graph cannot percolate.

Next, we look at ensuring connectivity in the SINR model, where we assume that there are n nodes that are independently and uniformly distributed in a unit square. We consider the case when Col(n) separate frequency bands/time slots (called colors) are used by the n nodes for transmission and reception, where only signals belonging to the same color interfere with each other. We show that Col(n) = Θ(ln n) is necessary and sufficient for ensuring connectivity in the SINR model with high probability.