## 3 Connectivity in Wireless Ad Hoc and Sensor Networks
### Connectivity on Finite Graphs  
The effect of a phase transition to partial connectivity in infinite networks is mirrored by a similar effect for complete connectivity in large but finite networks. [PERSON] _et al._[33] considered a geometric random graph model of a wireless packet radio network with a Poisson process of nodes within a finite but large area \(A\). They extended [PERSON]'s results by studying the relationship between \(A\) and the average nodal degree \(E\) to ensure that all nodes in the network are connected. It was proved that for any \(\epsilon>0\), with transmission range \(r\) given by \(r=\sqrt{(1-\epsilon)\log A/\pi\lambda}\), the probability of being connected tends to 0 as \(A\) becomes large. It was also conjectured that given \(r=\sqrt{(1+\epsilon)\log A/\pi\lambda}\), \(\epsilon>0\), the network is almost surely connected. This conjecture would imply that to obtain asymptotic almost surely connectivity, the expected number of nodes within transmission range of an arbitrary node should grow logarithmically with network area. This result is formulated with the density fixed and the area growing; for comparison with (1), the radius required for a fixed area with increasing \(n=\lambda A\) would be  
\[r(n)=\sqrt{A(\log n+\epsilon\log n)/(\pi n)}. \tag{2}\]  
It can be seen that this conjecture, in two dimensions, is established and tightened by (1), which replaces \(\epsilon\log n\) by an arbitrary function of \(n\) that tends to infinity. [PERSON] [40] studied [PERSON] _et al._'s problem for \(1\)-D networks, and showed that the conjecture in [33] does not hold in that case. There are many cases in which \(1\)-D networks are an exception, with more stringent connectivity requirements. So far, we have considered the problem of determining the radius required to ensure a high probability of connectivity in large networks. The converse problem of estimating the probability of connectivity for a given radius is if considerable engineering interest. Consider nodes placed uniformly in a square region, with a pair of nodes connected if their distance is below a threshold, \(r_{0}\). As the number of nodes becomes large, the probability that the network is connected (or \(k\)-connected) is asymptotically the same as the probability that no node is isolated (or has degree less than \(k\)). This follows from the fundamental result in random graph theory that, for random geometric graphs of a hypercube of two or more dimensions: the minimum connectivity radius for achieving \(k\)-connectivity is exactly equal to the minimum radius for achieving a minimum nodal degree \(k\), with probability tending to 1 as the number of vertices goes to infinity [41]. This probability can be calculated by treating the node locations as a 2-D Poisson process [42]. This result holds for more general regions than squares, although not to all 2-D regions. Note that the proof in [41] (and hence the corollary in [42]) only applies to the square case. The result also does not establish almost sure connectivity for finite graphs, as suggested in [42]. The analogous problem of finding the probability of a finite \(1\)-D network being connected can be addressed directly. Considering a \(1\)-D interval with \(n\) nodes uniformly distributed within it, [PERSON] and [PERSON] [43] and [PERSON] [44; 45] studied the probability that the network is connected for a given radio range. [PERSON] and [PERSON] [46] enhanced the results by providing a closed form expression for the connectivity probability of a 1-D WSN consisting of two additional border nodes in the \(1\)-D interval. In a practical sensor deployment, it may not be realistic to assume that the nodes are identically distributed. An alternative model, studied in [47], is for the nodes to have target locations spaced uniformly, but for the true locations to have identically distributed offsets from those targets. This study quantifies how the uncertainty in the offsets increases the number of nodes which need to be deployed.