## 3 Connectivity in Wireless Ad Hoc and Sensor Networks
### Percolation in Infinite Graphs  
Many of the results concerning connectivity of large ad hoc networks are derived from results in percolation theory. This section gives an introduction to percolation theory, and reviews some existing work related to the network connectivity studies. An introduction to theoretical aspects of percolation can be found in [28] and [29]. The notion of percolation was developed by [PERSON] [30], [PERSON] [31], and [PERSON] [32] to mathematically model the phenomenon of fluid flowing through random porous materials, e.g., water soaking a sponge. The condition of holes in the material being sufficiently connected that the entire sponge becomes wet is analogous to long-range communication being possible in a multi-hop network. An important characteristic of percolation models is the existence of phase transitions. The degree of connectedness is typically controlled by some parameter, such as the radio transmission range, and there is a critical value below which an infinite network is very fragmented, and above which it is \"partially connected\", in a sense which will be described below. Mathematically, percolation theory studies infinite random graphs, which contain an infinite set of vertices \(V\) spreading over an infinite plane. Correspondingly, percolation theory in wireless ad hoc networking areas focuses on the connectivity of infinite networks, which contain an infinite number of nodes that are distributed on an infinite plane. In an infinite plane, the probability that at least one node is isolated typically tends to 1, and thus full connectivity defined previously almost never occurs. Therefore, the literature often consider the formation of a connected component with an infinite number of nodes. This is called partial connectivity, as distinct from full connectivity, because it cannot guarantee that all nodes are connected. An infinite connected component is a collection of vertices, which is an infinite subset \(V_{1}\) of \(V\), such that there is at least one path between any arbitrary pair of nodes in \(V_{1}\). An infinite connected component corresponds to a communication network of infinitely many nodes spread over a large geographic plane. Therefore, the existence of an infinite connected component implies the capability of long distance communication via multi-hop links. Early studies of percolation constrained vertices to lie on a regular lattice. This requirement was relaxed by [PERSON] [24], who introduced continuum percolation in which vertices can lie anywhere in a continuum such as a plane. This seminal work indicated its applicability to multi-hop communications. It investigated \(\mathrm{P}(n)\), the probability that there exists a connected component containing \(n\) nodes; in particular, this was studied as \(n\) goes to infinity, giving the probability of forming an infinite connected component. It was expressed as a function of average nodal degree \(E=\lambda\pi r^{2}\), where \(\lambda\) is the density of nodes. It was shown that there is a critical value \(E_{c}\) of \(E\), such that an infinite connected component is only possible when \(E>E_{c}\). Although the exact value of \(E_{c}\) was not known, [24] showed that \(1.75\leq E_{c}\leq 17.4\). [PERSON] _et al._[33] improved the results by providing a tighter bound of \(E_{c}\) as \(2.195<E_{c}<10.526\). Besides the analytical approaches to evaluating \(E_{c}\), numerical methods [34] have also been used to obtain bounds for \(E_{c}\). These results provide some necessary conditions to construct a connected network in a large plane. As percolation theory focuses on the infinite networks and studies the existence probability of an infinite connected component, the connectivity it emphasized is indeed partial connectivity rather than full connectivity. However, as the density increases, the network becomesfully connected in the sense that the probability of a random node not being in the infinite connected component tends to 0.